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 es casi seguro que siempre convergerá a alguna raíz del polinomio, sin importar qué se elige la conjetura inicial. Sin embargo, para computadoraPara el cálculo, 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íz real ).
Este método lleva el nombre de Edmond Laguerre , un matemático francés.
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 0
- Para k = 0, 1, 2,…
- Si es muy pequeño, sal del bucle
- Calcular
- Calcular
- Calcular , donde se elige el signo para dar el denominador con el valor absoluto mayor, para evitar la pérdida de significancia a medida que avanza la iteración.
- Colocar
- Repita hasta que a sea lo suficientemente pequeño o si se ha alcanzado el número máximo de iteraciones.
Si se ha encontrado una raíz, el factor lineal correspondiente se puede eliminar de p . Este paso de deflación reduce el grado del polinomio en uno, de modo que eventualmente 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 el orden de magnitud creciente.
Derivación
El teorema fundamental del álgebra establece que todos los n º polinomio de grado se puede escribir en la forma
tal que dónde son las raíces del polinomio. Si tomamos el logaritmo natural de ambos lados, encontramos que
Denote la derivada por
y la segunda derivada negada por
Luego hacemos lo que Acton llama un 'conjunto drástico de suposiciones', que la raíz que estamos buscando, digamos, está a cierta distancia de nuestra conjetura , y todas las demás raíces están agrupadas a cierta distancia. Si denotamos estas distancias por
y
entonces nuestra ecuación para puede escribirse como
y la expresión para se convierte en
Resolviendo estas ecuaciones para , encontramos eso
- ,
donde se elige la raíz cuadrada de un número complejo para producir un valor absoluto mayor del denominador, o de manera equivalente, para satisfacer:
- ,
donde Re denota parte real de un número complejo y G es el complejo conjugado de G ; o
- ,
donde se elige la raíz cuadrada de un número complejo para que tenga una parte real no negativa.
Para valores pequeños de p ( x ), esta fórmula difiere del desplazamiento del método de Halley de tercer orden por un error de O ( p ( x ) 3 ) , por lo que la convergencia cercana a una raíz también será cúbica.
Tenga en cuenta que, incluso si el 'conjunto drástico de supuestos' no funciona para algún polinomio particular p ( x ) , p ( x ) se puede transformar en un polinomio relacionado r para el cual los supuestos son correctos, por ejemplo, cambiando el origen hacia número complejo adecuado w , dando q ( x ) = p ( x - w ) , para dar raíces distintas magnitudes distintas si es necesario (que será si algunas raíces son conjugados complejos), y luego obtener r de q ( x ) repetidamente aplicar la transformación de cuadratura de raíz utilizada en el 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 tanto, agrupadas en comparación); la raíz aproximada del método de Graeffe se puede utilizar para iniciar la nueva iteración del método de Laguerre en r . Entonces se puede obtener una raíz aproximada para p ( x ) directamente a partir de la de r .
Si hacemos la suposición más fuerte de que los términos en G correspondientes a las raíces x i , i = 2, 3,…, n son insignificantemente pequeños en comparación con el término correspondiente a la raíz x 1 , esto conduce al método de Newton .
Propiedades
Si x es una raíz simple del polinomio p ( x ) , entonces el método de Laguerre converge cúbicamente siempre que la suposición inicial x 0 esté lo suficientemente cerca de la raíz x . Por otro lado, si x es una raíz múltiple, entonces la convergencia es solo lineal. Esto se obtiene con la penalización de calcular valores para el polinomio y su primera y segunda derivadas en cada etapa de la iteración.
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, que puede fallar en la convergencia para conjeturas iniciales mal elegidas. Incluso puede converger a una raíz compleja del polinomio, debido a la raíz cuadrada de ser tomado en el cálculo de un anterior puede ser de un número negativo. Esto puede considerarse una ventaja o una desventaja según la aplicación en la que se utilice el método. La evidencia empírica ha demostrado 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 polinomiales de propósito general. Sin embargo, dada la comprensión teórica bastante limitada del algoritmo, muchos analistas numéricos dudan en usarlo como tal y prefieren métodos mejor entendidos como el algoritmo Jenkins-Traub , para el cual se ha desarrollado una teoría más sólida. Sin embargo, el algoritmo es bastante simple de usar en comparación con estos otros métodos "infalibles", bastante fácil de usar a mano o con la ayuda de una calculadora de bolsillo cuando no se dispone de una computadora automática. La velocidad a la que converge el método significa que muy pocas veces se requiere calcular más de unas pocas iteraciones para obtener una alta precisión.
Referencias
- Acton, Forman S. (1970). Métodos numéricos que funcionan . Harper y Row. ISBN 0-88385-450-3.
- Goedecker, S. (1994). "Comentario sobre algoritmos para encontrar raíces de polinomios". SIAM J. Sci. Computación . 15 (5): 1059–1063. doi : 10.1137 / 0915064 .
- Mekwi, Wankere R. (2001). "Métodos iterativos de raíces de polinomios" . Tesis de maestría, Universidad de Oxford . Archivado desde el original el 23 de diciembre de 2012.
- Pan, VY (1997). "Resolver una ecuación polinomial: algo de historia y avances recientes". SIAM Rev . 39 (2): 187–220. doi : 10.1137 / S0036144595288554 .
- Presione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Apartado 9.5.3. Método de Laguerre" . Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York: 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.