| 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 $\textit{y′}$ = ƒ(y, t), and let the values $\textit{y′}(\textit{t}0)$ = $\textit{y}0′,$ $\textit{y′}(\textit{t}0$ + $\textit{h})$ = $\textit{y}1′,$ $\textit{y}(\textit{t}0)$ = $\textit{y}0,$ $\textit{y}(\textit{t}0$ + $\textit{h})$ = $\textit{y}1,$ be given. The general three-point predictor-corrector process consists of estimating (in some unspecified way) a value $\textit{y}2′$ of $\textit{y}2′$ computing a first estimate $\textit{y}2$ by means of a closed three-point integration formula; obtaining the (presumably) better value $\textit{y}2′$ = $ƒ(\textit{y}2,$ $\textit{t}0$ + $2\textit{h});$ and then repeating the process until some convergence criterion is satisfied, either for $\textit{y}2′$ or for $\textit{y}2.$ The process could have started by first estimating $\textit{y}2,$ rather than $\textit{y}2′.$ It is important to note that as long as the step size $\textit{h}$ and the first estimate $\textit{y}2′$ of $\textit{y}2′$ 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 $\textit{y}\textit{n}+1$ = $\textit{yn}$ + $\textit{h}/12[5ƒ(\textit{t}\textit{n}+1,$ $\textit{y}\textit{n}+1)$ + $8ƒ(\textit{tn},$ $\textit{yn})$ - $ƒ(\textit{t}\textit{n}-1,$ $\textit{yn}-1)].$ (1) $\textit{Tn},$ the single step truncation error, is given by $\textit{Tn}$ = - $\textit{h}4/24ƒ′′′(\textit{&xgr;}),$ $\textit{t}\textit{n}-1$ ≦ $\textit{&xgr;}$ ≦ $\textit{t}\textit{n}+1.$ The quantities $\textit{yn},$ $\textit{y}′\textit{n}+1,$ $\textit{y}\textit{n}′,$ $\textit{y}′\textit{n}-1$ are assumed exact. Let the initial conditions $\textit{y}0′,$ $\textit{y}0$ be specified for $\textit{y}′$ = ƒ(y, t). As a first approximation, let $\textit{y}(0)-1′$ = $\textit{y}0′,$ $\textit{y}(0)+1′$ = $\textit{y}0′,$ $\textit{y}(0)-1$ = $\textit{y}0,$ $\textit{y}(0)+1$ = $\textit{y}0.$ The superscript zero in parentheses indicates that these are the initial estimates of $\textit{y},$ $\textit{y}′.$ The starting procedure consists of performing corrective iterations in the forward (+1) and backward (-1) direction as follows: $\textit{y}(\textit{i})+1$ = $\textit{y}0$ + $\textit{h}/12[5ƒ(\textit{t}+1,$ $\textit{y}(\textit{i}-1)+1)$ + $8ƒ(\textit{t}0,$ $\textit{y}0)$ - $ƒ(\textit{t}-1,$ $\textit{y}(\textit{j})-1)],$ $\textit{y}(\textit{j})-1$ = $\textit{y}0$ - $\textit{h}/12[5ƒ(\textit{t}-1,$ $\textit{y}(\textit{j}-1)-1)$ + $8ƒ(\textit{t}0,$ $\textit{y}0)$ - $ƒ(\textit{t}+1,$ $\textit{y}(\textit{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 $\textit{y}+1$ be the value of $\textit{y}$ at $\textit{t}+1$ to which the iterative process converges (if at all). The error at the $\textit{i}th$ forward iteration is defined as $\textit{α}(\textit{i}),$ such that $\textit{y}(\textit{i})+1$ = $\textit{y}+1$ + $\textit{α}(\textit{i}).$ (3) The error in the backward direction is $\textit{β}(\textit{j}),$ such that $\textit{y}(\textit{j})-1$ = $\textit{y}-1$ + $\textit{β}(\textit{j}).$ (3′) Substituting the error definition into equation (2) yields $\textit{α}(\textit{i})$ = $5\textit{h}/12{ƒ[\textit{t}+1,$ $\textit{y}+1$ + $\textit{α}(\textit{i}-1)]$ - $ƒ[\textit{t}+1,$ $\textit{y}+1]}$ - $\textit{h}/12{ƒ[\textit{t}-1,$ $\textit{y}-1$ + $\textit{β}(\textit{i})]$ - $ƒ[\textit{t}-1,$ $\textit{y}-1]},$ (4) $\textit{β}(\textit{j})$ = - $5\textit{h}/12{ƒ[\textit{t}-1,$ $\textit{y}-1$ + $\textit{β}(\textit{i}-1)]$ - $ƒ[\textit{t}-1,$ $\textit{y}-1]}$ + $\textit{h}/12{ƒ[\textit{t}+1,$ $\textit{y}+1$ + $\textit{α}(\textit{i})]$ - $ƒ[\textit{t}+1,$ $\textit{y}+1]}.$ Let $\textit{g}+1$ = $∂ƒ[\textit{t}+1,$ $\textit{y}(\textit{t}0$ + $\textit{&xgr;}1)]/∂\textit{y},$ 0 ≦ $\textit{&xgr;}1$ ≦ $\textit{h},$ and (5) $\textit{g}-1$ = $∂ƒ[\textit{t}-1,$ $\textit{y}(\textit{t}0$ + $\textit{&xgr;}2)]/∂\textit{y},$ $-\textit{h}$ ≦ $\textit{&xgr;}2$ ≦ 0. Let it be assumed that $\textit{g}+1$ and $\textit{g}-1$ are insensitive to small changes in $\textit{&xgr;}1$ and $\textit{&xgr;}2;$ then, by the law of the mean, equations (4) can be written as $\textit{α}(\textit{i})$ = $5\textit{h}/12$ $\textit{g}+1\textit{α}(\textit{i}-1)$ - $\textit{h}/12$ $\textit{g}-1\textit{β}(\textit{j}),$ $\textit{β}(\textit{j})$ = $5\textit{h}/12$ $\textit{g}-1\textit{α}(\textit{j}-1)$ + $\textit{h}/12$ $\textit{g}+1\textit{α}(\textit{i}).$ (6) The order in which the iterations are performed may now be specified by letting $\textit{i}$ = $2\textit{k}$ + 3, $\textit{j}$ = $2\textit{k}$ + 2, $\textit{k}$ = -1, 0, 1, ···, ∞. Equations (6) can be reduced to a single equation in either $\textit{α}$ or $\textit{β}.$ Choosing $\textit{β}$ results in $\textit{β}(2\textit{k}+4)$ + $5\textit{h}/12$ $(\textit{g}-1$ - $\textit{g}+1)\textit{β}(2\textit{k}+2)$ - $24\textit{h}2/12$ $\textit{g}+1\textit{g}-1\textit{β}(2\textit{k})$ = 0. (7) The condition for convergence of the starting process is that $\textit{β}$ → 0 as $\textit{k}$ → ∞; i.e., that the roots of equations (7), when considered as a polynomial in $\textit{β}2,$ be less than one in magnitude. The conditions for convergence are then ‖- $5\textit{h}/12$ $(\textit{g}+1$ - $\textit{g}-1)$ ± $\textit{h}/12$ $√[5(\textit{g}+1$ - $\textit{g}-1]2$ - $4\textit{g}+1\textit{g}-1‖$ < 1. (8) Choosing $\textit{α}$ instead of $\textit{β}$ yields the same result. The condition for the convergence of the usual predictor-corrector process, in which $\textit{y}-1$ and $\textit{y}0$ are given, is $‖5\textit{h}/12\textit{g}1‖$ < 1. (9) Conditions (8) are quite similar to condition (9). As can be seen, convergence can always be obtained for sufficiently small values of $\textit{h}.To$ say that the starting process gives values $\textit{y}+1,$ and $\textit{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 $\textit{y}-1$ and $\textit{y}0$ be given exactly, and let $\textit{y}+1$ be the value to which successive forward iterations converge. If $\textit{y}+1$ is the true value of $\textit{y}$ at $\textit{t}+1,$ the error ε1 is then defined as $\textit{y}+1$ = $\textit{y}+1$ + ε1, (10) By definition, $\textit{y}+1$ satisfies $\textit{y}+1$ = $\textit{y}0$ + $\textit{h}/12$ $[5ƒ(\textit{t}+1,$ $\textit{y}+1)$ + $8ƒ(\textit{t}0,$ $\textit{y}0)$ - $ƒ(\textit{t}-1,$ $\textit{y}-1)].$ (11) It is known that $\textit{y}+1$ = $\textit{y}0$ + $\textit{h}/12$ $[5ƒ(\textit{t}+1,$ $\textit{y}+1)$ + $8ƒ(\textit{t}0,$ $\textit{y}0)$ - $ƒ(\textit{t}-1,$ $\textit{y}-1)]$ + $\textit{T}1,$ (1′) where $\textit{T}1$ is the truncation error.From equations (1), (10) and (11), and by the law of the mean, it can be stated that ε1 = $-\textit{T}1$ + $\textit{h}/12{5ε1$ $∂ƒ/∂\textit{y}$ $[\textit{t}+1,$ $\textit{y}(\textit{t}0$ + $\textit{&xgr;}1)]},$ 0 ≦ $\textit{&xgr;}1$ ≦ $\textit{h}.$ (12) By defining $\textit{γ}1$ = $\textit{h}/12$ $∂ƒ/∂\textit{y}$ $[\textit{t}+1,$ $\textit{y}(\textit{t}0$ + $\textit{&xgr;}1)],$ (13) the error equation becomes ε1 = $-\textit{T}1/1$ - $5\textit{γ}1.$ (14) The quantity $\textit{γ}1$ may be estimated, since $\textit{γ}1$ = $\textit{h}/12$ $ƒ[\textit{t}+1,$ $\textit{y}(\textit{i})+1]$ - $ƒ[\textit{t}+1,$ $\textit{y}(\textit{i}-1)+1]/\textit{y}(\textit{i})+1$ - $\textit{y}(\textit{i}-1)+1;$ (15) the superscript again refer to iterations. As a rule, the step size $\textit{h}$ is chosen so as to make $\textit{γ}1$ small compared to one.A similar analysis for the proposed starting process yields ε1 = $-\textit{T}1$ - $\textit{γ}-1(5\textit{T}1$ - $\textit{T}-1)/1$ - $5\textit{γ}1$ + $5\textit{γ}1$ - $24\textit{γ}1\textit{γ}-1.$ (16) The difference between the error of equation (14) and that of equation (16) is Δ = $\textit{γ}-1\textit{T}-1$ - $5\textit{γ}1\textit{T}1$ - $24\textit{γ}1\textit{γ}-1\textit{T}1/(1$ - $5\textit{γ}1)(1$ + $5\textit{γ}-1)$ + $\textit{γ}1\textit{γ}-1.$ (17) This equation may be simplified by considering a worst possible case, in which $\textit{T}-1$ and $\textit{T}1$ are replaced by some maximum $\textit{T}$ and $\textit{γ}-1$ and $\textit{γ}1$ by some maximum $\textit{γ},$ and the signs adjusted. This yields $‖Δ‖≦‖\textit{γ}(6$ + $\textit{γ})/1$ - $26\textit{γ}2\textit{T}‖.$ (18) Thus, if $\textit{γ}$ is of the order of 10-2, the difference Δ is less than seven percent of the single step truncation error. In general, if the step size $\textit{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 $\textit{y}\textit{n}+1$ if $\textit{y}′\textit{n}+1,$ $\textit{y}\textit{n}′,$ and $\textit{y}\textit{n}-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. |
