Newtons metod: Hitta rötter snabbt med iterativ approximation

Vissa ekvationer har helt enkelt ingen snygg algebraisk lösning.

Du kan faktorisera och substituera hur mycket du vill, men vissa ekvationer har ingen sluten form. Till exempel har ett polynom av grad fem eller högre ingen allmän algebraisk lösning. Funktioner som blandar exponentialer med polynom, som e^x = 3x, hamnar i samma kategori. I dessa fall behöver du en annan metod.

Newtons metod är den metoden. Den hittar rötter numeriskt genom att göra allt smartare gissningar – var och en styrd av funktionskurvans tangent i den aktuella uppskattningspunkten.

I den här artikeln går jag igenom formeln bakom Newtons metod, hur den fungerar steg för steg, när den konvergerar och när den inte gör det – med konkreta exempel som får teorin att fastna.

Letar du efter fler matematikämnen du bör kunna som data scientist? Läs vårt blogginlägg Geometriska serier: formel, konvergens och exempel för att se hur det används inom finans, fysik och CS.

Vad är Newtons metod?

Newtons metod är en iterativ teknik för att hitta en funktions rötter. Rötterna är de indata där funktionen är lika med noll.

Du börjar processen med en startgissning. Sedan använder metoden funktionens geometri vid den punkten för att göra en bättre gissning. Du upprepar processen, och varje iteration för dig närmare den faktiska roten.

Det är hela idén. Du behöver bara en smart, upprepningsbar uppdateringsregel som konvergerar mot svaret.

Formeln för Newtons metod

Kärnan i Newtons metod är en enda uppdateringsregel som du tillämpar upprepade gånger tills du är tillräckligt nära roten.

Här är formeln:

Formel för Newtons metod

Varje iteration tar din aktuella uppskattning x_n och ger en bättre, x_{n+1}. Du fortsätter att uppdatera tills resultatet är tillräckligt nära noll.

Formeln har tre komponenter:

• x_n – din nuvarande uppskattning av roten

• f(x_n) – funktionens värde vid den uppskattningen

• f'(x_n) – funktionens derivata vid den uppskattningen, som anger tangentens lutning

Om f(x_n) är stort är du långt från roten. Om f'(x_n) är brant förändras funktionen snabbt, så du kan ta ett större steg. Kvoten f(x_n) / f'(x_n) talar om exakt hur långt du ska flytta – och du subtraherar den från din nuvarande gissning för att komma närmare.

Om f'(x_n) är noll eller nära noll fungerar formeln egentligen inte. Du skulle dividera med noll, vilket innebär att metoden inte kan ge en ny uppskattning. Jag går igenom detta mer i detalj i avsnittet om begränsningar.

Hur Newtons metod fungerar

Newtons metod följer samma fyra steg i varje iteration.

1. Välj en startgissning: Välj ett startvärde x_0 någonstans nära roten. Du behöver inte vara exakt – bara tillräckligt nära för att funktionen ska uppföra sig förutsägbart runt den punkten. Jag tar upp vad ”tillräckligt nära” betyder i avsnittet om konvergens.

2. Beräkna funktionsvärdet: Beräkna f(x_0). Det visar hur långt funktionen är från noll vid din aktuella uppskattning. Om f(x_0) = 0 är du klar – du har hittat roten.

3. Beräkna derivatan: Beräkna f'(x_0). Det ger dig funktionens lutning vid x_0, alltså tangentens lutning där.

4. Uppdatera uppskattningen: Tillämpa uppdateringsregeln enligt formeln från föregående avsnitt.

Och så är du klar!

Detta nya värde x_1 är där tangenten skär x-axeln. Geometriskt ritar du en rät linje som tangerar kurvan i x_0 och följer den ner till noll. Skärningspunkten är din nästa, bättre gissning.

Sedan upprepar du. Sätt in x_1 tillbaka i steg 2 till 4 för att få x_2, sedan x_3, och så vidare. Varje iteration ritar en ny tangent i den uppdaterade punkten och hittar var den skär x-axeln.

Processen stoppar när f(x_n) är tillräckligt nära noll – vanligtvis när det understiger en liten tröskel som du definierar i förväg.

Geometrisk tolkning av Newtons metod

Föreställ dig en kurva i ett diagram – det är din funktion f(x). Roten är där kurvan skär x-axeln. Du vet ännu inte var skärningen är, så du börjar med en gissning x_0 någonstans på x-axeln.

Vid varje steg plottar du punkten (x_0, f(x_0)) på kurvan, och ritar sedan tangenten i den punkten – en rät linje som tangerar kurvan där och följer dess lutning. Den tangenten är inte horisontell. Den är lutad, och om du följer den nedåt skär den x-axeln någonstans. Den skärningen är din nästa uppskattning, x_1.

Sedan upprepar du. Vid x_1 ritar du en ny tangent och hittar var den skär x-axeln. Det ger x_2. Varje tangent är en lokal linjär approximation av kurvan, och varje skärningspunkt hamnar närmare den verkliga roten.

