Algoritmy numerického derivovania

Algoritmy a programovanie

---

Dátový typ

Štruktúry

Rekurzia

Algoritmy vyhľadávania

Algoritmy triedenia

Lineárny zoznam

Binárny strom

Numerické algoritmy

>Algoritmy hľadania nulových miest
>Algoritmy numerického derivovania
>Algoritmy numerického integrovania
>Algoritmy interpolácie
>Algoritmy aproximácie
>Algoritmy numerického riešenia diferenciálnych rovníc

Grafové algoritmy

Niektoré algoritmy, ako napr. hľadanie riešenie funkcie f(x)=0 pomocou Newtonovej metódy hľadania nulových miest potrebujú mať dispozícii prvú deriváciu funkcie f(x). Pri komplikovanejších funkciách je výhodnejšie si deriváciu funkcie f(x) vypočítať, resp. odhadnúť numerickými metódami.

Numerické derivovanie

Derivácia funkcie f(x) je definovaná nasledovne:

[math]f'(x) = \lim_{h\to 0} \frac{f(x+h)-f(x)}{h}[/math]

Tento vzťah je označovaný aj ako rozdielová diferencia alebo aj dopredná diferencia.

Podobný výsledok nám dá aj vzťah, ktorý je označovaný ako spätná diferencia:

[math]f'(x) = \lim_{h\to 0} \frac{f(x)-f(x-h)}{h}[/math]

Pri numerických výpočtoch eliminujeme limitu a hodnotu parametra h nastavíme na malú hodnotu. Odvodíme si vzorec pre výpočet prvej derivácie a aj chybu tohto výpočtu. Podľa Taylorovho rozvoja funkcie f(x) môžeme zapísať:

[math]f(x+h)=f(x)+hf'(x)+\frac{h^2}{2}f''(\xi), \xi\in(x,x+h)[/math]

Deriváciu f'(x) funkcie f(x) môžeme vyjadriť ako: [math]f'(x) = \frac{f(x+h)-f(x)}{h} - \frac{h}{2}f''(\xi), \xi\in(x,x+h)[/math]

Výraz [math]\frac{h}{2}f''(\xi)[/math] definuje chybu derivácie.

Je možné zapísať presnejší vzorec pre výpočet prvej derivácie. Namiesto funkčných hodnôt, ktoré sú od seba vzdialené o h, môžeme použiť funkčné hodnoty f(x-h) a f(x+h). Potom vzťah pre výpočet prvej derivácie je nasledovný:

[math]f'(x) \approx \frac{f(x-h)-f(x+h)}{2h}[/math]

Podobným princípom môžeme odhadnúť derivácie vyšších rádov. Pre druhú derivácu platí vzťah:

[math]f''(x) \approx \frac{f(x+h) - 2f(x) + f(x+h)}{h^2}[/math]

Presnešie odhady derivácie

Existujú metódy vyššieho rádu pre aproximovanie derivácie funkcie f(x). V predchádzajúcich metódach sme pre výpočet prvej derivácie uvažovali s hodnotu h, resp. 2h. Využime ešte väčší interval: 4h. Dostávame vzorec pre výpočet prvej derivácie pomocou piatich bodov:

[math]f'(x) = \frac{-f(x + 2h) + 8 f(x + h) - 8 f(x - h) + f(x - 2h)}{12h} + \frac{h^4}{30} f^{(5)}(c),[/math]

kde [math]c \in [x - 2h, x + 2h][/math] a [math]\frac{h^4}{30} f^{(5)}(c)[/math] je chyba metódy.

Stirlingova metóda aproximácie

Stirlingova metóda dokáže jednoduchým spôsobom vypočítať deriváciu f'(x) ak poznáme funkčné hodnoty f(x) v bodoch: x0-2h, x0-h, x0, x0+h, x0+2h. Stirlingova metóda využíva tabuľku centrálnych rozdielov:

x	[math]f(x)[/math]	[math]\delta f(x)[/math]	[math]\delta^2 f(x)[/math]	[math]\delta^3 f(x)[/math]	[math]\delta^4 f(x)[/math]
[math]x_0-2h[/math]	[math]f(x_0-2h)[/math] [math]\searrow[/math]
		[math]\delta f(x_0-\frac{3}{2}h)[/math]
[math]x_0-h[/math]	[math]f(x_0-h)[/math] [math]\nearrow[/math]		[math]\delta^2 f(x_0-h)[/math]
		[math]\delta f(x_0-\frac{1}{2}h)[/math]		[math]\delta^3 f(x_0-\frac{1}{2}h)[/math]
[math]x_0[/math]	[math]f(x_0)[/math])		[math]\delta^2 f(x_0)[/math]		[math]\delta^4 f(x_0)[/math]
		[math]\delta f(x_0+\frac{1}{2}h)[/math]		[math]\delta^3 f(x_0+\frac{1}{2}h)[/math]
[math]x_0+h[/math]	[math]f(x_0+h)[/math]		[math]\delta^2 f(x_0+h)[/math]
		[math]\delta f(x_0+\frac{3}{2}h)[/math]
[math]x_0+2h[/math]	[math]f(x_0+2h)[/math]

Rozdiely sa určujú pre celú tabuľku rovnako:

[math]\delta f(x_0-\frac{3}{2}h) = f(x_0-h) - f(x_0 - 2h)[/math]

Pre bod x0 je derivácia nasledovná:

[math]f'(x_0) = \frac{1}{h}\left(\frac{\delta f(x_0-\frac{1}{2}h)+\delta f(x_0+\frac{1}{2}h)}{2}-\frac{1}{6}\frac{\delta^3 f(x_0-\frac{1}{2}h) + \delta^3 f(x_0+\frac{1}{2}h)}{2}\right)[/math]

Príklad pre implementáciu tejto metódy v jazyku C je Numerické derivovanie (riešené príklady)

Zdroje

• https://en.wikipedia.org/wiki/Numerical_differentiation
• https://nptel.ac.in/content/storage2/courses/122104018/node117.html