29.2. Families of integration methods#

Methods for the first-order IVP

(29.1)#\[\begin{split}\left\{ \begin{aligned} & \dot{\mathbf{y}} = \mathbf{f}(t,\mathbf{y}) \\ & \mathbf{y}(0) = \mathbf{y}_0 \ . \end{aligned}\right.\end{split}\]

29.2.1. One-step methods (I): Euler, Crank-Nicolson#

29.2.2. Multi-step methods#

Adams-Bashforth and Adams-Moulton. The integration of the first-order equation (29.1) between \(t_n\) and \(t_{n+1}\) reads

\[\mathbf{y}(t_{n+1}) - \mathbf{y}(t_n) = \int_{\tau = t_n}^{t_{n+1}} \mathbf{f}(\tau, \mathbf{y}(\tau)) \, d \tau \ .\]

AB and AM methods replace the function \(\mathbf{f}(t, \mathbf{y}(t))\) with a polynomial Lagrangian approximation \(\mathbf{p}_s(t) \simeq \mathbf{f}(t)\) built with values of \(\mathbf{f}(t_{n-k}, \mathbf{y}(t_{n-k}) )\), with \(k_{AB} = 0:s-1\) (AB are explicit methods) and \(k_{AM} = -1:s-1\) (AM are implicit methods).

Once the original function is replaced by its polynomial approximation, the integration can be performed exactly.

Backward Differentiation Formulas. BDF methods exploits the derivative of the polynomial approximation \(\mathbf{q}_s(t) \simeq \mathbf{y}(t)\). The value of the derivative \(\dot{\mathbf{q}}_s(t)\) evaluated in \((t_{n+1}, \mathbf{y}_{n+1})\) can be written as a linear combinations of the \(\{ \mathbf{y}_{n-k} \}_{k=-1:s-1}\) values. BDF immediately follows from the comparison

\[\begin{aligned} \mathbf{f}(t_{n+1}, \mathbf{y}_{n+1}) & = \dot{\mathbf{y}}(t_{n+1}) \simeq \dot{\mathbf{q}}_s(t) = \sum_{k=-1}^{s-1} a_k \mathbf{y}_{n-k} \end{aligned}\]

29.2.2.1. Adams-Bashforth (AB)#

For the derivation of the low-order AB methods, see Lagrange interpolation: Applications: Adams-Bashforth

29.2.2.2. Adams-Moulton (AM)#

For the derivation of the low-order AB methods, see Lagrange interpolation: Applications: Adams-Moulton

29.2.2.3. Backward Differentiation Formulas (BDF)#

For the derivation of the low-order AB methods, see Lagrange interpolation: Applications: BDF

29.2.3. One-step methods (II): Runge-Kutta (RK)#

Method.

\[y_{n+1} = y_{n} + h \sum_{m=1}^s b_m k_m \ ,\]

with

\[\begin{split}\begin{aligned} k_1 & = f(t_n,y_n) \\ k_2 & = f(t_n + h c_2, y_n + h a_{21} k_1 ) \\ \dots \\ k_s & = f\left(t_n + h c_s, y_n + h \sum_{j=1}^{s-1} a_{sj} k_j \right) \ . \end{aligned}\end{split}\]
Rationale

Starting from a \(n\)-order Taylor series

\[y(t+h) = \sum_{p=0}^{n} \frac{h^p}{p!} y^{(p)}(t) \ ,\]

and matching it with a linear combination of evaluations of the first-order derivative,

\[y_{n+1} = y_{n} + h \sum_{m=1}^s b_m k_m \ ,\]

with \(t_{n+1} = t_n + h\).

Butcher tableau

The coefficients of a RK method can be organized in Butcher tableau

