College of Engineering, Department of Mechanical Engineering

Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

Interpolation

Goal: To estimate intermediate values from given data points. The

most common method used for this purpose is:
polynomial interpolation.
 For n+1 data points: There is one and only one polynomial of
order n that passes through all the points:
Only one 1st order polynomial passes thru a set of 2 data point.
Only one 2nd order polynomial passes thru a set of 3 data points.
……
……

Examples of interpolating polynomials: (a) first-order (linear) connecting two

points (b) second order connecting three points, (c) third-order connecting four
points.
 College of Engineering, Department of Mechanical Engineering
Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

Linear Interpolation
Recall: The general formula for an nth-order polynomial is:
𝒇(𝒙) = 𝒂𝒐 + 𝒂𝟏 𝒙 + 𝒂𝟐 𝒙𝟐 + ⋯ + 𝒂𝒏 𝒙𝒏 (𝟏)
Linear interpolation  polynomial od degree 1:
𝒇(𝒙) = 𝒂𝒐 + 𝒂𝟏 𝒙 (𝟐)

To simplify finding 𝒂𝒐 , 𝒂𝟏 , re-write (2) as:

𝒇(𝒙) = 𝒃𝒐 + 𝒃𝟏 (𝒙 − 𝒙𝒐 ) (𝟑)
→ 𝒇(𝒙𝒐 ) = 𝒃𝒐 (𝟒)
𝒇(𝒙𝟏 ) = 𝒇(𝒙𝒐 ) + 𝒃𝟏 (𝒙𝟏 − 𝒙𝒐 )
𝒇(𝒙𝟏 ) − 𝒇(𝒙𝒐 )
→ 𝒃𝟏 = (𝟓)
(𝒙𝟏 − 𝒙𝒐 )
Substitute (4) & (5) in (3):
𝑳𝒊𝒏𝒆𝒂𝒓 𝒊𝒏𝒕𝒆𝒓𝒑𝒐𝒍𝒂𝒕𝒊𝒐𝒏 𝒇𝒐𝒓𝒎𝒖𝒍𝒂:

𝒇(𝒙𝟏 ) − 𝒇(𝒙𝒐 )
𝒇(𝒙) = 𝒇(𝒙𝒐 ) + (𝒙 − 𝒙𝒐 ) (6)
𝒙𝟏 − 𝒙𝒐
 College of Engineering, Department of Mechanical Engineering
Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

Quadratic Interpolation
𝒇(𝒙) = 𝒃𝒐 + 𝒃𝟏 (𝒙 − 𝒙𝒐 ) + 𝒃𝟐 (𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 )
→ 𝒇(𝒙𝒐 ) = 𝒃𝒐
𝒇(𝒙𝟏 ) = 𝒇(𝒙𝒐 ) + 𝒃𝟏 (𝒙𝟏 − 𝒙𝒐 )
𝒇(𝒙𝟏 ) − 𝒇(𝒙𝒐 )
→ 𝒃𝟏 =
𝒙𝟏 − 𝒙𝒐
𝒇(𝒙𝟏 ) − 𝒇(𝒙𝒐 )
𝒇(𝒙𝟐 ) = 𝒇(𝒙𝒐 ) + (𝒙𝟐 − 𝒙𝒐 ) + 𝒃𝟐 (𝒙𝟐 − 𝒙𝒐 )(𝒙𝟐 − 𝒙𝟏 )
𝒙𝟏 − 𝒙𝒐
Solve for 𝒃𝟐 :
𝒇(𝒙𝟐 ) − 𝒇(𝒙𝟏 ) 𝒇(𝒙𝟏 ) − 𝒇(𝒙𝒐 )
−
𝒙 𝟐 − 𝒙𝟏 𝒙 𝟏 − 𝒙𝒐
𝒃𝟐 =
𝒙𝟐 − 𝒙𝒐

 Quadratic interpolating polynomial:

𝒇(𝒙𝟐 ) − 𝒇(𝒙𝟏 ) 𝒇(𝒙𝟏 ) − 𝒇(𝒙𝒐 )

𝒇(𝒙𝟏 ) − 𝒇(𝒙𝒐 ) −
𝒙𝟐 − 𝒙𝟏 𝒙𝟏 − 𝒙𝒐
𝒇(𝒙) = 𝒇(𝒙𝒐 ) + (𝒙 − 𝒙𝒐 ) + (𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 )
𝒙 𝟏 − 𝒙𝒐 𝒙𝟐 − 𝒙𝒐

General form of Newton’s interpolating polynomials:

From Previous examples:
𝒃𝒐 = 𝒇(𝒙𝒐 ): 𝟎𝒕𝒉 𝒅𝒊𝒗𝒊𝒅𝒆𝒅 𝒅𝒊𝒇𝒇𝒆𝒓𝒆𝒏𝒄𝒆
𝒇(𝒙𝟏 ) − 𝒇(𝒙𝒐 )
𝒃𝟏 = = 𝒇[ 𝒙 𝟏 , 𝒙 𝒐 ] : 𝟏𝒔𝒕 𝒅𝒊𝒗𝒊𝒅𝒆𝒅 𝒅𝒊𝒇𝒇𝒆𝒓𝒆𝒏𝒄𝒆
𝒙𝟏 − 𝒙 𝒐
𝒇(𝒙𝟐 ) − 𝒇(𝒙𝟏 ) 𝒇(𝒙𝟏 ) − 𝒇(𝒙𝒐 )
−
𝒙𝟐 − 𝒙𝟏 𝒙𝟏 − 𝒙𝒐
𝒃𝟐 = = 𝒇[𝒙𝟐 , 𝒙𝟏 , 𝒙𝒐 ]: 𝟐𝒏𝒅 𝒅𝒊𝒗𝒊𝒅𝒆𝒅 𝒅𝒊𝒇𝒇𝒆𝒓𝒆𝒏𝒄𝒆
𝒙𝟐 − 𝒙𝒐
OR:
𝒇 [ 𝒙 𝟐 , 𝒙 𝟏 ] − 𝒇[ 𝒙 𝟏 , 𝒙 𝒐 ]
𝒃𝟐 = = 𝒇[ 𝒙 𝟐 , 𝒙 𝟏 , 𝒙 𝒐 ] : 𝟐𝒏𝒅 𝒅𝒊𝒗𝒊𝒅𝒆𝒅 𝒅𝒊𝒇𝒇𝒆𝒓𝒆𝒏𝒄𝒆
𝒙𝟐 − 𝒙𝒐
 College of Engineering, Department of Mechanical Engineering
Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

