Iterační metoda řešení rovnic

Iterační metoda řeší rovnici přibližně: místo jednoho chytrého výpočtu opakujeme pořád stejný jednoduchý krok a každé opakování nás přiblíží k řešení. Rovnici převedeme na tvar `x=g(x)`, zvolíme počáteční odhad `x_0` a dosazujeme výsledek zpět do vzorce:

`\displaystyle x_{n+1}=g(x_n)`

Pokud se čísla `x_1,\ x_2,\ x_3,\ \ldots` ustálí, číslo, ke kterému se blíží, je řešením rovnice. Metoda se hodí hlavně na rovnice, které vzorcem vyřešit nejde, třeba `\cos x=x` nebo `x^5+x=3`, a přesně tak počítají kořeny rovnic počítače a kalkulačky.

Níže je postup prosté iterace na příkladech, pravidlo, kdy iterace funguje a kdy ne, a dvě nejznámější chytřejší iterační metody: Newtonova metoda tečen a metoda půlení intervalu. Na konci je iterační řešení soustav rovnic a příklady k procvičení.

Co je iterace

Slovo iterace pochází z latinského iterare, opakovat. Iterace je jedno opakování téhož postupu, při kterém se výsledek jednoho kroku stane vstupem do kroku dalšího. Stejné slovo se používá v programování (jeden průchod cyklem) i v řízení projektů (jedno kolo vylepšování).

V matematice je výsledkem iterace rekurentně zadaná posloupnost: každý člen se spočítá z předchozího. Když má tato posloupnost limitu `L` a funkce `g` je spojitá, platí `L=g(L)`, takže limita je řešením rovnice. Takovému číslu se říká pevný bod funkce `g` a prosté iteraci také metoda pevného bodu.

Iteraci si můžete vyzkoušet hned. Přepněte kalkulačku na radiány, zadejte 0 a mačkejte pořád dokola tlačítko cos. Čísla nejdřív skáčou (1; 0,540; 0,858; 0,654; ...), pak se ustálí na 0,739085. To je řešení rovnice `\cos x=x`, ke kterému se vrátíme níž.

Postup prosté iterace

1. Převeďte rovnici na tvar `x=g(x)`. Jde to vždy mnoha způsoby a na volbě záleží, jak ukáže další oddíl.
2. Zvolte počáteční odhad `x_0`. Stačí hrubý, třeba z náčrtu grafu nebo z dosazení několika čísel.
3. Počítejte `x_1=g(x_0)`, `x_2=g(x_1)`, ... a každý výsledek dosaďte zpátky.
4. Skončete, když se dva po sobě jdoucí členy liší méně, než je požadovaná přesnost, například když se shodují na čtyřech desetinných místech.
5. Udělejte zkoušku dosazením do původní rovnice.

Příklad 1

Řešte iterační metodou rovnici `\dfrac{1}{x}-x+3=0` s přesností na čtyři desetinná místa.

Osamostatníme `x`, které stojí samo, a dostaneme tvar `x=3+\dfrac{1}{x}`, tedy `g(x)=3+\dfrac{1}{x}`. Začneme od `x_0=1`:

`\begin{gathered}x_1=3+\dfrac{1}{1}=4 \\[10pt] x_2=3+\dfrac{1}{4}=3{,}25 \\[10pt] x_3=3+\dfrac{1}{3{,}25}\doteq 3{,}3077 \\[10pt] x_4=3+\dfrac{1}{3{,}3077}\doteq 3{,}3023 \\[10pt] x_5=3+\dfrac{1}{3{,}3023}\doteq 3{,}3028 \\[10pt] x_6=3+\dfrac{1}{3{,}3028}\doteq 3{,}3028\end{gathered}`

Pátý a šestý člen se shodují na čtyřech desetinných místech, řešení je `x\doteq 3{,}3028`.

Kontrola. Po vynásobení `x` je to kvadratická rovnice `x^2-3x-1=0` s kořeny `\dfrac{3\pm\sqrt{13}}{2}`, tedy `3{,}302\,776` a `-0{,}302\,776`. Iterace našla ten kladný. Kvadratickou rovnici samozřejmě umíme vyřešit přesně (viz kvadratická rovnice nebo kalkulačka kvadratické rovnice), proto se na ní dobře ověřuje, že iterace počítá správně.

