Tuesday, February 2, 2010

Runge-Kutta-Fehlberg Method

One way to guarantee accuracy in the solution of an I.V.P. is to solve the problem twice using step sizes h and[Graphics:Images/RungeKuttaFehlbergMod_gr_1.gif] and compare answers at the mesh points corresponding to the larger step size. But this requires a significant amount of computation for the smaller step size and must be repeated if it is determined that the agreement is not good enough. The Runge-Kutta-Fehlberg method (denoted RKF45) is one way to try to resolve this problem. It has a procedure to determine if the proper step size h is being used. At each step, two different approximations for the solution are made and compared. If the two answers are in close agreement, the approximation is accepted. If the two answers do not agree to a specified accuracy, the step size is reduced. If the answers agree to more significant digits than required, the step size is increased.

Each Runge-Kutta-Fehlberg step requires the use of the following six values:

[Graphics:Images/RungeKuttaFehlbergMod_gr_2.gif]

Then an approximation to the solution of the I.V.P. is made using a Runge-Kutta method of order 4:

[Graphics:Images/RungeKuttaFehlbergMod_gr_3.gif]

And a better value for the solution is determined using a Runge-Kutta method of order 5:

[Graphics:Images/RungeKuttaFehlbergMod_gr_4.gif]

The optimal step size
sh can be determined by multiplying the scalar s times the current step size h. The scalar s is

[Graphics:Images/RungeKuttaFehlbergMod_gr_5.gif]

where
[Graphics:Images/RungeKuttaFehlbergMod_gr_6.gif] is the specified error control tolerance.

Adams-Bashforth-Moulton Method

The methods of Euler, Heun, Taylor and Runge-Kutta are called single-step methods because they use only the information from one previous point to compute the successive point, that is, only the initial point [Graphics:Images/AdamsBashforthMod_gr_1.gif] is used to compute [Graphics:Images/AdamsBashforthMod_gr_2.gif] and in general [Graphics:Images/AdamsBashforthMod_gr_3.gif] is needed to compute [Graphics:Images/AdamsBashforthMod_gr_4.gif]. After several points have been found it is feasible to use several prior points in the calculation. The Adams-Bashforth-Moulton method uses [Graphics:Images/AdamsBashforthMod_gr_5.gif] in the calculation of [Graphics:Images/AdamsBashforthMod_gr_6.gif]. This method is not self-starting; four initial points [Graphics:Images/AdamsBashforthMod_gr_7.gif], [Graphics:Images/AdamsBashforthMod_gr_8.gif], [Graphics:Images/AdamsBashforthMod_gr_9.gif], and [Graphics:Images/AdamsBashforthMod_gr_10.gif] must be given in advance in order to generate the points [Graphics:Images/AdamsBashforthMod_gr_11.gif].

A desirable feature of a multistep method is that the local truncation error (L. T. E.) can be determined and a correction term can be included, which improves the accuracy of the answer at each step. Also, it is possible to determine if the step size is small enough to obtain an accurate value for [Graphics:Images/AdamsBashforthMod_gr_12.gif], yet large enough so that unnecessary and time-consuming calculations are eliminated. If the code for the subroutine is fine-tuned, then the combination of a predictor and corrector requires only two function evaluations of f(t,y) per step.

Adams-Bashforth-MoultonMethod:

Assume that f(t,y) is continuous and satisfies a Lipschits condition in the variable y, and consider the I. V. P. (initial value problem)

[Graphics:Images/AdamsBashforthMod_gr_13.gif] with [Graphics:Images/AdamsBashforthMod_gr_14.gif], over the interval [Graphics:Images/AdamsBashforthMod_gr_15.gif].

The Adams-Bashforth-Moulton method uses the formulas [Graphics:Images/AdamsBashforthMod_gr_16.gif], and

the predictor [Graphics:Images/AdamsBashforthMod_gr_17.gif], and

the corrector [Graphics:Images/AdamsBashforthMod_gr_18.gif] for [Graphics:Images/AdamsBashforthMod_gr_19.gif]

as an approximate solution to the differential equation using the discrete set of points [Graphics:Images/AdamsBashforthMod_gr_20.gif].

Remark: The Adams-Bashforth-Moulton method is not a self-starting method. Three additional starting values [Graphics:Images/AdamsBashforthMod_gr_21.gif] must be given. They are usually computed using the Runge-Kutta method.

Precision of Adams-Bashforth-MoultonMethod: Assume that [Graphics:Images/AdamsBashforthMod_gr_22.gif] is the solution to the I.V.P. [Graphics:Images/AdamsBashforthMod_gr_23.gif] with [Graphics:Images/AdamsBashforthMod_gr_24.gif]. If [Graphics:Images/AdamsBashforthMod_gr_25.gif] and [Graphics:Images/AdamsBashforthMod_gr_26.gif] is the sequence of approximations generated by Adams-Bashforth-Moulton method, then at each step, the local truncation error is of the order [Graphics:Images/AdamsBashforthMod_gr_27.gif], and the overall global truncation error [Graphics:Images/AdamsBashforthMod_gr_28.gif] is of the order

