Methode van Newton: Vind snel nulpunten met iteratieve benadering

Sommige vergelijkingen hebben gewoon geen nette algebraïsche oplossing.

Je kunt zoveel ontbinden en substitueren als je wilt, maar sommige vergelijkingen hebben geen gesloten vorm. Zo heeft een polynoom van graad vijf of hoger geen algemene algebraïsche oplossing. Functies die exponentiëlen met polynomen combineren, zoals e^x = 3x, vallen in dezelfde categorie. In zulke gevallen heb je een andere aanpak nodig.

De methode van Newton is die aanpak. Ze vindt nulpunten numeriek door steeds slimmere gokjes te maken - elk gestuurd door de raaklijn van de functie bij de huidige schatting.

In dit artikel neem ik je mee door de formule achter de methode van Newton, hoe ze stap voor stap werkt, wanneer ze convergeert en wanneer niet - met concrete voorbeelden om de theorie te laten beklijven.

Op zoek naar meer wiskundetopics die je als data scientist moet kennen? Lees onze blogpost Meetkundige reeks: formule, convergentie en voorbeelden om te zien hoe die wordt toegepast in financiën, natuurkunde en informatica.

Wat is de methode van Newton?

De methode van Newton is een iteratieve techniek om de nulpunten van een functie te vinden. De nulpunten zijn de invoerwaarden waarvoor de functie nul is.

Je begint dit proces met een eerste gok. Vervolgens gebruikt de methode de geometrie van de functie op dat punt om een betere gok te maken. Je herhaalt dit proces, en elke iteratie brengt je dichter bij het echte nulpunt.

Dat is het hele idee. Je hebt alleen een slimme, herhaalbare update-regel nodig die naar het antwoord convergeert.

De formule van de methode van Newton

De kern van de methode van Newton is één enkele update-regel die je herhaaldelijk toepast totdat je dicht genoeg bij het nulpunt bent.

Hier is de formule:

Formule van de methode van Newton

Elke iteratie neemt je huidige schatting x_n en produceert een betere, x_{n+1}. Je blijft updaten tot het resultaat dicht genoeg bij nul is.

De formule heeft drie componenten:

• x_n - je huidige schatting van het nulpunt

• f(x_n) - de functiewaarde bij die schatting

• f'(x_n) - de afgeleide van de functie bij die schatting, die de helling van de raaklijn aangeeft

Als f(x_n) groot is, zit je ver van het nulpunt. Als f'(x_n) steil is, verandert de functie snel en kun je een grotere stap nemen. De verhouding f(x_n) / f'(x_n) vertelt je precies hoe ver je moet bewegen - en je trekt die af van je huidige gok om dichterbij te komen.

Als f'(x_n) nul of bijna nul is, werkt de formule eigenlijk niet. Je zou door nul delen, wat betekent dat de methode geen volgende schatting kan produceren. Ik ga hier dieper op in bij de beperkingen.

Hoe de methode van Newton werkt

De methode van Newton volgt bij elke iteratie dezelfde vier stappen.

1. Kies een beginwaarde: Kies een startwaarde x_0 ergens in de buurt van het nulpunt. Je hoeft niet exact te zitten - alleen dichtbij genoeg zodat de functie zich rond dat punt voorspelbaar gedraagt. Ik leg in het deel over convergentie uit wat "dicht genoeg" betekent.

2. Bereken de functiewaarde: Evalueer f(x_0). Dit vertelt je hoe ver de functie van nul af zit bij je huidige schatting. Als f(x_0) = 0, ben je klaar - je hebt het nulpunt gevonden.

3. Bereken de afgeleide: Evalueer f'(x_0). Dit geeft je de helling van de functie bij x_0, oftewel de helling van de raaklijn op dat punt.

4. Werk de schatting bij: Pas de update-regel toe volgens de formule uit de vorige sectie.

En klaar!

Deze nieuwe waarde x_1 is waar de raaklijn de x-as snijdt. Geometrisch teken je een rechte lijn die de kromme raakt bij x_0 en volg je die naar nul. Dat snijpunt is je volgende, betere gok.

