Numerické riešenie nelineárnych rovníc \(f(x)=0\)

Ciele
  1. Ilustrovať pojem intervalu separácie koreňa rovnice.\(\def\a{&}\)
  2. Naučiť sa odhadnúť [ne]presnosť numerického riešenia rovnice.
  3. Naučiť sa používať metódu bisekcie na riešenie nelineárnej rovnice \(f(x)=0\).
  4. Naučiť sa používať Newtonovu metódu na riešenie nelineárnej rovnice \(f(x)=0\).
Úvod
    Nelineárne rovnice \(f(x)=0\), respektíve systémy nelineárnych rovníc, sa vyskytujú pri riešení mnohých technických (inžinierskych) úloh. Ako príklad môžeme uviesť charakteristickú rovnicu lineárnej diferenciálnej rovnice s konštantnými koeficientami – algebrickú rovnicu. Znalosť (všetkých, vrátane komplexných) koreňov charakteristickej rovnice (jej riešení) je potrebná, napríklad, na pochopenie toho, či je opisovaný technický systém stabilný alebo nie. My sa budeme venovať len reálnym koreňom nelineárnej rovnice.

    Je známe, že množina nelineárnych úloh, ktoré je možné vyriešiť presne, je dosť úzka, väčšinou sa stretávame s úlohami, ktorých riešenie si vyžaduje použitie numerických metód na určenie približného riešenia.

    Na numerické riešenie konkrétnych nelineárnych rovníc môžeme použiť tak všeobecné metódy, akými sú, napríklad metóda bisekcie alebo Newtonova metódu, ako aj špecializované metódy, vhodné na riešenie istých typov (tried) úloh.

    Riešenie rovnice môžeme symbolicky rozdeliť na tri podúlohy:
    1. Analýza existencie koreňov rovnice, ich počtu a podľa možnosti odhadu intervalov, v ktorom ležia jednotlivé korene, t. j. separácia koreňov. Interval \(\langle a_i; b_i\rangle\) budeme nazývať intervalom separácie koreňa \(\alpha_i\) práve vtedy, ak \(\alpha_i\in(a_i;b_i)\), \(f(\alpha_i)=0\) a pre každé \(x\in \langle a_i; b_i\rangle\), \(x\ne \alpha_i\) je \(f(x)\ne0\).
    2. Použitie iteračných postupov konkrétnej metódy, ktorá umožňuje postupné upresňovanie približných riešení.
    3. Odhad [ne]presnosti priebežného/výsledného numerického riešenia.
    Poznámka: Intervalom separácie koreňov v širšom zmysle budeme nazývať taký uzavretý interval \(\langle a;b\rangle\), v ktorom leží aspoň jeden koreň rovnice \(f(x)=0\). Je zrejmé, že interval separácie koreňa \(\alpha\) obsahujúci práve jeden koreň je automaticky intervalom separácie aj v širšom zmysle, naopak to však neplatí.


    Bolzanova veta. Nech funkcia \(f: \mathbb{R} \supset A\ \to \mathbb{R}\) je spojitá na intervale \(\langle a;b \rangle \subset A\) a platí \(f(a)\cdot f(b)\lt 0\). Potom existuje aspoň jedno číslo \(c \in (a;b)\) také, že \(f(c) = 0\).

    Poznámka: Splnenie podmienok Bolzanovej vety implikuje fakt, že interval \(\langle a;b \rangle\) je intervalom separácie v širšom zmysle slova. Existenciu práve jedného koreňa na intervale je potrebné zdôvodniť ďalšími argumentmi.