In general:
𝒇(𝒙𝒊 ) − 𝒇(𝒙𝒋 )
𝟏𝒔𝒕 𝒅𝒊𝒗𝒊𝒅𝒆𝒅 𝒅𝒊𝒇𝒇𝒆𝒓𝒆𝒏𝒄𝒆: 𝒇[𝒙𝒊 , 𝒙𝒋 ] =
𝒙𝒊 − 𝒙𝒋

𝟐𝒏𝒅 𝒅𝒊𝒗𝒊𝒅𝒆𝒅 𝒅𝒊𝒇𝒇𝒆𝒓𝒆𝒏𝒄𝒆:

𝒇(𝒙𝒊 ) − 𝒇(𝒙𝒋 ) 𝒇(𝒙𝒋 ) − 𝒇(𝒙𝒌 )
−
𝒇[𝒙𝒊 , 𝒙𝒋 ] − 𝒇[𝒙𝒋 , 𝒙𝒌 ] 𝒙𝒊 − 𝒙𝒋 𝒙𝒋 − 𝒙𝒌
𝒇[𝒙𝒊 , 𝒙𝒋 , 𝒙𝒌 ] = =
𝒙𝒊 − 𝒙𝒌 𝒙𝒊 − 𝒙𝒌

𝒏𝒕𝒉 𝒅𝒊𝒗𝒊𝒅𝒆𝒅 𝒅𝒊𝒇𝒇𝒆𝒓𝒆𝒏𝒄𝒆:

𝒇[𝒙𝒏 , 𝒙𝒏−𝟏 , … 𝒙𝟏 ] − 𝒇[ 𝒙𝒏−𝟏 , … 𝒙𝟏 , 𝒙𝒐 ]
𝒇[𝒙𝒏 , 𝒙𝒏−𝟏 , … 𝒙𝟏 , 𝒙𝒐 ] =
𝒙𝒏 − 𝒙𝒐

Interpolating formulas in terms of Newton’s divided differences:

Linear Interpolation formula:

𝒇𝟏 (𝒙) = 𝒇(𝒙𝒐 ) + 𝒇[𝒙𝟏 , 𝒙𝒐 ](𝒙 − 𝒙𝒐 )

Quadratic Interpolation formula:

𝒇𝟐 (𝒙) = 𝒇(𝒙𝒐 ) + 𝒇[𝒙𝟏 , 𝒙𝒐 ](𝒙 − 𝒙𝒐 ) + 𝒇[𝒙𝟐 , 𝒙𝟏 , 𝒙𝒐 ](𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 )

Cubic (3rd order) Interpolation formula:

𝒇𝟑 (𝒙) = 𝒇(𝒙𝒐 ) + 𝒇[𝒙𝟏 , 𝒙𝒐 ](𝒙 − 𝒙𝒐 ) + 𝒇[𝒙𝟐 , 𝒙𝟏 , 𝒙𝒐 ](𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 )

+ 𝒇[𝒙𝟑 , 𝒙𝟐 , 𝒙𝟏 , 𝒙𝒐 ](𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 )(𝒙 − 𝒙𝟐 )
 College of Engineering, Department of Mechanical Engineering
Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

nth order Interpolation formula:

𝒇𝒏 (𝒙) = 𝒇(𝒙𝒐 ) + 𝒇[𝒙𝟏 , 𝒙𝒐 ](𝒙 − 𝒙𝒐 ) + 𝒇[𝒙𝟐 , 𝒙𝟏 , 𝒙𝒐 ](𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 )
+ 𝒇[𝒙𝟑 , 𝒙𝟐 , 𝒙𝟏 , 𝒙𝒐 ](𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 )(𝒙 − 𝒙𝟐 ) + ⋯
+ 𝒇[𝒙𝒏 , 𝒙𝒏−𝟏 ,…. , 𝒙𝒐 ](𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 ) … (𝒙 − 𝒙𝒏−𝟏 )

Notes on Newton’s Interpolating Polynomials:

1. Data points need not be equally spaced.
2. Data points need not be in ascending/descending order
3. Newton’s divided difference polynomials are recursive;
higher-order differences are composed of lower-order
differences  easy to program.

