Cieľom tohto cvičenia je naučiť sa riešiť rovnice typu \(f(x)=0\), poprípade sústavu \(\vec{F}(x_1,x_2,..,x_n)=\vec{0}\), teda nájsť koreň rovnice alebo systému n rovníc o n neznámych.
Funkcia jednej premennej
Uvažujme funkciu, ktorá je spojitá na intervale <a,b>. Ak je zároveň splnené, že \(f(a).f(b)<0\), potom v intervale <a,b> leží aspoň jeden koreň rovnice \(f(x)=0\). Veta je intuitívne ľahko pochopiteľná z geometrickej predstavy. Je potrebné si však uvedomiť že:
- koreňov môže byť v intervale viac - o ich počte veta nevraví nič
- ak podmienka splnená nie je, neznamená to, že v intervale neleží žiaden koreň
Pomocou spomenutej vety sa realizuje prvý rok riešenia nelineárnej úlohy - ohraničenie koreňa. Ak sme určili intervaly, v ktorých sa nachádza iba jeden koreň, môžme začať s hľadaním samotného koreňa na danom intervale.
Bisekcia
Najjednoduchšou a metódou je bisekcia - půlení intervalov. Metóda je intuitívna, viď prednáška a novšia verzia prednášky. Vysvetlenie implementácie sa nachádza vo videu, ktoré nahral Honza Vábek. Čas 12:40-23:50, môžte si k tomu stiahnuť matlaboský skript.
Vlastnosti metódy
- vždy konverguje, ale pomaly (lineárne)
- počet iterácií potrebný k dosiahnutí danej presnosti nezávisí od riešenej rovnice
- po \(k\) iteráciách je veľkosť intervalu \(\frac{b-a}{2^k}\)
Sekantová metóda
Implementácia sekantovej je vysvetlená vo videu v čase 30:19-52:20, využíva tento skript. Záujemcovia si môžu metódu naimplementovať sami, nezabudnite však pridať do kódu podmienku na ukončenie cyklu v závislosti od chyby. Takisto je dobré počítať s možnosťou, že sekantová metóda nemusí konvergovať, pridajte preto podmienku na maximálny počet iterácií aby sa program nezasekol v nekonečnom cykle. Ak je sekantová metóda neúspešná v hľadaní koreňa, treba zvoliť iný počiatočný bod alebo inú metódu. Nový bod \(x_{k+1}\) volíme vzťahom
\begin{equation} x_{k+1}=\frac{x_{k-1}f(x_{k})-x_kf(x_{k-1})}{f(x_k)-f(x_{k-1})} \end{equation}
Vlastnosti metódy
- nie je zaručená konvergencia
- ak konverguje, tak rýchlejšie ako lineárne, konrétne \(m=\frac{1+\sqrt{5}}{2}\approx 1.618\) (pre definíciu \(m\) viď prednáška)
Regula falsi
Zatiaľ čo sekantová metóda využíva dva posledné kroky k zisteniu nového bodu, regula falsi vyberá body tak, aby koreň ostal ohraničený. Implementácia v čase 52:20-59:35. Pre záujemcov samozrejme platí možnosť preskočiť video a naimplementovať si metódu sám.
Vlastnosti metódy
- metóda konverguje stále
- pomalšia konvergencia než sekantová metóda, no stále superlineárna (\(m>1\))
Newtonova metóda
Newtonova metóda sa využíva hlavne v prípadoch, kedy je možné rýchlo spočítať deriváciu funkcie. Predpokladajme teda, že funkcia \(f\) má deriváciu. Najprv zvolíme počiatočný odhad koreňa \(x_0\) a postupujeme ďalej podľa vzťahu
\begin{equation} x_{k+1}=x_k - \frac{f(x_k)}{f’(x_k)}. \end{equation}
Bod \(x_{k+1}\) je vlastne priesečník tečny v bode \((x_k,f(x_k))\) s osou \(x\). Graficky sa dá metóda popísať nasledovne. Bodom \((x_0,f(x_0))\) vedieme tečnu ku grafu funkcie \(f\). Jej priesečník s osou \(x\) označím \(x_1\). Následne vediem tečnu bodom \((x_1,f(x_1))\) a priesečník s osou \(x\) označím označím ako \(x_2\) atď. Implementácia v čase 59:35-1:10:50.
Vlastnosti metódy
- nemusí stále konvergovať
- kvadratická metóda, konverguje rýchlo hlavne blízko koreňa
Pre záujemcov
- Vysvetlenie Mullerovej metódy a odpovedajúci skript
- Video vysvetľujúce teóriu a implementáciu Newton-Raphsonovej metódy pre sústavy nelineárnych rovníc
Domáca úloha
Tento týždeň výnimočne posunutý deadline na piatok 9. Apríla 2021 23:59:59(namiesto stredy) kvôli sviatkom. Konzultácie a odovzdanie úlohy cez chat v MS Teams. Zadanie dostanete ako obvykle takisto v MS Teams.
Comments