Polynomial Interpolation Newton’s Form CS/SE 4X03
Ned Nedialkov McMaster University February 4, 2021
Outline
Basis
Computing coefficients Divided differences Example
Basis Computing coefficients Divided differences Example Basis
• Basis functions are
j−1
φj (x) = (x−xi) = (x−x0)(x−x1) · · · (x−xj−1),
i=0
• Example: for a cubic interoplant, we have
φ0(x) = 1
φ1(x) = x − x0
φ2(x) = (x − x0)(x − x1)
φ3(x) = (x − x0)(x − x1)(x − x2)
j = 0 : n
Copyright © 2021 N. Nedialkov. All rights reserved.
3/10
Basis Computing coefficients Divided differences Example Computing coefficients
Let yi = f(xi). From
pn(x)=c0 +c1(x−x0)+c2(x−x0)(x−x1)+··· +cn(x−x0)(x−x1)···(x−xn−1)
pn(xi)=c0 +c1(xi −x0)+c2(xi −x0)(xi −x1)+···
+cn(xi −x0)(xi −x1)···(xi −xn−1)=f(xi)
at x = x0, we have
pn(x0)=c0 +c1(x0 −x0)+c2(x0 −x0)(x0 −x1)+···
+cn(x0 −x0)(x0 −x1)···(x0 −xn−1)=f(x0)
c0 = f(x0)
Copyright © 2021 N. Nedialkov. All rights reserved. 4/10
Basis Computing coefficients Divided differences Example Computing coefficients
At x1,
pn(x1)=c0 +c1(x1 −x0)+c2(x1 −x0)(x1 −x1)+···
+cn(x1 −x0)(x1 −x1)···(x1 −xn−1)=f(x1)
c0 + c1(x1 − x0) = f(x1) c1 = f(x1)−c0
x1 − x0
= f(x1) − f(x0)
x1 − x0
Copyright © 2021 N. Nedialkov. All rights reserved. 5/10
Basis Computing coefficients Divided differences Example Computing coefficients
At x2,
pn(x2) = c0 + c1(x2 − x0) + c2(x2 − x0)(x2 − x1) +c3(x2 −x0)(x2 −x1)(x2 −x2)+···
Then
+cn(x1 −x0)(x1 −x1)···(x1 −xn−1)=f(x1)
c0 +c1(x2 −x0)+c2(x2 −x0)(x2 −x1)=f(x2)
f(x ) − c − c (x − x ) f(x2)−f(x1) − f(x1)−f(x0)
c2= 2 0 1 2 0 = x2−x1 x1−x0 (x2 −x0)(x2 −x1) x2 −x0
Exercise: verify the last equality
Copyright © 2021 N. Nedialkov. All rights reserved.
6/10
Basis Computing coefficients Divided differences Example Divided differences
Given x0,x1,…,xn, where 0 ≤ i < j ≤ n, define
f[xi] = f(xi)
f[xi,...,xj]= f[xi+1,...,xj]−f[xi,...,xj−1]
xj − xi f[xi,...,xj] are divided differences over xi,...,xj
Copyright © 2021 N. Nedialkov. All rights reserved. 7/10
Basis Computing coefficients Divided differences Example Divided differences
c0 = f(x0) = f[x0]
c1 = f(x1)−f(x0) =f[x0,x1]
x1 − x0
f(x2)−f(x1) − f(x1)−f(x0)
.
xn − x0
pn (x) = f [x0 ] + f [x0 , x1 ](x − x0 ) + f [x0 , x1 , x2 ](x − x0 )(x − x1 ) +f[x0,x1,...,xn](x−x0)(x−x1)···(x−xn−1) Copyright © 2021 N. Nedialkov. All rights reserved. 8/10
c2 = x2−x1 x1−x0 x2 − x0
f[x ,x ]−f[x ,x ]
= 1 2 0 1 =f[x0,x1,x2]
x2 − x0
cn = f[x1,...,xn]−f[x0,...,xn−1] =f[x0,x1,...,xn]
Basis Computing coefficients Divided differences
Example
Example
i xi f[xi] f[·, ·] f[·, ·, ·] 011 1232
2 4 3 0 −2
3
p2 (x) = f [x0 ] + f [x0 , x1 ](x − x0 ) + f [x0 , x1 , x2 ](x − x0 )(x − x1 ) = 1 + 2(x − 1) − 2(x − 1)(x − 2)
3
Copyright © 2021 N. Nedialkov. All rights reserved. 9/10
Basis Computing coefficients Divided differences Example Example
Suppose we add a new point (3, 5) Then
i xi f[xi] f[·,·] f[·,·,·] f[·,·,·,·] 01
132
2 3 0 −2
3
3 3 5 −2 −2 −2 3
p3(x) = 1 + 2(x − 1) − 2(x − 1)(x − 2) 3
− 2(x−1)(x−2)(x−4) 3
1 2 4
Copyright © 2021 N. Nedialkov. All rights reserved.
10/10