CS计算机代考程序代写 Polynomial Interpolation Newton’s Form CS/SE 4X03

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