Derivation of Newton's Method:
Given a point xn on a graph of function f, we can create a line tangent to this point like so:
g(x) = f(xn) + f'(xn)(x - xn)
The root of g(x) is found like this:
0 = f(xn) + f'(xn)(x - xn)
0 = f(xn) + f'(xn)x - f'(xn)xn
f'(xn)x = f'(xn)xn - f(xn)
f'(xn)xn - f(xn)
x = ----------------
f'(xn)
f(xn)
x = xn - ------
f'(xn)
Because this root approximates the nearest root of f(x), we can say that
f(xn)
x{n+1} = ------
f'(xn)
where initial value x0 is a number close to the
root we want to find. xn will (hopefully) make progressively better
approximations of the actual
root of g(x).
Newton's method also has a quadratic version, akin to it in the same way that Mueller's Method is akin to the "regula falsi" method. I derived it myself, I don't know if it has a name already.
Given a point xn on the graph of function g, we can create a parabola tangent to this point like so:
1 2
g(x) = f(xn) + f'(xn)(x-xn) + - f''(xn)(x-xn)
2
The roots of g(x) can be found using the quadratic formula like this:
Distribute and collect like terms:
1 2
0 = - f''(xn)x
2
+ (f'(xn) - f''(xn)xn)x
1 2
+ f(xn) - f'(xn)xn + - f''(xn)xn
2
And now
wantonly plug into the
quadratic formula. This is so horrendously messy that I cannot legibly write it without
MathML or some other such, so that is an
exercise left to the reader. Anyways, it's really fun because it all cancels out to look like this, after replacing x with x{n+1} as above:
Method 1
______________________
/ 2
f'(x) -+ \/ f'(xn) - 2f(xn)f''(xn)
x{n+1} = xn - ----------------------------------
f''(xn)
This looks remarkably like the
quadratic formula! Let's play around with it a bit more, namely
distributing the
denominator into the
radical, and as above, replacing x with x{n+1}:
Method 2
______________________
f'(xn) / f'(xn) 2 2f(xn)
x{n+1} = xn - ------- +- \ | ( ------- ) - -------
f''(xn) \/ f''(xn) f''(xn)
Now this looks similar to Newton's Method of old!
Yet the question still remains: which root should we go with? Here's a chart, showing the sign of the radical for each method as a function of the signs of the first two derivatives:
f'(x) + + - -
f''(x) + - + -
Method 1 - - + +
Method 2 + - - +
Note that method 1 is not
dependant on the
sign of f''(x) because the
radical is
divided by the same, thus affecting the
sign change automatically.
This method converges about twice as fast as the standard Newton's Method, but takes about twice as much work. Unlike Newton's Method, however, it does converge for cbrt(x) and the like, though somewhat slowly.