Všimněte si, že se čísla střídavě dostávají nad výsledek a pod něj (4; 3,25; 3,3077; 3,3023; ...) a odchylka se každým krokem zmenší zhruba jedenáctkrát. Proč zrovna tolik, vysvětluje následující oddíl.

Kdy iterace konverguje

Iterace nemusí vést k řešení. Zkusme stejnou rovnici `x^2-3x-1=0` převést jinak: `3x=x^2-1`, tedy `x=\dfrac{x^2-1}{3}`. Od `x_0=3{,}5`, tedy blízko kořene 3,30, dostaneme 3,75; 4,35; 5,99; 11,61 a čísla utíkají do nekonečna. Stejná rovnice, jiný tvar, a iterace selže.

Rozhoduje sklon funkce `g` v okolí kořene, tedy její derivace:

`\begin{gathered}|g'(x)|\lt 1\ \Rightarrow\ \text{iterace konverguje} \\[6pt] |g'(x)|\gt 1\ \Rightarrow\ \text{iterace se od kořene vzdaluje}\end{gathered}`

Přesněji: když na nějakém okolí kořene platí `|g'(x)|\le q\lt 1` a začneme v tomto okolí, posloupnost ke kořeni konverguje a odchylka se každým krokem zmenší přibližně `|g'|`-krát. Chyby tedy klesají jako členy geometrické posloupnosti s kvocientem `q`.

V příkladu 1 je `g'(x)=-\dfrac{1}{x^2}`, u kořene `-\dfrac{1}{3{,}3028^2}\doteq -0{,}092`. Odchylka se tak každým krokem zmenší asi jedenáctkrát a znaménko mínus způsobí střídání nad a pod výsledkem. U tvaru `g(x)=\dfrac{x^2-1}{3}` je `g'(x)=\dfrac{2x}{3}`, u kořene 3,30 to je 2,2, a proto se odchylka každým krokem zhruba zdvojnásobí.

Je to dobře vidět i na obrázku. Kreslíme graf `y=g(x)` a přímku `y=x`, jejich průsečík je řešení. Z bodu `x_0` jdeme svisle ke grafu (spočítáme `g(x_0)`) a vodorovně k přímce `y=x` (výsledek se stane novým `x`). Vznikne schodiště, nebo spirála, nebo cesta pryč:

Zajímavost: tvar `x=\dfrac{x^2-1}{3}`, který u kořene 3,30 selhal, u druhého kořene `-0{,}30` funguje, protože tam je `g'(-0{,}30)\doteq -0{,}2`. Od `x_0=0` dává `-0{,}3333;\ {-0{,}2963};\ {-0{,}3041};\ {-0{,}3025};\ \ldots` a míří k `-0{,}3028`. Naopak tvar `x=3+\dfrac{1}{x}` má u záporného kořene `|g'|\doteq 10{,}9` a od toho kořene iterace uteče, i když začnete hned vedle něj. Pro každý kořen je proto potřeba hledat vhodný tvar zvlášť.

Příklad 2: rovnice cos x = x

Tuhle rovnici žádnými úpravami nevyřešíte, `x` je jednou uvnitř kosinu a jednou venku. Iterace je tu nejjednodušší cesta: tvar `x=\cos x` už máme, takže `g(x)=\cos x`. Počítáme v radiánech od `x_0=0`:

`\begin{gathered}x_1=1,\quad x_2\doteq 0{,}5403,\quad x_3\doteq 0{,}8576 \\[6pt] x_4\doteq 0{,}6543,\quad x_5\doteq 0{,}7935,\quad x_6\doteq 0{,}7014 \\[6pt] x_7\doteq 0{,}7640,\quad x_8\doteq 0{,}7221,\quad \ldots\end{gathered}`

Ke kořeni `x\doteq 0{,}7391` to jde pomalu: aby se člen od kořene lišil méně než o 0,00005, je potřeba 23 kroků. Důvod je zase v derivaci: `|g'(x)|=|\sin x|` je u kořene asi 0,67, chyba se tedy každým krokem zmenší jen o třetinu. To je prostý odhad, kdy je iterace pomalá: čím blíž je `|g'|` k jedničce, tím víc kroků.

