Main Program

Final-Project

Group member:

Objective:

Project Description:

Let A be a given real symmetric, i.e. A=A', matrix. Then, its minimal eigenvalue is real and can be found as a minimum of the following function:

R(x)=(Ax,x)/(x,x),

where x is an arbitrary nonzero real column-vector, and (u,v)=u'v is the standard scalar product of real column vectors. The gradient of this function is:

grad R(x)=Ax - R(x)x,

up to a scalar multiplier, which is not important for us.

Write and test a MATLAB program of the gradient descent method

x(k+1)=xk - alpha(Axk - R(x)xk)

to find the minimum of function R(x), thus, to find the smallest eigenvalue of A. Use algorithm 10.3, pp. 716-618 from the text. Test it for different matrices. Try to use it to find the smallest eigenvalue of the matrix NOS6:from set LANPRO, from the Harwell-Boeing Collection. use a random vector as the initial guess. use MATLAB built in functions eig, and eigs, to find the eigenvalue, too. Discuss numerical results and performance. Write a report and publish it on the Internet.

Source code:

We used the MATLAB build in functions to solve the problem. The Steepest Descent procedure is as follow:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function steepestDescent(A,x)
tolerance = 1e-6;
maxIteration = 100;
for k = 1 : maxIteration
     g1 = raleigh (A,x);
     z = gradient(A,x);
   z0 = norm(z);
     if ( z0 == 0 )
          fprintf( 'Zero gradient after %d iteration\n', k);
          fprintf('R(x) has a minimum at x = '); fprintf('%15.6f',x');fprintf('\n');
          fprintf('Calculated Minimal eigent value of A = %15.6f\n', g1);
          fprintf('Minimal eigent value of A = %15.6f\n', min(eig(A)));
          return;
     end
     z = z / z0;
     a1 = 0;
     a3 = 1;
     g3 = raleigh(A,x - a3*z);
     while ( g3 >= g1 )
          a3 = a3 / 2;
          g3 = raleigh(A,x - a3*z);
          if ( a3 < tolerance/2 )
               fprintf( 'Not convergence\n');
               fprintf( 'x = %10.3f\n', x' );
               return;
          end
     end
     a2 = a3/2;
     g2 = raleigh(A,x-a2*x);
     h1 = (g2 - g1)/a2;
     h2 = (g3 - g2)/(a3-a2);
     h3 = (h2 - h1)/a3;

     a0 = 0.5*(a2 - h1/h3);
     g0 = raleigh(A,x-a0*z);
     g3 = raleigh(A,x-a3*z);
     if ( g3 > g0 )
          a = a0;
          g = g0;
     else
          a = a3;
          g = g3;
     end
     x = x - a*z;
     if (abs(g-g1) < tolerance)
          fprintf('Convert after %d iteration\n', k);
          fprintf('R(x) has a minimum at x = '); fprintf('%15.6f',x');fprintf('\n');
          fprintf('Calculated Minimal eigent value of A = %15.6f\n', g);
          fprintf('Correct Minimal eigent value of A: %15.6f\n', min(eig(A)));
          return;
     end
end

%%%%%%%%%%%%%%%%%%%%%%%%%

The Raleigh procedure is as follow:

% Raleigh Quotion computation.
% Given a matrix A, this function calculate the
% Raleigh Quotion at point x = (x1, x2, ... , xN)
function r = raleigh(A,x)
if size(x,2) ~= 1
x = x';
end
r = ((A*x)'*x)/(x'*x);

%%%%%%%%%%%%%%%%%%%%%%%%%

The gradient procedure is as follow:

function grad = gradient(A,x)
% Compute the gradient
if size(x,2) ~= 1
x = x';
end
grad = A*x - raleigh(A,x)*x;

Test Oracle:

***** Case #1: Two dimentional symmetric matrix with random vector as initial guess

» A = [2 1 ; 1 2];
» X = rand(2 , 1);
» steepestdescent(A , X)
Convert after 8 iteration
R(x) has a minimum at x = -0.932744 0.933202
Calculated Minimal eigent value of A = 1.000000
Correct Minimal eigent value of A = 1.000000
»

***** Case #2: Two dimentional symmetric matrix with initial guess vector x =(1, 1)'

» A = [2 1 ; 1 2];
» X = [1 ; 1];
» steepestdescent(A , X)
Zero gradient after 1 iteration
x = 1.000000 1.000000
g = 3.000000
Minimal eigent value of A: 1.000000
»

In this case, the result is not correct. Because of the steepest descent method convert to the shadow point instead of the minimum point.

***** Case #3: Two dimentional symmetric matrix with initial guess vector x = (1, 1)'

» A = [45 2 ; 2 80];
» X = [1 ; 1];
» steepestdescent(A , X)
Convert after 9 iteration
R(x) has a minimum at x = 1.804459 -0.102634
Calculated Minimal eigent value of A = 44.886085
Correct Minimal eigent value of A = 44.886085
»

***** Case #4: Three dimentional symmetric matrix with random vector as initial guess

» A = [1 2 5 ; 2 2 4 ; 5 4 1];
» X = rand(3, 1);
» steepestdescent(A , X)
Convert after 12 iteration
R(x) has a minimum at x = -1.170465 -0.568230 1.497053
Calculated Minimal eigent value of A = -4.425613
Correct Minimal eigent value of A = -4.425614
»

***** Case #5: Four dimentional symmetric matrix with random vector as initial guess

» A = [1 0 2 3 ; 0 4 1 2 ; 2 1 5 4 ; 3 2 4 1];
» X = rand(4, 1);
» steepestdescent(A , X)
Convert after 14 iteration
R(x) has a minimum at x = -0.973523 -0.382599 -0.490434 1.526597
Calculated Minimal eigent value of A = -2.698782
Correct Minimal eigent value of A = -2.698782
»

Discussion numerical results and performance:

By doing this project, we have learned how to use the Steepest Descent method to find the minimal eigent value of a square symmetric matrix. After a few trials, we found that when the dimention of the original matrix A increases, the number of iteration also increases. That mean the number of iteration linearly proportional to the dimention of the matrix.

For all trial we tested, as long as the matrix is real symmetric, this method always convert to the correct value except the cases where there is a shadow point near the convert path.

We did download the files from LandPro collection. When we apply this method to find the minimal eigent value for the matrix nos4 and nos6. The result is failed since we set the maximum iteration not big enough.

**********%%%%%%%%%%%%%%%%%%%%%%**************

Special thanks to Prof. Andrew Knyazev for given us enough time to work on this project.