INTERPOLATION
Read sections 18.1 and 18.2 in the textbook
INTERPOLATION
In some cases we have to estimate intermediate values between precise data points. The
most common method used for this purpose is polynomial interpolation
the general formula for an nth-order polynomial is
𝑓 𝑥 = 𝑎0 + 𝑎1 𝑥 + 𝑎2 𝑥 2 + ⋯ + 𝑎𝑛 𝑥 𝑛
For n + 1 data points, there is one and only one polynomial of order n that passes through
all the points.
first-order Second-order third-order
connecting two points connecting three points connecting four points
INTERPOLATION
There are a variety of mathematical formats in which this polynomial can
be expressed.
The Newton and the Lagrange polynomials are the most popular and
useful forms.
THE INTERPOLATION PROBLEM
Given a set of n+1 points:
x0 , f ( x0 ), x1, f ( x1 ), ...., xn , f ( xn )
Find an nth order polynomial:
f n (x)
that passes through all points, such that:
f n ( xi ) f ( xi ) for i 0,1, 2,..., n
GENERAL NTH ORDER NEWTON’S DIVIDED DIFFERENCES
INTERPOLATION
Given any n+1 points:
x0 , f ( x0 ), x1 , f ( x1 ), ..., xn , f ( xn )
The polynomial that interpolates all points is:
f n ( x) b0 b1 x x0 b2 x x0 x x1 ... bn x x0 ... x xn 1
b0 f ( x0 )
b1 f [ x0 , x1 ]
....
bn f [ x0 , x1 , ... , xn ]
DIVIDED DIFFERENCES
f [ x0 ] f ( x0 ) Zeroth order DD
f [ x1 ] f [ x0 ]
f [ x0 , x1 ] First order DD
x1 x0
f [ x1 , x2 ] f [ x0 , x1 ]
f [ x0 , x1 , x2 ] Second order DD
x2 x0
............
f [ x1 , x2 ,..., xn ] f [ x0 , x1 ,..., xn 1 ]
f [ x0 , x1 ,..., xn ]
xn x0
DIVIDED DIFFERENCE TABLE
x F[ ] First second F[ , , ,]
x0 F[x0] F[x0,x1] F[x0,x1,x2] F[x0,x1,x2,x3]
x1 F[x1] F[x1,x2] F[x1,x2,x3]
x2 F[x2] F[x2,x3]
x3 F[x3]
EXAMPLE
Estimate the natural logarithm of 2 using
1. linear interpolation(first-order polynomial)
2. Quadratic interpolation(second-order polynomial)
3. Cubic interpolation(third-order polynomial)
x 1 4 5 6
F(x) 0 1.386294 1.609438 1.791759
Note that the true value of ln 2 is 0.6931472.
x F(x) first second third
1 0 0.462098 -0.0597385 0.0078654
4 1.386294 0.223144 -0.0204115
5 1.609438 0.182321
6 1.791759
𝑓1 𝑥 = 𝑏0 + 𝑏1 𝑥 − 𝑥0 ⇒ 𝑓1 2 = 0 + 0.462098 2 − 1 = 0.462098
𝑓2 𝑥 = 𝑏0 + 𝑏1 𝑥 − 𝑥0 + 𝑏2 𝑥 − 𝑥0 𝑥 − 𝑥1
𝑓2 2 = 0 + 0.462098 2 − 1 − 0.0597385(2 − 1)(2 − 4) = 0.581575
𝑓3 𝑥 = 𝑏0 + 𝑏1 𝑥 − 𝑥0 + 𝑏2 𝑥 − 𝑥0 𝑥 − 𝑥1 + 𝑏3 𝑥 − 𝑥0 𝑥 − 𝑥1 𝑥 − 𝑥2
𝑓3 2 = 0 + 0.462098 2 − 1 − 0.0597385 2 − 1 2 − 4 + 0.0078654 2 − 1 2 − 4 (2 − 5) = 0.6287674
First-order polynomial Third-order polynomial
ln(x) Second-order polynomial
𝜀𝑡 = 33.3%(𝑓𝑖𝑟𝑠𝑡 − 𝑜𝑟𝑑𝑒𝑟 𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙)
𝜀𝑡 = 16.1%(𝑠𝑒𝑐𝑜𝑛𝑑 − 𝑜𝑟𝑑𝑒𝑟 𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙)
𝜀𝑡 = 9.3%(𝑡ℎ𝑖𝑟𝑑 − 𝑜𝑟𝑑𝑒𝑟 𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙)
Errors of Newton’s Interpolating Polynomials
• The truncation error for the Taylor series could be expressed generally as
𝑓 𝑛+1
(𝜉)
𝑅𝑛 = (𝑥𝑖+1 −𝑥𝑖 )𝑛+1
𝑛+1 !
where ξ is somewhere in the interval 𝑥𝑖 to 𝑥𝑖 . For an nth-order interpolating polynomial, an
analogous relationship for the error is
𝑓 𝑛+1 𝜉
𝑅𝑛 = 𝑥 − 𝑥0 𝑥 − 𝑥1 … (𝑥 − 𝑥𝑛 )
𝑛+1 !
where ξ is somewhere in the interval containing the unknown and the data.
• An alternative formulation uses a finite divided difference to approximate the (n + 1)th derivative,
𝑅𝑛 = 𝐹[𝑥, 𝑥𝑛 , 𝑥𝑛−1 , … , 𝑥0 ] 𝑥 − 𝑥0 𝑥 − 𝑥1 … (𝑥 − 𝑥𝑛 )
• Because this equation contains the unknown f(x), it cannot be solved for the error.
• If an additional data point f(𝑥𝑛+1 ) is available, then the equation can be used to estimate the error
𝑅𝑛 ≅ 𝐹[𝑥𝑛+1 , 𝑥𝑛 , 𝑥𝑛−1 , … , 𝑥0 ] 𝑥 − 𝑥0 𝑥 − 𝑥1 … (𝑥 − 𝑥𝑛 )
EXAMPLE
Estimate the error for the second-order polynomial interpolation at x =2 for the
following given data.
X Y
1 0
4 1.386294
5 1.609438
6 1.791759
SOLUTION
x F(x) first second third
1 0 0.462098 -0.0597385 0.0078654
4 1.386294 0.223144 -0.0204115
5 1.609438 0.182321
6 1.791759
𝑅𝑛 ≅ 𝐹[𝑥𝑛+1 , 𝑥𝑛 , 𝑥𝑛−1 , … , 𝑥0 ] 𝑥 − 𝑥0 𝑥 − 𝑥1 … (𝑥 − 𝑥𝑛 )
𝑅2 ≅ 𝐹[𝑥3 , 𝑥2 , 𝑥1 , 𝑥0 ] 𝑥 − 𝑥0 𝑥 − 𝑥1 (𝑥 − 𝑥2 )
𝑅2 ≅ 0.0078654 2 − 1 2 − 4 (2 − 5)
𝑅2 ≅ 0.0471924
LAGRANGE INTERPOLATING POLYNOMIALS
The Lagrange interpolating polynomial is simply a reformulation of the Newton
polynomial that avoids the computation of divided difference
n
f n ( x) f xi i ( x)
i 0
x x
n
i ( x) x x
j 0, j i
j
i j
LAGRANGE INTERPOLATING POLYNOMIALS
For example:
when n=1
(𝑥 − 𝑥1 ) (𝑥 − 𝑥0 )
𝑓1 𝑥 = 𝑓 𝑥𝑜 + 𝑓(𝑥1 )
(𝑥0 −𝑥1 ) (𝑥1 −𝑥0 )
when n=2
(𝑥 − 𝑥1 )(𝑥 − 𝑥2 ) 𝑥 − 𝑥0 𝑥 − 𝑥2 (𝑥 − 𝑥0 )(𝑥 − 𝑥1 )
𝑓2 𝑥 = 𝑓 𝑥𝑜 + 𝑓 𝑥1 + 𝑓(𝑥2 )
(𝑥0 −𝑥1 )(𝑥0 −𝑥2 ) (𝑥1 −𝑥0 )(𝑥1 −𝑥2 ) (𝑥2 −𝑥0 )(𝑥2 −𝑥1 )
EXAMPLE
Use a Lagrange interpolating polynomial of the first and second order to evaluate ln 2
on the basis of the data given in the following table.
x 1 4 5
F(x) 0 1.386294 1.609438
SOLUTION
for n=1
(𝑥 − 𝑥1 ) (𝑥 − 𝑥0 )
𝑓1 𝑥 = 𝑓 𝑥𝑜 + 𝑓(𝑥1 )
(𝑥0 −𝑥1 ) (𝑥1 −𝑥0 )
2−4 2−1
𝑓1 2 = 0 ∗ + 1.386294 ∗ = 0.462098
1−4 4−1
for n=2
(𝑥 − 𝑥1 )(𝑥 − 𝑥2 ) 𝑥 − 𝑥0 𝑥 − 𝑥2 (𝑥 − 𝑥0 )(𝑥 − 𝑥1 )
𝑓2 𝑥 = 𝑓 𝑥𝑜 + 𝑓 𝑥1 + 𝑓(𝑥2 )
(𝑥0 −𝑥1 )(𝑥0 −𝑥2 ) (𝑥1 −𝑥0 )(𝑥1 −𝑥2 ) (𝑥2 −𝑥0 )(𝑥2 −𝑥1 )
2−4 2−5 2−1 2−5 2−1 2−4
𝑓2 2 = 0 ∗ + 1.386294 ∗ + 1.609438 = 0.581575
1−4 1 −5 4−1 4 −5 5−1 5 −4
HIGH ORDER POLYNOMIALS INTERPOLATION
20th order polynomial
5th order polynomial
1
𝑓 𝑥 = 1+25𝑥 2
ERRORS IN POLYNOMIAL INTERPOLATION
Polynomial interpolation may lead to large errors (especially for high order
polynomials).
BE CAREFUL
SUMMARY
Newton Divided Difference Lagrange
It takes more space to store divided Easier to Implement By computer
difference. Programming
Better when the rank of the Preferable when the order is
polynomial is unknown a priori known a priori and one
interpolation is performed.
The error equation can be easily The error equation is not easy
integrated into the algorithm integrated since it needs to
compute divided difference.