Graf `y=\cos x` klesá, proto prostřední obrázek nahoře ukazuje spirálu: čísla skáčou střídavě nad řešení a pod něj.

Newtonova metoda (metoda tečen)

Newtonova metoda je iterace, kterou nemusíte vymýšlet. Rovnici zapíšete jako `f(x)=0` a v bodě `x_n` nahradíte graf funkce jeho tečnou. Tam, kde tečna protne osu `x`, je další odhad:

`\displaystyle x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}`

Potřebujete k tomu derivaci. Odměnou je rychlost: blízko kořene se počet správných desetinných míst každým krokem zhruba zdvojnásobí.

Příklad 3: odmocnina ze dvou

Číslo `\sqrt{2}` je kladné řešení rovnice `x^2-2=0`. Je `f(x)=x^2-2`, `f'(x)=2x` a po dosazení do vzorce a úpravě vyjde

`\displaystyle x_{n+1}=x_n-\frac{x_n^2-2}{2x_n}=\frac{1}{2}\left(x_n+\frac{2}{x_n}\right)`

Od `x_0=2`:

`\begin{gathered}x_1=\frac{1}{2}\left(2+1\right)=1{,}5 \\[10pt] x_2=\frac{1}{2}\left(1{,}5+\frac{2}{1{,}5}\right)\doteq 1{,}416\,667 \\[10pt] x_3\doteq 1{,}414\,216 \\[10pt] x_4\doteq 1{,}414\,213\,562\end{gathered}`

Skutečně `\sqrt{2}=1{,}414\,213\,562\ldots` Správné cifry za desetinnou čárkou: 0, 2, 5, 11. Postup se připisuje už starověkým Babyloňanům a říká se mu také Heronova metoda.

Příklad 4: cos x = x Newtonovou metodou

Zapíšeme `f(x)=\cos x-x`, `f'(x)=-\sin x-1`. Od `x_0=1`:

`\begin{gathered}x_1=1-\dfrac{\cos 1-1}{-\sin 1-1}\doteq 0{,}7504 \\[10pt] x_2\doteq 0{,}739\,113,\quad x_3\doteq 0{,}739\,085\,133\end{gathered}`

Tři kroky místo dvaceti tří. Newtonova metoda ale může selhat: když je derivace v některém kroku nula (tečna je vodorovná a osu neprotne), nebo když je počáteční odhad daleko a tečna pošle další odhad úplně jinam. Proto se start volí z náčrtu grafu co nejblíž kořeni.

Metoda půlení intervalu (bisekce)

Nejjednodušší a nejspolehlivější iterační metoda. Když je funkce `f` spojitá a má na krajích intervalu `\langle a;\ b\rangle` opačná znaménka, leží mezi nimi kořen. Spočítáte hodnotu ve středu intervalu a ponecháte tu polovinu, na jejíchž koncích má `f` pořád opačná znaménka. Interval s kořenem se každým krokem zmenší na polovinu.

Příklad 5

Najděte kořen rovnice `x^3+x-1=0`. Je `f(0)=-1\lt 0` a `f(1)=1\gt 0`, takže kořen leží v `\langle 0;\ 1\rangle`.

Po osmi krocích víme, že kořen leží mezi 0,6797 a 0,6836. Obě meze se zaokrouhlí na 0,68, takže `x\doteq 0{,}68`. Skutečný kořen je `0{,}682\,328`. Na každé další desetinné místo potřebuje půlení asi 3,3 kroku (`2^{3{,}3}\doteq 10`), je tedy pomalé, ale nikdy neselže. Půlením intervalu počítá například naše kalkulačka RPSN: úrok, při kterém se splátky vyrovnají půjčce, nejde vyjádřit vzorcem.

Iterační řešení soustav rovnic

Iterovat jde i soustavu. Z každé rovnice vyjádříme jednu neznámou, zvolíme počáteční hodnoty a dosazujeme. Vezměme soustavu

`\begin{gathered}x+\dfrac{1}{2}y=0 \\[10pt] y+\dfrac{1}{2}x=8\end{gathered}`

