Exercise 6.8: The QR algorithm In this exercise you'll write a program to calculate the eigenvalues and eigenvectors of a real symmetric matrix using the QR algorithm. The first challenge is to write a program that finds the QR decomposition of a matrix. Then we'll use that decomposition to find the eigenvalues. As described above, the QR decomposition expresses a real square matrix A in the form A = QR, where Q is an orthogonal matrix and R is an upper-triangular matrix. Given an N X N matrix A we can compute the QR decomposition as follows. Let us think of the matrix as a set of N column vectors an .. .an-1 thus: A = ao a1 a2 where we have numbered the vectors in Python fashion, starting from zero, which will be convenient when writing the program. We now define two new sets of vectors up . .. UN-1 and 90 . . . qN-1 as follows: up = a0, 90 u1 uj = a1 - (90 . a1) 90, 91 = u1 U2 U2 = a2 - (90 . a2) q0 - (91 . a2) q1, 92 U2and so forth. The general formulas for calculating a, and q,- are U: ml i1 u;- = a,- 20% ' 30% ch = | j=0 a) Show, by induction or otherwise, that the vectors q, are orthonormal, i.e., that they satisfy ' q _ _ 1 if 1' = j, '1' qt' 0 ifiaj. Now, rearranging the definitions of the vectors, we have an = luol '10: a1 =|111|11+(q0'31)10: a2 = |u2| f~12 + (90 ' 32MB +(CI1'32)611: and so on. Or we can group the vectors q,- together as the columns of a matrix and write all of these equations as a single matrix equation I | | I I I IuII $1011 Gn'az A: 3.0 3.1 32 = CH] q1 q2 0 lull q1.a2 ... _ I I I I I I 0 0 '11,. (If this looks complicated it's worth multiplying out the matrices on the right to verify for yourself that you get the correct expressions for the a,.) Notice now that the first matrix on the right-hand side of this equation, the matrix with columns q,-, is orthogonal, because the vectors q,- are orthonormal, and the second matrix is upper triangular. In other words, we have found the QR decomposition A = QR. The matrices QandRare I l l luul '1'31 I310"\":12 Q: q\" (11 q: ... 1 R: U lull 511.32 ... _ I | l U {j lull