Runge-Kutta-metoder

Løsning til initialverdiproblemet ${\dot {y}}=0.5t,\quad y(0)=1$.

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:

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

Der ${\dot {y}}$ er $y$ derivert med hensyn på $t$. Det antas at $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 $y_{0}$ til $y_{1}$, og så videre til $y_{n}$. Da må den deriverte approksimeres. Runge-Kutta metoden gjør dette ved å gjentatte ganger sette inn forskjellige verdier i funksjonen $f(t,y)$, og velge lineære kombinasjoner slik at flest mulig ledd i Taylor-utviklingen til $y_{n+1}$ stemmer overens med $y(t)$.

En andre ordens metode

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

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

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

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

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

$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:

$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 $b_{1}+b_{2}=1$ og $a_{1}b_{2}=1/2$. En (av flere mulige) andre ordens metode er derfor gitt ved:

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

Metoden ovenfor samsvarer med valget $b_{1}=0$, $b_{2}=1$ og $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 $h^{5}$ og høyere gjenstår. En av de vanligste fjerde ordens metodene er:

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

${\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 $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 $\nu$ stegs Runge-Kutta metode gitt av likningene:

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

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

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

	$0$
	$c_{2}$	$a_{21}$
	$c_{3}$	$a_{31}$	$a_{32}$
	$\vdots$	$\vdots$		$\ddots$
	$c_{s}$	$a_{s1}$	$a_{s2}$	$\cdots$	$a_{s,s-1}$
		$b_{1}$	$b_{2}$	$\cdots$	$b_{s-1}$	$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)