BAP: Lecture 2 (feb 12, 2002)

The notes for this lecture are available in

The main topic of this lecture was the condition number of a matrix. Standard references on Numerical Linear Algebra that discuss the condition number are:

Matrix Computation, by Golub and van Loan ,
Applied Numerical Linear Algebra, by James Demmel, and
Numerical Linear Algebra, by Trefethen and Bau

Material that inspired this lecture may be found in

The Probability that A Numerical Analysis Problem is Difficult, by James W. Demmel, appeared in Mathematics of Computation, Vol 50, No 182, April 1988, pp. 449-480. Available at JSTOR.
Eigenvalues and Condition Numbers of Random Matrices, by Alan Edelman, appeared in SIAM J. Matrix Anal. Appl., 1988, vol 9, no 4, pp. 543-560.
Eigenvalues and Condition Numbers of Random Matrices, by A. Edelman MIT PhD Dissertation, 1989.

All of the matlab code used in this lecture may be found on the BAP matlab code directory. The following are the matlab code used to generate some of the experiments performed in class, and some of those that should have been. Download the code and try some out!

for i = 1:10000,
  a = randn(32);
  d(i) = min(svd(a));
end

d = sort(d);

clf
plot([1:10000]/10000,d)


A = 2*eye(32) - tril(ones(32));
min(svd(A))

for i = 1:10000,
  a = A + randn(32)/100;
  dp(i) = min(svd(a));
end

dp = sort(dp);
hold on;
plot([1:10000]/10000,dp,'r')


clf;

for i = 1:10000,
  a = (rand(32) < .3);
  d(i) = min(svd(a));
end
d = sort(d);
plot([1:10000]/10000,d)


clf;

for i = 1:100000,
  a = ((rand(32) < 1/2)-1/2)/100 ;
  d(i) = min(svd(a));
end


for i = 1:100000,
  a = ((rand(32) < 1/2)-1/2)/100 + A;
  dp(i) = min(svd(a));
end
dp = sort(dp);

hold on
plot(dp,'r')


D = zeros(10);
E = crossedGrid(D,1)  %% a 1 at the end plots it!

A = graph2A(E);
min(abs(eig(A)))

for i = 1:10000,
  D = (rand(10) < 1/2);
  E = crossedGrid(D,0);
  A = graph2A(E);
d(i) = min(abs(eig(A)));
end

d = sort(d);
clf
plot(d)