Runge-Kutta-metoder

Runge-Kutta-metoder er en familie av numeriske metoder som gir tilnærmete løsninger på differensiallikninger. Metoden ble utviklet omkring år 1900 av de tyske matematikerne Carl Runge og Martin Wilhelm Kutta.

Introduksjon

Følgende initialverdiproblem betraktes:

${\displaystyle {\dot {y}}=f(t,y),\quad y(t_{0})=y_{0}.}$

Der ${\displaystyle {\dot {y}}}$ er ${\displaystyle y}$ derivert med hensyn på ${\displaystyle t}$. Det antas at ${\displaystyle f(t,y)}$ er en komplisert funksjon, og at vi ikke har en eksplisitt løsning på problemet. For å generere en løsning er det ønskelig å bevege seg fra ${\displaystyle y_{0}}$ til ${\displaystyle y_{1}}$, og så videre til ${\displaystyle y_{n}}$. Da må den deriverte approksimeres. Runge-Kutta metoden gjør dette ved å gjentatte ganger sette inn forskjellige verdier i funksjonen ${\displaystyle f(t,y)}$, og velge lineære kombinasjoner slik at flest mulig ledd i Taylor-utviklingen til ${\displaystyle y_{n+1}}$ stemmer overens med ${\displaystyle y(t)}$.

En andre ordens metode

I denne seksjonen utledes en andre-ordens metode for initialverdiproblemet:

${\displaystyle {\dot {y}}=f(y),\quad y(t_{0})=y_{0}.}$

Der ${\displaystyle f}$ kun er en funksjon av ${\displaystyle y}$. En Runge-Kutta metode er gitt ved:

${\displaystyle y_{n+1}=y_{n}+h\left[b_{1}f(y_{n})+b_{2}f(y_{n}+ha_{1}f(y_{n}))\right]}$

der ${\displaystyle h}$ er skrittlengde og ${\displaystyle b_{1}}$, ${\displaystyle b_{2}}$ og ${\displaystyle a_{1}}$ er konstanter. For å få en andre ordens metode må konstantene stemme overens med Taylor-utviklingen av ${\displaystyle y(t)}$.Taylor-utviklingen til ${\displaystyle y(t)}$ rundt ${\displaystyle t}$ er gitt av:

${\displaystyle y(t+h)\approx y(t)+h{\dot {y}}(t)+{\frac {1}{2}}h^{2}{\ddot {y}}(t)+...}$

Dersom metoden ovenfor utvides, kan den skrives som:

${\displaystyle y_{n+1}=y_{n}+h\left[b_{1}+b_{2}\right]{\dot {y}}_{n}+h^{2}\left[a_{1}b_{2}\right]{\ddot {y}}_{n}+...}$

Kravene for en andre ordens metode blir derfor at ${\displaystyle b_{1}+b_{2}=1}$ og ${\displaystyle a_{1}b_{2}=1/2}$. En (av flere mulige) andre ordens metode er derfor gitt ved:

${\displaystyle y_{n+1}=y_{n}+hf(y_{n}+h{\frac {1}{2}})}$

Metoden ovenfor samsvarer med valget ${\displaystyle b_{1}=0}$, ${\displaystyle b_{2}=1}$ og ${\displaystyle a_{1}=1/2}$.

En fjerde ordens metode

For å utlede en fjerde ordens metode må man sette opp konstanter, utvide Taylor-rekken og velge konstater slik at kun ledd med grad ${\displaystyle h^{5}}$ og høyere gjenstår. En av de vanligste fjerde ordens metodene er:

${\displaystyle {\begin{aligned}y_{n+1}&=y_{n}+{\tfrac {h}{6}}\left(k_{1}+2k_{2}+2k_{3}+k_{4}\right)\\t_{n+1}&=t_{n}+h\\\end{aligned}}}$

for n = 0, 1, 2, 3, . . . , der