[Graphics:Images/AdamsBashforthMod_gr_29.gif], for [Graphics:Images/AdamsBashforthMod_gr_30.gif].


The error at the right end of the interval is called the final global error

[Graphics:Images/AdamsBashforthMod_gr_31.gif].


Adams-Bashforth-Moulton Method:

To approximate the solution of the initial value problem [Graphics:Images/AdamsBashforthMod_gr_32.gif] with [Graphics:Images/AdamsBashforthMod_gr_33.gif] over [Graphics:Images/AdamsBashforthMod_gr_34.gif] at a discrete set of points using the formulas:

use the predictor [Graphics:Images/AdamsBashforthMod_gr_35.gif]

and the corrector [Graphics:Images/AdamsBashforthMod_gr_36.gif] for [Graphics:Images/AdamsBashforthMod_gr_37.gif].

Milne-Simpson's Method

The methods of Euler, Heun, Taylor and Runge-Kutta are called single-step methods because they use only the information from one previous point to compute the successive point, that is, only the initial point [Graphics:Images/MilneSimpsonMod_gr_1.gif] is used to compute [Graphics:Images/MilneSimpsonMod_gr_2.gif] and in general [Graphics:Images/MilneSimpsonMod_gr_3.gif] is needed to compute [Graphics:Images/MilneSimpsonMod_gr_4.gif]. After several points have been found it is feasible to use several prior points in the calculation. The Milne-Simpson method uses [Graphics:Images/MilneSimpsonMod_gr_5.gif] in the calculation of [Graphics:Images/MilneSimpsonMod_gr_6.gif]. This method is not self-starting; four initial points [Graphics:Images/MilneSimpsonMod_gr_7.gif], [Graphics:Images/MilneSimpsonMod_gr_8.gif], [Graphics:Images/MilneSimpsonMod_gr_9.gif], and [Graphics:Images/MilneSimpsonMod_gr_10.gif] must be given in advance in order to generate the points [Graphics:Images/MilneSimpsonMod_gr_11.gif].

A desirable feature of a multistep method is that the local truncation error (L. T. E.) can be determined and a correction term can be included, which improves the accuracy of the answer at each step. Also, it is possible to determine if the step size is small enough to obtain an accurate value for [Graphics:Images/MilneSimpsonMod_gr_12.gif], yet large enough so that unnecessary and time-consuming calculations are eliminated. If the code for the subroutine is fine-tuned, then the combination of a predictor and corrector requires only two function evaluations of f(t,y) per step.

Theorem (Milne-Simpson's Method:

Assume that f(t,y) is continuous and satisfies a Lipschits condition in the variable y, and consider the I. V. P. (initial value problem)

[Graphics:Images/MilneSimpsonMod_gr_13.gif] with [Graphics:Images/MilneSimpsonMod_gr_14.gif], over the interval [Graphics:Images/MilneSimpsonMod_gr_15.gif].

The Milne-Simpson method uses the formulas [Graphics:Images/MilneSimpsonMod_gr_16.gif], and

the predictor [Graphics:Images/MilneSimpsonMod_gr_17.gif], and

the corrector [Graphics:Images/MilneSimpsonMod_gr_18.gif] for [Graphics:Images/MilneSimpsonMod_gr_19.gif]

as an approximate solution to the differential equation using the discrete set of points [Graphics:Images/MilneSimpsonMod_gr_20.gif].

Remark: The Milne-Simpson method is not a self-starting method. Three additional starting values [Graphics:Images/MilneSimpsonMod_gr_21.gif] must be given. They are usually computed using the Runge-Kutta method.


Theorem (Precision of the Milne-Simpson Method:

Assume that [Graphics:Images/MilneSimpsonMod_gr_22.gif] is the solution to the I.V.P. [Graphics:Images/MilneSimpsonMod_gr_23.gif] with [Graphics:Images/MilneSimpsonMod_gr_24.gif]. If [Graphics:Images/MilneSimpsonMod_gr_25.gif] and [Graphics:Images/MilneSimpsonMod_gr_26.gif] is the sequence of approximations generated by Milne-Simpson method, then at each step, the local truncation error is of the order [Graphics:Images/MilneSimpsonMod_gr_27.gif], and the overall global truncation error [Graphics:Images/MilneSimpsonMod_gr_28.gif] is of the order

[Graphics:Images/MilneSimpsonMod_gr_29.gif], for [Graphics:Images/MilneSimpsonMod_gr_30.gif].


The error at the right end of the interval is called the final global error

[Graphics:Images/MilneSimpsonMod_gr_31.gif].

Introductory Methods of Numerical Analysis