LECTURE 9
CE 25
Mathematical Methods
in Civil Engineering II Function
Approximation
and Interpolation
ENGR. MATTHEW TRAVIS ALCANTARA
Instructor
Institute of Civil Engineering
University of the Philippines Diliman
Direct Polynomial Approximation | Lagrange
Interpolation | Newton’s Divided Difference
Interpolation
Function Approximation and Interpolation
Interpolation
▪ Interpolation is one of the oldest
problems in Mathematics.
▪ It is also one of the most applied.
▪ Interpolation means finding
(approximate) values of a function
𝑓(𝑥) for an 𝑥 between different x-values,
𝑥𝑜, 𝑥1, … , 𝑥𝑛 at which the values of
𝑓(𝑥) are given.
CE 25: Mathematical Methods in CE II
2
Function Approximation and Interpolation
Function Approximation
Objective: Approximate a given function f from among other simpler
functions, typically (but not always) polynomials
Variation: Constructing a smooth function from a discrete set of data points.
𝑓0 = 𝑓 𝑥0 𝑓1 = 𝑓 𝑥1 ⋯ 𝑓𝑛 = 𝑓 𝑥𝑛
Find 𝒑𝒏(𝒙) such that
𝑝𝑛 𝑥0 = 𝑓0 𝑝𝑛 𝑥1 = 𝑓1 ⋯ 𝑝𝑛 𝑥𝑛 = 𝑓𝑛
CE 25: Mathematical Methods in CE II
3
Function Approximation and Interpolation
CASE 1
Given a set of nodes {𝑥𝑖, 0 ≤ 𝑖 ≤ 𝑛}, find the polynomial 𝒑𝒏(𝒙) of
degree less than or equal to 𝑛 such that
𝒑𝒏 𝒙𝒊 = 𝒚𝒊 , 𝟎≤𝒊≤𝒏
Interpolation Polynomial
CASE 2
Given a set of nodes {𝑥𝑖, 0 ≤ 𝑖 ≤ 𝑛} and a continuous function 𝑓(𝑥), find
the polynomial 𝒑𝒏(𝒙) of degree less than or equal to 𝑛 such that
𝒑𝒏 𝒙𝒊 = 𝒇 𝒙𝒊 , 𝟎≤𝒊≤𝒏
Polynomial Approximation
CE 25: Mathematical Methods in CE II
4
Function Approximation and Interpolation
Why use polynomials?
▪ Polynomials are easy to evaluate
▪ Polynomials are easy to differentiate
▪ Polynomials are easy to integrate
3𝑥 2 + 2𝑥 − 7 𝑤ℎ𝑒𝑛 𝑥 = −3 𝑔 𝑥 = 𝐴𝑥 3 + 𝐵𝑥 2 + 𝐶𝑥 + 𝐷 𝑎𝑥 2
න 𝑎 𝑑𝑥 = 𝑎𝑥 න 𝑎𝑥 𝑑𝑥 =
𝑔′ 𝑥 = 3𝐴𝑥 2 + 2𝐵𝑥 + 𝐶 2
3(−3)2 +2 −3 − 7 𝑔′′ 𝑥 = 6𝐴𝑥 + 2𝐵
= 27 − 6 − 7 𝑎𝑥 3 𝑎𝑥 4
𝑔′′′ 𝑥 = 6𝐴 2
න 𝑎 𝑥 𝑑𝑥 = 3
න 𝑎𝑥 𝑑𝑥 =
= 14 3 4
CE 25: Mathematical Methods in CE II
5
Function Approximation and Interpolation
Existence and Uniqueness
Let the nodes 𝑥𝑖 𝜖 𝐼, 0 ≤ 𝑖 ≤ 𝑛 be given. So long as each of the 𝑥𝑖 are distinct,
(i.e. 𝑥𝑖 = 𝑥𝑗 if and only if 𝑖 = 𝑗), then there exists a unique polynomial 𝑝𝑛, of
degree less than or equal to n, which satisfies either of
𝑝𝑛 𝑥𝑖 = 𝑦𝑖 , 0≤𝑖≤𝑛
for a given set of data values {𝑦𝑖 }; or
𝑝𝑛 𝑥𝑖 = 𝑓(𝑥𝑖 ), 0≤𝑖≤𝑛
for a given function 𝑓.
CE 25: Mathematical Methods in CE II
6
Lecture 9
Function
Approximation
and Interpolation
Interpolation
Methods
Direct Method | Lagrange
Interpolation | Newton’s Divided
Difference Method
CE 25
Mathematical Methods in Civil Engineering II
Function Approximation and Interpolation
Direct Method
Given 𝑛 + 1 data points (𝑥𝑜, 𝑦𝑜), (𝑥1, 𝑦1), … , (𝑥𝑛, 𝑦𝑛), pass a
polynomial of order 𝑛 through the data as
𝑦 = 𝑎𝑜 + 𝑎1 𝑥 + ⋯ + 𝑎𝑛 𝑥 𝑛
where 𝑎𝑜, 𝑎1, … , 𝑎𝑛 are real constants
CE 25: Mathematical Methods in CE II
8
Direct Method
Example 9.1
t (sec) v (m/s)
The upward velocity of a rocket is given 0 0
as a function of time. Find the velocity at 10 227.04
t = 16 seconds using the direct method
15 362.78
for quadratic interpolation. Use the
velocity corresponding to t = 10, 15, and 20 517.35
20 seconds. 22.5 602.97
30 901.67
CE 25: Mathematical Methods in CE II
9
Function Approximation and Interpolation
Lagrange Interpolation
Given (𝑥𝑜, 𝑓𝑜), (𝑥1, 𝑓1), … , (𝑥𝑛, 𝑓𝑛) with arbitrarily spaced 𝑥𝑖, each
𝑓𝑗 is multiplied by a polynomial that is equal to 1 at 𝒙𝒋 and 0 at
the other nodes, and summing these 𝑛 + 1 polynomials will
serve as the interpolation polynomial.
*This method is useful in Numerical
Differentiation and Integration.
CE 25: Mathematical Methods in CE II
12
Function Approximation and Interpolation
LINEAR Lagrange Interpolation
Interpolation by the straight line through (𝑥𝑜, 𝑓𝑜), (𝑥1, 𝑓1).
The Linear Lagrange polynomial 𝑝1 is a sum 𝑝1 = 𝐿0 𝑓0 + 𝐿1𝑓1 with 𝐿0 the
linear polynomial that is 1 at 𝑥0 and 0 at 𝑥1; similarly, 𝐿1 is 0 at 𝑥0 and 1 at 𝑥1.
𝑥 − 𝑥1 𝑥 − 𝑥0
𝐿0 𝑥 = 𝐿1 𝑥 =
𝑥0 − 𝑥1 𝑥1 − 𝑥0
This gives the Linear Lagrange polynomial
𝑝1 𝑥 = 𝐿𝑜 (𝑥)𝑓𝑜 + 𝐿1 (𝑥)𝑓1
𝑥 − 𝑥1 𝑥 − 𝑥𝑜
𝑝1 𝑥 = 𝑓𝑜 + 𝑓1
𝑥𝑜 − 𝑥1 𝑥1 − 𝑥𝑜
CE 25: Mathematical Methods in CE II
13
Function Approximation and Interpolation
LINEAR Lagrange Interpolation
𝑥 − 𝑥1 𝑥 − 𝑥𝑜
𝑝1 𝑥 = 𝑓𝑜 + 𝑓1
𝑥𝑜 − 𝑥1 𝑥1 − 𝑥𝑜
CE 25: Mathematical Methods in CE II
14
Lagrange Method
Example 9.2
Compute ln 9.2 from ln 9.0 = 2.1972, ln 9.5 = 2.2513 by linear
Lagrange interpolation and determine the relative error using
ln 9.2 = 2.2192
Given nodes: Linear Lagrange polynomial:
(𝑥𝑜 , 𝑓𝑜 ) = 9.0, 2.1972 (𝑥1 , 𝑓1 ) = 9.5, 2.2513 𝑥 − 𝑥1 𝑥 − 𝑥𝑜
𝑝1 𝑥 = 𝑓 + 𝑓
𝑥𝑜 − 𝑥1 𝑜 𝑥1 − 𝑥𝑜 1
𝑥 − 9.5 𝑥−9
𝑝1 𝑥 = × 2.1972 + × 2.2513
9 − 9.5 9.5 − 9
9.2 − 9.5 9.2 − 9
𝑝1 9.2 = × 2.1972 + × 2.2513 = 𝟐. 𝟐𝟏𝟖𝟖𝟒
9 − 9.5 9.5 − 9
𝑥𝑒 − 𝑥𝑎 |2.21884 − 2.2192|
𝜖𝑟 = = × 100% = 𝟎. 𝟎𝟏𝟔%
𝑥𝑒 2.2192
CE 25: Mathematical Methods in CE II
15
Function Approximation and Interpolation
QUADRATIC Lagrange Interpolation
Interpolation of given (𝑥𝑜, 𝑓𝑜), (𝑥1, 𝑓1), (𝑥2, 𝑓2) by a second degree polynomial.
𝒑𝟐 𝒙 = 𝑳𝒐 𝒙 𝒇𝒐 + 𝑳𝟏 𝒙 𝒇𝟏 + 𝑳𝟐 𝒙 𝒇𝟐
with 𝐿𝑜(𝑥𝑜) = 1, 𝐿1(𝑥1) = 1, 𝐿2(𝑥2) = 1, and
𝐿𝑜(𝑥1) = 𝐿𝑜(𝑥2) = 𝐿1(𝑥𝑜) = 0, etc.
(𝒙 − 𝒙𝟏 )(𝒙 − 𝒙𝟐 )
𝑳𝒐 𝒙 =
(𝒙𝒐 − 𝒙𝟏 )(𝒙𝒐 − 𝒙𝟐 )
(𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟐 )
𝑳𝟏 𝒙 =
(𝒙𝟏 − 𝒙𝒐 )(𝒙𝟏 − 𝒙𝟐 )
(𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 )
𝑳𝟐 𝒙 =
(𝒙𝟐 − 𝒙𝒐 )(𝒙𝟐 − 𝒙𝟏 )
CE 25: Mathematical Methods in CE II
16
Lagrange Method
Example 9.3
Compute ln 9.2 from ln 9.0 = 2.1972 , ln 9.5 = 2.2513 , ln 11.0 = 2.3979 by quadratic
Lagrange interpolation and determine the relative error using ln 9.2 = 2.2192
Given nodes:
(𝑥𝑜 , 𝑓𝑜 ) = 9.0, 2.1972 (𝑥1 , 𝑓1 ) = 9.5, 2.2513 (𝑥2 , 𝑓2 ) = 11.0, 2.3979
𝑥 − 9.5 𝑥 − 11
𝑝2 𝑥 = × × 2.1972
9 − 9.5 9 − 11 𝑝2 9.2 = 𝟐. 𝟐𝟏𝟗𝟏𝟓𝟒
𝑥−9 𝑥 − 11
+ × × 2.2513 |2.219154 − 2.2192|
9.5 − 9 9.5 − 11 𝜖𝑟 = × 100%
2.2192
𝑥−9 𝑥 − 9.5 𝜖𝑟 = 𝟎. 𝟎𝟎𝟐𝟏%
+ × × 2.3979
11 − 9 11 − 9.5
CE 25: Mathematical Methods in CE II
18
Function Approximation and Interpolation
GENERAL Lagrange Interpolation
For general 𝑛 we obtain,
𝑛 𝑛
𝑙𝑘 𝑥
𝑓 𝑥 ≈ 𝑝𝑛 𝑥 = 𝐿𝑘 𝑥 𝑓𝑘 = 𝑓𝑘
𝑙𝑘 (𝑥𝑘 )
𝑘=0 𝑘=0
where 𝐿𝑘(𝑥𝑘) = 1 and 𝐿𝑘 is 0 at the other nodes, and 𝐿𝑘’s are independent
of the function 𝑓 to be interpolated.
Note:
𝑙𝑜 𝑥 = (𝑥 − 𝑥1 )(𝑥 − 𝑥2 ) ⋯ (𝑥 − 𝑥𝑛 )
𝑙𝑘 𝑥 = (𝑥 − 𝑥𝑜 ) ⋯ (𝑥 − 𝑥𝑘−1 )(𝑥 − 𝑥𝑘+1 ) ⋯ (𝑥 − 𝑥𝑛 )
𝑙𝑛 𝑥 = (𝑥 − 𝑥𝑜 )(𝑥 − 𝑥1 )(𝑥 − 𝑥2 ) ⋯ (𝑥 − 𝑥𝑛−1 )
CE 25: Mathematical Methods in CE II
19
Function Approximation and Interpolation
Newton’s Divided Difference Interpolation
This method of interpolation constructs the interpolation polynomial using
a recursive pattern.
CE 25: Mathematical Methods in CE II
20
Function Approximation and Interpolation
Newton’s Divided Difference Interpolation
How do we get 𝒂𝒌 ?
For first degree polynomial, 𝑝1 𝑥 = 𝑎0 + 𝑎1 (𝑥 − 𝑥0 )
𝑓 𝑥1 − 𝑓 𝑥0
𝑎0 = 𝑓(𝑥0 ) 𝑎1 =
𝑥1 − 𝑥0
𝑓[𝑥0 ] 𝑓[𝑥0 , 𝑥1 ]
For second degree polynomial, 𝑝2 𝑥 = 𝑝1 𝑥 + 𝑎2 𝑥 − 𝑥0 𝑥 − 𝑥1
Divided Difference! 𝑓 𝑥2 −𝑓 𝑥1
−
𝑓 𝑥1 −𝑓 𝑥0
𝑥2 −𝑥1 𝑥1 −𝑥0
𝑎2 =
𝑥2 −𝑥0
𝑓[𝑥0 , 𝑥1 , 𝑥2 ]
CE 25: Mathematical Methods in CE II
21
Function Approximation and Interpolation
Newton’s Divided Difference Interpolation
Divided Difference
The divided difference for a function f(x) are defined as follows
f xk = f (xk )
f xk − f xk −1
f xk −1 , xk =
xk − xk −1
f xk −1 , xk − f xk − 2 , xk −1
f xk − 2 , xk −1 , xk =
xk − xk − 2
f xk − 2 , xk −1 , xk − f xk −3 , xk − 2 , xk −1
f xk −3 , xk − 2 , xk −1 , xk =
xk − xk −3
CE 25: Mathematical Methods in CE II
22
Function Approximation and Interpolation
Newton’s Divided Difference Interpolation
Divided Difference Table
𝒙𝒌 𝒇 𝒙𝒌 𝒇 , 𝒇 ,, 𝒇 ,,, 𝒇 ,,,,
𝒙𝟎 𝒇 𝒙𝟎
𝒇 𝒙𝟎 , 𝒙𝟏
𝒙𝟏 𝒇 𝒙𝟏 𝒇 𝒙𝟎 , 𝒙𝟏 , 𝒙𝟐
𝒇 𝒙𝟏 , 𝒙𝟐 𝒇 𝒙𝟎 , 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑
𝒙𝟐 𝒇 𝒙𝟐 𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 𝒇 𝒙𝟎 , 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 , 𝒙𝟒
𝒇 𝒙𝟐 , 𝒙𝟑 𝒇 𝒙𝟏 , 𝒙𝟐 , 𝒙𝟑 , 𝒙𝟒
𝒙𝟑 𝒇 𝒙𝟑 𝒇 𝒙𝟐 , 𝒙𝟑 , 𝒙𝟒
𝒇 𝒙𝟑 , 𝒙𝟒
𝒙𝟒 𝒇 𝒙𝟒
CE 25: Mathematical Methods in CE II
23
Function Approximation and Interpolation
Newton’s Divided Difference Interpolation
Newton Divided Difference Interpolation Formula
𝑓 𝑥 ≈ 𝑝𝑛 𝑥 = 𝑎0 + 𝑎1 𝑥 − 𝑥0 + ⋯ + 𝑎𝑛 𝑥 − 𝑥0 𝑥 − 𝑥1 … (𝑥 − 𝑥𝑛−1 )
where
𝑓 𝑥1 , … , 𝑥𝑘 − 𝑓 𝑥0 , … , 𝑥𝑘−1
𝑎𝑘 = 𝑓 𝑥0 , … , 𝑥𝑘 =
𝑥𝑘 − 𝑥0
*This method is useful in
numerical solutions of ODEs
CE 25: Mathematical Methods in CE II
30
Function Approximation and Interpolation
Newton’s Divided Difference Interpolation
CE 25: Mathematical Methods in CE II
31
Newton’s Divided Difference Method
Example 9.4
Compute ln 9.2 from the table using Newton’s divided difference
method. Determine the relative error using ln 9.2 = 2.2192.
𝑥 𝒍𝒏 𝒙
8 2.07944
9 2.197225
9.5 2.251292
11 2.397895
CE 25: Mathematical Methods in CE II
32
Newton’s Divided Difference Method
Example 9.4
Compute ln 9.2 from the table using Newton’s divided difference method.
𝑓 𝑥 ≈ 𝑝3 𝑥 = 2.07944 + 0.117783 𝑥 − 8 − 0.00643 𝑥 − 8 𝑥 − 9
+0.000411 𝑥 − 8 (𝑥 − 9)(𝑥 − 9.5)
𝑓 9.2 ≈ 𝑝3 9.2 = 𝟐. 𝟐𝟏𝟗𝟐𝟎𝟖
|2.219208 − 2.2192|
𝜖𝑟 = × 100 = 𝟎. 𝟎𝟎𝟎𝟑𝟔%
2.2192
CE 25: Mathematical Methods in CE II
34
Lecture 9
Function
Approximation
and Interpolation
END
Any questions?
CE 25
Mathematical Methods in Civil Engineering II
SEE YOU NEXT MEETING!
mmalcantara@up.edu.ph
ICE 319
TTH 1130 - 1700
1. Kreyszig, E., Advanced Engineering Mathematics 10th ed.
References
