Niklas Hedberg: Derivation of Runge-Kutta order conditions

In the field of numerical analysis to solve Ordinary Differential Equations (ODEs), Runge-Kutta (RK) methods take a sequence of first order approximations of the ODE and weights them in a linear combination for each time step. Given existence and uniqueness criteria, the numerical solution can therefore approximate the theoretical solution to a great deal of accuracy. The point of interest when constructing these methods is thus to ensure convergence. In order to do this, one compares the Taylor expansions of the "true" solution with that of the numerical. One matches the two up to and including the order of a particular derivative, we gain a RK method of that order. The strive for higher orders makes this matching difficult, and this paper concerns the derivation of the conditions required to construct a method of a certain order. This is done by connecting the Taylor expansions with rooted trees.VE is proposed.