$$\require{cancel}$$

# 1.11: Fitting a Polynomial to a Set of Points - Lagrange Polynomials and Lagrange Interpolation

• • Contributed by Jeremy Tatum
• Emeritus Professor (Physics & Astronomy) at University of Victoria

Given a set of $$n$$ points on a graph, there any many possible polynomials of sufficiently high degree that go through all $$n$$ of the points. There is, however, just one polynomial of degree less than $$n$$ that will go through them all. Most readers will find no difficulty in determining the polynomial. For example, consider the three points (1 , 1), (2 , 2) , (3 , 2). To find the polynomial $$y = a_0 + a_1 x + a_2 x^2$$ that goes through them, we simply substitute the three points in turn and hence set up the three simultaneous Equations

\begin{array}{c c l}
1 & = & a_0 + a_1 + a_2 \\
2 & = & a_0 + 2a_1 + 4a_2 \\
2 & = & a_0 + 3a_1 + 9a_2 \\
\label{1.11.1} \tag{1.11.1}
\end{array}

and solve them for the coefficients. Thus $$a_0 = -1$$, $$a_1 = 2.5$$ and $$a_3 = -0.5$$. In a similar manner we can fit a polynomial of degree $$n − 1$$ to go exactly through $$n$$ points. If there are more than $$n$$ points, we may wish to fit a least squares polynomial of degree $$n − 1$$ to go close to the points, and we show how to do this in sections 1.12 and 1.13. For the purpose of this section (1.11), however, we are interested in fitting a polynomial of degree $$n − 1$$ exactly through $$n$$ points, and we are going to show how to do this by means of Lagrange polynomials as an alternative to the method described above.

While the smallest-degree polynomial that goes through $$n$$ points is usually of degree $$n − 1$$, it could be less than this. For example, we might have four points, all of which fit exactly on a parabola (degree two). However, in general one would expect the polynomial to be of degree $$n − 1$$, and, if this is not the case, all that will happen is that we shall find that the coefficients of the highest powers of $$x$$ are zero.

That was straightforward. However, what we are going to do in this section is to fit a polynomial to a set of points by using some functions called Lagrange polynomials. These are functions that are described by Max Fairbairn as “cunningly engineered” to aid with this task.

Let us suppose that we have a set of $$n$$ points:

$(x_1, y_1) , (x_1, y_1), (x_2, y_2) , ... \ ...(x_i, y_i), ... \ ...(x_n, y_n),$

and we wish to fit a polynomial of degree $$n-1$$ to them.

I assert that the function

$y = \sum_{i=1}^n y_i L_i (x) \label{1.11.2} \tag{1.11.2}$

is the required polynomial, where the $$n$$ functions , $$L_i(x)$$, $$i=1,n,$$ are $$n$$ Lagrange polynomials, which are polynomials of degree $$n − 1$$ defined by

$L_i(x) = \prod^n_{j=1, \ j \neq i} \frac{x- x_j}{x_i - x_j} \label{1.11.3} \tag{1.11.3}$

Written more explicitly, the first three Lagrange polynomials are

$L_1(x) = \frac{(x- x_2)(x-x_3)(x-x_4)... \ ... (x - x_n)}{(x_1-x_2) (x_1 - x_3) (x_1 - x_4) ... \ ... (x_1 - x_n)}, \label{1.11.4}\tag{1.11.4}$

and $L_2(x) = \frac{(x-x_1)(x-x_3)(x-x_4) ... \ ... ( x - x_n)}{(x_2 - x_1)(x_2 - x_3) (x_2 - x_4) ... \ ... (x_2 - x_n)} \label{1.11.5} \tag{1.11.5}$

and $L_3 (x) = \frac{(x-x_1) (x-x_2)(x-x_4)... \ ...(x-x_n)}{(x_3 - x_1) (x_3 - x_2) (x_3 - x_4) ... \ ... (x_3 - x_n)} \label{1.11.6} \tag{1.11.6}$

At first encounter, this will appear meaningless, but with a simple numerical example it will become clear what it means and also that it has indeed been cunningly engineered for the task.

Consider the same points as before, namely (1 , 1), (2 , 2) , (3 , 2). The three Lagrange polynomials are

$L_1(x) = \frac{(x-2)(x-3)}{(1-2)(1-3)} = \frac{1}{2} (x^2 - 5x + 6), \label{1.11.7} \tag{1.11.7}$

$L_2(x) = \frac{(x-1)(x-3)}{(2-1)(2-3)} = -x^2 + 4x - 3 , \label{1.11.8} \tag{1.11.8}$

$L_3 (x) = \frac{(x-1)(x-2)}{(3-1)(3-2)} = \frac{1}{2} (x^2 - 3x + 2) . \label{1.11.9} \tag{1.11.9}$

Equation $$\ref{1.11.2}$$ for the polynomial of degree $$n − 1$$ that goes through the three points is, then,

$y = 1 \times \frac{1}{2} (x^2 - 5x + 6) + 2 \times ( -x^2 + 4x - 3) + 2 \times \frac{1}{2} (x^2 - 3x + 2); \label{1.11.10} \tag{1.11.10}$

that is $y = - \frac{1}{2} x^2 + \frac{5}{2} x - 1 , \label{1.11.11} \tag{1.11.11}$

which agrees with what we got before.

One way or another, if we have found the polynomial that goes through the $$n$$ points, we can then use the polynomial to interpolate between nontabulated points. Thus we can either determine the coefficients in $$y = a_0 + a_1 x^2 + a_2 x^2 ...$$ by solving $$n$$ simultaneous Equations, or we can use Equation $$\ref{1.11.2}$$ directly for our interpolation (without the need to calculate the coefficients $$a_0$$, $$a_1$$, etc.), in which case the technique is known as Lagrangian interpolation. If the tabulated function for which we need an interpolated value is a polynomial of degree less than $$n$$, the interpolated value will be exact. Otherwise it will be approximate. An advantage of this over Besselian interpolation is that it is not necessary that the function to be interpolated be tabulated at equal intervals in $$x$$. Most mathematical functions and astronomical tables, however, are tabulated at equal intervals, and in that case either method can be used.

Let us recall the example that we had in Section 1.10 on Besselian interpolation, in which we were asked to estimate the value of $$\sin 51^\circ$$ from the table

\begin{array}{r l}
x^\circ & \sin x \\
\\
0 & 0.0 \\
30 & 0.5 \\
60 & \sqrt{3}/2 = 0.86603 \\
90 & 1.0 \\
\end{array}

The four Lagrangian polynomials, evaluated at $$x = 51$$, are

$L_1(51) = \frac{(51-30)(51-60)(51-90)}{(0-30)(0-60)(0-90)} = - 0.0455,$

$L_2(51) = \frac{(51-0)(51-60)(51-90)}{(30-0)(30-60)(30-90)} = +0.3315,$

$L_3(51) = \frac{(51-0)(51-30)(51-90)}{(60-0)(60-30)(60-90)} = +0.7735,$

$L_4 (51) = \frac{(51-0)(51-30)(51-60)}{(90-0)(90-30)(90-60)} = -0.0595.$

Equation $$\ref{1.11.2}$$ then gives us

$$\sin 51^\circ = 0 \times (-0.0455) + 0.5 \times 0.3315 + 0.86603 \times 0.7735 + 1 \times (-0.0595)$$
$$= 0.776$$.

This is the same as we obtained with Besselian interpolation, and compares well with the correct value of $$0.777$$. I point out again, however, that the Lagrangian method can be used if the function is not tabulated at equal intervals, whereas the Besselian method requires tabulation at equal intervals.