Newton's interpolation polynomial
In this section, we shall study the polynomial interpolation in the form of Newton. Given a sequence of (n+1) data points and a function f, the aim is to determine an n-th degreee polynomial which interpolates f at these points. We shall resort to the notion of divided differences.
Interpolation
Given a set of $(n+1)$ data points
\[(x_0,y_0),(x_1,y_1), \ldots ,(x_n,y_n)\]The points defined by $(x_i)_{0 \leq i\leq n}$ are called points of interpolation.
The points $(y_i)_{0 \leq i\leq n}$ are the values of interpolation. To interpolate a function $f$, we define the values of interpolation as follows: \(y_i=f(x_i), \quad \forall i=0, \ldots ,n\)
Reminders about Lagrange interpolation polynomials
We have seen that Lagrange interpolation polynomial of degree $n$ was:
\[P_n(x)= \sum_{k=0}^n l_k(x)f(x_k)\]where the $l_k$’s are polynomials of degree $n$ forming a basis of $\mathcal{P}_n$.
\[l_k(x)= \prod_{i=0,\, i\neq k}^{n} \frac{x-x_i}{x_k-x_i}=\frac{x-x_0}{x_k-x_0} \cdots \frac{x-x_{k-1}}{x_k-x_{k-1}} \frac{x-x_{k+1}}{x_k-x_{k+1}} \cdots \frac{x-x_{n}}{x_k-x_{n}}\]Such polynomials are not convenient, since numerically, it is difficult to deduce $l_{k+1}$ from $l_{k}$. For this reason, we introduce Newton’s interpolation polynomial.
Newton’s interpolation polynomial and Newton’s basis properties
- The polynomials of Newton’s basis, $e_k$, are defined by:
with the following convention:
\[e_0=1\]Moreover
\[\begin{array}{rcl} e_1&=&(x-x_0)\\ e_2&=&(x-x_0)(x-x_1)\\ e_3&=&(x-x_0)(x-x_1)(x-x_2)\\ \vdots&&\vdots\\ e_n&=&(x-x_0)(x-x_1)\cdots(x-x_{n-1}) \end{array}\]- The set of polynomials $(e_k)_{0 \leq k\leq n}$(Newton’s basis) are a basis of $\mathcal{P}_n$, the space of polynomials of degree at most equal to $n$. Indeed, they constitute an echelon-degree set of $(n+1)$ polynomials.
- Newton’s interpolation polynomial of degree $n$ related to the subdivision ${(x_0,y_0),(x_1,y_1),\ldots,(x_n,y_n)}$ is:
where
\[P_n(x_i)=f(x_i),\quad \forall i=0,\ldots,n.\]We shall see how to determine the coefficients $(\alpha_k)_{0 \leq k\leq n}$ in the following section entitled the divided differences.
Divided differences
Newton’s interpolation polynomial of degree $n$, $P_n(x)$, evaluated at $x_0$, gives:
\[P_n(x_0)= \sum_{k=0}^n \alpha_k e_k(x_0)=\alpha_0=f(x_0)=f[x_0]\]Generally speaking, we write:
\[f[x_i]=f(x_i), \quad \forall i=0,\ldots,n\]$f[x_0]$ is called a zero-order divided difference.
Newton’s interpolation polynomial of degree $n$, $P_n(x)$, evaluated at $x_1$, gives:
\[\begin{array}{lll} P_n(x_1)&=&\displaystyle \sum_{k=0}^n \alpha_k e_k(x_1)\\ &=&\alpha_0 + \alpha_1(x_1-x_0)\\ &=&f[x_0] + \alpha_1(x_1-x_0)\\ &=&f[x_1] \end{array}\]Hence
\[\alpha_1=\frac{f[x_1]-f[x_0]}{x_1-x_0}=f[x_0,x_1]\]$f[x_0,x_1]$ is called $1^{st}$-order divided difference.
Newton’s interpolation polynomial of degree $n$, $P_n(x)$, evaluated at $x_2$, gives:
\[\begin{array}{rcl} P_n(x_2)&=&\displaystyle \sum_{k=0}^n \alpha_k e_k(x_2)\\ &=&\alpha_0 + \alpha_1(x_2-x_0) +\alpha_2(x_2-x_0)(x_2-x_1) \\ &=&f[x_0] + f[x_0,x_1](x_2-x_0)+\alpha_2(x_2-x_0)(x_2-x_1) \\ &=&f[x_2] \end{array}\]Therefore:
\[\begin{array}{rcl} \alpha_2(x_2-x_0)(x_2-x_1)&=&f[x_2]-f[x_0] -f[x_0,x_1](x_2-x_0)\\ \alpha_2&=&\displaystyle\frac{f[x_2]-f[x_0] -f[x_0,x_1](x_2-x_0)}{(x_2-x_0)(x_2-x_1)}\\ \alpha_2&=&\displaystyle\frac{f[x_2]-f[x_0]}{(x_2-x_0)(x_2-x_1)}- \frac{f[x_0,x_1]}{x_2-x_1}\\ \alpha_2&=&\displaystyle\frac{f[x_0,x_2]-f[x_0,x_1]}{x_2-x_1} \end{array}\]The following form is generally preferred:
\[\begin{array}{rcl} \alpha_2(x_2-x_0)(x_2-x_1)&=&f[x_2]-f[x_0] -f[x_0,x_1](x_2-x_0)\\ \alpha_2(x_2-x_0)(x_2-x_1)&=&f[x_2]-f[x_0] -f[x_0,x_1](x_2-x_0)-f[x_1]+f[x_1]\\ \alpha_2(x_2-x_0)(x_2-x_1)&=&f[x_2]-f[x_1]+f[x_1]-f[x_0] -f[x_0,x_1](x_2-x_0)\\ \alpha_2(x_2-x_0)(x_2-x_1)&=&f[x_2]-f[x_1]+(x_1-x_0)f[x_0,x_1] -f[x_0,x_1](x_2-x_0)\\ \alpha_2(x_2-x_0)(x_2-x_1)&=&f[x_2]-f[x_1]+(x_1-x_2)f[x_0,x_1]\\ \alpha_2(x_2-x_0)&=&\displaystyle\frac{f[x_2]-f[x_1]}{x_2-x_1}-f[x_0,x_1]\\ \alpha_2(x_2-x_0)&=&f[x_1,x_2]-f[x_0,x_1] \end{array}\]Hence \(\alpha_2=\displaystyle\frac{f[x_1,x_2]-f[x_0,x_1]}{x_2-x_0}=f[x_0,x_1,x_2]\)
$f[x_0,x_1,x_2]$ is called$2^{nd}$-order divided difference.
By recurrence, we obtain:
\[\alpha_k=\displaystyle\frac{f[x_1,\ldots,x_k]- f[x_0,\ldots,x_{k-1}]}{x_k-x_0}=f[x_0,\ldots,x_k]\]$f[x_0,\ldots,x_k]$ is thus called a $k^{th}$-order divided difference. In practice, when we want to determine the $3^{rd}$-order divided difference $f[x_0,x_1,x_2,x_3]$ for instance, we need the following quantities
\[\left[\begin{array}{ccccc} x_0 & f[x_0] & & & \cr x_1 & f[x_1] & f[x_0,x_1] & & \cr x_2 & f[x_2] & f[x_1,x_2] & f[x_0,x_1,x_2] & \cr x_3 & f[x_3] & f[x_2,x_3] & f[x_1,x_2,x_3] & f[x_0,x_1,x_2,x_3] \end{array}\right]\]Hence
\[f[x_0,x_1,x_2,x_3]=\displaystyle\frac{f[x_1,x_2,x_3]- f[x_0,x_1,x_{2}]}{x_3-x_0}\]Properties. Let $E={0,1,\ldots,n}$ and $\sigma$ be a permutation of $\mathfrak{S}(E)$. Then
\[f[x_{\sigma(0)},\ldots,x_{\sigma(n)}]=f[x_0,\ldots,x_{n}].\]Newton’s interpolation polynomial of degree $n$
Newton’s interpolation polynomial of degree $n$ is obtained via the successive divided differences:
\[P_n(x)= f[x_0] + \sum_{k=1}^n f[x_0,\ldots,x_k] e_k(x)\]Error of interpolation
Assume that $f\in \mathcal{C}^{n}([a,b])$ and $x\in[a,b]$. Let $I$ be the closed set defined by $I=[\min(x,x_0),\max(x,x_n)]$ (the smallest closed set containing $x$ and the $x_i$’s).
Theorem.
\[\exists \xi \in I / f[x_0,\ldots,x_{n}]=\displaystyle\frac{f^{n}(\xi)}{n!}\]Proof. Let $d(x)=f(x)-p(x).$ We have:
\[d(x_i)=f(x_i)-P_n(x_i)=0\quad \forall i=0,\ldots,n\]By successively applying Rolle’s theorem ($n$ times), $d^{(n)}(x)$ equals zero at a given point $\xi\in I$:
\[d^{(n)}(\xi)=0.\]Therefore, we have:
\[f^{(n)}(\xi)=P_n^{(n)}(\xi)\]Since the coefficient of $x^n$ in $P_n$ is $f[x_0,\ldots,x_{n}]$,
\[f^{(n)}(\xi)=P_n^{(n)}(\xi)=n!\cdot f[x_0,\ldots,x_{n}]\]hence
\[f[x_0,\ldots,x_{n}]=\displaystyle\frac{f^{(n)}(\xi)}{n!}\]We now assume that $f\in \mathcal{C}^{n+1}([a,b])$ and $x\in[a,b]$. Let $I$ be the closed set defined by $I=[\min(x,x_0),\max(x,x_n)]$ (the smallest closed set containing $x$ and the $x_i$’s).
Theorem. \(\forall x\in [a,b],\quad \exists \xi \in I / f(x)-P_n(x)= \displaystyle\frac{f^{n+1}(\xi)}{(n+1)!} \displaystyle\prod_{i=0}^{n}(x-x_i)\)
Proof. There are two possible ways: (1) the one encountered in [Lagrange polynomial interpolation->article71] and (2) the following.
If $x=x_i$, the problem is over!
\[f(x)-P_n(x)=f(x_i)-P_n(x_i)=0.\]Let $\hat{x}\in[a,b]$ and assume that $\hat{x}\neq x_i$.
Consider the unique polynomial $P_{n+1}$ of degree $(n+1)$ which interpolates $f$ at the points ${(x_0,y_0),(x_1,y_1),\ldots,(x_n,y_n),(\hat{x},f(\hat{x}))}$. $P_{n+1}$ verifies
\[\left\{\begin{array}{rcl} P_{n+1}(x_i)&=&f(x_i),\quad\forall i=0,\ldots,n \\ P_{n+1}(\hat{x})&=&f(\hat{x}). \end{array}\right.\]The polynomial $P_{n+1}$ can be written as:
\[P_{n+1}(x)=P_{n}(x)+(x-x_0)\ldots(x-x_n)f[x_0,\ldots,x_{n},\hat{x}]\]According to the previous theorem
\[f[x_0,\ldots,x_{n},\hat{x}]=\displaystyle\frac{f^{(n+1)}(\xi)}{(n+1)!}\]By setting $x=\hat{x}$, $P_{n+1}(\hat{x})=f(\hat{x})$,
\[f(\hat{x})=P_{n}(\hat{x})+(\hat{x}-x_0)\ldots(\hat{x}-x_n)\displaystyle\frac{f^{(n+1)}(\xi)}{(n+1)!}\]Since this result is valid regardless of $\hat{x}$, the case is made!
An example of computing Newton’s interpolation polynomial
Given a set of 3 data points ${(0,1), (2,5),(4,17)}$, we shall determine Newton’s interpolation polynomial of degree 2 which passes through these points. \(\left[\begin{array}{ccccc} x_0=0 & f[x_0]=1 & & & \cr x_1=2 & f[x_1]=5 & f[x_0,x_1]=\displaystyle\frac{5-1}{2-0} = 2& & \cr x_2=4 & f[x_2]=17 & f[x_1,x_2]=\displaystyle\frac{17-5}{4-2}=6 & f[x_0,x_1,x_2]= \displaystyle\frac{6-2}{4-0}=1 & \end{array}\right]\)
Consequently:
\[\begin{array}{rcl} P_2(x)&=&f[x_0]+f[x_0,x_1]x+f[x_0,x_1,x_2]x(x-2)\\ &=&1+2x+x(x-2)\\ &=&1+x^2 \end{array}\]Scilab: computing Newton’s interpolation polynomial
Scilab function newton.sci determines Newton’s interpolation polynomial. $X$ contains the points of interpolation and $Y$ the values of interpolation. $P$ is Newton’s interpolation polynomial computed by means of divided differences.sées.
newton.sci
function[P]=newton(X,Y)//X nodes,Y values;P is the numerical Newton polynomial
n=length(X);// n is the number of nodes. (n-1) is the degree
for j=2:n,
for i=1:n-j+1,Y(i,j)=(Y(i+1,j-1)-Y(i,j-1))/(X(i+j-1)-X(i));end,
end,
x=poly(0,"x");
P=Y(1,n);
for i=2:n, P=P*(x-X(i))+Y(i,n-i+1); end
endfunction;Therefore, we obtain:
-->X=[0;2;4]; Y=[1;5;17]; P=newton(X,Y)
P = 1 + x^2
If you found this post or this website helpful and would like to support our work, please consider making a donation. Thank you!
Help Us