In
mathematics, and more specifically in
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of numerical methods ...
, Householder's methods are a class of
root-finding algorithm
In mathematics and computing, a root-finding algorithm is an algorithm for finding zeros, also called "roots", of continuous functions. A zero of a function , from the real numbers to real numbers or from the complex numbers to the complex numbers ...
s that are used for functions of one real variable with continuous derivatives up to some order . Each of these methods is characterized by the number , which is known as the ''order'' of the method. The algorithm is iterative and has a
rate of convergence
In numerical analysis, the order of convergence and the rate of convergence of a convergent sequence are quantities that represent how quickly the sequence approaches its limit. A sequence (x_n) that converges to x^* is said to have ''order of c ...
of .
These methods are named after the American mathematician
Alston Scott Householder
Alston Scott Householder (5 May 1904 – 4 July 1993) was an American mathematician who specialized in mathematical biology and numerical analysis.
He is the inventor of the Householder transformation and of Householder's method.
Career
Hous ...
.
Method
Householder's method is a numerical algorithm for solving the nonlinear equation . In this case, the function has to be a function of one real variable. The method consists of a sequence of iterations
:
beginning with an initial guess .
If is a times continuously differentiable function and is a zero of but not of its derivative, then, in a neighborhood of , the iterates satisfy:
:
, for some
This means that the iterates converge to the zero if the initial guess is sufficiently close, and that the convergence has order .
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 . The ''Ostrowski index'' expresses the error reduction in the number of function evaluations instead of the iteration count.
* For polynomials, the evaluation of the first derivatives of at using the
Horner method
In mathematics and computer science, Horner's method (or Horner's scheme) is an algorithm for polynomial evaluation. Although named after William George Horner, this method is much older, as it has been attributed to Joseph-Louis Lagrange by H ...
has an effort of polynomial evaluations. Since evaluations over iterations give an error exponent of , the exponent for one function evaluation is