Automatic differentiation using dual numbers

[Albert Chan]

(06-22-2022 10:36 PM)Thomas Klemm Wrote:  Halley's Method

It's straightforward to implement Halley's method:

\(
\begin{align}
x_{{n+1}}=x_{n}-{\frac{2f(x_{n})f'(x_{n})}{2{[f'(x_{n})]}^{2}-f(x_{n})f''(x_{n})}}
\end{align}
\)

However we rather use this formula:

\(
\begin{align}
x_{n+1}
&=x_{n}-{\frac {f(x_{n})}{f'(x_{n})-{\frac {f(x_{n})}{f'(x_{n})}}{\frac {f''(x_{n})}{2}}}} \\
&=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\left[1-{\frac {f(x_{n})}{f'(x_{n})}}\cdot {\frac {f''(x_{n})}{2f'(x_{n})}}\right]^{-1} \\
\end{align}
\)

Is correction factor to Newton's always positive ?
How do we ensure Halley's method is safe to use ?

I've seen some page (search for householder) flip the correction: 1/(1-ε) ≈ 1+ε
Correction is less aggressive, but safer (if f'≠0, no division by zero problem)

\( \displaystyle
x_{n+1}
=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}\left[1+{\frac {f(x_{n})}{f'(x_{n})}}\cdot {\frac {f''(x_{n})}{2f'(x_{n})}}\right]
\)