Lecture Note 4:Numerical differentiation and integration Xiaoqun Zhang Shanghai Jiao Tong University Last updated:November 6,2012
Lecture Note 4: Numerical differentiation and integration Xiaoqun Zhang Shanghai Jiao Tong University Last updated: November 6, 2012
Lecture note 4 Numerical Analysis 1.1 Numerical differentiation 1.1.1 Introduction Find an approximation of f'(zo),f"(zo),...,in terms of only f(x). ·Since f'(o)= f(co+h)-f(xo) h we use f'(o)≈fo+)-fo) h Used in Secant method. h>0,forward difference formula .h<0,backward difference formula Use a graph to illustrate this. Not successful due to round-off error. Quantitative study of the error: -Assume that zo∈(a,b).Suppose that f∈C2[a,bj.x1=xo+h∈[a,bl. -Use Taylor's expansion. f(ro+h)=f(ro)+f(o)h+f"(2 So f'm)=fo+）-fo_f"(h. h 2 - The error is of (h)since is bounded. -Error:0.1,h is O(0.1) Eror:0.001,hisO(0.001) -To get an accurate f'(zo),h must be very small.However,a small denominator exaggerate the round-off error of f(zo+h)-f(zo).(Recall loss of significant digits.) Error is of O(h).a is the order of the formula. -Error 0.01,order 1:h=0(0.01),order 2:h=O(0.1). -Error0.0001,order1:h=O(0.0001),order2:h=O(0.01) To minimize the influence of the round-off error,higher order formulas are desired. Higher order formula.Idea:Involving more points than only zo,zo+h. 2
Lecture note 4 Numerical Analysis 1.1 Numerical differentiation 1.1.1 Introduction • Find an approximation of f 0 (x0), f 00(x0), . . ., in terms of only f(x). • Since f 0 (x0) = lim h→0 f(x0 + h) − f(x0) h , we use f 0 (x0) ≈ f(x0 + h) − f(x0) h • Used in Secant method. • h > 0, forward difference formula • h < 0, backward difference formula • Use a graph to illustrate this. • Not successful due to round-off error. • Quantitative study of the error: – Assume that x0 ∈ (a, b). Suppose that f ∈ C 2 [a, b]. x1 = x0 + h ∈ [a, b]. – Use Taylor’s expansion. f(x0 + h) = f(x0) + f 0 (x0)h + f 00(ξ) 2 h 2 . So f 0 (x0) = f(x0 + h) − f(x0) h − f 00(ξ) 2 h. – The error is of O(h) since f 00(ξ) 2 is bounded. – Error: 0.1, h is O(0.1) Error: 0.001, h is O(0.001). – : To get an accurate f 0 (x0), h must be very small. However, a small denominator exaggerate the round-off error of f(x0 +h)−f(x0). (Recall loss of significant digits.) • Error is of O(h α). α is the order of the formula. – Error 0.01, order 1: h = O(0.01), order 2: h = O(0.1). – Error 0.0001, order 1: h = O(0.0001), order 2: h = O(0.01). • To minimize the influence of the round-off error, higher order formulas are desired. • Higher order formula. Idea: Involving more points than only x0, x0 + h. 2
Lecture note 4 Numerical Analysis Method:using polynomial P(x)interpolation to approximate f(x),and use P'(zo)to approximate f'(zo). 1.Construct a polynomial P(x)that passes through all the given points. (Lagrange or Newton's divided difference) 2.Pn(x)≈f(z),soPn(a)≈f'() 3.Use Pn(xo)as the formula to approximate f(). Use a graph to illustrate. fa)=∑f0,, fn+1) =0 =0 +Ⅱe-) =0 ·Two-point formula.(f'(zo)≈feo+h-feol) -Interpolate f(z)using two points zo,z1. f回=f+fo,l红-0+"（红-olz-） 2 -Take derivative on both hand side. f'(x)=f[xo,x1] (g"红-o红-x)+"e-o+S红-x +（2d证 2 2 Replace x by to and z1 by zo +h,we obtain f(o)=f,0+月-"》h 2 -The same as obtained from Taylor's expansion. Higher order formula:three-point formula. -Interpolate f(x)using three points ro,t1 and z2. f()=f[xo]+f[zo,1](x-z0)+f[zo,21,2](x-zo)(x-1) +(()(-2o)(-1)(-a). 6 -Take derivative on both hand sides, f'(x)=fz0,x1]+fx0,E1,2](x-xo)+fx0,x1,x2](z-x1) (Ld"((红-oe-x)z-2） +（6d证 +f"（0-oe-)+(e-e-2)+(口-oz-2》) 6 3
Lecture note 4 Numerical Analysis • Method: using polynomial P(x) interpolation to approximate f(x), and use P 0 (x0) to approximate f 0 (x0). 1. Construct a polynomial Pn(x) that passes through all the given points. (Lagrange or Newton’s divided difference) 2. Pn(x) ≈ f(x), so P 0 n (x) ≈ f 0 (x). 3. Use P 0 n (x0) as the formula to approximate f 0 (x). • Use a graph to illustrate. • f(x) = Xn i=0 f[x0, . . . , xi ] i Y−1 j=0 (x − xj ) + f (n+1) (n + 1)! Yn j=0 (x − xj ). • Two-point formula. (f 0 (x0) ≈ f(x0+h)−f(x0) h ) – Interpolate f(x) using two points x0, x1. f(x) = f[x0] + f[x0, x1](x − x0) + f 00(ξ(x)) 2 (x − x0)(x − x1). – Take derivative on both hand side. f 0 (x) =f[x0, x1] + 1 2 df00(ξ(x)) dx (x − x0)(x − x1) + f 00(ξ(x)) 2 (x − x0) + f 00(ξ(x)) 2 (x − x1) – Replace x by x0 and x1 by x0 + h, we obtain f 0 (x0) = f[x0, x0 + h] − f 00(ξ(x)) 2 h. – The same as obtained from Taylor’s expansion. • Higher order formula: three-point formula. – Interpolate f(x) using three points x0, x1 and x2. f(x) =f[x0] + f[x0, x1](x − x0) + f[x0, x1, x2](x − x0)(x − x1) + f 000(ξ(x)) 6 (x − x0)(x − x1)(x − x2). – Take derivative on both hand sides, f 0 (x) = f[x0, x1] + f[x0, x1, x2](x − x0) + f[x0, x1, x2](x − x1) + 1 6 df000(ξ(x)) dx (x − x0)(x − x1)(x − x2) + f 000(ξ(x)) 6 ((x − x0)(x − x1) + (x − x1)(x − x2) + (x − x0)(x − x2)) 3
Lecture note 4 Numerical Analysis Let x zo:Z1 zo-h,and x2 xo +h. f()fo.((2 6 We have fo,fof(oh)-f(o) f(zo+h)-f(ro-h)f(ro-h)-f(o) 2 -h -h =fo+)-f0-) 2h Central difference formula f(xo+h)-f(xo-h) 2h Error term f"(》2, 0h2). 6 Let I Zo:Z1=x+h,T2 =x+2h. f'o)=o,-hfo,1,+"》h2 3 We have fof(h)f(o)h f(zo+2h)-f(zo+h)f(ro+h)-f(Fo) h h 2h =-3fo)+4f0+)-f(0+2h) 2h Another three-point formula -3f(zo)+4f(x0+h)-f(xo+2h) 2h Error term f"(h2, 0(h2). -The error of the central difference formula is half of the other.The reason:z1 and x2 are closer to zo in its derivation. ·Similarly,we have -Five-point formula. f'(2o）)=12ifao-2h）-8fzo-h0+8f6+0+-f6ao+2h》+30f() 1 -Can construct formulae involving more points
Lecture note 4 Numerical Analysis – Let x = x0, x1 = x0 − h, and x2 = x0 + h. f 0 (x0) = f[x0, x1] + hf[x0, x1, x2] − f 000(ξ(x)) 6 h 2 We have f[x0, x1] + hf[x0, x1, x2] = f(x0 − h) − f(x0) −h + h f(x0+h)−f(x0−h) 2h − f(x0−h)−f(x0) −h h = f(x0 + h) − f(x0 − h) 2h Central difference formula f(x0 + h) − f(x0 − h) 2h . Error term − f 000(ξ(x)) 6 h 2 , O(h 2 ). – Let x = x0, x1 = x + h, x2 = x + 2h. f 0 (x0) = f[x0, x1] − hf[x0, x1, x2] + f 000(ξ(x)) 3 h 2 We have f[x0, x1] + hf[x0, x1, x2] = f(x0 + h) − f(x0) h − h f(x0+2h)−f(x0+h) h − f(x0+h)−f(x0) h 2h = −3f(x0) + 4f(x0 + h) − f(x0 + 2h) 2h Another three-point formula −3f(x0) + 4f(x0 + h) − f(x0 + 2h) 2h . Error term f 000(ξ(x)) 3 h 2 , O(h 2 ). – The error of the central difference formula is half of the other. The reason: x1 and x2 are closer to x0 in its derivation. • Similarly, we have – Five-point formula. f 0 (x0) = 1 12h (f(x0−2h)−8f(x0−h)+8f(x+0+h)−f(x0+2h))+h 4 30 f (5)(ξ) – Can construct formulae involving more points. 4
Lecture note 4 Numerical Analysis Interpolation error: f(z)-Pn(x)= fa+9a-10e-2)（r-n (n+1)！ Assume h >0. Summary of formulas Two-points:zo and zo+h f(xo+h)-f(xo) error =O(h). h Forward difference formula. Two-points:Zo and zo-h f(xo)-f(xo-h) error =O(h). h Backward difference formula. Three points:To-h,To:zo +h f(xo+h)-f(zo-h) error =O(h2). 2h Central difference formula. .Three points:zo;zo+h,zo +2h -3f(xo)+4f(x0+h)-f(x0+2h) error =O(h3). 2h Five points:xo-2h,To -h,zo,zo+h,zo +2h f(x0-2h)-8f(xo-h)+8f(xo+h)-f(x0+2h) error =O(h). 2h 1.1.2 Higher order derivative Expand f at zo and evaluate at xo-h,xo+h: )=(o)+("(( (1.1 f-月=f)-rh+-君an+员G- (1.2) where zo-h<E-1<zo <E1<zo+h.Add the two equations,we have fo+)+f-)=2o)+f"o)k2+29G)+95-h 5
Lecture note 4 Numerical Analysis • Interpolation error: f(x) − Pn(x) = f (n+1)(ξ) (n + 1)! (x − x1)(x − x2). . .(x − xn). Assume h > 0. Summary of formulas • Two-points: x0 and x0 + h f(x0 + h) − f(x0) h , error = O(h). Forward difference formula. • Two-points: x0 and x0 − h f(x0) − f(x0 − h) h , error = O(h). Backward difference formula. • Three points: x0 − h, x0, x0 + h f(x0 + h) − f(x0 − h) 2h , error = O(h 2 ). Central difference formula. • Three points: x0, x0 + h, x0 + 2h −3f(x0) + 4f(x0 + h) − f(x0 + 2h) 2h , error = O(h 3 ). • Five points: x0 − 2h, x0 − h, x0, x0 + h, x0 + 2h f(x0 − 2h) − 8f(x0 − h) + 8f(x0 + h) − f(x0 + 2h) 2h , error = O(h 4 ). 1.1.2 Higher order derivative • Expand f at x0 and evaluate at x0 − h, x0 + h: f(x0 + h) = f(x0) + f 0 (x0)h + 1 2 f 00(x0)h 2 + 1 6 f 000(x0)h 3 + 1 24 f (4)(ξ1)h 4 (1.1) f(x0 − h) = f(x0) − f 0 (x0)h + 1 2 f 00(x0)h 2 − 1 6 f 000(x0)h 3 + 1 24 f (4)(ξ−1)h 4 (1.2) where x0 − h < ξ−1 < x0 < ξ1 < x0 + h. Add the two equations, we have f(x0 + h) + f(x0 − h) = 2f(x0) + f 00(x0)h 2 + 1 24 [f (4)(ξ1) + f (4)(ξ−1)]h 4 5
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
Lecture note 4 Numerical Analysis Uo二+f)=oi=f儿o x0-x1 x1-0 西-眼。+e-0 =-foo-+fca-o） 1 =2(f(o)+fe1-0o) -Uo)+fa》. ●Remarks: The error term for the Trapezoidal rule involves f",so the rule gives the exact result when applied to any function whose second derivative is identically zero, that is,any polynomial of degree one or less. Simpson's rule Assume that the polynomial on [zo,x2]is P(z).Write P(z)=ax2+8x+y Peh=ar2+a+h =(Gar2+号r2+四jen =0(g-功》+2g-》+-w） 后2a(2-oz+20+6)+38(2-ojl2+0）+2-0》 =2四(2a(号+20+)+382+0)+） 6 号2aG++6+39+w+》 ·Let us prove that 2a(+x20+x)+33(x2+x0)+y=f(x0)+4f(x1)+f(x2) Since P(r)is the interpolation of f at zo,x1 and r2,we have f(xo)=ax哈+Bx0+Y e=ai++7=(色）°+e(色）+T f(x2)=axz+8x2+y 8
Lecture note 4 Numerical Analysis Z x1 x0 (f(x0) x − x1 x0 − x1 + f(x1) x − x0 x1 − x0 dx = f(x0) x0 − x1 1 2 (x − x1) 2 | x1 x=x0 + f(x1) x1 − x0 1 2 (x − x0) 2 | x1 x=x0 = − 1 2 f(x0)(x0 − x1) + 1 2 f(x1)(x1 − x0) = 1 2 (f(x0) + f(x1))(x1 − x0) = h 2 (f(x0) + f(x1)). • Remarks: The error term for the Trapezoidal rule involves f 00, so the rule gives the exact result when applied to any function whose second derivative is identically zero, that is, any polynomial of degree one or less. Simpson’s rule • Assume that the polynomial on [x0, x2] is P(x). Write P(x) = αx2 + βx + γ Z x2 x0 P(x)dx = Z x2 x0 (αx2 + βx + γ)dx = (1 3 αx3 + 1 2 βx2 + γx)| x2 x=x0 = 1 3 α(x 3 2 − x 3 0 ) + 1 2 β(x 2 2 − x 2 0 ) + γ(x2 − x0) = 1 6 (2α(x2 − x0)(x 2 2 + x2x0 + x 2 0 ) + 3β(x2 − x0)(x2 + x0) + γ(x2 − x0)) = x2 − x0 6 (2α(x 2 2 + x2x0 + x 2 0 ) + 3β(x2 + x0) + γ) = h 3 (2α(x 2 2 + x2x0 + x 2 0 ) + 3β(x2 + x0) + γ) • Let us prove that 2α(x 2 2 + x2x0 + x 2 0 ) + 3β(x2 + x0) + γ = f(x0) + 4f(x1) + f(x2) Since P(x) is the interpolation of f at x0, x1 and x2, we have f(x0) = αx2 0 + βx0 + γ f(x1) = αx2 1 + βx1 + γ = α x0 + x2 2 2 + β x0 + x2 2 + γ f(x2) = αx2 2 + βx2 + γ 8
Lecture note 4 Numerical Analysis So f(xo)+4f(x1)+f(x2) 2 =a6+( +)+a(0+40十2+2)+6的 2 h P()=3fzo)+4f()+f2). 1.2.2 Composite formula .We want to findf()dr using piecewise polynomail to avoid(Runge's phe- nomenon). Cut [a,b]into n subintervals using equally spaced nodes.xo =a,1,2,...,In= b.Do integral on each subinterval. Composite Trapezoidal formula:let h=(b-a)/n and xj=a+jh,j= 0,1…,n. In(f)=h(f(xo)/2+f(x1)+f(x2)+..+f(xn-1)+f(xn)/2) 回+2e+o n-1 j=1 Composite Simpson'rule:choose an even integer n and divide [a,b]into n subintervals with h=(b-a)/n and rj=a+jh.Group the nodes every three points,and we choose the unique polynomial of degree <2 which goes through the 3 points.Do Integral on each sub-interval. In(f):=3f(o)+4f(x)+2f(x2）+4f)+2fx4)+…+2fxm-2)+4fzn-1)+fzn》. n/2-1 n/2 3)+2∑f)+4f-i)+fe》 = ●Remark 1.Why not use one polynomial and then integral?(Runge's phenomenon) 2.limn+In(f)=ff()dr. How fast does it converge? 3.Trapezoid:order 2. Simpson:order 4. in-frwso n-fsc
Lecture note 4 Numerical Analysis So f(x0) + 4f(x1) + f(x2) =α(x 2 0 + 4 x0 + x2 2 2 + x 2 2 ) + βα(x0 + 4x0 + x2 2 + x2) + 6γ = . . . Z x2 x0 P(x) = h 3 (f(x0) + 4f(x1) + f(x2)). 1.2.2 Composite formula • We want to find R b a f(x)dx using piecewise polynomail to avoid (Runge’s phenomenon). • Cut [a, b] into n subintervals using equally spaced nodes. x0 = a, x1, x2, . . . , xn = b. Do integral on each subinterval. • Composite Trapezoidal formula: let h = (b − a)/n and xj = a + jh, j = 0, 1 · · · , n. In(f) := h(f(x0)/2 + f(x1) + f(x2) + . . . + f(xn−1) + f(xn)/2) := h 2 [f(a) + 2 nX−1 j=1 f(xj ) + f(b)] • Composite Simpson’rule: choose an even integer n and divide [a, b] into n subintervals with h = (b − a)/n and xj = a + jh. Group the nodes every three points, and we choose the unique polynomial of degree ≤ 2 which goes through the 3 points. Do Integral on each sub-interval. In(f) := h 3 (f(x0) + 4f(x1) + 2f(x2) + 4f(x3) + 2f(x4) + . . . + 2f(xn−2) + 4f(xn−1) + f(xn)). := h 3 (f(x0) + 2 n/ X 2−1 j=1 f(x2j ) + 4X n/2 j=1 f(x2j−1) + f(xn)). • Remark 1. Why not use one polynomial and then integral? (Runge’s phenomenon) 2. limn→+∞ In(f) = R b a f(x)dx. How fast does it converge? 3. Trapezoid: order 2. Simpson: order 4. In(f) − Z b a f(x)dx ≤ Ch2 In(f) − Z b a f(x)dx ≤ Ch5 9
Lecture note 4 Numerical Analysis 4.f100 points,h=6品=10-2. Eror≈10-4or≈10-8. 1.2.3 Error analysis Lemma 1 (Weighted mean value theorem)Suppose that g(r),w(r)ECla,b] and w(r)doesn't change sign in [a,b.Then,there erists a 0E(a,b)such that rb g()w(e)dz=go。wu Error analysis for Trapezoidal rule In(f)=h(f(xo)/2+f(1)+f(x2)+..+f(xn-1)+f(xm)/2) Theorem 1 Suppose f EC2(a,b].Then 3En [a,b]such that ff-1.)--6-oFp 12 Proof. Step 1 Let P(z)be the unique polynomial that goes through xi and i+1.Error is f-Pn(回=@r-e-4+1,回∈G+山. 2 Then Ea=o恤-fe地 (f(r)-P(z))dx = +f"e(红-e-+1d 2 .(-zi)(zi+1)is continuous and doesn't change the sign in [ri,i+1] .is continuous,and will not prove it. 2 By the weighted mean value theorem,there exists 6E[xi,i+]such that f"()+1 2 J (x-x)(x-x+1)dz. where ni E [zi,zi+1].We have e-e-4b=41- +1 Finally, h3 B=-12"() 10
Lecture note 4 Numerical Analysis 4. If 100 points, h = b−a 100 = 10−2 . Error ≈ 10−4 or ≈ 10−8 . 1.2.3 Error analysis Lemma 1 (Weighted mean value theorem) Suppose that g(x), w(x) ∈ C[a, b] and w(x) doesn’t change sign in [a, b]. Then, there exists a θ ∈ (a, b) such that Z b a g(x)w(x)dx = g(θ) Z b a w(x)dx Error analysis for Trapezoidal rule In(f) = h(f(x0)/2 + f(x1) + f(x2) + . . . + f(xn−1) + f(xn)/2) Theorem 1 Suppose f ∈ C 2 [a, b]. Then ∃ ξn ∈ [a, b] such that Z b a f(x)dx − In(f) = − (b − a)f 00(ξn) 12 h 2 Proof. Step 1 Let P1(x) be the unique polynomial that goes through xi and xi+1. Error is f(x) − P1(x) = f 00(ξ(x)) 2 (x − xi)(x − xi+1), ξ(x) ∈ (xi , xi+1). Then Ei(x) = Z xi+1 xi f(x)dx − Z xi+1 xi f(x)dx = Z xi+1 xi (f(x) − P1(x))dx = Z xi+1 xi f 00(ξ(x)) 2 (x − xi)(x − xi+1)dx • (x − xi)(xi+1) is continuous and doesn’t change the sign in [xi , xi+1] • f 00(ξ(x)) 2 is continuous, and will not prove it. By the weighted mean value theorem, there exists θ ∈ [xi , xi+1] such that Ei = f 00(ηi) 2 Z xi+1 xi (x − xi)(x − xi+1)dx. where ηi ∈ [xi , xi+1]. We have Z xi+1 xi (x − xi)(x − xi+1)dx = − 1 6 (xi+1 − xi) 3 . Finally, Ei = − h 3 12 f 00(ηi) 10