The QR Decomposition
The QR decomposition or QR factorization of a matrix expresses the matrix as the product of an orthogonal matrix and an upper triangular matrix. The matrix can be of any type, and of any shape. The QR decomposition is usually written as
A = QR,
where Q is a square, orthogonal matrix (or a unitary matrix if A is complex), and R is an upper-triangular matrix. The QR algorithm uses orthogonal (or unitary) transformations. This gives the QR decomposition much better numerical stability than the LU decomposition, even though the computation takes twice as long. When the matrix is ill-conditioned, or high accuracy is required, the longer running time is justified.
Working with QR Decompositions
The QR decomposition is implemented by the QRDecomposition<T> class. It has no constructors. Instead, it is created by calling the GetQRDecomposition method on the matrix. This method has two overloads. The first overload has no arguments. The second overload takes a Boolean value that specifies whether the contents of the matrix may be overwritten by the QR decomposition. The default is false.
var A = Matrix.CreateFromArray(5, 3, new double[] {
2.0, 2.0, 1.6, 2.0, 1.2,
2.5, 2.5,-0.4,-0.5,-0.3,
2.5, 2.5, 2.8, 0.5,-2.9
}, MatrixElementOrder.ColumnMajor);
var qr = A.GetQRDecomposition();The Decompose method performs the actual decomposition. This method copies the matrix if necessary. It then calls the appropriate LAPACK routine to perform the actual decomposition. This method is called by other methods as needed. You will rarely need to call it explicitly.
Once the decomposition is computed, a number of operations can be performed in much less time. You can repeatedly solve a system of simultaneous linear equations with different right-hand sides. If the system is overdetermined, you can use the LeastSquaresSolve method to obtain a least squares solution to an over-determined system. If the matrix is square, you can also calculate the determinant and the inverse of the base matrix:
var b = Vector.Create(1.1, 0.9, 0.6, 0.0, -0.8);
var x = qr.LeastSquaresSolve(b);The OrthogonalFactor property returns orthogonal matrix, Q, of the decomposition. The UpperTriangularFactor property returns a TriangularMatrix<T> containing the upper triangular matrix, R:
var Q = qr.OrthogonalFactor;
var R = qr.UpperTriangularFactor;
var R2 = qr.TrimmedUpperTriangularFactor;The matrix Q is kept in a compact format. Although it is possible to convert it to a regular dense matrix, the calculation is fairly expensive. Fortunately, this is hardly ever necessary. Operations like transposition, multiplication, and solving (which is equivalent to multiplying by the transpose for an orthogonal matrix) avoid the conversion:
var Qx = Q * x;
var QTx = Q.Transpose() * x;
var QTx2 = Q.Solve(x);When the number of rows of the matrix A is greater than the number of columns, the triangular matrix R will contain rows of zeros below the diagonal. The columns of Q that are multiplied by these rows in the product QR do not contribute to the product. In this scenario, two further properties may be useful. The TrimmedUpperTriangularFactor property returns the square part of the matrix R, with the zero rows removed. The ThinOrthogonalFactor property returns the orthogonal matrix with the columns that don't contribute to the product removed.
The RQ, QL, and LQ Decompositions
There are several matrix decompositions that are closely related to the QR decomposition. The RQ decomposition factors a matrix into a product RQ, where R is an upper triangular matrix and Q is an orthogonal matrix. The QL decomposition factors a matrix into a product QL, where L is a lower triangular matrix, and the LQ decomposition factors matrix into a product LQ.
These decompositions are implemented by the RQDecomposition<T>, QLDecomposition<T>, and LQDecomposition<T> classes, respectively. They work in exactly the same way as the QR decomposition. There are GetRQDecompositionGetQLDecompositionGetLQDecomposition methods that return the decomposition for a specific matrix. The properties are analogous, including the trimmed and thin versions.