General linear methods

The most important process classes for ordinary differential equations are the Runge-Kutta processes , which use internal steps in each time step, and the multi-step processes , which fall back on a certain number of previous solution approximations, i.e. with two apparently completely different structures. To unify beat John C. Butcher , the class of general linear methods ( Engl. General Linear Methods = GLM) also in the expectation that in the general structure of new and better methods are found. In addition, basic statements such as consistency or stability properties only have to be formulated once. ${\displaystyle s}$

Runge-Kutta and multi-step processes

Both classes of procedures approximate the solution of the autonomous initial value problem in time steps and generate approximations at points . For motivation, the procedures are written in a slightly different form than in the article Runge-Kutta procedure , but equivalent to it: ${\displaystyle y(t)\in \mathbb {R} ^{d}}$ ${\displaystyle y'(t)=f{\big (}y(t){\big )},\ y(t_{0})=y_{0},}$ ${\displaystyle y_{n}\approx y(t_{n})}$ ${\displaystyle t_{n}=t_{n-1}+h}$

${\displaystyle Y_{i}=y_{n-1}+h\sum _{j=1}^{s}a_{ij}f(Y_{j}),\quad i=1,\ldots ,s,}$

${\displaystyle y_{n}=y_{n-1}+h\sum _{j=1}^{s}b_{j}f(Y_{j}).}$

For a general linear -step method with , the rule is as follows: ${\displaystyle m}$ ${\displaystyle \alpha _{0}=1}$

${\displaystyle y_{n}=-\sum _{j=1}^{m}\alpha _{j}y_{n-j}+h\sum _{j=0}^{m}\beta _{j}f(y_{n-j}).}$

Here only the values come from the current time step, all others from earlier. ${\displaystyle y_{n-1},f(y_{n-1}),f(y_{n})}$

Structure of general linear procedures

By combining the older information in a vector with old information, one obtains the general linear method with internal steps : ${\displaystyle y^{[n-1]}}$ ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle Y_{j}}$

${\displaystyle Y_{i}=h\sum _{j=1}^{s}a_{ij}f(Y_{j})+\sum _{j=1}^{r}u_{ij}y_{j}^{[n-1]},\quad i=1,\ldots ,s,}$

${\displaystyle y_{i}^{[n]}=h\sum _{j=1}^{s}b_{ij}f(Y_{j})+\sum _{j=1}^{r}v_{ij}y_{j}^{[n-1]},\quad i=1,\ldots ,r.}$

In the context of this process structure, the process is fully described by its coefficients, which can be summarized in matrices . Therefore, the procedure is again specified in a compact form by his Butcher tableau ${\displaystyle A=(a_{ij})\in \mathbb {R} ^{s\times s},\ B=(b_{ij})\in \mathbb {R} ^{r\times s},\ U=(u_{ij})\in \mathbb {R} ^{s\times r},\ V=(v_{ij})\in \mathbb {R} ^{r\times r}}$

${\displaystyle \left[{\begin{array}{c|c}A&U\\\hline B&V\end{array}}\right].}$

For the stability of these processes, one can consider their stability function .

Runge-Kutta methods as general linear methods

With the Runge-Kutta process , you can easily see that the classic procedures fit into this framework . Here is , the matrix corresponds to the one- vector consisting of all ones and is the Butcher tableau of the Runge-Kutta method ${\displaystyle r=1}$ ${\displaystyle U}$ ${\displaystyle e}$

${\displaystyle \left[{\begin{array}{c|c}A&U\\\hline B&V\end{array}}\right]=\left[{\begin{array}{c|c}A&e\\\hline b^{T}&1\end{array}}\right].}$

Multi-step processes as general linear processes

A favorable notation for multi-step methods depends on how many of the coefficients really differ from zero. With the simply structured implicit BDF procedure , the only requirement is , for example with . Here you put and and define . The new approximation must be introduced both as and as . Therefore, the first two lines in the table of the BDF process are the same: ${\displaystyle \alpha _{j},\beta _{j}}$ ${\displaystyle \beta _{0}\not =0}$ ${\displaystyle \sum _{j=0}^{m}\alpha _{j}y_{n-1}=h\beta _{0}f(y_{n})}$ ${\displaystyle \alpha _{0}=1}$ ${\displaystyle s=1}$ ${\displaystyle r=m}$ ${\displaystyle y^{[n-1]}=(y_{n-1},\ldots ,y_{n-m})}$ ${\displaystyle y_{n}}$ ${\displaystyle y_{n}=Y_{1}}$ ${\displaystyle y_{n}=y_{1}^{[n]}}$

${\displaystyle \left[{\begin{array}{c|c}A&U\\\hline B&V\end{array}}\right]=\left[{\begin{array}{c|cccc}\beta _{0}&-\alpha _{1}&\ldots &-\alpha _{m-1}&-\alpha _{m}\\\hline \beta _{0}&-\alpha _{1}&\ldots &-\alpha _{m-1}&-\alpha _{m}\\0&1&\ldots &0&0\\\vdots &&\ddots &&\vdots \\0&&&1&0\end{array}}\right]}$

The lower part of the matrix block corresponds to the shift of the old values ​​in the vector . Therefore this matrix has the form of a companion matrix (or its transpose ). ${\displaystyle V}$ ${\displaystyle y}$ ${\displaystyle V}$

In the Adams-Bashforth method , however, is only (namely −1). Here you choose and , as well . The tableau is here ${\displaystyle \alpha _{1}\not =0}$ ${\displaystyle s=1}$ ${\displaystyle r=m+1}$ ${\displaystyle y^{[n-1]}={\big (}y_{n-1},hf(y_{n-1}),\ldots ,hf(y_{n-m}){\big )}}$

${\displaystyle \left[{\begin{array}{c|c}A&U\\\hline B&V\end{array}}\right]=\left[{\begin{array}{c|cccccc}0&1&\beta _{1}&\ldots &\beta _{m-1}&\beta _{m}\\\hline 0&1&\beta _{1}&\ldots &\beta _{m-1}&\beta _{m}\\1&0&0&\ldots &0&0\\0&0&1&&0&0\\\vdots &&&\ddots &&\vdots \\0&&&&1&0\end{array}}\right]}$

The new function value is calculated with the third line of the tableau . You can see from this multiple representation that this formulation is not necessarily suitable for efficient implementation, but primarily serves to provide a uniform description of theoretical statements. ${\displaystyle y_{2}^{[n]}=f(y_{1}^{[n]})=f(Y_{1})=f(y_{n}))}$

With general linear multi-step procedures , however, you then have to include up to old values. ${\displaystyle r=2m}$

literature

• JC Butcher: Numerical methods for ordinary differential equations , John Wiley & Sons, 2nd ed., 2008.
• E. Hairer, G. Wanner: Solving Ordinary Differential Equations II, Stiff problems , Springer Verlag
• Z. Jaciewicz: General linear methods for ordinary differential equations , John Wiley & Sons, 2009.
• K. Strehmel, R. Weiner, H. Podhaisky: Numerics of ordinary differential equations - non -rigid, rigid and differential-algebraic equations , Springer Spectrum, 2012.