cache missing

# Interpolation

# Data and Interpolating Functions

# Lagrange interpolation

(x1,y1),(x2,y2),(x3,y3)P2(x)=y1(x−x2)(x−x3)(x1−x2)(x1−x3)+y2(x−x1)(x−x3)(x2−x1)(x2−x3)+y3(x−x1)(x−x2)(x3−x1)(x3−x2) \begin{align} & (x_1,y_1), (x_2,y_2), (x_3,y_3) \\\\ & P_2(x) = y_1 \frac{(x-x_2)(x-x_3)}{(x_1-x_2)(x_1-x_3)} + y_2 \frac{(x-x_1)(x-x_3)}{(x_2-x_1)(x_2-x_3)} + y_3 \frac{(x-x_1)(x-x_2)}{(x_3-x_1)(x_3-x_2)} \end{align}

# Newton's divided differences

f[xk]=f(xk)f[xkxk+1]=f[xk+1]−f[xk]xk+1−xkf[xkxk+1xk+2]=f[xk+1xk+2]−f[xkxk+1]xk+2−xkf[xkxk+1xk+2xk+3]=f[xk+1xk+2xk+3]−f[xkxk+1xk+2]xk+3−xk \begin{align} f[x_k] &= f(x_k) \\ f[x_k\,x_{k+1}] &= \frac{f[x_{k+1}]-f[x_k]}{x_{k+1} - x_k} \\ f[x_k\,x_{k+1}\,x_{k+2}] &=\frac{f[x_{k+1}\,x_{k+2}] - f[x_k\,x_{k+1}]}{x_{k+2} - x_k} \\ f[x_k\,x_{k+1}\,x_{k+2}\,x_{k+3}] &= \frac{ f[x_{k+1}\,x_{k+2}\,x_{k+3}] - f[x_k\,x_{k+1}\,x_{k+2}] }{ x_{k+3} - x_k } \end{align}
P(x)=f[x1]+f[x1x2](x−x1)+f[x1x2x3](x−x1)(x−x2)+f[x1x2x3,x4](x−x1)(x−x2)(x−x3)+⋯+f[x1⋯xn](x−x1)(x−x2)⋯(x−xn−1) \begin{align} P(x) = f[x_1] &+ f[x_1\,x_2] (x- x_1) \\ & + f[x_1\,x_2\,x_3] (x - x_1)(x - x_2) \\ & + f[x_1\,x_2\,x_3,x_4] (x - x_1)(x - x_2)(x - x_3) \\ & + \cdots \\ & + f[x_1\,\cdots\,x_n] (x - x_1)(x - x_2)\cdots(x - x_{n-1}) \end{align}
x1f[x1]f[x1x2]x2f[x2]f[x1x2x3]f[x2x3]x3f[x3] \begin{array}{c|ccc} x_1 & f[x_1] \\ && f[x_1\,x_2] \\ x_2 & f[x_2] && f[x_1\,x_2\,x_3]\\ & & f[x_2\,x_3] \\ x_3 & f[x_3] \end {array}

# How many degree d polynomials pass through n points

points:(−1,−5),(0,−1),(2,1),(3,11)P3(x)=−5+4(x+1)−(x+1)x+(x+1)x(x−2)P4(x)=P3(x)+c1(x+1)x(x−2)(x−3)P5(x)=P3(x)+c2(x+1)x2(x−2)(x−3)c1≠0,c2≠0 \begin{align} & points:(-1,-5),(0,-1),(2,1),(3,11) \\\\ & P_3(x) = -5 + 4(x+1) - (x+1)x + (x+1)x(x-2) \\ & P_4(x) = P_3(x) + c_1(x+1)x(x-2)(x-3) \\ & P_5(x) = P_3(x) + c_2(x+1)x^2(x-2)(x-3) \\\\ & c_1\ne 0, c_2\ne 0 \end{align}

# Representing functions by approximating polynomials

a major use of polynomial interpolations is to replace evaluation of a complicated function by evaluation of a polynomial, which involves only elementary computer operation like addition , subtraction , and multiplication . Think of this as a form of compression

# Interpolation error

# Interpolation error formula

interpolation error=f(x)−P(x)=(x−x1)(x−x2)…(x−xn)n!f(n)(c) \text{interpolation error} = f(x) - P(x) = \frac{ (x-x_1)(x-x_2)\dots(x-x_n) }{ n! }f^{(n)}(c)

where c lies between the smallest and largest of the numbers x,x1,⋯,xnx,x_1,\cdots,x_n , and P(x) is the (degree n - 1 or less) interpolating polynomial fitting the n points (x1,y1),⋯,(xn,yn)(x_1,y_1),\cdots,(x_n,y_n)

