Lecture note 4 Numerical Analysis 。We obtain h2 "(o)=o-月-2fo)+fo+1-5f9飞-) for some ro-h<ξ<xo+h. 1.1.3 Richardson's extrapolation Use less accurate formulas to generate a high accuracy formula. Forward difference formula: f(xo+h)-f(xo) h Assume that f is smooth enough.Expand the terms involved in the formula by Taylor's expansion. ()=f(ro)+(( 2 6 n!h"t... So the error of this formula is feo)=f儿m+月-f四+"mlh+olh2+.+faoh h 2 6 n!ha-1+... ·Error is O(h). Richardson's extrapolation:Using other h's to eliminate the term of O(h). ·Replace h by-h: f)=o1---"n+"巴R-+--+ h 2 6 Summing together and dividing by 2: feo）=eo+-feo-D+f”@lh2+fol+… 2h 6 120 ·Central difference formula.Error O(h2)！ To get a more accuracy formula:Replace h by 2h in the above formula fo）)=f儿o+2m-f儿a-2n+4f"wln2+16f6l+.… 4h 6 120 ·One×4-Two 3()2()f(ro-h)f(ro+2h)f(ro-2h)( h 4h 120 ·Error O(h4) f0）=fm-2)-8fo-月+8feo+月-fw+2h+fo6m+.… 12h 30 6
Lecture note 4 Numerical Analysis • We obtain f 00(x0) = 1 h 2 [f(x0 − h) − 2f(x0) + f(x0 + h)] − h 2 12 f (4)(ξ−1) for some x0 − h < ξ < x0 + h. 1.1.3 Richardson’s extrapolation • Use less accurate formulas to generate a high accuracy formula. • Forward difference formula: f(x0 + h) − f(x0) h • Assume that f is smooth enough. Expand the terms involved in the formula by Taylor’s expansion. f(x0 + h) = f(x0) + f 0 (x0)h + f 00(x0) 2 h 2 + f 000(x0) 6 h 3 + . . . + f (n)(x0) n! h n + . . . • So the error of this formula is f 0 (x0) = f(x0 + h) − f(x0) h + f 00(x0) 2 h + f 000(x0) 6 h 2 + . . . + f (n)(x0) n! h n−1 + . . . • Error is O(h). • Richardson’s extrapolation: Using other h’s to eliminate the term of O(h). • Replace h by −h: f 0 (x0) = f(x0) − f(x0 − h) h − f 00(x0) 2 h+ f 000(x0) 6 h 2−. . .+ f (n)(x0) n! (−h) n−1+. . . • Summing together and dividing by 2: f 0 (x0) = f(x0 + h) − f(x0 − h) 2h + f 000(x0) 6 h 2 + f (5)(x0) 120 h 4 + . . . • Central difference formula. Error O(h 2 )! • To get a more accuracy formula: Replace h by 2h in the above formula f 0 (x0) = f(x0 + 2h) − f(x0 − 2h) 4h + 4f 000(x0) 6 h 2 + 16f (5)(x0) 120 h 4 + . . . • One × 4 − T wo 3f 0 (x0) = 2(f(x0 + h) − f(x0 − h)) h − f(x0 + 2h) − f(x0 − 2h) 4h + 12f (5)(x0) 120 h 4+. . . • Error O(h 4 ) f 0 (x0) = f(x0 − 2h) − 8f(x0 − h) + 8f(x0 + h) − f(x0 + 2h) 12h + f (5)(x0) 30 h 4+. . . 6
Lecture note 4 Numerical Analysis 1.2 Numerical integration 1.2.1 Elements of Numerical integration The need often arises for evaluating the definite integral of a function that has no explicit antiderivative or whose antiderivative is not easy to obtain.We want to computeff()dr using only f(),i.e. =0 Called numerical quadrature. Basic idea:use piecewise polynomial to approximate f(z).For each subin- terval,select a set of distinct nodes x0,...,n from the interval [a,b.Then integrate the interpolating polynomial P()=f(L()and its trun- cation error term over [a,b to obtain [fa=[p.a+a+n人ee-raat 1 -∑af+n+n人Eala-)fces where ai()=i()for each i=0,..,n and ()[a, Numerical quadrature: fro-Eu =0 and error En(f)= 1 IIP=o(-i)f(n+1)(())d Trapezoidal rule .Use linear polynomial and approximatef()by a trapezoid area. When f is positive value function,the integral is given by the trapezoid area h(f(xo)+f(a1)/2. Used piecewise linear function to approximate f(z)using zo a,x1 =b, h=6-a. P.倒)=fo)-+f)2二0 0-E1 E1-T0 7
Lecture note 4 Numerical Analysis 1.2 Numerical integration 1.2.1 Elements of Numerical integration • The need often arises for evaluating the definite integral of a function that has no explicit antiderivative or whose antiderivative is not easy to obtain. We want to compute R b a f(x)dx using only f(x), i.e. Z b a f(x) ≈ Xn i=0 aif(xi) Called numerical quadrature. • Basic idea: use piecewise polynomial to approximate f(x). For each subinterval, select a set of distinct nodes x0, · · · , xn from the interval [a, b]. Then integrate the interpolating polynomial Pn(x) = Pn i=0 f(xi)Li(x) and its truncation error term over [a, b] to obtain Z b a f(x) = Z b a Pn(x) + 1 (n + 1)! Z a,b Π n i=0(x − xi)f (n+1)(ξ(x))dx = X i aif(xi) + 1 (n + 1)! Z a,b Π n i=0(x − xi)f (n+1)(ξ(x))dx where ai(x) = R b a Li(x) for each i = 0, · · · , n and ξ(x) ∈ [a, b]. • Numerical quadrature: Z b a f(x) ≈ Xn i=0 aif(xi) and error En(f) = 1 (n + 1)! Z b a Π n i=0(x − xi)f (n+1)(ξ(x))dx Trapezoidal rule • Use linear polynomial and approximate R b a f(x) by a trapezoid area. • When f is positive value function, the integral is given by the trapezoid area h(f(x0) + f(x1))/2. • Used piecewise linear function to approximate f(x) using x0 = a, x1 = b, h = b − a. Pn(x) = f(x0) x − x1 x0 − x1 + f(x1) x − x0 x1 − x0 7