ODE

Ordinära differentialekvationer - ODE

Min plan var att göra en pendel men först vill jag ha en bra ode-lösare.

Det finns ett exempel i slutet som du kan hoppa till om du redan är inläst.

Vi börjar med att definiera problemet:

\frac{d y}{d x} = f (y, x)

Vi säger att funktionen $f$ deriverar $y$ med avseende på $x$

Man kan såklart sätta $x = t$ för att få:

y' = f (y, t)

Eulers metod

Den lättaste lösningen är Eulers-metod: (aka Eulers stegmetod, Eulersteg, osv.)

y' = f (y, t), y_{0} = y (t_{0})

y' = \frac{Δ y}{Δ t} = \frac{y_{n + 1} - y_{n}}{t_{n + 1} - t_{n}} \Leftrightarrow y_{n + 1} = y_{n} + y' Δ t

y_{n + 1} = y_{n} + f (y_{n}, t_{n}) Δ t

Vi testar med det lättaste fallet:

y' = y, y_{0} = 1

Vilket ger oss: (tidsinvariant)

f (y, t) = y

y_{n + 1} = y_{n} + y_{n} Δ t = y_{n} (1 + Δ t)

Man ser snabbt i plotten att Eulers metod underskattar funktionsvärdet.
Man kan räkna ut felet med hjälp av en annan härledning av Eulers metod.
Vi börjar med taylor-serien för $y$ i punkt $a$ :

