Metodi di Runge-Kutta

In analisi numerica i metodi di Runge-Kutta [ˌʁʊŋəˈkʊta] sono un'importante famiglia di metodi iterativi impliciti ed espliciti per l'approssimazione delle soluzioni delle equazioni differenziali ordinarie. Queste tecniche furono sviluppate intorno al 1900 dai matematici tedeschi Carl Runge e Martin Wilhelm Kutta, dai quali prendono il nome.

Introduzione

I metodi di Runge-Kutta, spesso abbreviati con le iniziali "RK", sono una famiglia di metodi iterativi discreti utilizzati nell'approssimazione numerica di soluzioni di equazioni differenziali ordinarie (ODE), e più specificatamente per problemi ai valori iniziali. Fanno parte della famiglia più generale di metodi discreti per le equazioni differenziali ordinarie, ovvero di quella classe di metodi numerici che fornisce un'approssimazione della soluzione di un'equazione differenziale (o più precisamente di un problema di Cauchy) in un insieme discreto di punti.

Per trovare un'approssimazione della funzione $y(t):ℝ\to {ℝ}^d$ che verifichi il generico problema di Cauchy:

$\{\begin{array}{c}{y}^{\prime }(t)=f(t,y(t))\\ y(t_0)=y_0\end{array}$

in un insieme discreto di punti in cui si considera il problema (solitamente nell'intervallo $[t_0,t_f]$), si considera un campionamento dell'intervallo $\mathrm{\Delta }$ in un insieme di punti $\{t_i\mid i=0\dots n\}$, dove $t_i=t_0+ih$ e $h=(t_f-t_0)/n$. Il metodo numerico fornisce allora l'approssimazione dei valori $y(t_i)$, e per ottenere una ricostruzione abbastanza fedele della funzione il numero $n$ deve essere sufficientemente elevato.

Formulazione

L'idea che sta alla base dei metodi di Runge-Kutta è la trasposizione del problema dalla forma differenziale alla forma integrale, per la quale esistono metodi numerici (come le formule di quadratura) che permettono l'approssimazione della soluzione. In generale un metodo di Runge-Kutta è caratterizzato da tre parametri: un vettore $b=(b_i{)}_{i=0,\dots ,s}$, una matrice $a=(a_{i,j}{)}_{i,j=0,\dots ,s}$ e un vettore $\theta =({\theta }_i{)}_{i=0,\dots ,s}$. L'approssimazione è data dal sistema:

$\{\begin{array}{c}{y}_{n+1}=y_n+h\sum _{i=1}^s{b}_{i}f(t_n+{\theta }_{i}h,Y_i)\\ Y_i=y_n+h\sum _{j=1}^s{a}_{ij}f(t_n+{\theta }_{j}h,Y_j)i=1,\dots ,s\end{array}$

dove i valori $y_i$ approssimano il valore esatto $y(t_i)$.

Considerando il generico problema di Cauchy:

$\{\begin{array}{c}{y}^{\prime }(t)=f(t,y(t))\\ y(t_0)=y_0\end{array}$

Si può considerare una sua riformulazione in forma integrale:

$y(t)=y_0+\underset{t_0}{\overset{t}{\int }}{y}^{\prime }(s)ds=y_0+\underset{t_0}{\overset{t}{\int }}f(s,y(s))ds$

dove l'ultima sostituzione è legittima in quanto la funzione è soluzione dell'equazione differenziale. Da questa riformulazione segue in particolare che, per una suddivisione uniforme $\mathrm{\Delta }=\{t_i\}=\{t_0+ih{\}}_{\{i=0,\dots ,n\}}$, il valore della soluzione nel punto $t_1$ è dato da:

$y(t_1)=y_0+\underset{t_0}{\overset{t_0+h}{\int }}f(s,y(s))ds$

Da questo risultato, attraverso la sostituzione $s=t_0+\theta h$ si può normalizzare l'intervallo di integrazione e ottenere:

$y(t_1)=y_0+h\underset{0}{\overset{1}{\int }}f(t_0+\theta h,y(t_0+\theta h))d\theta$

Da questa scrittura appare evidente che con opportune sostituzioni si può esprimere il valore della funzione in ogni punto intermedio tra $t_0$ e $t_1$.

Utilizzando un'approssimazione per via numerica dell'integrale attraverso delle formule di quadratura sui nodi ${\theta }_i$ e pesi $b_i$ (che dipendono dalla scelta della formula di quadratura) si ottiene una stima del valore $y_1$:

$y_1=y_0+h\sum _{i=0}^{\nu }{b}_{i}f(t_0+{\theta }_{i}h,Y_i)$

dove i valori $Y_i$ sono approssimazioni di $y(t_0+{\theta }_{i}h)$, che sono ignote a priori. Applicando nuovamente il ragionamento precedente si può scrivere che:

$y(t_0+{\theta }_{i}h)=y_0+h\underset{0}{\overset{{\theta }_i}{\int }}f(t_0+vh,y(t_0+vh))dv$

Questi valori possono essere approssimati a loro volta utilizzando una formula di quadratura con pesi $a_{ij}$; si ottiene così che (per semplicità si considerano formule con i medesimi nodi di quadratura di quelle usate in precedenza):

$Y_i=y_0+h\sum _{j=1}^{\nu }{a}_{ij}f(t_0+{\theta }_{j}h,Y_j)$

Iterando tale costruzione si ottengono le approssimazioni nei punti $t_i$, e come conseguenza la formulazione generale per i metodi di Runge-Kutta.

Metodi espliciti

Dato il problema ai valori iniziali:

$\dot{y}=f(t,y)y(t_0)=y_0$

dove i valori di $t_0$ e $y_0$ sono noti, si consideri un intervallo sufficientemente piccolo $h>0$ e si definiscano:

$\begin{array}{cc}{y}_{n+1}& =y_n+\frac{h}{6}(k_1+2k_2+2k_3+k_4)\\ t_{n+1}& =t_n+h\\ \end{array}$

per $n=1,2,3,\dots$. In questo modo $y(t_{n+1})$ è approssimato con $y_{n+1}$, e $y_{n+1}$ è determinato da $y_n$ più la media pesata di quattro incrementi $k_1$, $k_2$, $k_3$ e $k_4$:

$\begin{array}{cc}{k}_1& =f(t_n,y_n)\\ k_2& =f(t_n+\frac{h}{2},y_n+\frac{1}{2}{k}_{1}h)\\ k_3& =f(t_n+\frac{h}{2},y_n+\frac{1}{2}{k}_{2}h)\\ k_4& =f(t_n+h,y_n+k_{3}h)\end{array}$

dove ogni incremento è il prodotto di $h$ e una stima della pendenza di $f$. Nello specifico:

• $k_1$ è l'incremento basato sulla pendenza all'inizio dell'intervallo, utilizzando ${\dot{y}}_n$ (metodo di Eulero)
• $k_2$ è l'incremento basato sulla pendenza alla metà dell'intervallo, utilizzando $k_1$
• $k_3$ è un altro incremento basato sulla pendenza alla metà dell'intervallo, utilizzando $k_2$
• $k_4$ è l'incremento basato sulla pendenza alla fine dell'intervallo, utilizzando $k_3$

Nel fare la media, gli incrementi valutati in un punto intermedio dell'intervallo hanno peso maggiore, ed i coefficienti sono scelti in modo che se $f$ è indipendente da $y$, sicché l'equazione dipende da un semplice integrale, allora il metodo RK coincide con la regola di Cavalieri-Simpson.

In generale, la famiglia di metodi espliciti di Runge-Kutta è data da:

$y_{n+1}=y_n+\sum _{i=1}^{s}h{b}_i{k}_i$

dove:

$\begin{array}{cc}{k}_1& =f(t_n,y_n)\\ k_2& =f(t_n+c_{2}h,y_n+h(a_{21}{k}_1))\\ k_3& =f(t_n+c_{3}h,y_n+h(a_{31}{k}_1+a_{32}{k}_2))\\ & ⋮\\ k_s& =f(t_n+c_{s}h,y_n+h(a_{s1}{k}_1+a_{s2}{k}_2+\cdots +a_{s,s-1}{k}_{s-1}))\\ \end{array}$

Per specificare un particolare metodo si deve definire il numero $s$ ed i coefficienti $a_{ij}$ (per $1\le j<i\le s$), $b_i$ (per $i=1,2,\dots ,s$) e $c_i$ (per $i=2,3,\dots ,s$). La matrice dei coefficienti $a_{ij}$ è detta matrice di Runge-Kutta. Si usa spesso rappresentare i coefficienti in una tabella:

	0
	$c_2$	$a_{21}$
	$c_3$	$a_{31}$	$a_{32}$
	$⋮$	$⋮$		$\ddots$
	$c_s$	$a_{s1}$	$a_{s2}$	$\cdots$	$a_{s,s-1}$
		$b_1$	$b_2$	$\cdots$	$b_{s-1}$	$b_s$

e si deve avere:

$\sum _{j=1}^{i-1}{a}_{ij}=c_{i}i=2,\dots ,s$

Derivazione per il quarto ordine

In generale, un metodo di Runge-Kutta di ordine $s$ può essere scritto come:

$y_{t+h}=y_t+h\cdot \sum _{i=1}^s{a}_i{k}_i+𝒪(h^{s+1})$

dove:

$k_i=f(y_t+h\cdot \sum _{j=1}^s{\beta }_{ij}{k}_j,t_n+{\alpha }_{i}h)$

sono gli incrementi ottenuti valutando le derivate di $y_t$ all'$i$-esimo ordine.

Un modo per derivare il metodo per $s=4$ utilizzando la formula generale è il seguente. Si sceglie:

$\begin{array}{cc}{\alpha }_i& {\beta }_{ij}\\ {\alpha }_1=0& {\beta }_{21}=\frac{1}{2}\\ {\alpha }_2=\frac{1}{2}& {\beta }_{32}=\frac{1}{2}\\ {\alpha }_3=\frac{1}{2}& {\beta }_{43}=1\\ {\alpha }_4=1& \end{array}$

con ${\beta }_{ij}=0$ altrimenti. Si definiscono quindi le quantità:

$\begin{array}{cc}{y}_{t+h}^1& =y_t+hf(y_t,t)\\ y_{t+h}^2& =y_t+hf(y_{t+h/2}^1,t+\frac{h}{2})\\ y_{t+h}^3& =y_t+hf(y_{t+h/2}^2,t+\frac{h}{2})\end{array}$

dove:

$y_{t+h/2}^1=\frac{y_t+y_{t+h}^1}{2}{y}_{t+h/2}^2=\frac{y_t+y_{t+h}^2}{2}$

Se si pone:

$\begin{array}{cc}{k}_1& =f(y_t,t)\\ k_2& =f(y_{t+h/2}^1,t+\frac{h}{2})\\ k_3& =f(y_{t+h/2}^2,t+\frac{h}{2})\\ k_4& =f(y_{t+h}^3,t+h)\end{array}$

sostituendo si ha a meno di $O(h^2)$:

$\begin{array}{cc}{k}_2& =f(y_{t+h/2}^1,t+\frac{h}{2})=f(y_t+\frac{h}{2}{k}_1,t+\frac{h}{2})\\ & =f(y_t,t)+\frac{h}{2}\frac{d}{dt}f(y_t,t)\\ k_3& =f(y_{t+h/2}^2,t+\frac{h}{2})=f(y_t+\frac{h}{2}f(y_t+\frac{h}{2}{k}_1,t+\frac{h}{2}),t+\frac{h}{2})\\ & =f(y_t,t)+\frac{h}{2}\frac{d}{dt}[f(y_t,t)+\frac{h}{2}\frac{d}{dt}f(y_t,t)]\\ k_4& =f(y_{t+h}^3,t+h)=f(y_t+hf(y_t+\frac{h}{2}{k}_2,t+\frac{h}{2}),t+h)\\ & =f(y_t+hf(y_t+\frac{h}{2}f(y_t+\frac{h}{2}f(y_t,t),t+\frac{h}{2}),t+\frac{h}{2}),t+h)\\ & =f(y_t,t)+h\frac{d}{dt}[f(y_t,t)+\frac{h}{2}\frac{d}{dt}[f(y_t,t)+\frac{h}{2}\frac{d}{dt}f(y_t,t)]]\end{array}$

dove:

$\frac{d}{dt}f(y_t,t)=\frac{\partial }{\partial y}f(y_t,t){\dot{y}}_t+\frac{\partial }{\partial t}f(y_t,t)=f_y(y_t,t)\dot{y}+f_t(y_t,t):={\ddot{y}}_t$

è la derivata totale di $f$ rispetto a $t$. Scrivendo la formula generale con quanto ricavato:

$\begin{array}{cc}{y}_{t+h}& =y_t+h\{a\cdot f(y_t,t)+b\cdot [f(y_t,t)+\frac{h}{2}\frac{d}{dt}f(y_t,t)]+\\ & +c\cdot [f(y_t,t)+\frac{h}{2}\frac{d}{dt}[f(y_t,t)+\frac{h}{2}\frac{d}{dt}f(y_t,t)]]+\\ & +d\cdot [f(y_t,t)+h\frac{d}{dt}[f(y_t,t)+\frac{h}{2}\frac{d}{dt}[f(y_t,t)+\frac{h}{2}\frac{d}{dt}f(y_t,t)]]]\}+𝒪(h^5)\\ & =y_t+a\cdot h{f}_t+b\cdot h{f}_t+b\cdot \frac{h^2}{2}\frac{d{f}_t}{dt}+c\cdot h{f}_t+c\cdot \frac{h^2}{2}\frac{d{f}_t}{dt}+\\ & +c\cdot \frac{h^3}{4}\frac{d^2{f}_t}{d{t}^2}+d\cdot h{f}_t+d\cdot h^2\frac{d{f}_t}{dt}+d\cdot \frac{h^3}{2}\frac{d^2{f}_t}{d{t}^2}+d\cdot \frac{h^4}{4}\frac{d^3{f}_t}{d{t}^3}+𝒪(h^5)\end{array}$

e confrontando con l'espansione di serie di Taylor di $y_{t+h}$ intorno a $t$:

$\begin{array}{cc}{y}_{t+h}& =y_t+h{\dot{y}}_t+\frac{h^2}{2}{\ddot{y}}_t+\frac{h^3}{6}{y}_t^{(3)}+\frac{h^4}{24}{y}_t^{(4)}+𝒪(h^5)=\\ & =y_t+hf(y_t,t)+\frac{h^2}{2}\frac{d}{dt}f(y_t,t)+\frac{h^3}{6}\frac{d^2}{d{t}^2}f(y_t,t)+\frac{h^4}{24}\frac{d^3}{d{t}^3}f(y_t,t)\end{array}$

si ottiene un sistema di equazioni per i coefficienti:

$\{\begin{array}{cc}& a+b+c+d=1\\ & \frac{1}{2}b+\frac{1}{2}c+d=\frac{1}{2}\\ & \frac{1}{4}c+\frac{1}{2}d=\frac{1}{6}\\ & \frac{1}{4}d=\frac{1}{24}\end{array}$

che fornisce:

$a=\frac{1}{6}b=\frac{1}{3}c=\frac{1}{3}d=\frac{1}{6}$

Bibliografia

• Template:De C. Runge e H. Koenig Vorlesungen über numerisches Rechnen Springer - 1924 (capitolo 10)
• Template:En D. M. Yound e R. T. Gregory A survey of numerical methods (Dover, New York) ISBN 0486656926
• Template:En Kendall E. Atkinson. An Introduction to Numerical Analysis. John Wiley & Sons - 1989
• Template:En Ward Cheney e David Kincaid Numerical Mathematics and Computing Brooks/Cole - 1985 programmi Fortran
• Template:En David Kincaid e Ward Cheney Numerical Analysis Mathetatics of Scientific Computing Brooks/Cole -1991 programmi Fortran
• Template:En R.W. Brankin, I. Gladwell, e L.F. Shampine metodi di Runge Kutta in Fortran 77

Voci correlate

• Metodi di soluzione numerica per equazioni differenziali ordinarie
• Metodo di Eulero
• Problema di Cauchy
• Integrazione numerica

Collegamenti esterni

• Template:SpringerEOM
• Template:EnRunge-Kutta 4th-order method textbook notes, PPT, Matlab Mathematica Maple Mathcad at Holistic Numerical Methods Institute