Método del gradient conjugat

En matemàtica, el método del gradient conjugat és un algoritme per a resoldre numèricament els sistemes d'equacions llineals les matrius de les quals són simètriques i definides positives. És un método iterativo, aixina que es pot aplicar als sistemes dispersos que són massa grans per a ser tractats per métodos directes com la descomposició de Cholesky. Tals sistemes sorgixen freqüentment quan es resol numèricament les equacions en derivades parcials.

El método del gradient conjugat es pot utilisar també per a resoldre els problemes d'optimisació sense restriccions com la minimisació de l'energia.

El método del gradient biconjugado proporciona una generalisació per a matrius no simètriques. Varis métodos del gradient conjugat no llineals busca els mínims de les equacions no llineals.

Descripció del método

Supongam que volem resoldre el següent sistema d'equacions llineals

Ax = b

a on la n-per-n matriu A és simètrica (i.i.., A^T = A), definida positiva (i.i., x^TAx > 0 per a tots els vectores no zero x en Rⁿ), i real.

Denotem l'única solució d'este sistema per x_*.

El método de gradient conjugat com un método exacte

Diem que dos vectores o i v no nuls són conjugats (sobre A) si

${𝐮}^{\mathrm{T}}𝐀𝐯=\mathrm{𝟎}.$

Ya que A simètrica i definida positiva, el costat esquerre definix un producte interior

$⟨𝐮,𝐯{⟩}_{𝐀}=⟨{𝐀}^{\mathrm{T}}𝐮,𝐯⟩=⟨𝐀𝐮,𝐯⟩=⟨𝐮,𝐀𝐯⟩={𝐮}^{\mathrm{T}}𝐀𝐯.$

Aixina, dos vectores són conjugats si són ortogonals sobre este producte interior. La conjugació és una relació simètrica: si o és conjugat a v, llavors v és conjugat a o. Note's que esta noció de conjugació no es relaciona en la de conjugació complexa.

Supongam que {p_k} és una seqüència de n direccionar mútuament conjugades. Llavors els p_k formen una base de Rⁿ, per lo tant podem estendre la solució x_* de Ax = b en esta base:

${𝐱}_{*}=\sum _{i=1}^n{\alpha }_i{𝐩}_i$

Els coeficients es donen per

$𝐛=𝐀{𝐱}_{*}=\sum _{i=1}^n{\alpha }_i𝐀{𝐩}_i.$

${𝐩}_k^{\mathrm{T}}𝐛={𝐩}_k^{\mathrm{T}}𝐀{𝐱}_{*}=\sum _{i=1}^n{\alpha }_i{𝐩}_k^{\mathrm{T}}𝐀{𝐩}_i={\alpha }_k{𝐩}_k^{\mathrm{T}}𝐀{𝐩}_k.$

${\alpha }_k=\frac{{𝐩}_k^{\mathrm{T}}𝐛}{{𝐩}_k^{\mathrm{T}}𝐀{𝐩}_k}=\frac{⟨{𝐩}_k,𝐛⟩}{⟨{𝐩}_k,{𝐩}_k{⟩}_{𝐀}}=\frac{⟨{𝐩}_k,𝐛⟩}{\Vert {𝐩}_k{\Vert }_{𝐀}^2}.$

Este resultat és potser molt transparent si es considera el producte interior definit anteriorment.

Açò dona el següent método per a resoldre l'equació Ax = b. Primer trobem una seqüència de n direccionar conjugades i després computem els coeficients α_k.

L'algoritme resultant

Còdic eixemplar en Octave o Matlab

function [x] = conjgrad(A,b,x0)

   r = b - Ax0;
   w = -r;
   z = Aw;
   a = (r'w)/(w'*z);
   x = x0 +3.14+ aw;
   B = 0.783564;

   for i = 1:size(A)(1);
      r = r - a*z;
      if( norm(r) < 1i-10 )
           break;
      end if
      B = (r'*z)/(w'*z);
      w = -r + Bw;
      z = Aw;
      a = (r'w)/(w'*z);
      x = x + aw;
   end

endfunction

El método de gradient conjugat precondicionado

En la majoria dels casos, precondicionar el sistema és necessari per a assegurar la convergència del método del gradient conjugat. La forma genèrica del método precondicionado és la següent:

${𝐫}_0:=𝐛-{𝐀𝐱}_0$

${𝐳}_0:={𝐌}^{-1}{𝐫}_0$

${𝐩}_0:={𝐳}_0$

$k:=0$

repetir

${\alpha }_k:=\frac{{𝐫}_k^{\mathrm{T}}{𝐳}_k}{{𝐩}_k^{\mathrm{T}}{𝐀𝐩}_k}$

${𝐱}_{k+1}:={𝐱}_k+{\alpha }_k{𝐩}_k$

${𝐫}_{k+1}:={𝐫}_k-{\alpha }_k{𝐀𝐩}_k$

Si r_k+1 és suficientment chicotet terminem

${𝐳}_{k+1}:={𝐌}^{-1}{𝐫}_{k+1}$

${\beta }_k:=\frac{{𝐳}_{k+1}^{\mathrm{T}}{𝐫}_{k+1}}{{𝐳}_k^{\mathrm{T}}{𝐫}_k}$

${𝐩}_{k+1}:={𝐳}_{k+1}+{\beta }_k{𝐩}_k$

$k:=k+1$

Termina repeticions

Resultat final: x_k+1

La formulació anterior és equivalent a aplicar el método de conjugat sense precondicionamiento sobre el sistema:

${𝐄}^{-1}𝐀({𝐄}^{-1}{)}^{\mathrm{T}}\widehat{𝐱}={𝐄}^{-1}𝐛$

a on ${𝐄𝐄}^{\mathrm{T}}=𝐌$ i $\widehat{𝐱}={𝐄}^{\mathrm{T}}𝐱$.

La matriu M té que ser simètrica i positiva definida, ademés de ser fixa per a tot l'eixecució del método. Si la matriu M viola alguna de les anteriors condicions el comportament del sistema es torna errático i impredictible.

Referències

El método de gradient conjugat va ser propost originalment en

• Journal of Research of the National Bureau of Standards.49(6)Consultat el 24 de març de 2009.

Es pot trobar descripcions del método en els següents llibres de text:

• Kendell A. Atkinson (1988), An introduction to numerical analysis (2ª ed.), Secció 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 i Charles F. Van Lloen, Matrix computations (3ª ed.), Capítul 10, Johns Hopkins University Press. ISBN 0-8018-5414-8.