Metodo del gradiente coniugato

Da Wikipedia, l'enciclopedia libera.

In analisi numerica, il metodo del gradiente coniugato è un algoritmo per la risoluzione di un sistema lineare della forma  A x = b . Per poter applicare questo metodo è necessario che A sia una matrice simmetrica definita positiva cioè  \forall x, \,  x^t A x > 0.

Spiegazione del metodo[modifica | modifica sorgente]

Quando A è simmetrica si ha che la minimizzazione della funzione f(x) = {1 \over 2} x^t A x -x^t \cdot b + c è equivalente alla risoluzione del sistema iniziale Ax = b, ed avviene quando
\bigtriangledown f(x) = A x - b = 0
cioè quando:
\bigtriangledown f(x) = 0 \Leftrightarrow A x - b = 0 \Leftrightarrow A x = b

Questo significa che risolvere il sistema lineare è equivalente a trovare lo zero di \bigtriangledown f e quindi il minimo di f.

Per trovare il minimo si procede iterativamente come nel metodo del gradiente cioè, partendo da un punto x_i si sceglie una direzione d_i e si trova il punto successivo minimizzando f sulla retta avente direzione d_i e passante per x_i.

La differenza sostanziale rispetto al metodo del gradiente è nella scelta della direzione d_i che non corrisponde alla direzione di massima pendenza come nel metodo del gradiente, ma è scelta A-ortogonale alle superfici di livello.

La ragione di questa scelta è che f(x) è un paraboloide dilatato con coefficiente  c_i sulla direzione  e_i e poi traslato. I  c_i sono gli autovalori di A e gli e_i i corrispondenti autovettori che esistono per il teorema spettrale. La direzione scelta coincide con il gradiente nel paraboloide originale. Questo assicura la convergenza in n-1 passi.


Il metodo del gradiente biconiugato fornisce una generalizzazione per matrici non simmetriche.

Implementazione d'esempio nel linguaggio Octave[modifica | modifica sorgente]

 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( r < 1e-10)
         break;
    endif
    B = (r'*z)/(w'*z);
    w = -r + B*w;
    z = A*w;
    a = (r'*w)/(w'*z);
    x = x + a*w;
 end

Collegamenti esterni[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica