Contents

• 1  Interpolation
  • 1.1  Lagrange polynomial interpolation
• 2  Exercise
  • 2.1  Compute the Lagrange fundamental polynomials and draw their graphs
  • 2.2  Compute the interpolation polynomial by Lagrange’s method
  • 2.3  Approximate the value in $x=2$ and compute an error bound and compare it with the absolute error

Interpolation

Sometimes we need to compute the value of a function at several points but

• We may not have the value of the function for all points but only for some because, for example, we have obtained the values we have from an experiment.
• Or the function may take a lot of time to compute.
• Or we may want an approximate function that is easier to differentiate or integrate.

The interpolation technique may be used to solve these problems. In interpolation, we use the data (value, derivative) of a function at some points to build a new approximate function. These new approximate functions are, for example, polynomials and trigonometric functions.

We will study:

• Lagrange polynomial interpolation.
  • Using the fundamental Lagrange polynomials.
  • Using Newton's form with divided differences.
• Piecewise polynomial interpolation.

Lagrange polynomial interpolation

In this type of interpolation we have as data:

• The interpolation nodes are $n+1$ points $x_0$, $x_1$, $x_2,\ldots,x_n$
• Values of the function $f$ in the nodes: $f(x_0)$, $f(x_1)$, $f(x_2),\ldots,f(x_n)$

And we are searching for a polynomial that goes through all these points. This can be all the information we have about $f$ and there is not necessarily an analytic expression of $f.$

For example, for the points

\begin{array}{|c|ccccc|} \hline k & 0 & 1 & 2 & 3 & 4 \\ \hline x & 1 & 2 & 3 & 4 & 5 \\ y & 1 & 2 & 4 & 3 & 5 \\ \hline \end{array}

we are searching for a polynomial that goes through all these points

Existence and uniqueness of the Lagrange polynomial

In the example of the previous graph, since we have $5$ points we can generate $5$ equations and we need $ 5 $ unknowns that will be the coefficients of the polynomial. Thus:

$$P_4(x)=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4$$

that is, $a_0,$ $a_1,$ $a_2,$ $a_3$ and $a_4$ are the $5$ unknowns and the polynomial is of degree $4$. In general, for the points $(x_0,y_0),(x_1,y_1),\ldots,(x_n,y_n)$ the interpolating polynomial will be of degree $\leq n$.

The equations are

$$ \begin{array}{lll} P_{4}(x_{0})=y_{0} & \quad & a_{0}+a_{1}x_{0}+a_{2}x_{0}^{2}+a_{3}x_{0}^{3}+a_{4}x_{0}^{4}=y_{0}\\ P_{4}(x_{1})=y_{1} & \quad & a_{0}+a_{1}x_{1}+a_{2}x_{1}^{2}+a_{3}x_{1}^{3}+a_{4}x_{1}^{4}=y_{1}\\ P_{4}(x_{2})=y_{2} & \quad & a_{0}+a_{1}x_{2}+a_{2}x_{2}^{2}+a_{3}x_{2}^{3}+a_{4}x_{2}^{4}=y_{2}\\ P_{4}(x_{3})=y_{3} & \quad & a_{0}+a_{1}x_{3}+a_{2}x_{3}^{2}+a_{3}x_{3}^{3}+a_{4}x_{3}^{4}=y_{3}\\ P_{4}(x_{4})=y_{4} & \quad & a_{0}+a_{1}x_{4}+a_{2}x_{4}^{2}+a_{3}x_{4}^{3}+a_{4}x_{4}^{4}=y_{4} \end{array} $$

And the linear system is

