Numerical Analysis: Part Four

Chapter 17: Polynomial Interpolation

Prof. Sung Jin Yoo

School of Electrical and Electronics Engineering

Chung-Ang University

Numerical analysis Chapter 17

17. Polynomial Interpolation – Introduction to interpolation

 Polynomial interpolation
• You will frequently have occasions to estimate intermediate values
between precise data points.
• The function you use to interpolate must pass through the actual data
points - this makes interpolation more restrictive than fitting.
• The most common method for this purpose is polynomial interpolation,
where an (n-1)th order polynomial is solved that passes through n data
points:
f (x)  a1  a2 x  a3 x 2  an x n1
MATLAB version :
f (x)  p1 x n1  p2 x n2  pn1 x  pn

Numerical analysis Chapter 17

17. Polynomial Interpolation – Introduction to interpolation

 Determining polynomial coefficients

• Since polynomial interpolation provides as many basis functions as
there are data points (n), the polynomial coefficients can be found
exactly using linear algebra.
ex 17.1)

Sol.)

Numerical analysis Chapter 17

17. Polynomial Interpolation – Introduction to interpolation

 Polynomial Interpolation Problems

x1n1 x1n2  x1 1 p1   f x1  
 n1   f x 
• General form: x
 2
x2n2  x2 1  
 2   2 
p  

 n1         
xn1
n2
xn1  xn1 1pn1  f xn1 
   

xn  xn  pn   f xn  
1
n1
xnn2
 The matrices are very ill-conditioned. That is, the solutions are very
sensitive to round-off errors. So, alternative approaches are required.
• MATLAB’s built in polyfit and polyval commands can also be used - all
that is required is making sure the order of the fit for n data points is n-1.

Numerical analysis Chapter 17

17. Polynomial Interpolation – Newton Interpolating Polynomials

• Another way to express a polynomial interpolation is to use Newton’s

interpolating polynomial.

 Linear interpolation
• The first-order Newton interpolating
polynomial may be obtained from
linear interpolation and similar
triangles, as shown.
• The resulting formula based on
known points x1 and x2 and the
values of the dependent function at
those points is:
f (x 2 ) - f (x 1 )
f1 (x ) = f (x 1 ) + (x - x1 )
x 2 - x1
f1 (x ) : a first-order interpolating polynomial
 Newton linear-interpolation formula
Numerical analysis Chapter 17
17. Polynomial Interpolation – Newton Interpolating Polynomials

 Linear interpolation (cont.)

Ex 17.2) Estimate the natural logarithm of 2 using linear interpolation.
1) Interval ln1=0 and ln6=1.791759.
2) Interval ln1=0 and ln4=1.386294.
Sol).
1) Interval ln1=0 and ln6=1.791759

2) Interval ln1=0 and ln4=1.386294

Numerical analysis Chapter 17

17. Polynomial Interpolation – Newton Interpolating Polynomials

 Quadratic interpolation
• The second-order Newton interpolating polynomial introduces some
curvature to the line connecting the points, but still goes through the first
two points.
• The resulting formula based on known points x1, x2, and x3 and the
values of the dependent function at those points is:

f 2  x   b1  b2  x  x1   b3  x  x1  x  x2 

f x3   f x2  f x2   f x1 


f x2   f x1  x 3  x2 x2  x1
f2 x  f x1    1
x  x  x  x1 x  x2 
x2  x1 x3  x1

Numerical analysis Chapter 17

17. Polynomial Interpolation – Newton Interpolating Polynomials

 Quadratic interpolation (cont.)

ex 17.3) Employ a second-order Newton
polynomial to estimate ln 2 with three
points

Sol.)

Numerical analysis Chapter 17

17. Polynomial Interpolation – Newton Interpolating Polynomials

 General form of newton’s interpolation polynomials

• In general, an (n-1)th Newton interpolating polynomial has all the terms
of the (n-2)th polynomial plus one extra.
• The general formula is:

fn1 x  b1  b2 x  x1     bn x  x1 x  x2 x  xn1 

where
b1  f x1 
b2  f x2 , x1 
b3  f x3 , x2 , x1 

bn  f xn , xn1 ,, x2 , x1 

