A root-finding algorithm which converges to a complex root from any starting position. To motivate the formula, consider an th order polynomial and its derivatives,
(1)
| |||
(2)
| |||
(3)
| |||
(4)
|
Now consider the logarithm and logarithmic derivatives of
(5)
| |||
(6)
| |||
(7)
| |||
(8)
| |||
(9)
| |||
(10)
|
Now make "a rather drastic set of assumptions" that the root being sought is a distance from the current best guess, so
(11)
|
while all other roots are at the same distance , so
(12)
|
for , 3, ..., (Acton 1990; Press et al. 1992, p. 365). This allows and to be expressed in terms of and as
(13)
| |||
(14)
|
Solving these simultaneously for gives
(15)
|
where the sign is taken to give the largest magnitude for the denominator.
To apply the method, calculate for a trial value , then use as the next trial value, and iterate until becomes sufficiently small. For example, for the polynomial with starting point , the algorithmic converges to the real root very quickly as (, , ).
Setting gives Halley's irrational formula.