$$ \left(\begin{array}{ccccc} 1 & x_{0} & x_{0}^{2} & x_{0}^{3} & x_{0}^{4}\\ 1 & x_{1} & x_{1}^{2} & x_{1}^{3} & x_{1}^{4}\\ 1 & x_{2} & x_{2}^{2} & x_{2}^{3} & x_{2}^{4}\\ 1 & x_{3} & x_{3}^{2} & x_{3}^{3} & x_{3}^{4}\\ 1 & x_{4} & x_{4}^{2} & x_{4}^{3} & x_{4}^{4} \end{array}\right)\left(\begin{array}{c} a_{0}\\ a_{1}\\ a_{2}\\ a_{3}\\ a_{4} \end{array}\right)=\left(\begin{array}{c} y_{0}\\ y_{1}\\ y_{2}\\ y_{3}\\ y_{4} \end{array}\right) $$

The coefficient matrix of the system is Vandermonde matrix and its determinant is

$$\det\left(A\right)=\prod_{0\leq l\lt k\leq n}\left(x_{k}-x_{l}\right)\neq0\quad \mathrm{if}\quad x_k \ne x_l$$

that is

$$\det(A) = (x_1-x_0)(x_2-x_0)(x_3-x_0)(x_4-x_0)(x_2-x_1)(x_3-x_1)(x_4-x_1)(x_3-x_2)(x_4-x_2)(x_4-x_3)$$

which is nonzero if no two $x_i$ are the same. And in this case, the system solution exists and is unique.

In the previous example $(x_k,y_k),$ and $y_k = f(x_k)$ are

\begin{array}{|c|ccccc|} \hline k & 0 & 1 & 2 & 3 & 4 \\ \hline x & 1 & 2 & 3 & 4 & 5 \\ y & 1 & 2 & 4 & 3 & 5 \\ \hline \end{array}

And the system is

$$ \left(\begin{array}{ccccc} 1 & x_{0} & x_{0}^{2} & x_{0}^{3} & x_{0}^{4}\\ 1 & x_{1} & x_{1}^{2} & x_{1}^{3} & x_{1}^{4}\\ 1 & x_{2} & x_{2}^{2} & x_{2}^{3} & x_{2}^{4}\\ 1 & x_{3} & x_{3}^{2} & x_{3}^{3} & x_{3}^{4}\\ 1 & x_{4} & x_{4}^{2} & x_{4}^{3} & x_{4}^{4} \end{array}\right)\left(\begin{array}{c} a_{0}\\ a_{1}\\ a_{2}\\ a_{3}\\ a_{4} \end{array}\right)=\left(\begin{array}{c} y_{0}\\ y_{1}\\ y_{2}\\ y_{3}\\ y_{4} \end{array}\right) $$

$$ \left(\begin{array}{ccccc} 1 & 1 & 1 & 1 & 1\\ 1 & 2 & 4 & 8 & 16\\ 1 & 3 & 9 & 27 & 81\\ 1 & 4 & 16 & 64 & 256\\ 1 & 5 & 25 & 125 & 625 \end{array}\right)\left(\begin{array}{c} a_{0}\\ a_{1}\\ a_{2}\\ a_{3}\\ a_{4} \end{array}\right)=\left(\begin{array}{c} 1\\ 2\\ 4\\ 3\\ 5 \end{array}\right) $$

As there are 5 different nodes the determinant of the coefficient matrix is nonzero.

$$\det\left(A\right)=(2-1)(3-1)(4-1)(5-1)(3-2)(4-2)(5-2)(4-3)(5-3)(5-4)=288$$

And, solving the system, the Lagrange interpolating polynomial is

$$P_4(x)=15-28.66666667\,x+19.08333333\,x^2-4.83333333\,x^3+0.41666667\,x^4$$

One way to obtain the Lagrange interpolating polynomial is to solve the above system. But this system is ill-conditioned (small errors in the data can produce large errors in the results) and the computation is comparatively expensive.

We are going to see two alternative ways to compute the Lagrange interpolation polynomial:

• Through the fundamental Lagrange polynomials.
• Using Newton's divided differences.

Exercise

For the nodes $x_{0}=-1,$ $x_{1}=1,$ $x_{2}=3$ y $x_{3}=5$ and the function $f\left(x\right)=\sin\left(\dfrac{\pi}{6}x\right)$

• Compute the Lagrange fundamental polynomials and draw their graphs.
• Compute the interpolation polynomial by Lagrange’s method.
• Approximate the value in $x=2$ and compute an error bound and compare it with the absolute error.

