Inhoud – Newtons methode

De waarheid is veel te ingewikkeld om iets anders dan benaderingen toe te laten.

– John Von Neumann

Newtons methode

Laat $f: \mathbb{R} \rrechtsarrow \mathbb{R}$ een differentieerbare functie zijn. We zoeken een oplossing van $f(x) = 0$, uitgaande van een beginschatting $x = x_1$.

Bij de $n Het is echter belangrijk op te merken dat de methode van Newton niet altijd werkt. Er kunnen verschillende dingen fout gaan, zoals we zo dadelijk zullen zien.

De methode van Newton gebruiken

Net als bij de bisectiemethode benaderen we enkele bekende constanten.

De methode van Newton in het bovenstaande voorbeeld is veel sneller dan het bisectie-algoritme! In slechts 4 iteraties hebben we 11 decimalen nauwkeurigheid! De volgende tabel laat zien hoeveel decimalen nauwkeurigheid we hebben in elke $x_n$.

Het aantal decimale plaatsen van nauwkeurigheid verdubbelt ongeveer bij elke iteratie!

In het bovenstaande voorbeeld is de convergentie nog sneller dan in ons $\sqrt{2}$ voorbeeld. Het aantal decimalen nauwkeurigheid verdrievoudigt ruwweg bij elke iteratie!

Wat kan er misgaan

Hoewel de methode van Newton fantastisch goede benaderingen van een oplossing kan geven, kunnen er verschillende dingen misgaan. We bekijken nu enkele van deze minder gelukkige gedragingen.

Het eerste probleem is dat de $x_n$ misschien niet eens gedefinieerd is!

Dit probleem doet zich steeds voor als $f'(x_n) = 0$. Als $x_n$ een stationair punt van $f$ is, probeert Newtons methode door nul te delen – en mislukt.

Het volgende voorbeeld illustreert dat zelfs als de “benaderde oplossingen” $x_n$ bestaan, zij een oplossing misschien niet erg goed “benaderen”.

In bovenstaand voorbeeld is er eigenlijk een oplossing, $x = \frac{1}{3} \links( 4 + \sqrt{10} + \sqrt{100} rechts) \sim 3.59867$. Onze “benaderende oplossingen” $x_n$ benaderen het niet, in plaats daarvan fietsen ze zoals hieronder geïllustreerd.

Het derde probleem laat zien dat alle $x_n$ steeds verder van een oplossing af kunnen komen te liggen!

Het bovenstaande voorbeeld lijkt misschien een beetje dwaas, omdat het vinden van een exacte oplossing voor $x=0$ niet moeilijk is: de oplossing is $x=0$! Maar soortgelijke problemen zullen zich voordoen bij toepassing van de methode van Newton op elke kromme met een vergelijkbare vorm. Het feit dat $f'(x_n)$ dicht bij nul ligt, betekent dat de raaklijn dicht bij horizontaal ligt, en dus ver weg kan lopen om bij het $x$ -uiteinde van $x_{n+1}$ uit te komen.

Sensitieve afhankelijkheid van beginvoorwaarden

Soms kan de keuze van de beginvoorwaarden heel klein zijn, maar toch tot een radicaal andere uitkomst leiden in Newtons methode.

Overweeg het oplossen van $f(x) = 2x – 3x^2 + x^3 = 0$. Het is mogelijk om de kubus te ontbinden in factoren, $f(x) = x(x-1)(x-2)$, zodat de oplossingen gewoon $x=0, 1$ en $2$ zijn.

Als we de methode van Newton toepassen met verschillende beginschattingen $x_1$, komen we misschien uit bij een van deze drie oplossingen….of ergens anders.

Zoals hierboven geïllustreerd, passen we de methode van Newton toe uitgaande van $x_1 = 1.4$ en $x_1 = 1.5$. Uitgaande van $x_1 = 1.4 = \frac{7}{5}$ berekenen we, tot 6 decimalen achter de komma,

en de $x_n$ convergeren naar de oplossing $x=1$. En uitgaande van $x_1 = 1.5$ berekenen we $x_2 = 0$, een exacte oplossing, dus alle $x_3 = x_4 = \cdots = 0$.

