Errors in Polynomial Interpolation
CS/SE 4X03
Ned Nedialkov McMaster University February 9, 2021
Outline
Polynomial interpolation error Chebyshev nodes
Polynomial interpolation error Chebyshev nodes Polynomial interpolation error
• Assume
◦ Polynomial pn of degree ≤ n interpolates f at n + 1 distinct
points x0,x1,…,xn, where xi ∈ [a,b] ◦ f(n+1) is continuous on [a,b]
• Then, for each x ∈ [a,b], there is a ξ = ξ(x) ∈ (a,b) such that f(n+1)(ξ) n
f(x)−pn(x) = (n+1)!
(x−xi)
Copyright © 2021 N. Nedialkov. All rights reserved. 3/8
i=0
Polynomial interpolation error Chebyshev nodes Polynomial interpolation error cont.
• Let M = maxa≤t≤b |f(n+1)(t)| Then
M n
|x−xi|
• Leth=(b−a)/nandletxi =a+ihfori=0,1,…,n
Then
|f(x) − pn(x)| ≤ M hn+1 4(n+1)
|f(x)−pn(x)| ≤ (n+1)!
i=0
Copyright © 2021 N. Nedialkov. All rights reserved. 4/8
Polynomial interpolation error Chebyshev nodes Polynomial interpolation error cont.
Example 1. Consider cos(x) and assume values f(xi) = cos(xi) are given at 11 equally spaced points in [a, b] = [−π, π]. What is the error in the interpolating polynomial?
Here n = 10 and h = (b − a)/n = 2π/10. M = max−π≤t≤π | cos(n+1)(t)| = 1.
Then
|f(x) − cos(x)| ≤ M hn+1 = 1 (2π/10)11 ≈ 1.3694 × 10−4
4(n + 1) 4(11)
Copyright © 2021 N. Nedialkov. All rights reserved. 5/8
Polynomial interpolation error Chebyshev nodes Chebyshev nodes
• Suppose f(xi) is given at n+1 distinct points x0,x1,…,xn in [a, b] and pn(x) of degree ≤ n interpolates f at these points
• We have for the error
max |f(x) − pn(x)| ≤ max
M
x∈[a,b] (n + 1)! s∈[a,b] i=0
(s − xi)
n
where M = maxt∈[a,b] |f(n+1)(t)| • How to chose the xi so
n max (s−xi)
is minimized?
s∈[a,b] i=0 Copyright © 2021 N. Nedialkov. All rights reserved.
6/8
Polynomial interpolation error Chebyshev nodes Chebyshev nodes cont.
• Chebyshev nodes on [−1, 1]: 2i+1
xi=cos 2n+2π , i=0,1,…,n
• Min-max property: over all possible xi they minimize
maxs∈[−1,1] |(s − x0)(s − x1) · · · (s − xn)|
min max |(s−x0)(s−x1)···(s−xn)|=2−n
x0,x1,…,xn s∈[−1,1]
• Error bound using Chebyshev nodes in [−1, 1]:
max |f(x) − pn(x)| ≤ M x∈[−1,1] 2n(n + 1)!
M = maxt∈[−1,1] |f(n+1)(t)|
Copyright © 2021 N. Nedialkov. All rights reserved. 7/8
Polynomial interpolation error Chebyshev nodes Chebyshev nodes cont.
• For a general [a, b],
xi =0.5(a+b)+0.5(b−a)cos 2n+2π , i=0,1,…,n
2i+1
Example 2. In the previous example, if we chose Chebyshev nodes,
|f(x) − cos(x)| ≤ M = 1 ≈ 2.4465 × 10−11 2n(n + 1)! 210(10 + 1)!
Copyright © 2021 N. Nedialkov. All rights reserved. 8/8