Roteringsalgoritmer - Root-finding algorithms

I matematikk og databehandling , en rot-finne-algoritmen er en algoritme for å finne nullpunkter , også kalt "røtter", av kontinuerlige funksjoner . En null av en funksjon f , fra de reelle tallene til reelle tall eller fra de komplekse tallene til de komplekse tallene, er et tall x slik at f ( x ) = 0 . Som generelt nullene i en funksjon, kan ikke beregnes nøyaktig og heller ikke til uttrykk i lukket form , rot finn på algoritmer tilveiebringer tilnærmelser til nullpunkter, uttrykt enten som flyttall eller som små tette intervaller , eller disker for komplekse røtter (et intervall eller disk utgang tilsvarer en omtrentlig utgang sammen med en feilbundet).

Å løse en ligning f ( x ) = g ( x ) er det samme som å finne røttene til funksjonen h ( x ) = f ( x ) - g ( x ) . Dermed tillater rotfinneralgoritmer å løse enhver ligning definert av kontinuerlige funksjoner. De fleste rotfunn-algoritmer garanterer imidlertid ikke at de vil finne alle røttene; spesielt hvis en slik algoritme ikke finner noen rot, betyr det ikke at det ikke finnes noen rot.

De fleste numeriske rotfunnsmetoder bruker iterasjon , og produserer en tallrekke som forhåpentligvis konvergerer mot roten som en grense . De krever en eller flere innledende gjetninger av roten som startverdier, deretter gir hver iterasjon av algoritmen en etterfølgende mer nøyaktig tilnærming til roten. Siden iterasjonen må stoppes på et tidspunkt gir disse metodene en tilnærming til roten, ikke en eksakt løsning. Mange metoder beregner etterfølgende verdier ved å evaluere en tilleggsfunksjon på de foregående verdiene. Grensen er dermed et fast punkt for hjelpefunksjonen, som er valgt for å ha røttene til den opprinnelige ligningen som faste punkter, og for å konvergere raskt til disse faste punktene.

Oppførselen til generelle rotfinneralgoritmer studeres i numerisk analyse . For polynomer tilhører imidlertid rotfunnstudie generelt datamaskinalgebra , siden algebraiske egenskaper til polynomer er grunnleggende for de mest effektive algoritmene. Effektiviteten til en algoritme kan avhenge dramatisk av egenskapene til de gitte funksjonene. For eksempel bruker mange algoritmer derivatet av inngangsfunksjonen, mens andre jobber med hver kontinuerlige funksjon . Generelt er det ikke garantert at numeriske algoritmer finner alle røttene til en funksjon, så det å ikke finne en rot viser ikke at det ikke er noen rot. For polynomer er det imidlertid spesifikke algoritmer som bruker algebraiske egenskaper for å bekrefte at ingen rot savnes, og lokalisere røttene i separate intervaller (eller disker for komplekse røtter) som er små nok til å sikre konvergens av numeriske metoder (vanligvis Newtons metode ) til den unike roten så plassert.

Bracketing -metoder

Bracketing -metoder bestemmer suksessivt mindre intervaller (parenteser) som inneholder en rot. Når intervallet er lite nok, er det funnet en rot. De bruker vanligvis mellomverdisetningen , som hevder at hvis en kontinuerlig funksjon har verdier av motsatte tegn ved endepunktene i et intervall, så har funksjonen minst en rot i intervallet. Derfor krever de å starte med et intervall slik at funksjonen tar motsatte tegn ved sluttpunktene av intervallet. Når det gjelder polynomer er det imidlertid andre metoder ( Descartes tegnregel , Budans teorem og Sturms teorem ) for å få informasjon om antall røtter i et intervall. De fører til effektive algoritmer for isolering av virkelige roter av polynomer, som sikrer at alle virkelige røtter blir funnet med en garantert nøyaktighet.

Delingsmetode

Den enkleste rotfinneralgoritmen er biseksjonsmetoden . La f være en kontinuerlig funksjon , som man kjenner et intervall [ a , b ] slik at f ( a ) og f ( b ) har motsatte tegn (en parentes). La c = ( a + b )/2 være midten av intervallet (midtpunktet eller punktet som halverer intervallet). Da har enten f ( a ) og f ( c ) , eller f ( c ) og f ( b ) motsatte tegn, og man har delt på to størrelsen på intervallet. Selv om halveringsmetoden er robust, får den bare en bit nøyaktighet for hver iterasjon. Andre metoder, under passende forhold, kan få nøyaktighet raskere.

