Kapitola 2
Řešení nelineárních rovnic. Urychlování konvergence. Hledání kořenů
Řešení nelineárních rovnic pomocí iterací
Metodu, kterou se zde budeme zabývat, lze také najít pod názvem metoda postupných aproximací.
Rovnici typu \(x = f(x)\), kde \(f(x)\) je obecně nelineární funkce, či dokonce operátor, lze velmi často řešit pomocí metody prostých iterací. Zvolíme počáteční odhad \(x = x_0\) a iterujeme pomocí \begin{equation} x_{n+1} = f(x_n) . \label{eq:02:proste_iterace} \end{equation} Zda pro \(n \to \infty\) konvergujeme, tj. \(x_n \to x_P\), kde \(x_P\) řeší \(x_P = f(x_P)\), závisí obecně jak na problému (funkci \(f\)), tak na volbě \(x_0\).
Nechť \(f\) je spojité zobrazení definované na oblasti \(D\) a nechť \(f\) zobrazuje \(D\) na sebe, tj. \(f(D) \subset D\), a splňuje lipschitzovskou podmínku kontrahujícího zobrazení, tj. \(\exists L < 1\) takové, že pro \(\forall x_1, x_2 \in D\) platí (ve vhodné normě) \begin{equation} \|f(x_1) - f(x_2)\| \le L \, \|x_1 - x_2\| . \label{eq:02:lipschitz} \end{equation} Pak
- \(f(x)\) má na \(D\) právě jeden pevný bod \(x_P = f(x_P)\),
- posloupnost \(x_n = f(x_{n-1})\) konverguje k \(x_P\) pro libovolné počáteční \(x_0 \in D\), tj. \(\lim\limits_{n \to \infty} \|x_n - x_P\| = 0\),
- pro odhad chyby v \(n\)-té iteraci platí \begin{equation} \|x_n - x_P\| \le \frac{L^n}{1-L} \, \|x_1 - x_0\| . \label{eq:02:odhad_chyby} \end{equation}
Viz např. J. Segethová: Základy numerické matematiky.
□Pro \(F \in C^1\langle a,b \rangle\) tedy metoda konverguje, pokud \(|f'(x)| < 1\) pro \(\forall x \in \langle a,b \rangle\).
Pavučinový diagram iterace \(x_{n+1} = f(x_n)\): modrá je graf \(f\), šedá čárkovaná je osa prvního a třetího kvadrantu \(y = x\), zeleným kroužkem je vyznačen pevný bod. Táhněte bodem \(x_0\) po vodorovné ose a posuvníkem měňte počet iterací; panel dopočítává \(x_P\), směrnici \(q = f'(x_P)\) i skutečnou chybu \(e_n\). Přepnutím na \(f(x) = x^2 - 0{,}3\) uvidíte, co se stane, když podmínka \(|f'| < 1\) neplatí.
Pro rovnici \(x = \cos x\) dostáváme dokonce řešení pro libovolné \(x_0\), tj. vždy konvergujeme k \(x_P \doteq 0{,}739\ldots\) Otázkou zůstává, jak rychle.
Rychlost konvergence a řád iterační metody
Rychlost konvergence (speed of convergence) je dána tzv. řádem iterační metody (order of convergence). Označíme-li chybu v \(n\)-tém kroku \(e_n = x_n - x_P\), pak pro diferencovatelnou funkci \(f\) dostáváme
\begin{align*} e_{n+1} &= x_{n+1} - x_P = f(x_n) - f(x_P) = f(x_P + e_n) - f(x_P) = \\ &= f'(x_P)\, e_n + \frac{1}{2} f''(x_P)\, e_n^2 + \dots \qquad \text{pro malé } e_n . \end{align*}V závislosti na tom, kolik derivací je nulových v bodě \(x_P\), dostáváme metody různých řádů. Pro lineární metody bude \(f'(x_P) \neq 0\), a tedy \(e_{n+1} \approx q\, e_n\), kde \(q = f'(x_P)\). Počet správných cifer tedy roste lineárně s počtem kroků, neboť \(e_n \sim e_0 q^n\), a proto
\begin{equation} \underbrace{\log|e_n| - \log|e|_{n+1}}_{\text{počet platných cifer získaných v jedné iteraci}} = \big[n - (n+1)\big] \log|q| = -\log|q| . \label{eq:02:cifry_linearni} \end{equation}Pro kvadratické metody bude \(f'(x_P) = 0\) a \(f''(x_P) \neq 0\), a tedy \[ e_{n+1} \approx \tfrac{1}{2} f''(x_P)\, e_n^2 . \] Nyní \begin{equation} \log|e_{n+1}| = \log|q| + 2\log|e_n| , \label{eq:02:cifry_kvadraticke} \end{equation} a počet platných cifer se v každé iteraci minimálně zdvojnásobí. Podobně je tomu i pro metody vyšších řádů.
Řád metody je nenulové \(\alpha\), pro nějž existuje konečná, nenulová limita \begin{equation} \lim_{n \to \infty} \frac{|x_{n+1} - x_P|}{|x_n - x_P|^\alpha} = C < \infty \qquad \left( = \lim_{n \to \infty} \frac{|e_{n+1}|}{|e_n|^\alpha} \right) . \label{eq:02:rad_metody} \end{equation} Říkáme též, že iterační metoda má řád konvergence \(\alpha\) v bodě \(x_P\).
- \(C\) samozřejmě závisí na \(f(x)\).
- \(\alpha\) je jednoznačně určeno díky \(c \neq 0\) a \(\alpha \geq 1\).
Existují i obecnější metody, například vícekrokové \[ F_n(x_n, x_{n-1}, \dots, x_{n-s+1}) = x_{n+1} , \] a pokud \(F_n = F\), jde o stacionární metodu. Existují také vždy konvergentní metody fungující pro libovolné \(f(x)\) a \(x_0\); ty jsou ovšem typicky pomalejší a používají se jako startovací.
Hledání řešení rovnice \(x = \cos x\) prostou iterací je lineární metoda (\(\alpha = 1\)), neboť \(\frac{\mathrm{d}}{\mathrm{d}x} \cos x \big|_{x = x_P} \neq 0\). Přesněji \[ \left. \frac{\mathrm{d}\cos x}{\mathrm{d}x} \right|_{x = x_P} = -\sin x_P \doteq -0{,}6736\ldots \approx -\frac{2}{3} , \] a tedy \(e_{n+1} \approx -\frac{2}{3} e_n\), z čehož vidíme, že zhruba po šesti iteracích se zmenší chyba o jeden řád, neboť \(\left(\frac{2}{3}\right)^6 \sim \frac{1}{10}\).
Urychlování konvergence lineárních metod
Aitkenova \(\Delta^2\) metoda
Pro lineární metody lze pro dostatečně velké \(n\) psát chybu jako \(e_n \simeq cq^n\), a pro tři po sobě jdoucí aproximace tak máme (alespoň přibližně)
\begin{align*} x_n - x_P &\simeq cq^n , \\ x_{n+1} - x_P &\simeq cq^{n+1} , \\ x_{n+2} - x_P &\simeq cq^{n+2} , \end{align*}což jsou tři rovnice pro tři neznámé \(x_P\), \(c\) a \(q\). Vyjádříme \begin{equation} q = \frac{x_{n+1} - x_P}{x_n - x_P} = \frac{x_{n+2} - x_P}{x_{n+1} - x_P} , \label{eq:02:aitken_q} \end{equation} z čehož \begin{equation} x_P \simeq \frac{x_n x_{n+2} - x_{n+1}^2}{x_n - 2x_{n+1} + x_{n+2}} = x_n - \frac{(x_{n+1} - x_n)^2}{x_{n+2} - 2x_{n+1} + x_n} . \label{eq:02:aitken_xp} \end{equation} Druhý tvar je lepší z hlediska zaokrouhlovacích chyb, neboť \(x_n x_{n+2}\) a \(x_{n+1}^2\) mohou být blízká čísla.
Neboli \begin{equation} x_P \approx x_n' = x_n - \frac{(\Delta x_n)^2}{\Delta^2 x_n} \quad , \text{kde } \Delta \text{ je operátor dopředné diference} , \label{eq:02:aitken_delta} \end{equation} přičemž právě od \(\Delta^2 x_n\) ve jmenovateli pochází název metody.
Pozor, výsledek je opět jen přibližný, takže dostáváme novou posloupnost \(x_n'\), pro kterou lze ukázat, že \begin{equation} \lim_{n \to \infty} \frac{x_n' - x_P}{x_n - x_P} = 0 , \label{eq:02:aitken_limita} \end{equation} a tedy konverguje k \(x_P\) rychleji než \(x_n\). Obecně však jde opět o lineární metodu, ovšem s \(q' < q\).
Později se setkáme s podobnou „extrapolací“ ze známého chování chyby u numerické derivace a integrace.
Archimedův výpočet čísla \(\pi\)
Číslo \(\pi\) postupně aproximujeme obvodem mnohoúhelníku vepsaného do kružnice.
Do kružnice o poloměru 1 se středem \(O\) je vepsaný \(2^k\)-úhelník, který posuvníkem zjemňujete; zvýrazněné jsou tětivy \(z_1\) (průměr), \(z_2\) a \(z_3\). Panel počítá tětivu \(z_k\) obojí rekurencí — naivní i stabilní, obě jsou odvozeny níže — takže je přímo vidět, jak se naivní varianta kolem \(k \approx 15\) rozpadne odčítáním blízkých čísel, zatímco stabilní drží chybu na úrovni \(10^{-15}\).
\begin{align*} 2\pi &\doteq 2z_1 &&\Rightarrow& \pi &\doteq 2 \\ 2\pi &\doteq 4z_2 &&\Rightarrow& \pi &\doteq 2\sqrt{2} \\ 2\pi &\doteq 8z_3 &&\Rightarrow& \pi &\doteq 4\sqrt{2-\sqrt{2}} \end{align*}a tak dále.
Obecně dostaneme rekurentní vztah pro \(z_k\). Nejprve \begin{equation} x = 1 - \sqrt{1 - \left(\frac{z_k}{2}\right)^2} , \label{eq:02:archimedes_x} \end{equation}
Výsek kružnice se dvěma poloměry délky 1, tětivou \(z_k\), poloviční tětivou \(z_{k+1}\) a kolmou úsečkou \(x\) mezi tětivou a obloukem. Táhněte krajním bodem oblouku nebo posuvníkem měňte středový úhel; panel průběžně počítá \(z_k\), \(x\) i \(z_{k+1}\) z rekurence a porovná je s přesnou hodnotou \(2\sin(\theta/4)\).
a tedy
\begin{align*} z_{k+1} &= \sqrt{x^2 + \left(\frac{z_k}{2}\right)^2} = \\ &= \sqrt{1 - 2\sqrt{1-\left(\frac{z_k}{2}\right)^2} + \left(1 - \left(\frac{z_k}{2}\right)^2\right) + \left(\frac{z_k}{2}\right)^2} , \end{align*}takže \begin{equation} z_{k+1} = \sqrt{2}\,\sqrt{1 - \sqrt{1-\left(\frac{z_k}{2}\right)^2}} . \label{eq:02:archimedes_rekurence} \end{equation}
Protože \(2\pi \doteq 2^k z_k = 2 y_k\), bude \begin{equation} \pi \doteq y_{k+1} = 2^k z_{k+1} = \frac{2^{k+1}}{\sqrt{2}} \sqrt{1 - \sqrt{1 - \left(\frac{y_k}{2^k}\right)^2}} . \label{eq:02:archimedes_yk} \end{equation} Zde je ovšem problém s odčítáním dvou blízkých čísel, neboť \(\frac{y_k}{2^k} \to 0\) pro velká \(k\).
Proto výraz vynásobíme zlomkem \(\dfrac{\sqrt{1+\sqrt{\dots}}}{\sqrt{1+\sqrt{\dots}}}\) a dostaneme
\begin{equation} \tilde{y}_{k+1} = \frac{2^{k+1}}{\sqrt{2}} \cdot \frac{\sqrt{1 - \left(1 - \left(\frac{\tilde{y}_k}{2^k}\right)^2\right)}}{\sqrt{1 + \sqrt{1 - \left(\frac{\tilde{y}_k}{2}\right)^2}}} = \tilde{y}_k \sqrt{\frac{2}{1 + \sqrt{1 - \left(\frac{\tilde{y}_k}{2^k}\right)^2}}} , \label{eq:02:archimedes_stabilni} \end{equation}což je stabilní výpočet s chybou zhruba \(10^{-14}\) po \(25\) iteracích.
Aitkenova–Steffensenova metoda
Použijeme-li opakovaně Aitkenovu \(\Delta^2\) metodu, dostaneme posloupnosti \[ x_n \to x_n' \to x_n'' \to \dots \]
Opakované použití Aitkenovy metody: z řady \(x_0,\dots,x_4\) vzniknou šipkami body \(x_0',x_1',x_2'\), z nich \(x_0''\) a tak dále — vše počítané ze skutečné iterace \(x_{n+1}=f(x_n)\). Pod každým bodem je jeho hodnota a skutečná chyba, takže je vidět zrychlení o několik řádů na každé úrovni. Fialová řada navíc ukazuje Steffensenovu variantu, kde se \(\Delta^2\) aplikuje vždy znovu z nového bodu.
Alternativně lze uvažovat posloupnosti \(x_0^{(k)}\), \(x_1^{(k)}\) a \(x_2^{(k)}\), které získáme následovně (nyní se mění horní index):
- na začátku položíme \(x_0^{(0)} = x_0\), \(x_1^{(0)} = x_1 = f(x_0)\), \(x_2^{(0)} = x_2 = f(x_1)\);
- pro \(k = 0,1,2,\dots\) spočteme vždy \(x_0^{(k)}\) z Aitkenovy \(\Delta^2\) metody, tj. \begin{equation} x_0^{(k+1)} = x_0^{(k)} - \frac{\left(x_1^{(k)} - x_0^{(k)}\right)^2}{x_2^{(k)} - 2x_1^{(k)} + x_0^{(k)}} , \label{eq:02:steffensen_krok} \end{equation} ovšem \(x_1^{(k)} = f\!\left(x_0^{(k)}\right)\) a \(x_2^{(k)} = f\!\left(x_1^{(k)}\right)\).
Souhrnně lze psát jedinou posloupnost \(x_0^{(k)}\) danou vztahem \begin{equation} x_0^{(k+1)} = x_0^{(k)} - \frac{\left[f\!\left(x_0^{(k)}\right) - x_0^{(k)}\right]^2}{f\!\left(f\!\left(x_0^{(k)}\right)\right) - 2f\!\left(x_0^{(k)}\right) + x_0^{(k)}} , \label{eq:02:steffensen} \end{equation} o které si ukažme, že konverguje kvadraticky k \(x_p\).
Nyní totiž neiterujeme \(f\), ale novou funkci \begin{equation} \tilde{f}(x) = x - \frac{[f(x) - x]^2}{f(f(x)) - 2f(x) + x} . \label{eq:02:steffensen_ftilde} \end{equation} Označme \(q = f'(x_p)\), pak
\begin{align*} f(x_p + \varepsilon) &= x_p + \varepsilon q + \mathcal{O}(\varepsilon^2) , \\ f(f(x_p + \varepsilon)) &= x_p + \varepsilon q^2 + \mathcal{O}(\varepsilon^2) , \end{align*}a dostaneme
\begin{align*} \tilde{f}(x_p + \varepsilon) &= x_p + \varepsilon - \frac{\left(x_p + \varepsilon q - x_p - \varepsilon\right)^2}{x_p + \varepsilon q^2 - 2x_p - 2\varepsilon q + x_p + \varepsilon} + \mathcal{O}(\varepsilon^2) \\ &= x_p + \varepsilon - \varepsilon\,\frac{(q-1)^2}{(q-1)^2} + \mathcal{O}(\varepsilon^2) \;=\; x_p + \mathcal{O}(\varepsilon^2) . \end{align*}Neboli \(\tilde{f}(x_p) = x_p\), jde tedy o pevný bod \(\tilde{f}\), a zároveň \(\tilde{f}'(x_p) = 0\), což znamená kvadratickou konvergenci.
Hledání kořenů algebraické rovnice \(g(x) = 0\)
Vždy konvergentní metody
Uvažujme reálné funkce na intervalu \(\langle a,b \rangle\). Základním předpokladem je, že \(g(x)\) je spojitá na \(\langle a,b \rangle\) a \(g(a)\,g(b) < 0\), aby zde měla kořen. Standardní „klasické“ metody jsou následující.
a) Metoda bisekce (půlení intervalu)
Konstruujeme dvě posloupnosti \(a_n\) a \(b_n\):
\begin{align*} &a_0 = a, \quad b_0 = b , \\ &\text{pro } n = 0,1,2 \dots \qquad x_n = \frac{a_n + b_n}{2} , \\ &\text{je-li } g(a_n)\, g(x_n) \leq 0 : \; b_{n+1} = x_n, \; a_{n+1} = a_n , \\ &\text{jinak } b_{n+1} = b_n, \; a_{n+1} = x_n , \end{align*}a to dokud \(|g(x_n)| \ngeq \varepsilon\).
Rostoucí funkce protínající osu; dělicí body jsou vyznačené čárkami a svislou spojnicí od osy ke křivce. Táhněte krajními body \(a\) a \(b\) a přidávejte kroky: zelený pás je aktuální interval \(\langle a_n,b_n\rangle\), šedé čárky jsou všechny dosavadní středy \(x_n\). Panel ukazuje \(|g(x_n)|\) i šířku intervalu, která se každým krokem přesně půlí. Zkuste i interval, kde \(g(a)\,g(b) > 0\).
b) Metoda regula falsi (metoda sečen)
Opět konstruujeme \(a_n\) a \(b_n\) s \(a_0 = a\), \(b_0 = b\), ale nyní proložíme přímku: \begin{equation} \text{pro } n = 0,1, \dots \qquad x_n = \frac{a_n\, g(b_n) - b_n\, g(a_n)}{g(b_n) - g(a_n)} . \label{eq:02:regula_falsi} \end{equation} Podmínky pro výběr nového intervalu jsou stejné jako u bisekce.
Rostoucí konvexní křivka s vepsanými sečnami a svislými úsečkami od osy ke křivce. Sečny se počítají z výše uvedeného vzorce pro \(x_n\); poslední je zvýrazněná, starší jsou čárkované. Táhněte \(a\) a \(b\) a sledujte, jak u konvexní funkce jeden krajní bod „zamrzne“ a šířka intervalu přestane klesat, přestože \(x_n\) ke kořeni konverguje.
c) Modifikovaná metoda regula falsi
Uvedeme ji pouze obrázkově, viz interaktivní ukázky před modifikací a po modifikaci.
Klasická regula falsi: z pravého krajního bodu nad osou vychází celý svazek sečen do postupných bodů na křivce vlevo dole. Posuvník přidává kroky, takže svazek roste; panel navíc spočítá, kolik kroků klasická metoda potřebuje na chybu \(10^{-10}\).
Modifikovaná varianta: zůstane-li tentýž krajní bod dvakrát po sobě, jeho funkční hodnota se půlí, tedy \(f(b) \to \tfrac{1}{2}f(b)\). Sečny se sklánějí, body \(a_0, a_1, a_2\) a \(b_2\) se ke kořeni blíží rychleji; šipky u svislých úseček naznačují postup. Zaškrtnutím lze překrýt šedou klasickou variantu a v panelu porovnat počty kroků obou metod.
Podrobnosti o konvergenci a detaily algoritmů viz J. Segethová: Základy numerické matematiky, kap. 6.3.
Iterační metody vyššího řádu
Pišme \begin{equation} x = f(x) = x - \phi(x)\, g(x) , \label{eq:02:vyssi_rad_tvar} \end{equation} kde \(\phi(x)\) je vhodná funkce. Je-li \(x_p\) kořen, tj. \(g(x_p) = 0\), pak je též pevným bodem funkce \(f(x)\), a to za předpokladu, že jde o kontrahující zobrazení.
Funkce \(\phi(x)\) nesmí mít kořen na intervalu, kde hledáme \(x_p\), a navíc musí platit \(0 < |\phi(x)| < \infty\), tedy musí být omezená.
Jinou možností je například \(f(x) = x - F(g(x))\), kde \begin{equation} F(0) = 0, \quad F(y) \neq 0 \text{ pro } y \neq 0 . \label{eq:02:podminka_F} \end{equation}
a) Newtonova metoda (metoda tečen)
Pokud má být \(x = f(x) = x - \phi(x)\, g(x)\) metodou 2. řádu, musí být \begin{equation} f'(x_p) = 0 = 1 - \phi'(x_p)\,\underbrace{g(x_p)}_{\substack{\| \\ 0}} - \phi(x_p)\, g'(x_p) , \label{eq:02:newton_podminka} \end{equation} neboť \(x_p\) je kořen rovnice \(g(x) = 0\).
Metoda tečen: z bodu \(x_n\) vede svislice ke křivce a tečna v tomto bodě protne osu v \(x_{n+1}\). Táhněte startovním bodem \(x_0\) po ose a přidávejte kroky; panel ukazuje chybu i počet platných cifer, který se v každém kroku zhruba zdvojnásobí. Volba \(g(x) = \mathrm{arctg}\,x\) s \(x_0 \gtrsim 1{,}4\) ukazuje, že metoda nekonverguje vždy.
Z toho plyne \(\phi(x_p) = \dfrac{1}{g'(x_p)}\), neboli zvolíme \(\phi(x) = \dfrac{1}{g'(x)}\), což dává \begin{equation} x_{n+1} = x_n - \frac{g(x_n)}{g'(x_n)} . \label{eq:02:newton} \end{equation} A protože \[ f'(x_p) = \frac{g(x_p)\, g''(x_p)}{[g'(x_p)]^2} = 0 , \] vyžadujeme \(g'(x_p) \neq 0\) a existenci \(g''(x_p)\).
Newtonova metoda nekonverguje vždy, ale pokud je na určitém intervalu \(|f'(x)| < 1\), pak ano. Často funguje, pokud \(g''(x)\) kolem kořene \(x_p\) nemění znaménko. Je nutný „nástřel“ pomocí nějaké vždy konvergentní metody a pak lze rychle doiterovat Newtonovou metodou.
Speciálně pro \(g(x) = x^2 - C = 0\), kdy hledáme \(\sqrt{C}\), dostaneme \begin{equation} x_{n+1} = x_n - \frac{x_n^2 - C}{2x_n} = \frac{1}{2}\left(x_n + \frac{C}{x_n}\right) . \label{eq:02:newton_odmocnina} \end{equation}
b) Dvoubodová metoda sečen
Neznáme-li derivaci \(g'(x)\), nebo je-li obtížné ji spočítat, lze ji aproximovat, například \[ g'(x_k) = \frac{g(x_k) - g(x_{k-1})}{x_k - x_{k-1}} , \] a tedy \begin{equation} x_{n+1} = \frac{x_{n-1}\, g(x_n) - x_n\, g(x_{n-1})}{g(x_n) - g(x_{n-1})} . \label{eq:02:secny} \end{equation}
Lze ukázat (viz např. Isaacson, Keller: Analysis of Numerical Methods), že pro \(g(x)\) splňující \(g'(x) \neq 0\) na intervalu, kde hledáme kořen, a pro \(g''(x)\), které nemění znaménko, je konvergence řádu \begin{equation} \alpha = \frac{\sqrt{5}+1}{2} \simeq 1{,}618 , \label{eq:02:zlaty_rez} \end{equation} tedy zlatého řezu. Ukáže se totiž, že \(e_{n+1} \leq e_n e_{n-1}\), a pro počáteční chybu \(\varrho = \max(e_0, e_1)\) dostaneme \(e_2 \leq \varrho^2\), \(e_3 \leq \varrho^3\), \(e_4 \leq \varrho^5\) a tak dále; exponenty tvoří Fibonacciho posloupnost.
Protože však na jednu iteraci potřebujeme vyčíslit \(g\) pouze jednou, může být tato metoda rychlejší než Newtonova, kde potřebujeme i derivaci.
Kořeny polynomů
Pro hledání kořenů polynomů lze použít výše uvedené metody. Newtonovu metodu lze použít i pro hledání komplexních kořenů; jen pro vícenásobné kořeny dostáváme lineární konvergenci. Pokud známe násobnost kořene \(p\), iterujeme \begin{equation} x_{n+1} = x_n - p\,\frac{g(x_n)}{g'(x_n)} . \label{eq:02:newton_nasobny} \end{equation}
Dále je to například Laguerreova metoda, která využívá 2. derivace, též Skowron, Gould:
c) Iterační metoda pomocí Padého aproximace
Nahoře graf \(g(x)\) s body \(x_1\), \(x_p\), \(x_2\), \(x_3\) a svislicemi k ose, dole tytéž iterace vynesené v komplexní rovině (zde leží všechny na reálné ose). Táhněte třemi body na ose: fialová čárkovaná křivka je Padého aproximace \(P^1(x)/Q^1(x)\) proloženou těmito body a její kořen \(-a_0/a_1\) je další iterace. Vážený průměr týchž tří uzlů s vahami \(w_i = (x_j - x_k)/g(x_i)\), kde \(i,j,k\) probíhají cyklicky, dává tentýž bod jako přímé řešení soustavy pro koeficienty \(a_0\), \(a_1\), \(b_1\) — ověřeno na 15 platných cifer.
Vyjdeme z racionální aproximace jisté funkce \(f(x)\)
\begin{equation} f(x) \simeq \frac{a_0 + a_1 x + \dots + a_N x^N}{b_0 + b_1 x + \dots b_M x^M} = P_{I\!I}^{[N/M]}(x) = \frac{P^N(x)}{Q^M(x)} , \label{eq:02:pade_aproximace} \end{equation}s tím, že se obvykle položí \(b_0 = 1\). Aproximace \(P_I^{[N/M]}(x)\) by byla Padého aproximace získaná porovnáním s Taylorovým rozvojem.
K určení \(a_i\) a \(b_j\) je potřeba \(N+M+1\) bodů, což dává soustavu lineárních rovnic \begin{equation} P^N(x_k) = f(x_k)\, Q^M(x_k) . \label{eq:02:pade_soustava} \end{equation}
Použijeme-li \(P_{I\!I}^{[1/1]}(x)\) k aproximaci funkce \(g(x)\), jejíž kořen hledáme, a určíme-li kořen jako \(x_p \simeq -\dfrac{a_0}{a_1}\), pak opakováním tohoto postupu dostaneme iterační metodu \begin{equation} x_n = \frac{x_{n-1}\,\dfrac{(x_{n-2}-x_{n-3})}{F(x_{n-1})} + x_{n-2}\,\dfrac{x_{n-3}-x_{n-1}}{F(x_{n-2})} + x_{n-3}\,\dfrac{x_{n-1}-x_{n-2}}{F(x_{n-3})}}{\dfrac{x_{n-2}-x_{n-3}}{F(x_{n-1})} + \dfrac{x_{n-3}-x_{n-1}}{F(x_{n-2})} + \dfrac{x_{n-1}-x_{n-2}}{F(x_{n-3})}} . \label{eq:02:pade_iterace} \end{equation} Neboli jde o vážený průměr bodů \(x_{n-1}\), \(x_{n-2}\) a \(x_{n-3}\) pomocí vah \[ w_{n-1} = \frac{x_{n-2}-x_{n-3}}{F(x_{n-1})} \quad \text{atd.} \]
Řešení rovnic pro více proměnných
Banachova věta o pevném bodě platí stále, jen \(x\) je nyní vektor a \(f(x)\) je vektorová funkce. Iterujeme \begin{equation} x_i^{n+1} = f_i(x_1^n, \dots x_D^n) \quad \text{pro } i = 1,2,\dots,D . \label{eq:02:vice_promennych_iterace} \end{equation}
Pro chybu nyní máme \begin{equation} e^{n+1} = x^{n+1} - x_{(P)} = f(x^n) - f(x_{(P)}) = J(x_{(P)})\, e^n + O\big(\|e^n\|^2\big) , \label{eq:02:vice_promennych_chyba} \end{equation} kde \(J(x)\) je jakobián zobrazení \(f\), tj. \begin{equation} J = \begin{pmatrix} \dfrac{\partial f_1}{\partial x_1} & \cdots & \dfrac{\partial f_1}{\partial x_D} \\[2ex] \vdots & \ddots & \vdots \\[1ex] \dfrac{\partial f_D}{\partial x_1} & \cdots & \dfrac{\partial f_D}{\partial x_D} \end{pmatrix} . \label{eq:02:jakobian} \end{equation} Má-li být \(f(x)\) kontrahující zobrazení, musí být všechna vlastní čísla \(J\) menší než \(1\) (v absolutní hodnotě) pro \(\forall x\) z uvažované oblasti.
Řád konvergence \(\alpha\) je dán vztahem \begin{equation} \lim_{n \to \infty} \frac{\|x^{n+1} - x_{(P)}\|}{\|x^n - x_{(P)}\|^\alpha} = C < \infty , \label{eq:02:vice_promennych_rad} \end{equation} a je-li \(J(x_{(P)}) \neq 0\), budeme mít lineární konvergenci, atd.
Chceme-li vyřešit soustavu \(g(x) = 0\) pro vektorovou funkci \(g\), pak můžeme hledat pevný bod zobrazení \begin{equation} f(x) = x - A(x)\, g(x) , \label{eq:02:vice_promennych_f} \end{equation} kde \(A(x)\) je nesingulární matice pro \(\forall x\) z jistého okolí bodu \(x_{(P)}\), který je řešením \(g(x_{(P)}) = 0\).
Newtonova metoda plyne z požadavku, aby byl jakobián nulový, tj. \begin{equation} 0 = \frac{\partial f_i}{\partial x_j} = \delta_{ij} - \sum_k \left( \frac{\partial A_{ik}}{\partial x_j}\, \underbrace{g_k}_{\substack{\| \\ 0 \text{ pro } x = x_{(P)}}} + A_{ik} \frac{\partial g_k}{\partial x_j} \right) \quad \text{v } x = x_{(P)} , \label{eq:02:newton_vice_podminka} \end{equation} a tedy \begin{equation} \sum_{k=1}^{D} A_{ik} \frac{\partial g_k}{\partial x_j} = \delta_{ij} , \label{eq:02:newton_vice_A} \end{equation} neboli musíme iterovat \begin{equation} x^{n+1} = x^n - J_g(x^n)^{-1} g(x^n) \quad , \text{kde} \quad J_g(x)_{ij} = \frac{\partial g_i(x)}{\partial x_j} , \label{eq:02:newton_vice} \end{equation} nebo zapsáno jako soustava rovnic \[ J_g(x^n)(x^n - x^{n+1}) = g(x^n) . \]
Někdy se používá tzv. relaxace, kdy na pravé straně \(x = f(x)\) použijeme již modifikované složky \(x^n\): \begin{equation} x_i^{n+1} = f_i(x_1^{n+1}, \dots x_{i-1}^{n+1}, x_i^n, \dots x_D^n) . \label{eq:02:relaxace} \end{equation}