Numerical Accuracy - CEProfs

Numerical Accuracy - CEProfs

Chapter 19 Numerical Differentiation Estimate the derivatives (slope, curvature, etc.) of a function by using the function values at only a set of discrete points Ordinary differential equation (ODE) Partial differential equation (PDE) Represent the function by Taylor polynomials or Lagrange interpolation Evaluate the derivatives of the interpolation polynomial at selected (unevenly distributed) nodal points y f(x) Differentiation Difference dy f ( x x) f ( x) lim dx x 0 ( x x) x y f ( x x) f ( x) dy x ( x x) x

dx A smaller step x (or h) results in a smaller error Evenly distributed points along the xaxis x h xi-3 xi-2 xi-1 xi xi+1 xi+2 xi+3 Distance between two neighboring points is the same, i.e. h. Unevenly distributed points along the xaxis x1

x2 x3 Numerical Differentiation Forward difference Backward difference Centered difference Forward difference de e Tru ve i t a ri v ion t a

m i x o Appr h xi1 xi xi+1 x Backward difference A pp ro xi m at

io n de e Tru ve i t a ri v h xi1 xi xi+1 x Centered difference de

e Tru ve i t a ri v ro p Ap on i t a m i x 2h xi1 xi

xi+1 x y First Derivatives f ( x ) i-2 i-1 Forward difference i f ( x ) i+1 i+2 f ( x i 1 ) f ( x i ) y i 1 y i

x i 1 x i x i 1 x i Backward difference f ( x ) f ( x i ) f ( x i 1 ) y i y i 1 xi xi 1 Central difference f ( x ) xi xi 1 f ( x i 1 ) f ( x i 1 ) y i 1 y i 1 x i 1 x i 1 x i 1 x i 1 x Truncation Errors Uniform grid spacing h2 h3 f ( x i )

f ( x i ) f ( x i 1 ) f ( x i h ) f ( x i ) hf ( x i ) 2! 3! 2 3 h h f ( x ) f ( x h ) f ( x ) hf ( x ) f ( x i ) f ( x i ) i 1 i i i 2! 3! f ( x i 1 ) f ( x i ) h f ( 1 ) forward : f ( x i )

h 2 f ( xi ) f ( xi 1 ) h f ( 2 ) backward : f ( x i ) h 2 f ( x i 1 ) f ( x i 1 ) h 2 f ( 3 ) central : f ( x i ) 2h 6 O(h) O(h) O(h2 ) Example: First Derivatives Use forward and backward difference approximations

to estimate the first derivative of f ( x ) 0.1 x 4 0.15 x 3 0.5 x 2 0.25 x 1.2 at x = 0.5 with h = 0.5 and 0.25 (exact sol. = -0.9125) Forward Difference f ( 1) f (0.5 ) 0.2 0.925 h 0 . 5 , f ( 0 . 5 ) 1.45 , t 58.9%

1 0.5 0.5 h 0.25 , f (0.5 ) f (0.75 ) f (0.5 ) 0.63632813 0.925 1.155, 26.5% t 0.75 0.5 0.25 Backward Difference f (0.5 ) f (0 ) 0.925 1.2 h 0 . 5 , f ( 0 . 5 )

0.55 , t 39.7% 0.5 0 0.5 h 0.25 , f (0.5 ) f (0.5 ) f (0.25 ) 0.925 1.10351563 0.714 , 21.7% t 0.5 0.25 0.25 Example: First Derivative Use central difference approximation to estimate the first derivative of f ( x ) 0.1 x 4 0.15 x 3 0.5 x 2 0.25 x 1.2 at x = 0.5 with h = 0.5 and 0.25 (exact sol. = -0.9125) Central Difference h 0.5 , f ( 0.5 ) f ( 1 ) f ( 0 ) 0.2 1.2

1 .0 , t 9 .6 % 1 0 1 h 0.25 , f ( 0.5 ) f ( 0.75 ) f ( 0.25 ) 0.75 0.25 0.63632813 1.10351563 0.934 , t 2.4% 0.5 Second-Derivatives Taylor-series expansion Uniform grid spacing h2 h3 h4 f ( x i ) f ( x i ) f ( x i )

f ( x i 1 ) f ( x i ) hf ( x i ) 2! 3! 4! 2 3 4 f ( x ) f ( x ) hf ( x ) h f ( x ) h f ( x ) h f ( x ) i 1 i i i i i 2! 3! 4! h2 h4 f ( x i 1 ) f ( x i 1 ) 2 f ( x i ) f ( x i )

f ( x i ) 2! 4! Second-order accurate O(h2) f ( x i 1 ) 2 f ( x i ) f ( x i 1 ) h 2 f ( x i ) f ( ) 2 4! h Centered Finite-Divided Differences Forward Finite-divided differences Backward finite-divided differences First Derivatives f ( x ) Parabolic curve

