Name Michelle Yun AMATH 352 Final Review Practice Problems 1 Compute the reduced QR decomposition of the following matrix 1 0 1 1 2 1 A Therefore Q will be in R3 2 and R will be in R2 2 The general formula for cid 28 nding each column of Q is a Find pk ak cid 80 k 1 b qk pk cid 107 pk cid 107 Applying this formula i 1 cid 104 ak qi cid 105 qi 6 cid 43 1 6 1 6 2 6 p2 a2 cid 104 a2 q1 cid 105 q1 cid 107 p1 cid 107 q1 p1 a1 1 2 1 2 1 6 cid 112 6 1 6 2 6 12 12 22 1 1 1 1 cid 42 0 0 1 0 3 1 0 1 cid 114 1 6 1 6 2 6 6 1 6 2 6 1 2 2 1 2 1 1 2 0 1 2 1 2 1 1 1 1 1 1 1 1 2 6 2 2 2 2 2 2 2 2 0 1 2 0 cid 107 p2 cid 107 q2 Each element of R ri j will be cid 104 aj qi cid 105 1 2 R cid 35 3 6 2 2 0 cid 20 cid 104 a1 q1 cid 105 Q cid 2 q1 cid 104 a2 q1 cid 105 cid 104 a2 q2 cid 105 cid 21 1 6 1 6 2 6 cid 34 6 6 0 2 2 2 2 0 cid 3 q2 2 Suppose you compute the QR decomposition and then compute the SVD decomposition of R R Ur V T A QR Write down a singular value decomposition for A and verify that your decomposition satis cid 28 es the de cid 28 nition The following conditions have to be satis cid 28 ed for the SVD to be valid a U T U I b must be a diagonal matrix with non negative entries and the diagonal entries should be ordered from greatest to smallest c V T V I Rewriting A QR QUr V T We can let U QUr and what remains is to show that the above three conditions are satis cid 28 ed The last two conditions are satis cid 28 ed because we were already given the SVD fpr R To check the cid 28 rst condition QT Q QUr T QUr r QT QUr r IUr r Ur U T U T U T I Remember that QT Q I from the de cid 28 nition of the QR decomposition and U T r Ur I comes from the SVD of R 3 Suppose you want to cid 28 t a cubic polynomial to the set of points written in format xi yi 2 1 0 1 1 0 2 1 3 0 Write down the linear system A and vector b for the least squares problem you would need to solve into this equation gives A generic cubic polynomial looks like this ax3 bx2 cx d Plugging the given points 3 Simplifying These equations can be put into a matrix A and vector b 1 a 2 3 b 2 2 c 2 d 1 a 0 3 b 0 2 c 0 d 0 a 1 3 b 1 2 c 1 d 1 a 2 3 b 2 2 c 2 d 0 a 3 3 b 3 2 c 3 d 1 8a 4b 2c d 1 d 0 a b c d 1 8a 4b 2c d 0 27a 9b 3c d A 8 4 2 1 1 0 1 1 8 1 1 27 0 1 4 9 0 1 2 3 1 1 0 1 0 b 1 3 0 2 3 1 3 1 3 1 3 0 1 2 1 2 4 Suppose you have a Markov chain with 3 states with the following transition probability matrix a If you start in state 1 what is the chance that you will be in state 3 after one step cid 2 1 0 0 cid 3 Multiplying this vector by the transition matrix gives The problem states that we start in state 1 so that means that our starting state is cid 2 1 0 0 cid 3 1 3 0 2 3 1 3 1 3 1 3 1 2 1 2 0 cid 2 1 3 cid 3 0 2 3 So there is a 2 3 chance to be in state 3 given that you start in state 1 b If you are equally likely to start in any state what s the likelihood you are in state 2 after one step The problem states that there is an equal probability to start in any state so that means that every entry in the starting state vector will be 1 this vector by the transition matrix gives 1 3 1 3 3 3 cid 2 1 cid 3 Multiplying 4 cid 2 1 3 cid 3 1 3 1 3 1 3 0 2 3 1 3 1 3 1 3 1 2 1 2 0 cid 2 2 9 cid 3 5 18 1 2 So there is a 5 starting in any state 18 chance to be in state 2 given that there is an equal probability of c After 1000 steps what is the chance that you arein state 1 To cid 28 nd the steady state distribution we need to cid 28 nd the left eigenvector of the transition matrix that corresponds to an eigenvalue of 1 This is equivalent to cid 28 nding the right eigenvector of AT for an eigenvalue of 1 AT 0 0 1 3 1 2 2 3 1 3 1 2 1 3 1 3 2 3 1 3 0 2 3 0 0 1 2 2 3 1 2 Since we know that the eigenvalue must be 1 we can skip straight to cid 28 nding a basis for the null space of AT I 2 3 0 2 3 AT I 0 1 3 2 3 1 2 1 3 1 2 2 3 1 3 0 0 0 2 3 1 2 0 0 2 3 2 3 x2 3 4 1 2 1 3 x3 x2 x2 2 3 x3 x3 x1 x1 x1 3 8 or after normalizing by the sum of the elements 3 8 1 4 x3 3 17 6 17 8 17 So an eigenvector is 3 4 1 This means that there will be a 3 17 chance to be in state 1 after 1000 steps 5 Consider the matrix A uvT where u Rm 1 and v Rn 1 a What is the rank of A Find a basis for the range of A If A uvT then each column of A is just a scalar multiple of the vector u so a basis for the range of A is u and the rank of A is 1 b Find an eigenvalue eigenvector pair for A Au uvT u u vT u vT u u so u is an eigenvector with eigenvalue vT u …