info prev up next book cdrom email home

Laguerre's Method

A Root-finding algorithm which converges to a Complex Root from any starting position.

\end{displaymath} (1)

\ln\vert P_n(x)\vert = \ln\vert x-x_1\vert+\ln\vert x-x_2\vert+\ldots+\ln\vert x-x_n\vert
\end{displaymath} (2)

$\displaystyle P'_n(x)$ $\textstyle =$ $\displaystyle (x-x_2)\cdots(x-x_n)+(x-x_1)\cdots(x-x_n)+\ldots$  
  $\textstyle =$ $\displaystyle P_n(x)\left({{1\over x-x_1}+\ldots+{1\over x-x_n}}\right)$ (3)

$\displaystyle {d\ln\vert P_n(x)\vert\over dx}$ $\textstyle =$ $\displaystyle {1\over x-x_1}+{1\over x-x_2}+\ldots+{1\over x-x_n}$  
  $\textstyle =$ $\displaystyle {P_n'(x)\over P_n(x)}\equiv G(x)$ (4)

$\displaystyle -{d^2\ln\vert P_n(x)\vert\over dx^2}$ $\textstyle =$ $\displaystyle {1\over (x-x_1)^2}+{1\over (x-x_2)^2}+\ldots+ {1\over(x-x_n)^2}$  
  $\textstyle =$ $\displaystyle \left[{P_n'(x)\over P_n(x)}\right]^2-{P_n''(x)\over P_n(x)}\equiv H(x).$ (5)

Now let $a\equiv x-x_1$ and $b\equiv x-x_1$. Then
G\equiv {1\over a}+{n-1\over b}
\end{displaymath} (6)

H\equiv {1\over a^2}+{n-1\over b^2},
\end{displaymath} (7)

a={n\over {\rm max}\left[{G\pm\sqrt{(n-1)(nH-G^2)}\,}\right]}.
\end{displaymath} (8)

Setting $n=2$ gives Halley's Irrational Formula.

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


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.

© 1996-9 Eric W. Weisstein