Graeffe metode

I matematik, Graeffe metode eller Dandelin-Graeffe metoden er en algoritme til at finde alle rødderne af et polynomium. Den blev udviklet uafhængigt af Germinal Pierre Dandelin i 1826 og Karl Heinrich Gräffe i 1837. Lobachevsky i 1834 også opdaget den vigtigste idé om metoden. Fremgangsmåden adskiller rødder et polynomium ved kvadrering dem gentagne gange. Denne udligning af rødderne sker implicit, dvs. kun arbejder på koefficienterne i polynomiet. Endelig Viète formler anvendes for at tilnærme rødderne.

Dandelin-Graeffe iteration

Lad s være en n'te grad polynomium.

Derefter

Lad være polynomiet som har kvadraterne som sine rødder,

Derfor ved binomial identitet

Polynomiet q kan nu beregnes ved algebraiske operationer på koefficienterne i polynomiet p alene. Skrive

og

så koefficienterne er relateret ved

Graeffe observeret, at man opnår et forenklet algebraisk udtryk for q ved adskillelse p i sine ulige og lige dele,

Dette udtryk indebærer udligning af to polynomier af kun halvdelen graden, og anvendes derfor i de fleste implementeringer af fremgangsmåden.

Iteration denne procedure flere gange adskiller rødder med hensyn til deres størrelser. Gentagelse k gange giver et polynomium

af grad n med rødder. Hvis størrelserne af rødderne af oprindelige polynomium blev adskilt af nogle faktor, dvs. ,, derefter rødderne af k'te iterate er adskilt af en hurtigt voksende faktor.

Klassisk Graeffe metode

Næste anvendes forbindelserne Beliggenhed

Hvis rødderne er tilstrækkeligt adskilt, siger med en faktor ,, så itererede beføjelser rødderne er adskilt af faktoren, som hurtigt bliver meget store.

Koefficienterne i den gentog polynomium kan derefter estimeres ved deres førende sigt,

indebærer

Endelig logaritmer anvendes med henblik på at finde de absolutte værdier af rødderne af den oprindelige polynomium. Disse størrelser alene er allerede nyttigt at generere meningsfulde udgangspunkter for andre root-finding metoder.

For også at få vinklen af ​​disse rødder, er blevet foreslået flere forskellige metoder, de mest simple ene er til successivt at beregne kvadratroden af ​​en rod af, m spænder fra k til 1, og afprøvning hvilken af ​​de to tegn varianter er en roden af. Før du fortsætter til rødderne af, kan det være nødvendigt at numerisk forbedre nøjagtigheden af ​​de grundlæggende tilnærmelser til, for eksempel ved Newtons metode.

Graeffe metode virker bedst for polynomier med enkle reelle rødder, selv om det kan tilpasses til polynomier med komplekse rødder og koefficienter, og rødder med højere mangfoldighed. For eksempel er det blevet observeret, at for en rod med multiplicitet d, fraktionerne

for. Dette gør det muligt at estimere mangfoldighed strukturen af ​​sættet af rødder.

Fra et numerisk synspunkt denne metode er problematisk, da koefficienterne for de itererede polynomier span meget hurtigt mange størrelsesordener, hvilket indebærer alvorlige numeriske fejl. Et sekund, men mindre bekymring er, at mange forskellige polynomier fører til de samme Graeffe gentager.

Tangential Graeffe metode

Denne metode erstatter de numre ved trunkeret power række grad 1, også kendt som dobbelt tal. Symbolsk, opnås dette ved at indføre en "algebraisk uendelig" med den definerende egenskab. Så polynomiet har rødder, med beføjelser

Dermed værdien af ​​opnås let som fraktion

Denne form for beregning med infinitesimals er let at implementere analog med beregningen med komplekse tal. Hvis man antager komplekse koordinater eller en indledende skift af nogle tilfældigt valgt komplekst tal, så alle rødder i polynomiet vil være tydelig og dermed erstattes med iteration.

Renormalisering

Ethvert polynomium kan skaleres i domæne og rækkevidde, således at i den resulterende polynomium den første og den sidste koefficient har størrelse én. Hvis størrelsen af ​​de indre koefficienter er afgrænset af M, så er størrelsen af ​​de indre koefficienter efter et stadium i Graeffe iteration er afgrænset af. Efter k stadier man får den bundne til de indre koefficienter.

For at overvinde den grænse udgøres af væksten i de beføjelser, Malajovich-Zubelli foreslå at repræsentere koefficienter og mellemliggende resultater i KTH etape af algoritmen ved en skaleret polær form

hvor er et komplekst antal enhed længde og er et positivt reelt. Fraspaltning effekten i eksponenten reducerer den absolutte værdi af C til den tilsvarende dyadic rod. Da dette bevarer størrelsen af ​​de første koefficienter, blev denne proces ved navn renormalisering.

Multiplikation af to tal af denne type er ligetil, mens tilsætningen udføres efter faktoriseringen, hvor vælges som det største af de to tal, der er ,. Dermed

Koefficienterne for den afsluttende fase k af Graeffe iteration, for nogle rimelig stor værdi k, er repræsenteret ved parvis ,. Ved at identificere hjørnerne af konvekse hylster af punktet sæt kan man bestemme multipliciteterne af rødderne af polynomiet. Ved at kombinere denne renormalisering med tangenten iteration man kan udtrække direkte fra koefficienterne i hjørnerne af konvolutten rødderne af oprindelige polynomium.

  0   0

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