Skip to main content

Section 4.2 The Lagrange Form of the Interpolating Polynomial

Let’s return to the notion of fitting a polynomial to a set of data. We will start with two points. Consider the points \((x_{0},f_{0})\) and \((x_{1},f_{1})\text{.}\) The lowest-order polynomial that fits the data is a straight line which can be written in point-slope form as:
\begin{equation*} \begin{aligned}y=f_{0} + \frac{f_{1}-f_{0}}{x_{1}-x_{0}}(x-x_{0}).\end{aligned} \end{equation*}
Rearranging this a bit we can get:
\begin{align} y \amp =\frac{f_{0} (x_{1} - x_{0}) + (f_{1} - f_{0}) (x-x_{0}) }{x_{1}-x_{0}},\notag\\ \amp =\frac{f_{0} (x_{1}-x) + f_{1} (x - x_{0})}{x_{1} - x_{0}},\notag\\ \amp = f_{0} \frac{x-x_{1}}{x_{0}-x_{1}}+ f_{1} \frac{x-x_{0}}{x_{1}-x_{0}}.\tag{4.2.1} \end{align}
The functions
\begin{equation} \begin{aligned}L_{1,0}(x)\amp = \frac{x-x_{1}}{x_{0}-x_{1}},\amp L_{1,1}(x)\amp = \frac{x-x_{0}}{x_{1} - x_{0}},\end{aligned}\tag{4.2.2} \end{equation}
are called the Lagrange polynomials and are the “functional” part of (4.2.1). In this case, they are a lines and have the properties:
\begin{equation} \begin{aligned}L_{1,0}(x_{0})\amp = 1,\amp L_{1,0}(x_{1})\amp = 0,\\ L_{1,1}(x_{0})\amp = 0,\amp L_{1,1}(x_{1})\amp = 1. \end{aligned}\tag{4.2.3} \end{equation}
Because of this property, it makes the interpolating polynomial easy to find. You just need to multiply the each Lagrange polynomial by the appropriate \(y\)-value, thus (4.2.1)can be written as
\begin{equation} y = f_{0} L_{1,0}(x) + f_{1} L_{1,1}(x)\tag{4.2.4} \end{equation}
and we will see that both the quadratic form and general form of interpolation is similar. We can now use this in an example.

Example 4.2.1.

Use the Lagrange formulas above to find the line that interpolates through the points \((2,5)\) and \((4,1)\text{.}\)
First, we will find the Lagrange polynomials in (4.2.2) with \(x_{0}=2\) and \(x_{1}=4\)
\begin{equation*} \begin{aligned}L_{1,0}\amp = \frac{x-4}{2-4}\amp L_{1,1}\amp = \frac{x-2}{4-2}\end{aligned} \end{equation*}
and then the interpolated line is found using (4.2.4),
\begin{equation*} \begin{aligned}y\amp = 5 \cdot \frac{x-4}{-2}+ 1 \cdot \frac{x-2}{2}\\\amp = -2x +9\end{aligned} \end{equation*}
which is the same result if one found the line through the two given points using a technique from Precalculus.

Subsection 4.2.1 Quadratic Lagrange Polynomials

