Runge–Kuttametoden

Runge–Kuttametoden är ett viktigt hjälpmedel för att approximera lösningar till ordinära differentialekvationer. Egentligen är det en hel grupp metoder, varav vissa har fått egna namn. Dessa metoder utvecklades kring år 1900 av de tyska matematikerna Carl Runge och Martin Wilhelm Kutta.

De fokuserade på första ordningens icke-separabla differentialekvationer eftersom differentialekvationer av högre ordning går att transformera till ekvationssystem av första ordningens ekvationer, och separabla differentialekvationer går att lösa genom att (numeriskt) integrera bägge leden.

{\frac {dy}{dx}}=f(x,y){\text{, där }}y(x_{0})=y_{0}

Eulers stegmetod hade länge används för att numeriskt lösa denna typ av differentialekvationer. Men vid 1900-talets början fanns ett behov av att göra mer exakta beräkningar. Runge och Kutta sökte tillsammans efter en metod som gav en mer noggrann lösning.

Beskrivning

Taylors seriemetod är betydligt bättre än Eulers stegmetod på att hålla avvikelserna från lösningen små, men den har nackdelen att man måste beräkna högre ordningens derivator av f(x,y) vilket i allmänhet kan vara svårt.

Runge–Kuttametoden går ut på att behålla fördelarna från Taylorutvecklingen, men byta ut de högre ordningens derivator mot funktionsvärdet av f(x,y) i vissa punkter inom steglängden.

Eftersom det inte finns några krav på i vilka punkter funktionsvärdet skall beräknas, valde Runge och Kutta punkterna så att de uppfyllde Taylorpolynomet av en viss ordning och denna ordning kallas även Runge–Kuttametodens ordning.

Andra ordningens Runge–Kuttametod

Runge–Kuttametoden skrivs allmänt

y_{i+1}=y_{i}+(A_{1}k_{1}+A_{2}k_{2})h

där

k_{1}=f(x_{i},y_{i})

k_{2}=f(x_{i}+Bh,y_{i}+Qhk_{1})

För några konstanter A₁, A₂, B och Q som uppfyller

A_{1}+A_{2}=1

A_{2}B={\frac {1}{2}}

A_{2}Q={\frac {1}{2}}

.

Ekvationerna för konstanterna kommer från Taylorutvecklingen av y(x)

y(x)=y(x_{0})+y'(x_{0})(x-x_{0})+{\frac {y''(x_{0})}{2!}}(x-x_{0})^{2}+{\mathcal {O}}(x^{3})

Det går att ersätta y'(x₀) med f(x,y) eftersom det är den differentalekvation som ska lösas, samt sätta x − x₀ = h, som är steglängden i varje iteration.

