chapter 5 : polynomial approximation and interpolation problem

1
chapter 5 : polynomial approximation and interpolation
problem : Given a function f (x), find an approximating polynomial pn (x), where
pn (x) = a0 + a1 x + · · · + an xn is a polynomial of degree n.
application :
Z b
a
f (x)dx →
Z b
a
pn (x)dx , . . .
question : how to find pn (x)? , answer : Taylor approximation
Given f (x) and a point x = a, the Taylor polynomial of degree n about x = a is
pn (x) = f (a) + f 0 (a)(x − a) + 12 f 00 (a)(x − a)2 + · · · + n!1 f (n) (x − a)n .
1
, a = 0 , pn (x) = ?
1 + 25x2
In this case we can find pn (x) without computing f (a), f 0 (a), . . . , f (n) (a).
1
geometric series :
= 1 + r + r2 + · · · , converges iff |r| < 1
1−r
1
1
=
= 1 + (−25x2 ) + (−25x2 )2 + · · · , converges iff |x| ≤
2
2
1 + 25x
1 − (−25x )
ex : f (x) =
p0(x) = 1
p (x) = 1
0
1.5
1.5
1
1
0.5
0.5
0.5
0.5
0
0
0
0
−0.5
−0.5
−1
−1
1.5
1.5
−0.5
−0.5
0
0
0.5
0.5
1
1
p4(x) = 1−25x22+625x44
p (x) = 1−25x +625x
4
1.5
1.5
1
1
0.5
0.5
0.5
0.5
0
0
0
0
−0.5
−0.5
0
0
2
−0.5
−0.5
−1
−1
1
1
−0.5
−0.5
−1
−1
p2(x) = 1−25x22
p (x) = 1−25x
1.5
1.5
1
1
0.5
0.5
1
1
−0.5
−0.5
−1
−1
1
5
−0.5
−0.5
0
0
0.5
0.5
1
1
p6(x) = 1−25x22+625x44−15625x66
p (x) = 1−25x +625x −15625x
6
−0.5
−0.5
0
0
0.5
0.5
1
1
The Taylor polynomial pn (x) is a good approximation to f (x) when x is close
to a, but in general we need to consider other methods of approximation.
2
polynomial interpolation
thm : Assume f (x) is given and let x0 , x1 , . . . , xn be n + 1 distinct points. Then
there exists a unique polynomial pn (x), of degree less than or equal to n, which
interpolates f (x) at the given points, i.e. such that pn (xi ) = f (xi ) for i = 0 : n.
pf : omit
p1
ex : n = 1 ⇒ x0 , x1
f
x0

x1