If we look at the above properties for the linear Lagrange polynomials in (4.2.3), we can hypothesize the properties of a quadratic Lagrange polynomial.
\begin{equation*} \begin{aligned}L_{2,0}(x_{0})\amp = 1,\amp L_{2,0}(x_{1})\amp = 0,\amp L_{2,0}(x_{2})\amp = 0, \\ L_{2,1}(x_{0})\amp = 0,\amp L_{2,1}(x_{1})\amp = 1,\amp L_{2,1}(x_{2})\amp = 0, \\ L_{2,2}(x_{0})\amp = 0,\amp L_{2,2}(x_{1})\amp = 0,\amp L_{2,2}(x_{2})\amp = 1.\end{aligned} \end{equation*}
Also, analogous to (4.2.2), the following are the quadratic Lagrange polynomials.
\begin{equation} \begin{aligned}L_{2,0}(x)\amp = \frac{(x-x_{1})(x-x_{2})}{(x_{0}-x_{1})(x_{0}-x_{2})}, \\ L_{2,1}(x)\amp = \frac{(x-x_{0})(x-x_{2})}{(x_{1}-x_{0})(x_{1}-x_{2})}, \notag \\ L_{2,2}(x)\amp = \frac{(x-x_{0})(x-x_{1})}{(x_{2}-x_{0})(x_{2}-x_{1})}. \end{aligned}\tag{4.2.5} \end{equation}
And the quadratic function that interpolates the data \(\{(x_{0},f_{0}), (x_{1},f_{1}), (x_{2},f_{2})\}\) is
\begin{equation} \begin{aligned}y = f_{0} L_{2,0}(x) + f_{1} L_{2,1}(x)+f_{2} L_{2,2}(x)\end{aligned}\tag{4.2.6} \end{equation}
and is the quadratic version of (4.2.1).

Example 4.2.2.

Use the dataset \(\{(0,0),(1,1),(3,2)\}\) that was given in Example 4.1.2 to find the interpolating polynomial using the Lagrange formulas:
Solution.
First, find the individual Lagrange polynomials in (4.2.5) for the given \(x\) values:
\begin{equation*} \begin{aligned}L_{2,0}(x)\amp = \frac{(x-1)(x-3)}{(0-1)(0-3)}= \frac{1}{3}(x-1)(x-3), \\ L_{2,1}(x)\amp = \frac{(x-0)(x-3)}{(1-0)(1-3)}= -\frac{1}{2}x(x-3),\\ L_{2,2}(x)\amp = \frac{(x-0)(x-1)}{(3-0)(3-1)}= \frac{1}{6}x(x-1),\\\end{aligned} \end{equation*}
and the resulting interpolating polynomial given by (4.2.6) is
\begin{equation*} \begin{aligned}y\amp = (0) \frac{1}{3}(x-1)(x-3) + (1)\frac{-1}{2}x(x-3) + (2) \frac{1}{6}x(x-1), \\\amp = -\frac{1}{2}x^{2} + \frac{3}{2}x + \frac{1}{3}x^{2} - \frac{1}{3}x = -\frac{1}{6}x^{2} +\frac{7}{6}x,\end{aligned} \end{equation*}
which is the same polynomial that we found in Example 4.1.2.

Subsection 4.2.2 General Lagrange Polynomial

The general \(k\)-th Lagrange polynomial of order \(n\) is given by
\begin{equation*} \begin{aligned}L_{n,k}(x)\amp = \frac{ (x-x_{0})(x-x_{1})\cdots (x-x_{k-1})(x-x_{k+1}) \cdots (x-x_{n}) }{ (x_{k}-x_{0})(x_{k}-x_{1})\cdots (x_{k}-x_{k-1})(x_{k}-x_{k+1}), \cdots (x_{k}-x_{n})}\\\amp = \prod_{\stackrel{i=0,}{i\neq k}}^{n}\frac{x-x_{i}}{x_{k}-x_{i}}.\end{aligned} \end{equation*}
Notice that this gives the property
\begin{equation*} \begin{aligned}L_{n,k}(x_{i}) = 0 \quad\text{for all $i \neq k$}\quad L_{n,k}(x_{k}) = 1. \end{aligned} \end{equation*}
And the general interpolating polynomial \(P_{n}(x)\) that passes through the data \((x_{i},f_{i})\) for \(0 \leq i \leq n\) is
\begin{equation*} \begin{aligned}P_{n}(x)\amp = \sum_{k=1}^{n} f_{i} L_{n,k}(x) .\end{aligned} \end{equation*}

Example 4.2.3.