Dan herhaal je. Vul x_1 terug in bij stappen 2 t/m 4 om x_2 te krijgen, dan x_3, enzovoort. Elke iteratie tekent een nieuwe raaklijn op het geüpdatete punt en vindt waar die de x-as snijdt.

Het proces stopt wanneer f(x_n) dicht genoeg bij nul is - meestal zodra het onder een kleine drempel zakt die je van tevoren definieert.

Geometrische interpretatie van de methode van Newton

Stel je een kromme op een grafiek voor - dat is je functie f(x). Het nulpunt is waar de kromme de x-as kruist. Je weet nog niet waar dat kruispunt is, dus je begint met een gok x_0 ergens op de x-as.

Bij elke stap plot je het punt (x_0, f(x_0)) op de kromme en teken je de raaklijn op dat punt - een rechte lijn die de kromme daar raakt en diens helling volgt. Die raaklijn is niet horizontaal. Hij staat scheef, en als je hem naar beneden volgt, snijdt hij de x-as ergens. Dat snijpunt is je volgende schatting, x_1.

Dan herhaal je. Bij x_1 teken je een nieuwe raaklijn en zoek je waar die de x-as snijdt. Dat levert x_2 op. Elke raaklijn is een lokale lineaire benadering van de kromme, en elk snijpunt komt dichter bij het echte nulpunt uit.

De grafiek hieronder toont twee iteraties van de methode van Newton toegepast op f(x) = x^2 - 2, te beginnen bij x_0 = 2.5:

Geometrisch interpretatieschema

Dit werkt omdat een raaklijn de beste benadering met een rechte lijn is van een kromme op een gegeven punt. Hoe dichter je bij het nulpunt zit, hoe meer de raaklijn op de kromme zelf lijkt - en hoe nauwkeuriger je volgende stap wordt.

In de praktijk kruipen de schattingen niet alleen maar naar het nulpunt toe. Ze springen er snel naartoe, vaak met een verdubbeling van het aantal correcte decimalen per iteratie.

Stap-voor-stap voorbeeld van de methode van Newton

Laten we de methode van Newton toepassen op f(x) = x^2 - 2. Het nulpunt van deze functie is x = sqrt(2) ≈ 1.4142 - met andere woorden, we berekenen de vierkantswortel van 2.

De afgeleide is f'(x) = 2x, dus de update-regel wordt:

Voorbeeld (update-regel)

Laten we beginnen met een startgok van x_0 = 2.5.

Iteratie 1:

Voorbeeld (iteratie 1)

Iteratie 2:

Voorbeeld (iteratie 2)

Iteratie 3:

Voorbeeld (iteratie 3)

Na slechts drie iteraties zijn we al nauwkeurig tot op vier decimalen. De fout daalde van 1.086 bij x_0 naar 0.0001 bij x_3 - en blijft bij elke stap afnemen.

Zo zien deze schattings- en foutwaarden er visueel uit:

Visueel overzicht van schatting en fout

Het linkerpaneel laat zien hoe elke schatting dichter bij sqrt(2) ≈ 1.4142 komt, terwijl het rechterpaneel de fout kleiner laat worden op een log-schaal - elke iteratie verdubbelt ruwweg de precisie van de vorige.

Convergentie van de methode van Newton

De methode van Newton kan snel convergeren, maar alleen onder de juiste voorwaarden.

Als je eerste gok dicht bij het nulpunt ligt en de functie in dat gebied glad is, vertoont de methode kwadratische convergentie. Dat is de technische term voor wat je in het voorbeeld zag: elke iteratie kwadrateert ruwweg de fout van de vorige. Twee correcte decimalen worden er vier, vier worden er acht, enzovoort.

Twee voorwaarden moeten gelden om dit te laten werken:

• Een goede beginwaarde: Hoe dichter x_0 bij het echte nulpunt ligt, hoe sneller de methode convergeert. Als je te ver weg start, kan de raaklijn je de verkeerde kant op sturen.
• Een goed-gedragende functie: De functie moet vlakbij het nulpunt glad en differentieerbaar zijn. Scherpe bochten of vlakke stukken kunnen de raaklijnbenadering verstoren.

