Optimized computation with recursive power series integration NASA Technical Memorandum X-643-68-80 OPTIMIZED COMPUTATION WITH RECURSIVE POWER SERIES INTEGRATION R. H. Estes E. R. Lancaster March 1968 Goddard Space Flight Center Greenbelt, Maryland PRECEDING PAGE BLANK NOT FILMED. OPTIMIZED COMPUTATION WITH RECURSIVE POWER SERIES INTEGRATION ABSTRACT The power series technique is applied to the restricted three-body problem and recursion formulas are developed f o r the coefficients of the power series which reduce sig- nificantly the computation time required by the recursion formulas developed by previous authors. Van Flandern's method for maximizing the step size per unit of computer time is discussed and extended on the basis of relative e r r o r control. A method f o r controlling the magnitudes of the series coefficients is also presented. iii OPTIMIZED COMPUTATION WITH RECURSIVE POWER SERIES INTEGRATION INTRODUCTION The method of solution of second degree systems of differential equations by recurrent power series is well known [6]. This technique is especially use- ful when variable step sizes a r e needed in the integration, and has the bonus property of automatically choosing the correct step size relative to some pre- s e t e r r o r tolerance. A s pointed out by Fehlberg [2l, a substantial saving in computing time i s realizable under the above conditions by choosing a power s e r i e s method over a Runge-Kutta o r interpolation procedure. In this paper the power series technique will be applied to the restricted three-body problem and a few "tricks" will be presented which reduce signifi- cantly the computation time required by the recursion formulas presented in the papers we have seen [2, 5 , 61. Van Flandern's method [71 for maximizing the step size per unit of computer time is discussed and extended on the basis of relative e r r o r control. A method f o r controlling the magnitudes of the series coefficients is also presented. THE RESTRICTED THREE-BODY PROBLEM Second degree systems of differential equations are not always met in prac- tice. However, upon introducing appropriate auxiliary functions a given system may in many instances be transformed into one of the second degree. It i s to be noted that in general for a particular set of equations there are no unique auxiliary functions which will transform the system to the above form, but rather one must search for the functional substitutions which lead to more symmetric recursion formulas and fewer computational operations. A s an illustration, con- sider the restricted problem of three bodies. In a rotating coordinate system the equations of motion are d2X - - -xt2d_Y-(l-i?L) X+P x- 1 + p ' L 'L dt2 dt 3/2 '[(x t p ) 2 t y2]3/2 d 5 = y - 2 dx - --(l-p) Y - P Y dt2 dt [(x + p)2 -t y2] 3/2 [(x- 1 t p y t y2]3.'2 1 where p is the mass of the lighter body and 1-p is the m a s s of the heavier body. The commonly used auxiliary functions v =& s3 upon introduction into the equations of motion yield the following second degree system: d2y = y - 2 2 - uy - v y - dt2 dt r-du t 3u-d r = 0 dt dt dv ds s- t 3v- = 0 dt dt s2 = ( x - 1 t p ) * t y2 . 2 Letting x =z Xiti =z i=u Y Yiti ! u =c co ir 0 u it' and substituting into (3) we obtain, after equating coefficients of like powers, 2 rorn i'0 xixn-i -t 2 p x n -t & -- n YiY, i n- 1 rirn-i n n- I for n 21. 3 The initial conditions of the problem yield xo , x y o , and y1 , and ro, so , uo, v0 are obtained from (2), the auxiliary functions. It may be easily seen that proceeding through this algorithan t o calculate the (n + 1) st t e r m , i.e., x n and yn 1 , there are required 14n + 4 additions, 16n + 16 multiplications, and 6 divisions. Further, 26n + 4 quantities are addressed. Let us return now to (1)and consider instead the following auxiliary func- tions: ,B= a - 2 s + 1 p = -1 - P ,3/2 qx-. P p3/2 4 Substituting (Sj into (1) then yields the second degree system: -d2s =s+2dy-sp-(s-l)q-p , dt2 dt -- ds dt2 da dP 3p-+22a--zO , dt dt a = s2 + y 2 . Letting a, s = c Sitl i = O i = O a=C a, aiti i = O a, P=CPiti i=O al P = C Piti i=O .=E al q,t' i=O 5 and substituting into (7) there results for n l l . Again, the initial conditions yield s o , s1 y o , and y,; and a. P o , po, q, are determined from ( 6 ) . However, the calculation of the (n + 1) st term now involves 9n + 5 additions 7n + 20 multiplications and 4 divisions. Also, only 12n + 1 2 quantities a r e addressed. Thus, by simply choosing the auxiliary functions (6) instead of (2) the computation time for high order t e r m s will be approximately halved. It is to be noted that symmetries such as in the first of equations (9) occur frequently in practice and full advantage of these symmetries should be taken in a computational scheme. 6 I MINIMIZATION O F COMPUTER TIME In a power series integration method, the solution is represented as a power s e r i e s , e.g., x =z 03 n=O antn . (10) For a given number of t e r m s n, t is chosen s o that x has a desired accuracy, By using the solutions of the previous step a s initial conditions for a new step and computing a new power series, the solution is extended by analytic continuation. The following technique, due to Thomas Van Flandern,[7] minimizes the computer time required to integrate over a given interval. Let 7 designate total compu- tation time for a step and assume that a fixed time, , is the initialization time for each step. Since the computation time required for the (n + 1) st. term is greater than that for the nth t e r m , 7 = 7 (n) is an increasing monotone function. Further, with the addition of more terms in the series the integration step size h increases for fixed accuracy and approaches h m a x the , radius of convergence. Thus h = h(n) is also an increasing monotone function. We wish to make h a s large as possible for a given amount of computer time. Thus we a r e led to choose the value of n such that the quantity h/7 is a maxi- mum. That this ratio has at least one maximum is obvious from the fact that h/7 is zero for n = 0, approaches zeroas n gets large, and has only positive values for n> 0. The ratio h/7 should be calculated for each new t e r m of the s e r i e s , and a check made for i t s maximum value. The step size h may be estimated from the newly calculated term and a preset e r r o r tolerance, while 7 may be obtained from an accurate computer clock or from operation counting for the particular recursive formulas used. The following graphs illustrate the above procedure: 7 n n In practice, convergence of the series will usually insure that the sum of neglected terms will be smaller in magnitude than the first t e r m omitted. In such cases we may calculate the step size for each new t e r m from h =(+Y’*’ , where an is the n t h coefficient of the series and E is the absolute e r r o r tolerance. Many times with this procedure it is found to be true that the magnitudes of the calculated series coefficients a r e such that h = h(n) is not an increasing mono- tone function, Le., it has small oscillations in violation of the criteria of appli- cability for Van Flandern’s procedure. However, the authors have found in gen- eral that such coefficients which disrupt the smoothly increasing sequence of the magnitude of h are isolated and so the requirement that the ratio h/T of three consecutive terms form a strictly decreasing sequence yields excellent results as a test for the maximum value of h/T. In order to avoid unnecessary labor in computation it is desirable that all e r r o r s committed at any integration step contribute uniformly to the entire in- tegration e r r o r . Thus the e r r o r tolerance E of equation (11)must be a relative, rather than an absolute e r r o r . The authors have found it convenient to form the absolute e r r o r , ea, for eachintegration step by selecting a relative e r r o r e r f o r the entire integration and from the initial conditions a, at each step, forming 8 When a. is small, however, ea is replaced by a preset value. A major problem which occurs in practice is that the series coefficients a may become quite large for increasing n. This results in a loss of accuracy wh>n the truncated series is evaluated at a value of the independent variable for agiven integration step. However, the following convenient property of recursive power series may be used t o easily overcome this difficulty. Given the series (lo), i.e. a, n=O we may scale t such that t = hs so that the above series becomes W bnhn , v=o where the coefficients b n are calculated with the recursive relations which determine a n slightly changed and with simple changes in the initial conditions [ l ] , [41. By assuming that the step size for a given integration step will be nearly equal to that of the previous step, we set s equal to the previous step size so that h 2 1 and the coefficients b n are well behaved. In the interest of reducing roundoff e r r o r over the course of the integration the authors have found i t useful to set the scale factor equal to a power of two so that the operations involving the scale factor are merely shifts within a bi- nary digital computer. We have programmed the above techniques for the restricted problem of three bodies and applied the same initial conditions as those of Fehlberg [3lfor the integration of a periodic orbit. Our inability to obtain a replica of the opera- . ting program used by this author has led to limited comparison. However, our own results indicate that the reduced computational procedures outlined in this paper produce a 40%-50% time saving over a conventional power series integration of this periodic orbit with each step constrained to sixteen t e r m s , where both methods were performed in double precision arithmetic on an IBM 9 7094 computer with a preset e r r o r tolerance of We conclude from this that the above techniques lead to the same high precision in comparable computing time as the high order Runge-Kutta tranformation type formulas of Fehlberg[31 with the advantage of simpler and more compact programming. REFERENCES Estes, R. H. and E. R. Lancaster, "Power Series Inverses of the Universal Form of Kepler's Equation," X-64348-40, GSFC, NASA. Fehlberg, E., "Numerical Integration of Differential Equations by Power Series Expansions, Illustrated by Physical Examples," NASA TN D-2356, October 1964. Fehlberg, E., "New One-Step Integration Methods of High-Order Accuracy Applied to Some Problem in Celestial Mechanics," NASA TR R-248, October 1966. Lancaster, E. R. and R. H. Estes, "Some New Power Series Inversions of Kepler's Equation," NASA X-643-67-613, GSFC, December 1967. Rabe, E., "Determination and Survey of Periodic Trojan Orbits in the Re- stricted Problem of Three Bodies," Astronomical Journal 66, No. 9,1961. - Steffensen, J. F., "On the Restricted Problem of Three Bodies," Mat. Fys. Medd. Dan. Vid. Selsk. 30(1956), No. 18. Van Flandern, T., "Optimization of Steffensen's Method," paper presented to the IV Special Projects Branch Astrodynamics Conference, Goddard Space Flight Center, Greenbelt, Md., May 2, 19GG. 10