Author | Carr, John W. |
Source | ACM Digital Library |
Content type | Text |
Publisher | Association for Computing Machinery (ACM) |
File Format | |
Copyright Year | ©1958 |
Language | English |
Subject Domain (in DDC) | Computer science, information & general works ♦ Data processing & computer science |
Abstract | Although numerous writers have stated that the class of single-step (“Runge-Kutta”—like) methods of numerical integration of ordinary differential equations are stable under calculational or round-off error, no one has given formal equations for the bounds on the propagated error to indicate this stability. Rutishauser [1] justifies the stability by noting that there is only one solution to the approximating difference equation, and Hildebrand [2] calculates a propagated error bound for the simplest (Euler) case. However, the latter bound does not indicate the stability for even that case.It is the purpose of this paper to investigate this “stability” of the Kutta fourth order procedure for integration of the ordinary differential equation $\textit{dy}/\textit{dx}$ = ƒ(x, y), (1) where ƒ(x, y) possesses a continuous first-order partial derivative with respect to $\textit{y}$ throughout a region $\textit{D}$ in which the integration is to take place. (By alteration of the proof below, this condition can be replaced by a Lipschitz condition.) Since the Kutta process is the most complicated of such single-step procedures, it should be apparent that similar error bounds can be derived for the various other single-step methods of same or lower order (and in particular the Gill variant method, probably most often used in machine integration because of the storage savings). It is plausible that such error bounds can also be extended to the stable (extrapolation) multi-step methods, such as the Adams method, and to systems of ordinary differential equations. If the variational equation $\textit{d}&eegr;/\textit{dx}$ = ∂ƒ(x, $y})/∂\textit{y}$ &eegr; (2) for the above ordinary differential equation has $ƒ\textit{v}(\textit{x,$ y) < 0 throughout a region $\textit{D}$ the ordinary differential equation is termed $\textit{stable}$ in $\textit{D},$ and for small enough variations in the initial conditions the absolute value of the propagated error decreases with growing $\textit{x}.Todd$ [3], Milne [4], Rutishauser [1], and others have shown that numerous multi-step numerical integration techniques are unstable in that even when the differential equation is stable, the difference equation will introduce spurious solutions for $\textit{any}$ step-size $\textit{h}.$ For the Kutta fourth order process, as seen below, this is not the case; for the stable differential equation the propagated error in the difference approximation remains bounded for small enough (but not too small!) step-size $\textit{h};$ and for a given value of $\textit{x},$ bounds on the propagated error decrease to a minimum given as a function of the round-off error as the step-size is decreased. Similar statements can be proved (but are not proved here) for other single-step processes. For no round-off (an “infinite word-length machine”) the process converges as $\textit{h}$ goes to zero.In addition, an algorithm for determining the step-size as a function of the partial derivative is given below so as to keep the propagated error within a given bound. The classical Kutta procedure [5] gives the value of $\textit{y}$ at the $(\textit{i}$ + 1)th step in terms of the value at the $\textit{i}th$ step and the step-size $\textit{h}$ as follows: $\textit{y}\textit{i}+1$ = $\textit{y}\textit{i}$ + $\textit{h}/6(\textit{k}1$ + $2\textit{k}2$ + $2\textit{k}3$ + $\textit{k}4)$ + $\textit{O}(\textit{h}5)$ $\textit{k}1$ = $ƒ(\textit{x}\textit{i},$ $\textit{y}\textit{i})$ $\textit{k}2$ = $ƒ(\textit{x}\textit{i}$ + $\textit{h}/2,$ $\textit{y}\textit{i}$ + $\textit{k}1\textit{h}/2)$ $\textit{k}3$ = $ƒ(\textit{x}\textit{i}$ + $\textit{h}/2,$ $\textit{y}\textit{i}$ + $\textit{k}2\textit{h}/2)$ $\textit{k}4$ = $ƒ(\textit{x}\textit{i}$ + h, $y}\textit{i}$ + $\textit{k}3\textit{h})$ (3) When the $\textit{O}(\textit{h}5)$ term is neglected, the value of $\textit{y}\textit{i}+1,$ here called $\textit{y}\textit{t}\textit{i}+1,$ is only an approximation. An error bound for the truncation error at each step is given by Bieberbach [6, 7] and Lotkin [8]. This guarantees that for $\textit{h}$ small enough the truncation error at a single step, starting at $\textit{y}\textit{i},$ will be bounded by $|\textit{y}\textit{i}+1$ - $\textit{y}\textit{t}\textit{i}+1|$ ≦ $\textit{C}\textit{i}+1\textit{h}5,$ (4) where $\textit{C}\textit{i}+1$ ≧ 0 is a function only of $\textit{i},$ the function ƒ(x, y), and its partial derivatives of the first three orders; and $\textit{y}\textit{t}\textit{i}$ is the true solution to the equations (3) truncated so that the $\textit{O}(\textit{h}5)$ term does not appear. If the function and its derivaties of the first three orders exist and are bounded throughout a region, then all $\textit{C}\textit{i}$ would be bounded in the region. Suppose there exists an error ε1 in $\textit{y}\textit{i}$ at the $\textit{i}th$ step, which might be due either to previous truncation or round-off error. Then the calculated value $\textit{y}*\textit{i}+1$ (as opposed to the true value if $ε\textit{i}$ were zero) at the next step is given, after several applications of the mean value theorem, by $\textit{y}*\textit{i}+1$ = $\textit{y}\textit{i}$ + $ε\textit{i}$ + $\textit{h}/6{\textit{k}1$ + $∂ƒ/∂\textit{y}$ $ε\textit{i}$ + $2\textit{k}2$ + $2[∂ƒ/∂\textit{y}$ + $(∂ƒ/∂\textit{y})2$ $\textit{h}/2]ε\textit{i}$ + $2\textit{k}3$ + $2[∂ƒ/∂\textit{y}(1$ + $∂ƒ/∂\textit{y}$ $\textit{h}/2(1$ + $∂ƒ/∂\textit{y}$ $\textit{h}/2))]ε\textit{i}$ + $\textit{k}4$ + $[∂ƒ/∂\textit{y}(1$ + $∂ƒ/∂\textit{y}$ $\textit{h}(1$ + $∂ƒ/∂\textit{y}$ $\textit{h}/2(1$ + $∂ƒ/∂\textit{y}$ $\textit{h}/2)))]ε\textit{i}}$ (5) where the various partial derivatives are evaluated within a rectangle given by $\textit{x}\textit{i}$ ≦ $\textit{x}$ ≦ $\textit{x}\textit{i}$ + $\textit{h};$ $|\textit{y}\textit{i}$ - $\textit{y}|$ ≦ $\textit{Qh}$ + | $ε\textit{i}$ | where $\textit{Q}$ is given below. Consider the true solution $\textit{y}\textit{i}\textit{t}$ to the difference equation. During its evaluation, in order that all values of ƒ(x, y) used in its calculation lie within a region $\textit{D},$ the true solution should not approach the $\textit{y}-boundaries$ of $\textit{D}$ closer than | $\textit{y}\textit{i}\textit{t};$ - $\textit{y}|$ > $\textit{Qh},$ where if $\textit{Q}$ is chosen as $\textit{Q}$ ≧ $max\textit{x,y}ε\textit{D}$ | ƒ(x, y) | ≧ max (| $\textit{k}1/2$ |, | $\textit{k}2/2$ |, | $\textit{k}3$ |) then certainly only values within $\textit{D}$ will be involved in the calculations.The same argument holds for the difference equation containing error $ε\textit{i}$ at any step. If such a solution does not approach within closer than $\textit{Qh}$ + | $ε\textit{i}$ | to the $\textit{y}-boundary$ of $\textit{D}$ (such a region will be called $\textit{D}*$ below), then the true solution will not approach closer than $\textit{Qh}$ to the boundary. In the latter case the rectangle within which the partial derivatives are to be evaluated will always be within the given region $\textit{D}.$ This gives for the propagated error at the $(\textit{i}$ + 1)th step (if $\textit{y}\textit{i}+1$ is the value at step $\textit{i}$ + 1 given no error at step $\textit{i},$ and $\textit{y}*\textit{i}+1$ is the value at step $\textit{i}$ + 1 with error $ε\textit{i}$ present): $&eegr;\textit{i}+1$ = $\textit{y}*\textit{i}+1$ - $\textit{y}\textit{i}+1$ = $ε\textit{i}[1$ + $\textit{h}/6(∂ƒ/∂\textit{y}$ + $2∂ƒ/∂\textit{y}$ + $2∂ƒ/∂\textit{y}$ + $∂ƒ/∂\textit{y})$ + $\textit{h}2/6(∂ƒ/∂\textit{y}$ $∂ƒ/∂\textit{y}$ + $∂ƒ/∂\textit{y}$ $∂ƒ/∂\textit{y}$ + $∂ƒ/∂\textit{y}$ $∂ƒ/∂\textit{y})$ + $\textit{h}3/12(∂ƒ/∂\textit{y}$ $∂ƒ/∂\textit{y}$ $∂ƒ/∂\textit{y}$ + $∂ƒ/∂\textit{y}$ $∂ƒ/∂\textit{y}$ $∂ƒ/∂\textit{y})$ + $\textit{h}4/24(∂ƒ/∂\textit{y}$ $∂fnof;/∂\textit{y}$ $∂ƒ/∂\textit{y}$ $∂ƒ/∂\textit{y})]$ (6) where the partial derivaties are written out to indicate that each is evaluated at what may be a different point in the rectangle. One can now prove the following: THEOREM: $\textit{If}$ ∂ƒ/∂y is continuous, negative, and bounded from above and below throughout a region D in $the}(\textit{x,$ y) $\textit{plane,}$ $-\textit{M}2$ < $∂ƒ/∂\textit{y}$ < $-\textit{M}1$ < 0, where $\textit{M}2$ > $\textit{M}1$ < 0, then for a maximum error (truncation, or round-off, or both) E in absolute value at each step the Kutta fourth-order numerical integration procedure has total error at the i-th step, i arbitrary, in the region D*, of | $ε\textit{i}$ | ≦ $2\textit{E}/\textit{hM}1$ (7) where the step-size h is taken to be h < min $(\textit{M}1/\textit{M}22,$ $4\textit{M}13/\textit{M}24.$ (Obviously if $\textit{D}$ extends to infinity, the boundaries of $\textit{D}$ and $\textit{D}*$ will coincide at infinity. Better (but more complex) bounds could certainly be obtained on $\textit{Q}$ and therefore $\textit{D}*.)$ PROOF: For $\textit{h}$ as given, the multiplier of | $ε\textit{i}$ | within the absolute value signs on the right-hand side of (8) below is positive and the inequality does indeed hold, by applying the bounds on $ƒ\textit{v}$ of the theorem to (6) above.In fact, for $\textit{h}$ as given $&eegr;\textit{i}+1$ | = | $\textit{y}*\textit{i}+1$ - $\textit{y}\textit{i}+1$ | ≦ | $ε\textit{i}$ | | 1 - $\textit{hM}1$ + $(\textit{hM}2)2/2!$ - $(\textit{hM}1)3/3!$ + $(\textit{hM}2)4/4!|$ ≦ | $ε\textit{i}|$ |1 - $\textit{hM}1/2|.$ (8) The total error at the $(\textit{i}$ + 1)th step is, in absolute value, | $ε\textit{i}+1|$ = $|&rgr;\textit{i}+1|$ + $|&eegr;\textit{i}+1|$ ≦ $\textit{E}$ + | $ε\textit{i}$ | (1 - $\textit{hM}1/2)$ (9) where $&rgr;\textit{i}+1$ is the sum of the round-off and truncation error in that step and $&eegr;\textit{i}+1$ the propagated error, 1 - $\textit{hM}1/2$ < 1, and $\textit{E}$ > | $&rgr;\textit{i}$ | for all $\textit{i}.$ For $\textit{i}$ = 0, ε0 = 0, and therefore certainly | ε0 | ≦ $2\textit{E}/\textit{hM}1.$ (10) If for a given $\textit{i},$ | $ε\textit{i}$ | ≦ $2\textit{E}/\textit{hM}1,$ then from (9) | $ε\textit{i}+1$ | ≦ $\textit{E}$ + $2\textit{E}/\textit{hM}1$ (1 - $\textit{hM}1/2)$ ≦ $2\textit{E}/\textit{hM}1,$ (11) and the proof holds by induction1 on $\textit{i}.Note$ that, if $&rgr;\textit{i}$ consists only of truncation error, | $ε\textit{i}+1$ | ≦ $2\textit{Ch}5/\textit{hM}1,$ (12) where $\textit{C}$ > $\textit{Ci}$ for all $\textit{i}$ (if sufficient bounded derivatives on ƒ(x, y) are assumed), and $lim\textit{h}→0$ | $ε\textit{i}+1$ | = 0. (13) On the other hand, if $&rgr;\textit{i}$ consists of round-off error &rgr;* also, bounded by | &rgr;* | for all $\textit{i},$ then $lim\textit{h}→0$ | $ε\textit{i}+1$ | ≦ 2(| &rgr;* | + $\textit{Ch}5)/\textit{hM}1$ = ∞, (14) provided | &rgr;* | is bounded from below by a positive non-zero value, which is generally true for fixed word-length computers; and the error bound is of no value in the limit. In that case, for $\textit{h}$ small enough | $&eegr;\textit{i}+1$ | = | $\textit{y}*\textit{i}+1$ - $\textit{y}\textit{i}+1$ | ≧ | $ε\textit{i}$ | (1 - $\textit{hM}2)$ ≧ $\textit{K}$ | $ε\textit{i}$ |, (15) where now $\textit{K}$ = (1 - $\textit{hM}2).$ If, for example, $&rgr;\textit{k}$ > $\textit{R}$ > 0, for all $\textit{k},$ one obtains | $ε\textit{i}+1$ | = $&rgr;\textit{i}+1$ + | $&eegr;\textit{i}+1$ | ≧ $&rgr;\textit{i}+1$ + $\textit{K}(&rgr;\textit{i}$ + $\textit{K}(&rgr;\textit{i}-1$ + ··· + $\textit{K}\textit{i}+1&rgr;0)$ ···) (16) ≧ $\textit{R}(1$ + $\textit{K}$ + $\textit{K}2$ + ··· + $\textit{K}\textit{i}+1)$ ≧ $\textit{R}(\textit{i}$ + $2)\textit{K}\textit{i}+1$ $∴lim\textit{h}→0$ | $ε\textit{i}+1$ | ≧ $(\textit{i}$ + $2)\textit{R}$ (17) Therefore, in the case $&rgr;\textit{k}$ > $\textit{R}$ > 0, the error can increase without limit when $(\textit{i}$ + $1)\textit{h}$ is held constant. Thus, as perhaps seems obvious from the start, decreasing the step-size will in this case, speaking roughly, improve the propagated error until the point at which the round-off and truncation error have the same order of magnitude. If on the other hand the round-off error can be made a function of the step-size of order $\textit{h}\textit{k},$ where $\textit{k}$ > 1, then the total error will go to zero as $\textit{h}$ → 0, or will remain bounded in the case $\textit{k}$ = 1. Users of variable wordlength digital computing machines should therefore increase their word-length as $\textit{h}$ is decreased in order to avoid this lower limit due to round-off error. Users of fixed word-length computers must use multi-precision. This result is not surprising; a specific algorithm for doing it is given below. If $ƒ\textit{y}$ is allowed also to be zero or positive, but bounded throughout $\textit{D},$ 0 ≦ $|∂ƒ/∂\textit{y}|$ < $\textit{M}.$ (18) Then the propagated error in $\textit{D}*$ at the $(\textit{i}$ + 1)th step, due to a given (round-off or truncation error) $ε\textit{i}$ at the $\textit{i}th$ step, is $|\textit{y}*\textit{i}+1$ - $\textit{y}\textit{i}+1$ | ≦ | $ε\textit{i}$ | (1 + $\textit{hM}$ + $(\textit{hM})2)/2$ + $(\textit{hM})3)/3!$ + $(\textit{hM})4)/4!)$ (19) or | $&eegr;\textit{i}+1$ | ≦ | $ε\textit{i}$ | $\textit{ehM},$ (20) where $&eegr;\textit{i}+1$ is the propagated error and $\textit{E}$ and $\textit{h}$ are given as before; and one obtains an error bound similar to most classical ones | $ε\textit{i}+1$ | ≦ $\textit{E}(1$ + $\textit{K}$ + $\textit{K}2$ + ··· + $\textit{Ki})$ ≦ $\textit{E}$ $\textit{K}\textit{i}+1$ - $1/\textit{K}$ - 1 = $\textit{E}$ $\textit{e}(\textit{i}+1)\textit{h$ M - 1/eh M - 1, (21) where $\textit{K}$ = eh M. In both the stable and unstable case, ignoring round-off, the process is obviously convergent in $\textit{D}$ as $\textit{h}$ → 0, since $\textit{D}*$ approaches $\textit{D}$ as $\textit{h}$ → 0 and | $ε\textit{i}+1$ | → 0. For the case $ƒ\textit{y}$ < 0 equations (7) and (14) above give an algorithm for a bound on the stepsize $\textit{h};$ a similar analysis could be based on equation (21). Suppose the round-off error per single-precision step is bounded by | $&rgr;*(1)(\textit{h})$ |, per $\textit{n}-precision$ step by | $&rgr;*(n)(\textit{h})$ |. (Here $\textit{n}$ could just as well be number of digits as number of words.) Then, since | $ε\textit{i}+1$ | ≦ $2(|&rgr;*(\textit{n})(\textit{h})|$ + $\textit{Ch}5)/\textit{hM}1,$ (22) for | $ε\textit{i}+1$ | required to be less than $\textit{B}$ > 0, choose $\textit{h}$ < $\textit{M}1/\textit{M}22$ such that 2 $\textit{Ch}5/\textit{hM}1$ < $\textit{B}/2$ (23) or $\textit{h}4$ < $\textit{M}1\textit{B}/4\textit{C}.$ (23a) Then for that value of $\textit{h},$ choose the value of $\textit{n}$ such that | $&rgr;*(\textit{n})(\textit{h})$ | < $\textit{BhM}1/4.$ (24) This will guarantee | $ε\textit{i}+1$ | < $\textit{B}.$ Obviously, such an $\textit{h}$ is not necessarily the best possible. The computation of | $&rgr;*(\textit{n})(\textit{h})$ |, while intricate, could very well be done by the computer itself, if procedures for forming formal derivatives of machine functions were included in whatever compiling techniques were used with the routine. If the calculated solution approached the boundaries of $\textit{D}*,$ the step-size $\textit{h}$ would have to be decreased, and the values of $\textit{h}$ accordingly readjusted in order to continue to apply the theorem.If $\textit{h}$ and $\textit{n}$ are picked in this fashion, the numerical machine solution can be made as close to the true solution as desired, and the process will converge. As for “stability” of the solution process under round-off, as would appear intuitive, the propagated error can be guaranteed to go to zero with the step-size $\textit{h}$ only if the round-off error per step varies with $\textit{h}$ as $\textit{O}(\textit{hk})$ with $\textit{k}$ > 1. The Kutta process is stable in the sense that for a stable differential equation, for a given $\textit{h},$ the error will be bounded by (7), where $\textit{E}$ is given without round-off error by (12) and Bieberbach's bound (4). In the latter case, as $\textit{h}$ → 0, the truncation error goes to zero, which certainly is not true for many multi-step methods. |
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 | 1958-01-01 |
Publisher Place | New York |
e-ISSN | 1557735X |
Journal | Journal of the ACM (JACM) |
Volume Number | 5 |
Issue Number | 1 |
Page Count | 6 |
Starting Page | 39 |
Ending Page | 44 |
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