2.1 Bisectie-algoritme
Het bisectie-algoritme is een eenvoudige methode om de wortels van eendimensionale functies te vinden. Het doel is een wortel (x_0)zo te vinden dat f(x_0)=0). Het algoritme begint met een groot interval, waarvan bekend is dat het \(x_0) bevat, en verkleint dan achtereenvolgens het interval tot het de wortel omvat. De theoretische onderbouwing van het algoritme is de tussenwaardetheorema, die stelt dat als een continue functie \(f)\) waarden \(f(a)\) en \(f(b)\) aan de eindpunten van het interval \(\) heeft, dan moet \(f)\) alle waarden tussen \(f(a)\) en \(f(b)\) ergens in het interval hebben. Dus als f(a) < \gamma < f(b)\), dan bestaat er een \(cin) zo dat f(c)= \gamma).
Met deze informatie kunnen we het bissectricie-algoritme presenteren. Eerst moeten we controleren of \(f(a)) \een \tekst{teken}(f(b))\). Anders bevat het interval de wortel niet en moet het misschien verbreed worden. Dan kunnen we verdergaan:
-
Laat \(c = \frac{a + b}{2}\).
-
Als \(f(c) = 0), stop dan en geef \(c) terug.
-
Als \(\tekst{teken}(f(a))\neen \tekst{teken}(f(c))\), dan stel je \(\linkse pijl c\) in. Anders, als \(\tekst{teken}(f(b))\next{teken}(f(c))\), dan stel \(a\linksepijlc\) in.
-
Ga naar het begin en herhaal tot convergentie (zie hieronder).
Na \(n) iteraties is de grootte van het interval dat de wortel omhult \(2^{-n}(b-a)\).
Het bissectie-algoritme is nuttig, conceptueel eenvoudig, en is eenvoudig te implementeren. In het bijzonder is er geen speciale informatie nodig over de functie f, behalve de mogelijkheid om deze op verschillende punten in het interval te evalueren. De nadelen zijn dat het alleen bruikbaar is in één dimensie en dat de convergentie lineair is, wat de langzaamste convergentiesnelheid is voor algoritmen die we zullen bespreken (daarover later meer).
Het bisectie-algoritme kan in de problemen komen in situaties waarin de functie f zich niet goed gedraagt. De ideale situatie voor het bisectie-algoritme ziet er ongeveer zo uit.
Ideale opstelling voor bisectie-algoritme.
Hier zijn \(f(a)\) en \(f(b)\) van tegengestelde tekens en de wortel ligt duidelijk tussen \(a)\) en \(b)\) in.
In het onderstaande scenario zal het algoritme niet starten omdat \(f(a)>0) en \(f(b)>0).
Derivatief van \(f)bij de wortel is \(0)
.
In dit volgende scenario zijn er twee wortels tussen \(a) en \(b), naast \(f(a)>0) en \(f(b)>0). Men zou de lengte van het begininterval moeten verkorten om een van beide wortels te vinden.
Twee wortels binnen het interval.
In het onderstaande scenario start het algoritme omdat \(f(a)\) en \(f(b)\) tegengesteld van teken zijn, maar er is geen wortel.
Interval bevat een asymptoot maar geen wortel.
Convergentie van het bisectiealgoritme kan worden bepaald door ²(|b-a|<varepsilon) te hebben voor een kleine ²(\varepsilon) of door ²(|f(b)-f(a)|<varepsilon) te hebben. Welk criterium u gebruikt, hangt af van de specifieke toepassing en van de vereiste toleranties.
2.1.1 Voorbeeld: Kwantielen
Gegeven een cumulatieve verdelingsfunctie \(F(x)\) en een getal \(p(0, 1)\), is een kwantiel van \(F(x)\) een getal \(x)\) zo dat \(F(x) = p(x)\). Het bisectiealgoritme kan worden gebruikt om een kwantiel te vinden voor een gegeven kwantiel door de functie g(x) = F(x) – p(x) te definiëren en op te lossen voor de waarde van x die leidt tot g(x) = 0.
Een andere manier om dit te zeggen is dat we de CDF omkeren om te berekenen ^(x = F^{-1}(p)\). Dus het bisectie-algoritme kan worden gebruikt om functies in deze situaties te inverteren.