Trees and numerical methods for ordinary differential equations. (English) Zbl 1184.65072

Butcher, J. C.

Numer. Algorithms 53, No. 2-3, 153-170 (2010).

Summary: This paper presents a review of the role played by trees in the theory of Runge-Kutta methods. The use of trees is in contrast to early publications on numerical methods, in which a deceptively simpler approach was used. This earlier approach is not only non-rigorous, but also incorrect. It is now known, for example, that methods can have different orders when applied to a single equation and when applied to a system of equations; the earlier approach cannot show this. Trees have a central role in the theory of Runge-Kutta methods and they also have applications to more general methods, involving multiple values and multiple stages.

MSC:

65L06	Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations
65L05	Numerical methods for initial value problems involving ordinary differential equations
34A34	Nonlinear ordinary differential equations and systems
05C05	Trees

Keywords:

Runge-Kutta methods; trees; order conditions; Taylor expansions

References:

[1]	Butcher, J.C.: Coefficients for the study of Runge–Kutta integration processes. J. Aust. Math. Soc. 3, 185–201 (1963) · Zbl 0223.65031
[2]	Butcher, J.C.: On the integration processes of A. Huta. J. Aust. Math. Soc. 3, 202–206 (1963) · Zbl 0223.65032
[3]	Butcher, J.C.: An algebraic theory of integration methods. Math. Comp. 26, 79–106 (1972) · Zbl 0258.65070
[4]	Butcher, J.C.: On fifth order Runge–Kutta methods. BIT 35, 202–209 (1995) · Zbl 0837.65073
[5]	Butcher, J.C.: Numerical Methods for Ordinary Differential Equations, 2nd edn. Wiley, Chichester (2008) · Zbl 1167.65041
[6]	Gill, S.: A process for the step-by-step integration of differential equations in an automatic digital computing machine. Proc. Camb. Philos. Soc. 47, 96–108 (1951) · Zbl 0042.13202
[7]	Hairer, E., Nørsett, S.P., Wanner, G.: Solving Ordinary Differential Equations I: Nonstiff Problems, 2nd edn. Springer, Berlin (1993) · Zbl 0789.65048
[8]	Hairer, E., Wanner, G.: On the Butcher group and general multi-value methods. Computing 13, 1–15 (1974) · Zbl 0293.65050
[9]	Heun, K.: Neue methoden zur approximativen integration der differentialgleichungen einer unabhängigen Veränderlichen. Z. Math. Phys. 45, 23–38 (1900) · JFM 31.0333.02
[10]	Huta, A.: Une amélioration de la méthode de Runge–Kutta–Nyström pour la résolution numérique des équations différentielles du premier ordre. Acta Fac. Nat. Univ. Comen. Math. 1, 201–224 (1956) · Zbl 0074.10803
[11]	Kutta, W.: Beitrag zur näherungsweisen integration totaler differentialgleichungen. Z. Math. Phys. 46, 435–453 (1901) · JFM 32.0316.02
[12]	Nyström, E.J.: Über die numerische integration von differentialgleichungen. Acta Soc. Scient. Fenn. 50(13), 55pp. (1925) · JFM 51.0427.01
[13]	Runge, C.: Über die numerische Auflösung von differentialgleichungen. Math. Ann. 46, 167–178 (1895) · JFM 26.0341.01