A-Stable Composite Multistep Methods

ABSTRACT

Consider the set of multistep formulas ∑l-1jmn-k &agr;ijxmn+j - h ∑l-1jmn-k&bgr;ijxmn+j = 0, i = 1, ···, l, where xmn+j = ymn+j for j= -k, ···, -1 and xn = ƒn = ƒ(xn , tn). These formulas are solved simultaneously for the xmn+j with j = 0, ···, l - 1 in terms of the xmn+j with j = -k, ··· , - 1, which are assumed to be known. Then ymn+j is defined to be xmn+j for j = 0, ··· , m - 1. For j = m, ··· , l - 1, xmn+j is discarded. The set of y's generated in this manner for successive values of n provide an approximate solution of the initial value problem: y = ƒ(y, t), y(t0) = y0. It is conjectured that if the method, which is referred to as the composite multistep method, is A-stable, then its maximum order is 2l. In addition to noting that the conjecture conforms to Dahlquist's bound of 2 for l = 1, the conjecture is verified for k = 1. A third-order A-stable method with m = l = 2 is given as an example, and numerical results established in applying a fourth-order A-stable method with m = 1 and l = 2 are described. A-stable methods with m = l offer the promise of high order and a minimum of function evaluations—evaluation of ƒ(y, t) at solution points. Furthermore, the prospect that such methods might exist with k = 1—only one past point—means that step-size control can be easily implemented

REFERENCES

• 1: CURTISS, C F., AND HIRSCItFELDER, J O. Integration of stiff equations. Proc. Nat. Acad. Sc~. 38 (1952), 235--243.
• 2: DAHLQUIST, G. G. A special stability problem for linear multistep methods. BIT (1963), 27-43.
• 3: LINIGER, W., AND WILLOUGHBY, R.A. Efficient numerical integration of stiff systems of ordinary differential equations SIAM J. Num Anal. 7 (1970), 47-66.
• 4: I:~OSENBROCK, H.H. Some general imphcit processes for the numerical solution of diferential equations. Comput J. 5 (1963), 329-330.
• 5: CALAHAN, D.A. A stable accurate method of numerical integration for nonlinear systems. Proc. IEEE 56 (1968), 744.
• 6: ALLEN, n. H., AND POTTLE, C. Stable integration methods for electronic circuit analysis with widely separated time constants. Proc. Sixth Annual Allerton Conf. on Circuit and System Theory, U. of illinois, Urbana, Ill., 1968, pp. 311-320.
• 7: EHLE, B.L. High order A-stable methods for the numerical solution of systems of D.E.'s. BIT 8 (1968), 276-278.
• 8: Eldon Hansen, Cyclic composite multistep predictor-corrector methods, Proceedings of the 1969 24th national conference, p.135-139, August 26-28, 1969 [doi>10.1145/800195.805925]
• 9: DONELSON, J., IiI, AND HANSEN, E Cyclic composite multistep predictor-corrector methods. SIAM J Num. Anal. 9 (1971), 137-157.
• 10: GANTMACHER, F R The Theory of Matrices, Vol. I Chelsea, New York, 1959, pp. 130-145.
• 11: KELLY, L.G. Handbook of Numerical Methods and Applications Addison-Wesley, Reading, Mass., 1967.
• 12: HENRICZ, P. D~screte Vamable Methods zn Ordznary D~fferent~al Equatwns. Wiley, New York, 1962.
• 13: URABE, M. Theory of errors in numerical integration of ordinary differential equations. Tech. Sum Rep 183, US Army Math. Res Ctr, U. of Wisconsin, Madison, Wis., 1960
• 14: William B. Gragg , Hans J. Stetter, Generalized Multistep Predictor-Corrector Methods, Journal of the ACM (JACM), v.11 n.2, p.188-209, April 1964 [doi>10.1145/321217.321223]
• 15: SLOATE, H.M. Simultaneous implicit formulas for the solution of stiff systems of differential equations. Ph.D. D1ss., Syracuse U, Syracuse, N.Y., 1971.
• 16: Richard W. Hamming, Numerical Methods for Scientists and Engineers, McGraw-Hill, Inc., New York, NY, 1973
• 17: MILLIMAN, L. D., MASSENA, W. A, AND DICKHAUT, R.A. CIRCUS User's Grade. US Army Material Command, Harry Diamond Labs., Washington, D.C.
• 18: David A. Pope, An exponential method of numerical integration of ordinary differential equations, Communications of the ACM, v.6 n.8, p.491-493, Aug. 1963 [doi>10.1145/366707.367592]
• 19: 3RAYTON, R K, GUSTAVSON, F G, AND LINIGER, W. A numerical analysis of the transient behawor of a transistor c~rcmt IBM J Res. Devel 10 (1966), 292-299.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Multistep and multivalue methods

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.7 Ordinary Differential Equations
          Subjects: Stiff equations

General Terms:
Measurement, Performance, Reliability, Theory, Verification