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: for some 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. For polynomials, the evaluation of the first d derivatives of f at xn using the Horner method has an effort of d + 1 polynomial evaluations. Since n(d + 1) evaluations over n iterations give an error exponent of (d + 1)n, the exponent for one function evaluation is , numerically 1.4142, 1.4422, 1.4142, 1.3797 for d = 1, 2, 3, 4, and falling after that. By this criterion, the d=2 case (Halley's method) is the optimal value of d. For general functions the derivative evaluation using the Taylor arithmetic of automatic differentiation requires the equivalent of (d + 1)(d + 2)/2 function evaluations. One function evaluation thus reduces the error by an exponent of , which is for Newton's method, for Halley's method and falling towards 1 or linear convergence for the higher order methods.