De meest voorkomende faalmodus is een afgeleide dicht bij nul. 

Als f'(x_n) dicht bij nul is, deel je in de update-regel door een heel klein getal, wat de volgende schatting ver van het nulpunt wegstuurt. In het slechtste geval is f'(x_n) = 0 en stopt de berekening omdat je niet door nul kunt delen.

Een slechte startwaarde kan er ook voor zorgen dat de methode oscilleert of divergeert. In plaats van het nulpunt te naderen, schieten de schattingen heen en weer of drijven ze bij elke iteratie verder weg.

De methode van Newton beloont een goede setup. Een redelijke beginwaarde en een gladde functie zijn genoeg om te convergeren - en snel ook.

Voordelen van de methode van Newton

Als de omstandigheden kloppen, is de methode van Newton lastig te verslaan.

Het grootste voordeel is kwadratische convergentie. De meeste numerieke methoden naderen het nulpunt lineair, wat betekent dat elke iteratie de fout met een vast bedrag reduceert. De methode van Newton kwadrateert de fout, wat betekent dat ze met heel weinig iteraties snel nauwkeurig wordt.

Ze is ook generalistisch. Je kunt haar toepassen op een breed scala aan functies - polynomiaal, trigonometrisch, exponentieel - zonder iets te veranderen. Daarom kom je haar in zoveel domeinen tegen, van engineeringsimulaties tot het trainen van machine learning-modellen.

Beperkingen van de methode van Newton

De methode van Newton vraagt veel terug voor die snelheid. Hier zijn een paar beperkingen om in gedachten te houden:

• Er is een afgeleide nodig: Je hebt een analytische uitdrukking voor f'(x) nodig voordat je ook maar één iteratie kunt uitvoeren. Voor functies waarvan de afgeleide lastig te berekenen is (of niet bestaat) heb je een andere aanpak nodig.

• Ze is gevoelig voor de beginwaarde: Als je te ver van het nulpunt begint, kan de methode je de verkeerde richting opsturen.

• Ze convergeert mogelijk niet: Als de functie vlakke gebieden of scherpe bochten heeft, werkt de raaklijnbenadering gewoon niet.

• Ze kan divergeren of oscilleren: In slechte gevallen lukt het niet om te convergeren en drijven de schattingen verder van het nulpunt af of kaatsen ze eindeloos heen en weer.

Dus voordat je naar de methode van Newton grijpt, zorg dat je je functie begrijpt.

Methode van Newton vs. andere nulpuntsmethoden

De methode van Newton is niet de enige manier om nulpunten te vinden, en het is niet altijd de juiste voor jou.

Twee andere methoden komen vaak voorbij: de bisectiemethode en de secantmethode. Ik leg ze kort uit.

Bisectiemethode

De bisectiemethode is de eenvoudigste van de drie. Je begint met een interval [a, b] waarin de functie van teken verandert - wat betekent dat er ergens binnenin een nulpunt moet liggen. Vervolgens halveer je het interval herhaaldelijk en behoud je de helft waarin de tekenverandering nog steeds optreedt.

Het werkt, maar het is langzaam. De fout halveert bij elke iteratie, wat lineaire convergentie is. Maar het werkt wel gegarandeerd zolang de functie continu is en je begininterval een nulpunt insluit. Er zijn geen afgeleiden nodig.

Secantmethode

De secantmethode is een naaste verwant van de methode van Newton. In plaats van de afgeleide analytisch te berekenen, benadert ze die met twee vorige schattingen:

Formule van de secantmethode

Dit is een goede aanpak wanneer de afgeleide moeilijk te berekenen is. Je betaalt met convergentiesnelheid - de secantmethode is sneller dan bisectie maar langzamer dan de methode van Newton.

Toepassingen van de methode van Newton

De methode van Newton duikt overal op in wetenschap, engineering en machine learning. Zo precies werkt dat:

Vergelijkingen numeriek oplossen

De meest directe toepassing. Als een functie geen gesloten-vormoplossing heeft, vindt de methode van Newton het nulpunt. Dit komt voortdurend voor in wetenschappelijke computing - denk aan het vinden van evenwichtspunten in chemische reacties of het oplossen van transcendentale vergelijkingen in signaalverwerking.

