A Starting Method for the Three-Point Adams Predictor-Corrector Method

ABSTRACT

Certain higher order iterative procedures for the numerical solution of ordinary differential equations require a separate procedure for determining starting values. Such is the case in the Adams and Milne methods. The work involved in programming the computation of starting values may be of the same magnitude as that required in programming the method itself. This paper shows that the three-point Adams formula leads to a method which may be considered “self-starting” in the sense that very minor modifications of the method provide starting values of sufficient accuracy for continuing the solution. Let the equation under solution be y′ = ƒ(y, t), and let the values y′(t0) = y0′, y′(t0 + h) = y1′, y(t0) = y0, y(t0 + h) = y1, be given. The general three-point predictor-corrector process consists of estimating (in some unspecified way) a value y2′ of y2′ computing a first estimate y2 by means of a closed three-point integration formula; obtaining the (presumably) better value y2′ = ƒ(y2, t0 + 2h); and then repeating the process until some convergence criterion is satisfied, either for y2′ or for y2. The process could have started by first estimating y2, rather than y2′. It is important to note that as long as the step size h and the first estimate y2′ of y2′ result in a converging process, the values to which there is convergence are independent of the method of prediction. The Adams three-point formula is yn+1 = yn + h/12[5ƒ(tn+1, yn+1) + 8ƒ(tn, yn) - ƒ(tn-1, yn-1)]. (1) Tn, the single step truncation error, is given by Tn = - h4/24ƒ′′′(&xgr;), tn-1 ≦ &xgr; ≦ tn+1. The quantities yn, y′n+1, yn′, y′n-1 are assumed exact. Let the initial conditions y0′, y0 be specified for y′ = ƒ(y, t). As a first approximation, let y(0)-1′ = y0′, y(0)+1′ = y0′, y(0)-1 = y0, y(0)+1 = y0. The superscript zero in parentheses indicates that these are the initial estimates of y, y′. The starting procedure consists of performing corrective iterations in the forward (+1) and backward (-1) direction as follows: y(i)+1 = y0 + h/12[5ƒ(t+1, y(i-1)+1) + 8ƒ(t0, y0) - ƒ(t-1, y(j)-1)], y(j)-1 = y0 - h/12[5ƒ(t-1, y(j-1)-1) + 8ƒ(t0, y0) - ƒ(t+1, y(i)+1)]. (2) The superscript notation employed does not imply any order to the forward and backward iterations. In the following analysis, however, it will be assumed that the process starts with a forward iteration, and alternates thereafter. It is necessary to show the conditions under which the process converges and the conditions under which the resulting values are accurate enough to warrant continuing the solution by the Adams method. Let y+1 be the value of y at t+1 to which the iterative process converges (if at all). The error at the ith forward iteration is defined as &agr;(i), such that y(i)+1 = y+1 + &agr;(i). (3) The error in the backward direction is &bgr;(j), such that y(j)-1 = y-1 + &bgr;(j). (3′) Substituting the error definition into equation (2) yields &agr;(i) = 5h/12{ƒ[t+1, y+1 + &agr;(i-1)] - ƒ[t+1, y+1]} - h/12{ƒ[t-1, y-1 + &bgr;(i)] - ƒ[t-1, y-1]}, (4) &bgr;(j) = - 5h/12{ƒ[t-1, y-1 + &bgr;(i-1)] - ƒ[t-1, y-1]} + h/12{ƒ[t+1, y+1 + &agr;(i)] - ƒ[t+1, y+1]}. Let g+1 = ∂ƒ[t+1, y(t0 + &xgr;1)]/∂y, 0 ≦ &xgr;1 ≦ h, and (5) g-1 = ∂ƒ[t-1, y(t0 + &xgr;2)]/∂y, -h ≦ &xgr;2 ≦ 0. Let it be assumed that g+1 and g-1 are insensitive to small changes in &xgr;1 and &xgr;2; then, by the law of the mean, equations (4) can be written as &agr;(i) = 5h/12 g+1&agr;(i-1) - h/12 g-1&bgr;(j), &bgr;(j) = 5h/12 g-1&agr;(j-1) + h/12 g+1&agr;(i). (6) The order in which the iterations are performed may now be specified by letting i = 2k + 3, j = 2k + 2, k = -1, 0, 1, ···, ∞. Equations (6) can be reduced to a single equation in either &agr; or &bgr;. Choosing &bgr; results in &bgr;(2k+4) + 5h/12 (g-1 - g+1)&bgr;(2k+2) - 24h2/12 g+1g-1&bgr;(2k) = 0. (7) The condition for convergence of the starting process is that &bgr; → 0 as k → ∞; i.e., that the roots of equations (7), when considered as a polynomial in &bgr;2, be less than one in magnitude. The conditions for convergence are then ‖- 5h/12 (g+1 - g-1) ± h/12 √[5(g+1 - g-1]2 - 4g+1g-1‖ < 1. (8) Choosing &agr; instead of &bgr; yields the same result. The condition for the convergence of the usual predictor-corrector process, in which y-1 and y0 are given, is ‖5h/12g1‖ < 1. (9) Conditions (8) are quite similar to condition (9). As can be seen, convergence can always be obtained for sufficiently small values of h. To say that the starting process gives values y+1, and y-1 of sufficient accuracy to warrant the further use of the normal Adams procedure implies that the error introduced by the former is not significantly larger than the error introduced by a single step of the latter. Let y-1 and y0 be given exactly, and let y+1 be the value to which successive forward iterations converge. If y+1 is the true value of y at t+1, the error &egr;1 is then defined as y+1 = y+1 + &egr;1, (10) By definition, y+1 satisfies y+1 = y0 + h/12 [5ƒ(t+1, y+1) + 8ƒ(t0, y0) - ƒ(t-1, y-1)]. (11) It is known that y+1 = y0 + h/12 [5ƒ(t+1, y+1) + 8ƒ(t0, y0) - ƒ(t-1, y-1)] + T1, (1′) where T1 is the truncation error. From equations (1), (10) and (11), and by the law of the mean, it can be stated that &egr;1 = -T1 + h/12{5&egr;1 ∂ƒ/∂y [t+1, y(t0 + &xgr;1)]}, 0 ≦ &xgr;1 ≦ h. (12) By defining &ggr;1 = h/12 ∂ƒ/∂y [t+1, y(t0 + &xgr;1)], (13) the error equation becomes &egr;1 = -T1/1 - 5&ggr;1. (14) The quantity &ggr;1 may be estimated, since &ggr;1 = h/12 ƒ[t+1, y(i)+1] - ƒ[t+1, y(i-1)+1]/y(i)+1 - y(i-1)+1; (15) the superscript again refer to iterations. As a rule, the step size h is chosen so as to make &ggr;1 small compared to one. A similar analysis for the proposed starting process yields &egr;1 = -T1 - &ggr;-1(5T1 - T-1)/1 - 5&ggr;1 + 5&ggr;1 - 24&ggr;1&ggr;-1. (16) The difference between the error of equation (14) and that of equation (16) is &Dgr; = &ggr;-1T-1 - 5&ggr;1T1 - 24&ggr;1&ggr;-1T1/(1 - 5&ggr;1)(1 + 5&ggr;-1) + &ggr;1&ggr;-1. (17) This equation may be simplified by considering a worst possible case, in which T-1 and T1 are replaced by some maximum T and &ggr;-1 and &ggr;1 by some maximum &ggr;, and the signs adjusted. This yields ‖&Dgr;‖≦‖&ggr;(6 + &ggr;)/1 - 26&ggr;2T‖. (18) Thus, if &ggr; is of the order of 10-2, the difference &Dgr; is less than seven percent of the single step truncation error. In general, if the step size h is chosen so that the error introduced by a single step of the iterative procedure is of the order of magnitude of the single step truncation error (which is the error in yn+1 if y′n+1, yn′, and yn-1 are known exactly), then the proposed procedure results in starting values of sufficient accuracy to warrant continuing the solution by means of the three-point Adams method.

REFERENCES

• 1: RA~6N ALONSO, A special purpose digital calculator for the numerical solution of ordinary differential equations, Harvard University, 1957.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Performance, Theory