Numerické riešenie nelineárnych rovníc

Matematická formulácia tohoto problému je nasledovná: Je daná spojitá funkcia $f: {\bf R}\rightarrow {\bf R}$, definovaná na intervale $\langle a,b\rangle$. Chceme nájsť reálne číslo $\alpha \in \langle a,b\rangle$ (pokiaľ existuje), pre ktoré platí

$$f(\alpha) =0.$$

Takéto číslo $\alpha$ nazývame koreň rovnice. Keďže funkcia $f$ môže byť v podstate ľubovoľná funkcia jednej reálnej premennej, jej koreň vo všeobecnosti nevieme nájsť nejakým matematickým výpočtom ako napríklad u lineárnej alebo kvadratickej funkcie, prípadne niektorej goniometrickej funkcie. Tento koreň preto budeme hľadať numerickými metódami. Spravidla sa nám nepodarí nájsť koreň, ale len jeho aproximáciu - približnú hodnotu. Musí nás preto zaujímať okrem metódy, ktorú na výpočet použijeme, aj chyba, akej sa pri nájdení tohoto približného riešenia dopustíme (podrobnejšie o numerických metódach a chybách pozri kapitolu Reálne čísla, paragrafy Zdroje chýb, Chyby aritmetických operácií ). Numerické metódy, ktorými sa budeme teraz zaoberať, sú založené na iteračných princípoch (pozri kapitolu Reálne čísla, paragraf Algoritmy). Budú nás zaujímať hlavne dve základné otázky:

1. Konverguje postupnosť vytvorená danou iteračnou metódou?
2. Ak konverguje, tak ako rýchlo?

Ak konverguje postupnosť vytvorená danou iteračnou metódou, hovoríme, že iteračná metóda konverguje.
Ak o koreni rovnice vieme len toľko, že leží v intervale $\langle a,b\rangle$ a nemáme žiadne iné informácie o jeho polohe, použijeme iteračnú metódu, ktorej konvergencia nezávisí od voľby začiatočnej aproximácie. Takéto metódy voláme vždy konvergentné metódy. Spravidla majú tú nevýhodu, že konvergujú pomaly, a preto sú zvyčajne vhodné pre určenie takej aproximácie koreňa, ktorá by mohla slúžiť ako začiatočná aproximácia pre nejakú rýchlo konvergentnú metódu, ktorá ale vyžaduje "dobrú" počiatočnú aproximáciu koreňa. Preto metódy riešenia nelineárnych rovníc rozdeľujeme na dva typy:

1. štartovacie metódy
2. spresňujúce metódy

Neznamená to však, že štartovacia metóda konverguje vždy pomaly a spresňujúca zas konverguje vždy rýchlo. Závisí to vždy od konkrétnej situácie a vlastností funkcie $f$.
V ďalšom budeme predpokladať, že funkcia $f$, ktorej koreň na intervale $\langle a,b\rangle$ hľadáme, je na tomto intervale spojitá. K tomu, aby sme mohli odpovedať na druhú otázku z dvoch vyššie položených, zavedieme najskôr nasledujúci pojem:
Hovoríme, že postupnosť $\{x_k\}$ konverguje k číslu $\alpha$ s rýchlosťou rádu r, ak pre $k\rightarrow \infty$ platí: Existuje taká konštanta $C>0$, že

$$\vert x_{k+1} -\alpha \vert =C \vert x_k - \alpha\vert^r + o(\vert x_k -\alpha\vert^r),$$

$$\hbox{symbol } f(x)=o(g(x)), \hbox{ pre} \ x \rightarrow a,... ...znamen\' a, \v ze} \lim_{x \rightarrow a}\frac{f(x)}{g(x)} =0$$ (7.5)