Math 2.0

Numerical analysis Nonlinear equations Theorem

Halley's method

Builds on Newton's methodRate of convergenceDerivative

Statement

Let ff be a real function that is three 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. Halley's method is the iteration xn+1=xn−2f(xn)f′(xn)2f′(xn)2−f(xn)f′′(xn).x_{n+1} = x_n - \frac{2 f(x_n) f'(x_n)}{2 f'(x_n)^2 - f(x_n) f''(x_n)}. 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. The convergence has order at least 33: ∣xn+1−r∣≤C∣xn−r∣3\abs{x_{n+1} - r} \le C \abs{x_n - r}^3 for some constant CC and all nn.

Remarks

The step is Newton's method applied to g=f/∣f′∣g = f / \sqrt{\abs{f'}}. At a simple zero, gg has the zero rr and satisfies g′′(r)=0g''(r) = 0, and Newton's method on such a function converges cubically. The same formula can be written xn+1=xn−f/f′1−ff′′/(2f′2)x_{n+1} = x_n - \dfrac{f/f'}{1 - f f''/(2 f'^2)}, evaluated at xnx_n. Here f′f' is the derivative of ff. For f(x)=x2−af(x) = x^2 - a with a>0a > 0, the method gives xn+1=xnxn2+3a3xn2+ax_{n+1} = x_n \dfrac{x_n^2 + 3a}{3x_n^2 + a}, which roughly triples the number of correct digits of a\sqrt{a} per step near the root. At a multiple zero the order of convergence drops to 11.

Going deeper

For a student

Each step costs one evaluation of ff, f′f' and f′′f''. So it pays off when the second derivative is cheap, as for polynomials. It is the case d=2d = 2 of the Householder family of methods, whose case d=1d = 1 is Newton's method.

Reading path

To understand this page from the ground up, read these 7 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 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

Where this leads

1 page builds on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Halley%27s_method
About this page
TagRPME2B5MS2
URIm2://RPME2B5MS2
Kindstatement, theorem
WritingW0 stub
MSC65H05
StatusThis copy of the site has no build data. Run m2 status RPME2B5MS2.
AboutNewton's method
UsesNewton'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

Results about this

Used by