Runge-Kutta-metoder

Runge-Kutta metoden er en familie av numeriske algoritmer som gir tilnærmete løsning på differensiallikninger. Metoden ble utviklet omkring år 1900 av C. Runge og M. W. 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. For å generere en løsning er det ønskelig å bevege seg fra $y_{0}$ til $y_{1}$ , og videre til $y_{n}$ . Da må den deriverte approksimeres. Runke-Kutta metoden gjør dette ved å gjentatte ganger sette inn forskjellige verdier i funksjonen $f(t,y)$ , og velge lineære kombinasjoner lik 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 metoden 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

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

der $h$ er skrittlengde, $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)$ er gitt av:

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

Dersom vi bruker taylor på likningen ovenfor, 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 metoden blir at $b_{1}+b_{2}=1$ og $a_{1}b_{2}=1/2$ . En 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 Taylorrekken og velge konstater slik at kun ledd med grad $h^{5}$ og høyere gjenstår. Den vanligste fjerde ordens metoden 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}}

Dett er er metoden som oftest blir forbundet med Runge-Kutta. Legg merke til at metoden ovenfor krever 4 funksjonsevalueringer. Grunnen til at man som oftest ikke går høyere enn fjerde orden, er fordi høyere orden krevere flere funksjonsevalueringer enn ordenen man får.

Implementasjon av RK4

Fjerde ordens Runge-Kutta er rimelig enkelt å implementere, og gir gode resultater. Nedenfor er en implementasjon i Python, av RK4 slik den er gitt av^[1]

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^[2]:

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 konstatene stemme overens med Taylor-utviklingen. Konstantene kan organiseres i et RK-tablå: