Methode van Bairstow

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

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[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]

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:

Berekening 1e stap

Berekening

De vergelijkingen zijn dus:

De determinant van de matrix is:

,

zodat


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
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[bewerken | brontekst bewerken]

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[bewerken | brontekst bewerken]