Laguerre's method

In numerical analysis, Laguerre's method is a root-finding algorithm tailored to polynomials. In other words, Laguerre's method can be used to solve numerically the equation

p(x) = 0

for a given polynomial p.

Definition

Let x₀ be an initial guess for the root to be determined. Laguerre's method tries to improve this approximation iteratively by using the recurrence relation

$x_{k+1}=x_{k}-{\frac {n}{S_{1}(x_{k})\pm {\sqrt {(1-n)(nS_{2}(x_{k})+S_{1}^{2}(x_{k}))}}}},$

where the ± in the denominator is + or − according to which alternative yields the denominator with greater modulus. Furthermore, n denotes the degree of the polynomial p and S₁ and S₂ are the first and second logarithmic derivatives of p, i.e.

$S_{1}(x)={\frac {d}{dx}}\log p(x)={\frac {p'(x)}{p(x)}}$

$S_{2}(x)={\frac {d^{2}}{dx^{2}}}\log p(x)={\frac {p''(x)}{p(x)}}-\left({\frac {p'(x)}{p(x)}}\right)^{2}.$

Properties

If x is a simple root of the polynomial p, then Laguerre's method converges cubically whenever the initial guess x₀ is close enough to the root x. On the other hand, if x is a multiple root then the convergence is only linear.

This means that Laguerre's method converges even faster than Newton's method. However, Laguerre's method requires one to compute the first and the second derivative of p, while Newton's method requires only one derivative.

Laguerre's method also works for polynomials with real coefficients that have complex roots. Even if the initial guess is real, then the method will step off the real axis if the expression under the root sign is negative. This is in contrast to Newton's method, which will always stay on the real axis in this case.

References

• S. Goedecker, Remark on Algorithms to Find Roots of Polynomials, SIAM J. Sci. Comput. 15(5), 1059–1063 (September 1994).
• Wankere R. Mekwi (2001). Iterative Methods for Roots of Polynomials. Master's thesis, University of Oxford.
• V. Y. Pan, Solving a Polynomial Equation: Some History and Recent Progress, SIAM Rev. 39(2), 187–220 (June 1997).