and the f[…] represent divided differences.

Numerical analysis Chapter 17

17. Polynomial Interpolation – Newton Interpolating Polynomials

 General form of newton’s interpolation polynomials (cont.)

• Divided difference are calculated as follows:
f xi   f x j 
f xi , x j 
xi  x j
f xi , x j  f x j , xk 
f xi , x j , xk 
xi  x k
f xn , xn1 ,, x2   f xn1 , xn2 ,, x1 
f xn , xn1 ,, x2 , x1  
 xn  x1

• Divided differences are calculated using divided difference of a smaller

number of terms:

Numerical analysis Chapter 17

17. Polynomial Interpolation – Newton Interpolating Polynomials

 General form of newton’s interpolation polynomials (cont.)

ex 17.4) Estimate ln 2 with a third-order Newton’s interpolation polynomial.

Sol.) The third-order polynomial

The first divided differences The second divided differences

The third divided differences

Numerical analysis Chapter 17

17. Polynomial Interpolation – Newton Interpolating Polynomials

 General form of newton’s interpolation polynomials (cont.)

ex 17.4) Estimate ln 2 with a third-order Newton’s interpolation polynomial.
Sol.) (cont.)

Numerical analysis Chapter 17

17. Polynomial Interpolation
– Lagrange Interpolating Polynomials

 Lagrange Interpolating Polynomials

• Another method that uses shifted value to express an interpolating
polynomial is the Lagrange interpolating polynomial.
• The differences between a simply polynomial and Lagrange interpolating
polynomials for first and second order polynomials are:

Order Simple Lagrange

1st f1 (x)  a1  a2 x f1 (x)  L1 f x1   L2 f x2 
2nd f2 (x)  a1  a2 x  a3 x 2 f2 (x)  L1 f x1   L2 f x2   L3 f x 3 
where Li are weighting coefficients that are functions of x.

Numerical analysis Chapter 17

17. Polynomial Interpolation
– Lagrange Interpolating Polynomials

 Linear interpolation
• The first-order Lagrange
interpolating polynomial may
be obtained from a weighted
combination of two linear
interpolations, as shown.
• The resulting formula based
on known points x1 and x2
and the values of the
dependent function at those
points is:
f1 (x)  L1 f x1   L2 f x2 
x  x2 x  x1
L1  , L2 
x1  x2 x2  x1  Linear Lagrange interpolating polynomial
x  x2 x  x1
f1 (x)  f x1   f x2 
x1  x2 x2  x1
Numerical analysis Chapter 17
17. Polynomial Interpolation
– Lagrange Interpolating Polynomials

 High-order Lagrange polynomials

• In general, the Lagrange polynomial interpolation for n points is:
n
fn1 xi    Li x  f xi 
i1

where Li is given by:

x  xj
n
Li x  
x  xj
j1 i
ji

ex 17.5) Use a Lagrange interpolating polynomial of the first and second

order at x  15 .
Sol.)

Numerical analysis Chapter 17

17. Polynomial Interpolation – Extrapolation and oscillations

 Extrapolation
• Extrapolation is the process of
estimating a value of f(x) that
lies outside the range of the
known base points x1, x2, …,
xn.
• Extrapolation represents a
step into the unknown
because the process extends
the curve beyond the known
region,  Extreme care
should be required when
extrapolating!

Numerical analysis Chapter 17

17. Polynomial Interpolation – Extrapolation and oscillations

 Extrapolation Hazards
• The following shows the results of extrapolating a seventh-order
population data set:

 Once we move beyond the range of the date into the realm of
extrapolation, the seventh-order polynomial provides the erroneous
prediction in 2000. Numerical analysis Chapter 17
17. Polynomial Interpolation – Extrapolation and oscillations

 Oscillations
• Higher-order polynomials not only lead to round-off errors due to ill-
conditioning, but can also provide oscillations to an interpolation.

• In the figures below, the dashed line represents an function, the circles
represent samples of the function, and the solid line represents the
results of a polynomial interpolation:
< fourth-order polynomial> < tenth-order polynomial>

 Higher-order polynomials are usually to be avoided due to oscillations.

Numerical analysis Chapter 17