Term
|
Definition
| Ax = λx. The matrix expands or shrinks any vector lying in the direction of x by a scalar multiple (the eigenvalue). |
|
|
Term
|
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
|
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
|
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
|
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
|
Definition
|
|
Term
|
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
|
Definition
| Every matrix can be transformed into triangular form (Schur form) by a similarity transformation. |
|
|
Term
|
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
|
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
|
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
|
Definition
x = arbitrary nonzero vector
for k = 1, 2, ...
yk= Axk-1
xk = yk/||yk||∞
|
|
|
Term
|
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
|
Definition
Let H be any nonsingular matrix (Householder is a good one) such that Hx1=αe1. Similarity transformation gives
[image]
|
|
|
Term
|
Definition
X0 = arbitrary nxp matrix of rank p
for k = 1,2, ...
Xk = AXk-1 |
|
|
Term
|
Definition
X0 = arbitrary nxp matrix of rank p
for k = 1, 2, ...
compute reduced QR factorization
QkRk=Xk-1
Xk=AQk |
|
|
Term
|
Definition
A0=A
for k = 1, 2, ...
compute QR factorization
QkRk=Ak-1
Ak=RkQk |
|
|
Term
|
Definition
A0=A
for k = 1, 2, ...
Choose shift σk
Compute QR Factorization
QkRk=Ak-1-σkI
Ak=RkQk+σkI |
|
|
Term
|
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
|
Definition
| Krylov subspace method... Each iteration you generate the next vector u = Au. Then orthogonalize against all previous and normalize. |
|
|
Term
|
Definition
| For symmetric (or Hermitian) matrices, H is tridiagonal rather than just Hessenberg. Three term recurrence. |
|
|
Term
|
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 |
|
|
