1
Interpolation and Curve Fitting
CVG 2181 Lecture 12
Ata Babakhani
uOttawa.ca
2
Agenda
• wooclap
• Assignment Review
• Interpolation vs Curve Fitting
• Polynomial Interpolation
-Newton Interpolation
uOttawa.ca
3
wooclap
uOttawa.ca
4
wooclap
uOttawa.ca
5
Assignment
uOttawa.ca
6
Assignment
uOttawa.ca
7
Assignment
uOttawa.ca
8
Final Exam, Quiz, Lab, Assignment
• Final Exam is scheduled for April 22 at 9:30 am.
• There is no lab session scheduled for this week
• There is no quiz for this week
• Assignment 3 has posted to the virtual campus
uOttawa.ca
9
uOttawa.ca
10
Finding Points/Equation Between Discrete Values
i 0 1 2 …. n-1 n
ti
C(ti)
𝐶 (𝑡) ?
t0 t1 t2 t3 t tn-1 tn
How can we find C(t) function using the collected samples at different time intervals?
uOttawa.ca
11
Finding Points/Equation Between Discrete Values
• Interpolation: Process of fitting a curve
through data points by assuming that the data
points are error-free
• Getting reasonable estimates of data points
between the given points
• Curve Fitting: Process of fitting a curve
through data points by assuming that data
points are NOT error-free
• Finding the trend of a given set of data
uOttawa.ca
12
Interpolating Function
• We have error-free data points.
• We want to fit a function that exactly passes ?
through the given data points.
• Then, we can evaluate intermediate values
x
using this function.
uOttawa.ca
13
Polynomial Interpolation
These polynomials are approximating functions that have
an exact fit at a number of discrete data points.
Given the following n+1 error-free data points
(x0 , y0 ), (x2 , y2 ), (x3 , y3 ), . . . , (xn, yn)
There is one and only one polynomial of order n that passes through
all the points:
f n ( x) = a0 + a1 x + a2 x 2 + a3 x 3 + ... + an x n
The question is to find the coefficients a0 , a1 , . . ., an
uOttawa.ca
14
Polynomial Interpolation
n+1 data points generate a polynomial of order n
i 0 1
xi x0 x1
f(xi) f(x0) f(x1)
A first degree polynomial 𝑓(𝑥) = 𝑎0 + 𝑎1𝑥 passes exactly a0=?
through two points (Linear Interpolation) a1=?
Example:
i 0 1
xi 1 6 f(2)=?
f(xi) 0 1.7917595
uOttawa.ca
15
Polynomial Interpolation
n+1 data points generate a polynomial of order n
i 0 1 2
xi x0 x1 x2
f(xi) f(x0) f(x1) f(x2)
A second degree polynomial 𝑓(𝑥) = 𝑎0 + 𝑎1𝑥 + 𝑎2𝑥2 passes
exactly through three points (Quadratic Interpolation) a0=?
a1=?
a2=?
The more points, the more equations are required to be solved
i 0 1 2 …. n-1 n
xi x0 x1 x2 …. xn-1 xn
f(xi) f(x0) f(x1) f(x2) …. f(xn-1) f(xn)
A nth degree polynomial passes exactly through n+1 points
f n ( x) = a0 + a1 x + a2 x 2 + a3 x 3 + ... + an x n
uOttawa.ca
16
Polynomial Interpolation
i 0 1 2 …. n-1 n
xi x0 x1 x2 …. xn-1 xn
f(xi) f(x0) f(x1) f(x2) …. f(xn-1) f(xn)
An nth-order polynomial that passes through the n+1 points can be written as:
Example:
𝑓 𝑥 = 𝑎0 i 0 1
+ 𝑎1 𝑥 − 𝑥0 x 1 6 i
f(x ) 0 1.7917595
+ 𝑎2 𝑥 − 𝑥0 (𝑥 − 𝑥1 ) i
.
.
+𝑎𝑛−1 𝑥 − 𝑥0 𝑥 − 𝑥1 𝑥 − 𝑥2 ⋯ 𝑥 − 𝑥𝑛−2
+𝑎𝑛 𝑥 − 𝑥0 𝑥 − 𝑥1 𝑥 − 𝑥2 ⋯ 𝑥 − 𝑥𝑛−1
The target is to find the coefficients a0 , a1 , . . ., an
uOttawa.ca
17
Interpolating Function
Polynomial Interpolation Spline Interpolation
Newton Interpolating Lagrange Interpolating
Polynomials Polynomials
uOttawa.ca
18
Newton Interpolation
𝑓 𝑥 = 𝑎0
+ 𝑎1 𝑥 − 𝑥0
+ 𝑎2 𝑥 − 𝑥0 (𝑥 − 𝑥1 )
.
.
+𝑎𝑛−1 𝑥 − 𝑥0 𝑥 − 𝑥1 𝑥 − 𝑥2 ⋯ 𝑥 − 𝑥𝑛−2
+𝑎𝑛 𝑥 − 𝑥0 𝑥 − 𝑥1 𝑥 − 𝑥2 ⋯ 𝑥 − 𝑥𝑛−1
Based on the Newton method, the nth coefficient can be calculated as below:
𝑎𝑛 = 𝑓 𝑥𝑛 , 𝑥𝑛−1 , 𝑥𝑛−2 , … . , 𝑥1 , 𝑥0 𝑓𝑜𝑟 0 ≤ 𝑖 ≤ 𝑛
uOttawa.ca
19
Newton Interpolation
𝑎𝑛 = 𝑓 𝑥𝑛 , 𝑥𝑛−1 , 𝑥𝑛−2 , … . , 𝑥1 , 𝑥0 𝑓𝑜𝑟 0 ≤ 𝑖 ≤ 𝑛
𝑎0 = 𝑓 𝑥0 = 𝑓(𝑥0 )
𝑓(𝑥1 ) − 𝑓(𝑥0 )
𝑎1 = 𝑓 𝑥1 , 𝑥0 = The first-order divided difference
𝑥1 − 𝑥0
𝑓 𝑥2 , 𝑥1 − 𝑓 𝑥1 , 𝑥0
𝑎2 = 𝑓 𝑥2 , 𝑥1 , 𝑥0 = The second-order divided difference
𝑥2 − 𝑥0
𝑓 𝑥3 , 𝑥2 , 𝑥1 − 𝑓 𝑥2 , 𝑥1 , 𝑥0
𝑎3 = 𝑓 𝑥3 , 𝑥2 , 𝑥1 , 𝑥0 =
𝑥3 − 𝑥0
uOttawa.ca
20
Newton Interpolation
The Newton method coefficients using four data points:
xi f (xi) f [xn , xn-1] f [xn , xn-1 , xn-2] f [xn , xn-1 , xn-2 , xn-3]
x0 f(x0)
f [x1 , x0]
= f (x1)- f(x0)
x1-x0
f [x2 , x1 , x0]
x1 f(x1) = f [x2, x1]- f [x1, x0]
x2-x0 𝑓(𝑥)
f [x2 , x1] f [x3, x2 , x1 , x0]
= f(x2)- f(x1) = f [x3, x2, x1]- f [x2, x1, x0]
x2-x1 x3-x0
f [x3 , x2 , x1]
x2 f(x2) = f[x3, x2]- f [x2, x1]
x3-x1
f [x3 , x2] x0 x1 x2 x3
= f(x3)- f(x2)
x3-x2
x3 f(x3)
𝑓3 (𝑥) = 𝑓(𝑥0 ) + 𝑓[𝑥1 , 𝑥0 ](𝑥 − 𝑥0 ) + 𝑓[𝑥2 , 𝑥1 , 𝑥0 ](𝑥 − 𝑥0 )(𝑥 − 𝑥1 )
+ 𝑓[𝑥3 , 𝑥2 , 𝑥1 , 𝑥0 ](𝑥 − 𝑥0 )(𝑥 − 𝑥1 )(𝑥 − 𝑥2 )
uOttawa.ca
21
Newton Interpolation-Example
Example 1:
Find f(2) based on the given points:
i 0 1
a) xi 1 6
Two points = First-order polynomial
f(xi) 0 1.7917595
𝑓𝑛 (𝑥) = 𝑓(𝑥0 ) + 𝑓[𝑥1 , 𝑥0 ](𝑥 − 𝑥0 ) + 𝑓[𝑥2 , 𝑥1 , 𝑥0 ](𝑥 − 𝑥0 )(𝑥 − 𝑥1 )+. . .
+ 𝑓[𝑥𝑛 , 𝑥𝑛−1 , . . . , 𝑥0 ](𝑥 − 𝑥0 )(𝑥 − 𝑥1 ). . . (𝑥 − 𝑥𝑛−1 )
i x f(x) f[xn,xn-1]
𝑓1 (𝑥) = 𝑓(𝑥0 ) + 𝑓[𝑥1 , 𝑥0 ](𝑥 − 𝑥0 ) 0 1 0
0.358351894
1 6 1.7917595
𝑓(𝑥1 ) − 𝑓(𝑥0 )
𝑓 𝑥1 , 𝑥0 =
𝑥1 − 𝑥0
uOttawa.ca
22
Newton Interpolation-Example (cont’d)
Example 2:
Find f(2) based on the given points:
i 0 1
b) xi 1 4 Two points = First-order polynomial
f(xi) 0 1.3862944
𝑓𝑛 (𝑥) = 𝑓(𝑥0 ) + 𝑓[𝑥1 , 𝑥0 ](𝑥 − 𝑥0 ) + 𝑓[𝑥2 , 𝑥1 , 𝑥0 ](𝑥 − 𝑥0 )(𝑥 − 𝑥1 )+. . .
+ 𝑓[𝑥𝑛 , 𝑥𝑛−1 , . . . , 𝑥0 ](𝑥 − 𝑥0 )(𝑥 − 𝑥1 ). . . (𝑥 − 𝑥𝑛−1 )
x f(x) f[xn,xn-1]
𝑓1 (𝑥) = 𝑓(𝑥0 ) + 𝑓[𝑥1 , 𝑥0 ](𝑥 − 𝑥0 ) 1 0
0.46209812
4 1.3862944
𝑓(𝑥1 ) − 𝑓(𝑥0 )
𝑓 𝑥1 , 𝑥0 =
𝑥1 − 𝑥0
uOttawa.ca
23
Newton Interpolation-Example (cont’d)
Comparison between (a) and (b):
i 0 1
(a) xi 1 6 f(2)=0.3583519
f(xi) 0 1.7917595
i 0 1
(b) xi 1 4 f(2)=0.4620981
f(xi) 0 1.3862944
ln(2)=0.6931472
In general, the smaller the interval between the data points,
the better the approximation
uOttawa.ca
24
Newton Interpolation-Example (cont’d)
Example 3:
Find f(2) based on the given points:
i 0 1 2
c) xi 1 4 6 Three points = Second-order polynomial
f(xi) 0 1.3862944 1.7917595
𝑓𝑛 (𝑥) = 𝑓(𝑥0 ) + 𝑓[𝑥1 , 𝑥0 ](𝑥 − 𝑥0 ) + 𝑓[𝑥2 , 𝑥1 , 𝑥0 ](𝑥 − 𝑥0 )(𝑥 − 𝑥1 )+. . .
+ 𝑓[𝑥𝑛 , 𝑥𝑛−1 , . . . , 𝑥0 ](𝑥 − 𝑥0 )(𝑥 − 𝑥1 ). . . (𝑥 − 𝑥𝑛−1 )
𝑓2 (𝑥) = 𝑓(𝑥0 ) + 𝑓[𝑥1 , 𝑥0 ](𝑥 − 𝑥0 ) + 𝑓[𝑥2 , 𝑥1 , 𝑥0 ](𝑥 − 𝑥0 )(𝑥 − 𝑥1 )
𝑓(𝑥1 ) − 𝑓(𝑥0 )
𝑓 𝑥1 , 𝑥0 =
𝑥1 − 𝑥0
𝑓 𝑥2 , 𝑥1 − 𝑓 𝑥1 , 𝑥0
𝑓 𝑥2 , 𝑥1 , 𝑥0 =
𝑥2 − 𝑥0
uOttawa.ca
25
Newton Interpolation-Example (cont’d)
𝑓(𝑥1 ) − 𝑓(𝑥0 )
𝑓 𝑥1 , 𝑥0 =
𝑥1 − 𝑥0
𝑓 𝑥2 , 𝑥1 − 𝑓 𝑥1 , 𝑥0
𝑓 𝑥2 , 𝑥1 , 𝑥0 =
𝑥2 − 𝑥0
i x f(x) f[xn,xn-1] f[xn,xn-1,xn-2]
0 1 0
0.46209812
1 4 1.3862944
0.202732554
-0.051873113 f(2)=0.5658444
2 6 1.7917595
𝑓2 (𝑥) = 𝑓(𝑥0 ) + 𝑓[𝑥1 , 𝑥0 ](𝑥 − 𝑥0 ) + 𝑓[𝑥2 , 𝑥1 , 𝑥0 ](𝑥 − 𝑥0 )(𝑥 − 𝑥1 )
uOttawa.ca
26
Newton Interpolation-Example (cont’d)
Comparison between (a) and (b) and (c):
i 0 1
(a) xi 1 6 f(2)=0.3583519
f(xi) 0 1.7917595
i 0 1
(b) xi 1 4 f(2)=0.4620981
f(xi) 0 1.3862944
ln(2)=0.6931472
i 0 1 2
(c) xi 1 4 6
f(2)=0.5658444
f(xi) 0 1.3862944 1.7917595
In general, having more data points results in
uOttawa.ca
a better approximation
27
Newton Interpolation-Example (cont’d)
Example (2nd order Newton):
Find f(4.5) based on the given points:
i 0 1 2
d) xi 1 4 6
f(xi) 0 1.3862944 1.7917595
Three points = Second-order polynomial
𝑓2 (𝑥) = 𝑓(𝑥0 ) + 𝑓[𝑥1 , 𝑥0 ](𝑥 − 𝑥0 ) + 𝑓[𝑥2 , 𝑥1 , 𝑥0 ](𝑥 − 𝑥0 )(𝑥 − 𝑥1 )
𝑓(𝑥1 ) − 𝑓(𝑥0 ) 𝑓 𝑥2 , 𝑥1 − 𝑓 𝑥1 , 𝑥0
𝑓 𝑥1 , 𝑥0 = 𝑓 𝑥2 , 𝑥1 , 𝑥0 =
𝑥1 − 𝑥0 𝑥2 − 𝑥0
uOttawa.ca
28
Newton Interpolation-Example (cont’d)
f(4.5)=?
Non-Sorted Sorted
i x f(x) f[xn,xn-1] f[xn,xn-1,xn-2] i x f(x) f[xn,xn-1] f[xn,xn-1,xn-2]
0 1 0 0 4 1.3862944
0.46209812 0.202732554
1 4 1.3862944 -0.051873113 1 6 1.7917595 -0.051873113
0.202732554 0.358351894
2 6 1.7917595 2 1 0
𝑓2 (𝑥) = 𝑓(𝑥0 ) + 𝑓[𝑥1 , 𝑥0 ](𝑥 − 𝑥0 ) + 𝑓[𝑥2 , 𝑥1 , 𝑥0 ](𝑥 − 𝑥0 )(𝑥 − 𝑥1 )
f(4.5)=1.778 f(4.5)=1.394
εt =18.19% f(4.5)=ln(4.5)=1.504 εt =7.34%
uOttawa.ca Sorting the points results in a better approximation
