Math 2.0

Numerical analysis Nonlinear equations Theorem

Householder's method

Builds on Newton's methodHalley's methodRate of convergenceDerivative

Statement

Let d≥1d \ge 1 be an integer. Let ff be a real function that is d+1d + 1 times continuously differentiable on an open interval II. Let r∈Ir \in I be a simple zero of ff, that is, f(r)=0f(r) = 0 and f′(r)≠0f'(r) \ne 0. Householder's method of order d+1d + 1 is the iteration xn+1=xn+d (1/f)(d−1)(xn)(1/f)(d)(xn),x_{n+1} = x_n + d \, \frac{(1/f)^{(d-1)}(x_n)}{(1/f)^{(d)}(x_n)}, where (1/f)(k)(1/f)^{(k)} is the kk-th derivative of the function 1/f1/f. Then there is δ>0\delta > 0 such that for every x0x_0 with ∣x0−r∣<δ\abs{x_0 - r} < \delta the iterates are defined and converge to rr with order d+1d + 1.

Remarks

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

Going deeper

For a student

Higher order does not always mean less work, because each step needs more derivatives. In practice d=1d = 1 or d=2d = 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/f1/f.

Reading path

To understand this page from the ground up, read these 8 pages in order. The foundations come first.

Show the path as a graph
Limit point of a set, definition, no evidence levelLimit point of a setdefinitionRate of convergence, concept, no evidence levelRate of convergenceconceptLimit of a function, definition, no evidence levelLimit of a functiondefinitionDerivative, definition, no evidence levelDerivativedefinitionTangent line, concept, no evidence levelTangent lineconceptNewton's method, concept, no evidence levelNewton's methodconceptHalley's method, statement, no evidence levelHalley's methodstatementHouseholder's method, statement, no evidence levelHouseholder's methodstatement
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Limit point of a set definition
  2. Rate of convergence concept
  3. Limit of a function definition
  4. Derivative definition
  5. Tangent line concept
  6. Newton's method concept
  7. Halley's method statement
  8. Householder's method statement

Further reading

  1. Web https://en.wikipedia.org/wiki/Householder%27s_method
About this page
TagQ390KATZ87
URIm2://Q390KATZ87
Kindstatement, theorem
WritingW0 stub
MSC65H05
StatusThis copy of the site has no build data. Run m2 status Q390KATZ87.
AboutNewton's method, Halley's method
UsesNewton's method, Halley's method, Rate of convergence, Derivative
Same as

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.