Postup
  1. Pri analýze mnoh�ch nelineárnych rovníc je vhodné použitie grafických metód. Ak nevieme priamo načrtnúť graf funkcie \(f(x)\), rovnicu \(f(x)=0\), ktorej reálne riešenia predstavujú priesečníky grafu funkcie s osou \(o_x\), môžeme ekvivalentne prepísať na tvar \(h(x)=g(x)\), s funkciami, ktorých grafy sa dajú načrtnúť jednoduchšie. Riešeniami pôvodnej rovnice potom budú \(x\)-ové súradnice priesečníkov grafov funkcií \(h(x)\) a \(g(x)\).
    Poznámka: Pri náčrte grafov funkcií, ktorý je takmer vždy nepresný, sa môže stať, že si niektoré priesečníky nevšimneme. Grafické metódy je preto vhodné dopĺňať analytickými úvahami o možnej [ne]existencii koreňov v uvažovanej oblasti.
    Príklad: Určme počet reálnych riešení nelineárnej rovnice \[ x^4+2x+4=0 \] a separujme všetky reálne korene.
    Zobraziť riešenie
    Príklad: Určme počet reálnych riešení nelineárnej rovnice \[ x^3+2x+4=0 \] a separujme všetky reálne korene.
    Zobraziť riešenie
    Poznámka: Uvedené dve podmienky intervalu separácie sú postačujúce podmienky existencie riešenia vnútri intervalu, ale nie sú nutné, t. j. korene rovnice môžu ležať aj vnútri intervalu, na ktorom tieto podmienky nie sú splnené. To je prípad všetkých dvoj-, štvornásobných a pod. koreňov rovníc (napríklad pre riešenie \(x=0\) rovnice \(x^2=0\)).
    Príklad: Určme počet reálnych riešení nelineárnej rovnice \[ 2\cos x -\ln x=0 \] a separujme všetky reálne korene.
    Zobraziť riešenie
  2. Venujme sa teraz odhadu chyby približného riešenia nelineárnej rovnice.
    Príklad: Určme, akej chyby sa dopustíme, ak za približné riešenie rovnice \(x^3+2x+4=0\) vezmeme hodnotu \(x_p=-1{,}2\).
    Zobraziť riešenie
  3. Ďalej sa budeme venovať metóde bisekcie na riešenie nelineárnych rovníc \(f(x)=0\) so spojitou funkciou \(f(x)\). Predpokladajme, že sme pre niektoré riešenie rovnice \(f(x)=0\) určili interval separácie (v širšom zmysle) \(\langle a;b\rangle\), pričom platí \(f(a)\cdot f(b)\lt0\). Uvažujme stred intervalu separácie – bod \(c=(a+b)/2\). Môžu nastať 3 prípady:
    1. \(f(c)=0\), t. j. bod \(c\) je presné riešenie rovnice, \(c=x^*\)!
    2. \(f(c)\cdot f(a)\lt0\), t. j. interval \(\langle a;c\rangle\) je interval separácie, pričom jeho dĺžka je polovičná v porovnaní s intervalom separácie \(\langle a;b\rangle\). Bod \(c\) prehlásime za nový pravý kraj intervalu separácie, t. j. položíme \(b=c\).
    3. \(f(c)\cdot f(b)\lt0\), t. j. interval \(\langle c;b\rangle\) je interval separácie, pričom jeho dĺžka je polovičná v porovnaní s intervalom separácie \(\langle a;b\rangle\). Bod \(c\) prehlásime za nový ľavý kraj intervalu separácie, t. j. položíme \(a=c\).
    Poznámka: Bod \(c\) nemusí ležať presne v strede intervalu.
    Je zrejmé, že ak budeme v delení intervalu na dve rovnaké časti pokračovať, po každom kroku sa odhad nepresnosti stredu intervalu separácie zmenšuje na polovicu alebo sa stred stane presným riešením!
    Príklad: Metódou bisekcie určme približné riešenie rovnice \(x^3+2x+4=0\) s presnosťou \(\varepsilon=0{,}01\).
    Zobraziť riešenie
    Poznámka: Programy Matlab a Octave majú zabudovanú funkciu na riešenie algebrických rovníc, ktorá je samozrejme tiež numerická.
    Príkaz roots([1 0 2 4]) dáva odpoveď v nasledujúcom tvare:

    ans =
    0.589754512301458 + 1.744543250922657i
    0.589754512301458 - 1.744543250922657i
    -1.179509024602917 + 0.000000000000000i


    Odchýlka nášho numerického riešenia od numerického riešenia určeného funkciou roots je \(|-1{,}179509024602917-(-1{,}18125)|\lt 0{,}001741\) je blízka skutočnej absolútnej chybe.
    Poznámka: Najdôležitejšou vlastnosťou metódy bisekcie je jej bezpodmienečná konvergencia na ľubovoľnom intervale separácie (maximálny počet krokov sa dá dopredu odhadnúť) a tiež jednoduchá programová implementácia. Na uskutočnenie iteračného procesu postačuje výpočet funkčných hodnôt. Nevýhodou je pomalá konvergencia – na výpočet približného riešenia s nie veľmi veľkou presnosťou sme potrebovali uskutočniť 5 iterácií.
  4. Newtonova metóda na riešenie úloh sa vyznačuje tzv. kvadratickou rýchlosťou konvergencie, ktorá je oveľa lepšia, ako v prípade metód založených na využití výhradne funkčných hodnôt. Nevýhodou však je, že metóda nemusí konvergovať, presnejšie, ak chceme mať istotu jej konvergencie, musíme overiť/zabezpečiť splnenie niektorých postačujúcich podmienok konvergencie.

    Zameriame sa na overenie nasledujúcich postačujúcich podmienok konvergencie:
    1. \(f(a)\cdot f(b)\lt0\) – \(\langle a;b\rangle\) je interval separácie v širšom zmysle;
    2. \(f^{\prime\prime}(x)\ne 0\) – funkcia je na intervale separácie buď konvexná alebo konkávna;
    3. \(f(x_0)\cdot f^{\prime\prime}(x_0) \gt 0\) – štartovací bod \(x_0\in\langle a;b\rangle\) má byť správne zvolený. Najčastejšie sa volí \(x_0=a\) alebo \(x_0=b\) – jeden z týchto bodov spĺňa uvedenú podmienku;
    4. \begin{equation}\label{newton} x_{n+1}=x_n-\dfrac{f(x_n)}{f^{\prime}(x_n)}, \qquad n=0, 1, 2, \dots \end{equation} – iteračný proces na základe metódy dotyčníc.
    Poznámka: V prípade, ak na intervale separácie platí podmienka \(0\lt m\leqq |f^{\prime}(x)|\), na ukončenie procesu používame odhad chyby (\ref{odhad}). Podmienka konvexnosti resp. konkávnosti spolu s podmienkou \(f(a)\cdot f(b)\lt0\) zabezpečuje existenciu práve jedného koreňa. Samozrejme predpokladáme existenciu druhej derivácie, z ktorej vyplýva spojitosť funckie na intervale \(\langle a;b \rangle\).
    Výpočty je možné zorganizovať nasledujúcim spôsobom: pre aktuálnu hodnotu \(x_n\), \(n=0\), \(1\), \(2\), \(\dots\) vypočítame hodnotu \(f(x_n)\) a odhadneme chybu na základe vzorca (\ref{odhad}). Ak je chyba menšia ako zadaná presnosť, iterácie ukončíme, v opačnom prípade vypočítame \(f^{\prime}(x_n)\) a dosadením do vzorca (\ref{newton}) určíme novú hodnotu \(x_{n+1}\).
    Príklad: Newtonovou metódou určme približné reálne riešenie rovnice \(x^3+2x+4=0\) na intervale separácie \(\langle-2;-1\rangle\) s presnosťou \(\varepsilon=10^{-6}\).
    Zobraziť riešenie
    Príklad: Newtonovou metódou určme približne najväčšie reálne riešenie rovnice \(2\cos x-\ln x=0\) s presnosťou \(\varepsilon=10^{-6}\).
    Zobraziť riešenie
