Equivalent forms of multistep formulas

Author:
Robert D. Skeel

Journal:
Math. Comp. **33** (1979), 1229-1250

MSC:
Primary 65L05

DOI:
https://doi.org/10.1090/S0025-5718-1979-0537967-4

Corrigendum:
Math. Comp. **47** (1986), 769.

MathSciNet review:
537967

Full-text PDF Free Access

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 , 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) formulas but not for P(EC)E formulas.

**[G]**G. D. Byrne and A. C. Hindmarsh,*A polyalgorithm for the numerical solution of ordinary differential equations*, ACM Trans. Math. Software**1**(1975), no. 1, 71–96. MR**0378432**, https://doi.org/10.1145/355626.355636**[G]**Germund Dahlquist,*Convergence and stability in the numerical integration of ordinary differential equations*, Math. Scand.**4**(1956), 33–53. MR**0080998**, https://doi.org/10.7146/math.scand.a-10454**[G]**Germund G. Dahlquist,*A special stability problem for linear multistep methods*, Nordisk Tidskr. Informations-Behandling**3**(1963), 27–43. MR**0170477****[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]**C. W. Gear,*The numerical integration of ordinary differential equations*, Math. Comp.**21**(1967), 146–156. MR**0225494**, https://doi.org/10.1090/S0025-5718-1967-0225494-5**[C]**C. William Gear,*Numerical initial value problems in ordinary differential equations*, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1971. MR**0315898****[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*-*stabile Verfahren hoher Konsistenzordnung*, Nr. 34, Fachbereich Mathematik (3), Technische Universität Berlin.**[G]**G. K. Gupta,*Some new high-order multistep formulae for solving stiff equations*, Math. Comp.**30**(1976), no. 135, 417–432. MR**0423812**, https://doi.org/10.1090/S0025-5718-1976-0423812-1**[G]**G. K. Gupta and C. S. Wallace,*Some new multistep methods for solving ordinary differential equations*, Math. Comp.**29**(1975), 489–500. MR**0373290**, https://doi.org/10.1090/S0025-5718-1975-0373290-5**[P]**Peter Henrici,*Discrete variable methods in ordinary differential equations*, John Wiley & Sons, Inc., New York-London, 1962. MR**0135729****[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]**Donald E. Knuth,*The art of computer programming*, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR**0378456****[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]**Arnold Nordsieck,*On numerical integration of ordinary differential equations*, Math. Comp.**16**(1962), 22–49. MR**0136519**, https://doi.org/10.1090/S0025-5718-1962-0136519-5**[M]**M. R. Osborne,*On Nordsieck’s method for the numerical solution of ordinary differential equations*, Nordisk Tidskr. Informations-Behandling**6**(1966), 51–57. MR**0195264****[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]**R. D. Skeel and L. W. Jackson,*Consistency of Nordsieck methods*, SIAM J. Numer. Anal.**14**(1977), no. 5, 910–924. MR**0455412**, https://doi.org/10.1137/0714061**[R]**Robert D. Skeel and Antony K. Kong,*Blended linear multistep methods*, ACM Trans. Math. Software**3**(1977), no. 4, 326–345. MR**0461922**, https://doi.org/10.1145/355759.355762**[C]**C. S. Wallace and G. K. Gupta,*General linear multistep methods to solve ordinary differential equations*, Austral. Comput. J.**5**(1973), 62–69. MR**0362919**

Retrieve articles in *Mathematics of Computation*
with MSC:
65L05

Retrieve articles in all journals with MSC: 65L05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1979-0537967-4

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