General linear methods

Numerical methods for first-order ordinary differential equations approximate solutions to initial value problems of the form

${\displaystyle y'=f(t,y),\quad y(t_{0})=y_{0}.}$

The result is approximations for the value of ${\displaystyle y(t)}$ at discrete times ${\displaystyle t_{i}}$:

${\displaystyle y_{i}\approx y(t_{i})\quad {\text{where}}\quad t_{i}=t_{0}+ih,}$

where h is the time step (sometimes referred to as ${\displaystyle \Delta t}$).

We follow Butcher (2006), pps 189–190 for our description, although we note that this method can be found elsewhere.

General linear methods make use of two integers, ${\displaystyle r}$, the number of time points in history and ${\displaystyle s}$, the number of collocation points. In the case of ${\displaystyle r=1}$, these methods reduce to classical Runge–Kutta methods, and in the case of ${\displaystyle s=1}$, these methods reduce to linear multistep methods.

Stage values ${\displaystyle Y_{i}}$ and stage derivatives, ${\displaystyle F_{i},i=1,2,\dots s}$ are computed from approximations, ${\displaystyle y_{i}^{[n-1]},i=1,\dots ,r}$, at time step ${\displaystyle n}$:

${\displaystyle y^{[n-1]}=\left[{\begin{matrix}y_{1}^{[n-1]}\\y_{2}^{[n-1]}\\\vdots \\y_{r}^{[n-1]}\\\end{matrix}}\right],\quad y^{[n]}=\left[{\begin{matrix}y_{1}^{[n]}\\y_{2}^{[n]}\\\vdots \\y_{r}^{[n]}\\\end{matrix}}\right],\quad Y=\left[{\begin{matrix}Y_{1}\\Y_{2}\\\vdots \\Y_{s}\end{matrix}}\right],\quad F=\left[{\begin{matrix}F_{1}\\F_{2}\\\vdots \\F_{s}\end{matrix}}\right]=\left[{\begin{matrix}f(Y_{1})\\f(Y_{2})\\\vdots \\f(Y_{s})\end{matrix}}\right].}$

The stage values are defined by two matrices, ${\displaystyle A=[a_{ij}]}$ and ${\displaystyle U=[u_{ij}]}$:

${\displaystyle Y_{i}=\sum _{j=1}^{s}a_{ij}hF_{j}+\sum _{j=1}^{r}u_{ij}y_{j}^{[n-1]},\qquad i=1,2,\dots ,s,}$

and the update to time ${\displaystyle t^{n}}$ is defined by two matrices, ${\displaystyle B=[b_{ij}]}$ and ${\displaystyle V=[v_{ij}]}$:

${\displaystyle y_{i}^{[n]}=\sum _{j=1}^{s}b_{ij}hF_{j}+\sum _{j=1}^{r}v_{ij}y_{j}^{[n-1]},\qquad i=1,2,\dots ,r.}$

Given the four matrices, ${\displaystyle A,U,B}$ and ${\displaystyle V}$, one can compactly write the analogue of a Butcher tableau as,

${\displaystyle \left[{\begin{matrix}Y\\y^{[n]}\end{matrix}}\right]=\left[{\begin{matrix}A\otimes I&U\otimes I\\B\otimes I&V\otimes I\end{matrix}}\right]\left[{\begin{matrix}hF\\y^{[n-1]}\end{matrix}}\right],}$

where ${\displaystyle \otimes }$ stands for the tensor product.

We present an example described in (Butcher, 1996).[7] This method consists of a single 'predicted' step, and 'corrected' step, that uses extra information about the time history, as well as a single intermediate stage value.

An intermediate stage value is defined as something that looks like it came from a linear multistep method:

${\displaystyle y_{n-1/2}^{*}=y_{n-2}+h\left({\frac {9}{8}}f(y_{n-1})+{\frac {3}{8}}f(y_{n-2})\right).}$

An initial 'predictor' ${\displaystyle y_{n}^{*}}$ uses the stage value ${\displaystyle y_{n-1/2}^{*}}$ together with two pieces of time history:

${\displaystyle y_{n}^{*}={\frac {28}{5}}y_{n-1}-{\frac {23}{5}}y_{n-2}+h\left({\frac {32}{15}}f(y_{n-1/2}^{*})-4f(y_{n-1})-{\frac {26}{15}}f(y_{n-2})\right),}$

and the final update is given by:

${\displaystyle y_{n}={\frac {32}{31}}y_{n-1}-{\frac {1}{31}}y_{n-2}+h\left({\frac {5}{31}}f(y_{n}^{*})+{\frac {64}{93}}f(y_{n-1/2}^{*})+{\frac {4}{31}}f(y_{n-1})-{\frac {1}{93}}f(y_{n-2})\right).}$

The concise table representation for this method is given by:

${\displaystyle \left[{\begin{array}{ccc|cccc}0&0&0&0&1&{\frac {9}{8}}&{\frac {3}{8}}\\{\frac {32}{15}}&0&0&{\frac {28}{5}}&-{\frac {23}{5}}&-4&-{\frac {26}{15}}\\{\frac {64}{93}}&{\frac {5}{31}}&0&{\frac {32}{31}}&-{\frac {1}{31}}&{\frac {4}{31}}&-{\frac {1}{93}}\\\hline {\frac {64}{93}}&{\frac {5}{31}}&0&{\frac {32}{31}}&-{\frac {1}{31}}&{\frac {4}{31}}&-{\frac {1}{93}}\\0&0&0&1&0&0&0\\0&0&1&0&0&0&0\\0&0&0&0&0&1&0\\\end{array}}\right].}$

• Runge–Kutta methods
• Linear multistep methods
• Numerical methods for ordinary differential equations

• Butcher, John C. (January 1965). "A Modified Multistep Method for the Numerical Integration of Ordinary Differential Equations". Journal of the ACM. 12 (1): 124–135. doi:10.1145/321250.321261. S2CID 36463504.
• Gear, C.W. (1965). "Hybrid Methods for Initial Value Problems in Ordinary Differential Equations". Journal of the Society for Industrial and Applied Mathematics, Series B: Numerical Analysis. 2 (1): 69–86. Bibcode:1965SJNA....2...69G. doi:10.1137/0702006. hdl:2027/uiuo.ark:/13960/t4rj60q8s. S2CID 122744897.
• Gragg, William B.; Hans J. Stetter (April 1964). "Generalized Multistep Predictor-Corrector Methods". Journal of the ACM. 11 (2): 188–209. doi:10.1145/321217.321223. S2CID 17118462.
• Hairer, Ernst; Wanner, Wanner (1973), "Multistep-multistage-multiderivative methods for ordinary differential equations", Computing, 11 (3): 287–303, doi:10.1007/BF02252917, S2CID 25549771.

• General Linear Methods