Chapter4-Polynomial Interpolation

Polynomial Interpolation

Lagrange Interpolation

Assume that n data points $(x_1,y_1),\cdots ,(x_n,y_n)$ are given, and that we would like to find an interpolating polynomial. There is an explicit formula, called the Lagrange interpolating formula, for writing down a polynomial of degree $d=n-1$ that interpolates the points. For example, suppose that we are given three points $(x_1,y_1),(x_2,y_2),(x_3,y_3)$ . Then the polynomial:

$$\begin{array}{r}{P}_2\left(x\right)=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{array}$$

The main theorem behind polynomial interpolation is that:

Let $(x_1,y_1),\cdots ,(x_n,y_n)$ be $n$ points in the plane with distinct $x_i$ . Then there exists one and only on polynomial $P$ of degree $n-1$ or less that satisfies $P(x_i)=y_i$ for $i=1,\cdots ,n$

Example of Lagrange Interpolation

Example of Lagrange Interpolation

Newton’s Divided Differences For Interpolation.

Properties of Newton's divided differences

example of Newton's Interpolation

Error of Polynomial Interpolation

Assume that $P(x)$ is the (degree $n$ or less) interpolating polynomial fitting the $n$ points $(x_0,y_0),\cdots ,(x_n,y_n)$ . The interpolation error is

$$f(x)-P(x)=\frac{1}{(n+1)!}{f}^{(n+1)}(c)\prod _{i=0}^n(x-x_i)$$

Where $c\in (a,b)$

Chebyshev Interpolation

It is common to choose the base points xi for interpolation to be evenly spaced. In many cases, the data to be interpolated are available only in that form—for example, when the data consist of instrument readings separated by a constant time interval. It turns out that the choice of base point spacing can have a significant effect on the interpolation error. Chebyshev interpolation refers to a particular optimal way of spacing the points.

The motivation for Chebyshev interpolation is to improve control of the maximum value of the interpolation error.

Chebyshev Interpolation Nodes

On the interval $[a,b]$ ,

$$x_i=\frac{b+a}{2}+\frac{b-a}{2}\cos \frac{(2i+1)\pi }{2n+1}$$

For $i=0,2,\cdots ,n$ . The inequality

$$\begin{array}{rl}|(x-x_0)\cdots (x-x_n)|& \le \frac{{\left(\frac{b-a}{2}\right)}^{n+1}}{2^n}\\ f(x)-P(x)& ⩽\frac{1}{(n+1)!}{f}^{(n+1)}(c)\frac{{\left(\frac{b-a}{2}\right)}^{n+1}}{2^n}\end{array}$$

Holds on $[a,b]$ .

Example of Chebyshev Interpolation Error

Example of Chebyshev Interpolation Error

Hermite Interpolation

In real world problem, we not only want the interpolation function $p(x)$ go through all the points, but also want its differentials satisfy some value boundary conditions. Like find $P(x)$ that satisfies $P(x_i)=f(x_i),p^{{}^{\prime }}(x_i)=f^{{}^{\prime }}(x_i),p^{{}^{\prime \prime }}(x_i)=f^{{}^{\prime \prime }}(x_i)$

Hermite Interpolation

Hermite Interpolation With Lagrange Method

For given $n$ points ${\left\{x_i\right\}}_{i=0}^n$ , find polynomial $P(x)$ that satisfies: $P\left(x_i\right)=$ $f\left(x_i\right),P^{\prime }\left(x_i\right)=f^{\prime }\left(x_i\right)$ 。

