Polynomial Interpolation
CS/SE 4X03
Ned Nedialkov McMaster University February 2, 2021
Outline
The problem
Representation
Basis functions
Monomial interpolation
Uniqueness of the interpolating polynomial Lagrange interpolation
The problem Representation Basis functions Monomial Uniqueness Lagrange The problem
• Data fitting. Given data points (xi,yi)ni=0 find a function v(x) that fits the data:
v(xi) = yi, i = 0,…,n
• Approximating functions. For a complicated function f(x) find a simpler v(x) that approximates f(x)
E.g. may have values of f(x) at three points and use linear interpolation
• We can use v(x) to find v(x∗) for x∗ ̸= x0,x1,…xn
• We may need derivatives or an integral of the underlying function
Copyright © 2021 N. Nedialkov. All rights reserved. 3/11
The problem Representation Basis functions Monomial Uniqueness Lagrange Representation
n
v(x) = cj φj (x) = c0φ0(x) + c1φ1(x) + · · · + cnφn(x)
j=0
• The cj are unknown coefficients
• The φj are basis functions
They must be linearly independent Ifv(x)=0forallxthencj =0forallj
v(xi) = c0φ0(xi) + c1φ1(xi) + · · · + cnφn(xi) = yi, for all i = 0,…,n
Copyright © 2021 N. Nedialkov. All rights reserved. 4/11
The problem Representation Basis functions Monomial Uniqueness Lagrange Representation cont.
φ0(x0) φ0(x1)
φ1(x0)
φ1(x1)
· · · · · ·
φn(x0) c0 y0 φn(x1) c1 y1
. . = . φ0(xn) φ1(xn) · · · φn(xn) cn yn
.
Linear system of (n + 1) equations for ci
. …..
Copyright © 2021 N. Nedialkov. All rights reserved.
5/11
The problem Representation Basis functions Monomial Uniqueness Lagrange Basis functions
• Monomial basis
φj(x) = xj, j = 0,1,…,n v(x)=c0 +c1x+c2x2 +···+cnxn
• Trigonometric functions, e.g.
φj(x) = cos(jx), j = 0,1,…,n
Useful in signal processing, for wave and other periodic behavior
• Piecewise interpolation: linear, quadratic, cubic, splines
Copyright © 2021 N. Nedialkov. All rights reserved. 6/11
The problem Representation Basis functions Monomial Uniqueness Lagrange Monomial interpolation
• Let
• Example: interpolate {(1, 1), (2, 3), (4, 3)}
p(x)=pn(x)=c0 +c1x+c2x2 +···+cnxn
p(1)=c0 +c1 +1c2 =1 p(2)=c0 +2c1 +4c2 =3 p(4)=c0 +4c1 +16c2 =3
• Solve linear system to obtain
p2(x) = −7 + 4x − 2×2
33
Copyright © 2021 N. Nedialkov. All rights reserved. 7/11
The problem Representation Basis functions Monomial Uniqueness Lagrange Uniqueness of the interpolating polynomial
1 x 0 x 20 · · · x n0 c 0 y 0 1 x1 x2 ··· xn c1 y1
11 . . . . . = .
1 xn x2n ··· xn cn yn • The coefficient matrix is a Vandermonde matrix
Denote it by X
• det(X) = n−1 n (xj − xi)
i=0 j =i+1
• If all xi are distinct, det(X) ̸= 0
• We have a unique solution for the coefficients
• If all xi a distinct, there is a unique polynomial of deg ≤ n that interpolates the data
Copyright © 2021 N. Nedialkov. All rights reserved. 8/11
The problem Representation Basis functions Monomial Uniqueness Lagrange Uniqueness of the interpolating polynomial cont.
We can solve the above system to find the coefficients, but
• It can become poorly conditioned • Work is O(n3)
• Difficult to add new points
Copyright © 2021 N. Nedialkov. All rights reserved. 9/11
The problem Representation Basis functions Monomial Uniqueness Lagrange Lagrange interpolation
• Lagrange polynomial
Lj(xi)= 1 ifi=j
0 ifi̸=j
• Polynomial is given by p(x) = nj=0 yjLj(x)
Then
n
p(xi) = yjLj(xi) =
j=0
= y0L0(xi) + · · · + yiLi(xi) + · · · + ynLn(xi) = 0 + · · · + yi1 + · · · + 0 = yi
Copyright © 2021 N. Nedialkov. All rights reserved.
10/11
The problem Representation Basis functions Monomial Uniqueness Lagrange Lagrange interpolation cont.
Lj (x) = (x − x0 )(x − x1 ) · · · (x − xj −1 )(x − xj +1 ) · · · (x − xn ) (xj −x0)(xj −x1)···(xj −xj−1)(xj −xj+1)···(xj −xn)
=n x−xi i=0,i̸=j xj − xi
Example: write the Lagrange polynomial for (1, 1), (2, 3), (4, 3)
Copyright © 2021 N. Nedialkov. All rights reserved. 11/11