commons-issues mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Luc Maisonobe (JIRA)" <j...@apache.org>
Subject [jira] [Resolved] (MATH-1101) QR and Rank-revealing QR fail to find a least-squares solution
Date Sun, 23 Feb 2014 11:17:21 GMT

     [ https://issues.apache.org/jira/browse/MATH-1101?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]

Luc Maisonobe resolved MATH-1101.
---------------------------------

       Resolution: Fixed
    Fix Version/s: 3.3

Documentation has been improved as of r1570994, both in the javadoc and in the user guide.

Concerning the default threshold to 0, the decision to keep this value was taken when discussing
issue MATH-664.

Our implementation of QR decomposition does not try to circumvent singular matrices by itself.
I am not sure about this feature as it may fool the user into thinking everything is OK when
in fact the matrix was singular and an approximate solution was found when the user expected
an exact one.

> QR and Rank-revealing QR fail to find a least-squares solution
> --------------------------------------------------------------
>
>                 Key: MATH-1101
>                 URL: https://issues.apache.org/jira/browse/MATH-1101
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 3.2
>            Reporter: Roman Werpachowski
>              Labels: solver
>             Fix For: 3.3
>
>         Attachments: math-1101-bug.java
>
>
> QR and RRQR (rank-revealing) algorithms fail to find a least-squares solution in some
cases.
> The following code:
> final RealMatrix A = new BlockRealMatrix(3, 3);
>         A.setEntry(0, 0, 1);
>         A.setEntry(0, 1, 6);
>         A.setEntry(0, 2, 4);
>         A.setEntry(1, 0, 2);
>         A.setEntry(1, 1, 4);
>         A.setEntry(1, 2, -1);
>         A.setEntry(2, 0, -1);
>         A.setEntry(2, 1, 2);
>         A.setEntry(2, 2, 5);
>         final RealVector b = new ArrayRealVector(new double[]{5, 6, 1});
>         final QRDecomposition qrDecomposition = new QRDecomposition(A);
>         final RRQRDecomposition rrqrDecomposition = new RRQRDecomposition(A);
>         final SingularValueDecomposition svd = new SingularValueDecomposition(A);
>         final RealVector xQR = qrDecomposition.getSolver().solve(b);
>         System.out.printf("QR solution: %s\n", xQR.toString());
>         final RealVector xRRQR = rrqrDecomposition.getSolver().solve(b);
>         System.out.printf("RRSQ solution: %s\n", xRRQR.toString());
>         final RealVector xSVD = svd.getSolver().solve(b);
>         System.out.printf("SVD solution: %s\n", xSVD.toString());
> produces
> QR solution: {-3,575,212,378,628,897; 1,462,586,882,166,368; -1,300,077,228,592,326.5}
> RRSQ solution: {5,200,308,914,369,308; -2,127,399,101,332,898; 1,891,021,423,407,021}
> SVD solution: {0.5050344462; 1.0206677266; -0.2405935347}
> Showing that QR and RRQR algorithms fail to find the least-squares solution. This can
also be verified by calculating the dot product between columns of A and A*x - b:
> // x = xQR, xRRQR or xSVD
> final RealVector r = A.operate(x).subtract(b);
>         for (int i = 0; i < x.getDimension(); ++i) {
>             final RealVector columnVector = A.getColumnVector(i);
>             assertEquals(name, 0.0, r.dotProduct(columnVector), tolerance);
>         }
> Only SVD method passes this test with decent tolerance (1E-14 or so).



--
This message was sent by Atlassian JIRA
(v6.1.5#6160)

Mime
View raw message