Método del gradiente conjugado

Método del gradiente conjugado

En matemática, el método del gradiente conjugado es un algoritmo para resolver numéricamente los sistemas de ecuaciones lineales cuyas matrices son simétricas y definidas positivas. Es un método iterativo, así que se puede aplicar a los sistemas dispersos que son demasiado grandes para ser tratados por métodos directos como la descomposición de Cholesky. Tales sistemas surgen frecuentemente cuando se resuelve numéricamente las ecuaciones en derivadas parciales.

El método del gradiente conjugado se puede utilizar también para resolver los problemas de optimización sin restricciones como la minimización de la energía.

El método del gradiente biconjugado proporciona una generalización para matrices no simétricas. Varios métodos del gradiente conjugado no lineales busca los mínimos de las ecuaciones no lineales.

Contenido

Descripción del método

Supongamos que queremos resolver el siguiente sistema de ecuaciones lineales

Ax = b

donde la n-por-n matriz A es simétrica (i.e., AT = A), definida positiva (i.e., xTAx > 0 para todos los vectores no cero x en Rn), y real.

Denotamos la única solución de este sistema por x*.

El método de gradiente conjugado como un método directo

Decimos que dos vectores no cero u y v son conjugados (con respecto a A) si

 \mathbf{u}^{\mathrm{T}} \mathbf{A} \mathbf{v} = \mathbf{0}.

Ya que A simétrica y definida positiva, el lado izquierdo define un producto interior

 \langle \mathbf{u},\mathbf{v} \rangle_\mathbf{A} := \langle \mathbf{A}^{\mathrm{T}} \mathbf{u}, \mathbf{v}\rangle = \langle \mathbf{A} \mathbf{u}, \mathbf{v}\rangle = \langle \mathbf{u}, \mathbf{A}\mathbf{v} \rangle = \mathbf{u}^{\mathrm{T}} \mathbf{A} \mathbf{v}.

Así, dos vectores son conjugados si son ortogonales con respecto a este producto interior. La conjugación es una relación simétrica: si u es conjugado a v, entonces v es conjugado a u. Nótese que esta noción de conjugación no se relaciona con la de conjugación compleja.

Supongamos que {pk} es una secuencia de n direcciones mutuamente conjugadas. Entonces los pk forman una base de Rn, por lo tanto podemos extender la solución x* de Ax = b en esta base:

 \mathbf{x}_* = \sum^{n}_{i=1} \alpha_i \mathbf{p}_i

Los coeficientes se dan por

 \mathbf{b}=\mathbf{A}\mathbf{x}_* = \sum^{n}_{i=1} \alpha_i  \mathbf{A} \mathbf{p}_i.
 \mathbf{p}_k^{\mathrm{T}} \mathbf{b}=\mathbf{p}_k^{\mathrm{T}} \mathbf{A}\mathbf{x}_* = \sum^{n}_{i=1} \alpha_i\mathbf{p}_k^{\mathrm{T}} \mathbf{A} \mathbf{p}_i=\alpha_k\mathbf{p}_k^{\mathrm{T}} \mathbf{A} \mathbf{p}_k.
 \alpha_k = \frac{\mathbf{p}_k^{\mathrm{T}} \mathbf{b}}{\mathbf{p}_k^{\mathrm{T}} \mathbf{A} \mathbf{p}_k} = \frac{\langle \mathbf{p}_k, \mathbf{b}\rangle}{\,\,\,\langle \mathbf{p}_k,  \mathbf{p}_k\rangle_\mathbf{A}} = \frac{\langle \mathbf{p}_k, \mathbf{b}\rangle}{\,\,\,\|\mathbf{p}_k\|_\mathbf{A}^2}.

Este resultado es quizás muy transparente si se considera el producto interior definido anteriormente.

Esto da el siguiente método para resolver la ecuación Ax = b. Primero encontramos una secuencia de n direcciones conjugadas y luego computamos los coeficientes αk.

El método de gradiente conjugado como un método iterativo

El algoritmo resultante

Código ejemplar en Octave o Matlab

function [x] = conjgrad(A,b,x0)
 
   r = b - A*x0;
   w = -r;
   z = A*w;
   a = (r'*w)/(w'*z);
   x = x0 + a*w;
   B = 0;
 
   for i = 1:size(A)(1);
      r = r - a*z;
      if( norm(r) < 1e-10 )
           break;
      end if
      B = (r'*z)/(w'*z);
      w = -r + B*w;
      z = A*w;
      a = (r'*w)/(w'*z);
      x = x + a*w;
   end
 
end

El método de gradiente conjugado precondicionado

Referencias

El método de gradiente conjugado fue propuesto originalmente en

Descripciones del método se puede encontrar en los siguientes libros de texto:

  • Kendell A. Atkinson (1988), An introduction to numerical analysis (2ª ed.), Sección 8.9, John Wiley and Sons. ISBN 0-471-50023-2.
  • Mordecai Avriel (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
  • Gene H. Golub y Charles F. Van Loan, Matrix computations (3ª ed.), Capítulo 10, Johns Hopkins University Press. ISBN 0-8018-5414-8.

Wikimedia foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Mira otros diccionarios:

  • Método del gradiente biconjugado estabilizado — En álgebra lineal numérica, el método del gradiente biconjugado estabilizado, generalmente abreviado como BiCGSTAB (del inglés «biconjugate gradient stabilized method»), es un método iterativo propuesto por H. A. van der Vorst para la resolución… …   Wikipedia Español

  • Método iterativo — En matemática computacional, un método iterativo trata de resolver un problema (como una ecuación o un sistema de ecuaciones) mediante aproximaciones sucesivas a la solución, empezando desde una estimación inicial. Esta aproximación contrasta con …   Wikipedia Español

  • Método de los elementos finitos — Solución de MEF en 2D para una configuración de un magnetostato, (las líneas muestran la dirección de la densidad de flujo calculada, y el color, su magnitud) …   Wikipedia Español

  • Análisis numérico — El análisis numérico o cálculo numérico es la rama de las matemáticas que se encarga de diseñar algoritmos para, a través de números y reglas matemáticas simples, simular procesos matemáticos más complejos aplicados a procesos del mundo real. El… …   Wikipedia Español

  • Subespacio de Krylov — En álgebra lineal un subespacio de Krylov de orden r generado por una matriz cuadrada A de orden n y un vector v, es el subespacio vectorial generado por Akv con k < r El nombre se debe al matemático ruso Alekséi Krylov quien publicó un… …   Wikipedia Español

  • Segmentación (procesamiento de imágenes) — La segmentación en el campo de la visión artificial es el proceso de dividir una imagen digital en varias partes (grupos de píxeles) u objetos. El objetivo de la segmentación es simplificar y/o cambiar la representación de una imagen en otra más… …   Wikipedia Español

  • Modelado molecular — El Modelado molecular es un término general que engloba métodos teóricos y técnicas computacionales para modelar o imitar el comportamiento de moléculas. Las técnicas son utilizadas en los campos de la Química computacional, Biología… …   Wikipedia Español

  • Teoría cuántica de campos — Dispersión de neutrones. La dispersión inelástica de …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”