Chapter3
Polynomial Interpolation
The Concept of Interpolation:
Interpolation is a mathematical method used to find an approximate value of an unknown function at a
certain point using a set of known values of the function at specific points.
The goal of interpolation is to construct an approximate function (called the interpolation function) that
passes through all the known points and is used to estimate unknown function values within the given range.
Let 𝑓 be an unknown function whose images 𝑦0 , 𝑦1 , 𝑦2 , … , 𝑦𝑛 are known at the points 𝑥0 , 𝑥, 𝑥2 , … , 𝑥𝑛
If the interpolation function is a polynomial 𝑝(𝑥) , then:
𝑝 𝑥𝑖 = 𝑦𝑖 , 𝑖 = 0,1,2, … . 𝑛
Theorem : Polynomial Interpolation
Given 𝑛 + 1 distinct points 𝑥0 , 𝑥, 𝑥2 , … , 𝑥𝑛 and corresponding values 𝑦0 , 𝑦1 , 𝑦2 , … , 𝑦𝑛 , there exists a unique
polynomial 𝑝 of degree less than or equal to 𝑛 such that 𝑃(𝑥𝑖 ) = 𝑦𝑖 for 𝑖 = 0, … , 𝑛.
Lagrange Formula:
Theorem :
Given 𝑛 + 1 distinct points 𝑥0 , 𝑥, 𝑥2 , … , 𝑥𝑛 and corresponding values 𝑦0 , 𝑦1 , 𝑦2 , … , 𝑦𝑛 , there exists a unique
polynomial 𝑃𝑛 such that 𝑃𝑛 (𝑥𝑖 ) = 𝑦𝑖 . This polynomial can be written in the form:
𝑛 𝑛
𝑥 − 𝑥𝑗
𝑃𝑛 𝑥 = 𝐿𝑖 (𝑥)𝑦𝑖 , where 𝐿𝑖 𝑥 = ,𝑗 ≠ 𝑖
𝑥𝑖 − 𝑥𝑗
𝑖=0 𝑗 =0
This relation is called the Lagrange interpolation formula, and the polynomials 𝐿𝑖 are the characteristic
polynomials (of Lagrange).
𝐿𝑖 (𝑥) have the property that
1 if 𝑗 = 𝑖
𝐿𝑖 𝑥𝑗 =
0 if 𝑗 ≠ 𝑖
Example
Estimate the value of 𝑓(3.3) using the Lagrange interpolation formula based on the following data table:
(𝑥 − 𝑥1 )(𝑥 − 𝑥2 )(𝑥 − 𝑥3 ) (𝑥 − 1)(𝑥 − 3)(𝑥 − 4) −𝑥 3 2𝑥 2 19𝑥
𝐿0 𝑥 = = = + − +1
(𝑥0 − 𝑥1 )(𝑥0 − 𝑥3 )(𝑥0 − 𝑥3 ) (−1)(−3)(−4) 12 3 12
(𝑥 − 𝑥0 )(𝑥 − 𝑥2 )(𝑥 − 𝑥3 ) 𝑥(𝑥 − 3)(𝑥 − 4) 𝑥 3 7𝑥 2
𝐿1 𝑥 = = = − + 2𝑥
(𝑥1 − 𝑥0 )(𝑥1 − 𝑥2 )(𝑥1 − 𝑥3 ) (1)(−2)(−3) 6 6
(𝑥 − 𝑥0 )(𝑥 − 𝑥1 )(𝑥 − 𝑥3 ) 𝑥(𝑥 − 1)(𝑥 − 4) −𝑥 3 5𝑥 2 2
𝐿2 𝑥 = = = + − 𝑥
(𝑥2 − 𝑥0 )(𝑥2 − 𝑥1 )(𝑥2 − 𝑥3 ) (3)(2)(−1) 6 6 3
(𝑥 − 𝑥0 )(𝑥 − 𝑥1 )(𝑥 − 𝑥2 ) 𝑥(𝑥 − 1)(𝑥 − 3) 𝑥 3 𝑥 2 𝑥
𝐿3 𝑥 = = = − +
(𝑥3 − 𝑥0 )(𝑥3 − 𝑥1 )(𝑥3 − 𝑥2 ) (4)(3)(1) 12 3 4
𝑝 𝑥 = 𝐿0 𝑥 𝑦0 + 𝐿1 𝑥 𝑦1 + 𝐿2 𝑥 𝑦2 + 𝐿3 𝑥 𝑦3
𝑝(𝑥) = 𝑥 2 − 1
𝑓 3.3 ≈ 𝑝 3.3 = 9.89
Newton's method
Let (𝑥𝑖 , 𝑦𝑖 ) for 𝑖 = 0,1,2, … , 𝑛 be a set of 𝑛 + 1 distinct points.
The divided difference of order 1 is defined as:
𝑓(𝑥𝑖+1 ) − 𝑓(𝑥𝑖 )
𝑓 𝑥𝑖 , 𝑥𝑖+1 =
𝑥𝑖+1 −𝑥𝑖
The divided difference of order 2 is defined as:
𝑓 𝑥𝑖+1 , 𝑥𝑖+2 − 𝑓 𝑥𝑖 , 𝑥𝑖+1
𝑓 𝑥𝑖 , 𝑥𝑖+1 , 𝑥𝑖+2 =
𝑥𝑖+2 −𝑥𝑖
The divided difference of order 𝑛 is defined as:
𝑓 𝑥1 , 𝑥2 , … , 𝑥𝑛 − 𝑓 𝑥0 , 𝑥1 , … , 𝑥𝑛−1
𝑓 𝑥0 , 𝑥1 , 𝑥2 , … . , 𝑥𝑛 =
𝑥𝑛 − 𝑥0
The divided differences can be calculated by arranging them in a table as follows:
Theorem: Newton's Formula
Let (𝑥𝑖 , 𝑦𝑖 ) for 𝑖 = 0,1,2, … , 𝑛 be a set of 𝑛 + 1 distinct points. The interpolation polynomial in the
form of Newton's is given by:
𝑝 𝑥 = 𝑓 𝑥0 + 𝑓 𝑥0 , 𝑥1 , 𝑥2 , … , 𝑥𝑖 𝑥 − 𝑥0 𝑥 − 𝑥1 … . . 𝑥 − 𝑥𝑖−1
𝑖=0
Where
Example:
To find the Newton interpolation polynomial for the function 𝑓 passing through the points
0,1 , (1,2), (2,9), 𝑎𝑛𝑑 (3,28), we construct the divided difference table and use it to form the.
Estimate the value of 𝑓(2.3).
𝑝 𝑥 = 𝑥3 + 1
𝑓(2.3) ≈ 𝑝 2.3 = 13.167
𝑝3 𝑥 = 𝑥 3 + 1
𝑓 2.3 = 13.1670
Theorem: Error of interpolation
Suppose 𝑥0 , 𝑥1 , . . . , 𝑥𝑛 are distinct numbers in the interval [𝑎, 𝑏] and 𝑓 ∈ 𝐶 𝑛 +1 [𝑎, 𝑏]. Then,
for each 𝑥 in [𝑎, 𝑏], a number 𝜉 (generally unknown) between 𝑥0 , 𝑥1 , . . . , 𝑥𝑛 , and hence
𝑖𝑛 𝑎, 𝑏 , exists with
𝑛 +1
𝑓 𝜉
𝐸𝑛 (𝑥) = 𝑓 𝑥 − 𝑃𝑛 𝑥 = 𝑥 − 𝑥0 𝑥 − 𝑥1 … . . (𝑥 − 𝑥𝑛 )
𝑛 + 1 !
where 𝑃𝑛 (𝑥) is the interpolating polynomial.
Consequences: If 𝑓 (𝑛+1) is continuous on [𝑎, 𝑏] then:
𝑛+1 𝑛 𝑛
𝑓 𝜉 𝑀𝑛 +1
𝐸𝑛 (𝑥) = 𝑥 − 𝑥𝑖 ≤ 𝑥 − 𝑥𝑖
𝑛 + 1 ! 𝑛 + 1 !
𝑖=0 𝑖=0
Where
𝑛 +1
𝑀𝑛 +1 = max 𝑓 𝑥
𝑥∈[𝑎,𝑏]
Example:
Find the polynomial that fits the function y=1/x defined by the following table
Then, find the approximate value for f(3) and calculate the error incurred
x 2 2.5 4
y=f(x) 0.5 0.4 0.25
𝑥𝑖 𝑓(𝑥𝑖 ) 𝑓[𝑥𝑖 , 𝑥𝑖+1 ] 𝑓[𝑥0 , 𝑥1 , 𝑥2 ]
2 0.5
-0.2
2.5 0.4 0.05
-0.1
4 0.25
𝑝 𝑥 = 0.5 − 0.2 𝑥 − 2 + 0.05 𝑥 − 2 (𝑥 − 2.5)
𝑝 𝑥 = 0.05𝑥 2 − 0.425𝑥 + 1.15
𝑓 3 ≈ 𝑝 3 = 0.325
Estimate the error
−1 ′′ 2 −6
𝑓′ 𝑥 = 2
,𝑓 𝑥 = 3 ,𝑓 3 𝑥 = 4
𝑥 𝑥 𝑥
6 6 3
max 𝑓 3 𝑥 = max 4 = 4 =
𝑥∈[2,4] 𝑥∈[2,4] 𝑥 2 8
3 2 3
𝑓 𝜉 0.5
𝐸𝑛 (3) = 3 − 𝑥𝑖 ≤ 8 3 − 2 3 − 2.5 3 − 4 = = 0.03125
3! 3! 16
𝑖=0