2.1 Bisection Algorithm
A bisection algoritmus egy egyszerű módszer egydimenziós függvények gyökeinek megtalálására. A cél egy olyan \(x_0\in\) gyök megtalálása, hogy \(f(x_0)=0\). Az algoritmus egy nagy intervallummal kezd, amelyről tudjuk, hogy tartalmazza \(x_0\), majd fokozatosan csökkenti az intervallum méretét, amíg be nem zárja a gyökeret. Az algoritmus elméleti alapja a köztesérték-tétel, amely szerint ha egy folytonos \(f\) függvény \(f(a)\) és \(f(b)\) értékeket vesz fel az \(\) intervallum végpontjaiban, akkor \(f\) minden \(f(a)\) és \(f(b)\) közötti értéket fel kell vennie valahol az intervallumban. Tehát ha \(f(a) < \gamma < f(b)\), akkor létezik olyan \(c\in\), hogy \(f(c)=\gamma\).
Ezen információk felhasználásával bemutathatjuk a felező algoritmust. Először is ellenőriznünk kell, hogy \(\text{sign}(f(a)) \ne \text{sign}(f(b))\). Ellenkező esetben az intervallum nem tartalmazza a gyökeret, és esetleg ki kell szélesíteni. Ekkor folytathatjuk:
-
Legyen \(c = \frac{a + b}{2}\).
-
Ha \(f(c) = 0\), álljunk meg, és adjuk vissza \(c\).
-
Ha \(\text{jel}(f(a))\ne\text{jel}(f(c))\), akkor állítsuk be \(b\leftarrow c\). Máskülönben ha \(\text{sign}(f(b))\ne\text{sign}(f(c))\), akkor állítsuk \(a\balkanyar c\).
-
Menjünk az elejére és ismételjük a konvergenciáig (lásd alább).
Az \(n\) iteráció után a gyökeret záró intervallum mérete \(2^{-n}(b-a)\) lesz.
A kettéosztási algoritmus hasznos, fogalmilag egyszerű és könnyen megvalósítható. Különösen nincs szükség semmilyen különleges információra az \(f\) függvényről, kivéve, hogy ki tudjuk értékelni az intervallum különböző pontjain. Hátránya, hogy csak egy dimenzióban hasznos, és a konvergenciája lineáris, ami az általunk tárgyalt algoritmusok leglassabb konvergenciája (erről később).
A bisection algoritmus problémába ütközhet olyan helyzetekben, amikor az \(f\) függvény nem viselkedik jól. A bisection algoritmus ideális helyzete valahogy így néz ki.
Ideális helyzet a bisection algoritmushoz.
Itt \(f(a)\) és \(f(b)\) ellentétes előjelűek, és a gyök egyértelműen \(a\) és \(b\) között van.
A lenti forgatókönyvben az algoritmus nem indul el, mert \(f(a)>0\) és \(f(b)>0\).
Az \(f\) derivátuma a gyökérnél \(0\).
A következő forgatókönyvben \(a\) és \(b\) között két gyök van, amellett, hogy \(f(a)>0\) és \(f(b)>0\). A kiindulási intervallum hosszát csökkenteni kellene ahhoz, hogy bármelyik gyököt megtaláljuk.
Két gyök az intervallumon belül.
Az alábbi forgatókönyv szerint az algoritmus elindul, mert \(f(a)\) és \(f(b)\) ellentétes előjelű, de nincs gyök.
Az intervallum tartalmaz egy aszimptotát, de nincs gyökér.
A felező algoritmus konvergenciája úgy határozható meg, hogy vagy \(|b-a|<\varepsilon\) van valamilyen kis \(\varepsilon\) esetén, vagy \(|f(b)-f(a)|<\varepsilon\). Az, hogy melyik kritériumot alkalmazzuk, az adott alkalmazástól és attól függ, hogy milyen tűréseket kell alkalmazni.
2.1.1 Példa: \(F(x)\) és egy \(p\in (0, 1)\) számot, az \(F\) egy olyan \(x\) szám, hogy \(F(x) = p\). A kettéosztási algoritmus használható az \(x\) kvantilis megtalálására egy adott \(p\) esetén az \(g(x) = F(x) – p\) függvény definiálásával és az \(x\) azon értékének megoldásával, amely \(g(x) = 0\).
Egy másik módja ennek az, hogy megfordítjuk a CDF-et az \(x = F^{-1}(p)\) kiszámításához. Tehát a kettéosztási algoritmus használható függvények invertálására ezekben a helyzetekben.