Introduction
Among the multi-step methods which can be derived by integration of interpolating polynomials, we have (using fn to denote f(xn, yn)):
1. The midpoint method (second order):
2. Milne's Method (fourth order):
3. The family of Adams-Bashforth Methods, among which the second-order formula is given by:
and the fourth-order formula by:
4. The family of Adams-Moulton Methods, among which the second-order formula is given by:
,
often referred to as the trapezoidal method, and the fourth-order formula by:
.
Note that the family of Adams-Moulton methods requires evaluation of fn+1=f(xn+1,.yn+1). Because f(xn+1,.yn+1) is therefore involved on the left-hand as well as the right-hand sides of the expressions, such methods are known as implicit methods. On the other hand, since yn+1 appears only on the left-hand side in all the families listed under 1 - 3, they are called explicit methods. Implicit methods have the disadvantage that one usually requires some numerical technique (see STEP 7, STEP 8, STEP 9, STEP 10), in order to solve for yn+1. However, it is common to use explicit and implicit methods together and, thus, to produce a predictor-corrector method, an approach which is discussed in more advanced texts such as Mathews (1992).
We will not go into the various ways in which multi-step methods are used, but it is obvious that we will need more than one starting value, which may be obtained by first using a single-step method (cf the preceding Step). One advantage of a multi-step method is that we need to evaluate only once f(x, y) to obtain yn+1, since fn-1, fn-2, . . ., will already have been computed. In contrast, any Runge-Kutta method (i.e., single-step method) involves more than one function evaluation at each step, which in the case of complicated functions f (x, y) can be computationally expensive. Thus, the comparative efficiency of multi-step methods is often attractive, but such methods may be numerically unstable.
Stability
Numerical stability is discussed in depth in more advanced texts such as Burden and Faires (1993). In general, a method is unstable, if any errors introduced into the computation are amplified as computation progress. It turns out that the Adams-Bashforth and Adams-Moulton families of methods have good stability properties.
As an example of a multi-step method with poor stability properties, let us apply the mid-point method, given above, with h = 0.1 to the initial value problem for the differential equation y' = -5y, y(0) = 1. The correct solution to this problem is y(x) = e-5x. We will introduce an error by taking y1 to be the value obtained by rounding the true value e-0.5 to 5D, i.e., by setting y1 = 0.606 53. The resulting method is then given by:
.
Working to 5D, we construct the following table which allows us to compare the consequent estimates yn with the analytic values:
.
It is seen that the estimates get worse as n increases. Not only do the approximations alternate in sign after x6, but their magnitudes also grow. Further calculations shows that y20 has the value 77.824 55 with an error which is more than a million times larger than the analytic value!