1. Nestabilní rekurze - ukážeme si na poněkud umělém
případu počítání mocnin čísla
zvaného "Zlatý řez"
Lehce ukážete, že mocniny
splňují jednoduchý rekursní vztah
Protože známe
a
mohli bychom zkusit
počítat mocniny odečítáním, což je obvykle rychlejší než násobení.
Obrázek ukazuje, že uvedený postup zcela nepoužitelný, při jednoduché
přesnosti dostaneme viditelné chyby výsledky už od n = 16,
kdy
.
Pro n = 20 dostanu poprvé záporný
výsledek rekurze, a tedy rekurze už nijak neaproximuje hodnotu mocniny.
Nejdříve vzroste relativní chyba (chyba mění znaménko), pak
se objeví záporné hodnoty
a nakonec začne dokonce růst absolutní
hodnoty
.
Nestabilita se projeví i ve dvojité přesnosti,
zaokrouhlovací chyba narůstá ale z menší hodnoty a tak by se 1. záporný
výsledek rekurze objevil pro n=40.
Příčina nestability je v tom, že uvedená rekursní formule má
ještě druhé řešení
.
Protože rekurzivní
relace je lineární, absolutní velikost
zaokrouhlovací chyby bude narůstat geometrickou řadou
s kvocientem
.
Protože navíc řešení klesá,
relativní velikost zaokrouhlovací chyby roste geometrickou řadou
s kvocientem
.
Stejná rekurze by ale mohla být použita pro
výpočet mocnin čísla
. Pro tento výpočet je metoda stabilní a pracovala
by uspokojivě.
Uvedený příklad byl umělý, nicméně u mnoha speciálních funkcí
(např. Besselovy funkce) se k výpočtu hodnoty funkcí různých řadů
používají podobné rekurzivní relace, vždy ovšem tak, aby
metoda byla stabilní.
2. Nestabilní metoda
pro výpočet obyčejných diferenciálních rovnic
Nechť řešíme obyčejnou diferenciální rovnici 1. řádu
y' = f(x,y)
Na příkladu rovnice y'= - y s počáteční podmínkou y(0) = 1 řešené ve směru růstu proměnné x ukážeme,
že dvoukroková metoda 2. řádu
je nestabilní.
Jde vlastně o podobnou rekurzi jako výše a pro poměr q = y(x+h)/y(x)
existují 2 řešení,
je v absolutní hodnotě menší
než 1 a odpovídá prvním třem členům Taylorova rozvoje řešení
,
druhý kořen
je v absolutní hodnotě větší než 1 způsobuje nestabilitu algoritmu.
Na následujícím grafu je porovnána celková relativní chyba
uvedené nestabilní metody s chybou Eulerovy metody
Eulerova metoda se obvykle nepoužívá, neboť jde o metodu 1. řádu
s velkou chybou metody, nicméně je pro uvedený případ stabilní.
Obrázek ukazuje, že na začátku řešení je nestabilní metoda vzhledem
k relativně malé chybě metody přesnější, ale postupný růst
chyby přivede nakonec ke katastrofálním chybám. Katastrofálním chybám
nelze zabránit zkracováním kroku, užití dvojité přesnosti katastrofu
pouze oddálí. U stabilní metody roste chyba s délkou intervalu
nejvýše lineárně a chybu lze zmenšit zkracováním kroku.
3. Nestabilní spline
Při interpolaci dat pomocí kubického splinu (lokální interpolace
kubickým polynomem se spojitou derivací) je třeba zadat 2 podmínky
(např. hodnotu derivace funkce) v obou krajních bodech. Nesprávnou a
nestabilní metodu dostaneme, pokud obě podmínky zadáme v 1
z okrajových bodů. Pokud jako 2. podmínku v prvním okrajovém bodu zadáme
např. jako 2. derivaci rovnou hodnotě druhé derivace, která vyšla
při stabilním postupu, tj. zadaných 1. derivacích v obou okrajových bodech,
obě úlohy jsou z matematického hlediska zcela ekvivalentní a v případě
počítání s přesnými čísly bych dostal totožný výsledek.
Pokud však numericky počítám s konečnou délkou čísel, zaokrouhlovací chyba
však při postupném počítání od 1 okraje narůstá a řešení začne mezi
zadanými body silně oscilovat.
Na grafu jsou ukázány oscilace chybně počítaného (nestabilního) kubického
splinu. Je vidět jen několik prvních extrémů, další jsou v absolutní hodnotě příliš velké
(až 1013). Při počítání v dvojité přesnosti se viditelné oscilace
objeví pro x > 4.