Automatic differentiation using dual numbers

[Albert Chan]

If guess is close to root, we can consider f as the independent variable.

x = x0 + (dx/df)(f=f0) * (f-f0)/1! + (d²x/df²)(f=f0) * (f-f0)²/2! + ...

dx/df = 1 / (df/dx) = 1/f'
d²x/df² = d/df (dx/df) = d/dx (1/f') * dx/df = (-f''/f'^2) / f' = -f''/f'^3

Solving root is simplify x at f=0, with iteration formula:

x ← x + (1/f')*(-f) + (-f''/f'^3)*(f^2/2) + ... = x - f/f' - (f^2*f'')/(2*f'^3) + ...

Drop ... = O(f^3), we have:

(06-25-2022 11:05 AM)Albert Chan Wrote:  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]
\)