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:

  
    
      
        
          
            
              y
              ˙
            
          
        
        =
        f
        (
        t
        ,
        y
        )
        ,
        
        y
        (
        
          t
          
            0
          
        
        )
        =
        
          y
          
            0
          
        
        .
      
    
    {\displaystyle {\dot {y}}=f(t,y),\quad y(t_{0})=y_{0}.}
  Der 
  
    
      
        
          
            
              y
              ˙
            
          
        
      
    
    {\displaystyle {\dot {y}}}
   er 
  
    
      
        y
      
    
    {\displaystyle y}
   derivert med hensyn på 
  
    
      
        t
      
    
    {\displaystyle t}
  . Det antas at 
  
    
      
        f
        (
        t
        ,
        y
        )
      
    
    {\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 
  
    
      
        
          y
          
            0
          
        
      
    
    {\displaystyle y_{0}}
   til 
  
    
      
        
          y
          
            1
          
        
      
    
    {\displaystyle y_{1}}
  , og så videre til 
  
    
      
        
          y
          
            n
          
        
      
    
    {\displaystyle 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
        )
      
    
    {\displaystyle f(t,y)}
  , og velge lineære kombinasjoner slik at flest mulig ledd i Taylor-utviklingen til 
  
    
      
        
          y
          
            n
            +
            1
          
        
      
    
    {\displaystyle y_{n+1}}
   stemmer overens med 
  
    
      
        y
        (
        t
        )
      
    
    {\displaystyle y(t)}
  .


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

  
    
      
        
          
            
              y
              ˙
            
          
        
        =
        f
        (
        y
        )
        ,
        
        y
        (
        
          t
          
            0
          
        
        )
        =
        
          y
          
            0
          
        
        .
      
    
    {\displaystyle {\dot {y}}=f(y),\quad y(t_{0})=y_{0}.}
  Der 
  
    
      
        f
      
    
    {\displaystyle f}
   kun er en funksjon av 
  
    
      
        y
      
    
    {\displaystyle y}
  . En Runge-Kutta metode er gitt ved:

  
    
      
        
          y
          
            n
            +
            1
          
        
        =
        
          y
          
            n
          
        
        +
        h
        
          [
          
            
              b
              
                1
              
            
            f
            (
            
              y
              
                n
              
            
            )
            +
            
              b
              
                2
              
            
            f
            (
            
              y
              
                n
              
            
            +
            h
            
              a
              
                1
              
            
            f
            (
            
              y
              
                n
              
            
            )
            )
          
          ]
        
      
    
    {\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 
  
    
      
        h
      
    
    {\displaystyle h}
   er skrittlengde og 
  
    
      
        
          b
          
            1
          
        
      
    
    {\displaystyle b_{1}}
  , 
  
    
      
        
          b
          
            2
          
        
      
    
    {\displaystyle b_{2}}
   og 
  
    
      
        
          a
          
            1
          
        
      
    
    {\displaystyle a_{1}}
   er konstanter. For å få en andre ordens metode må konstantene stemme overens med Taylor-utviklingen av 
  
    
      
        y
        (
        t
        )
      
    
    {\displaystyle y(t)}
  .Taylor-utviklingen til 
  
    
      
        y
        (
        t
        )
      
    
    {\displaystyle y(t)}
   rundt 
  
    
      
        t
      
    
    {\displaystyle t}
   er gitt av: 

  
    
      
        y
        (
        t
        +
        h
        )
        ≈
        y
        (
        t
        )
        +
        h
        
          
            
              y
              ˙
            
          
        
        (
        t
        )
        +
        
          
            1
            2
          
        
        
          h
          
            2
          
        
        
          
            
              y
              ¨
            
          
        
        (
        t
        )
        +
        .
        .
        .
      
    
    {\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:

  
    
      
        
          y
          
            n
            +
            1
          
        
        =
        
          y
          
            n
          
        
        +
        h
        
          [
          
            
              b
              
                1
              
            
            +
            
              b
              
                2
              
            
          
          ]
        
        
          
            
              
                y
                ˙
              
            
          
          
            n
          
        
        +
        
          h
          
            2
          
        
        
          [
          
            
              a
              
                1
              
            
            
              b
              
                2
              
            
          
          ]
        
        
          
            
              
                y
                ¨
              
            
          
          
            n
          
        
        +
        .
        .
        .
      
    
    {\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 
  
    
      
        
          b
          
            1
          
        
        +
        
          b
          
            2
          
        
        =
        1
      
    
    {\displaystyle b_{1}+b_{2}=1}
   og 
  
    
      
        
          a
          
            1
          
        
        
          b
          
            2
          
        
        =
        1
        
          /
        
        2
      
    
    {\displaystyle 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
        
          
            1
            2
          
        
        )
      
    
    {\displaystyle y_{n+1}=y_{n}+hf(y_{n}+h{\frac {1}{2}})}
  Metoden ovenfor samsvarer med valget 
  
    
      
        
          b
          
            1
          
        
        =
        0
      
    
    {\displaystyle b_{1}=0}
  , 
  
    
      
        
          b
          
            2
          
        
        =
        1
      
    
    {\displaystyle b_{2}=1}
   og 
  
    
      
        
          a
          
            1
          
        
        =
        1
        
          /
        
        2
      
    
    {\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 
  
    
      
        
          h
          
            5
          
        
      
    
    {\displaystyle h^{5}}
   og høyere gjenstår. En av de vanligste fjerde ordens metodene er:

  
    
      
        
          
            
              
                
                  y
                  
                    n
                    +
                    1
                  
                
              
              
                
                =
                
                  y
                  
                    n
                  
                
                +
                
                  
                    
                      h
                      6
                    
                  
                
                
                  (
                  
                    
                      k
                      
                        1
                      
                    
                    +
                    2
                    
                      k
                      
                        2
                      
                    
                    +
                    2
                    
                      k
                      
                        3
                      
                    
                    +
                    
                      k
                      
                        4
                      
                    
                  
                  )
                
              
            
            
              
                
                  t
                  
                    n
                    +
                    1
                  
                
              
              
                
                =
                
                  t
                  
                    n
                  
                
                +
                h
              
            
          
        
      
    
    {\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

  
    
      
        
          
            
              
                
                  k
                  
                    1
                  
                
              
              
                
                =
                f
                (
                
                  t
                  
                    n
                  
                
                ,
                
                  y
                  
                    n
                  
                
                )
                ,
              
            
            
              
                
                  k
                  
                    2
                  
                
              
              
                
                =
                f
                (
                
                  t
                  
                    n
                  
                
                +
                
                  
                    
                      h
                      2
                    
                  
                
                ,
                
                  y
                  
                    n
                  
                
                +
                
                  
                    
                      h
                      2
                    
                  
                
                
                  k
                  
                    1
                  
                
                )
                ,
              
            
            
              
                
                  k
                  
                    3
                  
                
              
              
                
                =
                f
                (
                
                  t
                  
                    n
                  
                
                +
                
                  
                    
                      h
                      2
                    
                  
                
                ,
                
                  y
                  
                    n
                  
                
                +
                
                  
                    
                      h
                      2
                    
                  
                
                
                  k
                  
                    2
                  
                
                )
                ,
              
            
            
              
                
                  k
                  
                    4
                  
                
              
              
                
                =
                f
                (
                
                  t
                  
                    n
                  
                
                +
                h
                ,
                
                  y
                  
                    n
                  
                
                +
                h
                
                  k
                  
                    3
                  
                
                )
                .
              
            
          
        
      
    
    {\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 
  
    
      
        f
      
    
    {\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


== Generelle metoder ==
Generelt er en 
  
    
      
        ν
      
    
    {\displaystyle \nu }
   stegs Runge-Kutta metode gitt av likningene:

  
    
      
        
          y
          
            n
            +
            1
          
        
        =
        
          y
          
            n
          
        
        +
        h
        
          ∑
          
            j
            =
            1
          
          
            ν
          
        
        
          b
          
            j
          
        
        f
        
          (
          
            
              t
              
                n
              
            
            +
            
              c
              
                j
              
            
            h
            ,
            
              ξ
              
                j
              
            
          
          )
        
      
    
    {\displaystyle y_{n+1}=y_{n}+h\sum _{j=1}^{\nu }b_{j}f\left(t_{n}+c_{j}h,\xi _{j}\right)}
  

  
    
      
        
          ξ
          
            j
          
        
        =
        
          y
          
            n
          
        
        +
        h
        
          ∑
          
            i
            =
            1
          
          
            ν
            −
            1
          
        
        
          a
          
            ν
            ,
            i
          
        
        f
        (
        
          t
          
            n
          
        
        +
        
          c
          
            i
          
        
        h
        ,
        
          ξ
          
            i
          
        
        )
      
    
    {\displaystyle \xi _{j}=y_{n}+h\sum _{i=1}^{\nu -1}a_{\nu ,i}f(t_{n}+c_{i}h,\xi _{i})}
  Der 
  
    
      
        
          a
          
            ν
            ,
            i
          
        
      
    
    {\displaystyle a_{\nu ,i}}
  , 
  
    
      
        
          b
          
            j
          
        
      
    
    {\displaystyle b_{j}}
   og 
  
    
      
        
          c
          
            i
          
        
      
    
    {\displaystyle c_{i}}
   er konstanter. For å få ønsket orden må disse konstantene stemme overens med Taylor-utviklingen. Konstantene kan organiseres i et RK-tablå:


== 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)