i-2 i-1 i 3 -point Forward difference f ( x ) i+1 f ( x i 2 ) 4 f ( x i 1 ) 3 f ( x i ) x i 2 x i 3 -point Backward difference f ( x ) 3 f ( x i ) 4 f ( x i 1 ) 3 f ( x i 2 ) xi xi 2 i+2 Example: First Derivatives Use forward and backward difference approximations of O(h2) to estimate the first derivative of f ( x ) 0.1 x 4 0.15 x 3 0.5 x 2 0.25 x 1.2 at x = 0.5 with h = 0.25 (exact sol. = -0.9125)

Forward Difference f ( 0.5 ) f ( 1 ) 4 f ( 0.75 ) 3 f ( 0.5 ) 2( 0.25 ) 0.2 4 ( 0.6363281 ) 3( 0.925 ) 0.859375 , t 5.82% 0.5 Backward Difference 3 f ( 0.5 ) 4 f ( 0.25 ) f ( 0 ) 2( 0.25 ) 3( 0.925 ) 4 ( 1.035156 ) 1.2 0.878125 , t 3.77% 0.5 f ( 0.5 ) Higher Derivatives All second-order accurate O(h2) f ( x i 1 ) f ( x i 1 )

2h f ( x i 1 ) 2 f ( x i ) f ( x i 1 ) f ( x i ) h2 f ( x i 2 ) 2 f ( x i 1 ) 2 f ( x i 1 ) f ( x i 2 ) f ( x i ) h3 f ( x i 2 ) 4 f ( x i 1 ) 6 f ( x i ) 4 f ( x i 1 ) f ( x i 2 ) f ( xi ) h4 f ( x i ) More nodal points are needed for higher derivatives Higher order formula may be derived 19.3 Richardson Extrapolation D 2 D(h1 ) a2 h1

4 a4 h1 2 ........ D (h1 ) E1 (h1 ) (1) D is the true value but unknown and D(h1) is an approximation based on the step size h1. Reducing the step size to half, h2 =h1/2, we obtained another approximation D(h2). D D(h2 ) a2h22 a4h24 D(h2 ) E2 ( h22 ) (2) E1 ( h12 ) E2 ( h22 ) 4 4D( h2 ) D( h1 ) Hence 4*(2) - (1), D +E3 ( h14 ) 3 By properly combining the two approximations, D(h1) & D(h2),

the error is reduced to O(h4). Example of using Richardson Extrapolation Central Difference Scheme 1 h2 f '( x ) D h [ f ( x h ) f ( x h )] f '''( x ) O ( h 4 ) (1) 2h 6 1 h2 f '( x ) D h / 2 [ f ( x h / 2) f ( x h / 2)] f '''( x ) O ( h 4 ) (2) h 24 4 D( h / 2) D( h ) 4 4*(2) - (1), f ' O( h ) 3 By combining the two approximations, D(h/2) & D(h), the error of f(h) is reduced to O(h4).

Ex19.2: Richardson Extrapolation Use central difference approximation to estimate the first derivative of f ( x ) 0.1 x 4 0.15 x 3 0.5 x 2 0.25 x 1.2 at x = 0.5 with h = 0.5 and 0.25 (exact sol. = -0.9125) D1 ( h 0.5) f (1) f (0) 1.0, 1 0 D2 ( h 0.25) t 9.6% f (0.75) f (0.25) 0.934, t 2.4% 0.75 0.25 4 D2 D1 D 0.9125,

3 t 0% General Three-Point Formula Lagrange interpolation polynomial for unequally spaced data f ( x ) Li 1 ( x ) f ( x i 1 ) Li ( x ) f ( x i ) Li 1 ( x ) f ( x i 1 ) ( x x i )( x x i 1 ) f ( xi 1 ) ( x i 1 x i )( x i 1 x i 1 ) ( x x i 1 )( x x i 1 ) f ( xi ) ( x i x i 1 )( x i x i 1 ) ( x x i 1 )( x x i ) f ( x i 1 ) ( x i 1 x i 1 )( x i 1 x i ) Lagrange Interpolation 1st-order Lagrange polynomial x x0 x x1

f 1 ( x ) L0 f ( x0 ) L1 ( x ) f ( x1 ) f ( x0 ) f ( x1 ) x0 x 1 x 1 x0 Second-order Lagrange polynomial ( x x 1 )( x x 2 ) f2 ( x ) f ( x0 ) ( x0 x 1 )( x0 x 2 ) ( x x0 )( x x 2 ) f ( x1 ) ( x 1 x0 )( x 1 x 2 ) ( x x0 )( x x1 ) f ( x2 ) ( x 2 x0 )( x 2 x 1 ) Lagrange Interpolation Third-order Lagrange polynomial ( x x 1 )( x x 2 )( x x 3 ) f3 ( x ) f ( x0 )

