viernes, 30 de octubre de 2015

Algoritmos

Algoritmos de búsqueda de raíces

 método de Broyden es un método cuasinewtoniano para la solución numérica de ecuaciones no lineales con más de una variable. Fue descrito originalmente por C. G. Broyden en 1965.1
Para hallar la solución de la ecuación \displaystyle f(x) = 0, el método de Newton emplea el jacobiano \displaystyle J en cada iteración. Sin embargo, computar ese jacobiano es una operación difícil y costosa. La idea que subyace en el método de Broyden consiste en computar el jacobiano entero solamente en la primera iteración, y llevar a cabo una actualización de rango 1 en las demás iteraciones.
En 1979, Gay demostró que, cuando se aplica el método de Broyden a un sistema lineal, se requieren 2n pasos.

Descripción del método

El método de Broyden considera el método de la secante y establece una generalización de él para el espacio multidimensional.
El método de la secante sustituye la primera derivada \displaystyle f'(x_n) por la aproximación de diferencia finita
f'(x_n) \simeq \frac {f(x_n)-f(x_{n-1})}{x_n-x_{n-1} }
y procede según el método de Newton:
x_{n+1}=x_n-\frac{1}{f'(x_n)} f(x_n)
Broyden establece una generalización de esa fórmula para un sistema de ecuaciones mediante una sustitución de la derivada \displaystyle f' por el jacobiano \displaystyle J. Éste se determina por medio de la ecuación de la secante (la aproximación de diferencia finita):
J_n \cdot (x_n-x_{n-1})\simeq F(x_n)-F(x_{n-1})
Sin embargo, esta ecuación está infradeterminada por más de una dimensión.
Broyden sugiere un procedimiento que consta de los siguientes 3 pasos:
1) Emplear la aproximación del jacobiano \displaystyle J_{n-1}
2) Tomar la solución de la ecuación de la secante que suponga la modificación mínima de \displaystyle J_{n-1} (entendiendo por mínima que se dé una minimización de la norma de Frobenius \displaystyle \|J_{n} - J_{n-1}\|_{F})
J_n=J_{n-1}+\frac{\Delta F_n-J_{n-1} \Delta x_n}{\|\Delta x_n\|^2} \Delta x^T_n
3) Continuar según el método de Newton:
x_{n+1}=x_n-J_n^{-1}F(x_n).
En esa última fórmula,
\displaystyle x_n=(x_1[n],...,x_k[n])
y
\displaystyle F_n(x)=(f_1(x_1[n],...,x_k[n]),...,f_k(x_1[n],...,x_k[n])
son vectores columna de k elementos en un sistema de k dimensiones.
Así:
\Delta x_n=\begin{bmatrix} x_1[n]-x_1[n-1]\\ ...\\ x_k[n]-x_k[n-1] \end{bmatrix} \quad \text{y} \quad \Delta F_n=\begin{bmatrix} f_1(x_1[n],...,x_k[n])-f_1(x_1[n-1],...,x_k[n-1])\\ ...\\ f_k(x_1[n],...,x_k[n])-f_k(x_1[n-1],...,x_k[n-1]) \end{bmatrix}.
Broyden sugiere también emplear la fórmula de Sherman-Morrison para actualizar directamente el inverso del jacobiano:
J_n^{-1}=J_{n-1}^{-1}+\frac{\Delta x_n-J^{-1}_{n-1} \Delta F_n}{\Delta x_n^T J^{-1}_{n-1}\Delta F_n} (\Delta x_n^T J^{-1}_{n-1})
Éste último se conoce como el « buen método de Broyden».
Se puede obtener a partir de él una técnica similar empleando una modificación ligeramente distinta de J_{n-1} que minimiza en su lugar \displaystyle \|J^{-1}_{n} - J^{-1}_{n-1}\|_{F}
Tal sería el llamado « mal método de Broyden»:
J_n^{-1}=J_{n-1}^{-1}+\frac{\Delta x_n-J^{-1}_{n-1} \Delta F_n}{\Delta F_n^T \Delta F_n} \Delta F_n^T
Pero, en cuanto a lo de « mal método», véase "A faster Broyden method" ("Un método de Broyden más rápido").3
Se han sugerido muchos otros procedimientos cuasinewtonianos en el campo de la optimización, en el que se busca un máximo o un mínimo hallando la raíz de la primera derivada, o el gradiente si se trata de un espacio multidimensional. Se califica al jacobiano del gradiente de «hessiano», y es simétrico, lo que añaderestricciones a la hora de llevar a cabo su actualización.

Método de Broyden

Imagen 1

El método de Broyden es un método cuasi-newtoniano, se denomina así a los métodos que se aproxima a la matriz jacobiana mediante recurrencia que la relacionen con el  valor que tome en iteración anteriores. Para explicar el método consideremos f(x)=0 un sistema de ecuaciones lineales entonces es de la forma Ax-b=0. Si se restan dos valores de f(x) en dos puntos sucesivos de la iteración xk-1 y xk, se tiene que:

f(xk)-f(xk-1)=A(xk-xk-1)

Por el contrario en el caso no lineal la igualdad anterior no se cumple aunque se puede lograr, eligiendo adecuadamente A, que 

f(xk)-f(xk-1)≈Ak(xk-xk-1)

en si no el método no se ve muy complicado de lo expuesto hasta ahora, pero considerando los calculo que se realizan por cada iteración se ve la debilidad del método, para calcular el jacobiano asociado a un sistema de n ecuaciones no lineales requiere determinar y evaluar n derivadas parciales. Cuando no es práctico efectuar la evaluación exacta, podemos usar la aproximacion de diferencia finita a las derivadas parciales

 ∂fj(xi)/ ∂xk ≈ (fj(xi+ekh)-fj(xi))/h

Sin embargo está aproximación requiere efectuar, al menos, n2 evaluciones de funciones escalares para aproximar la matriz jacobiana y no disminuye la cantidad de cálculos, casi siempre es necesario O(n3) para resolver el sistema. Por lo tanto, el total de cálculos que se requiere para una sola iteración del método es almenos n2+n evaluaciones de funciones escalares(n2 para evaluar la matriz jacobiana y n para evaluar f), junto con O(n3) operaciones aritmeticas para resolver el sistema lineal. Asi la cantidad de cálculos aumenta conforme aumenta la cantidad de ecuaciones del sistema en el caso del método de Newton pero con el método de Broyden tiene una convergencia superlineal.

Generalizando para mas dimensiones la aproximación por la derivada de imagen 1 obtenemos

Jk(xk-xk-1) ≈ f(xk)-f(xk-1)

entonces según el método de newton las iteraciones seran segun

xk = xk-1 + Jk-1[ f(xk) ]

y para cada iteración usamos la siguiente formula propuesta por broyden para hallar el jacobiano J

Jk = Jk-1 + [ (∇yk-Jk-1∇sk) / ||∇sk||2 ] ∇skT
donde
∇y = f(xk)-f(xk-1)    ∇sk = xk-xk-1





















método de Bairstow es un algoritmo eficiente de búsqueda de las raíces de un polinomio real de grado arbitrario. Es un método iterativo, basado en el método de Müller y de Newton Raphson. Dado un polinonio \ f_n(x)  se encuentran dos factores, un polinomio cuadrático
\ f_2(x)=x^2-rx-s  y \ f_{n-2}(x)
El procedimiento general para el método de Bairstow es el siguiente. Dado:
\ f_n(x)  y \ r_0  y \ s_0
  • 1. Utilizando el método de Newton Raphson se calcula:
\ f_2(x)=x^2-rx-s  y \ f_{n-2}(x) , tal que, el residuo de \,f_n(x)/ f_2(x) , sea igual a cero.
  • 2. Se determinan la raíces \ f_2(x)  , utilizando la formula general.
  • 3. Se calcula \ f_{n-2}(x)=f_n(x)/f_2(x)
  • 4. Se hace \ f_n(x):=f_{n-2}(x)
  • 5. Si el grado del polinomio es mayor que tres regresamos al paso 2; en caso contrario, terminamos.
La principal diferencia de este método, respecto a otros, es que permite calcular todas las raíces de un polinomio (reales e imaginarias).
Para calcular la división de polinomios, hacemos uso de la división sintética. Así dado:
\ f_n(x)=a_n x^n+a_{n-1}x^{n-1}+...+a_2x^2+a_1x+a_0
Al dividir entre \ f_2(x)=x^2-rx-s  , se tiene como resultado el siguiente polinomio:
\ f_(n-2)(x)=b_nx^{n-2}+b_{n-1}x^{n-3}+...+b_3x+b_2
con un residuo \, R = b_1 {x-r} + b_0 , , el residuo será cero solo si \, b_1 y b_0 , lo son.
Los términos b, se calculan utilizando división sintética, la cual puede resolverse utilizando la siguiente relación de recurrencia:
\, b_n = a_n ,
\, b_{n-1} = a_{n-1} + rb_n ,
\, b_i = a_i + rb_{i+1} + sb_{i+2} ,
Una manera de determinar los valores de r y s que hacen cero el residuo es utilizar el método de Newton-Raphson. Para ello necesitamos una aproximación lineal de \ b_1 y b_0 , respecto a r y s la cual calculamos utilizando la serie de Taylor
\ b_1(r+dr,s+ds)=b_1+\frac{\partial b_1}{\partial r}dr+\frac{\partial b_1}{\partial s}ds
\ b_0(r+dr,s+ds)=b_0+\frac{\partial b_0}{\partial r}dr+\frac{\partial b_0}{\partial s}ds
donde los valores de r y s están dados y se calculan los incrementos dr y ds que hacen a \ b_1(r+dr, s+ds)  y \ b_0(r+dr, s+dr)  igual a cero. El sistema de ecuaciones que se tiene que resolver es:
\ \frac{\partial b_1}{\partial r}dr+\frac{\partial b_1}{\partial s}ds=-b_1
\ \frac{\partial b_0}{\partial r}dr+\frac{\partial b_0}{\partial s}ds=-b_0
Bairtow muestra que las derivadas parciales pueden obtener haciendo un procedimiento similar a la división sintética, así:
\ c_n=b_n
\ c_{n-1}=b_{n-1}+rc_n
\ c_i=b_i+rc_{i+1}+sc_{i+2}
donde:
\ \frac{\partial b_0}{\partial r}=c_1
\ \frac{\partial b_1}{\partial r}=\frac{\partial b_0}{\partial s}=c_2
\ \frac{\partial b_1}{\partial s}=c_3




El algoritmo de Bairstow tiene orden de convergencia cuadrático como el método de Newton, excepto en el caso de que el polinomio tenga factores cuadráticos de multiplicidad superior a 1, pudiendo ser el orden de convergencia menor.





Metodo de Bairstow. Raices de Polinomios .- ......................................:http://www.academia.edu/3524281/Metodo_de_Bairstow._Raices_de_Polinomios


Publicado por en

No hay comentarios:

Publicar un comentario

Suscribirse a: Enviar comentarios (Atom)