Libro Aplicaciones de Algebra Lineal Grossman

Libro Aplicaciones de Algebra Lineal Grossman

https://cape.fcfm.buap.mx/jdzf/cursos/proba2/libros/grossman.pdf

Comparación de solución de Sistemas Lineales por varios métodos

Método Iteraciones (it) Tiempo (s) r_h(it)

Jacobi 32 0.41519 4.3798 x 10-4

Gauss-Seidel 8 0.10910 8.5498 x 10-5

SOR 8 0.12509 1.4477 x 10-4

Gradiente Conjugado 173 0.22013 6.5405 x 10-4 

http://venus.ceride.gov.ar/cursos/moodledata/31/moddata/assignment/195/7392/Mendoza_Agustin_TP_03.pdf

Implementación del método de Laguerre en Python

Implementación del método de Laguerre en Python

 

https://www.analyticslane.com/2023/04/14/el-metodo-de-laguerre-e-implementacion-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, ${�}_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:

1. Seleccionar una suposición inicial de la raíz a la que se le denomina ${�}_0$.
2. Calcular el valor de la función ($�({�}_0)$), la primera derivada (${�}^{\mathrm{\prime }}({�}_0)$) y la segunda derivada (${�}^{\mathrm{\prime }\mathrm{\prime }}({�}_0)$) en el punto inicial.
3. Usando los valores obtenidos al evaluar el polinomio y las derivadas se definen los siguientes términos:$$�=\frac{{�}^{\mathrm{\prime }}({�}_0)}{�({�}_0)}$$y$$ℎ={�}^2-\frac{{�}^{\mathrm{\prime }\mathrm{\prime }}({�}_0)}{�({�}_0)}\mathrm{.}$$
4. Calcular el término de corrección, al que se le denomina $�$, utilizando la siguiente expresión:$$�=\frac{�}{�+\mathrm{sign}(�)\sqrt{(�-1)(�ℎ-{�}^2)}},$$donde $�$ es el grado del polinomio y $\mathrm{sign}(�)$ es el signo de $�$.
5. Obtener una nueva aproximación de la raíz restando el término anterior a la aproximación inicial:$${�}_1={�}_0-�$$.
6. 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.

Publicidad

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 $�(�)={�}^2-5�+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.