Numerieke Wiskunde VIII:
Nulpuntsbepaling met Bisectie

Een veel voorkomend wiskundig probleem is het berekenen van een snijpunt in de grafieken van twee functies. Je zou dat kunnen oplossen door de grafieken van die functies te tekenen en de coördinaten van het snijpunt uit de tekening af te lezen. De nauwkeurigheid van zo'n aanpak is echter beperkt; het is eigenlijk alleen bruikbaar als eerste schatting.

Er moet dus gerekend worden. Een algemeen toegepaste werkwijze is: de functievoorschriften van elkaar aftrekken en dan het punt berekenen waar de grafiek de X-as snijdt (dus waar Y = 0).
Een veel gebruikte methode heet Bisectie.

• Er worden twee items besproken:
  1. De Bisectie-methode voor het vinden van een nulpunt.
  2. De aanpak in de praktijk.
   
• De naam 'Bisecie' betekent zoveel als 'Tweedeling'. Bij deze methode wordt het interval waar het nulpunt wordt gezocht bij elke iteratiestap in twee gelijke delen verdeeld. Bisectie wordt ook wel 'Interval-halvering' genoemd.
• Nodig en voldoende is dat de functie continu monotoon stijgend of dalend is op een interval rond het nulpunt. In dat geval geeft deze methode altijd een oplossing. We zeggen dan dat de methode convergeert.
• Teken altijd eerst een grafiek van de functie. Dat geeft al een idee van de oplossing.
• Stel dat we zoeken naar F(x) = 0. Uit de grafiek kun je een schatting maken van x.
• Kies een waarde x0 < x en een waarde x1 > x. Het product F(x0) · F(x1) is dan kleiner dan nul.
• Bereken x2 = (x0 + x1) / 2. Bereken F(x2).
• Er zijn nu drie mogelijkheden:
  
  1. F(x2) = 0. Als dit gebeurt is x2 de exacte oplossing.
  2. F(x2)*F(x0) < 0 : Vervang x1 door x2. Bereken een nieuwe waarde van x2 en F(x2) en herhaal de beoordeling.
  3. F(x2)*F(x0) > 0 : Vervang x0 door x2. Bereken een nieuwe waarde van x2 en F(x2) en herhaal de beoordeling.
• Mogelijkheid 1 zal niet vaak voorkomen. Vrijwel altijd zal het iteratieproces worden afgebroken doordat de absolute waarde van het verschil tussen x0 en x1 kleiner is dan een grenswaarde ε (epsilon).
  In formule: |x0 - x1| < ε. Dit wordt het convergentie-criterium genoemd.
• De waarde van ε bepaalt de nauwkeurigheid van de oplossing. Uit de definitie van ε volgt dat het verschil tussen de benadering met Bisectie en de 'echte' oplossing maximaal ½·ε is.

Een uitgewerkt voorbeeld
Vraag: wat is het snijpunt, x ≠ 0, van f(x) = 0.5·x2 en g(x) = 2·x ?

Uitwerking: In het snijpunt is f(x) = g(x), daaruit volgt:
f(x) - g(x) = 0. Dat geeft de formule:
F(x) = 0.5·x2 - 2·x = 0.

• We tekenen eerst de grafiek van F(x), zie hiernaast.
• Als startwaarden voor het iteratieproces nemen we x0 = 3.5 en x1 = 4.8.
• Onderstaande tabel toont het verloop van het iteratieproces:

• De tabel begint met stap 0. Dit is de initialisatie van het iteratieproces.
• Het convergentiecriterium wordt bereikt in stap 11, dat is dus de twaalfde berekening. Daar is x2 gelijk aan 3.999877930. In vergelijking met de exacte oplossing (x = 4; zie de opmerking aan het einde van deze bladzijde) is dat netjes.
• In de tabel is te zien dat het iteratieproces veel stappen nodig heeft om het convergentiecriterium te bereiken. Daar zou je uit af kunnen leiden dat Bisectie een traag convergerend proces is. In vergelijking met andere methodes voor het bepalen van een nulpunt is dat —in zijn algemeenheid— waar, maar de keuze van de startwaarden x0 en x1 heeft een grote invloed. Als je in het voorbeeld x0 = 3 en x1 = 5 zou kiezen, wordt x2 in de eerste stap gelijk aan 4, de exacte oplossing.
   
• Natuurlijk is er ook een applicatie om zelf met deze techniek aan de slag te gaan. Klik op de knop hiernaast.
   
• De code van de applicatie kun je downloaden om zelf aan door te ontwikkelen.
• Als je verder wilt werken aan de applicatie, download je de .zip-file en pak je hem uit. Je hebt dan meteen een werkend voorbeeld.

Downloaden:
 
Druk op de knop:  File: voorb658.zip, 4294 bytes.

Opmerking:
 
De analytische oplossing van F(x) = 0 gaat als volgt:
0.5·x2 - 2·x = x (0.5·x - 2) = 0 ⇒
x = 0 ∨ (0.5·x - 2) = 0 ⇔
x = 0 ∨ 0.5·x = 2 ⇒
x = 0 ∨ x = 4
Dit is ook te zien in de grafiek.

Opmerking:
 
Deze methode convergeert het snelste als de startwaarden symmetrisch t.o.v. het geschatte nulpunt worden gekozen. Dus als je verwacht dat x = 5.7, kies je bijvoorbeeld x0 = 5.1 en x1 = 6.3.
Het oplossen van een nulpunt in de buurt van nul kan problemen opleveren als je de startwaarden niet symmetrisch kiest ten opzichte van x = 0, bijvoorbeeld x0 = -0.1 en x1 = 0.15. Bij de hierboven uitgewerkte formule heb je met deze startwaarden aan 1000 stappen niet genoeg voor het vinden van een oplossing met ε = 0.1. Dat komt doordat na ca. 75 stappen de waarden van x0 en x1 niet meer veranderen doordat er niet genoeg decimalen zijn. De waarden blijven steken bij x0 = -0.1 en x1 ≈ 0.0333. Dan is |x0 - x1| > ε en wordt convergentie nooit bereikt. Maar kies je x0 = -0.1 en x1= +0.1, dan convergeert het proces al in stap 0!