y (t) = y (a) + y^{'} (a) (t - a) + \frac{y^{''} (a)}{2!} (t - a)^{2} + . . . = \sum_{n = 0}^{\infty} \frac{y^{(n)} (a)}{n!} (t - a)^{n}

Nu byter vi ut $y'$ mot $f (y, t)$ med $a = t_{n}$ och skriver det i diskret form:

y_{n + 1} = y_{n} + f (y_{n}, t_{n}) (t_{n + 1} - t_{n}) + \frac{f^{'} (y_{n}, t_{n})}{2!} (t_{n + 1} - t_{n})^{2} + . . . + \frac{f^{(n)} (y_{n}, t_{n})}{n!} (t_{n + 1} - t_{n})^{n}

Med $(t_{n + 1} - t_{n}) = Δ t$ blir de första två termerna:

y_{n + 1} = y_{n} + f (y_{n}, t_{n}) Δ t

Det ser ju i princip exakt ut som uttrycket för Eulers metod.
Därför kan vi subtrahera bort uttrycket för Eulers metod från taylor-utvecklingen och få felet:

ε_{n} = \sum_{n = 2}^{\infty} \frac{f^{(n)} (y_{n}, t_{n})}{n!} Δ t^{n} = \frac{f^{'} (y_{n}, t_{n})}{2!} Δ t^{2} + . . . + \frac{f^{(n)} (y_{n}, t_{n})}{n!} Δ t^{n}

Hur ska vi då göra för att minska felet?
En bra start kan ju vara att plocka lite fler termer från taylor-serien, då tar det längre tid för felet att ackumuleras.
Problemet blir att derivera $f$ ...

Kan det finnas något annat sätt att minska felet?

Eftersom vi räknar med derivatan i punkt $n$ kommer
den hinna ändras hos lösningen innan vi når punkt $n + 1$ .
Om man istället tar ett eulersteg från $n - 1$ till $n$ och sedan ett till $n + 1$
och räknar derivatan från $n - 1$ till $n + 1$
borde den stämma bättre överens med den sanna funktionen.

Kolla bara på dom gröna linjerna, dom ser ju ut att stämma rätt bra,
vi måste bara komma ihåg att dela med 2.

Mittpunktsmetoden

Mittpunktsmetoden/modifierat eulersteg: (likt trapetsmetoden)
För att ta vårt extra steg kan vi ju helt enkelt mata funktionen $f$ med sig själv.

y' = f (y, t), y_{0} = y (t_{0})

y_{n + 1} = y_{n} + f (y_{n} + f (y_{n}, t_{n}) \frac{Δ t}{2}, t_{n} + \frac{Δ t}{2}) Δ t

I exemplet $y^{'} = y = f (y, t), y_{0} = y (t_{0}) = 1$ blir mittpunktssteget:

y_{n + 1} = y_{n} + y_{n} Δ t + y_{n} \frac{Δ t^{2}}{2}

Vilket är Eulersteget med en extra term från taylor-serien. I plotten syns att mittpunktsmetoden är betydligt bättre än Eulers metod.
Men vi har fler termer i taylor-serien så vi kan hitta en bättre lösning.

Runge-Kutta 4

Alla metoderna ovan är del av Runge-Kutta familjen.
RK4 blir sista bossen idag.
Då Eulersteget inkluderar 2 termer från taylor-utvecklingen kallar vi den en första ordningens Runge-Kutta metod. (Vi räknar inte första termen)
Då följer att mittpunktsmetoden blir en andra ordningens RK metod.
Vi skiter i 3:dje ordningens metoder och går direkt på 4:de

y^{'} = f (y, t), y_{0} = y (t_{0})

k_{1} = f (y_{n}, t_{n})

k_{2} = f (y_{n} + \frac{k_{1}}{2} Δ t, t_{n} + \frac{Δ t}{2})

k_{3} = f (y_{n} + \frac{k_{2}}{2} Δ t, t_{n} + \frac{Δ t}{2})

k_{4} = f (y_{n} + k_{3} Δ t, t_{n} + Δ t)

y_{n + 1} = y_{n} + \frac{Δ t}{6} (k_{1} + 2 k_{1} + 2 k_{3} + k_{4})

y_{n + 1} = y_{n} + y_{n} Δ t + y_{n} \frac{Δ t^{2}}{2}

Här tar man 4 skattningar och räknar ut ett viktat genomsnitt av derivatan. Hemläxa blir att härleda $y_{n + 1}$ för:

y^{'} = y = f (y, t), y_{0} = y (t_{0}) = 1

Fet hint: det är en fjärde ordningens metod

Formeln för RK4 ser ut som en röra så för att snygga till det finns Butcher-tabellen:

$c_{1}$	$a_{11}$	$a_{12}$	...	$a_{1s}$
$c_{2}$	$a_{21}$	$a_{22}$	...	$a_{2s}$
⋮	⋮		⋱	...
$C_{s}$	$a_{s1}$	$a_{s2}$	...	$a_{ss}$
	$b_{1}$	$b_{2}$	...	$b_{s}$

Där:

\sum_{i = 1}^{s} b_{i} = 1

\sum_{j = 1}^{s} a_{i j} = c_{i}

RK4:s tabell:

0
½	½
½	0	½
1	0	0	1
	⅙	⅓	⅓	⅙

Tabellerna ovan kan användas i formeln:

k_{n i} = f (y_{n} + Δ t \sum_{j = 1}^{i - 1} a_{i j} k_{n j}, t_{n} + c_{i} Δ t)

y_{n + 1} = y_{n} + Δ t \sum_{i = 1}^{s} b_{i} k_{n i}

Och här är Butcher-tabellerna för Euler:

0
	1

och för midpoint:

0
α	α
	$(1 - \frac{1}{2 α})$	$\frac{1}{2 α}$

Där $α = \frac{1}{2}$ Ger mittpunktsmetoden och $α = 1$ ger Heuns metod.

Så alla dessa metoder är bara diskreta integratorer, vilket inte låter särskillt spännande,
man behöver ju inte vara Einstein reinkarnerad för att lösa exempel-ekvationen...
Men det finns system där ett försök till en analytisk lösning vore psykologiskt självmord.
Om det låter spännande har jag gjort ett exempel: Lorentz-attraktorn

ODE

timestep

Euler

Midpoint

RK4

zoom

Ordinära differentialekvationer - ODE

Min plan var att göra en pendel men först vill jag ha en bra ode-lösare.

Det finns ett exempel i slutet som du kan hoppa till om du redan är inläst.

Vi börjar med att definiera problemet:

Vi säger att funktionen $f$ deriverar $y$ med avseende på $x$

Man kan såklart sätta $x = t$ för att få:

Eulers metod

Den lättaste lösningen är Eulers-metod: (aka Eulers stegmetod, Eulersteg, osv.)

Vi testar med det lättaste fallet:

Vilket ger oss: (tidsinvariant)

Man ser snabbt i plotten att Eulers metod underskattar funktionsvärdet.
Man kan räkna ut felet med hjälp av en annan härledning av Eulers metod.
Vi börjar med taylor-serien för $y$ i punkt $a$ :

Nu byter vi ut $y'$ mot $f (y, t)$ med $a = t_{n}$ och skriver det i diskret form:

Med $(t_{n + 1} - t_{n}) = Δ t$ blir de första två termerna:

Det ser ju i princip exakt ut som uttrycket för Eulers metod.
Därför kan vi subtrahera bort uttrycket för Eulers metod från taylor-utvecklingen och få felet:

Hur ska vi då göra för att minska felet?
En bra start kan ju vara att plocka lite fler termer från taylor-serien, då tar det längre tid för felet att ackumuleras.
Problemet blir att derivera $f$ ...

Kan det finnas något annat sätt att minska felet?

Mittpunktsmetoden

Mittpunktsmetoden/modifierat eulersteg: (likt trapetsmetoden)
För att ta vårt extra steg kan vi ju helt enkelt mata funktionen $f$ med sig själv.

I exemplet $y^{'} = y = f (y, t), y_{0} = y (t_{0}) = 1$ blir mittpunktssteget:

Vilket är Eulersteget med en extra term från taylor-serien. I plotten syns att mittpunktsmetoden är betydligt bättre än Eulers metod.
Men vi har fler termer i taylor-serien så vi kan hitta en bättre lösning.

Runge-Kutta 4

Här tar man 4 skattningar och räknar ut ett viktat genomsnitt av derivatan. Hemläxa blir att härleda $y_{n + 1}$ för:

Fet hint: det är en fjärde ordningens metod

Formeln för RK4 ser ut som en röra så för att snygga till det finns Butcher-tabellen:

Där:

RK4:s tabell:

Tabellerna ovan kan användas i formeln:

Och här är Butcher-tabellerna för Euler:

och för midpoint:

Där $α = \frac{1}{2}$ Ger mittpunktsmetoden och $α = 1$ ger Heuns metod.

Alternativt om man föredrar en extra dimension: Lorentz 3D

ODE

timestep

Euler

Midpoint

RK4

zoom

Ordinära differentialekvationer - ODE

Min plan var att göra en pendel men först vill jag ha en bra ode-lösare.

Det finns ett exempel i slutet som du kan hoppa till om du redan är inläst.

Vi börjar med att definiera problemet:

Vi säger att funktionen f deriverar y med avseende på x

Man kan såklart sätta x=t för att få:

Eulers metod

Den lättaste lösningen är Eulers-metod: (aka Eulers stegmetod, Eulersteg, osv.)

Vi testar med det lättaste fallet:

Vilket ger oss: (tidsinvariant)

Man ser snabbt i plotten att Eulers metod underskattar funktionsvärdet. Man kan räkna ut felet med hjälp av en annan härledning av Eulers metod. Vi börjar med taylor-serien för y i punkt a:

Nu byter vi ut y' mot f(y,t) med a=tn och skriver det i diskret form:

Med (tn+1−tn)=Δt blir de första två termerna:

Det ser ju i princip exakt ut som uttrycket för Eulers metod. Därför kan vi subtrahera bort uttrycket för Eulers metod från taylor-utvecklingen och få felet:

Hur ska vi då göra för att minska felet? En bra start kan ju vara att plocka lite fler termer från taylor-serien, då tar det längre tid för felet att ackumuleras. Problemet blir att derivera f... Kan det finnas något annat sätt att minska felet?

Mittpunktsmetoden

Mittpunktsmetoden/modifierat eulersteg: (likt trapetsmetoden) För att ta vårt extra steg kan vi ju helt enkelt mata funktionen f med sig själv.

I exemplet y′=y=f(y,t),y0=y(t0)=1 blir mittpunktssteget:

Vilket är Eulersteget med en extra term från taylor-serien. I plotten syns att mittpunktsmetoden är betydligt bättre än Eulers metod. Men vi har fler termer i taylor-serien så vi kan hitta en bättre lösning.

Runge-Kutta 4

Här tar man 4 skattningar och räknar ut ett viktat genomsnitt av derivatan. Hemläxa blir att härleda yn+1 för:

Fet hint: det är en fjärde ordningens metod

Formeln för RK4 ser ut som en röra så för att snygga till det finns Butcher-tabellen:

Där:

RK4:s tabell:

Tabellerna ovan kan användas i formeln:

Och här är Butcher-tabellerna för Euler:

och för midpoint:

Där α=12 Ger mittpunktsmetoden och α=1 ger Heuns metod.

Alternativt om man föredrar en extra dimension: Lorentz 3D

Vi säger att funktionen $f$ deriverar $y$ med avseende på $x$

Man kan såklart sätta $x = t$ för att få:

Man ser snabbt i plotten att Eulers metod underskattar funktionsvärdet.
Man kan räkna ut felet med hjälp av en annan härledning av Eulers metod.
Vi börjar med taylor-serien för $y$ i punkt $a$ :

Nu byter vi ut $y'$ mot $f (y, t)$ med $a = t_{n}$ och skriver det i diskret form:

Med $(t_{n + 1} - t_{n}) = Δ t$ blir de första två termerna:

Det ser ju i princip exakt ut som uttrycket för Eulers metod.
Därför kan vi subtrahera bort uttrycket för Eulers metod från taylor-utvecklingen och få felet:

Hur ska vi då göra för att minska felet?
En bra start kan ju vara att plocka lite fler termer från taylor-serien, då tar det längre tid för felet att ackumuleras.
Problemet blir att derivera $f$ ...

Kan det finnas något annat sätt att minska felet?

Mittpunktsmetoden/modifierat eulersteg: (likt trapetsmetoden)
För att ta vårt extra steg kan vi ju helt enkelt mata funktionen $f$ med sig själv.

I exemplet $y^{'} = y = f (y, t), y_{0} = y (t_{0}) = 1$ blir mittpunktssteget:

Vilket är Eulersteget med en extra term från taylor-serien. I plotten syns att mittpunktsmetoden är betydligt bättre än Eulers metod.
Men vi har fler termer i taylor-serien så vi kan hitta en bättre lösning.

Här tar man 4 skattningar och räknar ut ett viktat genomsnitt av derivatan. Hemläxa blir att härleda $y_{n + 1}$ för:

Där $α = \frac{1}{2}$ Ger mittpunktsmetoden och $α = 1$ ger Heuns metod.