10.3 POWER METHOD FOR APPROXIMATING EIGENVALUES

1 550 CHAPTER 10 NUMERICAL methods . POWER METHOD FOR APPROXIMATING EIGENVALUES . In Chapter 7 we saw that the EIGENVALUES of an n 3 n matrix A are obtained by solving its characteristic equation ln 1 cn21ln21 1 cn22ln22 1 .. 1 c0 5 0. For large values of n, polynomial equations like this one are difficult and time-consuming to solve. Moreover, numerical techniques for APPROXIMATING roots of polynomial equations of high degree are sensitive to rounding errors. In this section we look at an alternative METHOD for APPROXIMATING EIGENVALUES . As presented here, the METHOD can be used only to find the eigenvalue of A that is largest in absolute value we call this eigenvalue the dominant eigenvalue of A.

2 Although this restriction may seem severe, dominant eigenval- ues are of primary interest in many physical applications. Definition of Dominant Let l1, l2, .. , and ln be the EIGENVALUES of an n 3 n matrix A. l1 is called the Eigenvalue and dominant eigenvalue of A if Dominant Eigenvector |l | > |l |, 1 i i 5 2, .. , n. The eigenvectors corresponding to l1 are called dominant eigenvectors of A. Not every matrix has a dominant eigenvalue. For instance, the matrix 30 4. 1 0. A5. 21. (with EIGENVALUES of l1 5 1 and l2 5 21) has no dominant eigenvalue. Similarly, the matrix 3 4.

3 2 0 0. A5 0 2 0. 0 0 1. (with EIGENVALUES of l1 5 2, l2 5 2, and l3 5 1) has no dominant eigenvalue. EXAMPLE 1 Finding a Dominant Eigenvalue Find the dominant eigenvalue and corresponding eigenvectors of the matrix 2 212. A5 31 25.. 4. Solution From Example 4 of Section we know that the characteristic polynomial of A is l2 1 3l 1 2 5 (l 1 1)(l 1 2). Therefore the EIGENVALUES of A are l1 5 21 and l2 5 22, of which the dominant one is l2 5 22. From the same example we know that the dominant eigenvectors of A (those corresponding to l2 5 22) are of the form 3 14, 3. x5t t 0.

4 SECTION POWER METHOD FOR APPROXIMATING EIGENVALUES 551. The POWER METHOD Like the Jacobi and Gauss-Seidel methods , the POWER METHOD for APPROXIMATING eigenval- ues is iterative. First we assume that the matrix A has a dominant eigenvalue with corre- sponding dominant eigenvectors. Then we choose an initial approximation x0 of one of the dominant eigenvectors of A. This initial approximation must be a nonzero vector in Rn. Finally we form the sequence given by x1 5 Ax0. x2 5 Ax1 5 A(Ax0) 5 A2x0. x3 5 Ax2 5 A(A2x0) 5 A3x0.. xk 5 Axk21 5 A(Ak21x0) 5 Akx0. For large powers of k, and by properly scaling this sequence, we will see that we obtain a good approximation of the dominant eigenvector of A.

5 This procedure is illustrated in Example 2. EXAMPLE 2 APPROXIMATING a Dominant Eigenvector by the POWER METHOD Complete six iterations of the POWER METHOD to approximate a dominant eigenvector of 2 212. A5 31 25.. 4. Solution We begin with an initial nonzero approximation of 34. 1. x0 5 . 1. We then obtain the following approximations. Iteration Approximation 2 212 1 210. 31 43 4 3 4 x1 5 Ax0 5 5 24. 25 1 24. 2 212 210. 31 43 4 3 4 28 x2 5 Ax1 5 5 10. 25 24 10. 2 212 28 264. 31 2543104 5 32224 x3 5 Ax2 5 222. 2 212 264. 53. 1 25432224 3 464. 463. 136 x4 5 Ax3 5. 2 212 136 2280.

6 53. 1 2543 464 3 2944. 2943. x5 5 Ax4 5. 2 212 2280. 53 43 4 53 4 1903. 568 x6 5 Ax5. 1 25 294 190. 552 CHAPTER 10 NUMERICAL methods . Note that the approximations in Example 2 appear to be approaching scalar multiples of 314, 3. which we know from Example 1 is a dominant eigenvector of the matrix 2 212. A5 31 25.. 4. In Example 2 the POWER METHOD was used to approximate a dominant eigenvector of the matrix A. In that example we already knew that the dominant eigenvalue of A was l 5 22. For the sake of demonstration, however, let us assume that we do not know the dominant eigenvalue of A.

7 The following theorem provides a formula for determining the eigenvalue corresponding to a given eigenvector. This theorem is credited to the English physicist John William Rayleigh (1842 1919). Theorem If x is an eigenvector of a matrix A, then its corresponding eigenvalue is given by Ax ? x Determining an Eigenvalue l5 . x?x from an Eigenvector This quotient is called the Rayleigh quotient. Proof Since x is an eigenvector of A, we know that Ax 5 lx, and we can write Ax ? x lx ? x l(x ? x). 5 5 5 l. x?x x?x x?x In cases for which the POWER METHOD generates a good approximation of a dominant eigenvector, the Rayleigh quotient provides a correspondingly good approximation of the dominant eigenvalue.

8 The use of the Rayleigh quotient is demonstrated in Example 3. EXAMPLE 3 APPROXIMATING a Dominant Eigenvalue Use the result of Example 2 to approximate the dominant eigenvalue of the matrix 2 212. A5 31 25.. 4. Solution After the sixth iteration of the POWER METHOD in Example 2, we had obtained. 3 4 3 4. 568 x6 5 < 190 . 190 With x 5 ( , 1) as our approximation of a dominant eigenvector of A, we use the Rayleigh quotient to obtain an approximation of the dominant eigenvalue of A. First we compute the product Ax. SECTION POWER METHOD FOR APPROXIMATING EIGENVALUES 553.

9 2 212 31 4 5 Ax 5. 25. Then, since Ax ? x 5 ( )( ) 1 ( )(1) < and x ? x 5 ( )( ) 1 (1)(1) < , we compute the Rayleigh quotient to be Ax ? x l5 < < , x?x which is a good approximation of the dominant eigenvalue l 5 22. From Example 2 we can see that the POWER METHOD tends to produce approximations with large entries. In practice it is best to scale down each approximation before pro- ceeding to the next iteration. One way to accomplish this scaling is to determine the com- ponent of Axi that has the largest absolute value and multiply the vector Axi by the reciprocal of this component.

10 The resulting vector will then have components whose absolute values are less than or equal to 1. (Other scaling techniques are possible. For examples, see Exercises 27 and 28. EXAMPLE 4 The POWER METHOD with Scaling Calculate seven iterations of the POWER METHOD with scaling to approximate a dominant eigenvector of the matrix 3 4. 1 2 0. A 5 22 1 2 . 1 3 1. Use x0 5 (1, 1, 1) as the initial approximation. Solution One iteration of the POWER METHOD produces 3 43 4 3 4. 1 2 0 1 3. Ax0 5 22 1 2 1 5 1 , 1 3 1 1 5. and by scaling we obtain the approximation 34 3 4. 3 x1 5 15 1 5.)