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.