# Runge phenomenon (opens new window)

Runge's phenomenon is a problem of oscillation at the edges of an interval that occurs when using polynomial interpolation with polynomials of high degree over a set of equispaced interpolation points. It was discovered by Carl David Tolmé Runge (1901) when exploring the behavior of errors when using polynomial interpolation to approximate certain functions. The discovery was important because it shows that going to higher degrees does not always improve accuracy.

# Chebyshev interpolation

# Chebyshev's theorem

the choice of real numbers −1≤x1,⋯,xn≤1-1 \le x_1,\cdots,x_n \le 1 that makes the value of

max⁡−1≤x≤1∣(x−x1)⋯(x−xn)∣\max_{-1\le x \le 1}|(x-x_1)\cdots(x-x_n)|

as small as possible is xi=cos⁡(2i−1)π2nx_i = \cos\frac{(2i-1)\pi}{2n}

We will call the interpolating polynomial that uses the Chebyshev roots as base points the Chebyshev interpolating polynomial

# Change of interval

on the interval [a,b][a, b]

xi=a+b2+b−a2cos⁡(2i−1)π2n x_i = \frac{a+b}{2} + \frac{b-a}{2}\cos\frac{(2i-1)\pi}{2n}
∣(x−x1)⋯(x−xn)∣≤(b−a2)n2n−1 |(x - x_1)\cdots (x - x_n)| \le \frac{(\frac{b-a}{2})^n}{2^{n-1}}

# cubic splines

the idea of splines is to use several formulas , each a low-degree polynomial , to pass through the data points

linear splines lack smoothness , Cubic splines are meant to address this shortcoming of linear splines

the neighboring pieces SiS_i and Si+1S_{i+1} of the spline to have the same zeroth, first ,and second derivatives when evaluated at the knots

# Properties of splines

Sn−1(x)=yn−1+bn−1(x−xn−1)+cn−1(x−xn−1)2+dn−1(x−xn−1)3on[xn−1,xn] S_{n-1}(x) = y_{n-1} + b_{n-1}(x-x_{n-1}) + c_{n-1}(x-x_{n-1})^2 + d_{n-1}(x-x_{n-1})^3 \text{on}[x_{n-1},x_n]

Property 1: Si(xi)=yiS_i(x_i) = y_i and Si(xi+1)=yi+1S_i(x_{i+1}) = y_{i+1} for i=1,⋯,n−1i = 1,\cdots,n-1

Property 2: Si−1′(xi)=Si′(xi)S_{i-1}^{\prime}(x_i) = S_i^{\prime}(x_i) for i=2,⋯,n−1i = 2,\cdots,n-1

Property 3: Si−1′′(xi)=Si′′(xi)S_{i-1}^{\prime\prime}(x_i) = S_i^{\prime\prime}(x_i) for i=2,⋯,n−1i = 2,\cdots,n-1

there totally (n−1)+(n−2)+(n−2)(n-1) + (n-2) + (n-2) equations provided by these three properties ,but the unknown coefficients count is 3n−33n-3

Property 4 for Natural spline: S1′′(x1)=Sn−1′′(xn)=0S_1^{\prime\prime}(x_1) = S_{n-1}^{\prime\prime}(x_n) = 0

# Endpoint conditions

# Natural spline

S1′′(x1)=Sn−1′′(xn)=0 S_1^{\prime\prime}(x_1) = S_{n-1}^{\prime\prime}(x_n) = 0

# Curvature-adjusted cubic spline

setting S1′′(x1)S_1^{\prime\prime}(x_1) and Sn−1′′(xn)S_{n-1}^{\prime\prime}(x_n) to arbitrary values ,chosen by the user

# Clamped cubic spline

first derivatives S1′(x1)S_1^{\prime}(x_1) and Sn−1′(xn)S_{n-1}^{\prime} (x_n) that are set to user-specified values

# Parabolically terminated cubic spline

the first and last parts of spline , S1S_1 and Sn−1S_{n-1} are forced to be at most degree 2,by specifying that d1=dn−1=0d_1 = d_{n-1} = 0

# Not-a-knot cubic spline

d1=d2d_1 = d_2 and dn−2=dn−1d_{n-2} = d_{n-1}

# Bézier curves (opens new window)

Bézier splines are appropriate for cases where corners (discontinuous first derivatives) and abrupt changes in curvature (discontinuous second derivatives) are occasionally needed

{x(t)=1+6t2−5t3y(t)=1+6t−6t2+t3t∈[0,1] \begin{cases} x(t) = 1 + 6t^2 - 5t^3 \\ y(t) = 1 + 6t - 6t^2 + t^3 \end{cases} \,\, t \in [0,1]

← Least Squares →