Halveringsmethode
De halveringsmethode of bisectiemethode is een algoritme voor het oplossen van vergelijkingen. Het principe is heel eenvoudig en de methode is makkelijk op een computer te implementeren. De methode vertoont overeenkomsten met binair zoeken binnen een geordende rij gegevens.
Inhoud |
[bewerk] Beschrijving van de methode
Eerst wordt een interval bepaald waarin een oplossing van de vergelijking ligt, noem dat [a, b], dat is stap 1.
Stap 2 houdt in dat wordt bepaald of de oplossing zich links of rechts van het midden van het interval bevindt. Bij de op 0 herleide vergelijking f(x) = 0 komt dat neer op het bepalen van f((a + b)/2).
Zoek dan verder in het deelinterval waar de oplossing in ligt.
Bij elke iteratie wordt de lengte van het interval waarin verder gezocht wordt de helft kleiner. De methode convergeert dus gegarandeerd. Een belangrijk nadeel is dat deze convergentie ook langzaam is.
[bewerk] Voorbeeld
Worteltrekken is geen elementaire operatie zoals optellen of vermenigvuldigen. In de praktijk moeten wortels altijd worden benaderd met een iteratief algoritme of een reeks. We benaderen als voorbeeld 21 / 3 met de halveringsmethode. (Opmerking: voor het benaderen van wortels zijn er efficiëntere methoden dan bisectie.) We vertalen het berekenen van de derdemachtswortel in het oplossen van de vergelijking x3 − 2 = 0. Duidelijk is dat 1 < x < 2, dus als eerste benadering nemen we x1 = 1.5. Aangezien 1.53 = 3.375, ligt x dus in de linkerhelft: 1 < x < 1.5. We herhalen nu de procedure, en nemen als tweede benadering x2 = (1 + 1.5) / 2 = 1.25. Nu is 1.253 = 1.953125, dus ligt x in de rechterhelft: 1.25 < x < 1.5. Zo gaan we door: x3 = (1.25 + 1.5) / 2 = 1.375. Dan blijkt: 1.25 < x < 1.375. Dus nemen we x4 = (1.25 + 1.375) / 2 = 1.3125. Omdat voor de gezochte waarde geldt dat x ≈ 1.25992105 zullen we voorlopig steeds xi in de linkerhelft van de komende intervallen aantreffen:
- x5 = (1.25 + 1.3125) / 2 = 1.28125
- x6 = (1.25 + 1.28125) / 2 = 1.265625
- x7 = (1.25 + 1.265625) / 2 = 1.2578125
Nu duiken we onder x, wat we door berekening van de derde macht vaststellen, dus
- x8 = (1.2578125 + 1.265625) / 2 = 1.26171875.
Nu zitten we er weer boven:
- x9 = (1.2578125 + 1.26171875) / 2 = 1.259765625.
En zo gaan we door tot we de gewenste nauwkeurigheid bereikt hebben.
[bewerk] Toepasbaarheid
Deze methode is eigenlijk alleen zinvol wanneer de methode van Newton of Regula Falsi niet te gebruiken zijn, bijvoorbeeld als er veel oplossingen dicht bij elkaar liggen, wat die methoden kan ontregelen, of wanneer de startwaarden te ver van de oplossing af liggen. Als de gewenste nauwkeurigheid niet al te groot is, kan de bisectiemethode ook sneller zijn omdat per stap minder rekenwerk nodig is.
Uit het bovenstaande voorbeeld leren we dat we de methode kunnen toepassen voor het oplossen van een vergelijking van de vorm f(x) = 0, als we een interval [a, b] hebben waarin de/één oplossing ligt en alle functiewaarden links van de oplossing kleiner óf groter zjn dan alle functiewaarden rechts van de oplossing. Als f continu is op [a, b] en f(a) < 0 en f(b) > 0 (of andersom) is er volgens de tussenwaardestelling gegarandeerd ten minste één nulpunt.
[bewerk] Het algoritme in pseudocode
Stel eerst de te bereiken nauwkeurigheid δ vast.
Herleid de op te lossen vergelijking op 0 en zoek een interval [a, b] zo dat f(a) en (b) niet hetzelfde teken hebben.
Stap
- Het midden van dit interval m is het gemiddelde van a en b: m = (a + b)/2. Bereken f(m).
- Heeft f(m) hetzelfde teken als f(a), zoek dan verder in [m, b] (vervang a door m), zoek anders verder in [a, m] (vervang b door m)
Herhaal vanaf Stap tot de gewenste nauwkeurigheid bereikt is, dat wil zeggen b - a < δ. Een mogelijke implementatie in pseudo-code ziet er dan zo uit:
const d = ....
var a, b, m;
a, b := A, B;
ZOLANG (b - a) > d
m <- (a + b / 2
ALS f(m)*f(a) < 0
DAN b <- m
ANDERS a <- m
HERHAAL
schatting := (a + b) / 2
