Runge-Kutta method, the tables

114 Views Asked by At

I have a problem in this excellent book in the derivation of the Runge-Kutta methods, The numerical analysis of ODE.

My wish is to understand how the data as in [*] below are obtained from item $(242a)$.

What is the relationship between $\alpha$'s and $\beta$'s from $(242a)$ and $a$'s,$b$'s and $c$'s from the page $101$ ?

how have we created the numbers $\frac{1}{\gamma(t)}$ and the polynomials $\Phi(t)$ in the table on the page $101$ in oversimplified terms ?

[*] I would like to understand this on an example of this graph:

\/

why: $\sum b_i c_i ^2 = 1/3$

and the what does it tell us the shape itself of this graph ?

1

There are 1 best solutions below

0
On

Your question is mainly due to a misunderstanding of a section change. The $c_i,a_{ij},b_i$ belong indeed to the Butcher tableau of a Runge-Kutta one-step method. The $\alpha_i$, $\beta_i$ however are taken from the next section on linear multi-step methods. While there is some overlap in the lower-order methods, in general these methods and their theory are different.


As to the comment/bounty, the RK methods evaluate several expressions of the form $X_{..}=x_n+h\sum \text{coeff}_{..,j}k_j$. In the stages these are

$$ X_i=x_n+h\sum_ja_{ij}k_j $$ and the point for the next step $$ x_{n+1}=x_n+h\sum_ib_ik_i. $$ The, possibly recursive, connection of the $k_i$ and $X_i$ is that $$ k_i=f(X_i). $$


The $\gamma(\tau)=\tau!$ also belongs to the RK methods, to their order conditions, or more precisely, the Taylor expansion of the exact solution. The term $F(\tau)$ as part of the Taylor expansion has order $|\tau|$. As such it has the common factor $\frac{h^{|\tau|}}{(|\tau|)!}$ over all terms of the same order. But in the construction of this expansion there can be multiple paths to obtain the same term, resulting in some multiplicity $c(\tau)$. On the other side, the Taylor expansion of the RK method will also result in purely numerical factors, giving the coefficient $\frac{h^{|\tau|}}{\sigma(\tau)}$. Apparently $c(\tau)$ divides into $(|\tau|)!$ and $\sigma(\tau)$ divides into the remaining product, so it can be extracted via $\frac{c(\tau)}{(|\tau|)!}=\frac1{\sigma(\tau)\tau!}$

Thus Taylor expansion $$ x(t+h)=x(t)+\sum_{\tau}\frac{h^{|\tau|}}{\sigma(\tau)\tau!}F(\tau)(x(t)) $$ and method expansion $$ x_{n+1}=x_n+\sum_\tau\frac{h^{|\tau|}}{\sigma(\tau)}\Phi(\tau)F(\tau)(x_n) $$ where $F(\tau)$ is the combination of derivatives of $f$ corresponding to the tree $\tau$ and $\Phi(\tau)$ the polynomial in the method coefficients for the same tree.

For the example of $\tau=\backslash/=[[][]]$ you get, mostly mechanically, $\Phi(\backslash/)=\sum b_ic_i^2$ and $F(\backslash/)=f''[f,f]$. The factors are $(\backslash/)!=\gamma(\backslash/)=3\cdot 1\cdot 1=3$ and $\sigma(\backslash/)=3!/3=2$.