Solution to HW5, Q5

Computational Linear Algebra

I wrote several matlab programs to help with the solution to this problem:

tridi.m: Given an n by n matrix a, symmetrize it and make it tridiagonal by zeroing out selected entries, returning the answer in c.
countbig.m: Count the number of entries in an n by n matrix Q of value at least 10e-10.
countbigeps.m: Count the number of entries in an n by n matrix Q of value at least eps, where eps is a user supplied parameter.
laplace.m: Set up a Laplace matrix, stored as T.

Initially, I generated a 100 by 100 random matrix. I then called tridi.m to symmetrize it and make it tridiagonal. The eigenvalues and eigenvectors of the tridiagonal matrix c were found, and the number of entries in Q bigger than 10e-10 were counted.

>> n=100;
>> a=randn(100);
>> tridi;
>> [Q,D]=eig(c);
>> countbig

count =

        4150

The entries in Q were printed on a semilog scale, after zeroing out any smaller than 10e-10, giving this plot. The MATLAB command spy can be used to give a plot of the nonzero structure of Q; again after zeroing out small components, we get this plot. There are some dense columns, but there are also some sparse columns.

>> semilogy(max(abs(Q),10^(-10)))    %  saved as hw5q5f1.eps
>> eps=1e-10

eps =

   1.0000e-10

>> spy(max(abs(Q)-eps,0))            %  saved as hw5q5spy1.eps

It is possible to experiment with other choices for what we consider "small" values. The program countbigeps.m was used to count. Here are the corresponding semilog plot and spy plot.

>> semilogy(max(abs(Q),10^(-3)))     %  saved as hw5q5f3.eps
>> eps=1.e-3;
>> spy(max(abs(Q)-eps,0))            %  saved as hw5q5spy3.eps


>> eps=1.e-3

eps =

   1.0000e-03

>> countbigeps

count =

        1287

The same experiment can be conducted with the Laplace matrix. Every entry in the Q arising from the Laplace matrix is larger than 10e-3. Here is the semilog plot.

>> laplace;
>> [Q,D]=eig(T);
>> countbig

count =

       10000

>> semilogy(max(abs(Q),10^(-10)))    %  saved as hw5q5laplace.eps
>> eps=1.e-3

eps =

   1.0000e-03

>> countbigeps

count =

       10000

John Mitchell