Skip to main content

3  Numerical Integration of a Differential Equation

Chapter 6 (“Numerical Integration of a Differential Equation”) in Part IV of Papula (2015) gives an introduction to the numerical integration of ODEs. The symbols used in this chapter are listed in Table 3.1.

Table 3.1: Symbols in Chapter 03
Symbol Meaning Type Defined in
\(\mathrm{d}\) Differential (\(\mathrm{d}x\), \(\frac{\mathrm{d}y}{\mathrm{d}x}\)) Operator Ch. 02
\(\mathrm{e}\) Euler’s number Constant Example 2.1
\(f\) Function; right-hand side of the ODE \(y' = f(x,y)\) or \(u' = f(t,u)\) Function Definition 3.1, Equation 3.6
\(g\) Gravitational acceleration Constant Equation 2.30
\(h\) Step size of an integration scheme; grid spacing \(h = 1/(n+1)\) Scalar Definition 3.1
\(i\) Running index (component, row, eigenvalue number, spring number) Index Ch. 02
\(k\) Running index (time/iteration step, mode, eigenvalue number) Index Definition 3.1
\(k_1, \dots, k_4\) Increments of the Runge-Kutta method, \(k_i = h\,s_i\) Scalar Definition 3.7, Definition 3.8
\(l\) Length of the simple pendulum Constant Equation 2.30
\(n\) Order of an ODE; dimension of a matrix or system; number of steps Index Ch. 02, Definition 3.1
\(p\) Order of consistency, \(O(h^p)\) Index Definition 3.4
\(s_1, \dots, s_4\); \(\bar{s}\) Slope values of the Runge-Kutta method of order 4; mean slope Scalar Figure 3.7
\(t\) Time Scalar Ch. 02
\(t_k\) \(k\)-th time point of the grid; \(t_0\) initial time, \(t_f\) final time Scalar Example 3.2
\(x\) Independent variable (Ch. 02 §1–4, 03, 06, 08 eigenfunctions) Scalar Ch. 02
\(x_k, y_k\) Grid point \(x_k = x_0 + kh\) and approximation \(y_k \approx y(x_k)\) Scalar Definition 3.1
\(y\) Unknown function \(y(x)\) or vector of unknown functions; \(y', y'', y^{(n)}\) derivatives Function Ch. 02
\(y_0\) Initial value \(y(x_0)\) Scalar Ch. 02
\(y_1, \dots, y_n\) Components of the state vector \(S\) in the reduction of order (\(y_1 = y\), \(y_2 = y'\), …) or of the solution vector \(y\) of a system Function Theorem 2.14
\(y_1(k), y_2(k)\) Approximation of the components \(y_1\), \(y_2\) of the state vector in step \(k\) Scalar Example 3.2
\(O(h^p)\) Landau symbol (order of magnitude of the error) Operator Definition 3.4
\(P_0, P_k, Q, R, S\) Points in the geometric interpretation of the Euler and Runge-Kutta methods Point Definition 3.1, Figure 3.7
\(S\) State vector \(S(t)\); \(S_i\) its \(i\)-th component, \(S_0\) initial state Vector Ch. 02, Equation 3.4
\(\gamma_i\) Coefficient of a linear combination (weights of the RK2 method; expansion of the starting vector in eigenvectors; basis representation in the eigenspace) Scalar Equation 3.7
\(\Delta y_k\) Increment in step \(k\) Scalar Table 3.4
\(\eta_1, \eta_2\) Node parameters of the RK2 ansatz (fractions of \(h\) in the time and state directions) Scalar Equation 3.7
\(\varphi(t)\) Angle of deflection of the simple pendulum; \(\varphi_0\) initial deflection Function Equation 2.30
\(y', y'', y^{(n)}\) First, second, \(n\)-th derivative with respect to the independent variable Operator Ch. 02
\(\frac{\partial}{\partial t}\) Partial derivative Operator Ch. 02
\(A^{-1}\) Inverse Operator Example 3.2
local Line elements \(a, b, c, d\), straight line \(g\), and coordinates \(x_Q, y_Q, x_R, y_R, x_S, y_S\) of the construction in Figure 3.7; intermediate value \(y_{h/2}\) of the midpoint method local Figure 3.7, Table 3.4

3.1 Explicit Euler Method (Euler’s Polygon Method)

Definition 3.1 (Explicit Euler Method (Euler’s Polygon Method)) Let a first-order ODE \[ y' = f(x,y) \] with the initial point \(P_0 = (x_0, y_0)\) be given. The explicit Euler method (Euler’s polygon method) computes the solution curve \(y = y(x)\) point by point at the positions \(x_k = x_0 + kh\) with the step size \(h\) according to the iteration rule \[ y(x_k) \approx y_k = y_{k-1} + h f(x_{k-1}, y_{k-1}) \quad (k = 1, 2, \ldots, n), \tag{3.1}\] see Figure 3.1.

Coordinate system with an exponentially increasing exact solution curve and a dashed polygon of three straight segments of equal width h that runs below the curve. The vertices P0 to P3 are marked on the axes with their coordinates x0 to x3 and y0 to y3. A red double arrow shows the growing gap between the exact solution and the approximation at the last step.
Figure 3.1: Euler’s polygon method, computed for \(y'=y\) with \(h=0.6\): the exact solution curve \(y(x)\) (blue, solid) and the Euler polygon (orange, dashed) through the points \(P_k=(x_k,y_k)\) with \(x_k=x_0+kh\). Each segment has the slope \(f(x_{k-1},y_{k-1})\) of its left endpoint. The open circles mark the exact values \(y(x_k)\), the red arrow marks the deviation \(y(x_3)-y_3\) after three steps. Adapted from Papula (2015).

For practical computation, the computational scheme in Table 3.2 is used.

Table 3.2: Computational scheme for Euler’s method
\(k\) \(x\) \(y\) \(h \times f(x,y)\)
0 \(x_0\) \(y_0\) \(h \times f(x_0, y_0)\)
1 \(x_1 = x_0 + h\) \(y_1 = y_0 + h \times f(x_0, y_0)\) \(h \times f(x_1, y_1)\)
2 \(x_2 = x_0 + 2h\) \(y_2 = y_1 + h \times f(x_1, y_1)\) \(h \times f(x_2, y_2)\)
\(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\)
\(n\) \(x_n = x_0 + nh\) \(y_n = y_{n-1} + h \times f(x_{n-1}, y_{n-1})\) \(h \times f(x_n, y_n)\)

Example 3.1 (Euler’s Method) We solve the ODE \[ y' = \frac{\mathrm{d}y}{\mathrm{d}x} = \mathrm{e}^{-x} \] with the initial condition \(y(0) = -1\) numerically using Euler’s method and compare the result with the exact solution \(y(x) = -\mathrm{e}^{-x}\).

We use the step size \(h = 0.1\) and compute the approximate solution at the points \(x_k = 0.1\,k\) for \(k = 0, 1, \ldots, 10\), that is, for \(x = 0,\ 0.1,\ 0.2,\ \ldots,\ 1\). The right-hand side \(f(x,y) = \mathrm{e}^{-x}\) depends on \(x\) only. The iteration rule Equation 3.1 therefore reads \[ y_k = y_{k-1} + h\,\mathrm{e}^{-x_{k-1}} \quad (k = 1, 2, \ldots, 10). \] We start with \(x_0 = 0\) and \(y_0 = -1\):

  1. \(k = 1\): \(h f(x_0, y_0) = 0.1 \cdot \mathrm{e}^{0} = 0.1\), so \(y_1 = -1 + 0.1 = -0.9\).
  2. \(k = 2\): \(h f(x_1, y_1) = 0.1 \cdot \mathrm{e}^{-0.1} = 0.090484\), so \(y_2 = -0.9 + 0.090484 = -0.809516\).
  3. \(k = 3\): \(h f(x_2, y_2) = 0.1 \cdot \mathrm{e}^{-0.2} = 0.081873\), so \(y_3 = -0.809516 + 0.081873 = -0.727643\).

The remaining steps proceed in the same way. Table 3.3 contains the complete computational scheme from Table 3.2, extended by the exact values \(y(x_k) = -\mathrm{e}^{-x_k}\) and the error \(y_k - y(x_k)\).

Table 3.3: Euler’s method for \(y' = \mathrm{e}^{-x}\), \(y(0) = -1\), with \(h = 0.1\)
\(k\) \(x_k\) \(y_k\) \(h \times f(x_k,y_k)\) \(y(x_k)\) \(y_k - y(x_k)\)
0 \(0\) \(-1\) \(0.1\) \(-1\) \(0\)
1 \(0.1\) \(-0.9\) \(0.090484\) \(-0.904837\) \(0.004837\)
2 \(0.2\) \(-0.809516\) \(0.081873\) \(-0.818731\) \(0.009214\)
3 \(0.3\) \(-0.727643\) \(0.074082\) \(-0.740818\) \(0.013175\)
4 \(0.4\) \(-0.653561\) \(0.067032\) \(-0.670320\) \(0.016759\)
5 \(0.5\) \(-0.586529\) \(0.060653\) \(-0.606531\) \(0.020001\)
6 \(0.6\) \(-0.525876\) \(0.054881\) \(-0.548812\) \(0.022935\)
7 \(0.7\) \(-0.470995\) \(0.049659\) \(-0.496585\) \(0.025590\)
8 \(0.8\) \(-0.421337\) \(0.044933\) \(-0.449329\) \(0.027992\)
9 \(0.9\) \(-0.376404\) \(0.040657\) \(-0.406570\) \(0.030166\)
10 \(1.0\) \(-0.335747\) \(0.036788\) \(-0.367879\) \(0.032133\)

The approximation always lies above the exact solution, and the error grows from step to step. The reason is that the exact solution is concave because \(y'' = -\mathrm{e}^{-x} < 0\), and each segment of Euler’s method takes the slope at its left endpoint, which exceeds the mean slope over the interval. At \(x = 1\) the error is \(0.032\), roughly \(8.7\,\%\) of the exact value \(-0.367879\).

import numpy as np

ydot = lambda x, y: np.exp(-x) # ODE
h = 0.1 # step size
x = np.arange(0, 1 + h, h) # computational grid
y0 = -1 # initial value
n = len(x) # number of steps

# Explicit Euler method
y = np.zeros(n)
y[0] = y0
for k in range(0, n - 1):
    y[k + 1] = y[k] + h * ydot(x[k], y[k])
    print(f" k: {k:<2} x: {x[k]:<5.6f} y: {y[k]:<5.6f} h*f: {h*ydot(x[k], y[k]):<5.6f}")
k = n - 1
print(f" k: {k:<2} x: {x[k]:<5.6f} y: {y[k]:<5.6f} h*f: {h*ydot(x[k], y[k]):<5.6f}")
 k: 0  x: 0.000000 y: -1.000000 h*f: 0.100000
 k: 1  x: 0.100000 y: -0.900000 h*f: 0.090484
 k: 2  x: 0.200000 y: -0.809516 h*f: 0.081873
 k: 3  x: 0.300000 y: -0.727643 h*f: 0.074082
 k: 4  x: 0.400000 y: -0.653561 h*f: 0.067032
 k: 5  x: 0.500000 y: -0.586529 h*f: 0.060653
 k: 6  x: 0.600000 y: -0.525876 h*f: 0.054881
 k: 7  x: 0.700000 y: -0.470995 h*f: 0.049659
 k: 8  x: 0.800000 y: -0.421337 h*f: 0.044933
 k: 9  x: 0.900000 y: -0.376404 h*f: 0.040657
 k: 10 x: 1.000000 y: -0.335747 h*f: 0.036788
import matplotlib.pyplot as plt
%matplotlib inline
plt.figure(figsize = (9, 6))
plt.plot(x, y, 'bo--', label='Approximation')
plt.plot(x, -np.exp(-x), 'g', label='Exact')
plt.xlabel('x')
plt.ylabel('y(x)')
plt.grid()
plt.legend(loc='lower right')
plt.show()
Figure 3.2: Approximate solution of the differential equation with Euler’s method. Step size \(h = 0.1\).

In Figure 3.2 each point is a linear extrapolation of the previous point. Starting from the initial value, we thus obtain an approximation of the solution on the numerical grid. With \(h = 0.01\) the approximation improves, see Figure 3.3.

import numpy as np

ydot = lambda x, y: np.exp(-x) # ODE
h = 0.01 # step size
x = np.arange(0, 1 + h, h) # computational grid
y0 = -1 # initial value
n = len(x) # number of steps

# Explicit Euler method
y = np.zeros(n)
y[0] = y0
for k in range(0, n - 1):
    y[k + 1] = y[k] + h * ydot(x[k], y[k])

import matplotlib.pyplot as plt
%matplotlib inline
plt.figure(figsize = (9, 6))
plt.plot(x, y, '--', label='Approximation')
plt.plot(x, -np.exp(-x), 'g', label='Exact')
plt.xlabel('x')
plt.ylabel('y(x)')
plt.grid()
plt.legend(loc='lower right')
plt.show()
Figure 3.3: Approximate solution of the differential equation with Euler’s method. Step size \(h = 0.01\).

The method is called explicit because \(y_{k+1}\) is computed solely from the already known values \(x_k\) and \(y_k\).

3.2 Implicit Euler Method

The implicit Euler method differs from the explicit (forward) Euler method in that the function \(f\) is evaluated at the end point of the step rather than at the starting point.

Definition 3.2 (Implicit Euler Method) Let the initial value problem \[ y' = f(x,y), \quad y(x_0) = y_0, \] be given with a step size \(h > 0\) and the nodes \(x_k = x_0 + kh\), \(k = 0, 1, \dots\) The implicit Euler method computes the approximations \(y_k\) according to the iteration rule \[ y_{k+1} = y_k + hf(x_{k+1}, y_{k+1}), \quad k = 0, 1, \dots \tag{3.2}\]

The value \(f(x_{k+1}, y_{k+1})\) is not given explicitly, because \(y_{k+1}\) appears on both sides of the equation. The equation therefore has to be solved for \(y_{k+1}\) in every step. The explicit method does not need this computation, because its rule is already solved for \(y_{k+1}\). The values \(y_k\) approximate the values \(y(x_k)\) of the exact solution of the initial value problem. The smaller the step size \(h\), the higher the computational cost and the better the approximation.

3.3 Trapezoidal Method

Before showing how to solve the implicit Euler formula, we introduce another implicit formula, the trapezoidal formula. It is the average of the explicit and the implicit Euler formulas.

Definition 3.3 (Trapezoidal Method) The trapezoidal method computes the next point in each case according to the iteration rule \[ y_{k+1} = y_k + \frac{h}{2}\left( f(x_k, y_k) + f(x_{k+1}, y_{k+1}) \right). \tag{3.3}\]

The method can be read as a predictor-corrector scheme. First, the explicit Euler method yields a preliminary value for \(y_{k+1}\) (predictor step). This value is used to compute the slope at the end of the interval. The average of the slopes at the beginning and at the end of the interval then determines the final value \(y_{k+1}\).

3.4 Simple Pendulum: Euler Methods in Matrix Form

To show how the implicit schemes (Equation 3.2 and Equation 3.3) are solved, we consider the pendulum equation, which was reduced to a first-order system in Equation 2.37. With the state vector \(S(t) = (y_1(t), y_2(t))^T = (\varphi(t), \dot{\varphi}(t))^T\) it reads \[ \frac{\mathrm{d}S(t)}{\mathrm{d}t} = f(t, S(t)) = \begin{pmatrix} 0 & 1\\ -\frac{g}{l} & 0\\ \end{pmatrix} S(t). \tag{3.4}\]

Example 3.2 (Euler and Trapezoidal Methods for the Simple Pendulum) We consider the time points \(t_k = t_0 + kh\) and write \(y_1(k)\) and \(y_2(k)\) for the approximations of the components \(y_1(t_k)\) and \(y_2(t_k)\) in step \(k\). Substituting Equation 3.4 into the explicit Euler formula Equation 3.1 \[ y_{k+1} = y_{k} + h f(x_{k}, y_{k}) \] we obtain \[ \begin{pmatrix} y_1(k+1)\\ y_2(k+1)\\ \end{pmatrix} = \begin{pmatrix} y_1(k)\\ y_2(k)\\ \end{pmatrix} + h \begin{pmatrix} 0 & 1\\ -\frac{g}{l} & 0\\ \end{pmatrix} \begin{pmatrix} y_1(k)\\ y_2(k)\\ \end{pmatrix} = \begin{pmatrix} 1 & h\\ -\frac{gh}{l} & 1\\ \end{pmatrix} \begin{pmatrix} y_1(k)\\ y_2(k)\\ \end{pmatrix}. \]

Substituting Equation 3.4 into the implicit Euler formula Equation 3.2 \[ y_{k+1} = y_k + hf(x_{k+1}, y_{k+1}) \] yields \[ \begin{pmatrix} y_1(k+1)\\ y_2(k+1)\\ \end{pmatrix} = \begin{pmatrix} y_1(k)\\ y_2(k)\\ \end{pmatrix} + h \begin{pmatrix} 0 & 1\\ -\frac{g}{l} & 0\\ \end{pmatrix} \begin{pmatrix} y_1(k+1)\\ y_2(k+1)\\ \end{pmatrix} \] and hence \[ \begin{pmatrix} 1 & -h \\ \frac{gh}{l} & 1 \end{pmatrix} \begin{pmatrix} y_1(k+1)\\ y_2(k+1)\\ \end{pmatrix} = \begin{pmatrix} y_1(k)\\ y_2(k)\\ \end{pmatrix}. \] Rearranging (matrix inversion) yields \[ \begin{pmatrix} y_1(k+1)\\ y_2(k+1)\\ \end{pmatrix} = \begin{pmatrix} 1 & -h \\ \frac{gh}{l} & 1 \end{pmatrix}^{-1} \begin{pmatrix} y_1(k)\\ y_2(k)\\ \end{pmatrix}. \]

Substituting into the trapezoidal formula Equation 3.3 \[ y_{k+1} = y_k + \frac{h}{2}\left( f(x_k, y_k) + f(x_{k+1}, y_{k+1}) \right) \] we obtain \[ \begin{pmatrix} y_1(k+1)\\ y_2(k+1)\\ \end{pmatrix} = \begin{pmatrix} y_1(k)\\ y_2(k)\\ \end{pmatrix} + \frac{h}{2} \left\{ \begin{pmatrix} 0 & 1\\ -\frac{g}{l} & 0\\ \end{pmatrix} \begin{pmatrix} y_1(k)\\ y_2(k)\\ \end{pmatrix} + \begin{pmatrix} 0 & 1\\ -\frac{g}{l} & 0\\ \end{pmatrix} \begin{pmatrix} y_1(k+1)\\ y_2(k+1)\\ \end{pmatrix} \right\} \] and from this \[ \begin{pmatrix} 1 & -\frac{h}{2} \\ \frac{gh}{2l} & 1 \end{pmatrix} \begin{pmatrix} y_1(k+1)\\ y_2(k+1)\\ \end{pmatrix} = \begin{pmatrix} 1 & \frac{h}{2} \\ -\frac{gh}{2l} & 1 \end{pmatrix} \begin{pmatrix} y_1(k)\\ y_2(k)\\ \end{pmatrix}. \] Solving for \(y_{k+1}\) yields for the trapezoidal formula \[ \begin{pmatrix} y_1(k+1)\\ y_2(k+1)\\ \end{pmatrix} = \begin{pmatrix} 1 & -\frac{h}{2} \\ \frac{gh}{2l} & 1 \end{pmatrix}^{-1} \begin{pmatrix} 1 & \frac{h}{2} \\ -\frac{gh}{2l} & 1 \end{pmatrix} \begin{pmatrix} y_1(k)\\ y_2(k)\\ \end{pmatrix}. \]

These equations solve the initial value problem, because the next state \(S(t_{k+1})\) can be computed from every state \(S(t_k)\). In general, this is possible whenever the ODE is linear.

3.5 Numerical Error and Instability

For integration schemes for ODEs, two questions are central: accuracy and stability.

Definition 3.4 (Accuracy) The accuracy of an integration scheme describes how well it approximates the (usually unknown) exact solution as a function of the step size \(h\). It is stated in \(O\)-notation: a scheme has order \(p\) if its error behaves like \(O(h^p)\) for \(h \to 0\).

Definition 3.5 (Stability) The stability of an integration scheme is its ability to keep the error from growing while integrating forward in time. If the error does not grow, the scheme is stable; otherwise it is unstable. A scheme that is stable only for certain step sizes \(h\) is also referred to as unstable.

To illustrate stability problems, in Example 3.3 we solve the pendulum equation numerically using the explicit Euler method, the implicit Euler method, and the trapezoidal rule.

Example 3.3 (Programming the Euler Methods) We solve the pendulum equation Equation 3.4 over the time interval \([0,\,5]\) with the step size \(h = 0.1\) and the initial state \[ S_0 = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \] using the explicit Euler method, the implicit Euler method, and the trapezoidal rule. For the model parameters we use \(\sqrt{g/l} = 4\) (w in the code).

import numpy as np
from numpy.linalg import inv
import matplotlib.pyplot as plt

%matplotlib inline
# define step size
h = 0.1
# define numerical grid
t = np.arange(0, 5.1, h)
# oscillation freq. of pendulum
w = 4
s0 = np.array([[1], [0]])

m_e = np.array([[1, h],
               [-w**2*h, 1]])
m_i = inv(np.array([[1, -h],
               [w**2*h, 1]]))
m_t = np.dot(inv(np.array([[1, -h/2],
    [w**2*h/2,1]])), np.array(
      [[1,h/2], [-w**2*h/2, 1]]))

s_e = np.zeros((len(t), 2))
s_i = np.zeros((len(t), 2))
s_t = np.zeros((len(t), 2))

# do integrations
s_e[0, :] = s0.T
s_i[0, :] = s0.T
s_t[0, :] = s0.T

for j in range(0, len(t)-1):
    s_e[j+1, :] = np.dot(m_e,s_e[j, :])
    s_i[j+1, :] = np.dot(m_i,s_i[j, :])
    s_t[j+1, :] = np.dot(m_t,s_t[j, :])
plt.figure(figsize = (12, 8))
plt.plot(t,s_e[:,0],'b-')
plt.plot(t,s_i[:,0],'g:')
plt.plot(t,s_t[:,0],'r--')
plt.plot(t, np.cos(w*t), 'k')
plt.ylim([-3, 3])
plt.xlabel('t')
plt.ylabel(r'$\varphi(t)$')
plt.legend(['Explicit', 'Implicit', \
            'Trapezoidal', 'Exact'])
plt.show()
Figure 3.4: Comparison of the numerical solutions for the angle of deflection \(\varphi(t)\) of the pendulum with the explicit, implicit, and trapezoidal rules.

Figure 3.4 shows the angle \(\varphi\) over the time \(t\). The exact solution is a pure cosine wave. The explicit Euler method is clearly unstable. The solution of the implicit Euler method decays exponentially, which is not correct. The trapezoidal rule captures the solution correctly, although with a small phase shift that increases with time. Figure 3.5 shows the angular velocity \(\dot{\varphi}(t)\) of the pendulum.

# define step size
h = 0.1
# define numerical grid
t = np.arange(0, 5.1, h)
# oscillation freq. of pendulum
w = 4
s0 = np.array([[1], [0]])

m_e = np.array([[1, h],
               [-w**2*h, 1]])
m_i = inv(np.array([[1, -h],
               [w**2*h, 1]]))
m_t = np.dot(inv(np.array([[1, -h/2],
    [w**2*h/2,1]])), np.array(
      [[1,h/2], [-w**2*h/2, 1]]))

s_e = np.zeros((len(t), 2))
s_i = np.zeros((len(t), 2))
s_t = np.zeros((len(t), 2))

s_e[0, :] = s0.T
s_i[0, :] = s0.T
s_t[0, :] = s0.T
for j in range(0, len(t)-1):
    s_e[j+1, :] = np.dot(m_e,s_e[j, :])
    s_i[j+1, :] = np.dot(m_i,s_i[j, :])
    s_t[j+1, :] = np.dot(m_t,s_t[j, :])

plt.figure(figsize = (12, 8))
plt.plot(t,s_e[:,1],'b-')
plt.plot(t,s_i[:,1],'g:')
plt.plot(t,s_t[:,1],'r--')
plt.plot(t, -w*np.sin(w*t), 'k')
plt.ylim([-4*np.pi, 4*np.pi])
plt.xlabel('t')
plt.ylabel(r'$\dot{\varphi}(t)$')
plt.legend(['Explicit', 'Implicit', \
            'Trapezoidal', 'Exact'])
plt.show()
Figure 3.5: Comparison of the numerical solutions for the angular velocity \(\dot{\varphi}(t)\) of the pendulum with the explicit, implicit, and trapezoidal rules.

3.6 Runge-Kutta Methods

Runge-Kutta (RK) methods are among the most widely used methods for solving ODEs. They estimate the slope of the solution given by the ODE at several points within one time step. These estimates yield the next value without an explicit correction phase.

3.6.1 The Midpoint Method

More sophisticated methods achieve a higher order and thus more accuracy. One possibility is additional function evaluations, as the midpoint method in Definition 3.6 shows.

Definition 3.6 (The Midpoint Method) The midpoint method computes the next point in each case according to the iteration rule \[ y_{k+1} = y_k + h f \left( x_k + \frac{1}{2} h, y_k + \frac{1}{2} h f(x_k, y_k) \right). \]

The midpoint method improves on the explicit Euler method by evaluating the slope not only at the starting point but also at the middle of the interval. In its first step, it uses the slope at the starting point to predict the solution value halfway between \(x_k\) and \(x_{k+1}\): \[ y\left( x_k + \frac{h}{2} \right) = y(x_k) + \frac{h}{2}f(x_k, y(x_k)). \] The slope at this point then determines the value at the end of the interval: \[ y(x_{k+1}) = y(x_k) + h f\left(x_k + \frac{h}{2}, y\left(x_k + \frac{h}{2}\right)\right). \]

Example 3.4 (Midpoint Method) For the initial value problem \[ y' = f(x,y) = y + \mathrm{e}^x, \quad y(0) = 1, \] with the exact solution \(y(x) = (x+1)\, \mathrm{e}^x\), the midpoint method with step size \(h = 0.1\) can be carried out using the computational scheme in Table 3.4.

Table 3.4: Computational scheme for the midpoint method
\(k\) \(x\) \(y\) \(y_{\frac{h}{2}} = y + \frac{h}{2} f(x,y)\) \(\Delta y = h \times f(x + \frac{h}{2}, y_{\frac{h}{2}})\)
0 \(x_0\) \(y_0\) \(y_{\frac{h}{2},0} = y_0 + \frac{h}{2} \times f(x_0, y_0)\) \(\Delta y_0 = h \times f(x_0 + \frac{h}{2}, y_{\frac{h}{2},0})\)
1 \(x_1 = x_0 + h\) \(y_1 = y_0 + \Delta y_0\) \(y_{\frac{h}{2},1} = y_1 + \frac{h}{2} \times f(x_1, y_1)\) \(\Delta y_1 = h \times f(x_1 + \frac{h}{2}, y_{\frac{h}{2},1})\)
2 \(x_2 = x_1 + h\) \(y_2 = y_1 + \Delta y_1\) \(y_{\frac{h}{2},2} = y_2 + \frac{h}{2} \times f(x_2, y_2)\) \(\Delta y_2 = h \times f(x_2 + \frac{h}{2}, y_{\frac{h}{2},2})\)
\(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\) \(\vdots\)
\(n\) \(x_n = x_0 + nh\) \(y_n = y_{n-1} + \Delta y_{n-1}\)

An implementation of the midpoint method for Example 3.4 in Python reads:

import numpy as np

ydot = lambda x, y: y + np.exp(x) # ODE
h = 0.1 # step size
h2 = h/2
x = np.arange(0, 1 + h, h) # computational grid
y0 = 1 # initial value
n = len(x) # number of steps

# Midpoint method
y = np.zeros(n)
y2 = np.zeros(n)
y[0] = y0
for k in range(0, n - 1):
    y2[k] = y[k] + h2 * ydot(x[k], y[k])
    y[k + 1] = y[k] + h * ydot(x[k] + h2, y2[k])
    print(f" k: {k:<2} x: {x[k]:<5.1f} y: {y[k]:<5.8f} y2: {y2[k]:<5.8f} h*f: {h*ydot(x[k] + h2, y2[k]):<5.8f}")
k = n - 1
print(f" k: {k:<2} x: {x[k]:<5.1f} y: {y[k]:<5.8f} y2: {y2[k]:<5.8f} h*f: {h*ydot(x[k] + h2, y2[k]):<5.8f}")
 k: 0  x: 0.0   y: 1.00000000 y2: 1.10000000 h*f: 0.21512711
 k: 1  x: 0.1   y: 1.21512711 y2: 1.33114201 h*f: 0.24929763
 k: 2  x: 0.2   y: 1.46442474 y2: 1.59871611 h*f: 0.28827415
 k: 3  x: 0.3   y: 1.75269889 y2: 1.90782677 h*f: 0.33268943
 k: 4  x: 0.4   y: 2.08538832 y2: 2.26424897 h*f: 0.38325612
 k: 5  x: 0.5   y: 2.46864444 y2: 2.67451272 h*f: 0.44077657
 k: 6  x: 0.6   y: 2.90942101 y2: 3.14599800 h*f: 0.50615388
 k: 7  x: 0.7   y: 3.41557489 y2: 3.68704127 h*f: 0.58040413
 k: 8  x: 0.8   y: 3.99597902 y2: 4.30705502 h*f: 0.66467019
 k: 9  x: 0.9   y: 4.66064921 y2: 5.01666182 h*f: 0.76023715
 k: 10 x: 1.0   y: 5.42088636 y2: 0.00000000 h*f: 0.28576511
import matplotlib.pyplot as plt
%matplotlib inline
plt.figure(figsize = (9, 6))
plt.plot(x, y, 'bo--', label='Approximation')
plt.plot(x, (x+1)*np.exp(x), 'g', label='Exact')
plt.xlabel('x')
plt.ylabel('y(x)')
plt.grid()
plt.legend(loc='lower right')
plt.show()
Figure 3.6: Approximate solution of the differential equation \(y'=y+\mathrm{e}^x\) with the midpoint method. Step size \(h = 0.1\).

The midpoint method belongs to the family of Runge-Kutta methods; it is a second-order Runge-Kutta method.

3.6.2 Derivation of the Runge-Kutta Methods

Euler’s method approximates the state \(S\) with the first two terms of the Taylor series, that is, linearly: \[ S(t_{k+1}) = S(t_k + h) = S(t_k) + h \cdot S'(t_k). \]

Further terms of the Taylor series improve the accuracy of the numerical integration considerably: \[ S(t_{k+1}) = S(t_k + h) = S(t_k) + S'(t_k)h + \frac{1}{2!}S''(t_k)h^2 + \cdots + \frac{1}{n!}S^{(n)}(t_k)h^n. \tag{3.5}\]

This would require deriving the expressions for \(S''(t_k), S'''(t_k), \dots, S^{(n)}(t_k)\). The RK methods avoid this additional work. They are based on truncated Taylor series but do not require higher derivatives.

3.6.2.1 Second-Order Runge-Kutta Method

We derive the second-order Runge-Kutta method. Let \[ \frac{\mathrm{d}S(t)}{\mathrm{d}t} = f(t,S(t)). \tag{3.6}\] We assume an integration formula of the form \[ S(t + h) = S(t) + \gamma_1 f(t, S(t))h + \gamma_2 f\big(t+\eta_1 h, S(t)+\eta_2 hf(t, S(t))\big)h \tag{3.7}\] that requires no derivatives of \(S(t)\) beyond first order. Derivatives of second and higher order arise from combinations of \(f(t, S(t))\) and \(f\big(t+\eta_1 h, S(t)+\eta_2 hf(t, S(t))\big)\). We determine the parameters \(\gamma_1, \gamma_2, \eta_1, \eta_2\) by comparing Equation 3.7 with the second-order Taylor series.

Proposition 3.1 (Order Conditions of the Second-Order Runge-Kutta Ansatz) For every right-hand side \(f\), the integration formula Equation 3.7 agrees with the Taylor series Equation 3.5 up to terms of order \(h^3\) if and only if \[ \gamma_1 + \gamma_2 = 1, \quad \gamma_2\eta_1=\frac{1}{2}, \quad \gamma_2\eta_2=\frac{1}{2}. \tag{3.8}\]

Proof. The second-order Taylor series reads \[ S(t + h) = S(t) + S'(t)h + \frac{1}{2!}S''(t)h^2 = S(t) + f(t, S(t))h + \frac{1}{2!}f'(t, S(t))h^2. \tag{3.9}\] Because of Equation 3.6, the time derivative of \(f\) is \[ f'(t, S(t)) = \frac{\partial f}{\partial t} + \frac{\partial f}{\partial S}\frac{\mathrm{d}S}{\mathrm{d}t} = \frac{\partial f}{\partial t} + \frac{\partial f}{\partial S}f. \] Hence Equation 3.9 can be written as \[ S(t + h) = S + fh + \frac{1}{2!}\Big(\frac{\partial f}{\partial t} + \frac{\partial f}{\partial S}f\Big)h^2. \tag{3.10}\] We expand the last term in Equation 3.7 with the Taylor series in several variables: \[ f(t+\eta_1 h, S+\eta_2 hf) \approx f + \frac{\partial f}{\partial t}\eta_1 h + \eta_2 h\frac{\partial f}{\partial S}f. \] Hence Equation 3.7 becomes \[ S(t + h) = S + (\gamma_1+\gamma_2)fh + (\gamma_2\eta_1)\frac{\partial f}{\partial t}h^2 + (\gamma_2\eta_2)\frac{\partial f}{\partial S}fh^2. \tag{3.11}\] Comparing the coefficients of Equation 3.10 and Equation 3.11 yields Equation 3.8.

Since Equation 3.8 has four unknowns and only three equations, we can choose one parameter freely and determine the remaining ones from it. A popular choice is \[ \gamma_1 =\frac{1}{2}, \quad \gamma_2 =\frac{1}{2}, \quad \eta_1 =1, \quad \eta_2=1. \]

Definition 3.7 (Second-Order Runge-Kutta Method) With parameters \(\gamma_1, \gamma_2, \eta_1, \eta_2\) that satisfy Equation 3.8 and the increments \[ \begin{aligned} k_1 &= h f(t_k, S(t_k)),\\ k_2 &= h f\left(t_k + \eta_1 h, S(t_k) + \eta_2 k_1\right) \end{aligned} \] the second-order Runge-Kutta method computes the next state as \[ S(t_{k+1}) \approx S(t_k) + \gamma_1 k_1 + \gamma_2 k_2. \] For \(\gamma_1 = \gamma_2 = \frac{1}{2}\) and \(\eta_1 = \eta_2 = 1\), this gives \(S(t_{k+1}) \approx S(t_k) + \frac{1}{2}(k_1 + k_2)\).

3.6.2.2 Runge-Kutta Method of Order 4

A classical method for integrating ODEs with high accuracy is the fourth-order Runge-Kutta method (RK4). It can be derived from the Taylor series similarly to Section 3.6.2.1. Here we motivate it geometrically, see Figure 3.7.

A convex, increasing exact solution curve passes through the initial point P0. Dashed straight lines lead from P0 to the auxiliary points Q and R at the middle of the interval and S at its end; short arrows at these points indicate the respective slope. A red straight line g leads from P0 to the end point P1, which lies just below the point of the exact solution at x1; on the right, y1 and y(x1) are drawn as dimension arrows.
Figure 3.7: Geometric interpretation of one step of the Runge-Kutta method of order 4 (computed for \(y' = 2xy\), \(P_0 = (0.3,\,0.5)\), \(h = 1\)). From the initial point \(P_0\), straight lines with the slopes \(s_1\) (line element \(a\)), \(s_2\) and \(s_3\) lead to the auxiliary points \(Q\) and \(R\) at \(x_0 + h/2\) and \(S\) at \(x_1 = x_0 + h\). The line elements \(b\), \(c\), \(d\) at \(Q\), \(R\), \(S\) have the slopes \(s_2\), \(s_3\), \(s_4\). The straight line \(g\) with the mean slope \(\bar{s} = \frac{1}{6}(s_1 + 2s_2 + 2s_3 + s_4)\) leads to the end point \(P_1\), whose ordinate \(y_1\) approximates the exact solution \(y(x_1)\). Adapted from Papula (2015).

Starting from the initial point \(P_0\), we move along a straight line \(g\) with the mean slope \(\bar{s}\) to the end of the interval \(x_1 = x_0 + h\). The ordinate \(y_1\) of the end point \(P_1\) reached in this way is an approximation of the sought solution \(y(x_1)\). The mean slope is determined from four slope values, one at each of the two boundary points of the interval and two at the middle of the interval. The values at the middle of the interval enter the mean slope \(\bar{s}\) with a larger weight.

TipSummary: Runge-Kutta Method of Order 4
  1. From \(P_0\) with slope \(s_1\) by \(h/2\) to \(Q\); determine the slope \(s_2\) there.
  2. From \(P_0\) with slope \(s_2\) by \(h/2\) to \(R\); determine the slope \(s_3\) there.
  3. From \(P_0\) with slope \(s_3\) by \(h\) to \(S\); determine the slope \(s_4\) there.
  4. From \(P_0\) with the mean slope \(\bar{s} = \frac{1}{6}(s_1 + 2s_2 + 2s_3 + s_4)\) by \(h\) to \(P_1\).

Papula (2015) computes with the increments \(k_i = h\,s_i\) instead of the slopes \(s_i\).

The first slope \(s_1 = f(x_0, y_0)\) is the slope of the tangent to the solution curve at the initial point \(P_0\) (line element \(a\)). Along this tangent we move from \(P_0\) to the middle of the interval and reach the point \(Q\) with the coordinates \[ x_Q = x_0 + \frac{h}{2} \qquad \text{and} \qquad y_Q= y_0 + \frac{1}{2} h \times f(x_0, y_0) = y_0 + \frac{k_1}{2}, \qquad k_1 = h \times f(x_0, y_0). \] The solution curve through \(Q\) has the line element \(b\) there with the slope \[ s_2 = f\left(x_0 + \frac{h}{2}, y_0 + \frac{k_1}{2}\right). \] Parallel to the line element \(b\), we again move from \(P_0\) to the middle of the interval and reach the point \(R\) with the coordinates \[ x_R = x_0 + \frac{h}{2} \qquad \text{and} \qquad y_R = y_0 + \frac{1}{2}h \times s_2 = y_0 + \frac{k_2}{2}, \qquad k_2 = h \times s_2. \] The solution curve through \(R\) has the line element \(c\) there with the slope \[ s_3 = f\left(x_0 + \frac{h}{2}, y_0 + \frac{k_2}{2}\right). \] Parallel to the line element \(c\), we move from \(P_0\) to the end of the interval and reach the point \(S\) with the coordinates \[ x_S = x_0 + h \qquad \text{and} \qquad y_S = y_0 + h \times s_3 = y_0 + k_3, \qquad k_3 = h \times s_3. \] The solution curve through \(S\) has the line element \(d\) there with the slope \[ s_4 = f(x_0 + h, y_0 + k_3). \] The slope of the straight line \(g\) from the initial point \(P_0\) to the end point \(P_1\) is the weighted average of the four slope values: \[ \bar{s} = \frac{1}{6}(s_1 + 2s_2 + 2s_3 + s_4). \]

Definition 3.8 (Runge-Kutta Method of Order 4) Let a first-order ODE \[ y' = f(x,y) \] be given with the initial point \(P_0 = (x_0, y_0)\), the step size \(h = (x_n - x_0)/n\), and the nodes \(x_i = x_{i-1} + h\). The Runge-Kutta method of order 4 computes the approximations \(y_i \approx y(x_i)\) according to the rule \[ \begin{aligned} k_1 &= h f(x_{i-1}, y_{i-1}), \\ k_2 &= h f\left(x_{i-1} + \frac{h}{2}, y_{i-1} + \frac{k_1}{2}\right), \\ k_3 &= h f\left(x_{i-1} + \frac{h}{2}, y_{i-1} + \frac{k_2}{2}\right), \\ k_4 &= h f(x_{i-1} + h, y_{i-1} + k_3), \\ y_i &= y_{i-1} + \frac{1}{6} (k_1 + 2 k_2 + 2 k_3 + k_4). \end{aligned} \]

Unlike Euler’s polygon method, the RK4 method uses a mean slope value \(\bar{s}\) for the slope of the substitute straight line. It takes into account the slope behavior of the solution curve at the two boundary points and at the middle of the interval with different weights. The polygon method, in contrast, uses only the slope \(s_1 = f(x_0, y_0)\) at the initial point \(P_0\).