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:

: \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_1f(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} + h f(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{align}
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{align}

for *n*&nbsp;=&nbsp;0,&nbsp;1,&nbsp;2,&nbsp;3,&nbsp;.&nbsp;.&nbsp;.&nbsp;, der
:
\begin{align}
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{align}


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

```python
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å:

## Kilder
*
*