title: Methode van Bairstow
text: De methode van Bairstow is een numerieke methode om de nulpunten van een reële veelterm van willekeurige graad te vinden. De methode werd voor het eerst beschreven door Leonard Bairstow in de appendix van diens boek Applied Aerodynamics (1920), en is naar hem genoemd. Een reële veelterm heeft wortels die reëel zijn of anders voorkomen in paren van complex toegevoegde getallen. De methode zoekt naar kwadratische factoren, die ofwel reducibel zijn en twee reële wortels hebben, ofwel irreducibel zijn en twee complex toegevoegde wortels hebben. Op deze manier maakt de methode alleen gebruik van reële getallen. Een alternatief is de methode van Müller.
  
  Beschrijving van de methode
  Om de wortels van de veelterm
  
  te vinden zoekt deze methode de twee coëfficiënten  en  van de kwadratische veelterm
  
  waarvan de wortels ook wortels zijn van de veelterm . Dan kunnen enerzijds twee wortels bepaald worden en kan anderzijds de oorspronkelijke veelterm  in graad worden verlaagd door hem te delen door de kwadratische veelterm . Dit proces wordt herhaald tot een veelterm van graad 1 of 2 overblijft.
  
  Deling van  door  geeft als quotiënt
  
  en als rest
  ,
  
  zodat
  
  Het gaat er nu om waarden van  en  te vinden waarvoor . Daartoe wordt in een soortgelijke procedure als de methode van Newton-Raphson een verbetering  en  van  en  gezocht, waarvoor de rest bij deling door  gelijk is aan 0, of althans kleiner is dan .
  Dus:
  
  ,
  zodat
  
  Door de veelterm  een tweede keer te delen door  kan de uitdrukking voor de restterm vereenvoudigd worden:
  
  Omdat in de restterm  geen kwadratische term voorkomt, moet
  
  Daaruit volgen de twee lineaire vergelijkingen:
  
  In matrixvorm:
  
  Een verbeterde benadering wordt dus verkregen door de uitgangswaarden  en  te corrigeren met:
  
  De onbekenden  en  zijn functies van  en . Ze worden recursief bepaald via:
  
  Deze iteraties worden herhaald tot wanneer convergentie bereikt is. De methode kan op eenvoudige manier geprogrammeerd worden in de standaard programmeertalen.
  
  Voorbeeld
  Bepaal de wortels van de veelterm
  
  Neem als eerste kwadratische veelterm  een veelterm met als coëfficiënten de drie hoogste macht-coëfficiënten van , genormaliseerd op de hoogste graad, dus:
  ,
  zodat:
  
  De eerste stap geeft als betere benadering:
  
  De resultaten van de opeenvolgende iteraties staan in de volgende tabel. De daarin genoemde stapgrootte is gelijk aan:
  
  Voor de eerste stap is dus:
  
  De kolom "wortels" geeft de wortels van de kwadratische veelterm  in de vorm 
  . Omdat 
   en  
  geldt:
   en 
  
  {| class="wikitable" border="1"
  |+ Iteratiestappen van Bairstow
  ! Nr
  ! 
  ! 
  ! stapgrootte
  ! wortels
  |-
  | 0
  | 1,833333333333
  | −5,500000000000
  | 5,579008780071
  | −0,916666666667±2.517990821623
  |-
  | 1
  | 2,979026068546
  | −0,039896784438
  | 2,048558558641
  | −1,489513034273±1,502845921479
  |-
  | 2
  | 3,635306053091
  | 1,900693009946
  | 1,799922838287
  | −1,817653026545±1,184554563945
  |-
  | 3
  | 3,064938039761
  | 0,193530875538
  | 1,256481376254
  | −1,532469019881±1,467968126819
  |-
  | 4
  | 3,461834191232
  | 1,385679731101
  | 0,428931413521
  | −1,730917095616±1,269013105052
  |-
  | 5
  | 3,326244386565
  | 0,978742927192
  | 0,022431883898
  | −1,663122193282±1,336874153612
  |-
  | 6
  | 3,333340909351
  | 1,000022701147
  | 0,000023931927
  | −1,666670454676±1,333329555414
  |-
  | 7
  | 3,333333333340
  | 1,000000000020
  | 0,000000000021
  | −1,666666666670±1,333333333330
  |-
  | 8
  | 3,333333333333
  | 1,000000000000
  | 0,000000000000
  | −1,666666666667±1,333333333333
  |}
  
  Na acht iteraties wordt een kwadratische veelterm  gevonden met wortels −1/3 en −3, en dit binnen de gewenste nauwkeurigheid. Dit zijn dus ook oplossingen van de oorspronkelijke veelterm . De superlineaire snelheid van convergentie is merkbaar vanaf de vierde stap. Na deling van de oorspronkelijke veelterm  door de kwadratische veelterm
  
  vindt men als quotiënt een nieuwe veelterm:
  
  waarop de methode opnieuw kan worden toegepast.
  
  Zwakkere punten van de methode
  De methode van Bairstow erft de lokale kwadratische convergentiesnelheid van de Newton-Raphson methode, behalve indien wortels optreden met een multipliciteit groter dan 1. Dan daalt de snelheid tot lineair. Een tweede probleem kan optreden bij veeltermen met een oneven graad, die slechts één reële wortel hebben. Kwadratische factoren die in deze wortel een kleine functiewaarde hebben, hebben de neiging te divergeren naar oneindig. Deze neiging kan worden onderdrukt door in dat geval de veelterm uit te breiden met een extra reële wortel, waardoor het convergentiegedrag bevorderd wordt, zij het ten koste van de snelheid van convergentie.
  
  Externe links
   Bairstow's Algorithm on Mathworld
   Numerical Recipes in Fortran 77 Online
   Example polynomial root solver (deg(P)⇐10) using Bairstow's Method
   LinBairstowSolve, an open-source C++ implementation of the Lin-Bairstow method available as a method of the VTK library
  
  Numerieke wiskunde