Example 1:
Estimate the natural logarithm of 2 using linear interpolation.
First, perform the computation by interpolating between ln 1 = 0 and ln 6 =
1.791759.
Then, repeat the procedure, but use a smaller interval from ln 1= 0 to ln 4 =
1.386294. Note that the true value of ln 2 is 0.69314718
Solution:
Linear interpolation:
Case 1: 𝒙𝒐 = 𝟏, 𝒙𝟏 = 𝟔
𝒇𝟏 (𝒙) = 𝒇(𝒙𝒐 ) + 𝒇[𝒙𝟏 , 𝒙𝒐 ](𝒙 − 𝒙𝒐 )
𝒇(𝒙𝒐 ) = 𝒍𝒏 𝒙𝒐 = 𝒍𝒏 𝟏 = 𝟎
𝒇(𝒙𝟏 ) − 𝒇(𝒙𝒐 ) 𝒇(𝟔) − 𝒇(𝟏) 𝒍𝒏 𝟔 − 𝒍𝒏 𝟏
𝒇[𝒙𝟏 , 𝒙𝒐 ] = = = = 𝟎. 𝟑𝟓𝟖𝟑𝟓𝟏𝟗
𝒙𝟏 − 𝒙𝒐 𝟔−𝟏 𝟓
→ 𝒇𝟏 (𝒙) = 𝒇(𝟎) + 𝟎. 𝟑𝟓𝟖𝟑𝟓𝟏𝟗(𝒙 − 𝟏)
→ 𝒇𝟏 (𝟐) = 𝟎 + 𝟎. 𝟑𝟓𝟖𝟑𝟓(𝟐 − 𝟏) = 𝟎. 𝟑𝟓𝟖𝟑𝟓𝟏𝟗
(𝟎. 𝟔𝟗𝟑𝟏𝟒𝟕𝟏𝟖 − 𝟎. 𝟑𝟓𝟖𝟑𝟓𝟏𝟗)
→ ∈𝒕 = × 𝟏𝟎𝟎% = 𝟒𝟖. 𝟑%
𝟎. 𝟔𝟗𝟑𝟏𝟒𝟕𝟏𝟖
 College of Engineering, Department of Mechanical Engineering
Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

Case 2: 𝒙𝒐 = 𝟏, 𝒙𝟏 = 𝟒
𝒇𝟏 (𝒙) = 𝒇(𝒙𝒐 ) + 𝒇[𝒙𝟏 , 𝒙𝒐 ](𝒙 − 𝒙𝒐 )
𝒇(𝒙𝒐 ) = 𝒍𝒏 𝒙𝒐 = 𝒍𝒏 𝟏 = 𝟎
𝒇(𝒙𝟏 ) − 𝒇(𝒙𝒐 ) 𝒇(𝟒) − 𝒇(𝟏) 𝒍𝒏 𝟒 − 𝒍𝒏 𝟏
𝒇[𝒙𝟏 , 𝒙𝒐 ] = = = = 𝟎. 𝟒𝟔𝟐𝟎𝟗𝟖𝟏
𝒙𝟏 − 𝒙𝒐 𝟒−𝟏 𝟑
→ 𝒇𝟏 (𝒙) = 𝒇(𝟎) + 𝟎. 𝟒𝟔𝟐𝟎𝟗𝟖𝟏(𝒙 − 𝟏)
→ 𝒇𝟏 (𝟐) = 𝟎 + 𝟎. 𝟒𝟔𝟐𝟎𝟗𝟖𝟏(𝟐 − 𝟏) = 𝟎. 𝟒𝟔𝟐𝟎𝟗𝟖𝟏
(𝟎. 𝟔𝟗𝟑𝟏𝟒𝟕𝟏𝟖 − 𝟎. 𝟒𝟔𝟐𝟎𝟗𝟖𝟏)
→ ∈𝒕 = × 𝟏𝟎𝟎% = 𝟑𝟑. 𝟑%
𝟎. 𝟔𝟗𝟑𝟏𝟒𝟕𝟏𝟖

Example 1: Two linear interpolations to estimate ln 2. The smaller interval provides

a better estimate.

Example 2:
Fit a second-order polynomial to the three points used in Example 1:
𝒙𝒐 = 𝟏, 𝒇(𝒙𝒐 ) = 𝒍𝒏 𝟏 = 𝟎
𝒙𝟏 = 𝟒, 𝒇(𝒙𝟏 ) = 𝒍𝒏 𝟒 = 𝟏. 𝟑𝟖𝟔𝟐𝟗𝟒
𝒙𝟐 = 𝟔, 𝒇(𝒙𝟐 ) = 𝒍𝒏 𝟔 = 𝟏. 𝟕𝟗𝟏𝟕𝟓𝟗
Use the polynomial to estimate ln 2.
Solution:
𝒇𝟐 (𝒙) = 𝒇(𝒙𝒐 ) + 𝒇[𝒙𝟏 , 𝒙𝒐 ](𝒙 − 𝒙𝒐 ) + 𝒇[𝒙𝟐 , 𝒙𝟏 , 𝒙𝒐 ](𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 )
 College of Engineering, Department of Mechanical Engineering
Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

𝒇(𝒙𝒐 ) = 𝟎

𝒇(𝒙𝟏 ) − 𝒇(𝒙𝒐 ) 𝒇(𝟒) − 𝒇(𝟏) 𝒍𝒏 𝟒 − 𝒍𝒏 𝟏

𝒇[ 𝒙 𝟏 , 𝒙 𝒐 ] = = = = 𝟎. 𝟒𝟔𝟐𝟎𝟗𝟖𝟏
𝒙𝟏 − 𝒙𝒐 𝟒−𝟏 𝟑

𝒇 [ 𝒙 𝟐 , 𝒙 𝟏 ] − 𝒇[ 𝒙 𝟏 , 𝒙 𝒐 ]
𝒇[ 𝒙 𝟐 , 𝒙 𝟏 , 𝒙 𝒐 ] =
𝒙𝟐 − 𝒙𝒐

𝒇(𝒙𝟐 ) − 𝒇(𝒙𝟏 ) 𝒇(𝟔) − 𝒇(𝟒) 𝒍𝒏 𝟔 − 𝒍𝒏 𝟒

𝒇[ 𝒙 𝟐 , 𝒙 𝟏 ] = = = = 𝟎. 𝟐𝟎𝟐𝟕𝟑𝟐𝟓𝟓
𝒙𝟐 − 𝒙𝟏 𝟔−𝟒 𝟐