Zdroje
  1. Buša, Pirč, Schrötter: Numerické metódy, pravdepodobnosť a matematická štatistika, 2006, ISBN 80-8073-632-4. Stiahnuť obrazovkovú alebo tlačovú verziu.
  2. Daňo, Ostertagová: Vybrané kapitoly z numerických metód, pravdepodobnosti a matematickej štatistiky, Equilibria s.r.o., Košice, 2012, ISBN 978-80-8143-012-1.
Doplňujúce úlohy
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte najmenší reálny koreň rovnice \(x^3 + 2 x^2 - 4 x - 5 = 0\) s presnosťou \(0{,}005.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte najväčší reálny koreň rovnice \(x^3 + 0{,}9 x^2 + 1{,}1 x - 7{,}8 = 0\) s presnosťou \(0{,}005.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte najmenší reálny koreň rovnice \(x^3 -12 x + 1 = 0\) s presnosťou \(0{,}000001.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte všetky reálne korene rovnice \(2 x^5 + 5 x^4 -10 x^2 + 10x - 3 = 0\) s presnosťou \(0{,}000001.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte kladný koreň rovnice \(2 x^4 + 6 x^3 + 5 x^2 - 0{,}5 = 0\) s presnosťou \(0{,}0001.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte všetky reálne korene rovnice \(\sin x + 2 x - 2 = 0\) s presnosťou \(0{,}000001.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte všetky reálne korene rovnice \(2 x\cdot \ln x - 4 x + 5{,}3 = 0\) s presnosťou \(0{,}00001.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte všetky reálne korene rovnice \(x^3 - 8 x + 15 = 0\) s presnosťou \(0{,}0001.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte všetky reálne korene rovnice \(x^3 + 3 x^2 - 3 = 0\) s presnosťou \(0{,}001.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte najväčší reálny koreň rovnice \(5 x^3 + 2 x^2 - 15 x - 6 = 0\) s presnosťou \(0{,}0001.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte všetky reálne korene rovnice \(x^3 - 7 x - 7 = 0\) s presnosťou \(0{,}001.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte všetky reálne korene rovnice \(x^4-3 x^2+4 x-1 = 0\) s presnosťou \(0{,}001.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte všetky reálne korene rovnice \(x^5 - x^4 + 2 x^3 - 3 x^2 + 4 x - 5 = 0\) s presnosťou \(0{,}0001.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte záporný koreň rovnice \(x^6 - 3 x^2 + x - 1 = 0\) s presnosťou \(0{,}0001.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte všetky reálne korene rovnice \(x - \sin x = 0{,}25\) s presnosťou \(0{,}00001.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte všetky reálne korene rovnice \(2{,}2 x - 2^x = 0\) s presnosťou \(0{,}00001.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte všetky reálne korene rovnice \(2 \,\mathrm{ln} x - 1/x = 0\) s presnosťou \(0{,}00001.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte všetky reálne korene rovnice \(\mathrm{e}^{-x} + x^2 - 2 = 0\) s presnosťou \(0{,}00001.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte všetky reálne korene rovnice \(\mathrm{e}^x + x^2 - 2 = 0\) s presnosťou \(0{,}00001.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte všetky reálne korene rovnice \(2 x - \mathrm{log} x - 7 = 0\) väčšie ako 3 s presnosťou \(0{,}00001.\)
    Zobraziť výsledok
    Úloha: Pomocou metódy bisekcie a Newtonovej metódy určte kladné korene rovnice \(\mathrm{e}^x + \mathrm{e}^{-3x} = 4\) s presnosťou \(0{,}00001.\)
    Zobraziť výsledok
comments powered by Disqus