---

Compute the Lagrange fundamental polynomials and draw their graphs

Fundamental Lagrange polynomial value is 0 in all nodes except one of them, where it is equal to 1. There are as many fundamental Lagrange polynomials as nodes and they are $L_0(x),$ $L_1(x),$ $L_2(x)$ y $L_3(x).$

Let's see how they are built. First, we create polynomials that are zero in all interpolation nodes except one and we have

The nodes are

$$x_{0}=-1\quad x_{1}=1\quad x_{2}=3\quad x_{3}=5$$

And a polynomial that is zero in the last three nodes is

$$l_0(x)=(x-x_1)(x-x_2)(x-x_3)=(x-1)(x-3)(x-5)$$

If we divide this polynomial by $l_0(x_0)$

$$L_0(x)=\frac{(x-x_1)(x-x_2)(x-x_3)}{(x_0-x_1)(x_0-x_2)(x_0-x_3)} =\frac{(x-1)(x-3)(x-5)}{(-1-1)(-1-3)(-1-5)}$$

We are omitting from the numerator and denominator the term in $x_0,$ that is $(x-x_0)$ and

$$L_0(x_0)=1 \quad L_0(x_1)=0 \quad L_0(x_2)=0 \quad L_0(x_3)=0$$

that is

$$L_k(x_i)=\begin{cases} 0 & \mathrm{if} & k\ne i\\ 1 & \mathrm{if} & k= i \end{cases}$$

The nodes are

$$x_{0}=-1\quad x_{1}=1\quad x_{2}=3\quad x_{3}=5$$

And a polynomial that is zero at all but the second node is

$$l_1(x)=(x-x_0)(x-x_2)(x-x_3)=(x+1)(x-3)(x-5)$$

If we divide this polynomial by $l_1(x_1)$

$$L_1(x)=\frac{(x-x_0)(x-x_2)(x-x_3)}{(x_1-x_0)(x_1-x_2)(x_1-x_3)} =\frac{(x+1)(x-3)(x-5)}{(1+1)(1-3)(1-5)}$$

We are omitting from the numerator and denominator the term in $x_1,$ that is $(x-x_1)$ and

$$L_1(x_0)=0 \quad L_1(x_1)=1 \quad L_1(x_2)=0 \quad L_1(x_3)=0$$

that is

$$L_k(x_i)=\begin{cases} 0 & \mathrm{if} & k\ne i\\ 1 & \mathrm{if} & k= i \end{cases}$$

The nodes are

$$x_{0}=-1\quad x_{1}=1\quad x_{2}=3\quad x_{3}=5$$

And a polynomial that is zero at all but the third node is

$$l_2(x)=(x-x_0)(x-x_1)(x-x_3)=(x+1)(x-1)(x-5)$$

If we divide this polynomial by $l_2(x_2)$

$$L_2(x)=\frac{(x-x_0)(x-x_1)(x-x_3)}{(x_2-x_0)(x_2-x_1)(x_2-x_3)} =\frac{(x+1)(x-1)(x-5)}{(3+1)(3-1)(3-5)}$$

We are omitting from the numerator and denominator the term in $x_2,$ that is $(x-x_2)$ and

$$L_2(x_0)=0 \quad L_2(x_1)=0 \quad L_2(x_2)=1 \quad L_2(x_3)=0$$

that is

$$L_k(x_i)=\begin{cases} 0 & \mathrm{if} & k\ne i\\ 1 & \mathrm{if} & k= i \end{cases}$$

The nodes are

$$x_{0}=-1\quad x_{1}=1\quad x_{2}=3\quad x_{3}=5$$

And a polynomial that is zero at all but the last node is

$$l_3(x)=(x-x_0)(x-x_1)(x-x_2)=(x+1)(x-1)(x-3)$$

If we divide this polynomial by $l_3(x_3)$