We kunnen ons dan afvragen: waar, tussen de beginschattingen $x_1 = 1.4$ en $x_1 = 1.5$, schakelt de reeks over van het benaderen van $x=1$, naar het benaderen van $x=0$?

We vinden dat de beginschatting $x_1 = 1.45$ zich op dezelfde manier gedraagt als $1.5$: de reeks $x_n$ nadert de oplossing $x = 0$. Anderzijds gedraagt de beginschatting $x_1 = 1.44$ zich als $1.4$: $x_n$ nadert de oplossing $x=1$. De uitkomst lijkt te schakelen ergens tussen de beginschattingen $x_1 = 1.44$ en $x_1 = 1.45$. Met wat meer berekeningen kunnen we verder gaan en vinden we dat de omschakeling ergens tussen $x_1 = 1.447$ en $x_1 = 1.448$ gebeurt. De berekeningen (tot 3 decimalen) vanaf deze beginwaarden staan in de tabel hieronder.

Dus, als we $x_1 = 1.4475$ proberen, convergeert de $x_n$ dan naar de oplossing $x=1$ of $x=0$? Het antwoord is geen van beide: zoals uit de tabel blijkt, convergeert hij naar de oplossing $x=2$!

Verder, als we $x_1 = 1 + \frac{1}{\sqrt{5}} \sim 1,447214$, vinden we weer ander gedrag! Wat blijkt,

dus $x_1 = x_3$ en de $x_n$ wisselen tussen deze twee waarden.

Er is dus geen eenvoudige overgang van die waarden van $x_1$ die leiden tot de oplossing $x = 1$ en $x=0$. Het gedrag van de Newton-methode hangt uiterst gevoelig af van de beginwaarde $x_1$. We hebben immers slechts een handvol waarden voor $x_1$ uitgeprobeerd, en hebben slechts het topje van de ijsberg van dit gedrag gezien.

In de paragraaf Links vooruit onderzoeken we dit gedrag verder, en laten we enkele plaatjes zien van deze gevoelige afhankelijkheid van de beginvoorwaarden, die duidt op wiskundige chaos. Afbeeldingen die het gedrag van de methode van Newton illustreren tonen het ingewikkelde detail van een fractal.

De methode van Newton aan het werk zetten

In het algemeen is het moeilijk om precies aan te geven wanneer de methode van Newton goede benaderingen zal opleveren van een oplossing van $f(x) = 0$. Maar we kunnen de volgende opmerkingen maken, die een samenvatting zijn van onze eerdere waarnemingen.

• Als $f'(x_n) = 0$ dan faalt de methode van Newton onmiddellijk, omdat hij probeert te delen door nul.
• De “benaderingen” $x_1, x_2, x_3, \ldots$ kunnen ronddraaien, in plaats van naar een oplossing te convergeren.
• De “benaderingsoplossingen” $x_1, x_2, x_3, \ldots$ kunnen zelfs naar oneindig divergeren. Dit probleem doet zich voor als $f'(x_n)$ klein is, maar niet nul.
• Het gedrag van Newtons methode kan extreem gevoelig afhangen van de keuze van $x_1$, en leiden tot een chaotische dynamiek.

Een handige vuistregel is echter de volgende:

• Voorstel dat je een grafiek kunt schetsen van $y=f(x)$, en dat je bij benadering de plaats van een oplossing kunt zien, en dat $f'(x)$ niet te klein is in de buurt van die oplossing. Als je dan $x_1$ in de buurt van die oplossing neemt, en weg van andere oplossingen of kritieke punten, zal de methode van Newton $x_n$ opleveren die snel naar de oplossing convergeren.

Volgende pagina – Links vooruit – Snelheid van het bisectiealgoritme

Deze materialen zijn ontwikkeld in samenwerking met de Victorian Curriculum and Assessment Authority. © VCAA en The University of Melbourne namens AMSI 2015

Bijdragers Gebruiksvoorwaarden

th benadering $x_n$, wordt de volgende benadering gegeven door\

