Advanced Statistical Computing

2.1 Bisekční algoritmus

Bisekční algoritmus je jednoduchá metoda pro hledání kořenů jednorozměrných funkcí. Cílem je najít kořen \(x_0\in\) takový, že \(f(x_0)=0\). Algoritmus začíná s velkým intervalem, o kterém je známo, že obsahuje \(x_0\), a pak postupně zmenšuje velikost intervalu, dokud nenajde kořen. Teoretickým základem algoritmu je věta o mezilehlé hodnotě, která říká, že pokud spojitá funkce \(f\) nabývá hodnot \(f(a)\) a \(f(b)\) v koncových bodech intervalu \(\), pak \(f\) musí nabývat všech hodnot mezi \(f(a)\) a \(f(b)\) někde v intervalu. Jestliže tedy \(f(a) < \gamma < f(b)\), pak existuje \(c\in\) takové, že \(f(c)=\gamma\).

Pomocí této informace můžeme představit algoritmus bisekce. Nejprve musíme ověřit, že \(\text{sign}(f(a)) \ne \text{sign}(f(b))\). V opačném případě interval neobsahuje kořen a může být nutné jej rozšířit. Pak můžeme pokračovat:

1. Nechť \(c = \frac{a + b}{2}\).

2. Jestliže \(f(c) = 0\), zastavíme a vrátíme \(c\).

3. Jestliže \(\text{znak}(f(a))\ne\text{znak}(f(c))\), pak nastavíme \(b\leftarrow c\). Jinak pokud \(\text{sign}(f(b))\ne\text{sign}(f(c))\), pak nastavte \(a\leftarrow c\).

4. Přejděte na začátek a opakujte až do konvergence (viz níže).

Po \(n\) iteracích bude velikost intervalu ohraničujícího kořen \(2^{-n}(b-a)\).

Algoritmus bisekce je užitečný, koncepčně jednoduchý a snadno se implementuje. Zejména nepotřebujete žádné zvláštní informace o funkci \(f\) kromě schopnosti vyhodnotit ji v různých bodech intervalu. Jeho nevýhodou je, že je užitečný pouze v jedné dimenzi a jeho konvergence je lineární, což je nejpomalejší rychlost konvergence algoritmů, o kterých budeme hovořit (více o tom později).

Bisekční algoritmus se může dostat do problémů v situacích, kdy se funkce \(f\) nechová dobře. Ideální situace pro bisekční algoritmus vypadá asi takto.

Zde jsou \(f(a)\) a \(f(b)\) opačných znamének a kořen je jednoznačně mezi \(a\) a \(b\).

V následujícím případě se algoritmus nespustí, protože \(f(a)>0\) a \(f(b)>0\).

V tomto dalším případě jsou mezi \(a\) a \(b\) dva kořeny, kromě toho, že máme \(f(a)>0\) a \(f(b)>0\). Abychom našli některý z kořenů, museli bychom zkrátit délku počátečního intervalu.

V níže uvedeném případě se algoritmus spustí, protože \(f(a)\) a \(f(b)\) mají opačné znaménko, ale neexistuje žádný kořen.

Konvergenci bisekčního algoritmu lze určit tak, že buď máme \(|b-a|<\varepsilon\) pro nějaké malé \(\varepsilon\), nebo máme \(|f(b)-f(a)|<\varepsilon\). Které kritérium použijete, závisí na konkrétní aplikaci a na tom, jaké tolerance jsou požadovány.

.