2.1 Bissektionsalgoritme
Bissektionsalgoritmen er en simpel metode til at finde rødderne af endimensionale funktioner. Målet er at finde en rod \(x_0\in\), således at \(f(x_0)=0\). Algoritmen starter med et stort interval, som man ved indeholder \(x_0\), og reducerer derefter successivt størrelsen af intervallet, indtil det sætter roden i parentes. Det teoretiske grundlag for algoritmen er teoremet om mellemværdien, som siger, at hvis en kontinuert funktion \(f\) tager værdierne \(f(a)\) og \(f(b)\) i endepunkterne af intervallet \(\), så må \(f\) tage alle værdier mellem \(f(a)\) og \(f(b)\) et sted i intervallet. Så hvis \(f(a) < \gamma < f(b)\), så findes der en \(c\in\), således at \(f(c)=\gamma\).
Ved hjælp af disse oplysninger kan vi præsentere halveringsalgoritmen. Først skal vi kontrollere, at \(\text{sign}(f(a)) \ne \text{sign}(f(b))\). I modsat fald indeholder intervallet ikke roden og skal muligvis udvides. Så kan vi fortsætte:
-
Lad \(c = \frac{a + b}{2}\).
-
Hvis \(f(c) = 0\), skal du stoppe og returnere \(c\).
-
Hvis \(\text{tegn}(f(a))\ne\text{tegn}(f(c))\), så sæt \(b\leftremsen c\). Ellers hvis \(\text{sign}(f(b))\ne\text{sign}(f(c))\), så sæt \(a\leftarrow c\).
-
Gå til begyndelsen og gentag, indtil der er konvergens (se nedenfor).
Efter \(n\) gentagelser vil størrelsen af det interval, der omslutter roden, være \(2^{-n}(b-a)\).
Den halve algoritme er nyttig, begrebsmæssigt enkel og er let at implementere. Især har man ikke brug for nogen særlige oplysninger om funktionen \(f\), bortset fra evnen til at evaluere den i forskellige punkter i intervallet. Ulemperne er, at den kun er nyttig i én dimension, og at dens konvergens er lineær, hvilket er den langsomste konvergenshastighed for algoritmer, som vi vil diskutere (mere om det senere).
Den halve algoritme kan løbe ind i problemer i situationer, hvor funktionen \(f\) ikke har en god opførsel. Den ideelle situation for bisektionalgoritmen ser nogenlunde sådan ud.
Den ideelle opsætning for bisektionalgoritmen.
Her er \(f(a)\) og \(f(b)\) af modsat fortegn, og roden ligger tydeligt mellem \(a\) og \(b\).
I nedenstående scenarie vil algoritmen ikke starte, fordi \(f(a)>0\) og \(f(b)>0\).
Derivativ af \(f\) ved roden er \(0\).
I dette næste scenarie er der to rødder mellem \(a\) og \(b\), ud over at der er \(f(a)>0\) og \(f(b)>0\). Man ville være nødt til at reducere længden af startintervallet for at finde en af de to rødder.
To rødder inden for intervallet.
I nedenstående scenarie vil algoritmen starte, fordi \(f(a)\) og \(f(b)\) har modsat fortegn, men der er ingen rod.
Intervallet indeholder en asymptote, men ingen rod.
Konvergens af bispealgoritmen kan bestemmes ved enten at have \(|b-a|<\varepsilon\) for en lille \(\varepsilon\) eller ved at have \(|f(b)-f(a)|<\varepsilon\). Hvilket kriterium man anvender, afhænger af den specifikke anvendelse og af, hvilke former for tolerancer der kræves.
2.1.1 Eksempel: Kvantiler
Givet en kumulativ fordelingsfunktion \(F(x)\) og et tal \(p\i (0, 1)\), er et kvantil af \(F\) et tal \(x\), der er sådan, at \(F(x) = p\). Bisektionsalgoritmen kan bruges til at finde en kvantil \(x\) for en given \(p\) ved at definere funktionen \(g(x) = F(x) – p\) og løse for den værdi af \(x\), der opnår \(g(x) = 0\).
En anden måde at sige det på er, at vi inverterer CDF’en for at beregne \(x = F^{-1}(p)\). Så bisektionalgoritmen kan bruges til at invertere funktioner i disse situationer.