In numerical analysis, Laguerre's method is a root-finding algorithm tailored to polynomials. In other words, Laguerre's method can be used to numerically solve the equation p(x) = 0 for a given polynomial p(x). One of the most useful properties of this method is that it is, from extensive empirical study, very close to being a "sure-fire" method, meaning that it is almost guaranteed to always converge to some root of the polynomial, no matter what initial guess is chosen. However, for computer computation, more efficient methods are known, with which it is guaranteed to find all roots (see Root-finding algorithm § Roots of polynomials) or all real roots (see Real-root isolation). This method is named in honour of the French mathematician, Edmond Laguerre.
Definition The algorithm of the Laguerre method to find one root of a polynomial p(x) of degree n is:
Choose an initial guess x0 For k = 0, 1, 2, ... If p ( x k ) {\displaystyle p(x_{k})} is very small, exit the loop Calculate G = p ′ ( x k ) p ( x k ) {\displaystyle G={\frac {p'(x_{k})}{p(x_{k})}}}
Calculate H = G 2 − p ″ ( x k ) p ( x k ) {\displaystyle H=G^{2}-{\frac {p''(x_{k})}{p(x_{k})}}}
Calculate a = n G ± ( n − 1 ) ( n H − G 2 ) {\displaystyle a={\frac {n}{G\pm {\sqrt {(n-1)(nH-G^{2})}}}}} , where the sign is chosen to give the denominator with the larger absolute value, to avoid catastrophic cancellation. Set x k + 1 = x k − a {\displaystyle x_{k+1}=x_{k}-a}
Repeat until a is small enough or if the maximum number of iterations has been reached. If a root has been found, the corresponding linear factor can be removed from p. This deflation step reduces the degree of the polynomial by one, so that eventually, approximations for all roots of p can be found. Note however that deflation can lead to approximate factors that differ significantly from the corresponding exact factors. This error is least if the roots are found in the order of increasing magnitude.
Derivation The fundamental theorem of algebra states that every nth degree polynomial p {\displaystyle p} can be written in the form
p ( x ) = C ( x − x 1 ) ( x − x 2 ) ⋯ ( x − x n ) , {\displaystyle p(x)=C\left(x-x_{1}\right)\left(x-x_{2}\right)\cdots \left(x-x_{n}\right),}
so that x 1 , x 2 , … , x n , {\displaystyle x_{1},\ x_{2},\ \ldots ,\ x_{n},} are the roots of the polynomial. If we take the natural logarithm of both sides, we find that
ln | p ( x ) | = ln | C | + ln | x − x 1 | + ln | x − x 2 | + ⋯ + ln | x − x n | . {\displaystyle \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 |}.}
Denote the logarithmic derivative by
… excerpt ends here. Continue reading the full article.
