Numerical Analysis - Lecture 2: Mathematical Tripos Part IB: Lent 2010

Mathematical Tripos Part IB: Lent 2010
Numerical Analysis Lecture 21

1.2 Divided dierences: a denition
Given pairwise-distinct points x0 , x1 , . . . , xn [a, b], we let p Pn [x] interpolate f C [a, b] there. The coecient of xn in p is called the divided dierence and denoted by f [x0 , x1 , . . . , xn ]. We say that this divided dierence is of degree n. We can derive f [x0 , . . . , xn ] from the Lagrange formula,
n n
f [x0 , x1 , . . . , xn ] =
k=0
f (xk )
=0 =k
1 . xk x
(1.2)
Theorem Let [ a, b] be the shortest interval that contains x0 , x1 , . . . , xn and let f C n [ a, b]. Then there exists [ a, b] such that f [x0 , x1 , . . . , xn ] =
1 (n) ( ). n! f
(1.3)
Proof. Let p be the interpolating polynomial. The error function f p has at least n + 1 zeros in [ a, b] and, applying Rolles theorem n times, it follows that f (n) p(n) vanishes at some [ a, b]. 1 (n) n But p(x) = n! p ( )x + lower order terms (for any R), therefore, letting = , f [x0 , x1 , . . . , xn ] = and we deduce (1.3).
1 (n) ( ) n! p
1 (n) ( ) n! f
Application It is a consequence of the theorem that divided dierences can be used to approximate derivatives.
1.3
Recurrence relations for divided dierences
Our next topic is a useful way to calculate divided dierences (and, ultimately, to derive yet another means to construct an interpolating polynomial). We commence with the remark that f [xi ] is the coecient of x0 in the polynomial of degree 0 (i.e., a constant) that interpolates f (xi ), hence f [xi ] = f (xi ). Theorem Suppose that x0 , x1 , . . . , xk+1 are pairwise distinct, where k 0. Then f [x0 , x1 , . . . , xk+1 ] = f [x1 , x2 , . . . , xk+1 ] f [x0 , x1 , . . . , xk ] . xk+1 x0 (1.4)
Proof. Let p, q Pk [x] be the polynomials that interpolate f at {x0 , x1 , . . . , xk } respectively and dene r(x) := (x x0 )q (x) + (xk+1 x)p(x) Pk+1 [x]. xk+1 x0 and {x1 , x2 , . . . , xk+1 }
1 Corrections and suggestions to these notes should be emailed to A.Iserles@damtp.cam.ac.uk. All handouts are available on the WWW at the URL http://www.damtp.cam.ac.uk/user/na/PartIB/.
We readily verify that r(xi ) = f (xi ), i = 0, 1, . . . , k + 1. Hence r is the (k + 1)-degree interpolating polynomial and f [x0 , . . . , xk+1 ] is the coecient of xk+1 therein. The recurrence (1.4) follows from the denition of divided dierences. 2
1.4
The Newton interpolation formula
Recalling that f [xi ] = f (xi ), the recursive formula allows for rapid evaluation of the divided dierence table, in the following manner: f [x0 ] Pq P 1 f [x0 , x1 ] f [x1 ] PP q 1 f [x1 , x2 ] f [x2 ] PP q . . . f [xn1 , xn ] 1 f [xn ] 1 f [xn2 , xn1 , xn ] 1
PP q 1 PP q
f [x0 , x1 , x2 ]
PP q f [x0 , x1 , . . . , xn ]
This can be done in O n2 operations and the outcome are the numbers {f [x0 , x1 , . . . , xl ]}k l=0 . We now provide an alternative representation of the interpolating polynomial. Again, f (xi ), i = 0, 1, . . . , k, are given and we seek p Pk [x] such that p(xi ) = f (xi ), i = 0, . . . , k. Theorem Suppose that x0 , x1 , . . . , xk are pairwise distinct. The polynomial
k 1
pk (x) := f [x0 ] + f [x0 , x1 ](x x0 ) + + f [x0 , x1 , . . . , xk ]

i=0
(x xi ) Pk [x]
obeys pk (xi ) = f (xi ), i = 0, 1, . . . , k. Proof. By induction on k . The statement is obvious for k = 0 and we suppose that it is k true for k . We now prove that pk+1 (x) pk (x) = f [x0 , x1 , . . . , xk+1 ] i=0 (x xi ). Clearly, k+1 pk+1 pk Pk+1 [x] and the coecient of x therein is, by denition, f [x0 , . . . , xk+1 ]. Moreover, k pk+1 (xi ) pk (xi ) = 0, i = 0, 1, . . . , k, hence it is a multiple of i=0 (x xi ), and this proves the asserted form of pk+1 pk . The explicit form of pk+1 follows by adding pk+1 pk to pk . 2 We have derived the Newton interpolation formula, which requires only the top row of the divided dierence table. It has several advantages over Lagranges. In particular, its evaluation at a given point x (provided that divided dierences are known) requires just O(k ) operations, as long as we do it by the Horner scheme pk (x) = {{{f [x0 , . . . , xk ](x xk1 ) + f [x0 , . . . , xk1 ]} (x xk2 ) + f [x0 , . . . , xk2 ]} (x x3 ) + } + f [x0 ]. On the other hand, the Lagrange formula is often better when we wish to manipulate the interpolation polynomial as part of a larger mathematical expression. Well see an example in the section on Gaussian quadrature. b 2

Numerical Analysis - Lecture 2: Mathematical Tripos Part IB: Lent 2010

Uploaded by

Document Informationclick to expand document information

Copyright:

Available Formats

Numerical Analysis - Lecture 2: Mathematical Tripos Part IB: Lent 2010

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Numerical Analysis - Lecture 2: Mathematical Tripos Part IB: Lent 2010

Uploaded by

Copyright:

Available Formats

Mathematical Tripos Part IB: Lent 2010

Numerical Analysis Lecture 21

Recurrence relations for divided dierences

The Newton interpolation formula

pk (x) := f [x0 ] + f [x0 , x1 ](x x0 ) + + f [x0 , x1 , . . . , xk ]

You might also like