If we return to the problem of finding a polynomial that passes through the probability data given at the beginning of the chapter:
\(x\) \(0\) \(0.25\) \(0.50\) \(0.75\) \(1\)
\(y\) \(0.0000\) \(0.0987\) \(0.1915\) \(0.2734\) \(0.3413\)
in which \(y=P(X \gt x)\text{.}\) Then the Lagrange polynomials using the \(x\)-values in the table above are:
\begin{equation*} \begin{aligned}L_{4,0}(x)\amp = \frac{(x-0.25)(x-0.5)(x-0.75)(x-1)}{(0-0.25)(0-0.5)(0-0.75)(0-1)}\\ L_{4,1}(x)\amp = \frac{(x-0)(x-0.5)(x-0.75)(x-1)}{(0.25-0)(0.25-0.5)(0.25-0.75)(0.25-1)}\\ L_{4,2}(x)\amp = \frac{(x-0)(x-0.25)(x-0.75)(x-1)}{(0.5-0)(0.5-0.25)(0.5-0.75)(0.5-1)}\\ L_{4,3}(x)\amp = \frac{(x-0)(x-0.25)(x-0.5)(x-1)}{(0.75-0)(0.75-0.25)(0.75-0.5)(0.75-1)}\\ L_{4,4}(x)\amp = \frac{(x-0)(x-0.25)(x-0.5)(x-0.75)}{(1-0)(1-0.25)(1-0.5)(1-0.75)}\\\end{aligned} \end{equation*}
and the resulting Lagrange interpolating polynomial is
\begin{equation*} \begin{aligned}P_{4} (x)\amp = \sum_{k=0}^{4}f_{k} L_{4,k}\\\amp = 0.01923862081x^{4}-0.08107936270x^{3}\\\amp \qquad +0.00479110462x^{2}+0.3983943834x,\end{aligned} \end{equation*}
where simplification has taken place.
The data and the interpolating polynomial are plotted below:
Figure 4.2.4.
For example, if we use the interpolating polynomial to calculate the probability \(P(X \geq 0.64)\text{,}\) the polynomial gives us:
\begin{equation*} \begin{aligned}P_{4}(0.64)\amp = 0.2389,\end{aligned} \end{equation*}
which agrees to the cumulative density function (given in Probability and Statistics books) to 4 digits.
The following theorem shows that given a set of points, there exists a polynomials that passes through the points and that polynomial is unique.

Proof.

Existence:
Such a polynomial exists by constructing the Lagrange polynomial as seen above.
\begin{equation*} \begin{aligned}P_{n}(x)\amp = \sum_{i=0}^{n} f(x_{i}) L_{n,i}(x)\end{aligned} \end{equation*}
and using the properties of the Lagrange polynomials:
\begin{equation*} \begin{aligned}P_{n}(x_{i})\amp = \sum_{i=0}^{n} f(x_{i}) L_{n,i}(x_{i}) = f(x_{i}).\end{aligned} \end{equation*}
for each \(i=0,1,2, \ldots, n\text{.}\)
Uniqueness:
This will proceed by contradiction. Suppose both \(P(x)\) and \(Q(x)\) are polynomials of degrees at most \(n\) which interpolate \(f\) at the given points.
Let \(h(x) = P(x) - Q(x)\text{.}\) Since both \(P\) and \(Q\) are polynomials of degree at most \(n\text{,}\) the same is true for \(h\text{.}\) Also,
\begin{equation*} \begin{aligned}h(x_{i})\amp = P(x_{i}) - Q(x_{i}) = f(x_{i}) -f(x_{i}) = 0\end{aligned} \end{equation*}
for each \(i=0,1,2,\ldots, n\text{.}\) Therefore \(h\) is a polynomial of degree at most \(n\) with \(n+1\) roots. The fundamental Theorem of Algebra guarantees that the only way this can happen is if \(h(x) \equiv 0\text{.}\) This implies that \(P\equiv Q\text{,}\) and thus the polynomial is unique.
Since the above theorem shows that the interpolating polynomial is unique, therefore the method used to find it does not matter. Example 4.1.2 used a basic method to arrive at the interpolating polynomial through the points \((0,0), (1,1)\) and \((3,2)\text{.}\) Example 4.2.2 used Lagrange interpolation to arrive at the same answer and in the next section, we will see yet another form.

