Net als de bisectiemethode en de Regula falsi is ook de methode van Newton-Raphson een algoritme waarmee een nulwaarde van een functie \(f(x)\) gezocht kan worden. In tegenstelling tot de eerste twee algoritmes is de methode van Newton-Raphson niet gebaseerd op het herhaaldelijk verkleinen van een interval waarin de nulwaarde ligt. Je hebt daarentegen een startwaarde nodig voor het gezochte nulpunt. Als deze startwaarde niet al te ver ligt van de gezochte nulwaarde, geeft de methode van Newton-Raphson doorgaans in enkele stappen een bijzonder nauwkeurig resultaat. Daar staat tegenover dat de methode geen nulwaarde zal kunnen vinden als de startwaarde te ver ligt van de gezochte nulwaarde. De methode van Newton-Raphson is dus in het algemeen sneller dan de de bisectiemethode en de Regula falsi, maar het is een minder robuust algoritme.
Het algoritme verloopt als volgt:
Het zwakke punt van deze methode is dat je op een gegeven moment een \(x_0\) zou kunnen vinden waarvoor \(f'(x_0)\) heel klein is. In dat geval is de raaklijn zo goed als horizontaal, en het snijpunt kan erg ver weg liggen van de gezochte nulwaarde. \(x_1\) is in dat geval een minder goede schatting voor de gezochte nulwaarde dan \(x_0\). In het slechtste geval vind je een \(x_0\) waarvoor \(f'(x_0)\) exact gelijk is aan nul, waardoor de raaklijn horizontaal is. In dat geval vind je zelfs geen snijpunt met de \(x\)-as, waardoor je ook geen nieuwe waarde van \(x_0\) kunt vinden.
Neem een blad papier en noteer het voorschrift van de raaklijn \(t\) aan de grafiek van \(f(x)\) in \(P(x_0, f(x_0))\). Stel dit voorschrift gelijk aan nul, en los op naar \(x\). Deze uitdrukking bepaalt de waarde van \(x_1\) in elke stap van het algoritme. Je merkt dat \(f'(x_0)\) voorkomt in deze uitdrukking.
Schrijf een functie afgeleide(f, x_0, dx) die een benaderende waarde voor \(f'(x_0)\) berekent en teruggeeft:
waarbij \(dx\) een klein (positief of negatief) getal is. Probeer Voorbeeld 1 te begrijpen: we zoeken een benadering voor \(f'(0)\) waarbij \(f(x) = 5x^2 + 4x - 9\). Algebraïsch vind je natuurlijk dat \(f'(0) = 4\).
Schrijf vervolgens een functie bepaal_x_1(f, x_0) die de waarde van \(x_1\) berekent en teruggeeft. f is het functievoorschrift waarvan je de nulwaarde wilt bepalen. In je implementatie kan je gewoon verwijzen naar f(x_0) etc. Gebruik een waarde van \(10^{-6}\) voor dx.
Schrijf een functie newton_raphson_iteratief(f, x_O, e) die de vergelijking \(f(x) = 0\) numeriek oplost door de methode van Newton-Raphson op een iteratieve manier toe te passen met toleratie \(e\). Probeer Voorbeeld 3 te begrijpen: we zoeken een nulwaarde van \(f(x) = 2x^2 -7x -9\) door de methode van Newton-Raphson toe te passen met een startwaarde van 3 en een tolerantie van \(10^{-11}\). De gevonden oplossing is tot op 12 decimalen gelijk aan de oplossing die je algebraïsch zou vinden. Je hoeft niet te begrijpen waar lambda x: 2*x**2 + -7*x + -9 vandaan komt: dit is een manier om te noteren dat \(f(x) = f(x) = 2x^2 -7x -9\).
Schrijf een functie newton_raphson_recursief(f, x_O, e) die de vergelijking \(f(x) = 0\) numeriek oplost door de methode van Newton-Raphson op een recursieve manier toe te passen met toleratie \(e\). Probeer Voorbeeld 4 te begrijpen: we zoeken een nulwaarde van \(f(x) = 2x^4 + 5x^3 -4x^2 + 3x + 3\) door de methode van Newton-Raphson toe te passen met een startwaarde van -1 en een tolerantie van \(10^{-9}\). De gevonden oplossing is tot op 14 decimalen gelijk aan de oplossing die je algebraïsch zou vinden. Je hoeft niet te begrijpen waar lambda x: 2*x**2 - x - 3 vandaan komt: dit is een manier om te noteren dat \(f(x) = 2x^4 + 5x^3 -4x^2 + 3x + 3\).
Invoer:
> afgeleide(lambda x: 5*x**2 + 4*x + -9, 0, -2e-09)
Uitvoer:
4.000000330961484
Invoer:
> bepaal_x_1(lambda x: 7*x**2 + 8*x + -3, -2)
Uitvoer:
-1.549999842468907
Invoer:
> newton_raphson_iteratief(lambda x: 2*x**2 + -7*x + -9, 3, 1e-11)
Uitvoer:
4.500000000000282
Invoer:
> newton_raphson_recursief(lambda x: 2*x**4 + 5*x**3 + -4*x**2 + 3*x + 3, -1, 1e-09)
Uitvoer:
-0.4999999999999961