Halley's Method

Proof Technique

Halley's Method is a method of solving an equation $\map f x = 0$ involving the real function $f$ for which there may be no convenient closed form solution.

The derivative and the second derivative of $f$ have to be known in order to use Halley's Method.

Let $x_0$ be an initial guess.

Halley's Method uses the iteration:

$x_{n + 1} = x_n - \dfrac {\map f {x_n} } {\map {f'} {x_n} - \dfrac {\map f {x_n} \map {f} {x_n} } {2 \map {f'} {x_n} } }$

where:

$\map {f'} {x_n}$ is the derivative of $f$ with respect to $x$ evaluated at $x_n$

$\map {f} {x_n}$ is the second derivative of $f$ with respect to $x$ evaluated at $x_n$.

Proof

The function $\map f x$ can be expanded about $x_n$ using Taylor's Theorem:

$\map f x = \map f {x_n} + \map {f'} {x_n} \paren {x - x_n} + \dfrac 1 2 \map {f} {x_n} \paren {x - x_n}^2 + \dotsb$

This series can be rewritten with an error term as follows:

\(\ds \map f x\)

\(=\)

\(\ds \map f {x_n} + \map {f'} {x_n} \paren {x - x_n} + \dfrac 1 2 \map {f} {x_n} \paren {x - x_n}^2 + \dotsb\)

Taylor's Theorem

\(\ds \leadsto \ \ \)

\(\ds \map f x\)

\(=\)

\(\ds \map f {x_n} + \map {f'} {x_n} \paren {x - x_n} + \dfrac 1 2 \map {f} {x_n} \paren {x - x_n}^2 + \epsilon\)

for some small $\epsilon \in \R$

\(\ds \leadsto \ \ \)

\(\ds \paren {x - x_n} \paren {\map {f'} {x_n} + \dfrac 1 2 \map {f} {x_n} \paren {x - x_n} }\)

\(=\)

\(\ds \map f x - \map f {x_n} - \epsilon\)

rearranging

\(\ds \leadsto \ \ \)

\(\ds x - x_n\)

\(=\)

\(\ds \dfrac {\map f x - \map f {x_n} - \epsilon} {\map {f'} {x_n} + \dfrac 1 2 \map {f} {x_n} \paren {x - x_n} }\)

\(\ds \)

\(=\)

\(\ds \dfrac {\map f x} {\map {f'} {x_n} + \dfrac 1 2 \map {f} {x_n} \paren {x - x_n} } - \dfrac {\map f {x_n} } {\map {f'} {x_n} + \dfrac 1 2 \map {f} {x_n} \paren {x - x_n} } - \dfrac \epsilon {\map {f'} {x_n} + \dfrac 1 2 \map {f} {x_n} \paren {x - x_n} }\)

This needs considerable tedious hard slog to complete it. In particular: approximations need to be made, need to establish the range of values $\epsilon$ can take, all of which takes work. Lemmata to be structured. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Finish}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Historical Note

Halley's Method was devised by Edmund Halley in $1694$.

It uses a similar technique to Newton's Method, and has a faster speed of convergence.

However, this is at the cost of more computation per iteration.

Also see

• Newton's Method, which is slower but uses less computation per iteration

Source of Name

This entry was named for Edmund Halley.

Sources

• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): Halley's method
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Halley's method