Editing Laguerre's method (section)

==Derivation==
The [[fundamental theorem of algebra]] states that every {{mvar|n}}th degree polynomial <math> p </math> can be written in the form

:<math>p(x) = C \left( x - x_1 \right) \left( x - x_2 \right) \cdots \left(x - x_n \right) ,</math>

so that <math>x_1,\ x_2,\ \ldots,\ x_n ,</math> are the roots of the polynomial. If we take the [[natural logarithm]] of both sides, we find that

:<math>\ln \bigl| p(x) \bigr| = \ln \bigl| C \bigr| + \ln \bigl| x - x_1 \bigr| + \ln \bigl| x - x_2 \bigr| + \cdots + \ln \bigl| x - x_n \bigr|.</math>

Denote the [[logarithmic derivative]] by

: <math>\begin{align}
G &= \frac{ \operatorname{d} }{ \operatorname{d} x } \ln \Bigl| p(x) \Bigr| = \frac{ 1 }{ x - x_1 } + \frac{ 1 }{ x - x_2 } + \cdots + \frac{ 1 }{ x - x_n } \\
 &= \frac{ p'(x) }{ \bigl| p(x) \bigr| } ,
\end{align}</math>

and the negated second derivative by
:<math>\begin{align}
\ H &= -\frac{ \operatorname{d}^2 }{ \operatorname{d} x^2 } \ln \Bigl| p(x) \Bigr| = \frac{ 1 }{ (x - x_1)^2 } + \frac{ 1 }{ (x - x_2)^2 } + \cdots + \frac{ 1 }{ (x - x_n)^2 } \\
 &= -\frac{ p''(x) }{ \bigl| p(x) \bigr| } + \left( \frac{ p'(x) }{ p(x) } \right)^2 \cdot\ \sgn\!\Bigl( p(x) \Bigr) 
.\end{align}</math>

We then make what {{harvp|Acton|1970}}{{page needed|date=August 2024}} calls a "drastic set of assumptions", that the root we are looking for, say, <math>x_1 </math> is a short distance, <math>a,</math> away from our guess <math>x,</math> and all the other roots are all clustered together, at some further distance <math>b.</math> If we denote these distances by
:<math> a \equiv x - x_1 </math>
and
: <math> b \approx x - x_2 \approx x - x_3 \approx \cdots \approx x - x_n ,</math>
or exactly,
: <math>b \equiv \operatorname{harmonic\ mean}\Bigl\{ x - x_2,\ x - x_3,\ \ldots\ x - x_n \Bigr\} </math>

then our equation for <math>\ G\ </math> may be written as
:<math> G = \frac{ 1 }{ a } + \frac{ n - 1 }{ b } </math>
and the expression for <math>H </math> becomes
:<math> H = \frac{ 1 }{ a^2 } + \frac{ n - 1 }{ b^2 }.</math>
Solving these equations for <math>a,</math> we find that
:<math> a = \frac{ n }{ G \plusmn \sqrt{\bigl( n - 1 \bigr)\bigl( n H - G^2 \bigr) } } ,</math>
where in this case, the square root of the (possibly) [[complex number]] is chosen to produce largest absolute value of the denominator and make <math>\ a\ </math> as small as possible; equivalently, it satisfies:
:<math> \operatorname\mathcal{R_e} \biggl\{ \overline{G} \sqrt{ \left( n - 1 \right) \left( n H - G^2\right) } \biggr\} > 0 ,</math>
where <math>\mathcal{R_e} </math> denotes real part of a complex number, and <math>\overline{G} </math> is the complex conjugate of <math>G;</math> or
:<math> a = \frac{ p(x) }{ p'(x) } \cdot \Biggl\{ \frac{ 1 }{ n } + \frac{ n - 1 }{ n } \sqrt{ 1 - \frac{ n }{ n-1 } \frac{ p(x)\ p''(x) }{p'(x)^2 }} \Biggr\}^{-1},</math>
where the square root of a complex number is chosen to have a non-negative real part.

For small values of <math>p(x) </math> this formula differs from the offset of the third order [[Halley's method]] by an error of <math>\operatorname\mathcal{O}\bigl\{(p(x))^3\bigr\},</math> so convergence close to a root will be cubic as well. 

===Fallback===
Even if the "drastic set of assumptions" does not work well for some particular polynomial {{math|''p''(''x'')}}, then {{math|''p''(''x'')}} can be transformed into a related polynomial {{mvar|r}} for which the assumptions are viable; e.g. by first shifting the origin towards a suitable complex number {{mvar|w}}, giving a second polynomial {{math|''q''(''x'') {{=}} ''p''(''x'' − ''w'')}}, that give distinct roots clearly distinct magnitudes, if necessary (which it will be if some roots are complex conjugates).

After that, getting a third polynomial {{mvar|r}} from {{math|''q''(''x'')}} by repeatedly applying the root squaring transformation from [[Graeffe's method]], enough times to make the smaller roots significantly smaller than the largest root (and so, clustered comparatively nearer to zero). The approximate root from Graeffe's method, can then be used to start the new iteration for Laguerre's method on {{mvar|r}}. An approximate root for {{math|''p''(''x'')}} may then be obtained straightforwardly from that for {{mvar|r}}.

If we make the even more extreme assumption that the terms in <math>G </math> corresponding to the roots <math>x_2,\ x_3,\ \ldots,\ x_n </math> are negligibly small compared to the root <math>x_1,</math> this leads to [[Newton's method]].