NumMod 1 het 12

date: 2024.05.06

A második derivált közelítése

Definícióból a következőt jelenti a második derivált:

$$f^{\prime \prime }(x_i)=\underset{x\to x_i}{\lim }\frac{f^{\prime }(x)-f^{\prime }(x_i)}{x-x_i}$$

Kis $h$ esetén a második deriváltat a következőképpen tudjuk jól közelíteni:

$$f^{\prime \prime }(x_i)\approx \frac{f^{\prime }(x_i+h)-f^{\prime }(x_i)}{h}$$

Általában, amikor a második deriváltat kívánjuk közelíteni, az első deriváltat sem ismerjük. Így az első deriváltat is valahogyan közelítenünk kell. Szerencsére az előző fejezetben az első derivált közelítésével foglalkoztunk.

Közelítsük az első deriváltakat az előbb tanult módszerekkel.

Például mindkettőt a baloldali differenciahányadossal közelítjük

Így kapjuk a következő közelítést a második deriváltra:

$$f^{\prime \prime }(x_i)\approx \frac{\frac{f(x_i+h)-f(x_i)}{h}-\frac{f(x_i)-f(x_i-h)}{h}}{h}=\frac{f(x_i+h)-2f(x_i)+f(x_i-h)}{h^2}=:{\Delta }^2{f}_c$$

A fenti jelölésben a $c$ alső index a centrális szóbol ered.

Q.: Mi mondható a fenti közelítés rendjéről?

Állítás

Ez a bizonyos séma másodrendben közelíti $f^{\prime \prime }(x_i)$-t, ha eléggé sima függvény, azaz $f\in C^4(I)$
(Nem bizonyítjuk.)

A lépéstávolság dillemája

A következőkben arra a kérdésre próbálunk választ adni, hogy hogyan érdemes megválasztani a lépéstávolságokat, hogy minnél jobb közelítést érjünk el.

Hibaképletekből következik, hogy kisebb $h$ esetén kisebb hibát várunk.

Az $f(x_i)$ értéket gyakorlatban általában hibával terheltek (pl.: számábrázolási hiba, mérési hiba, stb.)

Mi következik ebből?

Tekintsük a $\Delta f_c$ központi sémát:

$$\Delta f_c:=\frac{f(x_i+h)-f(x_i-h)}{2h}$$

Tegyük fel, hogy $f(x_i+h)$ és $f(x_i-h)$ értéket valamilyen hibával terhelve ismerjük csak, ezért ${\tilde{f}}_{i-1}$ és ${\tilde{f}}_{i+1}$ értékekkel számolunk helyettük.

$$\Delta {\tilde{f}}_c=\frac{{\tilde{f}}_{i+1}-{\tilde{f}}_{i-1}}{2h}$$

és itt $f(x_i+h)={\tilde{f}}_{i+1}+{\epsilon }_{i+1}$ és $f(x_i-)={\tilde{f}}_{i-1}+{\epsilon }_{i-1}$

Továbbá, tegyük fel, hogy $|{\epsilon }_{i+1}|,|{\epsilon }_{i-1}|\le \epsilon >0$

Ekkor a következő összefüggést írhatjuk fel:

$$\Delta f_c=\frac{f(x_i+h)-f(x_i-h)}{2h}=\frac{{\tilde{f}}_{i+1}+{\epsilon }_{i+1}-{\tilde{f}}_{i-1}-{\epsilon }_{i-1}}{2h}=\stackrel{\Delta {\tilde{f}}_c}{\overbrace{\frac{{\tilde{f}}_{i+1}-{\tilde{f}}_{i-1}}{2h}}}+\frac{{\epsilon }_{i+1}-{\epsilon }_{i-1}}{2h}$$ $$f^{\prime }(x_i)+\frac{h^2}{6}{f}^{\prime \prime }(\eta )=\Delta {\tilde{f}}_c+\frac{{\epsilon }_{i+1}-{\epsilon }_{i-1}}{2h}$$ $$⟹|f^{\prime }(x_i)-\Delta {\tilde{f}}_c|\le \stackrel{g(h)}{\overbrace{\frac{h^2}{6}{M}_3+\frac{2\epsilon }{2h}}}$$

