Metodi Runge-Kutta

==Definizione generale==
Questi metodi sono del tipo
<math display="block">y_{n+1} = y_n+h F(t_n,y_n,h;f)</math>
e sono ad un passo. <math>F</math> è definita come
<math display="block">F(t_n,y_n,h;f) = \sum_{i=1}^s b_i*K_i</math>
dove i <math>K_i</math> vengono chiamati ''stadi''.

==Definizione degli stadi==
Gli stadi possono essere definiti come
<math display="block">K_i = f(t_n+c_i h,y_n+h\sum_{j=1}^s a_{ij} K_j)</math>
Nel secondo argomento compaiono nuovamente gli stadi, quindi questi metodi sono non lineari.

I coefficienti <math>c_i, b_i, a_{ij}</math> compaiono nella batcher array.
<math display="block">\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)</math>
In forma compatta:
<math display="block">\left(\begin{array}{cc} \boldsymbol{c} & A \\ & \boldsymbol{b} \end{array} \right)</math>
I coefficienti indicano caratteristiche del metodo usato. In particolare deve valere la ''row sum condition'', cioè
<math display="block">c_i = \sum_{j=1}^s a_{ij}</math>
se quest'uguaglianza non è verificata il metodo non funziona.



Si possono verificare tre casi:

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


Nel caso dei semiimpliciti devo risolvere il sistema:
<math display="block">K_i = f(t_n+c_i h,y_n+h\sum_{j=1}^{i-1} a_{ij} K_j+h a_{ii} K_i)</math>
per <math>i=1,\dots,s</math>, che è un sistema di <math>s</math> 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:
<math display="block">K_i = f(t_n+c_i h,y_n)+h\sum_{j=1}^s a_{ij} K_j+h a_{ii} K_i</math>

==Runge-Kutta 4 (esplicito)==
Il Runge-Kutta 4 è definito nel seguente modo:
<math display="block">y_{n+1} = y_n+h/6 (K_1+2 K_2+2 K_3+K_4)</math>
dove
<math display="block">K_1 = f(t_n,y_n)</math>
<math display="block">K_2 = f(t_n+h/2,y_n+h/2 K_1)</math>
<math display="block">K_3 = f(t_n+h/2,y_n+h/2 K_2)</math>
<math display="block">K_4 = f(t_{n+1},y_n+h K_3)</math>
<math display="block"></math>

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

==Consistenza==
Un metodo Runge-Kutta è consistente ovvero <math>\tau_h = \max_n |t_{nh}| \to 0</math> per <math>h \to 0</math> se e solo se
<math display="block">\sum_{i=1}^s b_i  = 1</math>
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, <math>s=2</math>, esplicito.
Supponiamo che
<math display="block">y_{n+1} = y(t_n)+h (b_1 K_1+b_2 K_2)</math>
con <math>K_1 = f(t_n,y(t_n))</math> e <math>K_2 = f(t_n+h c_2,y(t_n)+h a_{21} K_1)</math>.


Il blocco di Batcher è della forma:
<math display="block">\left(\begin{array}{ccc}0 & 0 & 0 \\c_2 & A_{21} & 0 \\\hline & b_1 & b_2\end{array} \right)</math>
Deve valere la condizione di somma sulle righe, quindi
<math display="block">a_{21} = c_2</math>
e si ottiene
<math display="block">K_2 = f(t_n+h c_2,y(t_n)+h c_2 K_1)</math>
e sostituendo l'espressione di <math>K_1</math>:
<math display="block">K_2 = f(t_n+h c_2,y(t_n)+h c_2 f(t_n,y(t_n))</math>
Sviluppando rispetto a <math>h</math>:
<math display="block">K_2 = f(t_n,y(t_n))+c_2 h f_t(t_n,y_n)+h c_2 f_y(t_n,y(t_n))+o(H^2)</math>
(<math>f_t, f_y</math> indicano le derivate parziali rispetto a <math>t</math> e a <math>y</math>) e sostituendo le espressioni degli stadi nell'espressione del metodo:
<math display="block">y_{n+1} = y(t_n)+h b_1 f(t_n,y(t_n))+ h b_2 [f(t_n,y(t_n))+h c_2 f_t(t_n,y(tn))+h c_2 f_y(t_n,y(t_n)+O(H^2))</math>
e associando i termini corrispondenti
<math display="block">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)</math>
ma <math>y_{n+1} = y(t_n)+h y'(t_n)+h^2/2 y''(t_n)+O(h^3)</math>, quindi
<math display="block">y(t_n)+h y'(t_n)+h^2/2 y''(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)</math><math display="block">h y'(t_n)+h^2/2 y''(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)</math>
Impongo che la soluzione esatta soddisfi lo schema numerico fino a un certo ordine, e confrontando i coefficienti a primo e secondo membro ottengo:
<math display="block">\begin{cases}b_1+b_2 =1 \\b_2 c_2 = 1/2 \end{cases}</math>
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.