# Shared Flashcard Set

## Details

Algebraic Eigenvalue Problems
Power method; QR iteration; Krylov Subspace methods; Jacobi iteration
30
Computer Science
03/03/2014

Term
 Eigenvalues
Definition
 Ax = λx.   The matrix expands or shrinks any vector lying in the direction of x by a scalar multiple (the eigenvalue).
Term
 Eigenvectors
Definition
 Ax = λx.  Any vector in a given direction that is shrunk or expanded by a scalar multiple when multiplied by A.
Term
 Characteristic Polynomial
Definition
 (A-λI)x = 0 has a nonzero solution only if the matrix is singular.  So det(A-λI) must equal 0, where det(A-λI) is a polynomial of degree n.  Roots = eigenvalues of A.
Term
 Cayley-Hamilton Theorem
Definition
 An nxn matrix satisfies its own characteristic equation, that is, if p(λ) = c0 + c1λ + ... + cn-1λn-1 + λn = 0 then p(A) = c0 + c1A + ... + cn-1An-1 + An = 0
Term
 Algebraic and Geometric Multiplicity
Definition
 Algebraic multiplicity is the number of times a given eigenvalue appears.  The multiplicity as a root of the characteristic polynomial. Geometric multiplicity is the number of linearly independent eigenvectors corresponding to the eigenvalue.
Term
 Defective matrix
Definition
 If geometric multiplicity is less than algebraic multiplicity, the nxn matrix has fewer than n linearly independent eigenvectors and it is said to be defective.  This means it is not diagonalizable
Term
 Diagonalizable matrix
Definition
 Any nondefective matrix has a full set of linearly independent eigenvectors, let D be a diagonal matrix of eigenvalues and X be a matrix of eigenvectors.  X is nonsingular.  AX = DX can be rewritten as X-1AX = D, so A is diagonalizable.
Term
 Normal Matrices
Definition
 AAT = ATA
Term
 Invariant Subspaces
Definition
 For a given matrix A, a given subspace S of Rn is said to be an invariant supspace if AS is a subset of S.  i.e. if x in S implies Ax in S.
Term
 Schur Form
Definition
 Every matrix can be transformed into triangular form (Schur form) by a similarity transformation.
Term
 real Schur form
Definition
 A block triangular matrix with only real entries, having 1x1 or 2x2 diagonal blocks corresponding to real eigenvalues and complex conjugate pairs of eigenvalues respectively.
Term
 Jordan Form
Definition
 The closest any general matrix can come to diagonal form.  The matrix is reduced to nearly diagonal form, but may yet have a few nonzero entries in the first superdiagonal corresponding to one or more multiple eigenvalues. Cannot be computed stably.
Term
 Gershgorin Theorem
Definition
 The eigenvalues of an nxn matrix A are all contained within the union of n disks, with the kth disk centered at akk and having radius ∑j≠k|akj|.
Term
 Problem Transformations: Shift
Definition
 Subtracts a constant scalar from each diagonal entry of a matrix, shifting the origin of the real line or complex plane. (A-σI)x=(λ-σ)x.
Term
 Problem Transformation: Inversion
Definition
 If A is nonsingular, and Ax = λx for nonzero x, then λ is nonzero so A-1x=(1/λ)x.
Term
 Problem Transformation: Powers
Definition
 If Ax = λx, then A2x = λ2x.  Taking the kth power of a matrix also takes the kth power of the eigenvalues without changing the eigenvectors
Term
 Problem Transformations: Polynomials
Definition
 If p(t) = c0 + c1t + c2t2 + ... + cktk then p(A) = c0 + c1A + c2A2 + ... + ckAk. If Ax = λx then p(A)x = p(λ)x.
Term
 Problem Transformations: Similarity
Definition
 A matrix B is similar to a matrix A if there is a nonsingular matrix T such that B = T-1AT.  By = λy T-1ATy = λy ATy = λTy x = Ty
Term
 Power Method
Definition
 x = arbitrary nonzero vector for k = 1, 2, ...     yk= Axk-1     xk = yk/||yk||∞
Term
 Inverse iteration
Definition
 x0=arbitrary nonzero vector for k = 1, 2, ...     Solve Ayk=xk-1 for yk     xk=yk/||yk||∞
Term
 Raleigh Quotient Iteration
Definition
 x0=arbitrary nonzero vector for k = 1, 2, ...      σk = xk-1TAxk-1/xk-1Txk-1     Solve (A - σkI)yk = xk-1     xk=yk/||yk||∞
Term
 Deflation
Definition
 Let H be any nonsingular matrix (Householder is a good one) such that Hx1=αe1.  Similarity transformation gives  [image]
Term
 Simultaneous Iteration
Definition
 X0 = arbitrary nxp matrix of rank p for k = 1,2, ...     Xk = AXk-1
Term
 Orthogonal Iteration
Definition
 X0 = arbitrary nxp matrix of rank p for k = 1, 2, ...     compute reduced QR factorization         QkRk=Xk-1     Xk=AQk
Term
 QR Iteration
Definition
 A0=A for k = 1, 2, ...     compute QR factorization         QkRk=Ak-1     Ak=RkQk
Term
 QR Iteration with Shifts
Definition
 A0=A for k = 1, 2, ...     Choose shift σk     Compute QR Factorization         QkRk=Ak-1-σkI     Ak=RkQk+σkI
Term
 Krylov Subspace Methods
Definition
 Build up a subspace incrementally, one vector at a time.  Let A be an nxn matrix, x0 an arbitrary starting vector, and for k>0, define the Krylov sequence xk=Axk-1 Krylov Matrix - Kk = [x0 x1 ... xk-1] Krylov subspace span(Kk)
Term
 Arnoldi Iteration
Definition
 Krylov subspace method... Each iteration you generate the next vector u = Au.  Then orthogonalize against all previous and normalize.
Term
 Lanczos Iteration
Definition
 For symmetric (or Hermitian) matrices, H is tridiagonal rather than just Hessenberg.  Three term recurrence.
Term
 Jacobi Method
Definition
 Plane Rotations (like Givens) A0=A (real symmetric matrix) Ak+1=JkTAkJk where J is a plane rotation chosen to annihilate a symmetric pair of entries
Supporting users have an ad free experience!