ahol $M_3:=\sup |f^{\prime \prime }|$

Látható, hogy a hibára felső korlátot adő $g(h)$ függvényben a második tag nő, ha csökken $h$. Tehát, $h$ nem választhatő sem túl negynak, sem túl kicsinek.

Q.: Mi lesz az optimális $h$ lépésköz?

$g(h)$-nak ott lehet minimuma, ahol a deriváltja $0$, azaz $g^{\prime }(h)=0$

$$g^{\prime }(h)=\frac{1}{3}h{M}_3-\frac{\epsilon }{h^2}=0$$ $$h^3=\frac{3\epsilon }{M_3}⟹h_{\text{opt}}={\left(\frac{3\epsilon }{M_3}\right)}^{1/3}$$

KDE-k megoldása

Megoldandó:

$$\text{(1)}{y}^{\prime }(t)=f(t,y(t)),t\in [t_0,T]$$ $$\text{(2)}y(t_0)=y_0$$

A fenti egy úgynevezett Cauchy-feladat.

Felmerül a probléma, hogy a pontos megoldást nem tudjuk mindig zárt alakban felírni

Véges külömbséges módszerek

(1)(2) egyenleteket diszkretizáljuk. Azaz, a $[t_0,T]$ intervallumon definiáljuk a következő rácshálót:

Legyen $N\in {\mathbb{N}}^{+}$ és jelöljük ${\omega }_{\tau }$-val a következő halmazt:

$${\omega }_{\tau }:=\left\{t_n=t_0+n\cdot \tau :n=0,1,\dots ,N,\tau =\frac{T-t_0}{N}\right\}$$

Egy folytonos függvény helyett egy olyan függvényt fogunk válaszul adni, mely csak ezeken a rácspontokon értelmezett. Gyakorlatilag egy vektort fogunk kapni, ahol az $i$-edik koordináta az $i$-edik rácsponton felvett függvényértéket jelképezi.

A megoldást csak az ${\omega }_{\tau }$ pontjaiban közelítjük. Tehát a numerikus megyoldás egy rácspontfüggvény lesz.

Jelölje a $t_n$ rácspontban a numerikus megoldást $y_n$. Szeretnénk, hogy ez köztel legyen a pontos megoldáshoz, azaz $y(t_n)$ értékhez.

Q.: Hogyan konstruálhatunk egy, a megoldást közelítő rácspontfüggvényt?

Explicit Euler-módszer (EE)

Az elejéről építjük fel a rácshálót.

$t_0$-ban $y(t_0)=y_0$ adva van.

$$y_1=?$$

Fejtsük sorba az $y$ pontos megoldást a $t_0$ körül. Ha $y\in C^2[t_0,T]$ akkor a következőt állíthatjuk:

$$y(\stackrel{t_1}{\overbrace{t_0+\tau }})=y(t_0)+y^{\prime }(t_0)\cdot \tau +O({\tau }^2)=y_0+f(t_0,y(t_0))\cdot \tau +O({\tau }^2)=y_0+f(t_0,y_0)\cdot \tau +O({\tau }^2)$$

Tehát, ha $\tau$ kicsi, akkor $O({\tau }^2)$ tag elhanyagolható és a következő közelítést kapjuk:

$$y(t_1)\approx y_0+f(t_0,y_0)\cdot \tau =:y_1$$

Ezután iteráljuk az eljárást: $y_1⇝y_2⇝\cdots ⇝y_N$

$$y_{n+1}=y_n+f(t_n,y_n)\cdot \tau$$

Megjegyzés: Ez úgy is megkapható, hogy az (1)-es egyenletben az $y^{\prime }$-t jobboldali differenciahányadossal közelítjük:

$$\frac{y_{n+1}-y_n}{\tau }=f(t_n,y_n)$$

Ezt átrendezve valóban az előbb kapott képletet visszakapjuk.

