Runge-Kuttametoden

Från Wikipedia
Hoppa till: navigering, sök

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 förra sekelskiftet 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[redigera | redigera wikitext]

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-Kutta metoden 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 man inte har några krav på vilka punkter som funktionsvärdet ska beräknas i, valde Runge och Kutta dem så de uppfyllde Taylorpolynomet av en viss ordning, som då även kallas ordningen av Runge-Kutta metoden.

Andra ordningens Runge-Kutta metod[redigera | redigera wikitext]

Runge-Kutta metoden skrivs allmänt

y_{i+1} = y_i + (A_1k_1 + A_2k_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 A1, A2, B och Q som uppfyller

A_1 + A_2 = 1
A_2B = \frac{1}{2}
A_2Q = \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'(x0) med f(x,y) eftersom det är den differentalekvation som ska lösas, samt sätta xx0 = 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-Kutta metod 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_1k_1 + A_2k_2)h

där k1 är början av stegintervallet och k2 är någon punkt längre fram som ges av (xi + Bh, yi + Qhk1).

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 k2 innehåller information om värdet vid en punkt framför (xi, yi) måste den funktionen Taylorutvecklas kring x.

k_2 = f(x,y) + f_x(x,y)Bh+f_y(x,y)Qhk_0 + \mathcal{O}(h^3)

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

y_{i+1} = y_i + (A_1+A_2)hf(x_i,y_i)+A_2h^2Bf_x(x_i,y_i)+A_2h^2Qf_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_2B = \frac{1}{2} \,\,\,\,\,\, A_2Q = \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 ekvationer än obekanta.

Genom att välja olika uppsättningar på konstanter fås olika Runge-Kutta metoder. Det finns åtminsone tre olika metoder som brukar användas.

Heuns metod[redigera | redigera wikitext]

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_2B = \frac{1}{2} \iff B = 1
A_2Q = \frac{1}{2} \iff Q = 1

Sätts dessa konstanter in i den allmänna Runge-Kutta formen 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_1h)


Mittpunktsmetoden[redigera | redigera wikitext]

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 k1 inte explicit ingår i uttrycket för yi+1, men det måste ändå beräknas för ge y-koordinaten till k2.

I mittpunktsmetoden väljer man följande konstanter

A_2 = 1
A_1 + A_2 = 1 \iff A_1 = 0
A_2B = \frac{1}{2} \iff B = \frac{1}{2}
A_2Q = \frac{1}{2} \iff Q = \frac{1}{2}

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

y_{i+1} = y_i + k_2h

där

k_1 = f(x_i,y_i) \text{ och } k_2 = f(x_i+\frac{h}{2},y_i+\frac{k_1h}{2})


Ralstons metod[redigera | redigera wikitext]

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_2B = \frac{1}{2} \iff B = \frac{3}{4}
A_2Q = \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_1h}{4})

Fjärde ordningens Runge-Kutta[redigera | redigera wikitext]

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 Kutta metod kan skrivas

y_{i+1} =  y_i + w_1k_1 + w_2k_2+w_3k_3 + w_4k_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_1h,y_i+b_1k_1)
k_3 = hf(x_i+a_2h,y_i+b_2k_1+b_3k_2)
k_4 = hf(x_i+a_3h,y_i+b_4k_1+b_5k_2+b_6k_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-Kutta metod, kan man visa att det blir 13 konstanter som ska uppfylla 11 ekvationer.


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

Runges metod[redigera | redigera wikitext]

När man bara säger Runge-Kutta metoden ä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-Kutta metoden 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[redigera | redigera wikitext]

Det här är den form som Kutta föredrog mest. Den liknar mycket Runges metod, enda skillnaden är att värdena av funktionen beräknas i andra punkter och de ges lite andra 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[redigera | redigera wikitext]

Det är sällan som Runge-Kutta metoden 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[redigera | redigera wikitext]

Mathias Lundgren har skrivit en låt om Runge-Kuttametoden där han beskriver hur Eulers stegmetod inte räcker till för att approximera en differentialekvation. En röst i hans huvud säger till honom att prova Runge-Kuttan och plötsligt minskade felet till h5. Han blir överlycklig och dansar Runge-Runge-Kutta! [1]

Matlab använder en fjärde ordningens Runge-Kutta algoritm 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. [2]

Se även[redigera | redigera wikitext]

Läs mer[redigera | redigera wikitext]

Referenser[redigera | redigera wikitext]

  1. ^ ”Matte Matik - Runge Kuttan” (MP3). Nya hyss i vektorrummet. http://www.helgo.net/gavel/sound/Matte%20Matik%20-%20Runge%20Kuttan.mp3. Läst 7 maj 2012. 
  2. ^ Erik Cheever. ”The 2nd Order Runge-Kutta Method”. http://www.swarthmore.edu/NatSci/echeeve1/Ref/NumericInt/RK2.html. Läst 7 maj 2012.