𝒇[𝒙𝟐 , 𝒙𝟏 ] − 𝒇[𝒙𝟏 , 𝒙𝒐 ] 𝟎. 𝟐𝟎𝟐𝟕𝟑𝟐𝟓𝟓 − 𝟎. 𝟒𝟔𝟐𝟎𝟗𝟖𝟏

→ 𝒇[ 𝒙 𝟐 , 𝒙 𝟏 , 𝒙 𝒐 ] = =
𝒙𝟐 − 𝒙𝒐 𝟔−𝟏
= −𝟎. 𝟎𝟓𝟏𝟖𝟕𝟑𝟏
→ 𝒇𝟐 (𝒙) = 𝒇(𝒙𝒐 ) + 𝒇[𝒙𝟏 , 𝒙𝒐 ](𝒙 − 𝒙𝒐 ) + 𝒇[𝒙𝟐 , 𝒙𝟏 , 𝒙𝒐 ](𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 )
→ 𝒇𝟐 (𝒙) = 𝟎 + 𝟎. 𝟒𝟔𝟐𝟎𝟗𝟖𝟏(𝒙 − 𝟏) − 𝟎. 𝟎𝟓𝟏𝟖𝟕𝟑𝟏(𝒙 − 𝟏)(𝒙 − 𝟒)
→ 𝒇𝟐 (𝟐) = 𝟎. 𝟓𝟔𝟓𝟖𝟒
(𝟎. 𝟔𝟗𝟑𝟏𝟒𝟕𝟏𝟖 − 𝟎. 𝟓𝟔𝟓𝟖𝟒)
→ ∈𝒕 = × 𝟏𝟎𝟎% = 𝟏𝟖. 𝟑𝟔%
𝟎. 𝟓𝟔𝟓𝟖𝟒

The use of quadratic interpolation to estimate ln 2. The linear interpolation from x 5 1

to 4 is also included for comparison.
 College of Engineering, Department of Mechanical Engineering
Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

Example 3:
In Example 2, data points at 𝒙𝒐 = 𝟏, 𝒙𝟏 = 𝟒, 𝒙𝟐 = 𝟔 were used to estimate ln 2
with a parabola. Now, adding a fourth point [𝒙𝟑 = 𝟓; 𝒇(𝒙𝟑 ) = 𝟏. 𝟔𝟎𝟗𝟒𝟑𝟖],
estimate ln 2 with a third-order Newton’s interpolating polynomial.
Solution:
The third-order polynomial is:

∈𝒕 = 𝟗. 𝟑%
 College of Engineering, Department of Mechanical Engineering
Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

The use of cubic interpolation to estimate ln 2.

 College of Engineering, Department of Mechanical Engineering
Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

Lagrange Interpolating Polynomials

A reformulation of Newton’s interpolating polynomials to avoid the
computation of divided differences.
1st order Lagrange interpolating polynomial:
Starting from the 1st order Newton’s interpolating polynomial:
𝒇𝟏 (𝒙) = 𝒇(𝒙𝒐 ) + (𝒙 − 𝒙𝒐 )𝒇[𝒙𝟏 , 𝒙𝒐 ]
𝒇(𝒙𝟏 ) − 𝒇(𝒙𝒐 )
→ 𝒇𝟏 (𝒙) = 𝒇(𝒙𝒐 ) + (𝒙 − 𝒙𝒐 )
𝒙𝟏 − 𝒙𝒐
𝒙 − 𝒙𝒐 𝒙 − 𝒙𝒐
→ 𝒇𝟏 (𝒙) = 𝒇(𝒙𝒐 ) + 𝒇(𝒙𝟏 ) + 𝒇(𝒙𝒐 )
𝒙𝟏 − 𝒙𝒐 𝒙𝒐 − 𝒙𝟏
𝒙 − 𝒙𝒐 𝒙 − 𝒙𝒐
→ 𝒇𝟏 (𝒙) = (𝟏 + ) 𝒇(𝒙𝒐 ) + 𝒇(𝒙𝟏 )
𝒙𝒐 − 𝒙𝟏 𝒙𝟏 − 𝒙𝒐

𝒙 − 𝒙𝟏 𝒙 − 𝒙𝒐 1st order Lagrange

𝒇𝟏 (𝒙) = 𝒇(𝒙𝒐 ) + 𝒇(𝒙𝟏 )
𝒙𝒐 − 𝒙𝟏 𝒙𝟏 − 𝒙𝒐 interpolating polynomial

Check:
𝒂𝒕 𝒙 = 𝒙𝒐 , → 𝒇𝟏 (𝒙) = 𝒇(𝒙𝒐 )
𝒂𝒕 𝒙 = 𝒙𝟏 , → 𝒇𝟏 (𝒙) = 𝒇(𝒙𝟏 )
Note:
𝒂𝒕 𝒙 = 𝒙𝒐 , → 𝒔𝒆𝒄𝒐𝒏𝒅 𝒕𝒆𝒓𝒎 𝒊𝒔 𝒛𝒆𝒓𝒐
𝒂𝒕 𝒙 = 𝒙𝟏 , → 𝑭𝒊𝒓𝒔𝒕 𝒕𝒆𝒓𝒎 𝒊𝒔 𝒛𝒆𝒓𝒐

2nd order Lagrange interpolating polynomial:

𝒇𝟐 (𝒙) = 𝒇(𝒙𝒐 ) + 𝒇[𝒙𝟏 , 𝒙𝒐 ](𝒙 − 𝒙𝒐 ) + 𝒇[𝒙𝟐 , 𝒙𝟏 , 𝒙𝒐 ](𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 ) (𝟏)
𝒙 − 𝒙𝟏 𝒙 − 𝒙𝒐
𝒇𝟐 (𝒙) = 𝒇(𝒙𝒐 ) + 𝒇(𝒙𝟏 ) + (𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 )𝒇[𝒙𝟐 , 𝒙𝟏 , 𝒙𝒐 ] (𝟐)
𝒙𝒐 − 𝒙𝟏 𝒙𝟏 − 𝒙𝒐

Last term in (2):

𝒇[ 𝒙 𝟐 , 𝒙 𝟏 ] − 𝒇[ 𝒙 𝟏 , 𝒙 𝒐 ]
(𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 )𝒇[𝒙𝟐 , 𝒙𝟏 , 𝒙𝒐 ] = (𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 )
𝒙𝟐 − 𝒙𝒐
 College of Engineering, Department of Mechanical Engineering
Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

(𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 )
= (𝒇[𝒙𝟐 , 𝒙𝟏 ] − 𝒇[𝒙𝟏 , 𝒙𝒐 ])
𝒙𝟐 − 𝒙𝒐
(𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 ) 𝒇(𝒙𝟐 ) − 𝒇(𝒙𝟏 ) 𝒇(𝒙𝟏 ) − 𝒇(𝒙𝒐 )
= ( − )
𝒙𝟐 − 𝒙𝒐 𝒙𝟐 − 𝒙𝟏 𝒙𝟏 − 𝒙𝒐

(𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 ) (𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 )
= (𝒇(𝒙𝟐 ) − 𝒇(𝒙𝟏 )) + (𝒇(𝒙𝟏 ) − 𝒇(𝒙𝒐 )) (𝟑)
(𝒙𝟐 − 𝒙𝒐 )(𝒙𝟐 − 𝒙𝟏 ) (𝒙𝟐 − 𝒙𝒐 )(𝒙𝟏 − 𝒙𝒐 )
Substitute (3) in (2) to get:
2nd order Lagrange interpolating polynomial:

(𝒙 − 𝒙𝟏 )(𝒙 − 𝒙𝟐 ) (𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟐 ) (𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 )

𝒇𝟐 (𝒙) = 𝒇(𝒙𝒐 ) + 𝒇(𝒙𝟏 ) + 𝒇(𝒙𝟐 )
(𝒙𝒐 − 𝒙𝟏 )(𝒙𝒐 − 𝒙𝟐 ) (𝒙𝟏 − 𝒙𝒐 )(𝒙𝟏 − 𝒙𝟐 ) (𝒙𝟐 − 𝒙𝒐 )(𝒙𝟐 − 𝒙𝟏 )

𝒂𝒕 𝒙 = 𝒙𝒐 , → 𝒐𝒏𝒍𝒚 𝒇𝒊𝒓𝒔𝒕 𝒕𝒆𝒓𝒎 𝒊𝒔 𝒏𝒐𝒏𝒛𝒆𝒓𝒐

𝒂𝒕 𝒙 = 𝒙𝟏 , → 𝒐𝒏𝒍𝒚 𝒔𝒆𝒄𝒐𝒏𝒅 𝒕𝒆𝒓𝒎 𝒊𝒔 𝒏𝒐𝒏𝒛𝒆𝒓𝒐
𝒂𝒕 𝒙 = 𝒙𝟐 , → 𝒐𝒏𝒍𝒚 𝒕𝒉𝒊𝒓𝒅 𝒕𝒆𝒓𝒎 𝒊𝒔 𝒏𝒐𝒏𝒛𝒆𝒓𝒐
In General:
The nth order Lagrange interpolating polynomial:
𝒏 𝒏
𝒙 − 𝒙𝒋
𝒇𝒏 (𝒙) = ∑ 𝑳𝒊 (𝒙)𝒇(𝒙𝒊 ) , 𝒘𝒉𝒆𝒓𝒆 𝑳𝒊 (𝒙) = ∏
𝒙𝒊 − 𝒙𝒋
𝒊=𝟎 𝒋=𝟎,𝒋≠𝒊

𝒏 𝒏
𝒙 − 𝒙𝒋
𝒇𝒏 (𝒙) = ∑ ( ∏ ) 𝒇(𝒙𝒊 )
𝒙𝒊 − 𝒙𝒋
𝒊=𝟎 𝒋=𝟎,𝒋≠𝒊

To check the above formula:

1. Derive the 1st order Lagrange interpolating polynomial from the general
formula above:

𝒏 = 𝟏, → 𝒊 = 𝟎, 𝟏
𝟏 𝟏
𝒙 − 𝒙𝒋 𝒙 − 𝒙𝒋
𝒇𝟏 (𝒙) = ∏ 𝒇(𝒙𝒐 ) + ∏ 𝒇(𝒙𝟏 )
𝒙𝒐 − 𝒙𝒋 𝒙𝟏 − 𝒙𝒋
𝒋=𝟎,𝒋≠𝒊 𝒋=𝟎,𝒋≠𝒊

𝒊=𝟎 𝒊=𝟏
 College of Engineering, Department of Mechanical Engineering
Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

𝟏 𝟏
𝒙 − 𝒙𝟏 𝒙 − 𝒙𝒐
𝒇𝟏 (𝒙) = ∏ 𝒇(𝒙𝒐 ) + ∏ 𝒇(𝒙𝟏 )
𝒙𝒐 − 𝒙𝟏 𝒙𝟏 − 𝒙𝒐
𝒋=𝟎,𝒋≠𝒊 𝒋=𝟎,𝒋≠𝒊

