Laguerre's Method

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

$\begin{displaymath} P_n(x)=(x-x_1)(x-x_2)\cdots(x-x_n) \end{displaymath}$

(1)

$\begin{displaymath} \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

$\begin{displaymath} G\equiv {1\over a}+{n-1\over b} \end{displaymath}$

(6)

$\begin{displaymath} H\equiv {1\over a^2}+{n-1\over b^2}, \end{displaymath}$

(7)

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

(8)

Setting

References

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.