\[\begin{split}\begin{array}{c|c} \mathbf{c} & \mathbf{A} \\ \hline & \mathbf{b}^T \end{array}\end{split}\]
\[\begin{split}\begin{array}{c|ccccc} 0 & & & & \\ c_2 & a_{21} & & & & \\ c_3 & a_{31} & a_{32} & & & \\ \vdots & \vdots & \vdots & \ddots & & \\ c_s & a_{s1} & a_{s2} & \dots & a_{s,s-1} & \\ \hline & b_1 & b_2 & \dots & b_{s-1} & b_s \end{array}\end{split}\]
Constraints
\[\sum_{j=1}^{s} b_j = 1 \ .\]

29.2.3.1. Example: RK2#

RK2 methods include mid-point, Heun and Ralston methods.

Derivation.

Starting from a \(2\)-order Taylor series, and matching it with a linear combination of evaluations of the first-order derivative.

\[\begin{split}\begin{aligned} y(t+h) & = y(t) + h y'(t) + \frac{h^2}{2} y''(t) + o(h^2) = \\ & = y(t) + h f(t, y(t)) + \frac{h^2}{2} \left[ f_t(t,y(t)) + y'(t) f_y(t,y(t)) \right] + o(h^2) = \\ & = y(t) + h f(t, y(t)) + \frac{h^2}{2} \left[ f_t(t,y(t)) + f(t,y(t)) f_y(t,y(t)) \right] + o(h^2) \ , \end{aligned}\end{split}\]

with \(y'(t) = f(t, y(t))\), so that \(y''(t) = f_t(t,y(t)) + y'(t) f_y(t,y(t))\).

RK approximation.

\[y_{n+1} = y_{n} + h( b_1 k_1 + b_2 k_2 ) \ ,\]

with

\[\begin{split}\begin{aligned} k_1 & = f(t_n,y_n) \\ k_2 & = f(t_n + h c_2, y_n + h a_{21} k_1 ) \ . \end{aligned}\end{split}\]

Expanding in Taylor series \(k_2\),

\[\begin{split}\begin{aligned} k_2 & = f(t_n + h c_2, y_n + h a_{21} k_1 ) = \\ & = f(t_n, y_n) + h c_2 f_t(t_n, y_n) + h a_{21} k_1 f_y(t_n, y_n) + O(h^2) \ , \end{aligned}\end{split}\]

inserting in the RK2 scheme

\[\begin{split}\begin{aligned} y_{n+1} & = y_n + h b_1 f(t_n,y_n) + h b_2 \left[ f(t_n, y_n) + h c_2 f_t(t_n, y_n) + h a_{21} k_1 f_y(t_n, y_n) \right] + o(h^2) = \\ & = y_n + h \left[ b_1 + b_2 \right] f(t_n, y_n) + h^2 b_2 c_2 f_t(t_n, y_n) + h^2 b_2 a_{21} f(t_n, y_n) f_y(t_n, y_n) + o(h^2) \ , \end{aligned}\end{split}\]

and matching coefficients of Taylor expansions, the coefficients of the RK method are computed as the solution of a underdetermined system of 3 equations with 4 unknowns

\[\begin{split}\begin{cases} b_1 + b_2 = 1 \\ b_2 c_2 = \frac{1}{2} \\ b_2 a_{21} = \frac{1}{2} \end{cases} \qquad , \qquad \begin{array}{c|cc} 0 & & \\ c_2 & a_{21} & \\ \hline & b_1 & b_2 \end{array} \end{split}\]

or leaving \(\alpha = c_2 = a_{21}\) as a free parameter,

\[\begin{split}\begin{cases} b_1 = 1 - \frac{1}{2 \alpha} \\ b_2 = \frac{1}{2 \alpha} \\ c_2 = \alpha \\ a_{21} = \alpha \end{cases} \qquad , \qquad \begin{array}{c|cc} 0 & & \\ \alpha & \alpha & \\ \hline & 1 - \frac{1}{2 \alpha} & \frac{1}{2 \alpha} \end{array} \end{split}\]

This system has infinite solutions. Different methods correspond to different choices among these solutions:

  • mid-point method, \(\alpha = \frac{1}{2}\)

  • Heun method, \(\alpha = 1\)

  • Ralston’s method (minimum truncation error todo prove it!), \(\alpha = \frac{2}{3}\)