Runge-Kutta methods. These are one-step methods where the solution #{y} is advanced by one step #{h} as #{y₁=y₀+hk}, where #{k} is a cleverly chosen constant. The first order Runge-Kutta method is simply the Euler's method #{k=f(x₀,y₀)}. Second order Runge-Kutta method advances the solution by an auxiliary evaluation of the derivative:

#{k=k1/2}	:	#{k0 = f(x0, y0)}, #{y1/2 = y0 + h/2 k0}, #{k1/2 = f(x1/2 , y1/2)}, #{y1 = y0 + hk1/2}
#{k= 1/2 (k0+k1)}	:	#{k1 = f(x1, y0+hk0)}, #{y1 = y0 + h 1/2 (k0+k1)}.

The two methods can be combined into a third order method #{k= ¹/₆ k₀ + ⁴/₆ k_1/2 + ¹/₆ k₁}. Higher order R-K methods have been devised, with the most noted being the famous Runge-Kutta-Fehlberg fourth-fifth order method implemented in the renowned rkf45 (now superseded by "ode/rksuite").

Bulirsch-Stoer methods. The idea is to evaluate y₁ with several (ever smaller) step-sizes and then make an extrapolation to step-size zero.

Multi-step and predictor-corrector methods. Multi-step methods try to use the information about the function gathered at previous steps. For example the sought function y can be approximated as y(x)~=~y₁+y'₁(x-x₁)+c(x-x₁)², where the coefficient c can be found from the condition y(x₀)=y₀, which gives c=[y₀-y₁-y'₁(x₀-x₁)]/(x₀-x₁)². We can now make a prediction for y₂ as y(x₂) and calculate f₂=f(x₂,y(x₂)). Having the new information, f₂, we can improve the approximation, namely y(x)~=~y₁+y'₁(x-x₁)+c(x-x₁)²+d(x-x₁)²(x-x₀). The coefficient d is found from the condition y'(x₂)=f₂, which gives d=( f₂-y'₁-2c(x₂-x₁) )/ (2(x₂-x₁)(x₂-x₀)+(x₂-x₁)²), from which we get a corrected estimate y₂=y(x₂). The correction can serve as an estimate of the error.

Step-size control. Tolerance \tt{tol} is the maximal accepted error consistent with the required absolute acc and relative eps accuracies tol~=~(eps*|y|+acc)*√(h/b-a). Error err is e.g. estimated from comparing the solution for a full-step and two half-steps (the Runge principle): err~=~|y(h)~-~y(2(h/2))|/(2n-1), where n is the order of the algorithm used. The next step h_next is estimated according to the prescription h_next~=~h_previous*(^tol/_err)^power*Safety, where #{power}∼0.25, #{Safety}∼0.95

Problems

1. Implement a Runge-Kutta method with adaptive step-size for a single first order differential equation.
2. Implement a Prediction-Correction method with adaptive step-size for a single first order differential equation.
3. With these routines integrate the equation y'(x)~=~+xy from #{a}=0 to #{b}=10 with the initial condition #{y(a)}=1.