𝒙 − 𝒙𝟏 𝒙 − 𝒙𝒐
𝒇𝟏 (𝒙) = 𝒇(𝒙𝒐 ) + 𝒇(𝒙𝟏 )
𝒙𝒐 − 𝒙𝟏 𝒙𝟏 − 𝒙𝒐

2. Derive the 2nd order Lagrange interpolating polynomial from the general
formula above:
𝒏 = 𝟐, → 𝒊 = 𝟎, 𝟏, 𝟐
𝟐 𝟐
𝒙 − 𝒙𝒋
𝒇𝟐 (𝒙) = ∑ ( ∏ ) 𝒇(𝒙𝒊 )
𝒙𝒊 − 𝒙𝒋
𝒊=𝟎 𝒋=𝟎,𝒋≠𝒊

𝟐 𝟐 𝟐
𝒙 − 𝒙𝒋 𝒙 − 𝒙𝒋 𝒙 − 𝒙𝒋
𝒇𝟐 (𝒙) = ∏ 𝒇(𝒙𝒐 ) + ∏ 𝒇(𝒙𝟏 ) + ∏ 𝒇(𝒙𝟐 )
𝒙𝒐 − 𝒙𝒋 𝒙𝟏 − 𝒙𝒋 𝒙𝟐 − 𝒙𝒋
𝒋=𝟎,𝒋≠𝒊 𝒋=𝟎,𝒋≠𝒊 𝒋=𝟎,𝒋≠𝒊

𝒊 = 𝟎, 𝒋 = 𝟏, 𝟐 𝒊 = 𝟏, 𝒋 = 𝟎, 𝟐 𝒊 = 𝟐, 𝒋 = 𝟎, 𝟏

(𝒙 − 𝒙𝟏 )(𝒙 − 𝒙𝟐 ) (𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟐 ) (𝒙 − 𝒙𝒐 )(𝒙 − 𝒙𝟏 )

𝒇𝟐 (𝒙) = 𝒇(𝒙𝒐 ) + 𝒇(𝒙𝟏 ) + 𝒇(𝒙𝟐 )
(𝒙𝒐 − 𝒙𝟏 )(𝒙𝒐 − 𝒙𝟐 ) (𝒙𝟏 − 𝒙𝒐 )(𝒙𝟏 − 𝒙𝟐 ) (𝒙𝟐 − 𝒙𝒐 )(𝒙𝟐 − 𝒙𝟏 )
 College of Engineering, Department of Mechanical Engineering
Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

Spline Interpolation
 Rather than using higher – order polynomials to connect between (n+1)
discrete data points, we use lower – order polynomials to subsets of data
points.
 Such lower order polynomials are called: “Spline Functions”.
 Spline functions give better accuracy when there are abrupt changes in
data, such as shock waves, solid – liquid interface,…..

A visual representation of a situation where the splines are superior to higher-order interpolating
polynomials. The function to be fit undergoes an abrupt increase at x 5 0.
Parts (a) through(c) indicate that the abrupt change induces oscillations in interpolating
polynomials. In contrast, because it is limited to third-order curves with smooth transitions, a linear
spline (d) provides a much more acceptable approximation.
 College of Engineering, Department of Mechanical Engineering
Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

1. Linear Splines

1st order splines for a group of ordered data points:

𝒇𝟏 (𝒙) = 𝒇(𝒙𝟏 ) + 𝒎𝟏 (𝒙 − 𝒙𝟏 ), 𝒙𝟏 ≤ 𝒙 ≤ 𝒙𝟐
𝒇𝟐 (𝒙) = 𝒇(𝒙𝟐 ) + 𝒎𝟐 (𝒙 − 𝒙𝟐 ), 𝒙𝟐 ≤ 𝒙 ≤ 𝒙𝟑
….
….
𝒇𝒏−𝟏 (𝒙) = 𝒇(𝒙𝒏−𝟏 ) + 𝒎𝒏−𝟏 (𝒙 − 𝒙𝒏−𝟏 ), 𝒙𝒏−𝟏 ≤ 𝒙 ≤ 𝒙𝒏
Where,
𝒇(𝒙𝒊+𝟏 ) − 𝒇(𝒙𝒊 ) 𝒇(𝒙𝟐 ) − 𝒇(𝒙𝟏 )
𝒎𝒊 = , 𝒎𝟏 =
𝒙𝒊+𝟏 − 𝒙𝒊 𝒙𝟐 − 𝒙𝟏

1st order splines

 College of Engineering, Department of Mechanical Engineering
Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

Example:
Fit the data below in 1st order splines, then evaluate the function at x = 5.
x: 3 4.5 7.0 9.0
f(x): 2.5 1.0 2.5 0.5
Solution:
m: -1 0.6 -1.0 -
𝒇𝟏 (𝒙) = 𝟐. 𝟓 − (𝒙 − 𝟑), 𝟑 ≤ 𝒙 ≤ 𝟒. 𝟓
𝒇𝟐 (𝒙) = 𝟏. 𝟎 + 𝟎. 𝟔(𝒙 − 𝟒. 𝟓), 𝟒. 𝟓 ≤ 𝒙 ≤ 𝟕. 𝟎
𝒇𝟑 (𝒙) = 𝟐. 𝟓 − (𝒙 − 𝟕. 𝟎), 𝟕. 𝟎 ≤ 𝒙 ≤ 𝟗. 𝟎
→ 𝒇(𝟓) = 𝒇𝟐 (𝟓) = 𝟏. 𝟎 + 𝟎. 𝟔(𝟓 − 𝟒. 𝟓) = 𝟏. 𝟑
Notes:
 Linear splines are not smooth;