Formeel ziet het algoritme van Newton er als volgt uit.

Some comments about this algorithm:

1. Often, Newton’s method works extremely well, and the $x_n$ converge rapidly to a solution. However, it’s important to note that Newton’s method does not always work. Several things can go wrong, as we will see shortly.
2. Note that if $f(x_n) = 0$, so that $x_n$ is an exact solution of $f(x) = 0$, then the algorithm gives $x_{n+1} = x_n$, and in fact all of $x_n, x_{n+1}, x_{n+2}, x_{n+3}, \ldots$ will be equal. If you have an exact solution, Newton’s method will stay on that solution!
3. While the bisection method only requires $f$ to be continuous, Newton’s method requires the function $f$ to be differentiable. This is necessary for $f$ to have a tangent line.

Using Newton’s method

As we did with the bisection method, let’s approximate some well-known constants.

Newton’s method in the above example is much faster than the bisection algorithm! In only 4 iterations we have 11 decimal places of accuracy! The following table illustrates how many decimal places of accuracy we have in each $x_n$.

The number of decimal places of accuracy approximately doubles with each iteration!

In the above example, convergence is even more rapid than for our $\sqrt{2}$ example. The number of decimal places accuracy roughly triples with each iteration!

What can go wrong

While Newton’s method can give fantastically good approximations to a solution, several things can go wrong. We now examine some of this less fortunate behaviour.

The first problem is that the $x_n$ may not even be defined!

This problem occurs whenever when $f'(x_n) = 0$. If $x_n$ is a stationary point of $f$, then Newton’s method attempts to divide by zero — and fails.

The next example illustrates that even when the “approximate solutions” $x_n$ exist, they may not “approximate” a solution very well.

In the above example, there is actually a solution, $x = \frac{1}{3} \left( 4 + \sqrt{10} + \sqrt{100} \right) \sim 3.59867$. Our “approximate solutions” $x_n$ fail to approximate it, instead cycling as illustrated below.

The third problem shows that all $x_n$ can get further and further away from a solution!

The above example may seem a little silly, since finding an exact solution to $\arctan x = 0$ is not difficult: the solution is $x=0$! But similar problems will happen applying Newton’s method to any curve with a similar shape. The fact that $f'(x_n)$ is close to zero means the tangent line is close to horizontal, and so may travel far away to arrive at its $x$-intercept of $x_{n+1}$.

Sensitive dependence on initial conditions

Sometimes the choice of initial conditions can be ever so slight, yet lead to a radically different outcome in Newton’s method.

Consider solving $f(x) = 2x – 3x^2 + x^3 = 0$. It’s possible to factorise the cubic, $f(x) = x(x-1)(x-2)$, so the solutions are just $x=0, 1$ and $2$.

If we apply Newton’s method with different starting estimates $x_1$, we might end up at any of these three solutions… or somewhere else.

As illustrated above, we apply Newton’s method starting from $x_1 = 1.4$ and $x_1 = 1.5$. Starting from $x_1 = 1.4 = \frac{7}{5}$ we compute, to 6 decimal places,

\

and the $x_n$ converge to the solution $x=1$. And starting from $x_1 = 1.5$ we compute $x_2 = 0$, an exact solution, so all $x_3 = x_4 = \cdots = 0$.

We might then ask: where, between the initial estimates $x_1 = 1.4$ and $x_1 = 1.5$, does the sequence switch from approaching $x=1$, to approaching $x=0$?

We find that the the initial estimate $x_1 = 1.45$ behaves similarly to $1.5$: the sequence $x_n$ approaches the solution $x = 0$. On the other hand, taking $x_1 = 1.44$ behaves similarly to $1.4$: $x_n$ approaches the solution $x=1$. The outcome seems to switch somewhere between the initial estimates $x_1 = 1.44$ and $x_1 = 1.45$. With some more computations, we can narrow down further and find that the switch happens somewhere between $x_1 = 1.447$ and $x_1 = 1.448$. The computations (to 3 decimal places) from these initial values are shown in the table below.

So, if we try $x_1 = 1.4475$, will the $x_n$ converge to the solution $x=1$ or $x=0$? The answer is neither: as shown in the table, it converges to the solution $x=2$!