$$L_3(x)=\frac{(x-x_0)(x-x_1)(x-x_2)}{(x_3-x_0)(x_3-x_1)(x_3-x_2)} =\frac{(x+1)(x-1)(x-3)}{(5+1)(5-1)(5-3)}$$

We are omitting from the numerator and denominator the term in $x_3,$ that is $(x-x_3)$ and

$$L_3(x_0)=0 \quad L_3(x_1)=0 \quad L_3(x_2)=0 \quad L_3(x_3)=1$$

that is

$$L_k(x_i)=\begin{cases} 0 & \mathrm{if} & k\ne i\\ 1 & \mathrm{if} & k= i \end{cases}$$

We have already seen the fundamental Lagrange polynomials for our nodes (4 nodes, 4 fundamental polynomials). In general, for $x_0,$ $x_1,\ldots, x_n$ nodes we have $n+1$ fundamental Lagrange polynomials that are

$$ L_{k}\left(x\right)= \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})}\quad k=0,1,\ldots,n $$

It can also be expressed

$$ L_{k}\left(x\right)=\prod_{\begin{array}{c} j=0\\ j\neq k \end{array}}^{n}\dfrac{x-x_{j}}{x_{k}-x_{j}} \quad k=0,1,\ldots,n $$

And these polynomial satisfy

$$L_k(x_i)=\begin{cases} 0 & \mathrm{if} & k\ne i\\ 1 & \mathrm{if} & k= i \end{cases}$$

Compute the interpolation polynomial by Lagrange’s method

The interpolant polynomia is

$$ P_{3}\left(x\right)=y_{0}L_{0}\left(x\right)+ y_{1}L_{1}\left(x\right)+y_{2}L_{2}\left(x\right)+y_{3}L_{3}\left(x\right) $$

The fundamental Lagrange polynomials are built only with the nodes. But now, to calculate the interpolation polynomial $P_3(x),$ we need the values of the function at the nodes

$$f\left(x\right)=\sin\left(\dfrac{\pi}{6}x\right)\\[0.7cm] y_0=f\left(-1\right)=\sin\left(-\dfrac{\pi}{6}\right)=-\frac{1}{2}\quad y_1=f\left(1\right)=\sin\left(\dfrac{\pi}{6}\right)=\frac{1}{2}\\[0.7cm] y_2=f\left(3\right)=\sin\left(3\dfrac{\pi}{6}\right)=\sin\left(\dfrac{\pi}{2}\right)=1\quad y_3=f\left(5\right)=\sin\left(\dfrac{5\pi}{6}\right)=\frac{1}{2}$$

\begin{array}{|l|cccc|} \hline k & 0 & 1 & 2 & 3\\ \hline x & -1 & 1 & 3 & 5\\ \hline y &-\dfrac{1}{2} & \dfrac{1}{2} & 1 & \dfrac{1}{2}\\ \hline \end{array}

• If we multiply each fundamental Lagrange polynomial $L_i(x)$ by the value of the corresponding function $y_i$ the polynomial $y_i\,L_i(x)$ takes the value $y_i$ in the node $i$ and zero in the other nodes.
• Thus we get 4 polynomials, each of which passes through one of the points to be interpolated.
• If we add these 4 polynomials, as the sum is done point by point, the value in the nodes will be the value of the function, $y_i.$ So this polynomial, $P_3(x)$ is the interpolation polynomial.
• All polynomials are of degree 3, so $P_3(x)$ will be of degree less than or equal to 3. In this case, the polynomial is of degree three but if, for example, the 4 points were aligned, the polynomial would be of degree 1. Or if the 4 points were on a horizontal line the polynomial would be of degree zero. Or if they were on a parable, it would be degree 2.

\begin{array}{|l|cccc|} \hline k & 0 & 1 & 2 & 3\\ \hline x & -1 & 1 & 3 & 5\\ \hline y &-\dfrac{1}{2} & \dfrac{1}{2} & 1 & \dfrac{1}{2}\\ \hline \end{array}

And taking into account the fundamental Lagrange polynomials we calculated above, the interpolation polynomial is

