Laguerre's method

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". 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. This method is named in honour of Edmond Laguerre, a French mathematician.

Derivation

The fundamental theorem of algebra states that every "n"th degree polynomial "p" can be written in the form

:p(x) = C(x - x_1)(x - x_2)cdots(x - x_n),

where "x""k" 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| + cdots + ln |x - x_n|.

Denote the derivative by

:G = frac{d}{dx} ln |p(x)| = frac{1}{x - x_1} + frac{1}{x - x_2} + cdots + frac{1}{x - x_n},

and the second derivative by

: H = -frac{d^2}{dx^2} ln |p(x)|= frac{1}{(x - x_1)^2} + frac{1}{(x - x_2)^2} + cdots + frac{1}{(x - x_n)^2}.

We then make what Acton calls a 'drastic set of assumptions', that the root we are looking for, say, x_1 is a certain distance away from our guess x, and all the other roots are clustered together some distance away. If we denote these distances by:a = x - x_1 ,and:b = x - x_i,quad i = 2, 3,ldots, nthen our equation for "G" may be written:G = frac{1}{a} + frac{n - 1}{b}and that for "H" becomes:H = frac{1}{a^2} + frac{n-1}{b^2}.Solving these equations, we find that:a = frac{n}{G plusmn sqrt{(n-1)(nH - G^2).

Definition

The above derivation leads to the following method:
* Choose an initial guess x_0
* For "k" = 0, 1, 2, …
** Calculate G = frac{p'(x_k)}{p(x_k)}
** Calculate H = G^2 - frac{p"(x_k)}{p(x_k)}
** Calculate a = frac{n}{G plusmn sqrt{(n-1)(nH - G^2) , where the sign is chosen to give the denominator with the larger absolute value, to avoid loss of significance as iteration proceeds.
** Set x_{k+1} = x_k - a
* Repeat until "a" is small enough or if the maximum number of iterations has been reached.

Properties

If "x" is a simple root of the polynomial "p", then Laguerre's method converges cubically whenever the initial guess "x"0 is close enough to the root "x". On the other hand, if "x" is a multiple root then the convergence is only linear. This is obtained with the penalty of calculating values for the polynomial and its first and second derivatives at each stage of the iteration.

A major advantage of Laguerre's method is that it is almost guaranteed to converge to "some" root of the polynomial "no matter where the initial approximation is chosen". This is in contrast to other methods such as the Newton-Raphson method which may fail to converge for poorly chosen initial guesses. It may even converge to a complex root of the polynomial, because of the square root being taken in the calculation of "a" above may be of a negative number. This may be considered an advantage or a liability depending on the application to which the method is being used. Empirical evidence has shown that convergence failure is extremely rare, making this a good candidate for a general purpose polynomial root finding algorithm. However, given the fairly limited theoretical understanding of the algorithm, many numerical analysts are hesitant to use it as such, and prefer better understood methods such as the Jenkins-Traub method, for which more solid theory has been developed. Nevertheless, the algorithm is fairly simple to use compared to these other "sure-fire" methods, easy enough to be used by hand or with the aid of a pocket calculator when an automatic computer is unavailable. The speed at which the method converges means that one is only very rarely required to compute more than a few iterations to get high accuracy.

References

* Forman S. Acton, "Numerical Methods that Work", Harper & Row, 1970, ISBN 0-88385-450-3.
* S. Goedecker, Remark on Algorithms to Find Roots of Polynomials, [http://epubs.siam.org/sam-bin/dbq/toclist/SISC "SIAM J. Sci. Comput."] 15(5), 1059–1063 (September 1994).
* Wankere R. Mekwi (2001). [http://eprints.maths.ox.ac.uk/archive/00000016/ Iterative Methods for Roots of Polynomials] . Master's thesis, University of Oxford.
* V. Y. Pan, Solving a Polynomial Equation: Some History and Recent Progress, [http://epubs.siam.org/sam-bin/dbq/toclist/SIREV "SIAM Rev."] 39(2), 187–220 (June 1997).
* Anthony Ralston and Philip Rabinowitz, "A First Course in Numerical Analysis", McGraw-Hill, 1978, ISBN 0-07-051158-6.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Laguerre polynomials — In mathematics, the Laguerre polynomials, named after Edmond Laguerre (1834 ndash; 1886), are the canonical solutions of Laguerre s equation::x,y + (1 x),y + n,y = 0,which is a second order linear differential equation.This equation has… …   Wikipedia

  • Méthode de Laguerre — En analyse numérique, la méthode de Laguerre est un algorithme de recherche d un zéro d une fonction polynomiale. En d autres termes, elle peut être utilisée pour trouver une valeur approchée d un solution d une équation de la forme p(x) = 0, où… …   Wikipédia en Français

  • Gauss–Laguerre quadrature — In numerical analysis Gauss–Laguerre quadrature is an extension of Gaussian quadrature method for approximating the value of integrals of the following kind::int {0}^{+infty} e^{ x} f(x),dx.In this case :int {0}^{+infty} e^{ x} f(x),dx approx sum …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • List of mathematics articles (L) — NOTOC L L (complexity) L BFGS L² cohomology L function L game L notation L system L theory L Analyse des Infiniment Petits pour l Intelligence des Lignes Courbes L Hôpital s rule L(R) La Géométrie Labeled graph Labelled enumeration theorem Lack… …   Wikipedia

  • Root-finding algorithm — A root finding algorithm is a numerical method, or algorithm, for finding a value x such that f(x) = 0, for a given function f. Such an x is called a root of the function f. This article is concerned with finding scalar, real or complex roots,… …   Wikipedia

  • Polynomial — In mathematics, a polynomial (from Greek poly, many and medieval Latin binomium, binomial [1] [2] [3], the word has been introduced, in Latin, by Franciscus Vieta[4]) is an expression of finite length constructed from variables (also known as… …   Wikipedia

  • Quintic equation — In mathematics, a quintic equation is a polynomial equation of degree five. It is of the form::ax^5+bx^4+cx^3+dx^2+ex+f=0, where a e 0.(if a = 0, then the equation becomes a quartic equation). (if a and b = 0, then the equation becomes a cubic… …   Wikipedia

  • Optical tweezers — (originally called single beam gradient force trap ) are scientific instruments that use a highly focused laser beam to provide an attractive or repulsive force (typically on the order of piconewtons), depending on the refractive index mismatch… …   Wikipedia

  • Théorie des équations (mathématiques) — Pour les articles homonymes, voir Théorie des équations. La théorie des équations est la partie des mathématiques qui traite des problèmes posés par les équations polynomiales de tous les degrés. Se trouvent ainsi rassemblés les problèmes de… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”