Description
1. Consider the matrices
A =
1 −1
1 −1.00001
B =
1 −1
−1 1.00001
What is ratio of the largest to smallest eigenvalues (in modulus) for A and for B? Show that
κ2(A) = κ2(B). What can you conclude about the ratio of the largest to smallest eigenvalues as
a way of estimating sensitivity of a linear system? Would you consider A ot be well-conditioned
or ill-conditioned?
2. (a) Find the LU factorization of the matrix:
A =
2 0 5 8
0 2 −1 −3
−2 6 2 −3
4 −4 0 2
(b) Find the PA=LU factorization of A using partial pivoting.
(c) What is the determinant of A?
(e) Using the LU factors obtained in (a) find the second column of the inverse of A, without
computing the whole inverse.
3. (a) Show that if A is Symmetric Positive Definite (SPD) then Trace(AX) > 0 for all SPD
matrices X. (b) Show that if Trace(AX) ≥ 0 for all Symmetric Positive Semi-Definite (PSD)
matrices X then A is PSD.
4. Write Matlab functions to carry out Gaussian Elimination without pivoting to solve a linear
system Ax = b where A is a tridiagonal matrix, stored as three columns (the subdiagonal, the
main diagonal, and the superdiagonal), and b is a vector of all ones of appropriate dimension.
You’ll need to write at least two functions, one to carry out Gaussian Elimination on A, together
with b, and one to solve the resulting triangular system.
Your matlab function should avoid storing the matrix as a full matrix or sparse matrix, though
you can use one of these to check your answers with the Matlab builtin functions. Apply this
function to the matrix formed by the following Matlab expression:
m = 10 or 500 or something bigger;
A_trid = [ [nan; ones(2*m,1)*m ], (m+1+(-m:m)’) , [ones(2*m,1)*m;nan]];
% the following converts the tridiagonal to a full matrix
% (just for the purpose of checking your answers)
A_full = diag(A_trid(:,2))+diag(A_trid(2:end,1),-1)+diag(A_trid(1:end-1,3),1);
1
The right hand side for this will be a vector of all ones of dimension n = 2m + 1, en.
Do all this for m = 500 : 500 : 5000 and time the elapsed time or CPU time for solving the linear
system. To time the process, you can use the Matlab functions tic,toc, etime, or cputime.
Submit a table of CPU or elapsed times together with norms of the residuals. What seems to be
the complexity of solving tridiagonal linear systems? Is it O(n), O(n
2
) or O(n
3
)? Optionally,
solve the linear systems with Matlab explicitly and compare the accuracy and costs of the two
different solutions. Are they close or not?
5. Write a Matlab code that computes the QR factorization of a tridiagonal matrix A stored in
the same compact form as given in the previous question, to solve the same system Ax = b with
b as before as well. The result should be QR = A, with R stored in the similar compact form
as A (need additional space for one extra superdiagonal), and Q should be left as a sequence of
Givens rotations or 2 × 2 Householder transformations. You can apply the Givens rotations or
reflections to b as you go, to obtain QT
b, and then solve the triangular system Rx = QT
b with
a triangular system solver similar to that used in the previous question. In this case, the upper
triangular will have two non-zero diagonals above the main diagonal, instead of just one.
Each Givens rotation of the form
Gij (c, s) =
1
←− col i
←− col j
.
.
.
1
c s ←− row i
−s c ←− row j
1
.
.
.
1
n×n
is specified by the two numbers c, s and the indices of the rows they apply to, where c
2 +s
2 = 1.
In this problem, the first Givens rotation is between rows 1 and 2, so the Givens rotation could
be stored in compact form as a row vector [c, s, 1, 2]. The entire Q is then stored as a stack
of n−1 such row vectors. To check your answers, you would need to write a function to multiply
out these Givens rotations to form the explicit Q to compare with the output from Matlab’s
built-in qr function.
You can also use 2 × 2 Householder reflections if you prefer (you can get the inverse of the
product of such H’s by simply reversing the order – this can save some bookkeeping)
Hij (c, s) =
1
←− col i
←− col j
.
.
.
1
c s ←− row i
s −c ←− row j
1
.
.
.
1
n×n
2