El método de Laguerre

Algoritmo para encontrar raíces polinómicas

En análisis numérico , el método de Laguerre es un algoritmo de búsqueda de raíces adaptado a polinomios . En otras palabras, el método de Laguerre se puede utilizar para resolver numéricamente la ecuación p ( x ) = 0 para un polinomio dado p ( x ) . Una de las propiedades más útiles de este método es que, a partir de un estudio empírico extenso, está muy cerca de ser un método "seguro", lo que significa que está casi garantizado que siempre convergerá a alguna raíz del polinomio, sin importar qué suposición inicial se elija. Sin embargo, para el cálculo computacional , se conocen métodos más eficientes, con los que se garantiza encontrar todas las raíces (ver Algoritmo de búsqueda de raíces § Raíces de polinomios ) o todas las raíces reales (ver Aislamiento de raíces reales ).

Este método recibe su nombre en honor al matemático francés Edmond Laguerre .

Definición

El algoritmo del método de Laguerre para encontrar una raíz de un polinomio p ( x ) de grado n es:

• Elija una suposición inicial x ₀
• Para k = 0, 1, 2, ...
  • Si es muy pequeño, salga del bucle. ${\displaystyle p(x_{k})}$
  • Calcular ${\displaystyle G={\frac {p'(x_{k})}{p(x_{k})}}}$
  • Calcular ${\displaystyle H=G^{2}-{\frac {p''(x_{k})}{p(x_{k})}}}$
  • Calcular , donde el signo se elige para dar el denominador con el valor absoluto mayor, para evitar una cancelación catastrófica . ${\displaystyle a={\frac {n}{G\pm {\sqrt {(n-1)(nH-G^{2})}}}}}$
  • Colocar ${\displaystyle x_{k+1}=x_{k}-a}$
• Repita hasta que a sea lo suficientemente pequeño o hasta que se haya alcanzado el número máximo de iteraciones.

Si se ha encontrado una raíz, se puede quitar el factor lineal correspondiente de p . Este paso de deflación reduce el grado del polinomio en uno, de modo que, finalmente, se pueden encontrar aproximaciones para todas las raíces de p . Sin embargo, tenga en cuenta que la deflación puede conducir a factores aproximados que difieren significativamente de los factores exactos correspondientes. Este error es mínimo si las raíces se encuentran en orden de magnitud creciente.

Derivación

El teorema fundamental del álgebra establece que todo polinomio de grado n puede escribirse en la forma ${\displaystyle \ p\ }$

${\displaystyle \ p(x)=C\left(x-x_{1}\right)\left(x-x_{2}\right)\ \cdots \ \left(x-x_{n}\right)\ ,}$

De modo que son las raíces del polinomio. Si tomamos el logaritmo natural de ambos lados, encontramos que ${\displaystyle \ x_{1},x_{2},\ \ldots ,\ 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 |}~.}$

Denotemos la derivada logarítmica por

${\displaystyle {\begin{aligned}\ G&~=~{\frac {\operatorname {d} }{\operatorname {d} x}}\ln {\Bigl |}\ p(x)\ {\Bigr |}~=~{\frac {1}{\ x-x_{1}\ }}+{\frac {1}{\ x-x_{2}\ }}+\ \cdots \ +{\frac {1}{\ x-x_{n}\ }}\\[0.3em]&~=~{\frac {\ p'(x)\ }{\ {\bigl |}\ p(x)\ {\bigr |}\ }}\ ,\end{aligned}}}$

y la segunda derivada negada por

${\displaystyle {\begin{aligned}\ H&~=~-{\frac {\operatorname {d} ^{2}}{\operatorname {d} x^{2}}}\ln {\Bigl |}\ p(x)\ {\Bigr |}~=~{\frac {1}{~~(x-x_{1})^{2}\ }}+{\frac {1}{~~(x-x_{2})^{2}\ }}+\ \cdots \ +{\frac {1}{~~(x-x_{n})^{2}\ }}\\[0.3em]&~=~-{\frac {\ p''(x)\ }{\ {\bigl |}\ p(x)\ {\bigr |}\ }}\ +\ \left({\frac {\ p'(x)\ }{\ p(x)\ }}\right)^{2}\cdot \ \operatorname {sgn} \!{\Bigl (}\ p(x)\ {\Bigr )}~.\end{aligned}}}$

Luego hacemos lo que Acton (1970) ^{[ página necesaria ]} llama un 'conjunto drástico de suposiciones' , que la raíz que estamos buscando, digamos, está a una distancia corta, lejos de nuestra suposición y todas las demás raíces están agrupadas juntas, a una distancia mayor. Si denotamos estas distancias por ${\displaystyle \ x_{1}\ }$ ${\displaystyle \ a\ ,}$ ${\displaystyle \ x\ ,}$ ${\displaystyle \ b~.}$

${\displaystyle \ a\ \equiv \ x-x_{1}\ }$

y

${\displaystyle \ b\ \approx \ x-x_{2}\ \approx \ x-x_{3}\ \approx \ \ldots \ \approx \ x-x_{n}\ ,}$

o exactamente,

${\displaystyle \ b\ \equiv \ \operatorname {\mathsf {harmonic\ mean}} {\Bigl \{}\ x-x_{2},\ x-x_{3},\ \ldots \ x-x_{n}\ {\Bigr \}}\ }$

Entonces nuestra ecuación para puede escribirse como ${\displaystyle \ G\ }$

${\displaystyle G={\frac {\ 1\ }{a}}+{\frac {\ n-1\ }{b}}}$

y la expresión para se convierte en ${\displaystyle \ H\ }$

${\displaystyle H={\frac {1}{~a^{2}\ }}+{\frac {\ n-1\ }{~b^{2}\ }}~.}$

Resolviendo estas ecuaciones encontramos que ${\displaystyle \ a\ ,}$

${\displaystyle a={\frac {n}{\ G\pm {\sqrt {{\bigl (}n-1{\bigr )}{\bigl (}n\ H-G^{2}{\bigr )}\ }}\ }}\ ,}$

donde en este caso, se elige la raíz cuadrada del número (posiblemente) complejo para producir el mayor valor absoluto del denominador y hacerlo lo más pequeño posible; equivalentemente, satisface: ${\displaystyle \ a\ }$

${\displaystyle \operatorname {\mathcal {R_{e}}} {\biggl \{}\ {\overline {G}}{\sqrt {\left(n-1\right)\left(n\ H-G^{2}\right)\ }}\ {\biggr \}}>0\ ,}$

donde denota la parte real de un número complejo, y es el conjugado complejo de o ${\displaystyle \ {\mathcal {R_{e}}}\ }$ ${\displaystyle \ {\overline {G}}\ }$ ${\displaystyle \ G\ ;}$

${\displaystyle a={\frac {\ p(x)\ }{p'(x)}}\cdot {\Biggl \{}\ {\frac {\ 1\ }{n}}+{\frac {\ n-1\ }{n}}\ {\sqrt {1-{\frac {n}{\ n-1\ }}\ {\frac {\ p(x)\ p''(x)\ }{~p'(x)^{2}\ }}\ }}\ {\Biggr \}}^{-1}\ ,}$

donde se elige que la raíz cuadrada de un número complejo tenga una parte real no negativa.

Para valores pequeños esta fórmula difiere del desplazamiento del método Halley de tercer orden por un error de modo que la convergencia cercana a una raíz también será cúbica. ${\displaystyle \ p(x)\ }$ ${\displaystyle \ \operatorname {\mathcal {O}} {\bigl \{}\ (p(x))^{3}\ {\bigr \}}\ ,}$

Retroceder

Incluso si el 'conjunto drástico de suposiciones' no funciona bien para algún polinomio particular p ( x ) , entonces p ( x ) puede transformarse en un polinomio relacionado r para el cual las suposiciones son viables; por ejemplo, desplazando primero el origen hacia un número complejo adecuado w , dando un segundo polinomio q ( x ) = p ( x − w ) , que da raíces distintas con magnitudes claramente distintas, si es necesario (lo que será así si algunas raíces son conjugadas complejas).

Después de eso, se obtiene un tercer polinomio r a partir de q ( x ) aplicando repetidamente la transformación de cuadratura de la raíz del método de Graeffe , suficientes veces para hacer que las raíces más pequeñas sean significativamente más pequeñas que la raíz más grande (y, por lo tanto, se agrupen comparativamente más cerca de cero). La raíz aproximada del método de Graeffe, se puede utilizar para comenzar la nueva iteración para el método de Laguerre en r . Una raíz aproximada para p ( x ) se puede obtener directamente a partir de la de r .

Si hacemos la suposición aún más extrema de que los términos correspondientes a las raíces son despreciablemente pequeños en comparación con la raíz, esto nos lleva al método de Newton . ${\displaystyle \ G\ }$ ${\displaystyle \ x_{2},\ x_{3},\ \ldots ,\ x_{n}\ }$ ${\displaystyle \ x_{1}\ ,}$

Propiedades

Zonas de atracción del método de Laguerre para el polinomio ${\displaystyle ~p(x)=x^{4}+2x^{3}+3x^{2}+4x+1~.}$

Si x es una raíz simple del polinomio , entonces el método de Laguerre converge cúbicamente siempre que la estimación inicial sea lo suficientemente cercana a la raíz. Por otro lado, cuando x es una raíz múltiple , la convergencia es meramente lineal, con la penalidad de calcular valores para el polinomio y sus derivadas primera y segunda en cada etapa de la iteración. ${\displaystyle \ p(x)\ ,}$ ${\displaystyle \ x^{(0)}\ ,}$ ${\displaystyle \ x_{1}~.}$ ${\displaystyle \ x_{1}\ }$

Una ventaja importante del método de Laguerre es que está casi garantizado que convergerá a alguna raíz del polinomio sin importar dónde se elija la aproximación inicial . Esto contrasta con otros métodos como el método de Newton-Raphson y el método de Stephensen , que notoriamente no convergen para conjeturas iniciales mal elegidas. El método de Laguerre puede incluso converger a una raíz compleja del polinomio, porque el radicando de la raíz cuadrada puede ser un número negativo, en la fórmula para la corrección, dada anteriormente, manejable siempre que los números complejos se puedan acomodar convenientemente para el cálculo. Esto puede considerarse una ventaja o una desventaja dependiendo de la aplicación para la que se esté utilizando el método. ${\displaystyle \ a\ ,}$

La evidencia empírica muestra que la falla de convergencia es extremadamente rara, lo que lo convierte en un buen candidato para un algoritmo de búsqueda de raíces polinómicas de propósito general. Sin embargo, dada la comprensión teórica bastante limitada del algoritmo, muchos analistas numéricos dudan en usarlo como predeterminado y prefieren métodos mejor comprendidos como el algoritmo Jenkins-Traub , para el cual se ha desarrollado una teoría más sólida y cuyos límites se conocen.

El algoritmo es bastante sencillo de utilizar, en comparación con otros métodos "seguros", y lo suficientemente sencillo como para realizar cálculos manuales, con la ayuda de una calculadora de bolsillo, si no se dispone de un ordenador. La velocidad a la que converge el método significa que rara vez es necesario realizar más de unas pocas iteraciones para obtener una alta precisión.

Referencias

• Acton, Forman S. (1970). Métodos numéricos que SIEMPRE funcionan . Harper & Row. ISBN 0-88385-450-3– vía Internet Archive (archive.org).
• Goedecker, S. (1994). "Observación sobre algoritmos para hallar raíces de polinomios". Revista SIAM de Informática Científica . 15 (5): 1059–1063. Bibcode :1994SJSC...15.1059G. doi :10.1137/0915064.
• Mekwi, Wankere R. (2001). Métodos iterativos para raíces de polinomios (tesis de maestría). Matemáticas. Oxford, Reino Unido: Universidad de Oxford. Archivado desde el original el 23 de diciembre de 2012.
• Pan, VY (1997). "Resolución de una ecuación polinómica: algo de historia y progreso reciente". SIAM Review . 39 (2): 187–220. Bibcode :1997SIAMR..39..187P. doi :10.1137/S0036144595288554.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 9.5.3 Método de Laguerre". Recetas numéricas : el arte de la computación científica (3.ª ed.). Nueva York, NY: Cambridge University Press. ISBN 978-0-521-88068-8.
• Ralston, Anthony; Rabinowitz, Philip (1978). Un primer curso de análisis numérico . McGraw-Hill. ISBN 0-07-051158-6.