Diagrammet nedan visar två iterationer av Newtons metod tillämpad på f(x) = x^2 - 2, med start i x_0 = 2.5:

Diagram över geometrisk tolkning

Detta fungerar eftersom en tangent är den bästa räta linje-approximationen av en kurva i en given punkt. Ju närmare du är roten, desto mer liknar tangenten själva kurvan – och desto mer exakt blir ditt nästa steg.

I praktiken smyger sig inte uppskattningarna bara mot roten. De hoppar dit snabbt och fördubblar ofta antalet korrekta decimaler för varje iteration.

Steg-för-steg-exempel på Newtons metod

Låt oss tillämpa Newtons metod på f(x) = x^2 - 2. Roten till den här funktionen är x = sqrt(2) ≈ 1.4142 – med andra ord beräknar vi kvadratroten ur 2.

Derivatan är f'(x) = 2x, så uppdateringsregeln blir:

Exempel (uppdateringsregel)

Vi börjar med en startgissning x_0 = 2.5.

Iteration 1:

Exempel (iteration 1)

Iteration 2:

Exempel (iteration 2)

Iteration 3:

Exempel (iteration 3)

Efter bara tre iterationer är vi redan korrekta till fyra decimaler. Felet sjönk från 1.086 vid x_0 till 0.0001 vid x_3 – och det fortsätter minska för varje steg.

Så här ser denna uppskattning och felvärden ut visuellt:

Visuell översikt av uppskattning och fel

Panelen till vänster visar hur varje uppskattning närmar sig sqrt(2) ≈ 1.4142, medan panelen till höger visar felet som blir mindre i log-skala – varje iteration ungefär kvadrerar föregående precisionsnivå.

Konvergens för Newtons metod

Newtons metod kan konvergera snabbt, men bara under rätt förutsättningar.

När din startgissning ligger nära roten och funktionen är slät i det området uppvisar metoden kvadratisk konvergens. Det är den tekniska termen för det du såg i exemplet: varje iteration kvadrerar ungefär felet från den föregående. Två korrekta decimaler blir fyra, fyra blir åtta, och så vidare.

Två villkor måste vara uppfyllda för att detta ska fungera:

• En bra startgissning: Ju närmare x_0 ligger den faktiska roten, desto snabbare konvergerar metoden. Om du börjar för långt bort kan tangenten i den punkten skicka dig åt fel håll.
• En välbeteende funktion: Funktionen behöver vara slät och deriverbar nära roten. Tvära svängar eller platta områden kan störa tangentapproximationen.

Det vanligaste felutfallet är en derivata nära noll. 

Om f'(x_n) är nära noll dividerar du med ett mycket litet tal i uppdateringsregeln, vilket skickar nästa uppskattning långt från roten. I värsta fall är f'(x_n) = 0 och beräkningarna slutar fungera eftersom du inte kan dividera med noll.

En dålig startpunkt kan också få metoden att oscillera eller divergera. I stället för att närma sig roten hoppar uppskattningarna fram och tillbaka eller driver längre bort för varje iteration.

Newtons metod belönar bra förarbete. En rimlig startgissning och en slät funktion är allt som behövs för att konvergera – och göra det snabbt.

Fördelar med Newtons metod

När förutsättningarna är de rätta är Newtons metod svårslagen.

Den största fördelen är kvadratisk konvergens. De flesta numeriska metoder närmar sig roten i linjär takt, vilket betyder att varje iteration minskar felet med en fast mängd. Newtons metod kvadrerar i stället felet, vilket gör att den blir noggrann snabbt med väldigt få iterationer.

Den är också allmänt användbar. Du kan tillämpa den på ett brett spektrum av funktioner – polynom, trigonometriska, exponentiella – utan att ändra något. Därför dyker den upp inom så många områden, från ingenjörssimuleringar till träning av maskininlärningsmodeller.

Begränsningar med Newtons metod

Newtons metod kräver en del i utbyte mot den hastigheten. Här är några begränsningar att ha i åtanke:

• Den kräver en derivata: Du behöver ett analytiskt uttryck för f'(x) innan du kan köra en enda iteration. För funktioner där derivatan är svår att beräkna (eller inte existerar) behöver du en annan metod.

• Den är känslig för startgissningen: Om du börjar för långt från roten kan metoden skicka dig åt fel håll.

• Den kanske inte konvergerar: Om funktionen har platta områden eller skarpa kurvor fungerar inte tangentapproximationen.

• Den kan divergera eller oscillera: I sämre fall misslyckas uppskattningarna med att konvergera och driver längre från roten eller studsar fram och tillbaka utan slut.

Så innan du väljer Newtons metod, se till att du förstår din funktion.

Newtons metod jämfört med andra rotfinningsmetoder

Newtons metod är inte det enda sättet att hitta rötter, och det är inte alltid rätt val för dig.

Två andra metoder dyker ofta upp: bisektionsmetoden och sekantmetoden. Låt mig kort förklara dessa.

Bisektionsmetoden