Subsection 4.2.3 Error in the interpolating polynomial

We saw in Example 4.2.3, the interpolating polynomial with the normal distribution data given was accurate to 4 decimal places at the desired point. The next theorem shows how to calculate this.

Proof.

First, note that because of the form of the error term
\begin{equation*} \begin{aligned}f(x_{i})\amp = P(x_{i})\amp \amp \text{for $i=0 \ldots n$}\\\end{aligned} \end{equation*}
since at each \(x_{i}\text{,}\) the error term is zero.
For any value \(x \in [a,b]\) such that \(x \neq x_{i}\) for all \(i\text{,}\) define:
\begin{equation*} \begin{aligned}g(t)\amp = f(t) - P(t) - \bigl(f(x) -P(x) \bigr) \prod_{i=0}^{n}\frac{t-x_{i}}{x-x_{i}}\\\end{aligned} \end{equation*}
By the conditions of the theorem, \(f\) has \(n+1\) continuous derivatives, and since \(P\) is a polynomial, and it has \(n+1\) continuous derivatives, \(g\) has \(n+1\) continuous derivatives on \((a,b)\text{.}\)
Furthermore,
\begin{equation*} \begin{aligned}g(x_{j})\amp = f(x_{j}) - P(x_{j}) - \bigl(f(x)-P(x) \bigr) \cdot 0 \\\amp = 0\end{aligned} \end{equation*}
for \(j=0, 1, \ldots, n\) and
\begin{equation*} \begin{aligned}g(x)\amp = f(x) - P(x) - \bigl(f(x) - P(x) \bigr) \prod_{i=0}^{n} \frac{x-x_{i}}{x-x_{i}}\\\amp = f(x) - P(x) - \bigl(f(x) - P(x)\bigr) \cdot 1 = 0.\end{aligned} \end{equation*}
therefore \(g\) has \(n+2\) roots on \([a,b]\text{.}\) Applying the Generalized Rolle’s Theorem given in Theorem 1.2.5, it follows that there exists \(\xi \in [a,b]\) such that \(g^{(n+1)}(\xi) = 0\text{.}\)
Note that \(P\) is a polynomial of degree at most \(n\text{,}\) so \(P^{(n+1)}(x) \equiv 0\text{.}\) And \(\prod_{i=0}^{n}\frac{t-x_{i}}{x-x_{i}}\) is a polynomial of degree \(n+1\) with leading coefficient \(\prod_{i=0}^{n} (x-x_{i})^{-1}\text{,}\) so
\begin{equation*} \begin{aligned}\frac{d^{n+1}}{dt^{n+1}}\biggl[\prod_{i=0}^{n} \frac{t-x_{i}}{x-x_{i}}\biggr] ,\amp = (n+1)! \biggl[\prod_{i=0}^{n} (x-x_{i}) \biggr]^{-1}.\end{aligned} \end{equation*}
Differentiating \(g\) \(n+1\) times and evaluating it at \(\xi\) yields
\begin{equation*} \begin{aligned}0\amp = g^{(n+1)}(\xi) = f^{(n+1)}(\xi) - 0 - \bigl(f(x) - P(x)\bigr) \biggl[\prod_{i=1}^{n} (x-x_{i})\biggr]^{-1}.\end{aligned} \end{equation*}
Solving for \(f(x)\text{,}\) results in
\begin{equation*} \begin{aligned}f(x)\amp = P(x) + \frac{f^{(n+1)}(\xi)}{(n+1)!}(x-x_{0})(x-x_{1}) \cdots (x-x_{n})\end{aligned} \end{equation*}
This theorem now allows us to determine the error associated with approximating a function. The following example shows how one can use this to determine how well an interpolated polynomial approximates a function.

Example 4.2.7.

