Higher Order Newton Fractals

February 15th, 2017

Householder's method:\[ z_{n+1} = z_{n} - \frac{p(z_n)}{p'(z_n)}\left(1 + \frac{p(z_n)p''(z_n)}{2p'(z_n)^2}\right) \]
Halley's method:\[ z_{n+1} = z_{n} - \frac{p(z_n)}{p'(z_n)}\left(1 - \frac{2p(z_n)p'(z_n)}{2[p'(z_n)]^2 - p(z_n)p''(z_n)}\right) \]
Warning: this may take a while to render

A root of a function \(f(x)\) is a number \(c\) such that \(f(c)=0\). Finding roots of functions is an important problem in many fields and Newton's method reduces the problem of finding roots of a function to finding roots of a simpler function. This is an extension of this post. Fundamentally, Newton's method uses something called Taylor's theorem, briefly discussed here. However, Newton's original method uses a first-order approximation, but we can get faster convergence, that is we can find a root in less time with a second order approximation. But in some cases the increased rate of convergence is outweighed by the greater complexity involved in computation. So people have come up with similar techniques which lie in a good middle ground between fast convergence and fast computation.