Edit made on March 09, 2009 by GarethMcCaughan at 09:54:24
Deleted text in red
/
Inserted text in green
WW
HEADERS_END
Also called the Newton-Raphson Method
A way of finding solutions to equations /f(x)=0./
Different starting points give different answers, and some
give no answers at all. Using complex numbers and plotting
the basins of attraction on the complex plane can give
fractals.
Which is nice.
----
!! More details ...
The first derivative of a function is its slope. That's
how much it changes in value for small perturbations of
the location. In other words, the derivative is defined
so that this is true:
* EQN:f(x+\epsilon){\approx}f(x)+{\epsilon}f'(x)
So let's suppose we have EQN:x_0 and we want to move it
a bit, say by EQN:\epsilon , to a location where the function
evaluates to 0. So we want to find EQN:\epsilon such that
* EQN:f(x_0+\epsilon)=0
In other words, we want to solve
* EQN:0{\approx}f(x_0)+{\epsilon}f'(x_0)
which is clearly
* EQN:\epsilon\approx\frac{-f(x_0)}{f'(x_0)}
So starting from EQN:x_0 we get EQN:x_1=x_0-\frac{f(x_0)}{f'(x_0)}
Lather, rinse, repeat.
This works in the complex plane with the complex numbers,
as well as with the real numbers.
Newton's method can be adapted for use on multidimensional
problems: you have a function /f/ from /n/ dimensional space to
/n/ dimensional space (equivalently: /n/ functions of /n/
variables); its derivative EQN:f'(x_0) (an /n/ by /n/ matrix,
now) is defined in the same way as above; provided the matrix
is invertible, we may then solve for EQN:\epsilon as before.
If the initial estimate EQN:x_0 is too far from the actual root /x/
(so that EQN:\epsilon is not small and the approximation
EQN:f(x+\epsilon){\approx}f(x)+{\epsilon}f'(x)
isn't a good one) then Newton's method may misbehave,
producing an updated estimate that's no better
(or even worse) than the original one. As an alarming
special case, consider what happens when /x/ is very close
to a zero of EQN:f' .