Find the interpolated polynomial for the function \(f(x)=\sin x\) on \([0,\pi]\) using 3 equally-spaced points. Find a bound on the error using Theorem 4.2.6.
Solution.
First, we will find the interpolated polynomial through the points \((0,0)\text{,}\) \((\pi/2,1)\) and \((\pi,0)\text{.}\) We will need the three Lagrange polynomials:
\begin{equation*} \begin{aligned}L_{2,0}(x)\amp = \frac{(x-\pi/2)(x-\pi)}{(0-\pi/2)(0-\pi)}\\ L_{2,1}(x)\amp = \frac{(x-0)(x-\pi)}{(\pi/2-0)(\pi/2-\pi)}\\ L_{2,2}(x)\amp = \frac{(x-0)(x-\pi/2)}{(\pi-0)(\pi-\pi/2)}\\\end{aligned} \end{equation*}
and then write:
\begin{equation*} \begin{aligned}P_{2}(x)\amp = 0 \cdot L_{2,0}(x) + 1 \cdot L_{2,1}(x) + 0 \cdot L_{2,2}(x) \\\amp = -\frac{4}{\pi^{2}}x(x-\pi)\end{aligned} \end{equation*}
Here is a plot of both \(f\) and \(P_{2}\) on \([0,\pi]\text{.}\)
Figure 4.2.8.
As you can see from the plot, the interpolated polynomial and the sine function are close (but not identical). Now, let’s use Theorem 4.2.6 to find the error,
\begin{equation*} \begin{aligned}R(x)\amp = |f(x)-P_{n}(x)| = \biggl\vert \frac{f^{(n+1)}(\xi(x))}{(n+1)!}\prod_{i=0}^{n} (x-x_{i}) \biggr\vert.\end{aligned} \end{equation*}
First, there is the term \(f^{(n+1)}(\xi(x))\) for \(\xi \in [0,\pi]\) and \(n=2\text{.}\) Since the function is the sine function, this can be bounded by 1. Next, is the term:
\begin{equation*} \begin{aligned}E(x)\amp =(x-0)(x-\pi/2)(x-\pi)\end{aligned} \end{equation*}
We also need to find the maximum of this error, which must occur when \(E'(x)=0\) or
\begin{equation*} \begin{aligned}E'(x)\amp = (x-\pi/2)(x-\pi) + x(x-\pi)+x(x-\pi/2) \\\amp = 3x^{2} - 3\pi x + \frac{\pi^{2}}{2}=0\end{aligned} \end{equation*}
which has a zero when \(x=(3\pi \pm \sqrt{9\pi^{2}-6\pi^{2}})/6=\frac{\pi}{2}(1 \pm \sqrt{3}/3)\) and \(|E(x)|\) at either of these points is \(\pi^{3}/(12\sqrt{3})\text{.}\) Therefore a bound on the error:
\begin{equation*} \begin{aligned}\biggl\vert\frac{f^{(n+1)}(\xi(x))}{(n+1)!}(x-0)(x-\pi/2)(x-\pi) \biggr\vert \leq \frac{1}{3!}\frac{\pi^{3}}{12 \sqrt{3}}\approx 0.2486.\end{aligned} \end{equation*}
Thus the approximation (using the polynomial) in place of the sine function on this interval is bounded by 0.2486.

Subsection 4.2.4 Advantages and Disadvantages of the Lagrange form

We will soon see an alternative way of finding a polynomial interpolant. Before moving on, let’s look at the advantages and disadvantages:
Advantages: The formula for computing the Lagrange form is relatively simple and easy (as we will see) to understand. The other advantage is the error formula just proved above is easy to derive because of the Lagrange form.
Disadvantages: The main disadvantage is seen by considering the following scenario: Let’s return to the problem seen above in that we found a polynomial interpolant through the data:
\(x\) 0 0.25 0.50 0.75 1
\(P(X \gt x)\) 0.0000 0.0987 0.1915 0.2734 0.3413
Consider the case of another point is found (perhaps we know that \(P(X \gt 0.6)= 0.2257\)) and we would like to produce a new polynomial that incorporates this new point.
Unfortunately, the Lagrange form requires that we start from scratch and rebuild the polynomial. That is, we can’t use the current polynomial to find a new polynomial. We will see that this is possible with the Newton Divided Differences in the next section.