Prelim 1 Review

Some study questions are below.

Here is an old prelim with solutions.

Questions that relate to assignments A1, A2, and A3 can be expected.

The syllabus page has details about what sections in Chapters 1-5 are relevant.

--------------------------------------------------------------------------------

11. Use the SVD to characterize

                                     norm(A*x(lambda) - b,2)^2

where x(lambda) solves the linear system  (A'*A + lambda^2*I )x = A'*b.

10. Suppose f and g are column n-vectors. Show how to compute an orthogonal Q as a product of Givens rotations so that Q' * (f * g') * Q  is zero everywhere except in the (1,1) and (1,2) entry. Hint. Put a lot of zeros into f and then put a lot of zeros in g. Hint: If (Q'*f)*(Q'*g)'  has all those zeros then Q'* had better be zero in all but component 1 and Q'*g had better be zero everywhere except components 1 and 2.

9. Suppose u is a unit m-vector and u(1:k-1) = 0. Suppose A is an m-by-n matrix. Carefully show how you would overwrite A with H*A where H = I - 2*u*u'. (b) Given c and s so c^2 + s^2 = 1, find c1 and s1 so that c1^2 + s1^2 = 1 and (I-2vv') = [c s;s -c] where v = [c1;s1].

 

8.  If  A is n-by-n, symmetric, and positive definite, explain why A(1:n-1,1:n-1) is symmetric and positive definite. Suppose b is a given column n-vector. How would you go about computing x and y so that Ax = b and A(1:n-1,1:n-1)y = b(1:n-1)?

7.. What is the exact 1-norm condition of the matrix U = eye(n,n) - triu(ones(n,n),1))?

6.. Suppose x and y are two positive, normalized floating numbers. (Assume IEEE double precision.)  Exactly how many floating point numbers are there  in between x and y given that

                                                           log2(x) = e1 <  e2 = log2(y)

and that neither x or y is an integral power of two.

5.. Suppose A is n-by-n and b, c, and d are column n-vectors. How would you compute x, y, and z so Ax = b, A'y=d and A(n:-1:1,,n:-1:1)z = d? Hint: live off of a single LU factorization.

4..  Modify this implementation so that it efficiently performs as advertised.

function x = Solve(A,b)
% Solves Ax = b
[n,n] = size(A);
for k=1:n-1
   m = A(k+1:n,k)/A(k,k);
   A(k+1:n,k+1:n) = A(k+1:n,k+1:n) - m*A(k,k+1:n)
end
 
 

3.. Suppose C, D, E, F, G, H, and Z are initialized n-by-n matrices. Assume that b is a 3n-by-1 vector. How would you solve [C D E; Z F G; Z Z Z]*x = b assuming that Z = zeros(n,n)? You may use the backslash operator.

2. Suppose A is m-by-n, B is n-by-p, C is p-by-q, and D is q-by-r. How would you compute F = ABCD if minimizing flops is the goal? How does your answer change if the four matrices are all square and B and C have zeros below their diagonal?

1. Suppose A is an initialized n-by-n matrix and y and z are initialized n-by-1 vectors. What is the dimension of B = z*y'*A and how would you compute it? How many flops would be required by your method?