Bairstow metode

I numerisk analyse, Bairstow metode er en effektiv algoritme til at finde rødderne af en reel polynomium af vilkårlig grad. Algoritmen først dukkede op i tillægget til 1920 bogen "Applied Aerodynamik" af Leonard Bairstow. Algoritmen finder rødderne i komplekse konjugerede par kun bruger ægte aritmetik.

Se root-finding algoritme til andre algoritmer.

Beskrivelse af fremgangsmåden

Bairstow tilgang er at anvende Newtons metode til at justere koefficienterne U og V i kvadratisk indtil dens rødder er også rødderne af polynomiet blive løst. Rødderne af den kvadratiske kan derefter bestemmes og polynomiet kan divideres med den kvadratiske at fjerne disse rødder. Denne proces gentages derefter, indtil polynomium bliver kvadratisk eller lineær, og alle rødder er blevet bestemt.

Long opdeling af polynomiet, der skal løses

af udbytter en kvotient og en rest, således at

En anden opdeling af efter udføres til opnåelse af en kvotient og resten med

De variabler, og er funktioner af og. De kan findes rekursivt som følger.

Den kvadratiske jævnt opdeler polynomium, når

Værdier, og hvor der dette sker kan opdages ved at udvælge startværdier og iteration Newtons metode i to dimensioner

indtil konvergens forekommer. Denne metode til at finde nullerne af polynomier kan således let implementeres med et programmeringssprog eller endda et regneark.

Eksempel

Opgaven er at bestemme et par rødder af polynomiet

Som første kvadratisk polynomium man kan vælge den normaliserede polynomium dannet af de førende tre koefficienter af f,

Iterationen producerer derefter tabellen

Efter otte gentagelser fremgangsmåden producerede en kvadratisk faktor, der indeholder rødderne -1/3 og -3 inden den repræsenterede præcision. Skridtet længde fra den fjerde iteration på demonstrerer superlinear hastighed på konvergens.

Præstation

Bairstow algoritme arver den lokale kvadratisk konvergens mellem Newtons metode, undtagen i tilfælde af kvadratiske faktorer af mangfoldighed højere end 1, da konvergens til denne faktor er lineær. En særlig form for ustabilitet observeres, når polynomiet har ulige grad og kun én reel rod. Kvadratiske faktorer, der har en lille værdi på dette reelle rod tendens til at afvige til uendeligt.

Billederne repræsenterer par. Punkter i den øverste halvdel flyet t & gt; 0 svarer til en lineær faktor med rødder, der er. Punkter i den nederste halvdel flyet t & lt; 0 svarer til kvadratiske faktorer med rødder, der er ,, så i almindelighed. Point er farvet i henhold til det sidste punkt i Bairstow iteration, sorte punkter indikerer divergerende adfærd.

Det første billede er en demonstration af det indre reelle rod sagen. Den anden viser, at man kan rette op på divergerende adfærd ved at indføre en ekstra virkelige rod, på bekostning af at bremse hastigheden af ​​konvergens. Man kan også i tilfælde af ulige grad polynomier først finde en reel rod hjælp af Newtons metode og / eller et interval skrumper fremgangsmåde, således at der efter deflation et bedre-behaved selv-graders polynomium rester. Det tredje billede svarer til ovenstående eksempel.

  0   0
Forrige artikel CIA i Brasilien

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha