% MATLAB M-file for Prototype Conjugate-Gradient Algorithm (with exact line search)
%
% Written by: Douglas B. Meade
% Created: 17 April 2006

function [x,r,k,Iterates,Directions] = ConjGrad( A, b, x, eps, N )

Iterates(:,1) = x;

if b'*b == 0,
   eps1 = eps;
else
   eps1 = eps * b'*b;
end

r = b - A*x;
nu0 = r'*r;
k = 1;

while (sqrt(nu0) > eps1) & (k < N),
 
   if (k==1)
      p = r;
   else
      beta = nu0/nu1;               
      p = r + beta*p;
   end;
   
   Directions(:,k) = p;
   q = A * p; 
   alpha = nu0 /(p'*q);
   x = x + alpha*p;
   r = r - alpha*q;
   nu1 = nu0;    
   nu0 = r'*r;
   k = k + 1;
   Iterates(:, k) = x;
end;