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. 

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

där 

För några konstanter A1, A2, B och Q som uppfyller 

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

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

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å 
.
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.

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

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. 

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

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

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 

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

där

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

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

där

 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  för nuvarande lutning och lutningen vid  av steglängden fick vikten . Konstanterna blev således 

Då ser Ralstons metod ut så här

där

 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

där  är vikterna och  är h'' multiplicerat med uppskattningar av lutningen på stegintervallet, och ges av 

där  och  ä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 

där

Den totala lutningen är då medelvärdet vid fyra olika punkter i stegintervallet. Vikterna är  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.

där

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  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.

Se även 
 Taylorseriemetod
 Heuns metod
 Mittpunktsmetoden
 Eulers stegmetod

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 

Numerisk analys