El método de Laguerre e implementación en Python

Cuando se necesita encontrar las raíces de polinomios complejos uno de los algoritmos que se pueden emplear es el método de Laguerre. Un método numérico propuesto por el matemático francés Edmond Laguerre en 1880. El método, al igual que el de Newton-Raphson para las raíces de funciones, utiliza las derivadas para aproximarse de manera iterativa a las raíces de los polinomios desde un punto inicial. Veamos los fundamentos del método de Laguerre y una posible implementación en Python.

El método de Laguerre

El método de Laguerre es un algoritmo iterativo para localizar las raíces de polinomios. En este, partiendo de una suposición inicial para la raíz del polinomio, $x_0$ , se genera una serie de aproximaciones cada de las cuales se acerca más a la solución. Serie que se genera corrigiendo la aproximación con una fórmula basada en las derivadas del polinomio.

Los pasos para implementar el método de Laguerre son los siguientes:

Seleccionar una suposición inicial de la raíz a la que se le denomina $x_0$ .
Calcular el valor de la función ( $f(x_0)$ ), la primera derivada ( $f'(x_0)$ ) y la segunda derivada ( $f''(x_0)$ ) en el punto inicial.
Usando los valores obtenidos al evaluar el polinomio y las derivadas se definen los siguientes términos: $g = \frac{f'(x_0)}{f(x_0)}$ y $h = g^2 - \frac{f''(x_0)}{f(x_0)}.$
Calcular el término de corrección, al que se le denomina $d$ , utilizando la siguiente expresión: $d = \frac{n}{g + \operatorname{sign}(g) \sqrt{(n-1)(n h -g^2)}},$ donde $n$ es el grado del polinomio y $\operatorname{sign}(g)$ es el signo de $g$ .
Obtener una nueva aproximación de la raíz restando el término anterior a la aproximación inicial: $x_1 = x_0 - d$ .
Repetir los pasos 2-6 hasta que la aproximación de la raíz sea lo suficientemente precisa o se llegue a un máximo de iteraciones permitidas.

Implementación del método de Laguerre en Python

En base a la descripción del algoritmo que se vio en la sección anterior se puede realizar una implementación en Python con el siguiente código.

import numpy as np

def laguerre(poly, x0, tol=1e-6, max_iter=100):
    """
    Encuentra una raíz de un polinomio utilizando el método de Laguerre.
    
    Parámetros
    ----------
    poly : array
        Coeficientes del polinomio. Los coeficientes deben estar en orden
        descendente, es decir, el término de mayor grado viene primero.
    x0 : float
        Suposición inicial para la raíz del polinomio.
    tol : float, opcional (valor por defecto = 1e-6)
        Tolerancia de convergencia. El algoritmo se detendrá cuando la
        diferencia entre dos aproximaciones consecutivas sea menor o igual
        que tol.
    maxiter : int, opcional (valor por defecto = 100)
        Número máximo de iteraciones permitidas.
    
    Devuelve
    --------
    root : float. Aproximación de la raíz del polinomio.
    """
    n = len(poly) - 1 # grado del polinomio
    x = x0
    for _ in range(max_iter):
        f = np.polyval(poly, x)
        if abs(f) < tol:
            return x

        g = np.polyval(np.polyder(poly), x) / f
        h = g**2 - np.polyval(np.polyder(poly, 2), x) / f

        if g > 0:
            d = n / (g + np.sqrt((x-1)*(n*h - g**2)))
        else:
            d = n / (g - np.sqrt((x-1)*(n*h - g**2)))

        x = x - d

        if abs(np.polyval(poly, x)) < tol:
            return x.real

    raise ValueError(f"El método no converge después de {max_iter} iteraciones.")

En donde se usan la funciones de NumPy np.polyval() para evaluar el polinomio en los puntos y np.polyder() para obtener la derivada de este.

Evaluación de la implementación

La función implementada en la sección anterior se puede evaluar con un polinomio para comprobar que se obtienen las raíces de este. Por ejemplo, se puede probar con $f(x) = x^2 - 5x + 6$ que tiene como raíces 2 y 3. Lo que se muestra en el siguiente código.

import numpy as np

# Definir el polinomio
poly = np.array([1, -5, 6])

# Imprimir la raíz encontrada
print(f"Una raíz es: {laguerre(poly, 1)}")
print(f"Una raíz es: {laguerre(poly, 5)}")

Una raíz es: 2.0000000000000004
Una raíz es: 3.000000000000902

Como se puede ver, cuando se parte de 1 el método obtiene un valor próximo a 2, mientras que cuando se parte de 5 el resultado es 3

Conclusiones

El método de Laguerre es una excelente solución para encontrar las raíces de un polinomio. Partiendo de un punto inicial y empleando las derivadas es capaz de llegar a una buena aproximación a la solución en pocos pasos.

Imagen de wendy CORNIQUET en Pix abay