Interpolation & Polynomial Approximation
插值多项式 | Interpolating Polynomial¶
Lagrange插值多项式 | Lagrange Interpolating Polynomial¶
Inspired by 加权平均.
There exists and only exists a \(n\)th Lagrange interpolating polynomial (拉格朗日基函数)
such that for each pair of given points \((x_i, y_i)\), \(i = 0, 1,2,\cdots n\), we have \(y_i = L_n(x_i)\).
Here we can consider \(l_i(x)\) as a base of a linear space \(\mathcal{P}_n(x)\), and it can be displayed by natural base \(1, x, x^2, \cdots x^n\). To be more specific,
readers can prove the above \(n+1\) polynomials are linearly irrelevant.
Another form of \(l_i(x)\)
If we denote \(\omega(x)=\prod\limits_{k=0}^{n}(x-x_k)\), so the numerator of \(l_i(x)\) is
and its demunerator is
so
which satisfies
Q1. Calculate the Lagrange polynomial that interpolates the following 3 points.
| \(x_i\) | 1 | 2 | 4 |
|---|---|---|---|
| \(f(x_i)\) | 8 | 1 | 5 |
In fact, if we assume \(P_n(x) = \sum\limits_{i=0}^{n}a_ix^i\)(natural base), and to get the parameters \(\{a_i\}\) such that \(P_n(x_i) = y_i\), we have to solve the following linear system
which is a little tedious.
Neville方法 | Neville's Method¶
There is another way to express polynomial, which is also a weighted average.
An interpolation polynomial for a set of points \(A =\{x_0, x_1, \cdots x_n \}\) can be expressed by two polynomials that interpolate \(A\) \ \(\{ x_i\}\) and \(A\) \ \(\{ x_j\}\). That is,
where \(P_{0,1,\cdots,i-1,i+1,\cdots,n}(x)\) and \(P_{0,1,\cdots,j-1,j+1,\cdots,n}(x)\) denotes the polynomial that interpolates \(A\) \ \(\{ x_i\}\) and \(A\) \ \(\{ x_j\}\) respectively.
For the first item, we have
Q2. Get the polynomial \(p_3(x)\) that interpolates the following 4 points and estimate \(f(5)\) by calculate \(p_3(5)\).
| \(x_i\) | 2 | 4 | 6 | 8 |
|---|---|---|---|---|
| \(f(x_i)\) | -8 | 0 | 8 | 64 |
It is a little tedious if we write the form of the polynomial and then substitute \(5\) in. It is more suitable to list a table.
| \(x\) | \(f(x)\) | \(p_1(5)\) | \(p_2(5)\) | \(p_3(5)\) |
|---|---|---|---|---|
| 2 | -8 | |||
| 4 | 0 | \(\frac{1}{(4-2)}\left|\begin{array}{cc} (5-2) & -8 \\ (5-4) & 0 \end{array}\right|=4\) | ||
| 6 | 8 | \(\frac{1}{(6-4)}\left|\begin{array}{cc} (5-4) & 0 \\ (5-6) & 8 \end{array}\right|=4\) | \(\frac{1}{(6-2)}\left|\begin{array}{cc} (5-2) & 4 \\ (5-6) & 4 \end{array}\right|=4\) | |
| 8 | 64 | \(\frac{1}{(8-6)}\left|\begin{array}{cc} (5-6) & -8 \\ (5-8) & 64 \end{array}\right|=-20\) | \(\frac{1}{(8-4)}\left|\begin{array}{cc} (5-4) & 4 \\ (5-8) & -20 \end{array}\right|=-2\) | \(\frac{1}{(8-2)}\left|\begin{array}{cc} (5-2) & 4 \\ (5-8) & -2 \end{array}\right|=1\) |
Newton差商表达式 | Newton's Divided Difference Formula¶
If we rewrite the \(n\)th Lagrange polynomial \(P_n(x)\) into another form:
By letting \(x =x_0, x_1,\cdots, x_n\), we get
Then we can define:
We can prove the above definition \(f[x_0,x_1\cdots,x_n]\), which is called divided difference, to be equal to \(a_n\) by induction.
We can also show that \(a_1\) is the coefficient of the highest item of polynomial of degree \(1\) that interpolates \(x_0,x_1\), and \(a_2\) is the coefficient of the highest item of polynomial of degree \(2\) that interpolates \(x_0,x_1,x_2\) ...
This iterative method is quite useful in determining the parameters of \(n\)th Lagrange polynomial.
The following relation gives a slightly quicker way to compute \(f[x_0,x_1,\cdots,x_n]\):
计算差商 | Calculating divided difference
where
We know from Lagrange polynomial of degree \(n\)
where
So the divided difference equals to the coefficient of the highest item of \(P_n(x)\), and we are done.
Now solve Question 1 in the above part of the article.
| \(x_i\) | \(f(x_i)\) | \(f[x_i,x_j]\) | \(f[x_i,x_j,x_k]\) |
|---|---|---|---|
| 1 2 4 |
8 1 5 |
-7 2 |
3 |
So the interpolating polynomial is
Some properties are the followings.
差商与微分均值的关系 | Relationship of DD & Mean Value Differentials
Suppose that \(f \in C^n[a, b]\) and \(x_0, x_1, \cdots, x_n\) are distinct numbers in \([a, b]\). Then a number \(\xi\) exists in \((a, b)\) with
Specifically, we denote \(a=\min\{x_i:i=0,1\cdots,n\}\) and \(b=\max\{x_i:i=0,1\cdots,n\}\)
It is like
but add \(n!\) to the denominator.
The collary can be quite simple.
Collary of the above
If \(f(x)\) is a polynomial of degree \(k\), \(k<n\), so the \(n\)th divided difference is \(0\).
插值误差分析 | Error Analysis of Interpolation¶
The following theorem gives the error bound.
拉格朗日基函数的余项 | The remainder of Lagrange interpolating polynomial
Suppose \(x_0, x_1, \cdots , x_n\) are distinct numbers in the interval \([a, b]\) and \(f \in C^{n+1}[a, b]\). Then, for each \(x \in [a, b]\), a number \(\xi(x)\) (generally unknown) between \(x_0, x_1, \cdots , x_n\), and hence in \((a, b)\), exists with
where \(P(x)\) is the Lagrange interpolating polynomial.
Prove it.
- Using a function
which is \(C^{n+1}[a, b]\). Here we see \(x\neq x_k\) is a constant for variable \(t\). Note that \(f(x_k)=0(k=0,1,\cdots n)\) and \(f(x)=0\) for \(x \in [a, b]\)(Readers can prove them by substituting in). We can see that \(n+1+1=n+2\) zero points here(\(x,x_0,\cdots, x_n\)).
- Using generalized Rolle's Theorem: There exists \(\xi(x) \in [a, b]\) such that \(g^{n+1}(\xi(x))=0\)
And make \(n+1\) derivatives to \(g(t)\)(with respect to \(t\)), we have
substitute in \(\xi\) we have
cause \(P(x)\) is \(n\)th polynomial, so \(P^{(n+1)}(\xi)=0\). So solve for \(f(x)\) we have
and we can get the result.
Or by using the relationship between divided difference and mean value differentials.
牛顿插值公式的余项 | The remainder of Newton's interpolating Formula
Suppose \(x_0, x_1, \cdots , x_n\) are distinct numbers in the interval \([a, b]\) and \(f \in C^{n+1}[a, b]\). Then, for each \(x \in [a, b]\), we have
Similar to proof of Lagrange interpolation polynomial. We assume \(z\neq x_0,x_1,\cdots,x_n\), then consider \(n+1\)th polynomial \(Q(x)\) that interpolates these \(n+2\) points \(\{z,x_0,x_1,\cdots,x_n\}\), so we have
which satisfies \(f(x_i)=Q(x_i)(i=0,1,\cdots,n)\) and \(f(z)=Q(z)\), the latter one gives
substitute \(z\) with \(x\) and we are done.
There is still one step left. For \(z=x_i\), divided difference \(f[x_0,x_1,\cdots,x_n,z]\) is not defined. So for \(x_i\), we consider a sequence \(\{y_k^{i}\}_{k=1}^\infty\), where \(y_k^i\neq x_i\) and \(\lim_{k\rightarrow \infty}y_k^i=x_i\). First we have the above theorem holds on \(y_k^i\), i.e.
we know that \(f(x)\) and \(Q(x)\)(\(n\)th polynomial) are continuous on \([a,b]\), so \(\lim_{k\rightarrow \infty}f(y_k^i)=f(x_i)\) and \(\lim_{k\rightarrow \infty}Q(y_k^i)=Q(x_i)=f(x_i)\), so
we could define \(R(x_i)=0\) and the above equation still holds.
The above error item is useful in Numerical Integration.
Compared to the remainder of Taylor's extension
Because \(\xi(x)\) is usually unknown, so we often use a number \(x' \in [a, b]\) such that
等距插值 | Interpolation of Equidistant Points¶
In actual calculation in computer, we use difference to replace divided difference when we interpolate points with equal distance.
Definition of Difference on Equidistant Points
Difference of first order is defined by
Difference of second order is defined by
By recursion, we define Difference of \(n\)th order
By induction, it is easy to see that
We usually use the recursive method for computing.
In situation where points are equally distant, we have a relationship between divided difference and difference.
relationship between divided difference and difference
Under equidistant points, we have
where \(h\) is the distance between two adjacent points.
By induction.
Hermite多项式 | Hermite Polynomials¶
We want to consider the smoothness of interpolating polynomials, so we need to consider its derivatives, especially the first order derivative.
Definition of Osculating Polynomial
The osculating polynomial approximating \(f\) is the polynomial \(P(x)\) of least degree such that
Where \(n\) is the total number of sampling points and \(m_i\) is the degree of smoothness at point \(x_i\).
If \(m_i=1\) for all \(i=0,1,\cdots, n\), then the above polynomial is called Hermite Polynomial.
Composition of Hermite Polynomial
If \(f \in C^1[a, b]\) and \(x_0, \cdots , x_n \in [a, b]\) are distinct, the unique polynomial of least degree agreeing with \(f\) and \(f'\) at \(x_0,\cdots , x_n\) is the Hermite polynomial of degree at most \(2n + 1\) given by
where, for \(L_{n, j}(x)\) denoting the \(j\)th Lagrange coefficient polynomial of degree \(n\), we have
The composition is usually a little tedious.
样条插值 | Cubic Spline Interpolation¶
We change \(\frac{d^kP(x_i)}{dx^k} = \frac{d^kf(x_i)}{dx^k}\) into equations between adjacent curves. Because we often do not know the derivatives of the point.
Define \(s(x)\) piece-wisely with \(s_i(x)\in [x_i,x_{i+1}]\)
which has 4 parameters to be determined. So the overall number of parameters to be determined is \(4n\). The condition they have to satisfy
So the above necessary condition gives \(4n-2\) equations while we have \(4n\) parameters to be determined. So we need to add another two equations for computing. There are many ways while the followings are usually seen.
Three possible dealings
(i) provide the derivatives of \(2\) endpoints, i.e. \(s'(a)=f'(a)\), \(s'(b)=f'(b)\), which is called D1 cubic spline or Clamped Cubic Spline.
(ii) provide the second derivatives of \(2\) endpoints, i.e. \(s''(a)=f''(a)\), \(s''(b)=f''(b)\), which is called D1 cubic spline. Specially, if \(s''(a)=s''(b)=0\), it is called Natural Spline.
(iii) take \(s(a)=f(a)\) or \(s(b)=f(b)\) out and provide extra \(3\) equations \(s(a)=s(b)\), \(s'(a)=s'(b)\), \(s''(a)=s''(b)\), which is called periodical cubic spline.
The solution for solving parameters by given condition.
Calculation of parameters
Consider \(s(x)\) on \([x_i,x_{i+1}]\), if we denote \(s''(x_i)=M_i\), then the overall equation becomes
where
for \(i=0\) and \(i=n\) two situation, we deduce different equations for different condition.
(i) D1 cubic spline. we have
| \(x_i\) | 0 | 1 | 2 |
|---|---|---|---|
| \(f(x_i)\) | 1 | 2 | 6 |
Define \(s_0(x)=a_0+b_0x+c_0x^2+d_0x^3\) and \(s_1(x)=a_1+b_1(x-1)+c_1(x-1)^2+d_1(x-1)^3\), then
with condition that satisfies passing data points
So represent all the parameters with \(d_1\) or \(d_0\), we get