% AMSC 600 / CMSC 760 Fall 2007
% Solution to Homework 4, Problem 1
% Dianne O'Leary 11/2007
% Consider the 1-dimensional model problem matrix
% of size n=11:
n = 11;
M = diag(2*ones(n,1),0) - diag(ones(n-1,1),-1);
N = diag(ones(n-1,1),1);
A = M - N;
% The Gauss-Seidel iteration matrix is G:
G = M\N;
% Compute the eigendecomposition of A:
[V,Lambda] = eig(A);
% Plot the eigenvectors, and notice that
% as the index k increases, the vectors
% oscillate more and more. In other words,
% their frequency is proportional to k.
for k=1:n,
plot(1:n,V(:,k))
xlabel('i')
ylabel('eigenvector of A')
title(sprintf('Eigenvector %d',k))
disp(sprintf('Plotting eigenvector %d',k))
disp('Press any key to continue.')
pause
end
% Now we see to what extent the Gauss-Seidel iteration
% damps out each of these components. Since any error
% vector can be expanded in these basis vectors, we want
% to verify that a few iterations of GS (1,2,4, or 8)
% effectively damps out the high frequency components --
% those for large values of k -- so that the error
% projected onto the coarse grid effectively represents
% all of the error. Thus GS is a good smoother for
% multigrid applied to this problem.
% We form G V, G^2 V, G^4 V, and G^8 V and plot the
% norm of each column divided by the norm of the original
% column of V (which is 1).
Gp = G;
newV = V;
for p=1:4,
newV = Gp*newV;
for k=1:n,
factor(k,p) = norm(newV(:,k));
end
Gp = Gp * Gp;
end
plot(1:n,factor(:,1),1:n,factor(:,2),1:n,factor(:,3),1:n,factor(:,4))
xlabel('k')
ylabel('|| G^p v_k ||')
title('Reduction factors for p iterations of Gauss Seidel')
axis([1 11 0 1])
legend('p=1','p=2','p=3','p=4')