Z první rovnice `x=-\dfrac{1}{2}y`, z druhé `y=8-\dfrac{1}{2}x`. Začneme od `x_0=0`, `y_0=0`.

Jacobiho metoda počítá nové `x` i nové `y` jen z hodnot předchozího kroku:

`\begin{gathered}{}[x_1;\ y_1]=[0;\ 8] \\[6pt] {}[x_2;\ y_2]=[-4;\ 8] \\[6pt] {}[x_3;\ y_3]=[-4;\ 10] \\[6pt] {}[x_4;\ y_4]=[-5;\ 10] \\[6pt] {}[x_5;\ y_5]=[-5;\ 10{,}5] \\[6pt] {}[x_6;\ y_6]=[-5{,}25;\ 10{,}5]\end{gathered}`

Gaussova-Seidelova metoda dosadí nové `x` do výpočtu `y` hned v tomtéž kroku:

`\begin{gathered}x_1=0,\quad y_1=8-0=8 \\[6pt] x_2=-4,\quad y_2=8+2=10 \\[6pt] x_3=-5,\quad y_3=8+2{,}5=10{,}5 \\[6pt] x_4=-5{,}25,\quad y_4=10{,}625\end{gathered}`

Gaussova-Seidelova metoda je po třech krocích tam, kam se Jacobiho dostane za pět, potřebuje tedy zhruba poloviční počet kroků. Obě míří k přesnému řešení

`\begin{gathered}x=-\dfrac{16}{3}\doteq -5{,}33 \\[10pt] y=\dfrac{32}{3}\doteq 10{,}67\end{gathered}`

Zkouška: `-\frac{16}{3}+\frac{1}{2}\cdot\frac{32}{3}=0` a `\frac{32}{3}+\frac{1}{2}\cdot\left(-\frac{16}{3}\right)=8`. Výsledek si můžete ověřit i v kalkulačce soustavy dvou rovnic.

Konvergenci zaručuje diagonální převaha: v každé rovnici je koeficient u vyjadřované neznámé v absolutní hodnotě větší než součet absolutních hodnot ostatních koeficientů na levé straně. Tady `1\gt\dfrac{1}{2}` v obou rovnicích. Malou soustavu je rychlejší vyřešit přesně (dosazením nebo Gaussovou eliminací), iterace se vyplácí u soustav s tisíci neznámých, jaké řeší počítače při simulacích.

Kterou metodu zvolit

V praxi se metody kombinují: půlením se kořen hrubě ohraničí a Newtonova metoda ho pak rychle zpřesní.

Časté chyby

• Tvar `x=g(x)` se volí naslepo. Než začnete počítat, odhadněte `|g'|` u kořene. Když vyjde víc než 1, osamostatněte `x` z jiného členu rovnice.
• Kalkulačka ve stupních. U `\cos x=x` ve stupních iterace skončí u čísla 0,99985, které rovnici v radiánech neřeší. Goniometrické funkce v rovnicích s `x` vně funkce se počítají v radiánech.
• Konec po prvních dvou podobných číslech. U pomalé iterace se sousední členy liší málo, i když je kořen ještě daleko. Při `|g'|` blízko jedné počítejte dál, nebo použijte Newtonovu metodu.
• Zaokrouhlování v průběhu. Mezivýsledky nechte v kalkulačce na plný počet míst a zaokrouhlete až výsledek. Iterace sice drobné chyby sama opravuje, ale při zaokrouhlení na dvě místa se ani nemůže dostat na čtyři.
• Chybí zkouška. Číslo, ke kterému iterace dospěla, dosaďte do původní rovnice. U soustav pozor na znaménka při vyjadřování neznámé: `x+\frac{1}{2}y=0` dává `x=-\frac{1}{2}y`, ne `x=\frac{1}{2}y`.

Příklady k procvičení

Kam dál

• Kalkulačky rovnic: lineární, kvadratická, soustava dvou rovnic, vždy s postupem, ať máte iteraci s čím porovnat.
• Výpočet RPSN: půlení intervalu v praxi.
• Rovnice: přehled druhů rovnic a jak je řešit přesně.
• Geometrická posloupnost: proč chyba iterace klesá jako její členy.
• Limity funkcí a základy derivace: pojmy, na kterých stojí podmínka konvergence a Newtonova metoda.