Metodi Runge-Kutta

Definizione generale

Questi metodi sono del tipo

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

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

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

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

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

dove i $K_{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})$$

$$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}$$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)$$

$$\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)$$

$$\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}$$

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

Nel caso dei semiimpliciti devo 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})$$

$$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$$i=1,\dots ,s$, che è un sistema di $s$$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}$$

$$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})$$

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

dove

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

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

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

$$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_{3}=f(t_{n}+h/2,y_{n}+h/2K_{2})$$

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

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

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

Consistenza

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

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

$$\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$$s=2$, esplicito. Supponiamo che

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

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

con $K_{1}=f(t_{n},y(t_{n}))$$K_{1}=f(t_{n},y(t_{n}))$ e $K_{2}=f(t_{n}+hc_{2},y(t_{n})+ha_{21}K_{1})$$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)$$

$$\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}$$

$$a_{21}=c_{2}$$

e si ottiene

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

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

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

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

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

Sviluppando rispetto a $h$$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})$$

$$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}$$f_{t},f_{y}$ indicano le derivate parziali rispetto a $t$$t$ e a $y$$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}))$$

$$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})$$

$$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})$$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})+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})$$=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})=$$

$$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})$$=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})$

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

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

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

Ci sono infinite soluzioni possibili, quindi infinii 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.