f (x1 ) − f (x0 ) 
(x − x0 ) : Newton form of p1 (x)
p1 (x) = f (x0 ) + 
x1 − x0
questions
1. How can we construct pn (x) for n ≥ 2?
2. For a given value of n, what is the best choice of interpolation points xi ?
section 5.3 : Newton form of the interpolating polynomial
pn (x) = a0 + a1 (x − x0 ) + a2 (x − x0 )(x − x1 ) + · · · + an (x − x0 ) · · · (x − xn−1 )
We will derive a method to compute a0 , . . . , an . First define some notation.
a0 = f [x0 ] , a1 = f [x0 , x1 ] , a2 = f [x0 , x1 , x2 ] , . . . , an = f [x0 , . . . , xn ]
f [x1 , . . . , xn ] − f [x0 , . . . , xn−1 ]
: divided difference
xn − x0
!
!
x − x0
xn − x
pf : define g(x) =
qn−1 (x) +
pn−1 (x)
xn − x0
xn − x0
claim : f [x0 , . . . , xn ] =
pn−1 (x) interpolates f (x) at x0 , . . . , xn−1 , deg pn−1 ≤ n − 1
qn−1 (x) interpolates f (x) at x1 , . . . , xn , deg qn−1 ≤ n − 1
then deg g ≤ n , g(x0 ) = pn−1 (x0 ) = f (x0 ) , g(xn ) = qn−1 (xn ) = f (xn )
xi − x0
xn − xi
i = 1 : n − 1 ⇒ g(xi ) =
qn−1 (xi ) +
pn−1 (xi ) = f (xi )
xn − x0
xn − x0
⇒ g(x) = pn (x)
!
!
now equate the coefficients of xn in g(x) and pn (x)
⇒
f [x1 , . . . , xn ] f [x0 , . . . , xn−1 ]
−
= f [x0 , . . . , xn ]
xn − x0
xn − x0
ok
3
ex : n = 2 ⇒ x0 , x1 , x2
p2 (x) = a0 + a1 (x − x0 ) + a2 (x − x0 )(x − x1 )
= f [x0 ] + f [x0 , x1 ](x − x0 ) + f [x0 , x1 , x2 ](x − x0 )(x − x1 )
The coefficients can be efficiently computed using a divided difference table.
x0
f[x0]
¤
f[x0;x1]
x1
¤
f[x1]
f[x0;x1;x2]
¤
f[x1;x2]
x2
f[x2]
The starred values are the coefficients in Newton’s form of p2 (x).
ex
f (x) =
1
, x0 = −1 , x1 = 0 , x2 = 1
1 + 25x2
p2 (x) = ?
divided difference table
xi
f (xi )
1
26
−1
0
25
26
− 25
26
1
− 25
26
1
26
1
p2 (x) =
1
26
+
25
26 (x
− (−1)) −
=
1
26
+
25
26 (x
+ 1) −
=1−
25
26 (x
25
26 (x
− (−1))(x − 0)
+ 1)x
25 2
26 x
check : p2 (−1) =
1
26
, p2 (0) = 1 , p2 (1) =
1
26
ok
4
section 5.4 : optimal points for interpolation
Given f (x) for −1 ≤ x ≤ 1, how should the interpolation points x0 , . . . , xn be
chosen? Consider two options.
2
1. uniform points : xi = −1 + ih , h = , i = 0 : n
n
π
2. Chebyshev points : xi = − cos θi , θi = ih , h = , i = 0 : n
n
x
!
uniform points , n=16
1
0
!1
!1.5
!1
!0.5
0
0.5
1
1.5
0.5
1
1.5
Chebyshev points , n=16
1
0
!1
!1.5
!1
!0.5
0
note : The Chebyshev points are clustered near the endpoints of the interval.
5
ex : f (x) =
1
, polynomial interpolation on the interval −1 ≤ x ≤ 1
1 + 25x2
solid line : f (x) , given function
dashed line : pn (x) , interpolating polynomial
uniform points, n=4
Chebyshev points , n=4
1.5
1.5
1
1
0.5
0.5
0
0
−0.5
−0.5
−1
−1
−1.5
−1
0
1
−1.5
uniform points , n=8
1.5
1
1
0.5
0.5
0
0
−0.5
−0.5
−1
−1
−1
0
1
−1.5
uniform points , n=16
1.5
1
1
0.5
0.5
0
0
−0.5
−0.5
−1
−1
−1
0
1
−1
0
1
Chebyshev points , n=16
1.5
−1.5
0
Chebyshev points , n=8
1.5
−1.5
−1
1
−1.5
−1
0
1
1. Interpolation at the uniform points gives a good approximation near the center
of the interval, but it gives a bad approximation near the endpoints.
2. Interpolation at the Chebyshev points gives a good approximation on the
whole interval.
6
section 5.6 : spline interpolation
Let x0 < x1 < · · · < xn−1 < xn . A cubic spline based on these points is a
function s(x) satisfying the following conditions.
1. s(x) is a cubic polynomial on each interval xi ≤ x ≤ xi+1 .
2. s(x) , s0 (x) , s00 (x) are continuous at the interior points x1 , . . . , xn−1
ex : x0 = −1 , x1 = 0 , x2 = 1
(
s(x) =
0 , −1 ≤ x ≤ 0
x3 , 0 ≤ x ≤ 1
(
0
s (x) =
s00 (x) =
0 , −1 ≤ x ≤ 0
3x2 , 0 ≤ x ≤ 1
(
!1
0
1
0 , −1 ≤ x ≤ 0
6x , 0 ≤ x ≤ 1
check : s(x) satisfies the conditions required to be a cubic spline
problem : Given f (x) and x0 < x1 < · · · < xn−1 < xn , find the cubic spline
s(x) which interpolates f (x) at the given points, i.e. s(xi ) = f (xi ) , i = 0 : n.
xi ≤ x ≤ xi+1 ⇒ s(x) = si (x) = c0 + c1 x + c2 x2 + c3 x3 , i = 0 : n − 1
s i{1(x)
x0
xi{1
s i(x)
xi
xi+1
xn
n + 1 points ⇒ n intervals ⇒ 4n unknown coefficients
interpolation conditions ⇒ 2n equations
continuity of s0 (x) , s00 (x) at interior points ⇒ 2(n − 1) equations
We can choose 2 more equations. A popular choice is s00 (x0 ) = s00 (xn ) = 0, which
gives the natural cubic spline interpolant.
how to find s(x)
ex : −1 ≤ x ≤ 1 , xi = −1 + ih , h =
2
n
, i = 0, . . . , n : uniform points
step 1 : 2nd derivative conditions
s00i (x) is a linear polynomial
!
!
xi+1 − x
x − xi
00
⇒ si (x) = ai
+ ai+1
, ai , ai+1 : to be determined
h
h
⇒ s00i (xi ) = ai , s00i (xi+1 ) = ai+1
⇒ s00i−1 (xi ) = ai = s00i (xi ) ⇒ s00 (x) is continuous at the interior points
7
step 2 : interpolation
integrate twice
ai (xi+1 − x)3
ai+1 (x − xi )3
xi+1 − x
x − xi
si (x) =
+
+ bi
+ ci
6h
6h
h
h
!
!
ai h2
ai h2
+ bi = fi ⇒ bi = fi −
si (xi ) =
6
6
ai+1 h2
ai+1 h2
si (xi+1 ) =
+ ci = fi+1 ⇒ ci = fi+1 −
6
6
ai (xi+1 − x)3
ai+1 (x − xi )3
si (x) =
+
6h
6h
!
!
!
!
ai+1 h2 x − xi
ai h2 xi+1 − x
+ fi+1 −
+ fi −
6
h
6
h
step 3 : 1st derivative conditions
ai (xi+1 − x)2
1
ai+1 (x − xi )2
ai h2 −1
ai+1 h2
= −
·
·
+
+ fi −
+ fi+1 −
2h
2h
6
h
6
h
fi
ai h
fi+1
ai+1 h
ai h
−
+
+
−
s0i (xi ) = −
2
h
6
h
6
fi
ai h
fi+1
ai+1 h
ai+1 h
−
+
+
−
s0i (xi+1 ) =
2
h
6
h
6
!
s0i (x)
!
we require s0i−1 (xi ) = s0i (xi )
ai h
fi−1
ai−1 h
fi
ai h
ai h
fi
ai h
fi+1
ai+1 h
−
+
+
−
= −
−
+
+
−
2
h
6
h
6
2
h
6
h
6
!
ai−1 h
h h h h
ai+1 h
fi−1 − 2fi + fi+1
+ ai
− + −
+
=
6
2 6 2 6
6
h
ai−1 + 4ai + ai+1 =
6
h2
(fi−1 − 2fi + fi+1 ) , i = 1 : n − 1
step 4 : apply BC
s000 (x0 ) = 0 ⇒ a0 = 0 , s00n−1 (xn ) = 0 ⇒ an = 0
4

1








1
4
...
f0 − 2f1 + f2
a1
 . 


..


  .. 
.




6
 . 


.


  ..  =
.
.




2
 . 


h 
..
.




1 . 
.


4
an−1
fn−2 − 2fn−1 + fn

1
...
...
...
...
1


A : tridiagonal , symmetric , positive definite

8
ex : natural cubic spline interpolation
f (x) =
1
2
, − 1 ≤ x ≤ 1 , xi = −1 + ih , h = , i = 0 : n
2
1 + 25x
n
solid line : f (x) , given function
dashed line : s(x) , natural cubic spline interpolant
n=!
n=4
!
!
1
1
0
0
!1
!1
!!
!!
!1
0
1
!
!!
!!
!1
n='
!
1
1
0
0
!1
!1
!1
0
1
!
1
!
n=8
!
!!
!!
0
1
1. error bound : |f (x) − s(x)| ≤
!
!!
!!
!1
0
5
max |f (4) (x)| h4 : 4th order accurate
384 a≤x≤b
2. The natural cubic spline interpolant has inflection points at the endpoints of
the interval, due to the boundary conditions s00 (x0 ) = s00 (xn ) = 0, but there are
additional inflection points in the interior of the interval, which are problematic
in some applications.

Download Report