Higher order: Taylor’s series

We can go a step beyond Euler’s method keeping up to second order terms in the expansion around $x_0$. Doing so we obtain $$y(x+\Delta x)=y(x)+y'(x)\Delta x+\frac{1}{2}y''(x)(\Delta x)^2+O(\Delta x^3)$$ from the ODE we get $$\begin{darray}{rcl} y'(x)&=&f(x,y), \\ y''(x)&=&\frac{df}{dx}=\frac{\partial f}{\partial x}+\frac{\partial f}{\partial y}\frac{dy}{dx}=\frac{\partial f}{\partial x}+\frac{\partial f}{\partial y} f \end{darray}$$

Substituting in the Taylor expansion we obtain

where all the functions and derivatives are evaluated in $(x_n,y_n)$.

Multistep or Predictor-Corrector methods

We can achieve higher accuracy by relating $y_{n+1}$ not only to $y_n$, but also to points further in the past $y_{n-1},y_{n-2},...$ To derive such formulas we can formally integrate exactly the equation of motion to obtain: $$y_{n+1}=y_n+\int_{x_n}^{x_{n+1}}f(x,y)dx$$

The problem is that we don’t know $f(x,y)$ over the interval $(x_n,x_{n+1})$. However, we can use the values of $y$ at $x_n$ and $x_{n-1}$ to provide a linear extrapolation: $$f=\frac{(x-x_{n-1})}{\Delta x}f_n-\frac{(x-x_n)}{\Delta x} f_{n-1}+O(\Delta x^2),$$ with $f_n=f(x_n,y_n)$. Inserting into the integral we obtain $$y_{n+1}=y_n+\Delta x(\frac{3}{2}f_n-\frac{1}{2}f_{n-1})+O(\Delta x^3)$$ Note that the value of $y_0$ is not sufficient information to get this algorithm started. The value of $y_1$ has to be obtained first by some other procedure, like the ones described previously. This means that the method is not "self starting".

Runge-Kutta methods

2nd order Runge-Kutta

Euler’s method rests on the idea that the slope at one point can be used to extrapolate to the next. A plausible idea to make a better estimate of the slope is to extrapolate to a point halfway across the interval, and then to use the derivative at this point to extrapolate across the whole interval. Thus,

It has the same accuracy as the Taylor series. It requires the evaluation of $f$ twice for each step.

4th order Runge-Kutta

Similar ideas can be used to derive a 3rd or 4th order Runge-Kutta method. It has been found by experience that the best balance between accuracy and computational effort is given by a fourth-order algorithm. Such a method would require evaluating $f$ four times at each step, with a local accuracy of $O(\Delta x^5)$. It can be written as follows: $$\begin{darray}{rcl} k_1&=&\Delta x f(x_n,y_n), \\ k_2&=&\Delta x f(x_n+\Delta x/2,y_n+k_1/2), \\ k_3&=&\Delta x f(x_n+\Delta x/2,y_n+k_2/2), \\ k_4&=&\Delta x f(x_n+\Delta x,y_n+k_3), \\ y_{n+1}&=&y_n+\frac{1}{6}(k_1+2k_2+2k_3+k_4)+O(\Delta x^5).\end{darray}$$

Runge-Kutta method are self-starting, meaning that they can be used to obtain the first few iterations for a non self-starting algorithm.

Challenge 1.2

Repeat the calculation in Challenge 1.1 using 4th order Runge-Kutta