3.2 Data Approximation and Neville’s Method
1. Interpolation of Tabulated Data
2. Neville’s Method
3. Neville’s Iterated Interpolation
C程式: ALG031 Neville’s Iterated
Interpolation
開課班級: 數學系資統組2A 數值分析
授課教師: 吳漢銘 (淡江大學 數學系)
教學網站: http://www.hmwu.idv.tw
Textbook: Burden & Faires’ Numerical
Analysis, 9/E
系級:
數學系資統組2A 數值分析
學號:
姓名:
3.2 Data Approximation and Neville’s Method
November 5, 2014
1 / 19
1. Application of Interpolation: illustration
Table 3.2 lists values of a function f at various
points. The approximations to f p1.5q obtained by
various Lagrange polynomials that use this data will
be compared to try and determine the accuracy of
the approximation.
(1) The most appropriate linear polynomial uses x0 1.3 and
x1 1.6 because 1.5 is between 1.3 and 1.6. The value of the
interpolating polynomial at 1.5 is
P1 p1.5q
數學系資統組2A 數值分析
p1.5 1.6q f p1.3q p1.5 1.3q f p1.6q
p1.3 1.6q
p1.6 1.3q
1.6q p0.6200860q p1.5 1.3q p0.4554022q
pp1.5
1.3 1.6q
p1.6 1.3q
0.5102968 .
3.2 Data Approximation and Neville’s Method
November 5, 2014
2 / 19
Application of Interpolation: illustration
(conti.)
(2) Two polynomials of degree 2 can reasonably be used, one with
x0 1.3 , x1 1.6 , and x2 1.9 , which gives
1.6qp1.5 1.9q p0.6200860q
pp1.5
1.3 1.6qp1.3 1.9q
p1.5 1.3qp1.5 1.9q p0.4554022q
p1.6 1.3qp1.6 1.9q
p1.5 1.3qp1.5 1.6q p0.2818186q 0.5112857
p1.9 1.3qp1.9 1.6q
and one with x0 1.0 , x1 1.3 , and x2 1.6 , which
gives Pˆ2 p1.5q 0.5124715 .
P2 p1.5q
數學系資統組2A 數值分析
3.2 Data Approximation and Neville’s Method
November 5, 2014
,
3 / 19
Application of Interpolation: illustration
(conti.)
(3) In the third-degree case,
(i) x0
1.3, x1 1.6, x2 1.9, and x3 2.2, which gives P3 p1.5q 0.5118302 .
(ii) x0 1.0, x1 1.3, x2 1.6, and x3
Pˆ3 p1.5q 0.5118127 .
1.9, which gives
(4) The fourth-degree Lagrange polynomial uses all the entries in the
table. With x0 1.0, x1 1.3, x2 1.6, x3 1.9, and x4 2.2,
the approximation is P4 p1.5q 0.5118200 .
P3 p1.5q, Pˆ3 p1.5q, and P4 p1.5q all agree to within
2 105 units, we expect this degree of accuracy for these
approximations. We also expect P4 p1.5q to be the most
accurate approximation, since it uses more of the given data.
(5) Because
數學系資統組2A 數值分析
3.2 Data Approximation and Neville’s Method
November 5, 2014
4 / 19
Application of Interpolation: illustration
(conti.)
(7) The function value at 1.5 is known to be 0.5118277 . Therefore,
the true accuracies of the approximations are as follows:
|P1 p1.5q f p1.5q| |Pˆ2 p1.5q f p1.5q| |Pˆ3 p1.5q f p1.5q| 1.53 103 ,
6.44 104 ,
1.50 105 ,
|P2 p1.5q f p1.5q| 5.42 104 ,
|P3 p1.5q f p1.5q| 2.5 106
|P4 p1.5q f p1.5q| 7.7 106
,
.
(8) Although P3 p1.5q is the most accurate approximation, if we had
no knowledge of the actual value of f p1.5q, we would accept
P4 p1.5q as the best approximation since it includes the most
data about the function.
(9) The Lagrange error term derived in Theorem 3.3 cannot be
applied here because we have no knowledge of the
fourth derivative of f . Unfortunately, this is generally the case.
數學系資統組2A 數值分析
3.2 Data Approximation and Neville’s Method
November 5, 2014
5 / 19
Lagrange Polynomial that Agrees with f pxq
(1) A practical difficulty with Lagrange interpolation is that the
error term is difficult to apply, so the degree of the polynomial
needed for the desired accuracy is generally not known until
computations have been performed.
(2) A common practice is to compute the results given from
polynomials until appropriate agreement is obtained.
various
Definition 3.4
Let f be a function defined at x0 , x1 , x2 , , xn , and suppose that m1 , m2 , , mk are k distinct integers, with 0 ¤
mi ¤ n for each i. The Lagrange polynomial that agrees
with f pxq at the k points xm1 , xm2 , , xmk is denoted
Pm1 ,m2 , ,mk pxq .
數學系資統組2A 數值分析
3.2 Data Approximation and Neville’s Method
November 5, 2014
6 / 19
Example 1
Suppose that x0 1, x1 2, x2 3, x3 4, x4 6, and f pxq ex .
Determine the interpolating polynomial denoted P1,2,4 pxq, and use this
polynomial to approximate f p5q.
Sol:
À This is the Lagrange polynomial that agrees with f pxq at x1
x2 3, and x4 6. Hence
P1,2,4 pxq Á
f p5q P p5q
px 3qpx 6q e2 px 2qpx 6q e3 px 2qpx 3q e6 .
p2 3qp2 6q
p3 2qp3 6q
p6 2qp6 3q
3qp5 6q 2 p5 2qp5 6q 3 p5 2qp5 3q 6
pp25 3qp2 6q e p3 2qp3 6q e p6 2qp6 3q e
12 e2 e3 12 e6 218.105.
end end
數學系資統組2A 數值分析
2,
3.2 Data Approximation and Neville’s Method
November 5, 2014
7 / 19
Theorem 3.5
Theorem 3.5
Let f be defined at x0 , x1 , , xk , and let
distinct numbers in this set. Then
P px q
xj
pxi xj q rpx xj qP0,1, ,j
and
1
px xiqP0,1, ,i1,i
1,
1,j 1,
xi
be two
,k pxq
,k pxqs
is the kth Lagrange polynomial that interpolates f at the k
points x0 , x1 , , xk .
數學系資統組2A 數值分析
3.2 Data Approximation and Neville’s Method
November 5, 2014
1
8 / 19
Theorem 3.5
(conti.)
(1) Theorem 3.5 implies that the interpolating polynomials can be
generated recursively . For example, we have
P0,1
P1,2
P0,1,2
1
rpx x0 qP1 px x1 qP0 s
,
1
rpx x1 qP2 px x2 qP1 s
,
1
rpx x0 qP1,2 px x2 qP0,1 s
x1 x0
x2 x1
x2 x0
,
and so on. They are generated in the manner shown in below,
where each row is completed before the succeeding rows are begun.
數學系資統組2A 數值分析
3.2 Data Approximation and Neville’s Method
November 5, 2014
9 / 19
Neville’s Method
(2) The procedure that uses the result of Theorem 3.5 to recursively
generate interpolating polynomial approximations is called
Neville’s method .
(3) To avoid the multiple subscripts, we let Qi,j pxq , for
0 ¤ j ¤ i , denote the interpolating polynomial of degree j
the pj 1q numbers xij , xij 1 , , xi1 , xi ; that is,
Qi,j
Pij,ij
1,
on
,i1,i .
Using this notation provides the Q notation array in Table 3.4.
數學系資統組2A 數值分析
3.2 Data Approximation and Neville’s Method
November 5, 2014
10 / 19
Example 2
Values of various interpolating polynomials at
x 1.5 were obtained in the Illustration at the
beginning of the Section using the data shown in
Table 3.5. Apply Neville’s method to the data by
constructing a recursive table of the form shown
in Table 3.4.
Sol:
Table 3.5
À Let x0 1.0, x1 1.3, x2 1.6, x3 1.9, and x4 2.2, then
Q0,0 f p1.0q, Q1,0 f p1.3q, Q2,0 f p1.6q, Q3,0 f p1.9q, and
Q4,0 f p2.2q.
Á These are the five polynomials of degree zero (constants) that
approximate f p1.5q, and are the same as data given in Table 3.5.
數學系資統組2A 數值分析
3.2 Data Approximation and Neville’s Method
November 5, 2014
11 / 19
Example 2
(conti.)
 Calculating the first-degree approximation Q1,1 p1.5q gives
