com.numericalmethod.suanshu.matrix.doubles.factorization.eigen.qr

Class QRAlgorithm

java.lang.Object

com.numericalmethod.suanshu.matrix.doubles.factorization.eigen.qr.QRAlgorithm

All Implemented Interfaces:

Spectrum, java.io.Serializable

public class QRAlgorithm
extends java.lang.Object
implements Spectrum

The QR algorithm is an eigenvalue algorithm by computing the real Schur canonical form of a matrix. That is, Q'AQ = T where Q is orthogonal, and T is quasi-triangular. The eigenvalues of A are the same as those of the diagonal blocks in T. The basic idea of the procedure is to perform the QR decomposition, writing the matrix as a product of an orthogonal matrix and an upper triangular matrix, multiply the factors in the opposite order, and iterate.

This implementation is the implicit double-shift version. It makes the use of multiple shifts easier to introduce. The matrix is first brought to the upper Hessenberg form: A₀ = QAQ' as in the explicit version; then, at each step, the first column of A_k is transformed via a small-size Householder similarity transformation to the first column of p(A_k)e₁, where p(A_k), of degree r, is the polynomial that defines the shifting strategy. Then successive Householder transformation of size r+1 are performed in order to return the working matrix A_k to the upper Hessenberg form. This operation is known as bulge chasing, due to the peculiar shape of the non-zero entries of the matrix along the steps of the algorithm. Deflation is performed as soon as one of the sub-diagonal entries of A_k is sufficiently small. No QR decomposition is explicitly performed. Instead, we use the Francis algorithm (FrancisQRStep), as described in Golub and Van Loan.

See Also:

Wikipedia: QR algorithm, Serialized Form

Constructor Summary

Constructors

Constructor and Description
QRAlgorithm(Matrix A) Run the QR algorithm on a square matrix.
QRAlgorithm(Matrix A, int maxIterations, double epsilon) Run the QR algorithm on a square matrix.

Method Summary

Modifier and Type	Method and Description
java.util.List<java.lang.Number>	getEigenvalues() Get all the eigenvalues.
Matrix	Q() Get the Q matrix as in the real Schur canonical form Q'MQ = T.
Matrix	T() Get the T matrix as in the real Schur canonical form Q'MQ = T.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

QRAlgorithm

public QRAlgorithm(Matrix A,
                   int maxIterations,
                   double epsilon)

Run the QR algorithm on a square matrix. The algorithm is a convergence algorithm. It stops when either

1. H becomes quasi-triangular, or
2. the maximum number of iterations is reached.

Parameters:

A - a square matrix

maxIterations - the maximum number of iterations

epsilon - a precision parameter: when a number |x| ≤ ε, it is considered 0

Throws:

java.lang.IllegalArgumentException - if A is not square

QRAlgorithm

public QRAlgorithm(Matrix A)

Run the QR algorithm on a square matrix. The algorithm loops until H becomes quasi-triangular.

Parameters:

A - a matrix

Throws:

java.lang.IllegalArgumentException - if A is not square

Method Detail

getEigenvalues

public java.util.List<java.lang.Number> getEigenvalues()

Get all the eigenvalues. Given a Hessenberg matrix, \[ \begin{bmatrix} H_{11} & H_{12} & H_{13}\\ 0 & H_{22} & H_{23}\\ 0 & 0 & H_{33} \end{bmatrix} \] the real Schur canonical form is Q'HQ = T, where Q is orthogonal, and T is quasi-triangular.

This implementation is a modified version of the algorithm in the reference.

Specified by:

getEigenvalues in interface Spectrum

Returns:

the list of eigenvalues

See Also:

"G. H. Golub, C. F. van Loan, "Algorithm 7.5.2," Matrix Computations, 3rd edition."

Q

public Matrix Q()

Get the Q matrix as in the real Schur canonical form Q'MQ = T. The columns of are called Schur vectors. If T is diagonal, then the Schur vectors are the eigenvectors.

This implementation stores all the Q_i's produced in the process of the QR algorithm. Q is a product of them. That is, \[ Q = (Q_1 \times ... \times Q_n) \]

Returns:

Q

T

public Matrix T()

Get the T matrix as in the real Schur canonical form Q'MQ = T. T is quasi upper triangular. The eigenvectors of A are the same as those of T.

Returns:

T

See Also:

"James W. Demmel, Applied Numerical Linear Algebra, SIAM; 1 edition (August 1, 1997)."