Newton's Method
Newton might be wondering what nowadays goes under his name. Nowadays, what is known as Newton's (or Newton-Raphson) method is an iterative process set up to approximate roots of equations
Let a be a root of the equation f(x) = 0, so that
f(a) = f(x) + (a - x) f '(x) + (a - x)² f ''(γ)/2. |
Since f(a) = 0 and assuming (a - x)² f ''(γ)/2 is small relative to the first term, we may write
0 ≈ f(x) + (a - x) f '(x) |
In other words,
a ≈ x - f(x) / f '(x). |
This suggests an iterative process:
(1) | x_{n + 1} = x_{n} - f(x_{n}) / f '(x_{n}), n = 0, 1, ... |
with x_{0} chosen arbitrarily but hopefully in a neighborhood of the root a. The iterations have a simple geometric interpretation.
The tangent to the graph of y = f(x) at point (x_{n}, f(x_{n})) is given by the linear equation
(2) | y = f(x_{n}) + (x - x_{n}) f '(x_{n}). |
The idea behind Newton's method is that the latter equation is easier to solve (even several times in a row) than the original equation
x = x_{n} - f(x_{n}) / f '(x_{n}) |
which is exactly x_{n + 1} in (1).
The applet below helps visualize the process.
What if applet does not run? |
To start iterations click anywhere in the applet area. This defines the abcissa x_{0} on the x-axis. The next click will clear the area. Once the starting point x_{0} is set you can specify the number of iterations you wish to observe. The best way is to increase the number of iterations by one at a time.
Newton's iterations do not always converge. For example, they may loop up in a vicinity of a local extreme:
Error Analysis
Assuming f '' exists and is continuous in a vicinity of a root a of the equation
f(a) = f(x_{n}) + (a - x_{n}) f '(x_{n}) + (a - x_{n})² f ''(γ_{n})/2, |
where γx_{n} is between a and x_{n}. Since
0 = f(x_{n}) / f '(x_{n}) + a - x_{n} + (a - x_{n})² f ''(γ_{n}) / 2f '(x_{n}). |
The way Newton's iterations run, the term f(x_{n}) / f '(x_{n}) is exactly
0 = x_{n} - x_{n+1} + a - x_{n} + (a - x_{n})² f ''(γ_{n}) / 2f '(x_{n}). |
Solved for a - x_{n+1} the above becomes
a - x_{n+1} = [-f ''(γ_{n}) / 2f '(x_{n})] (a - x_{n})² |
showing that the error estimate on an iteration is proportional to the square of a similar estimate on the previous iteration. Assuming that the iterates do congregate towards the root and relying on the continuity of both f ' and f '' around a, we approximate
-f ''(γ_{n}) / 2f '(x_{n}) ≈ -f ''(a) / 2f '(a) = M |
so that
a - x_{n+1} ≈ M (a - x_{n})². |
This leads to
a - x_{n+1} ≈ [M (a - x_{0})]^{2n}. |
Thus, to insure convergence of the iterations, we need
|M (a - x_{0})| < 1 |
showing how close to the root the initial approximation x_{0} should be chosen to insure convergence:
|a - x_{0}| < 1 / |M|. |
An Example
Let's find an approximation to √2. To this end, we may define
x_{n + 1} = x_{n} - (x²_{n} - 2) / 2x_{n} |
or, after simplifications,
(3) | x_{n + 1} = ½(x_{n} + 2 / x_{n}). |
Observe that if the iterations converge to a, i.e. if lim_{n→∞}x_{n} = a, then it follows from (3) that
a = ½(a + 2 / a) |
implying a² = 2. So let's start with x_{0} = 1. Then
x_{1} | = (1 + 2/1) / 2 | |
= 3/2. |
Next,
x_{2} | = (3/2 + 2/(3/2)) / 2 | |
= (3/2 + 4/3) / 2 | ||
= 17 / 12, etc |
And
x_{2} | = (17/12 + 2/(17/12)) / 2 | |
= (17/12 + 24/17) / 2 | ||
= (289 + 288) / 408 | ||
= 577 / 408, etc. |
In Java double precision the iterations appear as:
i | x_{i} | ||
---|---|---|---|
0 | 1 | ||
1 | 1.5 | ||
2 | 1.4166666666666665 | ||
3 | 1.4142156862745097 | ||
4 | 1.4142135623746899 | ||
5 | 1.414213562373095 | ||
6 | 1.414213562373095 |
In a similar way, taking f(x) = x² - N yields
(3) | x_{n + 1} = ½(x_{n} + N / x_{n}). |
as an approximation to √N. The first few iterations may well be calculated by hand.
This method for approximating square roots was known to Heron of Alexandria in the first century A.D. Already then it was possible to argue [The Princeton Companion to Mathematics, p. 110] that, since (x_{n} + N/x_{n}) / 2 is the arithmetic mean of x_{n} and N/x_{n} and since √N lies between x_{n} and N/x_{n}, x_{n+1} will be close to √N if x_{n} is and may be closer.
References
- K. Atkinson, Elementary Numerical Analysis, John Wiley & Sons, 1985
- T. Gowers (ed.), The Princeton Companion to Mathematics, Princeton University Press, 2008
|Activities| |Contact| |Front page| |Contents| |Algebra|
Copyright © 1996-2018 Alexander Bogomolny
71061274