Grafikusan az implicit Euler-módszer azt jelenti, hogy az $y_n$ pontból az $y_{n+1}$ pontba úgy jutunk el, hogy a $t_n$ pontban az $y$ pontos megoldásnak a meredekségével lépünk előre $\tau$ hosszút az $y_n$ ponttól. Azaz a megoldás iránymező alapján lépkedünk mindig $\tau$ hosszúakat a mező irányába.

Ezt a módszert azért híváják explicit módszernek, mert eggyoldalra rendezve ki lehet fejezni $y_{n+1}$ értéket.

Implicit Euler-módszer (IE)

Az EE-módszer képletében $f$-et ne $(t_n,y_n)$-ben, hanem $(t_{n+1},y_{n+1})$-ben értékeljük ki:

$$y_{n+1}=y_n+f(t_{n+1},y_{n+1})\cdot \tau$$

A fenti képletben felmerül a probléma, hogy $y_{n+1}$ kiszámításához kéne tudni $y_{n+1}$ értéket, mert szerepel a jobboldalon $f$ függvény hasában.

Tekinstünk a fenti képletre mint egy egyenletre és oldjuk meg $y_{n+1}$-re.

Jelölje $x:=y_{n+1}$. Megoldandó: $x$-re a következő egyenlet:

$$x=y_n+f(t_{n+1},x)\cdot \tau$$

Ezt az egyenletet midnen időlépésben meg kell oldanunk.

Az egyenletet meg tudjuk oldani előző fejezetekben tanult iterációs módszerekkel, például Newton-iterációval.

Rendezzünk $0$-re az egyenletet:

$$\stackrel{F(x)}{\overbrace{x-y_n-f(t_{n+1},x)\cdot \tau }}=0$$

Válasszunk $x_0$ kezdőértéket

$$x_{k+1}=x_k-\frac{F(x_k)}{F^{\prime }(x_k)}$$

Érdemes meggondolni, hogy $F^{\prime }(x)$ hogyan írható fel.

$$F^{\prime }(x)=1-{\partial }_{x}f(t_{n+1},x)\cdot \tau$$

Runge-Kutta módszerek

Egy fokkal bonyolultabb módszer:
Azt csináljuk, hogy az $y(t_n)$ pontban megnézzük a meredekséget és csak $t_n+\frac{\tau }{2}$ ponttig megyünk el és megnézzük itt is a meredekséget és miután ezt kiszámoltuk, ezzel a meredekséggel fogunk $y_n$-ből lépni.

Jelölje $k_1=f(t_n,y_n)$
$y_n+k_1\cdot \frac{\tau }{2}$
Így $k_2=f\left(t_n+\frac{\tau }{2},y_n+k_1\frac{\tau }{2}\right)$
$y_{n+1}=y_n+k_2\tau$

összegezve:

$$y_{n+1}=y_n+f\left(t_n+\frac{\tau }{2},y_n+f(t_n,y_n)\cdot \frac{\tau }{2}\right)\cdot \tau$$

Ez egy kétlépcsős Runge-Kutta módszer. Lehet általánosabban $s$ lépcsős Runga-Kutta módszert is definiálni.

$[t_n,t_{n+1}]$ intervallumon $s$ pontban számítjuk ki a meredekséget és ezeket súlyozzuk és végül ezen súlyozott meredekségek összegével lépünk $y_n$-ből $y_{n+1}$-be.

A legelterjettebb Runge-Kutta módszer az RK4 módszer, amely $4$ lépcsős.

A következő a képlete:

$$\begin{array}{rl}{k}_1& =f(t_n,y_n)\\ k_2& =f\left(t_n+\frac{\tau }{2},y_n+k_1\frac{\tau }{2}\right)\\ k_3& =f\left(t_n+\frac{\tau }{2},y_n+k_2\frac{\tau }{2}\right)\\ k_4& =f(t_n+\tau ,y_n+k_3\tau )\\ y_{n+1}& =y_n+\tau \left(\frac{1}{6}{k}_1+\frac{1}{3}{k}_2+\frac{1}{3}{k}_3+\frac{1}{6}{k}_4\right)\end{array}$$

related: NumMod 1