Newton's Method
Although bisection is simple and easy to code there exist far better
methods (faster and applicable in more situations) for solving nonlinear
equations. The best methods stem from Newton's application of what is
today called
The Fundamental Trick of Engineering: Pretend the world is linear.
More precisely, suppose f is a real function of the real variable x,
e.g., f(x)=x3-8, and we wish to solve f(x)=0. We begin with
the hope that the solution is near some point x0. For points
x near x0 we recall that Taylor's Theorem permits the
expression
f(x) = f(x0) + f'(x0)(x-x0) + f''(x0)(x-x0)2/2 + f'''(x0)(x-x0)3/3! + ...
where ... stands for higher order terms, meaning terms like
(x-x0)p where p exceeds 3. Now Newton's Method
consists in applying the FTE to the above as a means of providing a
better guess. Namely, let x1 be the place
where the linear part of f near x0
vanishes. That is, solve
0 = f(x0) + f'(x0)(x1-x0)
for x1. That is, set
x1 = x0 - f(x0)/f'(x0)
If f was indeed linear we would be done, i.e., f would vanish at
x1. In the nonlinear case x1 is not a solution
but is rather a better guess than what we started with. So you now
wonder, "Can this new guess be improved?" The answer is yes. It does
not require any new ideas, just stubborness. Namely, apply the FTE
(repeatedly) until you arrive at a guess you deem "close enough".
Anything you do repeatedly cries out to be looped. The fundamental
Newton Step to be taken each time through the loop is
xj = xj-1 - f(xj-1)/f'(xj-1)
One should exit the loop when |f(xj)| is sufficiently small.
For a slideshow graphical interpretation of each Newton Step hit this
Newton Demo site.
Here is a diary of Newton's
Method applied (successfully) to f(x)=x3-8 starting from
x0=1.
Here is a diary of Newton's
Method applied (unsuccessfully) to f(x)=x3-2x+2 starting from
x0=1.
