Spresňujúce metódy

Efektívne algoritmy na riešenie nelineárnych rovníc majú obvykle dve časti. V prvej časti použijeme niektorú štartovaciu metódu a v druhej časti sa prejde k nejakej rýchlejšie konvergujúcej metóde, ktorá slúži ku spresneniu počítanej aproximácie koreňa.

Newtonova metóda
Nech daný jednoduchý reálny koreň $\alpha$ leží v intervale $I$. Zvolíme $x_0 \in I$ a pomocou Taylorovho rozvoja vyjadríme funkciu f v tvare:

$$f(x)= f(x_0) + f^{'}(x_0) (x-x_0) +\frac{1}{2} f^{''} (\xi _0)(x-x_0)^2,$$ (7.10)

kde $\xi _0$ leží medzi $x$ a $x_0$, pričom predpokladáme, že v intervale $I$ existujú derivácie $f^{'}, f^{''}$. Rovnicu $f(x)=0$ teraz nahradíme (aproximujeme) lineárnou rovnicou (prvé dva členy rozvoja (7.10) ):

$$f(x_0)+f^{'}(x_0)(x-x_0) =0$$ (7.11)

a vypočítame jej koreň (označíme ho $x_1$):

$$x_1= x_0 -\frac{f(x_0)}{f^{'}(x_0)}\ \ \hbox{pre } f^{'}(x_0)\neq 0.$$ (7.12)

Teraz nahradíme rovnicu $f(x)=0$ rovnicou

$$f(x_1) +f^{'}(x_1)(x-x_1)=0,$$

ktorá tiež vychádza z Taylorovho rozvoja funkcie $f$, ale v bode $x_1$. Koreňom tejto lineárnej rovnice je číslo:

$$x_2 = x_1 -\frac{f(x_1)}{f^{'}(x_1)}.$$

Opakované nahradenie rovnice $f(x)=0$ lineárnymi rovnicami typu

$$f(x_k) +f^{'}(x_k) (x-x_k) =0$$

je základnou myšlienkou Newtonovej metódy, ktorej sa z tohoto dôvodu často hovorí aj metóda linearizácie. Korene týchto lineárnych rovníc tvoria postupnosť, ktorá je určená nasledujúcou rekurentnou formulou (Newtonova iteračná formula):

$$\vspace{-0.5cm} x_{k+1} =x_k+h_k, \ \ \ h_k = -\frac{f(x_k)}{f^{'}(x_k)}.$$ (7.13)

Pre spojitú funkciu $f$ musí byť hľadaný koreň $\alpha$ limitou postupnosti $\{x_k\}$. Iteračný proces zastavujeme podmienkou $\vert h_k\vert <\delta$, kde požadovanú presnosť $\delta$ zadávame spolu so vstupnými údajmi.
Poznámka 1. V geometrickej interpretácii vzorca (7.13) je bod $[x_{k+1},0]$ prienikom dotyčnice zostrojenej v bode $[x_k,f(x_k)]$ ku krivke $y=f(x)$ a x-ovej osi. Preto Newtonovej metóde hovoríme aj metóda dotyčníc.
Poznámka 2. Algoritmus Newtonovej metódy odpovedá algortimu metódy prostej iterácie pre funkciu

$$\phi(x) = x-\frac{f(x)}{f^{'}(x)}.$$

Príklad 42. Nájdime aproximáciu koreňa $\alpha \in\langle 1,5;2\rangle$ rovnice $f(x) \equiv (\frac{x}{2})^2 -\sin x = 0$ Newtonovou metódou. Výpočet zastavíme, ak bude $\vert h_k\vert = \vert x_{k+1}-x_k\vert < 10^{-5}$. Zvolíme $x_0 =1,5$. Výsledky sú uvedené v tabuľke:

k	$x_k$	$f(x_k)$	$f^{'}(x_k)$	$h_k$
0	1,50000	-0,434995	0,679263	6,403930 $\cdot 10^{-1}$
1	2,14039	0,303197	1,60948	-1,88381 $\cdot 10^{-1}$
2	1,95201	2,43719 $\cdot 10^{-2}$	1,34805	1,82563 $\cdot 10^{-2}$
3	1,93393	2,32991 $\cdot 10^{-4}$	1,32217	-1,76218 $\cdot 10^{-4}$
4	1,93375	-4,97570 $\cdot 10^{-6}$	1,32191	3.76402 $\cdot 10^{-6}$

Vyšetrovanie podmienok konvergencie Newtonovej metódy je pomerne zložité, a preto ho nebudeme uvádzať. Povieme si len, že táto metóda konverguje veľmi rýchlo, ak sme dostatočne blízko koreňa. V praxi sa často používa ľahko overiteľné kritérium konvergencie: Ak je $f^{'}(x) \neq 0, \ f^{''}$ nemení znamienko na intervale $I$, platí $f(a) \cdot f(b) <0$ a súčasne

$$\vert \frac{f(a)}{f^{'}(a)} \vert < b-a, \ \ \vert \frac{f(b)}{f^{'}(b)} \vert < b-a,$$

potom Newtonova metóda konverguje pre ľubovoľné $x_0 \in I$. Dá sa ukázať, že Newtonova metóda má rád rýchlosti konvergencie $r=2$.

Metóda sečníc
Predpokladajme, že $x_k \neq x_{k-1}$ sú "dobré" aproximácie jednoduchého koreňa $\alpha$ rovnice $f(x)=0$. Funkciu $f$ nahradíme lineárnou funkciou g:

$$g(x) =\frac{f(x_k) -f(x_{k-1})}{x_k-x_{k-1}} (x-x_k) + f(x_k)$$

( g je priamka, prechádzajúca bodmi $[x_{k-1},f(x_{k-1})], \ [x_k,f(x_k)]$) a namiesto rovnice $f(x)=0$ riešime rovnicu $g(x)=0$. Koreň $x_{k+1}$ tejto lineárnej rovnice je teda určený vzorcom:

$$x_{k+1} = x_{k} +\tau_k, \hbox{ kde } \ \tau_k = -f(x_k) \frac{x_k-x_{k-1}}{f(x_k) - f(x_{k-1})}$$

a považujeme ho za aproximáciu koreňa $\alpha$ rovnice $f(x)=0$. Dostali sme tak dvojkrokovú iteračnú formulu t.j. k zahájeniu jej výpočtu potrebujeme dve začiatočné aproximácie $x_0, x_1$. Oproti Newtonovej metóde má výhodu, že v každom kroku počítame len jednu novú funkčnú hodnotu a stačí, aby daná funkcia $f$ bola len spojitá, nemusí byť diferencovateľná.
Poznámka. V geometrickej interpretácii je graf funkcie $g$ sečnicou grafu funkcie $f$ a odtiaľ pochádza názov tejto metódy.
Dá sa ukázať, že rýchlosť konvergencie metódy sečníc je rádu $r= \frac{1}{2}(1+\sqrt 5) \approx 1,618.$ Pokiaľ začiatočné aproximácie $x_0, x_1$ nebudú "dobré", metóda sečníc nemusí vôbec konvergovať. Je preto nutné kombinovať ju s niektorou zo štartovacích metód.