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