Lagrange Interpolating Polynomials

James Keesling

1 Determining the Coefficients of the Lagrange Interpolat-

ing Polynomial by Linear Equations
It is frequently the case that we will have certain data points, {(x0 , y0 ), (x1 , y1 ), . . . , (xn , yn )},
and will want to fit a curve through these points. In this chapter we will fit a polynomial
of minimal degree through the points. We assume that the points {x0 , x1 , . . . , xn } are all
distinct. In that case we can fit a polynomial of degree n (or possibly less) through the
points. If we write the polynomial in the following form, then we can use the points to
determine the coefficients.

L(x) = a0 + a1 · x + a2 · x2 + · · · + an · xn

y0 = a0 + a1 · x0 + a2 · x20 + · · · an · xn0
y1 = a0 + a1 · x1 + a2 · x21 + · · · an · xn1
..
.
yn = a0 + a1 · xn + a2 · x2n + · · · an · xnn

We can solve these equations using matrices. The vector

 
a0
 a1 
A= . 
 
 .. 
an
is the set of coefficients to be determined. We let M = V [x0 , x1 , . . . , xn ] be the Van-
dermonde Matrix and B be the vector of y values for the interpolation points, then the
coefficients of the polynomial will be given by the following matrix equation.

1
 1 x0 x20 x30 xn0
   
··· y0
1 x1 x2 x3 ··· xn1   y1 
 1 1   
2 3 ··· xn2 
M = 1 x2 x2 x2  Y =  y2 
  
 .. .. ..   .. 
. . .  .
1 xn x2n x3n ··· xn n yn

A = M −1 · Y

2 TI-89 Programs Calculating The Vandermonde Matrix

and the Lagrange Polynomial
Below is a TI-89 program that determines the Vandermonde matrix for a set of points
{x0 , x1 , . . . , xn }. The input variable a a vector [x0 , x1 , . . . , xn ] and the input variable n
indicates that there are n + 1 components in the vector.

:vanderm(a)
:Prgm
:dim(a)[2]-1 → n
:newMat(n+1, n+1) → vander
:For i,1,n+1
:For j,1,n+1
:If a[1,i]=0 and j=1
:Then
:1 → vander[i,j]
:Else
:a[1,i]∧(j-1) → vander[i,j]
:EndIf
:EndFor
:EndFor
:EndPrgm

The program below computes the coefficients of the Lagrange polynomial for the
interpolation points {(x0 , y0 ), (x1 , y1 ), . . . , (xn , y) }. The input variable a is the vector
[x0 , x1 , . . . , xn ]. The input variable b is the vector [y0 , y1 , . . . , yn ]. The variable n is the
degree of the Lagrange polynomial. The variable coef is a column vector with the coeffi-
cients of the polynomial. The output variable P is the Lagrange polynomial with variable
x.

:lagrange(a,b)

2
 :DelVar x
:dim(a)[2]-1 → n
:vanderm(a)
:newMat(n+1,1) → coef
:vander∧(-1)*bT → coef
:0 → p
:For i,0,n
:p+coef[i+1,1]*x∧i → p
:Disp p
:EndFor
:EndPrgm

3 An Alternative Approach Using Special Polynomials

Let us start with the data points, {(x0 , y0 ), (x1 , y1 ), . . . , (xn , yn )}, as above. For i =
0, 1, 2, . . . , n consider the polynomials Li (x) given by the following formula.
n
Y (x − xj )
Li (x) =
(xj − xi )
j=0,j6=i

The polynomial Li (x) has the property that


0 j 6= i
Li (xj ) =
1 j=i
The polynomial Li (x) is the Lagrange polynomial for the interpolation points

{x0 , 0), . . . , (xi−1 , 0), (xi , 1), (xi+1 , 0), . . . , (xn , 0)}.
The Lagrange polynomial L(x) for the original interpolation points is now given by the
following formula.
n
X
L(x) = yi · Li (x)
i=0

It is clear that this polynomial has degree ≤ n and has the property that L(xi ) = yi as
required.
Note that the Lagrange polynomial, L(x), is unique. If there were two such polynomials,
L(x) and P (x), then L(x) − P (x) would be a polynomial of degree ≤ n with n + 1 zeros.
Thus it would have to be identically zero. Thus, we must have L(x) ≡ P (x).

3
4 Newton Polynomials
Another approach to determining the Lagrange polynomial is attributed to Newton. It is
similar to the approach in the previous section in that it uses linear factors that are zero at
the interpolation points. We still assume that we are fitting a polynomial of minimal degree
through the points {(x0 , y0 ), (x1 , y1 ), . . . , (xn , yn )}. The Newton form of the polynomial is
given by the following formula.
n i
!
X Y
L(x) = ai · (x − xi )
i=0 i=0

The problem is to determine the coefficients {ai |i = 0, 1, . . . , n}. It is obvious that a0 = y0 .

One can solve for the coefficients recursively. Or, one can use a method called divided
differences. The algorithm produces an array of the following form.
 
a00 a01 · · · a0n
D =  ... .. .. 

. . 
an0 an1 · · · ann
Where the entries are defined in the following way. The first column are the values
{y0 , . . . , yn }. That is to say:
   
a00 y0
 a01   y1 
 ..  =  .. 
   
 .  .
a0n yn
Each successive column will have one less non-zero entry with
ai+1,j − ai,j
ai,j+1 =
xi+j − xi
The final form of the Newton polynomial is given by setting the coefficients equal to
the first row of the divided difference matrix, ai = a0i .
Below is a program that computes the divided difference matrix and the Newton poly-
nomial from the entries in the matrix.

newtpoly(a,b)
:prgm
:dim(a)[2]-1 → n
:newMat(n+1,n+1) → coef
:For i,1,n+1
:b[1,i] → coef[i,1]

4
 :EndFor
:For j,1,n
:For i,1,n-j+1
:(coef[i+1,j]-coef[i,j])/(a[1,i+j)-a[1,i]) → coef[i,j+1]
:EndFor
:EndFor
:0 → p
:For j,1,n+1
:coef[i,j] → temp
:For i,1,j-1
:coef[1,j] → temp
:For i,1,j-1
:temp · (x-a[1,i]) → temp
:EndFor
:p+temp → p
:EndFor
:Disp coef
:Disp p
:EndPrgm

5 Taylor polynomials
Occasionally one may want other conditions on a polynomial other than fitting values at
different points. The most important is determining the polynomial that has a certain set
of derivatives at a point. In this case the point is taken to be x0 and suppose that the
first n derivatives are given, {a0 = p(x0 ), a1 = p0 (x0 ), . . . , p(n) (x0 )}. Then the polynomial
is given by the following formula.
n 
X ai 
p(x) = · (x − x0 )i
i!
i=0

This is called the Taylor polynomial of degree n centered at the point x0 . More will be
said about these polynomials as they are needed.
Other conditions on polynomials may include requiring that they be orthogonal to one
another as is the case with the Legendre polynomials. These will be dealt with in the
discussion of Gaussian quadrature. There is a built-in function in the TI-89 that will
produce the Taylor polynomial with a given set of derivatives. The syntax of the command
is below.

tayor(f(x),x,n,a)

5
The command produces the Taylor polynomial.
n 
1 di f (x)
X 
i
p(x) = · (x − a)
i! dxn x=a
i=0