Newtons metode (Newton–Raphson): Definition og brug til at finde nulpunkter
Newtons metode giver mulighed for at finde de reelle nulpunkter af en funktion. Denne algoritme kaldes undertiden Newton-Raphson-metoden, opkaldt efter Sir Isaac Newton og Joseph Raphson. Metoden bruges bredt i matematik, fysik, ingeniørarbejde og numerisk analyse, fordi den ofte konvergerer meget hurtigt, når startgættet er tilstrækkeligt godt.
Metoden anvender funktionens afledte værdi til at finde dens rødder. Der skal foretages et indledende "gæt" på nulpunktets placering. Ud fra denne værdi beregnes et nyt gæt ved hjælp af denne formel:
Her er xn det første gæt og xn+1 det næste gæt. Funktionen f (hvis nulpunkt søges løst) har den afledte funktion f'.
Hvordan metoden virker (grafisk og intuitivt)
Ved gentagne gange at anvende denne formel på de genererede gæt (dvs. ved at sætte værdien af xn til formlens output og foretage en ny beregning), vil værdien af gættene nærme sig funktionens nulpunkt, forudsat at visse betingelser er opfyldt.
Newtons metode kan forklares grafisk ved at se på tangentlinjernes skæringspunkter med x-aksen. Først beregnes en linje, der tangerer f ved xn. Dernæst findes skæringspunktet mellem denne tangentlinje og x-aksen. Endelig registreres x-positionen for dette skæringspunkt som det næste gæt, xn+1. Matematiske set er tangentens ligning ved xn y = f(xn) + f'(xn)(x - xn); sættes y = 0 og løses for x giver det Newton-iterationens formel.
Konvergens og forudsætninger
- Lokal quadratisk konvergens: Hvis f er to gange differentiérbar i et interval omkring en rod α, og f(α) = 0 samt f'(α) ≠ 0, så konvergerer Newtons metode kvadratiske (dvs. fejlene omtrent kvadreres ved hver iteration), når startgættet ligger tilstrækkeligt tæt på α.
- Krævet afledt: Metoden kræver at f'(xn) ikke er nul, ellers opstår division med nul. Hvis f' er meget lille, kan iterationen blive ustabil eller convergere langsomt.
- Ikke global garanti: Newtons metode garanterer ikke at finde en rod, hvis startgættet er langt fra den ønskede rod — den kan divergere, fange i en cyklus eller konvergere til en anden rod end forventet.
- Multiplicitet: Hvis roden har multiplicitet m > 1, er konvergens typisk kun lineær i stedet for kvadratisk. En modificeret iteration x_{n+1} = x_n - m f(x_n)/f'(x_n) kan genoprette hurtigere konvergens, hvis m kendes.
Fejl, begrænsninger og rettelser
- Hvis f'(xn) = 0 (eller næsten 0), kan metoden bryde sammen. I praksis kan man undgå strengt nul ved at afbryde eller bruge en alternativ strategi (fx sikkerhedsstep).
- Når funktionen har inflektionspunkter nær roden eller meget ikke-lineær adfærd, kan tangenttilnærmelsen føre væk fra roden.
- For funktioner uden let beregnelig afledt kan man bruge numeriske approksimationer (f(x+h)-f(x))/h eller alternative metoder som secantmetoden, som ikke kræver f'.
- Varianter som dæmpet Newton (dvs. x_{n+1} = x_n - λ f(x_n)/f'(x_n) med 0<λ≤1) kan forbedre robustheden ved at tage mindre skridt.
Praktiske stopkriterier
- |f(xn)| < tol (funktionen er tæt på nul)
- |xn+1 − xn| < tol (ændringen mellem to på hinanden følgende gæt er lille)
- maksimalt antal iterationer nået (for at undgå uendelig løkke)
- f'(xn) tæt på 0 (anomalitetsdetektion)
Eksempel: Approksimere √2
Tag f(x) = x² − 2. Så er f'(x) = 2x, og Newton-iteration reducerer til x_{n+1} = (x_n + 2/x_n)/2 (kaldet Herons metode for kvadratrødder).
Vælg startgæt x₀ = 1.5:
- x₁ = (1.5 + 2/1.5)/2 ≈ 1.4166667
- x₂ ≈ (1.4166667 + 2/1.4166667)/2 ≈ 1.4142157
- x₃ ≈ 1.41421356 (god præcision efter få iterationer)
Pseudokode (simpel implementering)
Givet f, f', x0, tol, maxit for n = 0 to maxit-1: fx = f(x0) dfx = f'(x0) if |dfx| < eps: stop med fejlmelding (afledt for lille) x1 = x0 - fx/dfx if |x1 - x0| < tol eller |f(x1)| < tol: return x1 x0 = x1 return sidste x0 (maks antal iterationer nået)
Varianter og alternativer
- Secantmetoden: Kræver ikke f', bruger to startgæt, har superlineær konvergens (≈1.618) men ikke kvadratisk.
- Quasi-Newton metoder: Anvendes i flere variable optimering (BFGS mv.), estimerer Jacobian/afledt numerisk.
- Halley's metode: Bruger også anden afledte og kan have kubisk konvergens under gode betingelser.
- Komplekse rødder: Newtons metode kan også anvendes i komplekse tal for at finde komplekse nulpunkter, hvilket ofte giver interessante fraktalmønstre (Newton-fraktaler).
Newtons metode er et meget effektivt værktøj til at finde nulpunkter, når afledte kan beregnes og startgættet er rimeligt tæt på løsningen. I praksis kombineres den ofte med andre metoder eller med sikkerhedsstrategier for at sikre robusthed.
Funktionen (blå) bruges til at beregne hældningen af en tangentlinje (rød) ved xn .
Problemer med Newtons metode
Newtons metode kan finde en løsning hurtigt, hvis gætværdien begynder tilstrækkeligt tæt på den ønskede rod. Men når den indledende gætteværdi ikke er tæt på, og afhængigt af funktionen, kan Newtons metode finde svaret langsomt eller slet ikke finde svaret.
Relaterede sider
- Kantorovich-sætningen (udsagn om konvergens af Newtons metode, fundet af Leonid Kantorovich)
Spørgsmål og svar
Spørgsmål: Hvad er Newtons metode?
A: Newtons metode er en algoritme til at finde de reelle nuller af en funktion. Den bruger funktionens afledte værdi til at beregne dens rødder og kræver et indledende gæt for nulpunktets placering.
Spørgsmål: Hvem har udviklet denne metode?
Svar: Metoden blev udviklet af Sir Isaac Newton og Joseph Raphson, og derfor kaldes den nogle gange Newton-Raphson-metoden.
Spørgsmål: Hvordan virker denne algoritme?
Svar: Denne algoritme fungerer ved gentagne gange at anvende en formel, som tager udgangspunkt i et indledende gæt (xn) og beregner et nyt gæt (xn+1). Ved at gentage denne proces nærmer gætterierne sig et nulpunkt for funktionen.
Spørgsmål: Hvad kræves der for at anvende denne algoritme?
Svar: For at bruge denne algoritme skal man have en indledende "gætværdi" for nulpunktets placering samt viden om den afledte af den givne funktion.
Spørgsmål: Hvordan kan vi forklare Newtons metode grafisk?
Svar: Vi kan forklare Newtons metode grafisk ved at se på skæringspunkterne mellem tangentlinjerne og x-aksen. Først beregnes en linje, der tangerer f ved xn. Dernæst finder vi skæringspunktet mellem denne tangentlinje og x-aksen og registrerer dens x-position som vores næste gæt - xn+1.
Spørgsmål: Er der nogen begrænsning, når man bruger Newtons metode?
A: Ja, hvis din oprindelige gætværdi er for langt væk fra den faktiske rod, kan det tage længere tid eller endog mislykkes at konvergere mod roden på grund af svingninger omkring den eller divergens væk fra den.
