Štartovacie metódy

Grafická metóda.
Pozorne nakreslený graf funkcie $y=f(x)$ nám pomôže separovať reálne korene rovnice $f(x)=0$, t.j. určiť intervaly, v ktorých korene ležia. Niekedy je výhodnejšie rovnicu $f(x)=0$ písať v tvare $f_1(x)=f_2(x)$. Potom korene určíme ako x-ové súradnice prienikov grafov funkcií $y=f_1(x)$ a $y=f_2(x)$. Grafická metóda nám tiež môže poskytnúť informáciu o tom, či daný reálny koreň rovnice v uvažovanom intervale vôbec existuje. Pre zložitejšie typy funkcií môžeme reálne korene lokalizovať tabelovaním funkcie $y=f(x)$.

Metóda bisekcie.
Nech je

• reálna funkcia $f$ spojitá na $I_0=\langle a_0,b_0\rangle$,
• $f(a_0). f(b_0) <0$ (funkčné hodnoty v koncových bodoch intervalu $I_0$ majú opačné znamienka).

Tieto predpoklady zaručujú, že existuje aspoň jedno číslo $\alpha \in I_0$ také, že $f(\alpha)=0$. Zostrojme postupnosť intervalov

$$I_0 \supset I_1\supset \dots \supset I_k , \hbox{ kde } I_k=\langle a_k,b_k\rangle$$

takto:
Ak je $f(a_{k-1}).f(b_{k-1}) <0\$, vypočítame stred intervalu $I_{k-1}$, t.j.

$$s_k=\frac{1}{2}(a_{k-1}+b_{k-1}).$$

V prípade, že $f(s_k)=0$ našli sme koreň rovnice. V opačnom prípade zvolíme za $I_k=\langle a_k,b_k\rangle$ ten z intervalov $\langle a_{k-1},s_k\rangle ,\ \langle s_k,b_{k-1}\rangle$, v ktorého koncových bodoch má funkcia $f$ opačné znamienka. Koreň $\alpha$ bude ležať v každom z intervalov $I_k$ a postupnosti $\{a_k\}, \{b_k\}$ koncových bodov týchto intervalov vždy konvergujú ku koreňu $\alpha$. Po $n$ krokoch bude mať interval dĺžku

$$b_n-a_n=\frac{1}{2}(b_{n-1}- a_{n-1}) =\frac{1}{2^2}( b_{n-2}-a_{n-2})= \dots =\frac{1}{2^n}(b_0-a_0).$$

Pre odhad chyby preto platí: ( $\alpha \in I_n$).

$$\vert a_n-\alpha\vert\leq \frac{b_0-a_0}{2^n} \hbox{ resp. } \vert b_n-\alpha\vert\leq \frac{b_0-a_0}{2^n}.$$

Metóda bisekcie (delenia intervalu) konverguje pomaly. Rýchlosť konvergencie tejto metódy je ale úplne nezávislá na tvare funkcie $f$.

Príklad 39. Nájdime aproximáciu koreňa rovnice

$$f(x) = \left(\frac{x}{2}\right)^2-\sin x =0.$$

Riešenie: Pre zastavovaciu podmienku zvolíme $\delta =0,05$. Z grafu funkcií $y=(\frac{x}{2})^2,\ y=\sin x$ odhadneme $I_0=\langle 1,5;2\rangle$. Skutočne $f(1,5).f(2) <0$. Podľa vzťahu, odvodeného pre odhad chyby, máme:

$$\vert a_4 -\alpha\vert <\frac{1}{2^4} . 0,5 <0,05.$$

Výsledky môžeme zapísať do tabuľky:

k	$a_k$	$b_k$	$s_{k+1}$	$f(s_{k+1})$	$b_k-a_k$
0	1,50000	2,00000	1,7500	$<0$	0,5
1	1,75000	2,00000	1,87500	$<0$	0,25
2	1,87500	2,00000	1,93750	$>0$	0,125
3	1,87500	1,93750	1,90625	$<0$	0,0625
4	1,90625	1,93750			0,03125

Výhoda tejto metódy okrem jej jednoduchosti je aj v tom, že môžeme dopredu určiť počet krokov, potrebných k dosiahnutiu požadovanej presnosti. Nevýhodou je pomalá konvergencia.

Metóda prostej iterácie.
Rovnicu $f(x)=0$ prepíšeme na tvar

$$\vspace{-0.4cm} x=\phi(x)$$ (7.6)

(obyčajne býva niekoľko možností).
Predpokladáme, že existuje interval $I_0=\langle a_0,b_0\rangle$ patriaci definičnému oboru a oboru spojitosti ako funkcie $f$, tak aj funkcie $\phi$ taký, ktorý obsahuje spoločný koreň $\alpha$ obidvoch vyššie uvedených rovníc a pre ktorý je splnená podmienka $\phi(I_0) \subset I_0$. Využijúc rovnicu (7.6), zostrojíme postupnosť aproximácií $x_1, x_2, \dots$, koreňa $\alpha$ podľa nasledujúceho návodu:

1. Zvolíme číslo $\delta >0$ a začiatočnú aproximáciu $x_0 \in I_0$.
2. Ďalšiu aproximáciu určíme z iteračnej formule
   

   $$x_k = \phi(x_{k-1}), \ \ k=1,2,3,\dots$$ (7.7)

   
   

3. Ak bude $\vert x_k-x_{k-1}\vert \geq \delta$, pokračujeme podľa bodu číslo 2, v opačnom prípade výpočet zastavíme a $x_k$ považujeme za aproximáciu koreňa $\alpha$.

Obrázok 7.6: Metóda prostej iterácie.

Pri realizácii tohoto algoritmu musíme mať zaručené, že postupnosť $\{x_k\}$, určená vzťahom (7.7), konverguje ku koreňu $\alpha$. K tomu nám slúži nasledujúca veta:

Veta 7.1 (Postačujúce podmienky konvergencie.)   Predpokladajme, že funkcia $\phi$ je na nejakom intervale $I=\langle a,b\rangle$ spojitá a má tieto vlastnosti:

$$\vspace{-0.5cm}\hbox{a) } \forall x \in I:\ \phi(x) \in I$$ (7.8)

$$\hbox{b) } \exists q \in \langle 0,1) \hbox{tak\' e, \v ze}: \forall x,y \in I \hbox{plat\' \i}: \vert\phi(x)-\phi(y)\vert \leq q \vert x-y\vert .$$

Potom v intervale $I$ existuje práve jeden reálny koreň $\alpha$ rovnice $x=\phi(x)$ a postupnosť $\{x_k\}$, určená formulou $x_k=\phi(x_{k-1})$ konverguje pre každé $x_0 \in I$ a platí $\lim_{k\rightarrow \infty} x_k =\alpha$.

Pre diferencovateľnú funkciu $\phi$ možno podmienku b) nahradiť podmienkou

