Thumbnail
Access Restriction
Subscribed

Author Galler, B. A. ♦ Rozenberg, D. P.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1960
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Abstract In [1] Carr established propagation error bounds for a particular Runge-Kutta (RK) procedure, and suggested that similar bounds could be established for other RK procedures obtained by choosing the parameters differently. More explicitly, a fourth-order Runge-Kutta procedure for the solution of the equation $\textit{y}′$ = $ƒ(\textit{x,y})$ is based on the computation: $\textit{k}1$ = $\textit{h}ƒ(\textit{xi},$ $\textit{yi})$ $\textit{k}2$ = $\textit{h}ƒ(\textit{xi},$ + $\textit{mh},$ $\textit{yi}$ + $\textit{mk}1)$ $\textit{k}3$ = $\textit{h}ƒ(\textit{xi},$ + $\textit{vh},$ $\textit{yi}$ + $(\textit{v}$ - $\textit{r})\textit{k}1$ + $\textit{rk2})$ $\textit{k}4$ = $\textit{h}ƒ(\textit{xi},$ + $\textit{ph},$ $\textit{yi}$ + $(\textit{p}$ - $\textit{s}$ - $\textit{t})\textit{k}1$ + $\textit{sk}2$ + $\textit{tk}3)$ $\textit{k}$ = $\textit{ak}1$ + $\textit{bk}2$ + $\textit{ck}3$ + $\textit{dk}4$ $\textit{y}\textit{i}+1$ = $\textit{yi}$ + $\textit{k},$ where $\textit{h}$ is the step size of the integration. Carr considered the case: $\textit{k}1$ = $\textit{h}ƒ(\textit{xi},$ $\textit{yi})$ $\textit{k}2$ = $\textit{h}ƒ(\textit{xi}$ + $1/2\textit{h},$ $\textit{yi}$ + 1/2 $\textit{k}1)$ $\textit{k}3$ = $\textit{h}ƒ(\textit{xi}$ + $1/2\textit{h},$ $\textit{yi}$ + 1/2 $\textit{k}2)$ $\textit{k}4$ = $\textit{h}ƒ(\textit{xi}$ + $\textit{h},$ $\textit{yi}$ + $\textit{k}3)$ $\textit{k}$ = 1/6 $(\textit{k}1$ + $2\textit{k}2$ + $2\textit{k}3$ + $\textit{k}4)$ $\textit{yi}+1$ = $\textit{yi}$ + $\textit{k},$ and established the following theorem (we shall use the notation of [1] without further explanation): THEOREM 1. $\textit{If}$ ∂ƒ/∂y is continuous, negative, and bounded from above and below throughout a region D in the (x, y)-plane, $-\textit{M}2$ < $∂ƒ/∂\textit{y}$ < - $\textit{M}1$ < 0, where M2 > $\textit{M}1$ > 0, then for a maximum error (truncation, or round-off, or both) E in absolute value at each step in the Kutta fourth-order numerical integration procedure has total error at the ith step, i arbitrary, in the region D* $\textit{of}$ | $ε\textit{i}$ | ≦ $2\textit{E}/\textit{hM}1,$ where the step size h is to be taken to be $\textit{h}$ < min $(4\textit{M}13/\textit{M}24$ , $\textit{M}1/\textit{M}22$ - 2 $\textit{dsM}22$ - 2 $\textit{dsmM}1\textit{M}2)PROOF.$ Let $\textit{yi}+1$ be the value of the solution obtained at step $\textit{i}$ + 1. If there is no error at step $\textit{i},$ let $\textit{yi}+1*$ be the value of the solution obtained assuming an error of $ε\textit{i}$ introduced at the $\textit{i}th$ step. Then the propagated error at the $(\textit{i}$ + 1)- st step is $&eegr;\textit{i}+1$ = $\textit{yi}+1*$ - $\textit{yi}+1.$ The proof of theorem 1 as given in [1] is based on the inequality | &eegr; $\textit{i}+1$ | ≦ | $ε\textit{i}$ || 1 - $\textit{hM}1/2$ |. We shall show that this inequality can be obtained under the hypotheses of theorem 2.In the determination of the parameters a, b, c, d, m, v, p, r, s, t for the Runge-Kutta procedure, certain coefficients of Taylor expansions of $\textit{k}1,$ $\textit{k}2,$ $\textit{k}3,$ $\textit{k}4,$ and $\textit{k}$ are equated, providing a set of eight equations: $\textit{a}$ + $\textit{b}$ + $\textit{c}$ + $\textit{d}$ = 1 $\textit{bm}$ + $\textit{cv}$ + $\textit{dp}$ = 1/2 $\textit{bm}2$ + $\textit{cv}2$ + $\textit{dp}2$ = 1/3 $\textit{bm}3$ + $\textit{cv}3$ + $\textit{dp}3$ = 1/4 $\textit{crm}$ + $\textit{d}(\textit{sm}$ + $\textit{tv})$ = 1/6 $\textit{crm}2$ + $\textit{d}(\textit{sm}2$ + $\textit{tv}2)$ = 1/12 $\textit{crmv}$ + $\textit{dp}$ $(\textit{sm}$ + $\textit{tv})$ = 1/8 $\textit{drtm}$ = 1/24 Assuming, then, that we have a Runge-Kutta procedure obtained this way, we may use the equations (3) when necessary.If there is an error $ε\textit{i}$ at the $\textit{i}th$ step, the value of $\textit{k}1$ (at the $(\textit{i}$ + 1)-st step) will be (by a simple application of the Mean Value Theorem): $\textit{k}1*$ = $\textit{h}ƒ(\textit{xi},$ $\textit{yi}$ + $ε\textit{i})$ = $\textit{h}ƒ(\textit{xi},$ $\textit{yi})$ + $\textit{h}$ $∂ƒ/∂\textit{y}$ $ε\textit{i}$ = $\textit{k}1$ + $\textit{h}ƒ\textit{y}ε\textit{i},$ where the partial derivative $ƒ\textit{y}$ = $∂ƒ∂\textit{y}$ is evaluated in a suitable rectangle. Similarly, (remembering that each occurrence of $ƒ\textit{y}$ is to be evaluated at a possibly different point): $\textit{k}2*$ = $\textit{k}2$ + $\textit{h}ƒ\textit{y}ε\textit{i}[1$ + $\textit{mh}ƒ\textit{y}]$ $\textit{k}3*$ = $\textit{k}3$ + $\textit{h}ƒ\textit{y}ε\textit{i}[1$ + $(\textit{v}$ - $\textit{r})\textit{h}ƒ\textit{y}$ + $\textit{rh}ƒ\textit{y}[1$ + $\textit{hm}ƒ\textit{y}]]$ $\textit{k}4*$ = $\textit{k}4$ + $\textit{h}ƒ\textit{y}ε\textit{i}[1$ + $(\textit{p}$ - $\textit{s}$ - $\textit{t})\textit{h}ƒ\textit{y}$ + $\textit{sh}ƒ\textit{y}[1$ + $\textit{hm}ƒ\textit{y}]$ + $\textit{th}ƒ\textit{y}[1$ + $(\textit{v}$ - $\textit{r})\textit{h}ƒ\textit{y}$ + $\textit{rh}ƒ\textit{y}[1$ + $\textit{hm}ƒ$ $\textit{k}4*$ = $\textit{k}4$ + $\textit{h}ƒ\textit{y}ε\textit{i}[1$ + $(\textit{p}$ - $\textit{s}$ - $\textit{t})\textit{h}ƒ\textit{y}$ + $\textit{sh}ƒ\textit{y}[1$ + $\textit{hm}ƒ\textit{y}]$ + $\textit{th}ƒ\textit{y}[1$ + $(\textit{v}$ - $\textit{r})\textit{h}ƒ\textit{y}$ + $\textit{rh}ƒ\textit{y}[1$ + $\textit{hm}ƒ\textit{y}]]]$ so that $\textit{y}1+1$ = $\textit{yi}$ + $ε\textit{i}$ + $\textit{ak}1*$ + $\textit{bk}2*$ + $\textit{ck}3*$ + $\textit{dk}4*$ = $\textit{y}\textit{i}+1$ + $ε\textit{i}[1$ + $\textit{h}(\textit{a}ƒ\textit{y}$ + $\textit{b}ƒ\textit{y}$ + $\textit{c}ƒ\textit{y}$ + $\textit{d}ƒ\textit{y})$
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-01-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 7
Issue Number 1
Page Count 4
Starting Page 57
Ending Page 60


Open content in new tab

   Open content in new tab
Source: ACM Digital Library