TOPICS
Search

Laguerre's Method


A root-finding algorithm which converges to a complex root from any starting position. To motivate the formula, consider an nth order polynomial and its derivatives,

P_n(x)=(x-x_1)(x-x_2)...(x-x_n)
(1)
P_n^'(x)=(x-x_2)...(x-x_n)+(x-x_1)...(x-x_n)+...
(2)
(3)
=P_n(x)(1/(x-x_1)+...+1/(x-x_n)).
(4)

Now consider the logarithm and logarithmic derivatives of P_n(x)

ln|P_n(x)|=ln|x-x_1|+ln|x-x_2|+...+ln|x-x_n|
(5)
(dln|P_n(x)|)/(dx)=1/(x-x_1)+1/(x-x_2)+...+1/(x-x_n)
(6)
=(P_n^'(x))/(P_n(x))
(7)
=G(x)
(8)
-(d^2ln|P_n(x)|)/(dx^2)=1/((x-x_1)^2)+1/((x-x_2)^2)+...+1/((x-x_n)^2)
(9)
=[(P_n^'(x))/(P_n(x))]^2-(P_n^('')(x))/(P_n(x))=H(x).
(10)

Now make "a rather drastic set of assumptions" that the root x_1 being sought is a distance a from the current best guess, so

 a=x-x_1,
(11)

while all other roots are at the same distance b, so

 b=x-x_i
(12)

for i=2, 3, ..., n (Acton 1990; Press et al. 1992, p. 365). This allows G and H to be expressed in terms of a and b as

G=1/a+(n-1)/b
(13)
H=1/(a^2)+(n-1)/(b^2),
(14)

Solving these simultaneously for a gives

 a=n/(max[G+/-sqrt((n-1)(nH-G^2))]),
(15)

where the sign is taken to give the largest magnitude for the denominator.

To apply the method, calculate a for a trial value x, then use x-a as the next trial value, and iterate until a becomes sufficiently small. For example, for the polynomial 4x^3+3x^2+2x+1 with starting point x_0=-1.0, the algorithmic converges to the real root very quickly as (-1.0, -0.58113883008419, -0.60582958618827).

Setting n=2 gives Halley's irrational formula.


See also

Halley's Irrational Formula, Halley's Method, Newton's Method, Root

Explore with Wolfram|Alpha

References

Acton, F. S. Numerical Methods That Work, 2nd printing. Washington, DC: Math. Assoc. Amer., 1990.Adams, D. A. "A Stopping Criterion for Polynomial Root Finding." Comm. ACM 10, 655-658, 1967.Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 365-366, 1992.Ralston, A. and Rabinowitz, P. §8.9-8.13 in A First Course in Numerical Analysis, 2nd ed. New York: McGraw-Hill, 1978.

Referenced on Wolfram|Alpha

Laguerre's Method

Cite this as:

Weisstein, Eric W. "Laguerre's Method." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/LaguerresMethod.html

Subject classifications