18.06 Professor Johnson FINAL EXAM May 19, 2009Grading123456Total:Your PRINTED name is:Please circle your recitation:(R01) M2 2-314 Qian Lin(R02) M3 2-314 Qian Lin(R03) T11 2-251 Martina Balagovic(R04) T11 2-229 Inna Zakharevich(R05) T12 2-251 Martina Balagovic(R06) T12 2-090 Ben Harris(R07) T1 2-284 Roman Bezrukavnikov(R08) T1 2-310 Nick Rozenblyum(R09) T2 2-284 Roman BezrukavnikovI AGREE NOT TO DISCUSS THE CONTENTS OF THIS EXAM WITH ANYSTUDENTS WHO HAVE NOT YET TAKEN IT UNTIL AFTER WEDNES-DAY, MAY 20.(YOUR SIGNATURE)1 (18 pts.) A sequence of numbers f0, f1, f2, . . . is defined by the recurrencefk+2= 3fk+1− fk,with starting values f0= 1, f1= 1. (Thus, the first few terms in thesequence are 1, 1, 2, 5, 13, 34, 89, . . ..)(a) Defining uk=fk+1fk, re-express the above recurrence as uk+1=Auk, and give the matrix A.(b) Find the eigenvalues of A, and use these to predict what the ratiofk+1/fkof successive terms in the sequence will approach for large k.(c) The sequence above starts with f0= f1= 1, and |fk| grows rapidlywith k. Keep f0= 1, but give a different value of f1that will makethe sequence (with the same recurrence fk+2= 3fk+1− fk) approachzero (fk→ 0) for large k.2This page intentionally blank.32 (18 pts.) For the matrix A =1 0 −11 1 12 1 0with rank 2, consider the system ofequations Ax = b.(i) Ax = b has a solution whenever b is orthogonal to some nonzerovector c. Explicitly compute such a vector c. Your answer can bemultiplied by any overall constant, because c is any basis for thespace of A.(ii) Find the orthogonal projection p of the vector b =999onto C(A).(Note: The matrix ATA is singular, so you cannot use your formulaP = A(ATA)−1ATto obtain the projection matrix P onto the columnspace of A. But I have repeatedly discouraged you from computing Pexplicitly, so you don’t need to be reminded anyway, right?)(iii) If p is your answer from (ii), then a solution y of Ay = p minimizeswhat? [You need not answer (ii) or compute y for this part.]4This page intentionally blank.53 (12 pts.) True or false. Give a counter-example if false. (You need not provide areason if true.)(a) If Q is an orthogonal matrix, then det Q = 1.(b) If A is a Markov matrix, then du/dt = Au approaches some finiteconstant vector (a “steady state”) for any initial condition u(0).(c) If S and T are subspaces of R2, then their intersection (points in bothS and T ) is also a subspace.(d) If S and T are subspaces of R2, then their union (points in either S orT ) is also a subspace.(e) The rank of AB is less than or equal to the ranks of A and B for anyA and B.(f) The rank of A + B is less than or equal to the ranks of A and B forany A and B.6This page intentionally blank.74 (18 pts.) Consider the matrixA =1 1 11 −1 −11 0 −31 0 −1(a) Find an orthonormal basis for C(A) using Gram-Schmidt, forming thecolumns of a matrix Q.(b) Write each step of your Gram-Schmidt process from (a) as a multi-plication of A on the (left or right) by some invertiblematrix. Explain how the product of these invertible matrices relatesto the matrix R from the QR factorization A = QR of A.(c) Gram-Schmidt on another matrix B (of the same size as A) gives thesame orthonormal basis (the same Q) as in part (a). Which of the foursubspaces, if any, must be the same for the matrices AATand BBT?[You can do this part without doing (a) or (b).]8This page intentionally blank.95 (16 pts.) The complete solution to Ax = b isx =10−1+ c110+ d−201for any arbitrary constants c and d.(i) If A is an m × n matrix with rank r, give as much true information aspossible about the integers m, n, and r.(ii) Construct an explicit example of a possible matrix A and a possibleright-hand side b with the solution x above. (There are many accept-able answers; you only have to provide one.)10This page intentionally blank.116 (18 pts.) Consider the matrixA =1 −1 −1−1 1 −1−1 −1 1(i) A has one eigenvalue λ = −1, and the other eigenvalue is a double rootof det(A − λI). What is the other eigenvalue? (Very little calculationrequired.)(ii) Is A defective? Why or why not?(iii) Using the above A, suppose we want to solve the equationdudt= Au + cuwhere c is some real number, for some initial condition u(0).(a) For what values of c will the solutions u(t) always to go zero ast → ∞?(b) For what values of c will the solutions u(t) typically diverge (ku(t)k →∞) as t → ∞?(c) For what values of c will the solutions u(t) approach a constantvector (possibly zero) as t → ∞?12This page intentionally
View Full Document
Unlocking...