Co sugeruje, by jako pierwszy wektor bazowy p1 wybrać gradient f w x = x0, który wynosi Ax0−b, a ponieważ wybraliśmy x0 = 0, otrzymujemy −b. Pozostałe wektory w bazie będą sprzężone do gradientu (stąd nazwa metoda gradientu sprzężonego).
Niech rk oznacza rezyduum w k-tym kroku:
Zauważmy, że rk jest przeciwny do gradientu f w x = xk, więc metoda gradientu prostego nakazywałaby ruch w kierunku rk. Tutaj jednak założyliśmy wzajemną sprzężoność kierunków pk, więc wybieramy kierunek najbliższy do rk pod warunkiem sprzężoności. Co wyraża się wzorem:
Wynikowy algorytm Upraszczając, otrzymujemy poniższy algorytm rozwiązujący Ax = b, gdzie macierz A jest rzeczywista, symetryczna i dodatnio określona. x0 jest punktem startowym.
repeat
if rk+1 jest "wystarczająco mały" then exit loop end if
end repeat Wynikiem jest
Przykład metody gradientu sprzężonego w Octave/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;
for i = 1:size(A,1); r = r - a*z; if( norm(r) < 1e-10 ) break; end B = (r'*z)/(w'*z); w = -r + B*w; z = A*w; a = (r'*w)/(w'*z); x = x + a*w; end
end
Zobacz też metoda gradientu prostego metoda najszybszego spadku metoda Newtona metoda złotego podziału optymalizacja