---
tag: Q390KATZ87
kind: statement
role: theorem
name: Householder's method
msc: [65H05]
uses: [07EXVNF9VP, RPME2B5MS2, YWZQC5E54B, 0F1WR9C83K]
about: [07EXVNF9VP, RPME2B5MS2]
sources:
  - url: https://en.wikipedia.org/wiki/Householder%27s_method
same_as:
  wikidata: Q1631446
  wikipedia: Householder's method
---

## Statement

Let $d \ge 1$ be an integer.
Let $f$ be a real function that is $d + 1$ times continuously differentiable on an open interval $I$.
Let $r \in I$ be a simple zero of $f$, that is, $f(r) = 0$ and $f'(r) \ne 0$.
*Householder's method of order $d + 1$* is the iteration
$$x_{n+1} = x_n + d \, \frac{(1/f)^{(d-1)}(x_n)}{(1/f)^{(d)}(x_n)},$$
where $(1/f)^{(k)}$ is the $k$-th [[derivative|0F1WR9C83K]] of the function $1/f$.
Then there is $\delta > 0$ such that for every $x_0$ with $\abs{x_0 - r} < \delta$ the iterates are defined and [[converge|YWZQC5E54B]] to $r$ with order $d + 1$.

## Remarks

For $d = 1$ the formula gives $x_{n+1} = x_n - f(x_n)/f'(x_n)$, which is [[Newton's method|07EXVNF9VP]].
For $d = 2$ it gives [[Halley's method|RPME2B5MS2]].
The idea of the proof: near $r$, the function $1/f$ has a simple pole at $r$, so it equals $c/(x - r)$ plus a function that is smoother at $r$.
For the pole part alone, the ratio of consecutive derivatives gives exactly $-(x - r)/d$, so the step lands on $r$.
The remainder adds an error of size $O(\abs{x - r}^{d+1})$.
The hypothesis $f'(r) \ne 0$ is needed: at a multiple zero the pole of $1/f$ has higher order and the convergence becomes linear.

## Explanations

### L1 human

Householder's methods form a ladder of root-finding methods.
The rung $d$ uses derivatives of $f$ up to order $d$, and near a simple root it multiplies the number of correct digits by about $d + 1$ at each step.
The first rung is Newton's method and the second is Halley's method.

### L2 human

Higher order does not always mean less work, because each step needs more derivatives.
In practice $d = 1$ or $d = 2$ is used, unless the derivatives come almost for free.
The formula is a convenient way to see all these methods as one family built on the reciprocal $1/f$.