Halveringsmethode

algoritme voor het oplossen van vergelijkingen

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.

Beschrijving van de methodeBewerken

Eerst wordt een interval bepaald waarin een oplossing van de vergelijking ligt, noem dat   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   komt dat neer op het bepalen van  

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.

VoorbeeldBewerken

Worteltrekken is geen elementaire operatie zoals optellen of vermenigvuldigen. In de praktijk moeten wortels altijd worden benaderd met een iteratief algoritme of een reeks. Een voorbeeld toont de benadering van   met de halveringsmethode. Voor het benaderen van wortels zijn er efficiëntere methoden dan bisectie.

Het berekenen van de derdemachtswortel wordt vertaald in het oplossen van de vergelijking

 .

Duidelijk is dat  , dus een eerste benadering is

 .

Aangezien  , ligt   dus in de linkerhelft:  . De procedure wordt nu herhaald en als tweede benadering krijgt men

 .

Nu is  , dus ligt   in de rechterhelft:  . Zo gaat men door:

 .

Dan blijkt:  . Dus wordt

 .

Omdat voor de gezochte waarde geldt dat  , zal voorlopig steeds   in de linkerhelft van de komende intervallen liggen:

 
 
 

Nu duikt men onder  , wat door berekening van de derde macht is vast te stellen, dus

 .

Nu ligt de benadering er weer boven:

 .

En zo gaat men door tot de gewenste nauwkeurigheid bereikt is.

ToepasbaarheidBewerken

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  , als we een interval   hebben waarin de/één oplossing ligt en alle functiewaarden links van de oplossing kleiner óf groter zijn dan alle functiewaarden rechts van de oplossing. Als   continu is op   en   en   (of andersom) is er volgens de tussenwaardestelling gegarandeerd ten minste één nulpunt.

Het algoritme in pseudocodeBewerken

Stel eerst de te bereiken nauwkeurigheid   vast.

Herleid de op te lossen vergelijking tot  , en zoek een interval   zo, dat   en   tegengestelde tekens hebben.

Herhaal vervolgens de volgende stappen:

  • Bereken de functiewaarde  in het midden   van het interval
  • Vergelijk deze waarde met de functiewaarden in de eindpunten van het interval
  • Vervang het eindpunt waarin de functie hetzelfde teken heeft als   door  

Ga hiermee door tot de gewenste nauwkeurigheid bereikt is, dat wil zeggen totdat de lengte van het resulterende interval kleiner is dan  .

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

Zie ookBewerken