check at the “knots” (points where splines meet):
𝒇′𝟏 = −𝟏, 𝒇′𝟐 = 𝟎. 𝟔, 𝒇′𝟑 = −𝟏
→ 𝒍𝒊𝒏𝒆𝒂𝒓 𝒔𝒑𝒍𝒊𝒏𝒆𝒔: 𝟏𝒔𝒕 𝒅𝒆𝒓𝒊𝒗𝒂𝒕𝒊𝒗𝒆 𝒊𝒔 𝒅𝒊𝒔𝒄𝒐𝒏𝒕𝒊𝒏𝒖𝒐𝒖𝒔

2. Quadratic Splines
 1st derivative is smooth at the “knots”

Quadratic Splines
 College of Engineering, Department of Mechanical Engineering
Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

General form for quadratic splines:

𝒇𝒊 (𝒙) = 𝒂𝒊 𝒙𝟐 + 𝒃𝒊 𝒙 + 𝒄𝒊 , 𝒊 = 𝟏, … , 𝒏 − 𝟏

𝒏: 𝒏𝒖𝒎𝒃𝒆𝒓 𝒐𝒇 𝒅𝒂𝒕𝒂 𝒑𝒐𝒊𝒏𝒕𝒔

For n data points  (n-1) intervals (splines)

 Total number of unknowns = 3(n-1)

 Need 3(n-1) equations/conditions to evaluate the 3(n-1) unknowns:

Conditions:

1. Splines pass thru the data points:

𝒇𝒊 (𝒙𝒊 ) = 𝒂𝒊 𝒙𝟐𝒊 + 𝒃𝒊 𝒙𝒊 + 𝒄𝒊 , 𝒊 = 𝟏, 𝟐, … , 𝒏 − 𝟏

𝒇𝒊 (𝒙𝒊+𝟏 ) = 𝒂𝒊 𝒙𝟐𝒊+𝟏 + 𝒃𝒊 𝒙𝒊+𝟏 + 𝒄𝒊 , 𝒊 = 𝟏, 𝟐, … , 𝒏 − 𝟏

2. Splines must be continuous at the interior data points:

𝒇′𝒊 (𝒙𝒊+𝟏 ) = 𝒇′𝒊+𝟏 (𝒙𝒊+𝟏 ), 𝒊 = 𝟏, 𝟐, … . , 𝒏 − 𝟐

 Total number of conditions =

→ 𝑻𝒐𝒕𝒂𝒍 𝒏𝒖𝒎𝒃𝒆𝒓 𝒐𝒇 𝒄𝒐𝒏𝒅𝒊𝒕𝒊𝒐𝒏𝒔 = (𝒏 − 𝟏) + (𝒏 − 𝟏) + (𝒏 − 𝟐)

= 𝟑(𝒏 − 𝟏) − 𝟏

 Short by one condition:

3. The last condition can be arbitrary,

Example: 𝒇′′
𝟏 (𝒙𝟏 ) = 𝟎, → 𝒂𝟏 = 𝟎

Example

Fit the data below in quadratic splines:

x: 15 42 128 317 433

f(x): 14.6 10.7 4.8 1.7 0.3

Solution:
 College of Engineering, Department of Mechanical Engineering
Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

We have 4 subintervals,  4 splines

𝒇𝒊 (𝒙𝒊 ) = 𝒂𝒊 𝒙𝟐𝒊 + 𝒃𝒊 𝒙𝒊 + 𝒄𝒊 , 𝒊 = 𝟏, 𝟐, 𝟑, 𝟒

Splines pass thru data points:

(𝟏) 𝒇𝒊 (𝒙𝒊 ) = 𝒂𝒊 𝒙𝟐𝒊 + 𝒃𝒊 𝒙𝒊 + 𝒄𝒊 , 𝒊 = 𝟏, 𝟐, 𝟑, 𝟒

𝟐𝟐𝟓𝒂𝟏 + 𝟏𝟓𝒃𝟏 + 𝒄𝟏 = 𝟏𝟒. 𝟔 (𝟏)

𝟏𝟕𝟔𝟒𝒂𝟐 + 𝟒𝟐𝒃𝟐 + 𝒄𝟐 = 𝟏𝟎. 𝟕 (𝟐)

𝟏𝟔𝟑𝟖𝟒𝒂𝟑 + 𝟏𝟐𝟖𝒃𝟑 + 𝒄𝟑 = 𝟒. 𝟖 (𝟑)

𝟏𝟎𝟎𝟒𝟖𝟗𝒂𝟒 + 𝟑𝟏𝟕𝒃𝟒 + 𝒄𝟒 = 𝟏. 𝟕 (𝟒)

(𝟐) 𝒇𝒊 (𝒙𝒊+𝟏 ) = 𝒂𝒊 𝒙𝟐𝒊+𝟏 + 𝒃𝒊 𝒙𝒊+𝟏 + 𝒄𝒊 , 𝒊 = 𝟏, 𝟐, 𝟑, 𝟒

𝟏𝟕𝟔𝟒𝒂𝟏 + 𝟒𝟐𝒃𝟏 + 𝒄𝟏 = 𝟏𝟎. 𝟕 (𝟓)

𝟏𝟔𝟑𝟖𝟒𝒂𝟐 + 𝟏𝟐𝟖𝒃𝟐 + 𝒄𝟐 = 𝟒. 𝟖 (𝟔)

𝟏𝟎𝟎𝟒𝟖𝟗𝒂𝟑 + 𝟑𝟏𝟕𝒃𝟑 + 𝒄𝟑 = 𝟏. 𝟕 (𝟕)

𝟏𝟖𝟕𝟒𝟖𝟗𝒂𝟒 + 𝟒𝟑𝟑𝒃𝟒 + 𝒄𝟒 = 𝟎. 𝟑 (𝟖)