Furthermore, if we try $x_1 = 1 + \frac{1}{\sqrt{5}} \sim 1.447214$, we find different behaviour again! As it turns out,

\

so $x_1 = x_3$ and the $x_n$ alternate between these two values.

So there is no simple transition from those values of $x_1$ which lead to the solution $x = 1$ and $x=0$. The behaviour of Newton’s method depends extremely sensitively on the initial $x_1$. Indeed, we have only tried only a handful of values for $x_1$, and have only seen the tip of the iceberg of this behaviour.

In the Links Forward section we examine this behaviour further, showing some pictures of this sensitive dependence on initial conditions, which is indicative of mathematical chaos. Pictures illustrating the behaviour of Newton’s method show the intricate detail of a fractal.

Getting Newton’s method to work

In general, it is difficult to state precisely when Newton’s method will provide good approximations to a solution of $f(x) = 0$. But we can make the following notes, summarising our previous observations.

• If $f'(x_n) = 0$ then Newton’s method immediately fails, as it attempts to divide by zero.
• The “approximations” $x_1, x_2, x_3, \ldots$ can cycle, rather than converging to a solution.
• The “approximate solutions” $x_1, x_2, x_3, \ldots$ can even diverge to infinity. This problem happens when $f'(x_n)$ is small, but not zero.
• The behaviour of Newton’s method can depend extremely sensitively on the choice of $x_1$, and lead to chaotic dynamics.

However, a useful rule of thumb is as follows:

• Suppose you can sketch a graph of $y=f(x)$, and you can see the approximate location of a solution, and $f'(x)$ is not too small near that solution. Then taking $x_1$ near that solution, and away from other solutions or critical points, Newton’s method will tend to produce $x_n$ which converge rapidly to the solution.

Next page – Links forward – Speed of the bisection algorithm

These materials have been developed in collaboration with the Victorian Curriculum and Assessment Authority. © VCAA and The University of Melbourne on behalf of AMSI 2015

Contributors Term of use

e stap, gegeven $x_n$, bereken je de volgende benadering $x_{n+1}$ door

Example

Use Newton’s method to find an approximate solution to $x^2 – 2 = 0$, starting from an initial estimate $x_1 =2$. After 4 iterations, how close is the approximation to $\sqrt{2}$?

Solution

Let $f(x) = x^2 – 2$, so $f'(x) = 2x$. At step 1, we have $x_1 = 2$ and we calculate $f(x_1) = 2^2 – 2 = 2$ and $f'(x_1) = 4$, so

\

At step 2, from $x_2 = \frac{3}{2}$ we calculate $f(x_2) = \frac{1}{4}$ and $f'(x_2) = 3$, so

\

At step 3, from $x_3 = \frac{17}{12}$ we have $f(x_3) = \frac{1}{144}$ and $f'(x_3) = \frac{17}{6}$, so

\

At step 4, from $x_4 = \frac{577}{408}$ we calculate $f(x_4) = \frac{1}{166,464}$ and $f'(x_4) = \frac{577}{204}$, so

\

In fact, to 12 decimal places $\sqrt{2} \sim 1.414213562373$. So after 4 iterations, the approximate solution $x_5$ agrees with $\sqrt{2}$ to 11 decimal places. The difference between $x_5$ and $\sqrt{2}$ is

\

Exercise 10

(Harder.) This problem investigates this doubling of accuracy:

1. First calculate that $x_{n+1} = \frac{x_n}{2} + \frac{1}{x_n}$ and that, if $y_n = x_n – \sqrt{2}$, then $y_{n+1} = \frac{y_n^2}{2(\sqrt{2} + y_n)}$.
2. Show that, if $x_1 > 0$ (resp. $x_1 \sqrt{2}$ (resp. $x_n
3. Show that if $0
4. Show that, for $n \geq 2$, if $x_n$ differs from $\sqrt{2}$ by less than $10^{-k}$, then $x_{n+1}$ differs from $\sqrt{2}$ by less than $10^{-2k}$.

Example

Find an approximation to $\pi$ by using Newton’s method to solve $\sin x = 0$ for 3 iterations, starting from $x_1=3$. To how many decimal places is the approximate solution accurate?

Solution

Let $f(x) = \sin x$, so $f'(x) = \cos x$. We compute $x_2, x_3, x_4$ directly using the formula

\

We compute directly each $x_n$ to 25 decimal places, for 3 iterations:

\

To 25 decimal places, $\pi = 3.1415926535897932384626433$; $x_4$ agrees to 24 places.

Exercise 11

Find all solutions to the equation $\cos x = x$ to 9 decimal places using Newton’s method. Compare the convergence to what you obtained with the bisection method in exercise 5.

Example

Find an approximate solution to $\sin x = 0$ using Newton’s method starting from $x_1 = \frac{\pi}{2}$.

Solution

We set $f(x) = \sin x$, so $f'(x) = \cos x$. Now $x_2 = x_1 – \frac{f(x_1)}{f'(x_1)}$, but $f'(x_1) = \cos \frac{\pi}{2} = 0$, so $x_2$ is not defined, hence nor are any subsequent $x_n$.

Example

Approximate a solution to $-x^3 + 4x^2 – 2x + 2 = 0$ using Newton’s method from $x_1 = 0$.

Solution

Let $f(x) = -x^3 + 4x^2 – 2x + 2$, so $f'(x) = -3x^2 + 8x – 2$. Starting from $x_1 = 0$, we have

\

We have now found that $x_3 = x_1 = 0$. The computation for $x_4$ is then exactly the same as for $x_2$, so $x_4 = x_2 = 1$. Thus $x_n = 0$ for all odd $n$, and $x_n = 1$ for all even $n$. The $x_n$ are locked into a cycle, alternating between two values.

Example

Find an approximate solution to $\arctan x = 0$, using Newton’s method starting at $x_1 = 3$.

Solution

Let $f(x) = \arctan x$, so $f'(x) = \frac{1}{1+x^2}$. From $x_1 = 3$ we can compute successively $x_2, x_3, \ldots$. We write them to 2 decimal places.

\begin{align*}x_2 &= x_1 – \frac{f(x_1)}{f'(x_1)} = 3 – \frac{\arctan 3}{\frac{1}{1+3^2}} = 3 – 10 \arctan 3 \sim -9.49. \\x_3 &= x_2 – \frac{f(x_2)}{f'(x_2)} \sim 124.00 \\x_4 &= x_3 – \frac{f(x_3)}{f'(x_3)} \sim -23,905.94\end{align*}

The “approximations” $x_n$ rapidly diverge to infinity.

Exercise 12

Verify that if $f(x) = 2x – 3x^2 + x^3 = x(x-1)(x-2)$ and $x_1 = 1 + \frac{1}{\sqrt{5}}$, then $x_2 = 1 – \frac{1}{\sqrt{5}}$ and $x_3 = 1 + \frac{1}{\sqrt{5}} = x_1$.

Newton’s method

Let $f: \mathbb{R} \rightarrow \mathbb{R}$ be a differentiable function. We seek a solution of $f(x) = 0$, starting from an initial estimate $x = x_1$.

At the $n$’th step, given $x_n$, compute the next approximation $x_{n+1}$ by

\

Example

Use Newton’s method to find an approximate solution to $x^2 – 2 = 0$, starting from an initial estimate $x_1 =2$. After 4 iterations, how close is the approximation to $\sqrt{2}$?

Solution

Let $f(x) = x^2 – 2$, so $f'(x) = 2x$. At step 1, we have $x_1 = 2$ and we calculate $f(x_1) = 2^2 – 2 = 2$ and $f'(x_1) = 4$, so

\

At step 2, from $x_2 = \frac{3}{2}$ we calculate $f(x_2) = \frac{1}{4}$ and $f'(x_2) = 3$, so

\

At step 3, from $x_3 = \frac{17}{12}$ we have $f(x_3) = \frac{1}{144}$ and $f'(x_3) = \frac{17}{6}$, so

\

At step 4, from $x_4 = \frac{577}{408}$ we calculate $f(x_4) = \frac{1}{166,464}$ and $f'(x_4) = \frac{577}{204}$, so

\

In fact, to 12 decimal places $\sqrt{2} \sim 1.414213562373$. So after 4 iterations, the approximate solution $x_5$ agrees with $\sqrt{2}$ to 11 decimal places. The difference between $x_5$ and $\sqrt{2}$ is

\

Exercise 10

(Harder.) This problem investigates this doubling of accuracy:

1. First calculate that $x_{n+1} = \frac{x_n}{2} + \frac{1}{x_n}$ and that, if $y_n = x_n – \sqrt{2}$, then $y_{n+1} = \frac{y_n^2}{2(\sqrt{2} + y_n)}$.
2. Show that, if $x_1 > 0$ (resp. $x_1 \sqrt{2}$ (resp. $x_n
3. Show that if $0
4. Show that, for $n \geq 2$, if $x_n$ differs from $\sqrt{2}$ by less than $10^{-k}$, then $x_{n+1}$ differs from $\sqrt{2}$ by less than $10^{-2k}$.

Example

Find an approximation to $\pi$ by using Newton’s method to solve $\sin x = 0$ for 3 iterations, starting from $x_1=3$. To how many decimal places is the approximate solution accurate?

Solution

Let $f(x) = \sin x$, so $f'(x) = \cos x$. We compute $x_2, x_3, x_4$ directly using the formula

\

We compute directly each $x_n$ to 25 decimal places, for 3 iterations:

\

To 25 decimal places, $\pi = 3.1415926535897932384626433$; $x_4$ agrees to 24 places.

Exercise 11

Find all solutions to the equation $\cos x = x$ to 9 decimal places using Newton’s method. Compare the convergence to what you obtained with the bisection method in exercise 5.

Example

Find an approximate solution to $\sin x = 0$ using Newton’s method starting from $x_1 = \frac{\pi}{2}$.

Solution

We set $f(x) = \sin x$, so $f'(x) = \cos x$. Now $x_2 = x_1 – \frac{f(x_1)}{f'(x_1)}$, but $f'(x_1) = \cos \frac{\pi}{2} = 0$, so $x_2$ is not defined, hence nor are any subsequent $x_n$.

Example

Approximate a solution to $-x^3 + 4x^2 – 2x + 2 = 0$ using Newton’s method from $x_1 = 0$.

Solution

Let $f(x) = -x^3 + 4x^2 – 2x + 2$, so $f'(x) = -3x^2 + 8x – 2$. Starting from $x_1 = 0$, we have

\

We have now found that $x_3 = x_1 = 0$. The computation for $x_4$ is then exactly the same as for $x_2$, so $x_4 = x_2 = 1$. Thus $x_n = 0$ for all odd $n$, and $x_n = 1$ for all even $n$. The $x_n$ are locked into a cycle, alternating between two values.

Example

Find an approximate solution to $\arctan x = 0$, using Newton’s method starting at $x_1 = 3$.

Solution

Let $f(x) = \arctan x$, so $f'(x) = \frac{1}{1+x^2}$. From $x_1 = 3$ we can compute successively $x_2, x_3, \ldots$. We write them to 2 decimal places.

\begin{align*}x_2 &= x_1 – \frac{f(x_1)}{f'(x_1)} = 3 – \frac{\arctan 3}{\frac{1}{1+3^2}} = 3 – 10 \arctan 3 \sim -9.49. \\x_3 &= x_2 – \frac{f(x_2)}{f'(x_2)} \sim 124.00 \\x_4 &= x_3 – \frac{f(x_3)}{f'(x_3)} \sim -23,905.94\end{align*}

The “approximations” $x_n$ rapidly diverge to infinity.

Exercise 12

Verify that if $f(x) = 2x – 3x^2 + x^3 = x(x-1)(x-2)$ and $x_1 = 1 + \frac{1}{\sqrt{5}}$, then $x_2 = 1 – \frac{1}{\sqrt{5}}$ and $x_3 = 1 + \frac{1}{\sqrt{5}} = x_1$.