( x0 x 1 )( x0 x 2 )( x0 x 3 ) ( x x0 )( x x 2 )( x x 3 ) f ( x1 ) ( x 1 x0 )( x 1 x 2 )( x 1 x 3 ) ( x x0 )( x x 1 )( x x 3 ) f ( x2 ) ( x 2 x0 )( x 2 x 1 )( x 2 x 3 ) ( x x0 )( x x 1 )( x x 2 ) f ( x3 ) ( x 3 x0 )( x 3 x 1 )( x 3 x 2 ) Lagrange Interpolation L2(x)f(x2) L0(x)f(x0) x0 L1(x)f(x1) x1

x2 General Three-Point Formula Lagrange interpolation polynomial for unequally spaced data f ( x ) Li 1 ( x ) f ( x i 1 ) Li ( x ) f ( x i ) Li 1 ( x ) f ( x i 1 ) ( x x i )( x x i 1 ) ( x x i 1 )( x x i 1 ) f ( xi 1 ) f ( x i ) ( x i 1 x i )( x i 1 x i 1 ) ( x i x i 1 )( x i x i 1 ) ( x x i 1 )( x x i ) ( x i 1 x i 1 )( x i 1 x i ) f ( x i 1 ) First derivative f ( x ) f ( x i 1 ) 2 x x i x i 1 2 x x i 1 x i 1 f ( x i ) ( x i 1 x i )( x i 1 x i 1 ) ( x i x i 1 )( x i x i 1 )

f ( x i 1 ) 2 x xi 1 xi ( x i 1 x i 1 )( x i 1 x i ) Second Derivative First Derivative for unequally spaced data f ( x ) f ( x i 1 ) 2 x x i x i 1 2 x x i 1 x i 1 f ( x i ) ( x i 1 x i )( x i 1 x i 1 ) ( x i x i 1 )( x i x i 1 ) f ( x i 1 ) 2 x xi 1 xi ( x i 1 x i 1 )( x i 1 x i ) Second Derivative for unequally spaced data f ( x ) f ( x i 1 ) ( xi 1

f ( x i 1 ) ( x i 1 2 2 f ( x i ) x i )( x i 1 x i 1 ) ( x i x i 1 )( x i x i 1 ) 2 x i 1 )( x i 1 x i ) Differentiation of Noisy Data MATLABs Methods Derivatives are sensitive to the noise Use least square fit before taking derivatives p = polyfit(x, y, n) - coefficients of Pn(x) polyfit(p, x) - evaluation of Pn(x) polyder(p) - differentiation x x( 1 ), x( 2 ), , x( n ) diff ( x ) x( 2 ) x( 1 ), x( 3 ) x( 2 ), , x( n ) x( n 1 ) dy/dx at x(i) forward difference dy diff(y)./diff(x)

dy/dx at x(i 1) backward difference

Recently Viewed Presentations

  • Japanese landscape - The Archi Blog

    Japanese landscape - The Archi Blog

    Unlike the western gardener the Japanese garden devotee visits and appreciates the garden in all the seasons. In spring one revels in the bright green of new buds and the blossoms of the azaleas. In summer you appreciate the contrasts...
  • NCSX TF Coil PDR NCSX Michael Kalish /

    NCSX TF Coil PDR NCSX Michael Kalish /

    On drawings S2/6 "Typical Bracing Detail", where does this detail apply? This does not correspond to the bracing for the Tray support towers shown on drawings S2. On drawings S1/1 Bridge Elevation, the diagonal bracing shown for the bridges does...
  • Title Goes Here

    Title Goes Here

    by writing ideas down, to listen to lectures, and. we all love to practice tasks. Different item. One. item. Compare the Joined Items. Compare each of the joined (coordinated) items to the other coordinate items in the sentence, list, or...
  • 1:002:30 1st Round of Tuesday, June 7th Afternoon

    1:002:30 1st Round of Tuesday, June 7th Afternoon

    Courses to be discussed: Eastern Kentucky University. HLS 201 - Introduction to Emergency Management. Fred May and Melody Buchanan. HLS 451 - Emergency Preparedness and Response
  • Transition Metal Halides in Space ... - Ohio State University

    Transition Metal Halides in Space ... - Ohio State University

    The Importance of Phosphorus Phosphorus key component of RNA, DNA (replication), ATP (metabolism), phospholipids (structure) Cosmically rare - 18th most abundant element Concentrated in biology - 5th most abundant Found in meteorites in the form of schreibersite (Fe,Ni)3P (Pasek &...
  • Becta Accreditation of Internet Services to Education 2005

    Becta Accreditation of Internet Services to Education 2005

    Providers must ensure that upgrades to the available Internet Transit Bandwidth are in place should the usage exceed 75%. Web content filtering across five large categories Content on the IWF CAIC list must be filtered. Providers must ensure that the...
  • Powdery Mildew in the Northeast: More Predictable than Wallstreet

    Powdery Mildew in the Northeast: More Predictable than Wallstreet

    Decision tree for estimating PM risk in the North East. Pan evaporation is in millimeters, fall degree-day accumulation is calculated from base 10°C using daily average temperature. Pan evaporation thresholds were created from averages from 1 Jun to 31 July,...
  • Forestry Review

    Forestry Review

    pa forestry review