Newton's method (idea)

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.