px x1 qQ0,0
px x0 qQ1,0
x1 x0
1,0 p1.5 1.3qQ0,0
p1.5 1.0qQ1.3
1.0
0.5p0.6200860q 0.2p0.7651977q
0.3
0.5233449.
p1.5 1.3qp0.4554022q p1.5 1.6qp0.6200860q
Q2,1 p1.5q 1.6 1.3
0.5102968,
Q3,1 p1.5q 0.5132634, and Q4,1 p1.5q 0.5104270.
Q1,1 p1.5q
數學系資統組2A 數值分析
3.2 Data Approximation and Neville’s Method
November 5, 2014
12 / 19
Example 2
(conti.)
à The best linear approximation is expected to be Q2,1 because 1.5 is
between x1 1.3 and x2 1.6.
Ä Approximations using higher-degree polynomials are given by
q p1.5 1.6qp0.5233449q
p1.5 1.0qp0.5102968
1.6 1.0
0.5124715,
Q3,2 p1.5q 0.5112857, and Q4,2 p1.5q 0.5137361.
Q2,2 p1.5q
The higher-degree approximations are generated in a similar
manner and are shown in Table 3.6.
end end
數學系資統組2A 數值分析
3.2 Data Approximation and Neville’s Method
November 5, 2014
13 / 19
Example 3 (a)
Table 3.7 lists the values of f pxq ln x accurate
to the places given. Use Neville’s method and
four-digit rounding arithmetic to a pproximate
f p2.1q ln 2.1 by completing the Neville table.
Sol:
Table 3.7
À Because x x0 0.1, x x1 0.1, x x2 0.2, and we are
given Q0,0 0.6931, Q1,0 0.7885, and Q2,0 0.8329,we have
Q1,1
Q2,1
Á Q2,2
1
rp0.1q0.7885 p0.1q0.6931s 0.14820.2 0.7410
0.2
1
rp0.1q0.8329 p0.2q0.7885s 0.07441
0.7441.
0.1
0.1
0.31 rp0.1q0.7441 p0.2q0.7410s 0.2276
0.3 0.7420.
end end
數學系資統組2A 數值分析
3.2 Data Approximation and Neville’s Method
November 5, 2014
14 / 19
Example 3 (b)
Find the absolute error and the Lagrange error bound in Example 3(a).
Sol:
À In Example 3(a) we have f p2.1q ln 2.1 0.7419 to four decimal
places, so the absolute error is
|f p2.1q P2 p2.1q| |0.7419 0.7420| 104 .
Á However, f 1 pxq 1{x, f 2 pxq 1{x2 , and f 3 pxq 2{x3 , so the
Lagrange error formula gives the error bound
|f p2.1q P 2p2.1q| ¤
end end
數學系資統組2A 數值分析
f 3 pξ p2.1qq
p
x x0 qpx x1 qpx x2 q
3!
1
p
0.1
qp
0.1
qp
0.2
q
3
3pξ p2.1qq
0.002
8.¯3 105 .
3p2q3
3.2 Data Approximation and Neville’s Method
November 5, 2014
15 / 19
Example 3
(conti.)
(1) Notice that the actual error, 104 , exceeds the error bound,
8.¯3 105 . This apparent contradiction is a consequence of
finite-digit computations.
(2) We used four-digit rounding arithmetic, and the Lagrange error
formula (3.3) assumes infinite-digit arithmetic. This caused our
actual errors to exceed the theoretical error estimate.
(3) Remember: You cannot expect more accuracy than the
arithmetic provides.
數學系資統組2A 數值分析
3.2 Data Approximation and Neville’s Method
November 5, 2014
16 / 19
ALGORITHM 031: Neville’s Iterated
Interpolation
To evaluate the interpolating polynomial P on the n 1 distinct
numbers x0 , , xn at the number x for the function f :
數學系資統組2A 數值分析
3.2 Data Approximation and Neville’s Method
November 5, 2014
17 / 19
Exercise Set 3.2
(1) 用手、 或計算機算: 5, 7
(2) 用電腦或寫程式算 (列出表格): 1(a)(b), 3(a)(b)
數學系資統組2A 數值分析
3.2 Data Approximation and Neville’s Method
November 5, 2014
18 / 19
C 程式: ALG031 Neville’s Iterated Interpolation
數學系資統組2A 數值分析
3.2 Data Approximation and Neville’s Method
November 5, 2014
19 / 19
© Copyright 2024 ExpyDoc
