Numerické řešení nelineárních rovnic

Budu se zabývat úlohami, kde hledáme reálné řešení rovnice f(x) = 0, kde f je spojitá reálná funkce na intervalu <ao, b0>. Při řešení předpokládáme, že f(a0) ⋅ f(b0) < 0, tedy že funkční hodnoty dvou různých bodů mají opačná znaménka a že f má v intervalu <a0,b0> právě jeden kořen. Řešení hledáme se zadanou přesností ε > 0.

Než se však lze pustit do řešení rovnice, musí se provést separace kořenů, tedy odhadnutí, kde zhruba se požadovaný kořen nalézá. Tento postup bohužel není algoritmizovatelný. K separaci kořenů je potřeba jistá zkušenost či znalost matematiky. V dnešní době se k tomu ale stejně využívá výpočetní technika.

Metody numerického řešení nelineárních rovnic:

Metoda půlení intervalu

Pokud je splněna podmínka přítomnosti právě jednoho kořene na intervalu <a0,b0>, metoda vždy vede k řešení a vždy konverguje stejně pomalu.

Postup je jednoduchý. Dělíme interval na poloviny a zkoumáme, která půlka původního intervalu splňuje podmínku opačných znamének funkčních hodnot. Na tom intervalu totiž leží hledané řešení a abychom jej ještě více upřesnili, znovu jej dělíme a zkoumáme, až dokud není dosaženo požadované přesnosti.

Vzato matematicky pro k ϵ N, bod xk + 1, rozdělující interval <ak, bk>, získáme z rovnice
x_k+1 = (a_k + b_k)/2

    Potom platí:
  • je-li f(xk + 1) ⋅ f(ak) < 0, pak x ϵ <ak, xk + 1>
  • je-li f(xk + 1) ⋅ f(bk) < 0, pak x ϵ <bk, xk + 1>
  • je-li f(xk + 1) = 0, pak x = xk + 1

Postup opakujeme dokud není dosažena požadovaná přesnost a neplatí, že bk - ak < 2ε.

Dá se vypočítat i počet kroků, který je potřeba k dosažení určité přesnosti a to pomocí vzorce
l/2^k < 2*epsilon,
kde l je délka intervalu (absolutní hodnota) ak je počet kroků.

Metoda regula falsi

Tato metoda je podobná jako metoda půlení intervalu, ale interval < a , b > dělíme na dvě obecně různé části a to v poměru
abs(f(a))/abs(f(b)).
Regula falsi konverguje vždy a rychleji než metoda půlení intervalu, ale je náročnější na výpočet.

Dělící bod x k získáme z rovnice
vzorec metody regula falsi
a výpočet zastavíme pokud pro k ϵ N platí: | x k - x k - 1 |< ε.

Metoda sečen

Od předchozích dvou se dost liší. Rozdíl je v tom, že místo a0, b0 použijeme vždy posledně vypočtené body x0, x1. Také konvergence už není zaručena, je ovšem rychlejší.

x0 = b0, x1 = a0

vzorec numericke metody sečen

Dokud |xk - xk - 1 |< ε nebo dokud i nebude rovno předepsanému počtu kroků.

Newtonova metoda (metoda tečen)

Při řešení jedné nelineární rovnice nás zajímá konkrétně jednobodová varianta metody. Existují totiž i varianty Newtonovy metody pro řešení soustav rovnic(dvoubodové, vícebodové). Metoda předpokládá existenci a znalost první derivace. Konvergence je nejrychlejší ale není zaručena.

Tečna ke grafu funkce f v bodě [xi - 1, f(xi - 1)] má rovnici

t i - 1 ( x ) = f ( x i - 1 ) + ( x - x i - 1 ) ⋅ f '( x i - 1 )

s nulovým bodem
vzorec pro nulový bod Newtonovy metody

Opět dokud |xi - xi - 1 |< ε nebo dokud i nebude rovno předepsanému počtu kroků.

Postup při řešení pomocí Newtonovy metody je následovný.

  1. Ověříme podmínky konvergence
  2. Zvolíme počáteční aproximaci kořene x0
  3. bodem [x0, f(x0)] vedeme tečnu ke grafu funkce f(x)
  4. její průsečík s osou x označíme x1
  5. iterujeme kroky 3 a 4.
    Nejsou-li ověřeny všechny následující podmínky konvergence, nemusí metoda konvergovat.
  1. Uzavřený interval <a,b>
  2. na <a,b> se nechází právě jeden kořen
  3. funkce f'(x) a f''(x) jsou spojité a na intervalu <a,b> nemění znaménko.

Počáteční aproximace se pak určí podle rozboru vztahu f(xo) ⋅ f''(x0) > 0, pro x0 ϵ <a,b>.

Metoda prosté iterace

Spočívá v drobné modifikaci funkce f(x) na funkci g(x), např.: g(x) = f(x) + x.

Počáteční odhad x0 je upřesnován podle xi = g(xi - 1) až dokud |xi - xi - 1 |< ε.

Najít vhodnou iterační funkci může být velmi obtížné a ověření podmínek konvergence bývá často problematické.