$$ P_{3}\left(x\right)=-\frac{1}{2}\,L_{0}\left(x\right)+ \frac{1}{2}\,L_{1}\left(x\right)+(1)\,L_{2}\left(x\right)+\frac{1}{2}\,L_{3}\left(x\right) $$

The interpolation polynomial, for a general case, where we have $n+1$ nodes $x_0,$ $x_1,\ldots, x_n$ will be

$$P_n(x)=y_0\,L_0(x)+y_1\,L_1(x)+\cdots+y_n\,L_n(x)=\sum_{k=0}^n y_k\,L_k(x)$$

where $P_n(x)$ is a polynomial of degree less than or equal to $n.$

Approximate the value in $x=2$ and compute an error bound and compare it with the absolute error

$$ P_{3}\left(x\right)=-\frac{1}{2}\,L_{0}\left(x\right)+ \frac{1}{2}\,L_{1}\left(x\right)+(1)\,L_{2}\left(x\right)+\frac{1}{2}\,L_{3}\left(x\right) $$

Plugging in $x=2$ in the expressions we calculate for the fundamental Lagrange polynomials

$$ P_{3}\left(2\right)=-\frac{1}{2}\,L_{0}\left(2\right)+ \frac{1}{2}\,L_{1}\left(2\right)+(1)\,L_{2}\left(2\right)+\frac{1}{2}\,L_{3}\left(2\right) $$

$$ P_{3}\left(2\right)=-\frac{1}{2}\,(-0.0625)+ \frac{1}{2}(0.5625)+(1)\,(0.5625)+\frac{1}{2}\,(-0.0625) $$

$$\sin\left(2\frac{\pi}{6}\right)=\sin\left(\frac{\pi}{3}\right)\approx P_3(2)=0.84375$$

Interpolation error

The interpolation error is

$$ E(x)=f(x)-P_{n}(x)=f^{(n+1)}(c)\dfrac{(x-x_{0})\ldots(x-x_{n})}{(n+1)!}, $$

where $x_{i}$ are the interpolation points and $c$ a point of the interpolation interval. In this case, since we have four nodes interpolation

$$ \left|E(x)\right|=\left|f(x)-P_{3}(x)\right|=\left|f^{(4)}(c)\right|\dfrac{\left|(x-x_{0})(x-x_{1})(x-x_{2})(x-x_{3})\right|}{4!}. $$

Since $c$ is unknown, even though we know it is in the interpolation interval, in our case $c\in\left(-1,5\right)$, we have to find a bound for that value

$$f(x)=\sin\left(\frac{\pi}{6} x\right) \quad f'(x)=\frac{\pi}{6}\,\cos\left(\frac{\pi}{6} x\right) \quad f''(x)=-\frac{\pi^2}{6^2}\,\sin\left(\frac{\pi}{6} x\right)$$

$$ f'''(x)=-\frac{\pi^3}{6^3}\,\cos\left(\frac{\pi}{6} x\right) \quad f^{(4)}(x)=\frac{\pi^4}{6^4}\,\sin\left(\frac{\pi}{6} x\right)$$

As $$\left|\sin\left(\dfrac{\pi}{6}x\right)\right|\le 1$$

then $$\left|f^{(4)}(c)\right|\le \frac{\pi^4}{6^4}(1)=\frac{\pi^4}{6^4}$$

And and error bound is

$$ \left|E(2)\right|\le\frac{\pi^4}{6^4}\dfrac{\left|(2-x_{0})(2-x_{1})(2-x_{2})(2-x_{4})\right|}{4!} $$

$$ \left|E(2)\right|\le \frac{\pi^4}{6^4}\dfrac{\left|(2+1)(2-1)(2-3)(2-5)\right|}{4!}=0.0282 $$

As $f(2)=\sin\left(\dfrac{\pi}{6}(2)\right)=\sin\left(\dfrac{\pi}{3}\right)=0.86603$

$$\mathrm{Error} = |f(2)-P_3(2)|=|0.86603-0.84375|=0.0223\lt 0.0282$$