// Catalano Math Library
// The Catalano Framework
//
// Copyright © Diego Catalano, 2012-2016
// diego.catalano at live.com
//
// Original work copyright © JAMA: A Java Matrix Package
// http://math.nist.gov/javanumerics/jama/
//
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
//
package Catalano.Math.Decompositions;
import Catalano.Math.Tools;
/** QR Decomposition.
For an m-by-n matrix A with m >= n, the QR decomposition is an m-by-n
orthogonal matrix Q and an n-by-n upper triangular matrix R so that
A = Q*R.
The QR decompostion always exists, even if the matrix does not have
full rank, so the constructor will never fail. The primary use of the
QR decomposition is in the least squares solution of nonsquare systems
of simultaneous linear equations. This will fail if isFullRank()
returns false.
*
*/
public class QRDecomposition implements java.io.Serializable {
/** Array for internal storage of decomposition.
@serial internal array storage.
*/
private double[][] QR;
/** Row and column dimensions.
@serial column dimension.
@serial row dimension.
*/
private int m, n;
/** Array for internal storage of diagonal of R.
@serial diagonal of R.
*/
private double[] Rdiag;
/**
* Initializes a new instance of the QRDecomposition class.
* @param matrix Matrix.
*/
public QRDecomposition (double[][] matrix) {
// Initialize.
QR = matrix.clone();
m = matrix.length;
n = matrix[0].length;
Rdiag = new double[n];
// Main loop.
for (int k = 0; k < n; k++) {
// Compute 2-norm of k-th column without under/overflow.
double nrm = 0;
for (int i = k; i < m; i++) {
nrm = Tools.Hypotenuse(nrm,QR[i][k]);
}
if (nrm != 0.0) {
// Form k-th Householder vector.
if (QR[k][k] < 0) {
nrm = -nrm;
}
for (int i = k; i < m; i++) {
QR[i][k] /= nrm;
}
QR[k][k] += 1.0;
// Apply transformation to remaining columns.
for (int j = k+1; j < n; j++) {
double s = 0.0;
for (int i = k; i < m; i++) {
s += QR[i][k]*QR[i][j];
}
s = -s/QR[k][k];
for (int i = k; i < m; i++) {
QR[i][j] += s*QR[i][k];
}
}
}
Rdiag[k] = -nrm;
}
}
/**
* Check if the matrix is full rank.
* @return True if R, and hence A has full rank, otherwise false.
*/
public boolean isFullRank () {
for (int j = 0; j < n; j++) {
if (Rdiag[j] == 0)
return false;
}
return true;
}
/**
* Get the Householder vectors.
* @return Lower trapezoidal matrix whose columns define the reflections.
*/
public double[][] getH () {
double[][] X = new double[m][n];
double[][] H = X;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i >= j) {
H[i][j] = QR[i][j];
} else {
H[i][j] = 0.0;
}
}
}
return X;
}
/**
* Get the upper triangular factor.
* @return Upper triangular factor.
*/
public double[][] getR () {
double[][] X = new double[n][n];
double[][] R = X;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i < j) {
R[i][j] = QR[i][j];
} else if (i == j) {
R[i][j] = Rdiag[i];
} else {
R[i][j] = 0.0;
}
}
}
return X;
}
/**
* Generate the (economy-sized) orthogonal factor.
* @return Economy-sized orthogonal factor.
*/
public double[][] getQ () {
double[][] X = new double[m][n];
double[][] Q = X;
for (int k = n-1; k >= 0; k--) {
for (int i = 0; i < m; i++) {
Q[i][k] = 0.0;
}
Q[k][k] = 1.0;
for (int j = k; j < n; j++) {
if (QR[k][k] != 0) {
double s = 0.0;
for (int i = k; i < m; i++) {
s += QR[i][k]*Q[i][j];
}
s = -s/QR[k][k];
for (int i = k; i < m; i++) {
Q[i][j] += s*QR[i][k];
}
}
}
}
return X;
}
/**
* Least squares solution of A*X = B
* @param B A Matrix with as many rows as A and any number of columns.
* @return X that minimizes the two norm of Q*R*X-B.
* @exception IllegalArgumentException Matrix row dimensions must agree.
* @exception RuntimeException Matrix is rank deficient.
*/
public double[][] solve (double[][] B) {
if (B.length != m) {
throw new IllegalArgumentException("Matrix row dimensions must agree.");
}
if (!this.isFullRank()) {
throw new RuntimeException("Matrix is rank deficient.");
}
// Copy right hand side
int nx = B[0].length;
double[][] X = B.clone();
// Compute Y = transpose(Q)*B
for (int k = 0; k < n; k++) {
for (int j = 0; j < nx; j++) {
double s = 0.0;
for (int i = k; i < m; i++) {
s += QR[i][k]*X[i][j];
}
s = -s/QR[k][k];
for (int i = k; i < m; i++) {
X[i][j] += s*QR[i][k];
}
}
}
// Solve R*X = Y;
for (int k = n-1; k >= 0; k--) {
for (int j = 0; j < nx; j++) {
X[k][j] /= Rdiag[k];
}
for (int i = 0; i < k; i++) {
for (int j = 0; j < nx; j++) {
X[i][j] -= X[k][j]*QR[i][k];
}
}
}
double[][] mat = new double[n][nx];
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat[0].length; j++) {
mat[i][j] = X[i][j];
}
}
return mat;
}
}
Ads help maintain this website.