Scribd Logo
Upload

Welcome to Scribd!

  • 107 views

    Predictor Corrector Method

    Uploaded by

    lazarbaruch3033
    This section discusses numerical methods for approximating derivatives of functions. It introduces Newton's forward and backward interpolation formulas which can be used to numerically evaluate derivatives. Higher order derivatives can be obtained by taking additional derivatives of the interpolation formulas. Predictor-corrector methods like Modified Euler's method and Milne's method are presented which use previous function evaluations to improve derivative approximations between points.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd

    Predictor Corrector Method

    Uploaded by

    lazarbaruch3033
    107 views5 pages
    This section discusses numerical methods for approximating derivatives of functions. It introduces Newton's forward and backward interpolation formulas which can be used to numerically evaluate derivatives. Higher order derivatives can be obtained by taking additional derivatives of the interpolation formulas. Predictor-corrector methods like Modified Euler's method and Milne's method are presented which use previous function evaluations to improve derivative approximations between points.

    Original Description:

    Symbolic Methods in numerical approximation

    Copyright

    © Attribution Non-Commercial (BY-NC)

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This section discusses numerical methods for approximating derivatives of functions. It introduces Newton's forward and backward interpolation formulas which can be used to numerically evaluate derivatives. Higher order derivatives can be obtained by taking additional derivatives of the interpolation formulas. Predictor-corrector methods like Modified Euler's method and Milne's method are presented which use previous function evaluations to improve derivative approximations between points.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    107 views5 pages

    Predictor Corrector Method

    Uploaded by

    lazarbaruch3033
    This section discusses numerical methods for approximating derivatives of functions. It introduces Newton's forward and backward interpolation formulas which can be used to numerically evaluate derivatives. Higher order derivatives can be obtained by taking additional derivatives of the interpolation formulas. Predictor-corrector methods like Modified Euler's method and Milne's method are presented which use previous function evaluations to improve derivative approximations between points.

    Copyright:

    Attribution Non-Commercial (BY-NC)
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    of 5

    Dierence operators

    Forward dierences yi = yi+1 yi Higher order forward dierences are dened recursively k+1 yi = k yi+1 k yi They can be expressed by binomail coecients n n k y0 = yn yn1 + yn2 + + (1)n y0 1 2 Forward dierences yi = yi yi1 k+1 yi = k yi k yi1 Central dierences 1 = yn yn1 = y1 y0 , y 3 = y2 y1 , . . . , yn 2 y 1 2 2 Higher order 2 y1 = y 3 y 1 , 2 y2 = y 5 y 3 and so on. 2 2 2 2 Shit operator E Ef (x) = f (x + h) Its inverse is E 1 f (x) = f (x h) Averaging operator \mu

    + yx h yx = 1 2 yx+ h 2 2 In dierence calculus, E is the fundamental operator and , , , can be expressed in terms of E. = E 1 or E = 1 + = 1 E 1 1 1 = E 2 E 2 1 1 2 2 = 1 2 E +E = E = E = E 2 E = ehD so = ehD 1 (falling) Factorial Notation (x)k = x(x 1) . . . (x k + 1) When the interval is h then (x)k = x(x h) . . . (x k 1h) Reciprocal factorial x(n) = (x+h)(x+21 h)...(x+nh) Netwon's forward formula )n n f (x + h) = n=0 (h n! f ( x ) or h f (x + h) = n=0 n f (x) a Newton's backward formula
    1

    Numerical dierentiation
    This section discusses numerical methods for approximating the derivative(s) f(k)(x), k \ge 1 of a given function f(x). Start with Nweton's forward interpolation formula 1) 2 u2) 3 y = y0 + uy0 + u(u y0 + u(u1)( y0 + . . . 2! 3! xa whereu = h and dierentiate by u to get dy 2u1 2 3u2 6u+2 3 y0 + . . . du = y0 + 2! y0 + 3! 1 Then du = and we get dx h
    dy du 2u1 2 1 3u 6u+2 3 = du y0 + . . . dx = h y0 + 2! y0 + 3! For seond derivative we use dy dy du d2 y d 2u1 2 d 1 3u2 6u+2 3 = y0 + . . . 2 dx dx dx = du dx dx = h y0 + 2! y0 + 3! 1 2 3u 6u+2 3 y0 + 2u y0 + . . . 2! y0 + 3! Otherwise we can start from E = ehD or 1 + = ehD This gives 2 3 4 hD = log(1 + ) = 2 + 3 4 + ... so 2 1 3 4 D= h 2 + 3 4 + ... . Similarly 1 h2
    2

    dy dx

    1 h

    D2 = and D3 =

    1 h2 1 h3

    2 2

    3 3

    4 4

    + ...

    1 h2

    2 3 +

    11 4 12

    55 5 6

    + ...

    4 3 3 2 + . . .

    Maxima and minima of a tabulated functions


    Since maxima and minima of y = f(x) can be found by equating dy/x to zero and solving the equation for the argument x, the same method can be used to determine maxima and minima of tabulated function by dierentiating the interpolating polynomial. For example, if Newton's forward dierence formula is used, we have 1) 2 u2) 3 y0 + u(u1)( y0 + . . . y = y0 + uy0 + u(u 2! 3! Dierentiating with respect to u we get 2u1) 2 dy 3u2 6u+2 3 y0 + . . . du = y0 + 2! y0 + 3! Ignoring terms of order 3 or higher we get a quadratic equation which can be solved for extremum/

    Newton Cotes formulae


    Let the interval of integration (a, b) be divided into n equal sub-intervals, each of a width h = b n = so that x0 = a, x1 = x0 +h, x2 = x0 +2h, . . . , xn = x0 +nh = b. 2

    Consider b x +nh x=x0 +rh n I = a f (x)dx = x00 f (x) = h 0 f (x0 + rh)drf By Newton's forward interpolation formula n r +2) 3 +1) 2 y0 + r(r+1)( y0 + . . . dr I = h 0 y0 + ry0 + r(r2 3! so n 2 r3 r2 1 r4 3 2 I = h ry0 + r2 y0 + 1 2 y0 + 3! 3 y0 + . . . 2 3 2 4 r +r 0 giving nally 2 n(2n3) 2 2) I = nh y0 + n y0 + n(n24 3 y 0 + . . . . 2 y 0 + 12 For n = 1, 2, 3, 4 and 6 we get trapezoidal rule, Simpson's one-third and three-eighth rules, Boole rule and Weddle's rule respectively. n = 1 x +h h 1 I = x00 f (x) = h y0 + 1 2 y0 = 2 (2y0 + y1 y0 ) = 2 (y0 + y1 ) n=2 Simpson's one third x +2h 1 2 h I = x00 f (x) = 2h y0 + y0 + 6 y0 = 26 [6y0 + 6(y1 y0 ) + (y2 2y1 + y0 )] = h 2 (y0 + 4y1 + y2 ) n=3

    Euler-MacLaurin's formula
    Assume that the function f (x) is the dierence function of F (x) F (x) = f (x). Then F (x) = (E 1)1 f (x) = (ehD 1)1 f (x) = 1 1 1 ( x) = f (x) = hD 2 D2 3 D3 1+hD + h 2! + h 3! +... 1 hD h2 D2 1+ + + ... 2! 3! Now develop
    1 1+x

    = 1 x + x2 x3 + . . . so we get
    hD 2

    F (x) =
    1 1 hD

    D 1 h

    +
    3

    h2 D 2 12
    3

    h4 D 4 720

    + . . . f (x) =

    ...

    hD h D h 2 + 12 720 + . . . f (x) On the other hand, cancellation n1 n1 = F (xn ) F (x0 ) i=1 f (xi ) = i=1 [F (xi+1 ) F (xi )] so nally 1 h3 D 3 hD h3 D 3 1 1 1 1 F (xn )F (x0 ) = h D 2 + hD 1 12 720 + . . . f (xn ) h D 2 + 12 720 + . . . f (x0 ) = 1 h h3 1 xn h x0 f (x)dx 2 [f (xn ) f (x0 )]+ 12 [f (xn ) f (x0 )]+ 720 [f (xn ) f (x0 )]+

    Now nally xn n1 h2 h4 f (x)dx = h i=1 yi + h 2 (y0 + yn ) 12 (y n y 0 ) + 720 (yn y0 ) + . . . x0 which is exactly the trapezoidal rule. This formula is often used to nd the sum of a series of the form y (x0 ) + y (x0 + h) + y (x0 + 2h) + + y (x0 + nh).

    Predictor-Corrector Methods.
    Modied Euler's method
    The modied Euler's method of solving the initial value problem, y = f (x, y ), y (x0 ) = y0 In Euler's method we advance from point (x0 , y0 ) to (x1 , y1 ) where y1 = y0 + (x0 x1 )f (x0 , y0 ). We can improve by using not the slope at (x1 , y1 ), but the average of the slopes at (x0 , y0 ) and at (x1 , y1 ). p In order to prevent confusion we denote the result of the rst step as y1 , i.e. a predicted value. p y1 = y0 + (x0 x1 )f (x0 , y0 ) c Then we get the corrected or improved value y1 p x 0 x 1 c y1 = y0 + 2 [f (x0 , y0 ) + f (x1 , y1 )] This is a typical case of Predictor-Corrector Method.

    Milne's Predictor-Corrector Method


    We assume that we have equidistant points, so xi+1 xi = h. For each step we use 4 previous points. so assume we start with x0 ,x1 , x2 and x3 . We integrate the Newton's forward interpolation formula for y over the interval [x0 , x4 ] . x0 For convenience we denote x by u. h

    Predictor

    x +4h 4 y4 y0 = x00 y dx = h 0 y du = 4 u2) 3 1) 2 y0 + u(u1)( y0 + y0 + uy0 + u(u2 3! 0

    u(u1)(u2)(u3) 4 y0 4!

    + . . . du

    which gives 8 3 28 4 2 h y0 + 8y0 + 20 3 y0 + 3 y0 + 90 y0 + . . . which expressed by = E 1 operator gives 8 2 3 h y0 + 8(E 1)y0 + 20 3 (E 1) y0 + 3 (E 1) y0 + After expansion we get h 4 y4 y0 = 43 (2y1 y2 + 2y3 ) + 28 90 y0 + . . .

    28 90 (E

    1)4 y0 + . . .

    Corrector
    We integrate Newton's forward formula from x0 to x2 + 2h and we get h 4 y2 y0 = h 3 (y0 + 4y1 + y2 ) 90 y0 + . . . But we want to apply it from x2 to x4 +2h so the algorithm becomes: Assume y0 ,y1 ,y3 computed. Then, if we remember that yi = f (xi , yi ), we have h yp = y0 + 43 (2y1 y2 + 2y3 ) h yc = y2 + 3 (y2 + 4y3 + f (x4 , yp )) 4

    y4 = yc Test case y = x + y withy (0) = 1 from x = 0.20 to x = 0.30 with h = 0.05. The exact solution is y = 2ex x 1 (so we can use them as rst values)

    AdamsMoultonPredictor Formula
    Start with Newton's backward interpolation formula which is integrated from x0 to x0 + h for f (x, y ): 1 u+2) 3 +1) 2 f0 + u(u+1)( f0 + . . . du y1 = y0 + h 0 f0 + uf0 + u(u2 3! which results in 1 5 3 y1 = y0 + h f0 + 2 f0 + 12 2 f0 + 3 8 f0 + . . . du Now replacing f0 = f0 f1 2 f0 = f0 2f1 + f2 3 f0 = f0 3f1 + 3f2 f3 we get p h (55f0 59f1 + 37f2 9f3 ) y1 = y0 + 24 The correction goes with the same computation for y' h c y1 = y0 + 24 (55y0 59y1 + 37y2 9y3 )

    You might also like