14 Eigenvalues and Eigenvectors.pdf

EIGENVALUES AND EIGENVECTORS DEFINITION OF EIGENVALUES Matrix A and Column Vector x AND Ax represents a linear transformation of x EIGENVECTORS Special Transform Equation Ax = λx...

EIGENVALUES AND EIGENVECTORS DEFINITION OF EIGENVALUES Matrix A and Column Vector x AND Ax represents a linear transformation of x EIGENVECTORS Special Transform Equation Ax = λx Eigenvalue Definition λ that satisfies Ax = λx Eigenvector Definition Vector x corresponding to eigenvalue λ UNDERSTANDING LINEAR TRANSFORMATIONS Vector Multiplication and Transformation Multiplying vector A to vector x transforms x into another vector Transformation represents scaling and/or rotation Effect of Transformation Ax For some vectors, transformation Ax only scales the vector Scaling includes stretching, compressing, and flipping Eigenvectors and Eigenvalues Eigenvectors have the property of only scaling during transformation Eigenvalues (λ) are the scale factors EXAMPLE OF EIGENVALUES AND EIGENVECTORS Transformation of vector [, ] Original vector is rotated and stretched Transformed to [, ] Transformation of vector [, ] Only the length changes Transformed to [, ] Transform is Ax = 2x Eigenvector verification [, ] is another eigenvector Verify by yourself THE Form of Eigenvalue Equation Ax = λx CHARACTERISTIC Transforming the Equation EQUATION (A − λI)x = 0 Identity Matrix I is the identity matrix with the same dimensions as A Trivial Solution If (A − λI) has an inverse, x = 0 Nontrivial Solution When A − λI is singular, det(A − λI) = 0 Characteristic Equation Leads to a polynomial equation for λ INTRODUCTION TO THE POWER Eigenvalues and Eigenvectors Obtained from matrix A METHOD Choice of eigenvectors is not unique Challenges with Larger Matrices Solving nth order polynomial characteristic equation Solution becomes more complicated Numerical Methods for Larger Matrices Developed for matrices with hundreds to thousands of dimensions Power method and QR method introduced FINDING THE Power Method Overview Iterative method to find the largest eigenvalue LARGEST Converges to the largest eigenvalue EIGENVALUE Matrix A and Eigenvalues n × n matrix A with n real eigenvalues Eigenvalues: λ1, λ2,..., λn Ranking Eigenvalues Ranked as |λ1| > |λ2|≥· · · ≥ |λn| Only require |λ1| > |λ2| Linearly Independent Eigenvectors Eigenvectors v1, v2,..., vn are linearly independent Linear Combination of Basis Vectors ITERATIVE First Iteration PROCESS OF New vector x1 is formed x1 = v1 + c2 λ2 v2 + ··· + cn λn vn THE POWER Second Iteration METHOD Apply A to x1 Ax1 = λ1v1 + c2 λ2 v2 + ··· + cn λn vn Rearrangement Ax1 = λ1 (v1 + c2 λ2 v2 + ··· + cn λn vn) Ax1 = λ1x2 Multiplication by A Ax0 = c1Av1 + c2Av2 + ··· + cnAvn Ax0 = c1λ1v1 + c2λ2v2 + ··· + cnλnvn CONVERGENCE Largest Eigenvalue and Corresponding OF THE POWER Eigenvector λ1 is the largest eigenvalue METHOD For large k, terms with λi < 1 can be neglected Normalization of Resulting Vector Factor out the largest element in the vector Largest element in the vector becomes 1 Stopping Criteria for Iteration Difference between eigenvalues is less than a specified tolerance Angle between eigenvectors is smaller than a threshold Norm of the residual vector is small enough EXAMPLE OF THE POWER Convergence Result After seven iterations METHOD Eigenvalue converged to four Corresponding Eigenvector: [0.5, Eigenvector 1] THE INVERSE POWER Eigenvalues of Inverse Matrix METHOD Reciprocals of the eigenvalues of A Inverse Power Method Uses the power method to find the smallest eigenvalue of A Applies A−1 for iteration Practical Application Calculate the inverse of the matrix using methods from previous chapter THE SHIFTED Shifted Power Method POWER Used to find all eigenvalues and eigenvectors METHOD Involves shifting the matrix by the largest eigenvalue Labor intensive and inefficient Applying Power Method to Shifted Matrix Determine largest eigenvalue of shifted matrix Obtain eigenvalue λk easily Repeating process finds all eigenvalues QR Method More efficient method for finding all eigenvalues INTRODUCTION TO THE QR QR Method Overview METHOD Preferred iterative method for finding eigenvalues Does not find eigenvectors simultaneously Key Concepts QR decomposition: Ak = QkRk Forming Ak+1: Ak+1 = RkQk Process Start with matrix A0 Perform QR decomposition at each step All Ak matrices have the same eigenvalues CONVERGENCE OF THE QR Convergence to Upper Triangular Matrix METHOD Iteration leads to upper triangular matrix Diagonal values are eigenvalues of the matrix QR Method Process Factoring matrix into orthogonal and upper triangular matrix Uses Householder matrix Python Function Obtain Q and R matrices directly EIGENVALUES AND EIGENVECTORS IN PYTHON Complexity of Methods Methods introduced are fairly complicated to execute Python's eig Function Built-in function in numpy.linalg Solves eigenvalue/eigenvector problem for square arrays Example Execution Example provided for executing eig function