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:

\begin{displaymath}
f(x)= f(x_0) + f^{'}(x_0) (x-x_0) +\frac{1}{2} f^{''}
(\xi _0)(x-x_0)^2,
\end{displaymath} (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) ):
\begin{displaymath}
f(x_0)+f^{'}(x_0)(x-x_0) =0
\end{displaymath} (7.11)

a vypočítame jej koreň (označíme ho $x_1$):
\begin{displaymath}
x_1= x_0 -\frac{f(x_0)}{f^{'}(x_0)}\ \ \hbox{pre } f^{'}(x_0)\neq 0.
\end{displaymath} (7.12)

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

\begin{displaymath}f(x_1) +f^{'}(x_1)(x-x_1)=0, \end{displaymath}

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

\begin{displaymath}x_2 = x_1 -\frac{f(x_1)}{f^{'}(x_1)}.\end{displaymath}

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

\begin{displaymath}f(x_k) +f^{'}(x_k) (x-x_k) =0 \end{displaymath}

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):
\begin{displaymath}
\vspace{-0.5cm}
x_{k+1} =x_k+h_k, \ \ \ h_k = -\frac{f(x_k)}{f^{'}(x_k)}.
\end{displaymath} (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

\begin{displaymath}\phi(x) = x-\frac{f(x)}{f^{'}(x)}.\end{displaymath}

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

\begin{displaymath}\vert \frac{f(a)}{f^{'}(a)} \vert < b-a, \ \
\vert \frac{f(b)}{f^{'}(b)} \vert < b-a, \end{displaymath}

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:

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

( 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:

\begin{displaymath}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})}\end{displaymath}

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.