Optimalisatie

Het minimum of maximum van een functie f(x) vinden betekent vinden waar de afgeleide f'(x) = 0. Dat is een nulpuntsprobleem - dus kan de methode van Newton worden toegepast. Je draait het algoritme gewoon op f'(x) in plaats van op f(x), met de tweede afgeleide f''(x) in plaats van de eerste.

Deze variant heet de methode van Newton voor optimalisatie en convergeert sneller dan gradient descent bij gladde, goed-gedragende functies.

Machine learning

In machine learning betekent het trainen van een model het minimaliseren van een verliesfunctie. De methode van Newton en varianten ervan zie je hier op een paar plekken terug.

L-BFGS (Limited-memory Broyden-Fletcher-Goldfarb-Shanno) is een quasi-Newton-optimalisator die de tweede afgeleide benadert om die niet direct te hoeven berekenen. Het is een standaardkeuze voor logistische regressie en andere convexe problemen. De methode van Newton vormt ook de basis voor de Newton-Raphson-updates die worden gebruikt bij het fitten van statistische modellen, zoals gegeneraliseerde lineaire modellen.

Natuurkunde en engineering

De methode van Newton is overal in simulatie en ontwerp. Ingenieurs gebruiken haar om niet-lineaire stelsels vergelijkingen op te lossen die fysieke systemen beschrijven - denk aan analyse van structurele spanningen en vloeistofdynamica. In elk geval reduceert het onderliggende probleem tot het vinden waar een stel vergelijkingen gelijk is aan nul.

Veelgemaakte fouten met de methode van Newton

De meeste fouten met de methode van Newton komen neer op dezelfde vier misstappen. Ik loop ze door:

• Te ver van het nulpunt beginnen: Een slechte beginwaarde is de meest voorkomende reden dat de methode divergeert of oscilleert. Als je geen goed gevoel hebt waar het nulpunt zit, plot dan eerst de functie. Dat vertelt je waar je moet beginnen.

• De afgeleide verkeerd bepalen: De update-regel hangt af van f'(x). Een onjuiste afgeleide - door een rekenfout of een codefout - levert vanaf de allereerste iteratie foute schattingen op, en de fout stapelt zich op met de iteraties.

• Niet controleren op deling door nul. Als f'(x_n) nul is of er heel dicht bij komt, kan de update-stap niet werken. Voeg een beveiliging toe in je implementatie: als de afgeleide onder een kleine drempel zakt, stop dan en rapporteer de mislukking in plaats van een onzinnig resultaat te produceren.

• Te vroeg stoppen. De iteraties afkappen voordat de schatting is geconvergeerd, laat je achter met een antwoord dat dichtbij lijkt maar het niet is. Stel je stopcriterium in op de werkelijke fout - ofwel |f(x_n)| ofwel |x_{n+1} - x_n| die onder een drempel zakt die je bewust hebt gekozen, niet slechts een vast aantal iteraties.

Conclusie

De methode van Newton is een van de nuttigste tools in numerieke berekeningen. Eén enkele update-regel, herhaald toegepast, kan nulpunten met willekeurige precisie vinden in slechts een paar iteraties.

Voor die snelheid betaal je met voorwaarden. Je hebt een goede beginwaarde nodig, een niet-vlakke functie, een niet-spijkerige functie en een niet-nul afgeleide om snelle convergentie te bereiken. Begrijp deze voorwaarden, en je weet wanneer je naar de methode van Newton moet grijpen en wanneer je iets anders moet gebruiken (zoals bisectie- of secantmethoden).

De beste manier om dat gevoel te ontwikkelen is oefenen met eenvoudige voorbeelden. Begin met f(x) = x^2 - 2, probeer verschillende startpunten en kijk wat er gebeurt. Ga verder naar functies met meerdere nulpunten of vlakke stukken en zie waar de methode het laat afweten.

Als je het concept van optimalisatie door iteratie aanspreekt, moet je gradient descent kennen. Lees onze Gradient Descent in Machine Learning: een deep dive om te leren hoe het modellen voor machine learning optimaliseert.