Avancerad statistisk beräkning

2.1 Bisektionsalgoritmen

Bisektionsalgoritmen är en enkel metod för att hitta rötterna till endimensionella funktioner. Målet är att hitta en rot \(x_0\in\) så att \(f(x_0)=0\). Algoritmen börjar med ett stort intervall, som man vet innehåller \(x_0\), och minskar sedan successivt storleken på intervallet tills det är en parentes av roten. Det teoretiska underlaget för algoritmen är mellanvärdessatsen som säger att om en kontinuerlig funktion \(f\) tar värdena \(f(a)\) och \(f(b)\) vid ändpunkterna av intervallet \(\), så måste \(f\) ta alla värden mellan \(f(a)\) och \(f(b)\) någonstans i intervallet. Så om \(f(a) < \gamma < f(b)\), så finns det en \(c\in\) så att \(f(c)=\gamma\).

Med hjälp av denna information kan vi presentera bisektionsalgoritmen. Först måste vi kontrollera att \(\text{sign}(f(a)) \ne \text{sign}(f(b))\). I annat fall innehåller intervallet inte roten och kan behöva breddas. Då kan vi fortsätta:

1. Låt \(c = \frac{a + b}{2}\).

2. Om \(f(c) = 0\), stoppa och återge \(c\).

3. Om \(\text{sign}(f(a))\ne\text{sign}(f(c))\), sätt då \(b\leftarrow c\). Annars om \(\text{sign}(f(b))\ne\text{sign}(f(c))\), sätt då \(a\leftarrow c\).

4. Gå till början och upprepa tills konvergens (se nedan).

Efter \(n\) iterationer blir storleken på det intervall som omger roten \(2^{-n}(b-a)\).

Bisection-algoritmen är användbar, begreppsmässigt enkel och är lätt att genomföra. I synnerhet behöver du inte någon speciell information om funktionen \(f\) förutom förmågan att utvärdera den i olika punkter i intervallet. Nackdelarna är att den bara är användbar i en dimension och att dess konvergens är linjär, vilket är den långsammaste konvergenshastigheten för algoritmer som vi kommer att diskutera (mer om det senare).

Bisection-algoritmen kan stöta på problem i situationer där funktionen \(f\) inte beter sig väl. Den ideala situationen för bisektionsalgoritmen ser ungefär så här ut.

Här är \(f(a)\) och \(f(b)\) av motsatt tecken och roten ligger tydligt mellan \(a\) och \(b\).

I scenariot nedan kommer algoritmen inte att starta eftersom \(f(a)>0\) och \(f(b)>0\).

I nästa scenario finns det två rötter mellan \(a\) och \(b\), förutom att det finns \(f(a)>0\) och \(f(b)>0\). Man skulle behöva minska längden på startintervallet för att hitta någon av rötterna.

I scenariot nedan startar algoritmen eftersom \(f(a)\) och \(f(b)\) har motsatt tecken, men det finns ingen rot.

Konvergens för bisektringsalgoritmen kan bestämmas genom att antingen ha \(|b-a|<\varepsilon\) för en viss liten \(\varepsilon\) eller att ha \(|f(b)-f(a)|<\varepsilon\). Vilket kriterium du använder beror på den specifika tillämpningen och på vilka typer av toleranser som krävs.