Author | Alonso, R. |
Source | ACM Digital Library |
Content type | Text |
Publisher | Association for Computing Machinery (ACM) |
File Format | |
Copyright Year | ©1960 |
Language | English |
Subject Domain (in DDC) | Computer science, information & general works ♦ Data processing & computer science |
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. |
ISSN | 00045411 |
Age Range | 18 to 22 years ♦ above 22 year |
Educational Use | Research |
Education Level | UG and PG |
Learning Resource Type | Article |
Publisher Date | 1960-04-01 |
Publisher Place | New York |
e-ISSN | 1557735X |
Journal | Journal of the ACM (JACM) |
Volume Number | 7 |
Issue Number | 2 |
Page Count | 5 |
Starting Page | 176 |
Ending Page | 180 |
Ministry of Human Resource Development (MHRD) under its National Mission on Education through Information and Communication Technology (NMEICT) has initiated the National Digital Library of India (NDLI) project to develop a framework of virtual repository of learning resources with a single-window search facility. Filtered and federated searching is employed to facilitate focused searching so that learners can find out the right resource with least effort and in minimum time. NDLI is designed to hold content of any language and provides interface support for leading vernacular languages, (currently Hindi, Bengali and several other languages are available). It is designed to provide support for all academic levels including researchers and life-long learners, all disciplines, all popular forms of access devices and differently-abled learners. It is being developed to help students to prepare for entrance and competitive examinations, to enable people to learn and prepare from best practices from all over the world and to facilitate researchers to perform inter-linked exploration from multiple sources. It is being developed at Indian Institute of Technology Kharagpur.
NDLI is a conglomeration of freely available or institutionally contributed or donated or publisher managed contents. Almost all these contents are hosted and accessed from respective sources. The responsibility for authenticity, relevance, completeness, accuracy, reliability and suitability of these contents rests with the respective organization and NDLI has no responsibility or liability for these. Every effort is made to keep the NDLI portal up and running smoothly unless there are some unavoidable technical issues.
Ministry of Human Resource Development (MHRD), through its National Mission on Education through Information and Communication Technology (NMEICT), has sponsored and funded the National Digital Library of India (NDLI) project.
Phone: +91-3222-282435
For any issue or feedback, please write to ndl-support@iitkgp.ac.in