$$P(x)=\sum _{i=0}^{2n+1}{a}_i{\phi }_i(x)=\sum _{i=0}^n{a}_i{A}_i(x)+\sum _{i=0}^n{b}_i{B}_i(x)$$ $$\left[\begin{array}{cccccc}{A}_0\left(x_0\right)& \cdots & A_n\left(x_0\right)& B_0\left(x_0\right)& \cdots & B_n\left(x_0\right)\\ ⋮& \cdots & ⋮& ⋮& \cdots & ⋮\\ A_0\left(x_n\right)& \cdots & A_n\left(x_n\right)& B_0\left(x_n\right)& \cdots & B_n\left(x_n\right)\\ A_0^{\prime }\left(x_0\right)& \cdots & A_n^{\prime }\left(x_0\right)& B_0^{\prime }\left(x_0\right)& \cdots & B_n^{\prime }\left(x_0\right)\\ ⋮& \cdots & ⋮& ⋮& \cdots & ⋮\\ A_0^{\prime }\left(x_n\right)& \cdots & A_n^{\prime }\left(x_n\right)& B_0^{\prime }\left(x_n\right)& \cdots & B_n^{\prime }\left(x_n\right)\end{array}\right]\left[\begin{array}{c}{a}_0\\ ⋮\\ a_n\\ b_0\\ ⋮\\ b_n\end{array}\right]=\left[\begin{array}{c}f\left(x_0\right)\\ ⋮\\ f\left(x_n\right)\\ f^{\prime }\left(x_0\right)\\ ⋮\\ f^{\prime }\left(x_n\right)\end{array}\right]$$

Solving it we have:

$$\begin{array}{rl}{A}_i\left(x\right)& =\left[1-2l_i^{\prime }\left(x_i\right)\left(x-x_i\right)\right]{\left[l_i\left(x\right)\right]}^2\\ B_i\left(x\right)& =\left(x-x_i\right){\left[l_i\left(x\right)\right]}^2\\ where{l}_i\left(x\right)& =\prod _{j=0}^n\frac{x-x_j}{x_i-x_j}\end{array}$$

example of 2-order Hermite Interpolation

2-point Hermite Interpolation

Hermite Interpolation with Newton’s Differences

Hermite interpolation with newton's differences

See the example below.

example of Hermite interpolation with Newton's differences

example of Hermite interpolation with Newton's differences

Hermite Interpolation Error

Hermite Interpolation Error

Natural Cubic Splines Interpolation

Splines represent an alternative approach to data interpolation. In polynomial interpolation, a single formula, given by a polynomial, is used to meet all data points. The idea of splines is to use several formulas, each a low degree polynomial, to pass through the data points.

Properties of Splines

$$\begin{array}{rl}& S_i\left(x_i\right)=f\left(x_i\right),S_i(x_{i+1})=f(x_{i+1})\\ & S_i(x_{i+1})=f(x_{i+1})\mathrm{for}i=0,\dots ,n-1.\\ & S_i^{\prime }(x_{i+1})=S_{i+1}^{\prime }(x_{i+1})\mathrm{for}i=0,\dots ,n-2.\\ & S_i^{\prime \prime }(x_{i+1})=S_{i+1}^{\prime \prime }(x_{i+1})\mathrm{for}i=0,\dots ,n-2.\end{array}$$

For all $S_i$ :

$$S_i\left(x\right)=f\left(x_i\right)+b_i\left(x-x_i\right)+c_i{\left(x-x_i\right)}^2+d_i{\left(x-x_i\right)}^3\left(i=0,...,n-1\right)$$

Example

example of natural cubic splines interpolation

给定三个插值节点：(-1,1), (1,1), (2,4)，设插值函数为 S (x)。

1. 对应每一个小区间内的插值函数： $S_i\left(x_i\right)=f\left(x_i\right),S_i(x_{i+1})=f(x_{i+1})$
2. 除边界点外每个节点的一阶导数： $S_i^{\prime }(x_{i+1})=S_{i+1}^{\prime }(x_{i+1})$
3. 除边界点每个节点的二阶导数: $S_i^{\prime \prime }(x_{i+1})=S_{i+1}^{\prime \prime }(x_{i+1})$
4. 边界条件： $S_0^{\prime \prime }(x_0)=0S_{n-1}^{\prime \prime }(x_n)=0$
5. 构造插值函数 $S_0(x)=a_0(x+1{)}^3+b_0(x+1{)}^2+c_0(x+1)+1,-1⩽x⩽1$

$S_1(x)=a_1(x-1{)}^3+b_1(x-1{)}^2+c_1(x-1)+1,1⩽x⩽2$

7. 解方程组，将以上节点代入方程组解得结果为： $a_0=-1,b_0=0,c_0=1/4;a_1=2,b_1=3/2,c_1=-1/2$