Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Equivalent forms of multistep formulas

Author: Robert D. Skeel
Journal: Math. Comp. 33 (1979), 1229-1250
MSC: Primary 65L05
Corrigendum: Math. Comp. 47 (1986), 769.
MathSciNet review: 537967
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: For uniform meshes it is shown that any linear k-step formula can be formulated so that only k values need to be saved between steps. By saving additional m values it is possible to construct local polynomial approximations of degree $ k + m - 1$, which can be used as predictor formulas. Different polynomial bases lead to different equivalent forms of multistep formulas. In particular, local monomial bases yield Nordsieck formulas. An explicit one-to-one correspondence is established between Nordsieck formulas and k-step formulas of order at least k, and a strong equivalence result is proved for all but certain pathological cases. Equivalence is also shown for P(EC)$ ^\ast$ formulas but not for P(EC)$ ^\ast$E formulas.

References [Enhancements On Off] (What's this?)

  • [G] D. BYRNE & A. C. HINDMARSH (1975), "A polyalgorithm for the numerical solution of ordinary differential equations," ACM Trans. Math. Software, v. 1, pp. 71-96. MR 0378432 (51:14600)
  • [G] DAHLQUIST (1956), "Numerical integration of ordinary differential equations," Math. Scand., v. 4, pp. 33-50. MR 0080998 (18:338d)
  • [G] DAHLQUIST (1963), "A special stability problem for linear multistep methods," BIT, v. 3, pp. 27-43. MR 0170477 (30:715)
  • [G] DAHLQUIST (1975), On Stability and Error Analysis for Stiff Non-linear Problems, Part I, Report TRITA-NA-7508, Dept. of Computer Sci., Roy. Inst. of Technology, Stockholm.
  • [J] DESCLOUX (1963), A Note on a Paper by A. Nordsieck, Report #131, Dept. of Computer Sci., Univ. of Illinois at Urbana-Champaign.
  • [C] DILL & C. W. GEAR (1971), "A graphical search for stiffly stable methods for ordinary differential equations," J. Assoc. Comput. Mach., v. 18, pp. 75-79.
  • [C] W. GEAR (1966), The Numerical Integration of Ordinary Differential Equations of Various Orders, Report #ANL-7126, Argonne National Laboratory, Argonne, Illinois. MR 0225494 (37:1087)
  • [C] W. GEAR (1971a), Numerical Initial Value Problems in Ordinary Differential Equations, Prentice-Hall, Englewood Cliffs, N. J. MR 0315898 (47:4447)
  • [C] W. GEAR (1971b), "Algorithm 407: DIFSUB for solution of ordinary differential equations," Comm. ACM, v. 14, pp. 185-190.
  • [R] D. GRIGORIEFF & J. SCHROLL (1977), Über $ A(\alpha )$-stabile Verfahren hoher Konsistenzordnung, Nr. 34, Fachbereich Mathematik (3), Technische Universität Berlin.
  • [G] K. GUPTA (1976), "Some new high-order multistep formulae for solving stiff equations," Math. Comp., v. 30, pp. 417-432. MR 0423812 (54:11786)
  • [G] K. GUPTA & C. S. WALLACE (1975), "Some new multistep methods for solving ordinary differential equations," Math. Comp., v. 29, pp. 489-500. MR 0373290 (51:9490)
  • [P] HENRICI (1962), Discrete Variable Methods in Ordinary Differential Equations, Wiley, New York. MR 0135729 (24:B1772)
  • [A] C. HINDMARSH (1974), GEAR: Ordinary Differential Equation Solver, UCID-3001, Rev. 3, Lawrence Livermore Laboratory, Univ. of California, Livermore, California.
  • [M] K. JAIN & V. K. SRIVASTAVA (1970), High Order Stiffly Stable Methods for Ordinary Differential Equations, Report #394, Dept. of Computer Sci., Univ. of Illinois at Urbana-Champaign.
  • [D] E. KNUTH (1968), The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Addison-Wesley, Reading, Mass. MR 0378456 (51:14624)
  • [A] K. KONG (1977), A Search for Better Linear Multistep Methods for Stiff Problems, Report R-77-899, Dept. of Computer Sci., Univ. of Illinois at Urbana-Champaign.
  • [A] NORDSIECK (1962), "On numerical integration of ordinary differential equations," Math. Comp., v. 16, pp. 22-49. MR 0136519 (24:B2552)
  • [M] R. OSBORNE (1966), "On Nordsieck's method for the numerical solution of ordinary differential equations," BIT, v. 6, pp. 51-57. MR 0195264 (33:3467)
  • [R] D. SKEEL (1973), Convergence of Multivalue Methods for Solving Ordinary Differential Equations, Report TR73-16, Dept. of Computing Sci., Univ. of Alberta, Edmonton.
  • [R] D. SKEEL & L. W. JACKSON (1977), "Consistency of Nordsieck methods," SIAM J. Numer. Anal., v. 14, pp. 910-924. MR 0455412 (56:13650)
  • [R] D. SKEEL & A. K. KONG (1977), "Blended linear multistep methods," ACM Trans. Math. Software, v. 3, pp. 326-345. MR 0461922 (57:1904)
  • [C] S. WALLACE & G. K. GUPTA (1973), "General linear multistep methods to solve ordinary differential equations," Austral. Comput. J., v. 5, pp. 62-69. MR 0362919 (50:15357)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65L05

Retrieve articles in all journals with MSC: 65L05

Additional Information

Keywords: Linear multistep formula, multistep formula, linear multistep method, multistep method, Nordsieck method, multivalue method, predictor-corrector method
Article copyright: © Copyright 1979 American Mathematical Society

American Mathematical Society