Calcolo numerico/Metodi Runge-Kutta

Definizione generale

Questi metodi sono del tipo

$y_{n+1}=y_{n}+hF(t_{n},y_{n},h;f)$

e sono a un passo. $F$ è definita come

$F(t_{n},y_{n},h;f)=\sum _{i=1}^{s}b_{i}*K_{i}$

dove i $K_{i}$ vengono chiamati stadi.

Definizione degli stadi

Gli stadi possono essere definiti come

$K_{i}=f(t_{n}+c_{i}h,y_{n}+h\sum _{j=1}^{s}a_{ij}K_{j})$

Nel secondo argomento compaiono nuovamente gli stadi, quindi questi metodi sono non lineari.

I coefficienti $c_{i},b_{i},a_{ij}$ compaiono nella batcher array.

$\left({\begin{array}{c|ccc}c_{1}&a_{11}&\dots &a_{1s}\\\dots &\dots &\dots &\dots \\c_{s}&a_{s1}&\dots &a_{ss}\\\hline &b_{1}&\dots &b_{s}\end{array}}\right)$

In forma compatta:

$\left({\begin{array}{cc}{\boldsymbol {c}}&A\\&{\boldsymbol {b}}\end{array}}\right)$

I coefficienti indicano caratteristiche del metodo usato. In particolare deve valere la row sum condition, cioè

$c_{i}=\sum _{j=1}^{s}a_{ij}$

se quest'uguaglianza non è verificata il metodo non funziona.

Si possono verificare tre casi:

1. metodi espliciti ($a_{ij}=0\iff j\geq i$): la sommatoria si ferma all'indice $i-1$, la diagonale principale e la parte triangolare superiore di $A$ sono nulle; compare solo la dipendenza dagli stadi precedenti, che sono già stati calcolati;
2. metodi semi-impliciti ($a_{ij}=0\iff j>i$):la diagonale principale non è nulla, ma la parte triangolare superiore di $A$ lo è, compare la dipendenza dal passo attivo;
3. metodi impliciti: $A$ è una matrice piena.

Nel caso dei semi-impliciti dobbiamo risolvere il sistema:

$K_{i}=f(t_{n}+c_{i}h,y_{n}+h\sum _{j=1}^{i-1}a_{ij}K_{j}+ha_{ii}K_{i})$

per $i=1,\dots ,s$, che è un sistema di $s$ equazioni non lineari disaccoppiate.

Nel caso degli impliciti invece ho un sistema di equazioni non disaccoppiate dove ogni stadio coinvolge tutti gli altri, e le equazioni sono del tipo:

$K_{i}=f(t_{n}+c_{i}h,y_{n})+h\sum _{j=1}^{s}a_{ij}K_{j}+ha_{ii}K_{i}$

Runge-Kutta 4 (esplicito)

Il Runge-Kutta 4 è definito nel seguente modo:

$y_{n+1}=y_{n}+h/6(K_{1}+2K_{2}+2K_{3}+K_{4})$

dove

$K_{1}=f(t_{n},y_{n})$

$K_{2}=f(t_{n}+h/2,y_{n}+h/2K_{1})$

$K_{3}=f(t_{n}+h/2,y_{n}+h/2K_{2})$

$K_{4}=f(t_{n+1},y_{n}+hK_{3})$

Se consideriamo un Runge-Kutta esplicito a $s$ stadi, l'ordine massimo di convergenza è $s$, anche se si dimostra che non esistono Runge-Kutta espliciti a $s$ stadi di ordine $s$ per $s>5$.

Consistenza

Un metodo Runge-Kutta è consistente ovvero $\tau _{h}=\max _{n}|t_{nh}|\to 0$ per $h\to 0$ se e solo se

$\sum _{i=1}^{s}b_{i}=1$

In questo caso 1 è l'unica radice del polinomio caratteristico e quindi la consistenza (e in questo caso la 0-stabilità) implica la convergenza.

Runge-Kutta 2

Consideriamo un Runge-Kutta a due stadi, $s=2$, esplicito. Supponiamo che

$y_{n+1}=y(t_{n})+h(b_{1}K_{1}+b_{2}K_{2})$

con $K_{1}=f(t_{n},y(t_{n}))$ e $K_{2}=f(t_{n}+hc_{2},y(t_{n})+ha_{21}K_{1})$.

Il blocco di Batcher è della forma:

$\left({\begin{array}{ccc}0&0&0\\c_{2}&A_{21}&0\\\hline &b_{1}&b_{2}\end{array}}\right)$

Deve valere la condizione di somma sulle righe, quindi

$a_{21}=c_{2}$

e si ottiene

$K_{2}=f(t_{n}+hc_{2},y(t_{n})+hc_{2}K_{1})$

e sostituendo l'espressione di $K_{1}$:

$K_{2}=f(t_{n}+hc_{2},y(t_{n})+hc_{2}f(t_{n},y(t_{n}))$

Sviluppando rispetto a $h$:

$K_{2}=f(t_{n},y(t_{n}))+c_{2}hf_{t}(t_{n},y_{n})+hc_{2}f_{y}(t_{n},y(t_{n}))+o(H^{2})$

($f_{t},f_{y}$ indicano le derivate parziali rispetto a $t$ e a $y$) e sostituendo le espressioni degli stadi nell'espressione del metodo:

$y_{n+1}=y(t_{n})+hb_{1}f(t_{n},y(t_{n}))+hb_{2}[f(t_{n},y(t_{n}))+hc_{2}f_{t}(t_{n},y(tn))+hc_{2}f_{y}(t_{n},y(t_{n})+O(H^{2}))$

e associando i termini corrispondenti

$y_{n+1}=y(t_{n})+h(b_{1}+b_{2})f(t_{n},y(t_{n}))+h^{2}b_{2}c_{2}(f_{t}(t_{n},y(tn))+f_{y}(t_{n},y(t_{n}))+O(H^{2})$

ma $y_{n+1}=y(t_{n})+hy'(t_{n})+h^{2}/2y''(t_{n})+O(h^{3})$, quindi

$y(t_{n})+hy'(t_{n})+h^{2}/2y''(t_{n})+O(h^{3})=$

$=y(t_{n})+h(b_{1}+b_{2})f(t_{n},y(t_{n}))+h^{2}b_{2}c_{2}(f_{t}(t_{n},y(tn))+f_{y}(t_{n},y(t_{n}))+O(H^{2})$

e

$hy'(t_{n})+h^{2}/2y''(t_{n})+O(h^{3})=$

$=h(b_{1}+b_{2})f(t_{n},y(t_{n}))+h^{2}b_{2}c_{2}(f_{t}(t_{n},y(tn))+f_{y}(t_{n},y(t_{n}))+O(H^{2})$

Imponiamo che la soluzione esatta soddisfi lo schema numerico fino a un certo ordine, e confrontando i coefficienti a primo e secondo membro otteniamo:

${\begin{cases}b_{1}+b_{2}=1\\b_{2}c_{2}=1/2\end{cases}}$

Ci sono infinite soluzioni possibili, quindi infiniti Runge-Kutta di tipo 2.

Passo di integrazione

Dato un problema di integrazione stiff, si deve sempre scegliere un passo di integrazione variabile. Nei metodi Runge-Kutta a un passo il passo può essere variato a piacere, mentre nei metodi multipasso questo non è vero.

I Runge-Kutta impliciti sono i metodi che raggiungono la massima potenza possibile. La loro teoria di convergenza viene trattata in maniera algebrica.