Class QRAlgorithm
- java.lang.Object
-
- dev.nm.algebra.linear.matrix.doubles.factorization.eigen.qr.QRAlgorithm
-
- All Implemented Interfaces:
Spectrum
public class QRAlgorithm extends 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: A0 = QAQ' as in the explicit version; then, at each step, the first column of Ak is transformed via a small-size Householder similarity transformation to the first column of p(Ak)e1, where p(Ak), 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 Ak 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 Ak 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
-
-
Constructor Summary
Constructors Constructor Description QRAlgorithm(Matrix A)
Runs the QR algorithm on a square matrix.QRAlgorithm(Matrix A, double epsilon)
Runs the QR algorithm on a square matrix.QRAlgorithm(Matrix A, double epsilon, int maxIterations)
Runs the QR algorithm on a square matrix.
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method Description List<Number>
getEigenvalues()
Get all the eigenvalues.List<Vector>
getEigenVectors()
Matrix
Q()
Gets the Q matrix as in the real Schur canonical form Q'AQ = T.List<Matrix>
Qs()
Gets the list of Qi's produced in the process of the QR algorithm (ifkeepQs
is set totrue
).Matrix
T()
-
-
-
Constructor Detail
-
QRAlgorithm
public QRAlgorithm(Matrix A)
Runs the QR algorithm on a square matrix. The algorithm loops until H becomes quasi-triangular.- Parameters:
A
- a matrix- Throws:
IllegalArgumentException
- if A is not square
-
QRAlgorithm
public QRAlgorithm(Matrix A, double epsilon)
Runs the QR algorithm on a square matrix. The algorithm loops until H becomes quasi-triangular.- Parameters:
A
- a square matrixepsilon
- a precision parameter: when a number |x| ≤ ε, it is considered 0
-
QRAlgorithm
public QRAlgorithm(Matrix A, double epsilon, int maxIterations)
Runs the QR algorithm on a square matrix. The algorithm is a convergence algorithm. It stops when either- H becomes quasi-triangular, or
- the maximum number of iterations is reached.
- Parameters:
A
- a square matrixepsilon
- a precision parameter: when a number |x| ≤ ε, it is considered 0maxIterations
- the maximum number of iterations- Throws:
IllegalArgumentException
- if A is not square
-
-
Method Detail
-
getEigenvalues
public List<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 interfaceSpectrum
- Returns:
- the list of eigenvalues
-
Qs
public List<Matrix> Qs()
Gets the list of Qi's produced in the process of the QR algorithm (ifkeepQs
is set totrue
).- Returns:
- the list of Qi's
-
Q
public Matrix Q()
Gets the Q matrix as in the real Schur canonical form Q'AQ = T. The columns of Q are called Schur vectors. If T is diagonal, then the Schur vectors are the eigenvectors. This implementation stores all the Qi'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()
-
-