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 methods refer to different root-finding algorithms: one that uses the derivatives of f(x) with d + 1 convergence order, and one that uses another modification of Halley's and Newton's methods, with cubic convergence order.

History

From "On Schröder's Families of Root-finding methods": "In 1953 Householder presented a family of iteration methods x_k+1 = K_m(x_k) := x_k + (m - 1)[(1/f(x_k))^(m-2)/(1/f(x_k))^(m-1)] (m = 2, 3, ...; k = 0, 1, ...) of the order m." It cites "Principles of Numerical Analysis" by Householder.

The second method

From "Newton's method and high order iterations" (http://numbers.computation.free.fr/Constants/Algorithms/newton.html#Householder): "The previous expression for h, allows to derive the following cubic iteration (the number of digits triples at each iteration), starting with x0

x_n+1 = x_n - f(x_n)/f'(x_n) (1 + (f(x_n)f''(x_n))/(2f'(x_n)^2)).

This procedure is given in A. S. Householder's "The Numerical Treatment of a Single Nonlinear Equation" (1970)."

A modified method

Again from: "Newton's method and high order iterations" (http://numbers.computation.free.fr/Constants/Algorithms/newton.html), section 4.2:

"Another idea is to write

x_n+1 = x_n + h_n + a2^n ((h_n^2)/2!) + a3^n ((h_n^3)/3!) + ...

where h_n = -f(x_n)/f'(x_n) is given by the simple Newton iteration and (a2^n, a3^n, ...) are real parameters which we will estimate in order to minimize the value of f(x_n+1):

f(x_n+1) = f(x_n + h_n + a2^n ((h_n^2)/2!) + a3^n ((h_n^3)/3!) + ...),

we assume that f is regular enough and h_n + a_2^n h_n^2/2! + a_3^n h_n^3/3! + ... is small, hence using the expansion of f near x_n

f(x_n+1) = f(x_n)+(x_n + h_n + a2^n ((h_n^2)/2!) + a3^n ((h_n^3)/3!) + ...) f'(x_n) + (x_n + h_n + a2^n ((h_n^2)/2!) + a3^n ((h_n^3)/3!) + ...)^2 (f''(x_n)/2) + ...,

and because f(x_n) + h_n f'(x_n) = 0, we have

f(x_n+1) = (a2^n f'(x_n) + f''(x_n)) h_n^2/2! + (a3^n f'(x_n) + 3a_2^n f''(x_n)+f^(3)(x_n)) h_n^3/3! + O(h_n^4).

A good choice for the a_i^n is clearly to cancel as many terms as possible in the previous expansion, so we impose

a_2^n = -f''_n/f'_n

a_3^n = (-f'_n f'''_n + 3(f''_n)^2)/((f'_n)^2)

a_4^n = ...

with, for the sake of brevity, the notation f_n^(k) = f^(k)(x_n)."

More here: http://numbers.computation.free.fr/Constants/Algorithms/newton.html#Householder