$$\hbox{ b')}\ \ \ \ \exists q:\ \forall x \in I \hbox{ je } \vert\phi '(x)\vert\leq q <1 .$$

Príklad 40. Budeme hľadať opäť koreň rovnice $(\frac{x}{2})^2 - \sin x =0$ v intervale $I_0=\langle 1,5;2\rangle$. Uvedenú rovnicu prepíšeme na tvar
$x= 2 \sqrt{\sin x}$. Budeme počítať podľa iteračného vzorca

$$x_k= 2 \sqrt{ \sin x_{k-1} }$$

a výpočet zastavíme, ak bude $\vert x_k-x_{k-1}\vert <10^{-3} =\delta$. Ľahko sa presvedčíme, že interval $I_0=\langle 1,5;2\rangle$ patrí do definičného oboru funkcie $\phi(x)=2 \sqrt{\sin x}$. Zderivovaním iteračnej funkcie $\phi(x)=2 \sqrt{\sin x}$. zistíme, že derivácia je skutočne na intervale $I_0$ menšia ako $1$. Z počtu iterácií uvedených v tabuľke môžeme posúdiť rýchlosť konvergencie. Vidíme, že táto je závislá od voľby začiatočnej hodnoty $x_0$.

k	$x_k,\ x_0 = 1,5$	$x_k, \ x_0 = 2,0$
1	1,99749	1,90714
2	1,80823	1,94316
3	1,94279	1,93025
4	1,93039	1,93503
5	1,83498	1,93328
6	1,93330	1,93392
7	1,93392

Na základe vety o postačujúcej podmienke konvergenie metódy prostej iterácie môžeme získať odhad chyby tejto metódy:

$$\vert x_k -\alpha \vert \leq \frac{q}{1-q}\vert x_k - x_{k-1}\vert.$$

Ak máme výpočet zastaviť pri splnení podmienky $\vert x_k-x_{k-1}\vert \leq \delta,$ potom pre odhad chyby dostávame

$$\vert x_k -\alpha \vert \leq \frac{q}{1-q} \delta.$$

Ak je funkcia $\phi$ dostatočne hladká môžeme pomocou jej Taylorovho rozvoja získať nasledujúci odhad: Pre $\phi ^{'}(\alpha) \neq 0$ máme

$$x_k -\alpha = \phi^{'}(\alpha)(x_{k-1}-\alpha) +o((x_{k-1} -\alpha)).$$

(Pre symbol $o((x_{k-1} -\alpha))$ pozri (7.5)). Vidíme, že rád rýchlosti konvergencie je $r=1$. Hovoríme preto o lineárnom iteračnom procese. V prípade, že je $\phi^{'}(\alpha) =0$ a $\phi ^{''}(\alpha) \neq 0$, potom

$$x_k -\alpha = \frac{\phi^{''} (\alpha) }{2}(x_{k-1}-\alpha)^2 +o((x_{k-1} -\alpha)^2).$$

a rýchlosť konvergencie je v tomto prípade druhého rádu.

Metóda regula falsi
Opäť uvažujme rovnicu $f(x)=0$ a predpokladáme, že táto funkcia je spojitá na intervale $I=\langle a,b\rangle$ a opäť platí: $f(a).f(b) <0$ (t.j. v intervale $I$ existuje reálny koreň rovnice). Vypočítame x-ovú súradnicu prieniku x-ovej osi a sečnice krivky $y=f(x)$, zostrojenej v bodoch $A=[a,f(a)], B=[b,f(b)]$ podľa vzorca

$$s_1 = a-\frac{f(a)}{f(b)-f(a)} (b-a).$$ (7.9)

Ak bude platiť $sign f(s_1) =sign f(a)$ (sign znamená znamienko príslušného reálneho čísla), potom preznačíme $s_1$ na $a$ a počítame $s_2$ podľa rovnakého vzorca. Ak bude $sign f(s_1) =sign f(b)$, preznačíme $s_1$ na $b$ a ďalej počítame $s_2$ opäť podľa vzorca (7.9). Proces výpočtu zastavíme napríklad podmienkou $\vert f(s_k)\vert < \delta$.

Obrázok 7.7: Metóda regula falsi.

Metóda regula falsi je vždy konvergentnou metódou, t.j. zostrojená postupnosť bodov $s_k$ vždy konverguje ku koreňu $\alpha$, pokiaľ je jeho existencia zaručená. Dá sa ukázať, že rýchlosť konvergencie je rádu $r=1$. Metóda sa neodporúča používať veľmi blízko pri hľadanom koreni. Z vety o strednej hodnote dostávame pre odhad chyby:

$$\vert s_k-\alpha\vert \leq \frac{f(s_k)}{m}, \ \hbox{kde } m=\min_{x\in I} \vert f^{'}(x)\vert.$$

Príklad 41. Metódou regula falsi riešme opäť úlohu $(\frac{x}{2})^2 - \sin x =0$. Voľme $I_0=\langle 1,5;2\rangle$. Výpočet sme zastavili podmienkou $\vert f(s_k)\vert< 10^{-5}$. Výsledky sú uvedené v nasledujúcej tabuľke:

k	$s_k$	$a_k$	$b_{k}$	$f(s_{k})$	$f(a_k)$	$f(b_k)$
0	-	1,50000	2,00000	-	$<0$	$>0$
1	1,91373	1,91375	2,00000	$<0$	$<0$	$>0$
2	1,93305	1,93305	2,00000	$<0$	$<0$	$>0$
3	1,93373	1,93373	2,00000	$<0$	$<0$	$>0$
4	1,93375