Falsk posisjon ( regula falsi )

Den falske stilling metode , også kalt Regula falsi metoden, er lik den halverings metode, men istedenfor å anvende bisection søk s midten av intervallet den bruker x -intercept av linjen som forbinder de plottede funksjonsverdiene ved endepunktene av intervallet , det er

${\ displaystyle c = {\ frac {af (b) -bf (a)} {f (b) -f (a)}}.}$

Falsk posisjon ligner secant -metoden , bortsett fra at den i stedet for å beholde de to siste punktene, sørger for å beholde ett poeng på hver side av roten. Den falske posisjonsmetoden kan være raskere enn halveringsmetoden og vil aldri avvike som sekantmetoden; Imidlertid kan det mislykkes i å konvergere i noen naive implementeringer på grunn av avrundingsfeil som kan føre til feil tegn for f ( c ) ; vanligvis kan dette skje hvis variasjonshastigheten til f er stor i nærheten av roten.

ITP -metode

Den ITP metode er den eneste kjente metode til braketten roten med de samme worst case garantier for Halveringsmetode og samtidig sikre en superlinear konvergens til roten av glatte funksjoner som sekant-metoden. Det er også den eneste kjente metoden som garantert overgår biseksjonsmetoden i gjennomsnitt for enhver kontinuerlig fordeling på plassering av roten (se ITP -metode#analyse ). Det gjør det ved å holde styr på både bracketing -intervallet og minmax -intervallet der et hvilket som helst punkt deri konvergerer like raskt som biseksjonsmetoden. Konstruksjonen av det forespurte punktet c følger tre trinn: interpolasjon (ligner regula falsi), trunkering (justering av regula falsi lik Regula falsi § Forbedringer i regula falsi ) og deretter projeksjon på minmax -intervallet. Kombinasjonen av disse trinnene gir en samtidig minmax optimal metode med garantier som ligner på interpolasjonsbaserte metoder for glatte funksjoner, og vil i praksis utkonkurrere både biseksjonsmetoden og interpolasjonsbaserte metoder under både glatte og ikke-glatte funksjoner.

Interpolasjon

Mange rotfunnprosesser fungerer ved interpolasjon . Dette består i å bruke de siste beregnede omtrentlige verdiene til roten for å tilnærme funksjonen med et polynom av lav grad, som tar de samme verdiene ved disse omtrentlige røttene. Deretter beregnes roten til polynomet og brukes som en ny omtrentlig verdi av roten til funksjonen, og prosessen itereres.

To verdier tillater interpolering av en funksjon med et polynom av grad én (det vil si tilnærming til grafen for funksjonen med en linje). Dette er grunnlaget for secant -metoden . Tre verdier definerer en kvadratisk funksjon , som tilnærmer grafen til funksjonen med en parabel . Dette er Mullers metode .

Regula falsi er også en interpolasjonsmetode, som skiller seg fra secant -metoden ved å bruke, for interpolering med en linje, to punkter som ikke nødvendigvis er de to siste beregnede punktene.

Iterative metoder

Selv om alle rotfunnalgoritmer fortsetter med iterasjon , bruker en iterativ rotfunningsmetode vanligvis en spesifikk type iterasjon, som består av å definere en tilleggsfunksjon, som brukes på de siste beregnede tilnærmingene til en rot for å få en ny tilnærming. Iterasjonen stopper når et fast punkt ( opp til ønsket presisjon) for tilleggsfunksjonen er nådd, det vil si når den nye beregnede verdien er tilstrekkelig nær de foregående.

Newtons metode (og lignende derivatbaserte metoder)

Newtons metode forutsetter at funksjonen f har et kontinuerlig derivat . Newtons metode konvergerer kanskje ikke hvis den startes for langt unna en rot. Imidlertid, når den konvergerer, er den raskere enn halveringsmetoden, og er vanligvis kvadratisk. Newtons metode er også viktig fordi den lett generaliserer til høyere dimensjonale problemer. Newton-lignende metoder med høyere konvergensordre er husmannens metoder . Den første etter Newtons metode er Halleys metode med kubisk rekkefølge av konvergens.

Sikker metode

Ved å erstatte derivatet i Newtons metode med en begrenset forskjell , får vi secant -metoden . Denne metoden krever ikke beregning (eller eksistens) av et derivat, men prisen er langsommere konvergens (rekkefølgen er omtrent 1,6 ( gylden snitt )). En generalisering av sekantmetoden i høyere dimensjoner er Broydens metode .

Steffensens metode

Hvis vi bruker en polynom tilpasning for å fjerne den kvadratiske delen av den endelige forskjellen som brukes i Secant -metoden, slik at den tilnærmer derivatet bedre, får vi Steffensens metode , som har kvadratisk konvergens, og hvis oppførsel (både god og dårlig) i hovedsak er det samme som Newtons metode, men krever ikke et derivat.

Invers interpolasjon

Utseendet til komplekse verdier i interpoleringsmetoder kan unngås ved å interpolere inversen av f , noe som resulterer i invers kvadratisk interpolasjonsmetode . Igjen er konvergens asymptotisk raskere enn sekantmetoden, men invers kvadratisk interpolasjon oppfører seg ofte dårlig når iterater ikke er nær roten.

Kombinasjoner av metoder

Brents metode

Brents metode er en kombinasjon av biseksjonsmetoden, sekantmetoden og invers kvadratisk interpolasjon . Ved hver iterasjon avgjør Brents metode hvilken metode av disse tre som sannsynligvis vil gjøre best, og fortsetter ved å gjøre et trinn i henhold til denne metoden. Dette gir en robust og rask metode, som derfor har stor popularitet.

Ridders metode

Ridders metode er en hybrid metode som bruker funksjonens verdi ved midtpunktet av intervallet for å utføre en eksponentiell interpolasjon til roten. Dette gir en rask konvergens med en garantert konvergens på maksimalt det dobbelte av antall iterasjoner som halveringsmetoden.

Røtter av polynomer

Å finne røtter til polynom er et mangeårig problem som har vært gjenstand for mye forskning gjennom historien. Et bevis på dette er at frem til 1800 -tallet betydde algebra i hovedsak teori om polynomligninger .

Å finne roten til et lineært polynom (grad en) er enkelt og trenger bare en divisjon. For kvadratiske polynomer (grad to) gir den kvadratiske formelen en løsning, men den numeriske evalueringen kan kreve en viss omhu for å sikre numerisk stabilitet . For grader tre og fire er det løsninger i lukket form når det gjelder radikaler , som generelt ikke er praktiske for numerisk evaluering, som for kompliserte og involverer beregning av flere n røtter hvis beregning ikke er enklere enn den direkte beregningen av røtter til polynomet (for eksempel uttrykk for de virkelige røttene til et kubisk polynom kan involvere ikke-virkelige kuberøtter ). For polynomer av grad fem eller høyere hevder Abel - Ruffini -setningen at det generelt ikke er noe radikalt uttrykk for røttene.

Så, bortsett fra svært lave grader, består rotfunn av polynomer av å finne tilnærminger til røttene. Ved grunnleggende teorem om algebra vet man at et polynom av grad n har høyst n reelle eller komplekse røtter, og dette tallet er nådd for nesten alle polynomer.

Det følger at problemet med rotfunn for polynomer kan deles i tre forskjellige delproblemer;

• Finne en rot
• Finner alle røtter
• Å finne røtter i en bestemt region av det komplekse planet , vanligvis de virkelige røttene eller de virkelige røttene i et gitt intervall (for eksempel når røtter representerer en fysisk mengde, er det bare de virkelige positive som er interessante).

For å finne en rot, fungerer Newtons metode og andre generelle iterative metoder generelt godt.

For å finne alle røttene, er den eldste metoden, når en rot r er funnet, å dele polynomet med x - r , og starte iterativt på nytt søket etter en rot av kvotientpolynomet. Bortsett fra lave grader, fungerer dette imidlertid ikke bra på grunn av den numeriske ustabiliteten : Wilkinsons polynom viser at en veldig liten modifikasjon av en koeffisient kan endre dramatisk ikke bare verdien av røttene, men også deres natur (reell eller kompleks). Selv med en god tilnærming, når man vurderer et polynom ved en omtrentlig rot, kan man også få et resultat som er langt til å være nær null. For eksempel, hvis et polynom av grad 20 (graden av Wilkinsons polynom) har en rot nær 10, kan derivatet av polynomet ved roten være av størrelsesorden dette innebærer at en feil på verdien av roten kan produsere en verdi av polynomet på omtrentlig rot som er i størrelsesorden${\ displaystyle 10^{20};}$${\ displaystyle 10^{-10}}$${\ displaystyle 10^{10}.}$

For å unngå disse problemene er det blitt utarbeidet metoder som beregner alle røtter samtidig, til ønsket nøyaktighet. For tiden er den mest effektive metoden Aberth -metoden . En gratis implementering er tilgjengelig under navnet MPSolve . Dette er en referanseimplementering, som rutinemessig kan finne røttene til polynomer med en grad større enn 1000, med mer enn 1000 betydelige desimalsifre.

Metodene for å beregne alle røtter kan brukes til å beregne virkelige røtter. Imidlertid kan det være vanskelig å avgjøre om en rot med en liten imaginær del er ekte eller ikke. Ettersom tallet på de virkelige røttene i gjennomsnitt er logaritmen til graden, er det sløsing med datamaskinressurser å beregne de ikke-virkelige røttene når man er interessert i virkelige røtter.

Den eldste metoden for å beregne antall virkelige røtter, og antall røtter i et intervall, stammer fra Sturms teorem , men metodene som er basert på Descartes tegnregel og dens utvidelser - Budans og Vincents teorier - er generelt mer effektive. For å finne rot, fortsett alle ved å redusere størrelsen på intervallene der røtter søkes til du får intervaller som inneholder null eller en rot. Da kan intervallene som inneholder en rot reduseres ytterligere for å få en kvadratisk konvergens av Newtons metode til de isolerte røttene. De viktigste datamaskinalgebrasystemene ( Maple , Mathematica , SageMath , PARI/GP ) har hver en variant av denne metoden som standardalgoritme for de virkelige røttene til et polynom.

En annen metodeklasse er basert på å konvertere problemet med å finne polynomrøtter til problemet med å finne egenverdier av ledsagermatrisen til polynomet. I prinsippet kan man bruke hvilken som helst egenverdi -algoritme for å finne røttene til polynomet. Av effektivitetshensyn foretrekker man imidlertid metoder som bruker strukturen til matrisen, det vil si kan implementeres i matrisefri form. Blant disse metodene er kraftmetoden , hvis anvendelse på transponering av ledsagermatrisen er den klassiske Bernoullis metode for å finne roten til største modul. Den omvendte kraftmetoden med skift, som først finner noen minste rot, er det som driver den komplekse ( cpoly ) varianten av Jenkins - Traub -algoritmen og gir den numerisk stabilitet. I tillegg er den ufølsom for flere røtter og har rask konvergens med orden (hvor er det gylne snittet ) selv i nærvær av grupperte røtter. Denne raske konvergensen kommer med en pris på tre polynomevalueringer per trinn, noe som resulterer i en rest på O (| f ( x ) | ^{2+3 φ} ) , det er en langsommere konvergens enn med tre trinn i Newtons metode. ${\ displaystyle 1+ \ varphi \ ca 2.6}$${\ displaystyle \ varphi}$

Finne en rot

Den mest brukte metoden for å beregne en rot er Newtons metode , som består av iterasjoner av beregningen av

${\ displaystyle x_ {n+1} = x_ {n}-{\ frac {f (x_ {n})} {f '(x_ {n})}}},}$

ved å starte fra en velvalgt verdi ${\ displaystyle x_ {0}.}$

Hvis f er et polynom, er beregningen raskere ved bruk av Horners metode eller evaluering med forbehandling for beregning av polynomet og dets derivat i hver iterasjon.

Konvergensen er generelt kvadratisk , den kan konvergere mye sakte eller til og med ikke konvergere i det hele tatt. Spesielt hvis polynomet ikke har noen reell rot, og er ekte, kan ikke Newtons metode konvergere. Men hvis polynomet har en ekte rot, som er større enn den større virkelige roten til derivatet, konvergerer Newtons metode kvadratisk til denne største roten hvis den er større enn denne større roten (det er enkle måter å beregne en øvre grense for røtter, se Egenskaper for polynomrøtter ). Dette er utgangspunktet for Horner -metoden for å beregne røttene. ${\ displaystyle x_ {0}}$${\ displaystyle x_ {0}}$

Når en rot r er funnet, kan man bruke euklidisk divisjon for å fjerne faktor x - r fra polynomet. Å beregne en rot av den resulterende kvoten, og gjenta prosessen gir i prinsippet en måte å beregne alle røtter på. Imidlertid er denne iterative ordningen numerisk ustabil; tilnærmingsfeilene akkumuleres under de påfølgende faktoriseringene, slik at de siste røttene bestemmes med et polynom som avviker mye fra en faktor i det opprinnelige polynomet. For å redusere denne feilen kan man, for hver rot som blir funnet, starte Newtons metode på nytt med det opprinnelige polynomet, og denne omtrentlige roten som startverdi.

Det er imidlertid ingen garanti for at dette vil tillate å finne alle røtter. Faktisk er problemet med å finne røttene til et polynom fra koeffisientene generelt svært dårlig betinget . Dette illustreres av Wilkinsons polynom : røttene til dette polynomet av grad 20 er de 20 første positive heltallene; endring av den siste biten i 32-biters representasjon av en av dens koeffisient (lik -210) gir et polynom med bare 10 virkelige røtter og 10 komplekse røtter med imaginære deler større enn 0,6.

Nært knyttet til Newtons metode er Halleys metode og Laguerres metode . Begge bruker polynomet og dets to første avledninger for en iterativ prosess som har en kubisk konvergens . Ved å kombinere to påfølgende trinn av disse metodene til en enkelt test, får man en konvergenshastighet på 9, på bekostning av 6 polynomevalueringer (med Horner -regelen). På den annen side gir kombinasjon av tre trinn med Newtons -metoden en konvergenshastighet på 8 på bekostning av samme antall polynomevalueringer. Dette gir en liten fordel til disse metodene (mindre tydelig for Laguerres metode, ettersom en kvadratrot må beregnes i hvert trinn).

Når du bruker disse metodene på polynomer med reelle koeffisienter og virkelige utgangspunkt, holder Newtons og Halleys metode seg inne i den reelle tallinjen. Man må velge komplekse utgangspunkt for å finne komplekse røtter. I kontrast vil Laguerre -metoden med kvadratrot i evalueringen forlate den virkelige aksen av seg selv.

Finne røtter i par

Hvis det gitte polynomet bare har reelle koeffisienter, kan det være lurt å unngå beregninger med komplekse tall. I den forbindelse må man finne kvadratiske faktorer for par med konjugerte komplekse røtter. Anvendelsen av den flerdimensjonale Newtons metode på denne oppgaven resulterer i Bairstows metode .

Den virkelige varianten av Jenkins - Traub -algoritmen er en forbedring av denne metoden.

Finner alle røtter på en gang

Den enkle Durand - Kerner og den litt mer kompliserte Aberth -metoden finner samtidig alle røttene ved hjelp av bare enkel kompleks tallregning. Akselererte algoritmer for flerpunktsevaluering og interpolasjon som ligner på den raske Fourier-transformasjonen, kan hjelpe dem med å øke hastigheten på store grader av polynomet. Det anbefales å velge et asymmetrisk, men jevnt fordelt sett med startpunkter. Implementeringen av denne metoden i den gratis programvaren MPSolve er en referanse for effektiviteten og nøyaktigheten.

En annen metode med denne stilen er Dandelin - Gräffe -metoden (noen ganger også tilskrevet Lobachevsky ), som bruker polynomiske transformasjoner for gjentatte ganger og implisitt å kvadrere røttene. Dette forstørrer variasjoner i røttene sterkt. Ved å bruke Viètes formler , får man enkle tilnærminger til røttemodulen, og med litt mer innsats, for røttene selv.

Utelukkelse og inneslutningsmetoder

Det finnes flere raske tester som forteller om et segment av den virkelige linjen eller et område av det komplekse planet ikke inneholder røtter. Ved å begrense røttemodulen og rekursivt dele den opprinnelige regionen som er angitt med disse grensene, kan man isolere små områder som kan inneholde røtter og deretter bruke andre metoder for å lokalisere dem nøyaktig.

Alle disse metodene innebærer å finne koeffisientene til skiftede og skalerte versjoner av polynomet. For store grader blir FFT -baserte akselererte metoder levedyktige.

For ekte røtter, se neste avsnitt.

Den Lehmer-Schur-algoritmen benytter den Schur-Cohn test for sirkler; en variant, Wilfs globale biseksjonsalgoritme bruker en viklingstallberegning for rektangulære områder i det komplekse planet.

Den splitting sirkel Metoden benytter FFT-baserte polynom-transformasjoner for å finne stor grad faktorer svarende til klynger av røtter. Presisjonen til faktoriseringen maksimeres ved bruk av en iterasjon av Newton-typen. Denne metoden er nyttig for å finne røttene til polynomer av høy grad til vilkårlig presisjon; den har nesten optimal kompleksitet i denne innstillingen.

Real-root isolasjon

Å finne de virkelige røttene til et polynom med virkelige koeffisienter er et problem som har fått mye oppmerksomhet siden begynnelsen av 1800 -tallet, og fremdeles er et aktivt forskningsområde. De fleste rotfinneralgoritmer kan finne noen virkelige røtter, men kan ikke bekrefte å ha funnet alle røttene. Metoder for å finne alle komplekse røtter, for eksempel Aberth -metoden, kan gi de virkelige røttene. På grunn av den numeriske ustabiliteten til polynomer (se Wilkinsons polynom ), kan de imidlertid trenge vilkårlig presisjon-aritmetikk for å bestemme hvilke røtter som er virkelige. Videre beregner de alle komplekse røtter når bare få er virkelige.

Det følger av at standardmetoden for å beregne virkelige røtter er å beregne første usammenhengende intervaller, kalt isolasjonsintervaller , slik at hver enkelt inneholder nøyaktig en ekte rot, og sammen inneholder de alle røttene. Denne beregningen kalles real-root isolasjon . Etter å ha et isolerende intervall, kan man bruke raske numeriske metoder, for eksempel Newtons metode for å forbedre presisjonen til resultatet.

Den eldste komplette algoritmen for real-root-isolasjon kommer fra Sturms teorem . Det ser imidlertid ut til å være mye mindre effektivt enn metodene som er basert på Descartes ’tegnregel og Vincents teorem . Disse metodene deler seg inn i to hovedklasser, den ene bruker fortsatte fraksjoner og den andre bruker biseksjon. Begge metoden har blitt dramatisk forbedret siden begynnelsen av det 21. århundre. Med disse forbedringene når de en beregningskompleksitet som ligner den for de beste algoritmene for å beregne alle røttene (selv når alle røttene er virkelige).

Disse algoritmene er implementert og er tilgjengelige i Mathematica (fortsatt brøkmetode) og lønn (biseksjonmetode). Begge implementeringene kan rutinemessig finne de virkelige røttene til polynomer med en grad høyere enn 1000.

Finne flere røtter av polynomer

De fleste rotfinneralgoritmer oppfører seg dårlig når det er flere røtter eller veldig nære røtter. For polynomer hvis koeffisienter er nøyaktig gitt som heltall eller rasjonelle tall , er det imidlertid en effektiv metode for å faktorisere dem til faktorer som bare har enkle røtter, og hvis koeffisienter også er nøyaktig gitt. Denne metoden, kalt kvadratfri faktorisering , er basert på de flere røttene til et polynom som er røttene til den største fellesdeleren til polynomet og dets derivat.

Kvadratfri faktorisering av et polynom p er en faktorisering der hver er enten 1 eller et polynom uten flere røtter, og to forskjellige ikke har noen felles rot. ${\ displaystyle p = p_ {1} p_ {2}^{2} \ cdots p_ {k}^{k}}$${\ displaystyle p_ {i}}$${\ displaystyle p_ {i}}$

En effektiv metode for å beregne denne faktoriseringen er Yuns algoritme .

Se også

• Liste over algoritmer for å finne rot
• Broyden's method  -Quasi-Newton root-finding method for the multivariable case
• Kryptografisk sikker pseudotilfeldig tallgenerator
• GNU Vitenskapelig bibliotek
• Graeffes metode  - Algoritme for å finne polynomiske røtter
• Lills metode  - Grafisk metode for de virkelige røttene til et polynom
• MPSolve  - Programvare for å tilnærme røttene til et polynom med vilkårlig høy presisjon
• Multiplikasjon (matematikk)  - Antall ganger et objekt må telles for å gjøre sann til en generell formel
• n rot -algoritme
• System for polynomligninger  -Rotfunnalgoritmer for vanlige røtter til flere multivariate polynomer
• Kantorovich -setning  - Innledende forhold som sikrer konvergensen av Newtons metode

Referanser