Bisektionsmetoden är den enklaste av de tre. Du börjar med ett intervall [a, b] där funktionen byter tecken – vilket betyder att en rot måste finnas någonstans däri. Sedan halverar du upprepade gånger intervallet och behåller halvan där teckenbytet kvarstår.

Det fungerar, men det är långsamt. Felet halveras vid varje iteration, vilket är linjär konvergens. Men det är också garanterat att fungera så länge funktionen är kontinuerlig och ditt startintervall innesluter en rot. Inga derivator krävs.

Sekantmetoden

Sekantmetoden är en nära släkting till Newtons metod. I stället för att beräkna derivatan analytiskt approximerar den den med hjälp av två tidigare uppskattningar:

Formel för sekantmetoden

Detta är en bra metod när derivatan är svår att beräkna. Du betalar med konvergenshastighet – sekantmetoden är snabbare än bisektion men långsammare än Newtons metod.

Tillämpningar av Newtons metod

Newtons metod dyker upp inom vetenskap, ingenjörskonst och maskininlärning. Låt mig förklara hur exakt.

Numerisk lösning av ekvationer

Den mest direkta tillämpningen. När en funktion saknar sluten form, hittar Newtons metod roten. Detta återkommer ständigt i vetenskapliga beräkningar – tänk att hitta jämviktspunkter i kemiska reaktioner eller lösa transcendentala ekvationer inom signalbehandling.

Optimering

Att hitta minimum eller maximum för en funktion f(x) innebär att hitta där dess derivata f'(x) = 0. Det är ett rotfinningsproblem – vilket betyder att Newtons metod kan tillämpas. Du kör helt enkelt algoritmen på f'(x) i stället för f(x), och använder andraderivatan f''(x) i stället för första.

Denna variant kallas Newtons metod för optimering och den konvergerar snabbare än gradientnedstigning på släta, välbeteende funktioner.

Maskininlärning

Inom maskininlärning innebär träning av en modell att minimera en förlustfunktion. Newtons metod och dess varianter används på ett par ställen här.

L-BFGS (Limited-memory Broyden-Fletcher-Goldfarb-Shanno) är en quasi-Newton-optimerare som approximerar andraderivatan för att slippa beräkna den direkt. Den är ett standardval för logistisk regression och andra konvexa problem. Newtons metod ligger också till grund för Newton–Raphson-uppdateringar som används vid anpassning av statistiska modeller, såsom generaliserade linjära modeller.

Fysik och ingenjörsvetenskap

Newtons metod finns överallt inom simulering och konstruktion. Ingenjörer använder den för att lösa icke-linjära ekvationssystem som beskriver fysiska system – tänk hållfasthetsanalys och strömningsdynamik. I varje fall reduceras grundproblemet till att hitta där ett system av ekvationer är lika med noll.

Vanliga misstag med Newtons metod

De flesta fel med Newtons metod handlar om samma fyra misstag. Låt mig gå igenom dem:

• Att börja för långt från roten: En dålig startgissning är den vanligaste orsaken till att metoden divergerar eller oscillerar. Om du saknar bra intuition om var roten ligger, plotta funktionen först. Det visar var du ska börja.

• Fel på derivatan: Uppdateringsregeln beror på f'(x). En felaktig derivata – vare sig från ett räknefel eller ett kodfel – ger felaktiga uppskattningar redan från första iterationen, och felet förstärks med iterationerna.

• Att inte kontrollera division med noll. Om f'(x_n) är noll eller blir mycket nära det, kan uppdateringssteget inte fungera. Lägg in ett skydd i din implementation: om derivatan understiger en liten tröskel, stoppa och rapportera felet i stället för att ge ett orimligt resultat.

• Att avbryta för tidigt. Att avbryta iterationerna innan uppskattningen har konvergerat lämnar dig med ett svar som ser nära ut men inte är det. Sätt ditt stoppvillkor på det faktiska felet – antingen |f(x_n)| eller |x_{n+1} - x_n| som understiger en tröskel du valt med omsorg, inte bara ett fast antal iterationer.

Slutsats

Newtons metod är ett av de mest användbara verktygen inom numeriska beräkningar. En enda uppdateringsregel, tillämpad upprepade gånger, kan hitta rötter med godtycklig noggrannhet på bara några få iterationer.

Du betalar för den hastigheten med villkor. Du behöver en bra startgissning, en icke-platt funktion, en icke-spikig funktion och en icke-noll derivata för att uppnå snabb konvergens. Förstå bara dessa villkor, så vet du när du ska välja Newtons metod och när du ska använda något annat (som bisection- eller sekantmetoder).

Det bästa sättet att bygga den intuitionen är att öva på enkla exempel. Börja med f(x) = x^2 - 2, prova olika startpunkter och se vad som händer. Gå vidare till funktioner med flera rötter eller platta områden och se var metoden bryter samman.

Om du gillar idén med optimering genom iteration bör du känna till gradientnedstigning. Läs vår Gradient Descent in Machine Learning: A Deep Dive för att lära dig hur den optimerar modeller för maskininlärning.