(𝟑) 𝒇′𝒊 (𝒙𝒊+𝟏 ) = 𝒇′𝒊+𝟏 (𝒙𝒊+𝟏 ), 𝒊 = 𝟏, 𝟐, 𝟑

𝒊 = 𝟏: 𝒇′𝟏 (𝒙𝟐 ) = 𝒇′𝟐 (𝒙𝟐 ), → 𝟐𝒂𝟏 𝒙𝟐 + 𝒃𝟏 = 𝟐𝒂𝟐 𝒙𝟐 + 𝒃𝟐

𝟐(𝟒𝟐)𝒂𝟏 + 𝒃𝟏 = 𝟐(𝟒𝟐)𝒂𝟐 + 𝒃𝟐 (𝟗)

𝒊 = 𝟐: 𝒇′𝟐 (𝒙𝟑 ) = 𝒇′𝟑 (𝒙𝟑 ), → 𝟐𝒂𝟐 𝒙𝟑 + 𝒃𝟐 = 𝟐𝒂𝟑 𝒙𝟑 + 𝒃𝟑

𝟐(𝟏𝟐𝟖)𝒂𝟐 + 𝒃𝟐 = 𝟐(𝟏𝟐𝟖)𝒂𝟑 + 𝒃𝟑 (𝟏𝟎)

𝒊 = 𝟑: 𝒇′𝟑 (𝒙𝟒 ) = 𝒇′𝟒 (𝒙𝟒 ), → 𝟐𝒂𝟑 𝒙𝟒 + 𝒃𝟑 = 𝟐𝒂𝟒 𝒙𝟒 + 𝒃𝟒

𝟐(𝟑𝟏𝟕)𝒂𝟑 + 𝒃𝟑 = 𝟐(𝟑𝟏𝟕)𝒂𝟒 + 𝒃𝟒 (𝟏𝟏)

(4) 𝑺𝒆𝒕 𝒇′′

𝟏 (𝒙𝟏 ) = 𝟎, → 𝒂𝟏 = 𝟎

Solve above system using Gauss elimination,……….

 College of Engineering, Department of Mechanical Engineering
Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

3. Cubic Splines

Cubic Splines
General Form:

𝒇𝒊 (𝒙) = 𝒂𝒊 𝒙𝟑 + 𝒃𝒊 𝒙𝟐 + 𝒄𝒊 𝒙 + 𝒅𝒊 , 𝒊 = 𝟏, … , 𝒏 − 𝟏

For “n” data points, we have “n-1” subintervals  “n-1” splines

 Total number of unknowns = 4(n-1)

Conditions to be satisfied by the splines:

1. Splines pass thru data points:

𝒇𝒊 (𝒙𝒊 ) = 𝒂𝒊 𝒙𝟑𝒊 + 𝒃𝒊 𝒙𝟐𝒊 + 𝒄𝒊 𝒙𝒊 + 𝒅𝒊 , 𝒊 = 𝟏, … , 𝒏 − 𝟏

𝒇𝒊 (𝒙𝒊+𝟏 ) = 𝒂𝒊 𝒙𝟑𝒊+𝟏 + 𝒃𝒊 𝒙𝟐𝒊+𝟏 + 𝒄𝒊 𝒙𝒊+𝟏 + 𝒅𝒊 , 𝒊 = 𝟏, … , 𝒏 − 𝟏

2. Splines’ 1st derivatives @ interior points exist:

𝒇′𝒊 (𝒙𝒊+𝟏 ) = 𝒇′𝒊+𝟏 (𝒙𝒊+𝟏 ), 𝒊 = 𝟏, 𝟐, … . , 𝒏 − 𝟐

3. 2nd derivative continuity at the interior points:

𝒇′′ ′′
𝒊 (𝒙𝒊+𝟏 ) = 𝒇𝒊+𝟏 (𝒙𝒊+𝟏 ), 𝒊 = 𝟏, 𝟐, … . , 𝒏 − 𝟐

 Total number of conditions = (n-1) +(n-1) + (n-2) + (n-2) = 4(n-1) – 2

 College of Engineering, Department of Mechanical Engineering
Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

Recall: total number of unknowns = 4(n-1)

 Short by 2 conditions

 Impose 2 more conditions:

4. Set 2nd derivatives at first and last points = 0

𝒇′′
𝟏 (𝒙𝟏 ) = 𝟎, → 𝟔𝒂𝟏 𝒙𝟏 + 𝒃𝟏 = 𝟎

𝒇′′
𝒏−𝟏 (𝒙𝒏 ) = 𝟎, → 𝟔𝒂𝒏−𝟏 𝒙𝒏 + 𝒃𝒏−𝟏 = 𝟎
 College of Engineering, Department of Mechanical Engineering
Lecture Notes 0402307 Numerical Analysis Khalid Ramadan

HW Problem Set 5 (Interpolation)

Problem 1:
Given the following data:
x: 3.0 4.5 7.0 9.0
f(x): 2.5 1.0 2.5 0.5
A. Fit quadratic splines to the given data
B. Fit cubic splines to the given data.
C. Plot the quadratic, cubic and the discrete data points on the same graph.

Problem 2:
Given 𝒇(𝒙) = 𝒍𝒏 𝒙,
Estimate ln 2 using:
A. Linear Lagrange interpolating functions, with 𝒙𝒐 = 𝟏, 𝒙𝟏 = 𝟒
B. 2nd order Lagrange interpolating functions, with 𝒙𝒐 = 𝟏, 𝒙𝟏 = 𝟒, 𝒙𝟐 = 𝟓
C. 3rd order Lagrange interpolating functions, with
𝒙𝒐 = 𝟏, 𝒙𝟏 = 𝟒, 𝒙𝟐 = 𝟓, 𝒙𝟑 = 𝟔