A Generalization of a Theorem of Carr on Error Bounds for Rung-Kutta Procedures

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 y′ = ƒ(x,y) is based on the computation: k1 = hƒ(xi, yi) k2 = hƒ(xi, + mh, yi + mk1) k3 = hƒ(xi, + vh, yi + (v - r)k1 + rk2) k4 = hƒ(xi, + ph, yi + (p - s - t)k1 + sk2 + tk3) k = ak1 + bk2 + ck3 + dk4 yi+1 = yi + k, where h is the step size of the integration. Carr considered the case: k1 = hƒ(xi, yi) k2 = hƒ(xi + 1/2h, yi + 1/2 k1) k3 = hƒ(xi + 1/2h, yi + 1/2 k2) k4 = hƒ(xi + h, yi + k3) k = 1/6 (k1 + 2k2 + 2k3 + k4) yi+1 = yi + k, and established the following theorem (we shall use the notation of [1] without further explanation): THEOREM 1. If ∂ƒ/∂y is continuous, negative, and bounded from above and below throughout a region D in the (x, y)-plane, -M2 < ∂ƒ/∂y < - M1 < 0, where M2 > M1 > 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* of | &egr;i | ≦ 2E/hM1, where the step size h is to be taken to be h < min (4M13/M24 , M1/M22 - 2 dsM22 - 2 dsmM1M2) PROOF. Let yi+1 be the value of the solution obtained at step i + 1. If there is no error at step i, let yi+1* be the value of the solution obtained assuming an error of &egr;i introduced at the ith step. Then the propagated error at the (i + 1)- st step is &eegr;i+1 = yi+1* - yi+1. The proof of theorem 1 as given in [1] is based on the inequality | &eegr; i+1 | ≦ | &egr;i || 1 - hM1/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 k1, k2, k3, k4, and k are equated, providing a set of eight equations: a + b + c + d = 1 bm + cv + dp = 1/2 bm2 + cv2 + dp2 = 1/3 bm3 + cv3 + dp3 = 1/4 crm + d(sm + tv) = 1/6 crm2 + d(sm2 + tv2) = 1/12 crmv + dp (sm + tv) = 1/8 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 &egr;i at the ith step, the value of k1 (at the (i + 1)-st step) will be (by a simple application of the Mean Value Theorem): k1* = hƒ(xi, yi + &egr;i) = hƒ(xi, yi) + h ∂ƒ/∂y &egr;i = k1 + hƒy&egr;i, where the partial derivative ƒy = ∂ƒ∂y is evaluated in a suitable rectangle. Similarly, (remembering that each occurrence of ƒy is to be evaluated at a possibly different point): k2* = k2 + hƒy&egr;i[1 + mhƒy] k3* = k3 + hƒy&egr;i[1 + (v - r)hƒy + rhƒy[1 + hmƒy]] k4* = k4 + hƒy&egr;i[1 + (p - s - t)hƒy + shƒy[1 + hmƒy] + thƒy[1 + (v - r)hƒy + rhƒy[1 + hmƒ k4* = k4 + hƒy&egr;i[1 + (p - s - t)hƒy + shƒy[1 + hmƒy] + thƒy[1 + (v - r)hƒy + rhƒy[1 + hmƒy]]] so that y1+1 = yi + &egr;i + ak1* + bk2* + ck3* + dk4* = yi+1 + &egr;i[1 + h(aƒy + bƒy + cƒy + dƒy)

REFERENCES

• 1: John W. Carr, III, Error Bounds for the Runge-Kutta Single-Step Integration Process, Journal of the ACM (JACM), v.5 n.1, p.39-44, Jan. 1958 [doi>10.1145/320911.320916]

INDEX TERMS

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

General Terms:
Performance, Reliability, Theory, Verification