Euler and Runge-Kutta Methods

Definition Consider the initial value problem $y' = f(x, y)$, $y(x_0) = y_0$. Choose a step size $h > 0$ and set $x_n = x_0 + nh$. Euler’s method computes

The Euler polygon is the broken line joining the points $(x_0, y_0), (x_1, y_1), (x_2, y_2), \dots$. Each segment has the slope that the equation assigns to its left endpoint.

Definition The improved Euler method first predicts with an Euler step and then averages the slopes at both ends of the step.

It is the trapezoidal rule applied to

with the unknown endpoint value replaced by the Euler prediction.

Definition A Runge-Kutta method computes several slopes $k_1, \dots, k_s$ at trial points inside the step, each built from the previous ones, and advances with a weighted average of them. The weights are chosen so that the step agrees with the Taylor expansion of the true solution through as high a power of $h$ as possible. The classical fourth order method is

When $f$ depends only on $x$, this step is exactly Simpson’s rule on $[x_n, x_{n+1}]$ with the midpoint $x_n + \frac{h}{2}$.

Definition The local truncation error of a one-step method at step $n$ is the error made in that one step when it starts from the exact value, that is $y(x_{n+1})$ minus the result of the method’s step applied to $y(x_n)$. The global error at $x_n$ is $e_n = y(x_n) - y_n$, the accumulated difference after all steps. A method has order $p$ if its local error is $O(h^{p+1})$, and then for a smooth problem its global error on a fixed bounded interval is $O(h^p)$. Euler’s method has order $1$, improved Euler order $2$ and classical Runge-Kutta order $4$.

For Euler’s method there is an explicit bound. Suppose $f$ is continuous for $x_0 \le x \le b$ and all real $y$, and satisfies the Lipschitz condition

there for all $u$ and $v$, with a constant $L > 0$. Suppose also that the exact solution exists on $[x_0, b]$, is twice differentiable there, and has $\lvert y'' \rvert \le M$ on $[x_0, b]$. If the arithmetic is exact and the method starts from the exact value $y_0 = y(x_0)$, then for every $x_n \le b$

Definition Step-size refinement means repeating a computation with $h$ replaced by $\frac{h}{2}$ and comparing. Write $y_h$ for the result at a fixed point $x$ computed with step $h$. For a method of order $p$ the global error at $x$ is about $Ch^p$ for small $h$, with $C$ independent of $h$, so halving $h$ divides the error by about $2^p$, and the error of the finer result is estimated by

Definition Apply a method to the test equation $y' = \lambda y$ with $\lambda < 0$, whose solutions all decay to $0$. The method is absolutely stable for a step $h$ if its numerical solution also tends to $0$ for every starting value. Euler’s method gives $y_{n+1} = (1 + h\lambda) y_n$, so $y_n = (1 + h\lambda)^n y_0$, and it is absolutely stable exactly when

Every explicit Runge-Kutta method has some such limit. On the test equation its step multiplies $y_n$ by a polynomial in $h\lambda$ that is not constant, and a nonconstant polynomial grows without bound in absolute value as $h\lambda \to -\infty$, so a large enough step always makes the numbers grow.

Definition An exact solution is a differentiable function $y$ that satisfies $y' = f(x, y)$ and the initial condition on an interval containing $x_0$. A numerical solution is a finite list of values $y_n$ at the grid points $x_n$, which depends on the method and on $h$ and approximates $y(x_n)$ only where the exact solution exists and the method converges. Between grid points it gives no values unless you interpolate.