i - - - - I OFI ORNL P 1303 . . : 1 : .. C ... - . - - - - - - - . ----..-..- - 50 TREET 14:40 MICROCOPY RESOLUTION TEST CHART NATIONAL BUREAU OF STANDARDS - 1963 U L LEGAL NOTICE This report was prepared as an account of Government sponsored work. Neither the United States, nor the Commission, nor any person acting on behalf of the Commission: A. Makes any warranty or representa- tion, expressed or implied, with respect to the accuracy, completeness, or usefulness of the information contained in this report, or that the use of any information, appa- ratus, method, or process disclosed in this report may not infringe privately owned rights; or B. Assumes any liabilities with respect to the use of, or for damages resulting from the use of any information, apparatus, method, or process disclosed in this report. As used in the above, “person acting on behalf of the Commission” includes any em- ployee or contractor of the Commission, or employee of such contractor, to the extent that such employee or contractor of the Commission, or employee of such contractor prepares, disseminates, or provides access to, any information pursuant to his employ- ment or contract with the Commission, or his employment with such contractor. . : - - ORN & -P11303 . 3کر دم کر سمیرم * JUN 2 4 1666... Two Algorithms of Romberg Type for Ordinary. Initial-Value Problems* ORNE-AEC - OFFICIAL William B. Grass Oak Ridge National Laboratory Oak Ridge, Tennessee The algorithm of Romberg (1) and its generalizations (2) for the computation of definite integrals are based on the fact that, under suitable regularity assumptions on the integrand, the trapezoidal rule with step h has an asymptotic expansion in powers of h'. It was proposed in (1) to apply similar ideas to the solution of ordinary initial-value problems using Euler's method as the basic discretization. The corresponding expansion contains also odd powers of h. The purpose of this note is to state the existence of simple discretizations of both first and special second order systems which have h' expansions. When coupled with extrapolation algorithms, as indicated in (6), these ',- schemes provide effective procedures for ordinary initial-value problems. Let I be infinitely differentiable and uniformly Lipschitzian . with respect to its second argument on the set I X C,, where I = (a,b] is finite ,and C, is Euclidean l-space. It is required to approximate the solution x(t) of the system x(a) = s, (1) x' = f(t,x), teI, at a fixed point + € I. Also put J(t) = de (t,x(t)), the Jacobian matrix of f evaluated at the solution X(t).. 1. + 14 Research sponsored by the U. S. Atomic Energy Commission under contract with the Union Carbide Corporation. TT . PATENT CLEARANCE OCTAINED. RELEASE TO THE PUBLIC IS APPRCHED. PROCEDURES ARE ON FIILE IN THE KLE:HG SECTION, 1 LEGAL NOTICE - The report was prepared as an account of Governmt sponsored work. Noltber the Valled statos, oor the Commisskoo, oor way pornoo acting on behalf of the Commuosion: A. Makeo may narranty or reprend la uon, expressed or impued, with respect to the accu- racy, completeness, or usefuldest of the Information sontalo.d to No report, or that the wire of any laformation, apparatus, molbod, or procura dincloned la to report may not fofringe printely oned rigalos or 8. Asmots may iladillues mu respect to the um of, or for damage resulung from ebe One of any information, apparatu, Bethod, or procesi di cloud la o report. As used in the abon, "perro act on behalf of the Comminoloo" includes way od. ploya or contractor of the Commisslon, or employm of such contractor, to the extat al euch employs or contractor of le Commission, or employs of such cootructor prepardı, dlouminater, or provides access to, ang Information purnoi 10 Na employment or cooirici with the Commission, or do employment with such contractor. ORNL - AEC - OFFICIAL -2- The Nyström second order method Xo = a , .*7 = s() , *2+1 = *2-1 + 2h f(t:X), n(t;n) = x, Nh = t - a , where s, (h) is a starting function, was studied in [3,4]. De logeleare [3] showed that if s, (h) is chosen in a certain definite manner', 87(h) x(a) + x'(a) h + { x"(a) be. 5(a) *** (a) = { }(4)(a) ]n* + ... (2) then there exist (infinitely differentiable) functions e, such that n(t;h) ~ x(t) + ez(t) h2 + eg(t) n* + ... . (3) This result, while interesting theoretically, is of limited practical value since the condition (2) is difficult to obtain. However, in [4] it was shown that the infinite generalized b2-expansion n[t;h) ~ x(t) + £ 14.(+) + (-1)" ()}22 (4) results from the natural starting function s, (h) = s + hf(a,b). The functions U V satisfy linear differential equations of the form + inhomogeneous terms, uns = J(t) 4x + inhomogeneous terms , v = -J(t) vx + inhomogeneous terms . The vi are the "weakly unstable" components oî the error. ORNI – AEC - OFFICIAL VIILIO 3. ORHIALI - OFFICIAL A consideration of the explicit form of these differential VNN-ni equations leads to the separation of the even and odá parts of the rule n and to the algorithm Xy = 5, y = $ + a (a,s), *n+1 = x + h f(tiptelin yond Yn+1 = yn + h f(th+1° *n+2 , M(t;h) = xy, Nh = t - a , T(t;h) = yy - f(t, xy). When is independent of x the rules M and T become the ordinary midpoint and trapezoidal rules, respectively. They both have h- . . expansions. Moreover their mean . . . . . . . . . . . . .. Alt;h) = (M(t;h) + T(t;h)] has an expansion of the form (3) with ez(t) = uz (t) + + x"(t), i.e., the rule A annihilates the leading unstable component of the error. Weak instability still precludes the general purpose application of these schemes in a global manner. However, the following observation guarantees the numerical stability of their step-by-step use when coupled with extrapolation algorithms. If either of the rules M, T, or A is coupled with the Neville (Stoer) ... . . .. .. in.. ; maaarin e mor nie... algorithm using a fixed number of extrapolations per step ho then the entire process is a Runge-Kutta (one-step) method. The existence nina.... of the Stoer 'schemes at each step must be assumed in the latter case. ORNL-AEC - OFFICIAL ORNL - AEC - OFFICIAL totimiz nebeska ܛܝ ORNL - AEC - OFFICIAL ORHI-ALC - OFFICIAL For the special second order system x(a) = s, x'(a) = s', x" = f(t,x), teI , where f satisfies the above conditions, the summed form of the Störmer second order method is Xo = s, Yo = s' + f(a,s), *n+1 = x + h yn Yn+1 = yn + h f(tn+2° *n+2), Analogous to (5) put s(t;h) = x , Nh = t - a , S*(t;n) = xy - F(t, xy). (7) . The rules S and S* have h' -expansions with constant terms x(t) and x'(t), respectively. The result concerning S was sti.ied by Mayers (5). Special methods for the system (6) are usually justified by the fact that a saving can be achieved if one avoids computation of the derivative x'(t). It is necessary to know x'(t) for tie step- by-step use of (7) coupled with extrapolation schemes. It is therefore noteworthy that an h2-expansion can be obtained for its computation with no essential increase in the number of evaluations of f. ORNI - AEC-Osiris ORNI ~ AEC - OFFICIAL References ORNI - AEC - OFFICIAL [1] F. L. Bauer, H. Rutishauser, and E. Stiefel: New Aspects in F!umerical Quadrature, Proc. of Symposia in f.pplied Mathematics 15, Amer. Math. Soc. (1963) 199-218. (2) R. Bulirsch and J. Stoer: Fehlerabschätzungen und Extrapolation mit rationalen Funktionen bei Verfahren vom Richardson-Ty.pus. Num. Math. 6 (1964) 413-427. (3] R. de Vogeleare: On a Paper of Gaunt concerned with the Start of Numerical Solutions of Differential Equations, 2. Angew. Math. Phys. 8 (1957) 151-156. [4] W. B. Gragg: Repeated Extrapolation to the Limit in the Numerical Solution of Ordinary Differential Equations, Doctoral . . . . . . - Dissertation, Univ. of California, Los Angeles, 1964. (51 D. F. Mayers: The deferred approach to the limit in ordinary differential equations. Comput. J. I (1964) 54-57. [6] J. Stoer: Convergence Acceleration by Extrapolation Methods, this vol.; ; 17..comiendast om o ........................... ORNL - AEC - OFFICIAL i vet stond de teinek.initiat END ---- too.. DATE FILMED 9/ 3 / 65 www 4 . . ' . 11 21 1 . : 1. * [. . . 1