${\displaystyle {\begin{aligned}k_{1}&=f(t_{n},y_{n}),\\k_{2}&=f(t_{n}+{\tfrac {h}{2}},y_{n}+{\tfrac {h}{2}}k_{1}),\\k_{3}&=f(t_{n}+{\tfrac {h}{2}},y_{n}+{\tfrac {h}{2}}k_{2}),\\k_{4}&=f(t_{n}+h,y_{n}+hk_{3}).\end{aligned}}}$

Dette er metoden som oftest blir forbundet med Runge-Kutta. Legg merke til at metoden ovenfor krever at vi evaluerer funksjonen ${\displaystyle f}$ 4 ganger. Grunnen til at man som oftest ikke går høyere enn fjerde orden er fordi høyere orden krever flere funksjonsevalueringer enn ordenen man får.

Implementasjon av RK4

Fjerde ordens Runge-Kutta er rimelig enkel å implementere, og gir gode resultater sammenlignet med lavere ordens metoder. Nedenfor er en implementasjon i Python av RK4

def runge_kutta4(y_n, t_n, h, f):
    '''
    Gir y_n+1 ved hjelp av Runge Kutta 4.
    '''
    # Konstanter
    k1 = f(t_n, y_n)
    k2 = f(t_n + h/2, y_n + (h/2)*k1)
    k3 = f(t_n + h/2, y_n + (h/2)*k2)
    k4 = f(t_n + h,   y_n + h * k3)
    
    # Regn ut og returner neste verdi
    return y_n + (h/6)*(k1 + 2*k2 + 2*k3 + k4)

def f(t, y):
    '''
    Funksjon til den deriverte.
    '''
    return 0.5 * y
    
# Startverdi, skrittlengde, starttid og sluttid
y_0, h, t_0, t_end = 1, 2, 0, 10 
tider = [i for i in range(t_0, t_end+h, h)] # Liste for tiden
y_verdier = [y_0]                           # Liste for y-verdier

for i in range(0, len(tider)-1):
    y_n, t_n = y_verdier[i], tider[i]               # Hent y og t
    y_verdier.append(runge_kutta4(y_n, t_n, h, f))  # Regn ut neste verdi

Generelle metoder

Generelt er en ${\displaystyle \nu }$ stegs Runge-Kutta metode gitt av likningene:

${\displaystyle y_{n+1}=y_{n}+h\sum _{j=1}^{\nu }b_{j}f\left(t_{n}+c_{j}h,\xi _{j}\right)}$

${\displaystyle \xi _{j}=y_{n}+h\sum _{i=1}^{\nu -1}a_{\nu ,i}f(t_{n}+c_{i}h,\xi _{i})}$

Der ${\displaystyle a_{\nu ,i}}$, ${\displaystyle b_{j}}$ og ${\displaystyle c_{i}}$ er konstanter. For å få ønsket orden må disse konstantene stemme overens med Taylor-utviklingen. Konstantene kan organiseres i et RK-tablå:

	${\displaystyle 0}$
	${\displaystyle c_{2}}$	${\displaystyle a_{21}}$
	${\displaystyle c_{3}}$	${\displaystyle a_{31}}$	${\displaystyle a_{32}}$
	${\displaystyle \vdots }$	${\displaystyle \vdots }$		${\displaystyle \ddots }$
	${\displaystyle c_{s}}$	${\displaystyle a_{s1}}$	${\displaystyle a_{s2}}$	${\displaystyle \cdots }$	${\displaystyle a_{s,s-1}}$
		${\displaystyle b_{1}}$	${\displaystyle b_{2}}$	${\displaystyle \cdots }$	${\displaystyle b_{s-1}}$	${\displaystyle b_{s}}$

Kilder

• Iserles, Arieh (29. desember 2008). A First Course in the Numerical Analysis of Differential Equations (2nd edition utg.). Cambridge ; New York: Cambridge University Press. ISBN 978-0-521-73490-5. CS1-vedlikehold: Ekstra tekst (link)
• Kincaid, David; Ward, Cheney (25. oktober 2001). Numerical Analysis: Mathematics of Scientific Computing (3 edition utg.). Pacific Grove, CA: Brooks Cole. ISBN 978-0-534-38905-5. CS1-vedlikehold: Ekstra tekst (link)