Householder's method
In mathematics, and more specifically in numerical analysis, Householder's methods are a class of root-finding algorithms that are used for functions of one real variable with continuous derivatives up to some order d+1. Each of these methods is characterized by the number d, which is known as the order of the method. The algorithm is iterative and has a rate of convergence of d+1.
These methods are named after the American mathematician Alston Scott Householder.
Householder's method is a numerical algorithm for solving the nonlinear equation f(x) = 0. In this case, the function f has to be a function of one real variable. The method consists of a sequence of iterations
beginning with an initial guess x0.
If f is a (d+1) times continuously differentiable function and a is a zero of f but not of its derivative, then, in a neighborhood of a, the iterates xn satisfy:
This means that the iterates converge to the zero if the initial guess is sufficiently close, and that the convergence has order (d+1).
Despite their order of convergence, these methods are not widely used because the gain in precision is not commensurate with the rise in effort for large d. The Ostrowski index expresses the error reduction in the number of function evaluations instead of the iteration count.
An approximate idea of Householder's method derives from the geometric series. Let the real-valued, continuously differentiable function f(x) have a simple zero at x=a, that is a root f(a)=0 of multiplicity one, which is equivalent to . Then 1/f(x) has a singularity at a, specifically a simple pole (also of multiplicity one), and close to a the behavior of 1/f(x) is dominated by 1/(x-a). Approximately, one gets
...
Wikipedia