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
[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–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
[redigera | redigera wikitext]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
[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
Sätts dessa konstanter in i den allmänna Runge–Kuttaformen fås
där
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
Sätter vi in dessa konstanter så fås
där
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 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
[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 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
[redigera | redigera wikitext]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
[redigera | redigera wikitext]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
[redigera | redigera wikitext]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
[redigera | redigera wikitext]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
[redigera | redigera wikitext]Läs mer
[redigera | redigera wikitext]- 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
[redigera | redigera wikitext]- ^ 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.