En 1.952 Magnus R. Hestenes y Eduard Stiefel publican «Methods of Congugate Gradients for Solving Linear Systems» siendo los primeros que hablan del gradiente conjugado (CG). Con posterioridad y en 1.971, J. K. Reid publica «On the Method of Conjugate Gradients for the Solution of Large Sparce Systems of Linear Equations», donde plantea el gradiente conjugado como un método iterativo, es la forma en la cual lo utilizmos ahora.


Su objetivo era llegar al mínimo de las funciones cuadráticas, ampliándose después para las funciones generales simples (no necesariamente convexas).
Fundamentalmente es una modificación del gradiente descendente, donde el gradiente ha sido reemplazado por direcciones conjugadas «ortogonales» (subespacio de Krylov) que pueden ser construidas usando gradientes como vectores de base. Su desarrollo está motivado por la necesidad de acelerar la convergencia, más lenta en el gradiente descendente y superar la limitación computacional del método de segundo orden.
Las ventajas del gradiente conjugado son varias: no requiere álgebra lineal numérica, utiliza poca memoria para problemas a gran escala, no requiere la matriz de Hesse, por tanto es más efectivo que otros métodos para el entrenamiento de redes neuronales grandes. Tiene el inconveniente de converger más lentamente que los métodos cuasi-Newton y los pasos suelen tener una reducida escala de longitud, por lo que puede requerir más iteraciones para encontrar un paso aceptable.
En el gráfico vemos el problema del método del gradiente descendente representado por la línea negra. Este necesita más iteraciones para funciones que tienen estructuras de valle largas y estrechas. En frente está el gradiente conjugado, aquí representado por la línea verde.
Matemáticamente es un método iterativo no estacionario que permite resolver sistemas lineales bajo la restricción de que la matriz de coeficientes A, sea simétrica y definida positiva:
donde:
x es un vector desconocido,
b es un vector conocido, b ∈ ℜn
A es una matriz cuadrada simétrica y definida positiva, A ∈ ℜn×n y A > 0
Antes de ver otros métodos debemos introducir el concepto de reinicio (búsqueda local repetida). El reinicio se aplica cuando se encuentra o podemos encontrar un comportamiento irregular de convergencia. El reinicio es la acción de limpiar la memoria y volver a comenzar desde el punto actual, esto lleva implícita la pregunta, ¿cuándo lo hacemos?. En función del algoritmo podemos ajecutarlo cuando dos gradientes consecutivos estén muy lejanos de la ortogonalidad o cada n iteracciones
Otros métodos.
Existen también variantes para abordar matrices no simétricas:
- Sistemas Transformadores. Toman el sistema no simétrico convirtiéndolo en simétrico y trabajan con él. El coste de almacenamiento se duplica por lo que su uso no es adecuado para grandes sistemas.
- Sistemas Directos.
PCG. Para resolver las deficiencias del Gradiente Conjugado en la convergencia, surgen los métodos pre-condicionados (PCG), la proposición es de Paul Concus, Gene H. Golub y Dianne P. O’Leary en 1.976. Pero estos tienen otro problema, es difícil encontrar un pre-condicionador que funcione bien en todas las situaciones, acción que no ayudará a mejorar la velocidad. Algunos de ellos:
- Jacobi, Gauss-Seidel, SOR, SSOR, Chebyshev.
- Factorizaciones Incompletas (ILU o ILUT)
- Aproximada Inversa de estructura diagonal.
La aplicación de un pre-condicionador o matriz de pre-condicionado consiste en reemplazar el sistema de ecuaciones original por uno de idéntica solución, pero cuyas propiedades numéricas puedan tener menores errores de redondeo. Su trabajo se basa en calcular una factorización de la matriz A con cierto grado de llenado, mientras se espera que el producto de dichos factores se asemeje a la matriz A y, más importante, que el producto de sus inversas se asemeje a A−1.
.
FOM (Full Orthogonalization Method). Aplica en cada paso el algoritmo de Arnoldi, modificado Gram-Schmidt. El coste computacional es ± k2n y el coste de almacenamiento es de kn, un problema para grandes valores de n.
GMRES y FGMRES. Generalized Minimal Residual y Algoritmo Flexible GMRES. Desarrollado por Y. Saad y M. H. Schultz en 1.986. Admite varios pre-condicionadores. Crea una base ortogonal del subespacio de Krylov utilizando la ortogonalización de Grahm-Schmidt. Es un devorador de memoria, ya que le es necesario almacenar la base que se incrementa con cada iteración. Se mejoró al incluir un reinicio cada cierto número de pasos (Restarted GMRES).
VFGMRES. Algoritmo Variable FGMRES. Utiliza la solución directa del problema de mínimos cuadrados. Su idea básica es usar el GMRES al principio del algoritmo hasta que satisface una cierta tolerancia, al finalizar hace un rearranque y comenza nuevamente con GMRES hasta finalizar.
BiCG. Gradiente Bi-conjugado. Desarrollado por D. A. H. Jacobs en 1.981. No exige que la matriz sea simétrica. Utiliza el algoritmo de biortogonalización de Lanczos. Se basa en reemplazar las secuencias ortogonales de residuos por dos secuencias mutuamente ortogonales. Para matrices simétricas y definidas positivas obtiene los mismos resultados que el método del GC.
CGS. Gradiente Conjugado Cuadrático. Fue desarrollado po P. Sonneveld en 1.989. Es una variante del Bi-Conjugado. La Cantidad de operaciones es muy similar al BiCG pero la convergencia puede ser más irregular que para el BiCG.
Bi-CGSTAB. Gradiente Bi-conjugado Estabilizado. Fue desarrollado por Hendrik A. Van der Vorst en 1.992 como una variante del CGS. Es aplicable a sistemas lineales no simétricos y reduce la irregularidad del CGS modificando el polinomio que se usa para el cálculo del residuo.
QMRCGSTAB. Este método aplica el principio de cuasi-minimización al BI-CGSTAG. La minimización por mínimos cuadrados incluida en el proceso es resuelta usando la descomposición QR de la matriz de Hessemberg.
Khó khăn trong việc xác định ngân sách và thời gian.
Coincido, es difícil de determinatr el presupuesto y el tiempo.
Có sự đồng ý bằng văn bản của Báo điện tử Dân trí.
My webpage – bao ho lao dong
La traducción de tu mensaje me es difícil de entender. Pudes enviarla en español u otro idioma europeo.
I’m not sure why but this site is loading incredibly slow for me.
Is anyone else having this issue or is it a problem on my end?
I’ll check back later on and see if the problem still exists.
Es correcto lo que dices. Nuestro proveedor de servicios debe tener problemas.
Nice blog! Is your theme custom made or did you download it from somewhere?
A theme like yours with a few simple tweeks would really make my blog stand out.
Please let me know where you got your design. Many thanks
Está hecho a medida
Thanks for some other fantastic article. The place else may just anyone get that kind of info in such a perfect method of writing?
I’ve a presentation subsequent week, and I’m on the look for such info.
Gracias, deseo que la presentación sea positiva.
Good day! This is my first visit to your blog! We are a team of volunteers and starting
a new initiative in a community in the same niche. Your blog provided us beneficial
information to work on. You have done a marvellous job!
Gracias. Es agradable compartir experiencias con resultados positivos. Informarme de vuestros trabajos.
I’m gone to tell my little brother, that he should also pay a quick visit this website on regular
basis to take updated from latest reports.
Buena elección
Appreciate this post. Let me try it out.
Correcto