y_{i+1}=y_{i}+f(x_{i},y_{i})h+{\frac {f'(x_{i},y_{i})}{2!}}h^{2}+{\mathcal {O}}(h^{3})

.

Om man bara väljer de två första termerna fås exakt samma utseende som Eulers stegmetod. Faktiskt kan Eulers stegmetod ses som en Runge–Kuttametod av ordning 1. Vill bättre resultat uppnås än det Euler ger, så verkar det rimligt att ta med fler termer i Taylorutvecklingen.

Eftersom y beror av x kan vi dela upp f'(x,y(x)) i dess partiella derivator och få

y_{i+1}=y_{i}+f(x_{i},y_{i})h+{\frac {h^{2}}{2!}}(f_{x}(x_{i},y_{i})+f_{y}(x_{i},y_{i})f(x_{i},y_{i}))+{\mathcal {O}}(h^{3})

.

Runge och Kutta ville inte beräkna derivatan av funktionen så de ansatte att lutningen kunde skrivas som en linjärkombination av några funktionsvärden i vissa punkter x.

y_{i+1}=y_{i}+(A_{1}k_{1}+A_{2}k_{2})h

där k₁ är början av stegintervallet och k₂ är någon punkt längre fram som ges av (x_i + Bh, y_i + Qhk₁).

k_{1}=f(x_{i},y_{i})

k_{2}=f(x_{i}+{B}h,y_{i}+{Q}{k_{1}}h)

Det vackra med detta är att Runge och Kutta inte längre behövde hitta derivatan av funktionen f. Genom att bestämma funktionens värde i rätt punkter kunde de bibehålla noggrannheten från Taylorutvecklingen, utan att beräkna derivatorna. För att få rätt värden på konstanterna jämförde Runge och Kutta sin ansats med en äkta Taylorutveckling och satte upp några villkor på konstanterna.

Eftersom k₂ innehåller information om värdet vid en punkt framför (x_i, y_i) måste den funktionen Taylorutvecklas kring x.

k_{2}=f(x,y)+f_{x}(x,y)Bh+f_{y}(x,y)Qhk_{1}+{\mathcal {O}}(h^{3})

Sen sätts detta in i uttrycket för y_i+1

y_{i+1}=y_{i}+(A_{1}+A_{2})hf(x_{i},y_{i})+A_{2}h^{2}Bf_{x}(x_{i},y_{i})+A_{2}h^{2}Qf_{y}(x_{i},y_{i})f(x_{i},y_{i})+{\mathcal {O}}(h^{3})

.

Genom att jämföra detta med den äkta Taylorutvecklingen fås tre ekvationer,

A_{1}+A_{2}=1\,\,\,\,\,\,A_{2}B={\frac {1}{2}}\,\,\,\,\,\,A_{2}Q={\frac {1}{2}}

.

Det är tre ekvationer och fyra okända som uppfyller Taylorutvecklingen och Runge Kuttas ansats upp till andra ordningen. Det går alltså att välja konstanterna på oändligt många sätt eftersom vi har fler obekanta än ekvationer.

Genom att välja olika uppsättningar på konstanter fås olika Runge–Kuttametoder. Det finns åtminstone tre olika metoder som brukar användas.

Heuns metod

Heuns metod kan rent geometriskt ses som medelvärdet av lutningen där du är, och i den x-koordinat du hamnar i nästa iteration.

Skillnaden mot Eulers metod är alltså att du även tar hänsyn till lutningen i punkten du är på väg till. Det är Eulers metod som används för att bestämma y-koordinaten för den punkt där den andra lutningen bestäms.

För Heuns metod väljs konstanterna

A_{2}={\frac {1}{2}}

A_{1}+A_{2}=1\iff A_{1}={\frac {1}{2}}

A_{2}B={\frac {1}{2}}\iff B=1

A_{2}Q={\frac {1}{2}}\iff Q=1

Sätts dessa konstanter in i den allmänna Runge–Kuttaformen fås

y_{i+1}=y_{i}+({\frac {1}{2}}k_{1}+{\frac {1}{2}}k_{2})h

där

k_{1}=f(x_{i},y_{i}){\text{ och }}k_{2}=f(x_{i}+h,y_{i}+k_{1}h)

Mittpunktsmetoden

Den kallas för mittpunktsmetoden eftersom man väljer att beräkna lutningen mitt i steglängden, i en punkt mellan den vi är nu och den vi är på väg till. Ibland kallas den även för en modifierad Eulers stegmetod.

Observera att k₁ inte explicit ingår i uttrycket för y_i+1, men det måste ändå beräknas för ge y-koordinaten till k₂.

I mittpunktsmetoden väljer man följande konstanter

A_{2}=1

A_{1}+A_{2}=1\iff A_{1}=0

A_{2}B={\frac {1}{2}}\iff B={\frac {1}{2}}

A_{2}Q={\frac {1}{2}}\iff Q={\frac {1}{2}}

Sätter vi in dessa konstanter så fås

y_{i+1}=y_{i}+k_{2}h

där

k_{1}=f(x_{i},y_{i}){\text{ och }}k_{2}=f(x_{i}+{\frac {h}{2}},y_{i}+{\frac {k_{1}h}{2}})

Ralstons metod

Ralston valde att beräkna riktningen till nästa punkt som ett viktat medelvärde av de två punkternas lutning. Han satte vikten ${\tfrac {1}{3}}$ för nuvarande lutning och lutningen vid ${\tfrac {3}{4}}$ av steglängden fick vikten ${\tfrac {2}{3}}$ . Konstanterna blev således

A_{2}={\frac {2}{3}}

A_{1}+A_{2}=1\iff A_{1}={\frac {1}{3}}

A_{2}B={\frac {1}{2}}\iff B={\frac {3}{4}}

A_{2}Q={\frac {1}{2}}\iff Q={\frac {3}{4}}

Då ser Ralstons metod ut så här

y_{i+1}=y_{i}+({\frac {k_{1}}{3}}+{\frac {2k_{2}}{3}})h

där

k_{1}=f(x_{i},y_{i}){\text{ och }}k_{2}=f(x_{i}+{\frac {3h}{4}},y_{i}+{\frac {3k_{1}h}{4}})

Fjärde ordningens Runge–Kutta

Högre ordningens Runge–Kuttametoder är mer praktiska att använda eftersom de ger ett bättre resultat. Enda skillnaden är att man tar med fler termer i Taylorutvecklingen och därmed får fler ekvationer och okända.

För fjärde ordningens Runge Kuttametod kan skrivas

y_{i+1}=y_{i}+w_{1}k_{1}+w_{2}k_{2}+w_{3}k_{3}+w_{4}k_{4}

där $w_{1},\ldots$ är vikterna och $k_{1},\ldots$ är h multiplicerat med uppskattningar av lutningen på stegintervallet, och ges av

k_{1}=hf(x_{i},y_{i})

k_{2}=hf(x_{i}+a_{1}h,y_{i}+b_{1}k_{1})

k_{3}=hf(x_{i}+a_{2}h,y_{i}+b_{2}k_{1}+b_{3}k_{2})

k_{4}=hf(x_{i}+a_{3}h,y_{i}+b_{4}k_{1}+b_{5}k_{2}+b_{6}k_{3})

där $a_{1},\ldots$ och $b_{1},...$ är konstanter som måste bestämmas. Genom att använda samma tekniker som för andra ordningens Runge–Kuttametod, kan man visa att det blir 13 konstanter som ska uppfylla 11 ekvationer.

Precis som för andra ordningens Runge–Kuttametod finns det flera uppsättningar av konstanter som man brukar använda.

Runges metod

När man bara säger Runge–Kuttametoden är det ofta den här man syftar på. Den benämns även RK4, eller Runges metod eftersom det var Runge själv som valde ut dessa konstanter.

Med Runges konstanter så ser Runge–Kuttametoden ut såhär

y_{i+1}=y_{i}+{\frac {h}{6}}(f_{1}+2f_{2}+2f_{3}+f_{4})

där

f_{1}=f(x_{i},y_{i})

f_{2}=f(x_{i}+{\frac {h}{2}},y_{i}+{\frac {h}{2}}f_{1})

f_{3}=f(x_{i}+{\frac {h}{2}},y_{i}+{\frac {h}{2}}f_{2})

f_{4}=f(x_{i}+h,y_{i}+hf_{3})

Den totala lutningen är då medelvärdet vid fyra olika punkter i stegintervallet. Vikterna är ${\tfrac {1}{6}},{\tfrac {1}{3}},{\tfrac {1}{3}},{\tfrac {1}{6}}$ så de två punkterna i mitten bidrar till största del till den totala lutningen.

Kuttas metod

Det här är den form som Kutta föredrog. Den liknar mycket Runges metod, skillnaden är att värdena av funktionen beräknas i andra punkter och ges något annorlunda vikter.

y_{i+1}=y_{i}+{\frac {h}{8}}(f_{1}+3f_{2}+3f_{3}+f_{4})

där

f_{1}=f(x_{i},y_{i})

f_{2}=f(x_{i}+{\frac {h}{3}},y_{i}+{\frac {h}{3}}f_{1})

f_{3}=f(x_{i}+{\frac {2h}{3}},y_{i}-{\frac {h}{3}}f_{1}+hf_{2})

f_{4}=f(x_{i}+h,y_{i}+hf_{1}-hf_{2}+hf_{3})

Implementation i Python

Det är sällan som Runge–Kuttametoden används manuellt för hand. Det är datorprogram som snabbt itererar igenom metoden med tillräckligt kort steglängd för att få önskad precision.

Ett program som löser differentialekvationen ${\frac {dy}{dx}}=3e^{-4x}-2y(x)$ kan se ut såhär i Python

""" Exempel på RK4 i Python """ 
def runge():
    x = 0   # Begynnelsevärde för X
    y = 1   # Begynnelsevärde för Y
    h = 0.1 # Steglängd
    end = 4 # Slutvärde för X
    
    while x <= end :
        f1 = f(x, y)
        f2 = f(x + h/2, y + h*f1/2)
        f3 = f(x + h/2, y + h*f2/2)
        f4 = f(x + h, y + h*f3)
        x += h
        y += h*(f1 + 2*f2 + 2*f3 + f4)/6
        
        print('%10f %10f' % (x, y))

""" Exempelfunktion """
def f(x, y):
    return 3*math.exp(-4*x) - 2*y

Övrigt

Matlab använder en fjärde ordningens Runge–Kuttaalgoritm med varierbar steglängd. Steglängden ökar där det är möjligt för att snabba upp uträkningarna och minskas där det krävs hög noggrannhet. ^[1]

Se även

Läs mer

http://pathfinder.scar.utoronto.ca/~dyer/csca57/book_P/node50.html läst 7 maj 2012
http://www.youtube.com/watch?v=ihEfPp5WRcE, sedd 7 maj 2012
"Runge–Kutta Methods with Minimum Error Bounds", Anthony Ralston, 1961

Referenser

^ Erik Cheever. ”The 2nd Order Runge-Kutta Method”. Arkiverad från originalet den 26 april 2012. https://web.archive.org/web/20120426090423/http://www.swarthmore.edu/NatSci/echeeve1/Ref/NumericInt/RK2.html. Läst 7 maj 2012.

[1] Erik Cheever. ”The 2nd Order Runge-Kutta Method”. Arkiverad från originalet den 26 april 2012. https://web.archive.org/web/20120426090423/http://www.swarthmore.edu/NatSci/echeeve1/Ref/NumericInt/RK2.html. Läst 7 maj 2012.

[1]