Method lu of package Matrix works fine for square matrices. However, I can't see why there is that square restriction. How can I perform LU decomposition on a rectangular matrix?
views:
61answers:
2
+2
A:
You can embed it into a identity matrix:
[ a11 a12 a13 ]
[ a21 a22 a23 ]
[ 0 0 1 ]
LU decomposition is for square matrices only. You may want to check Wikipedia for a refreshing.
Alexandre C.
2010-07-15 09:34:03
What about the rest of the system of equations? What do you add to the other side of the equation? This certainly makes your matrix "square", but I don't see the use of it besides allowing the LU decomposition to proceed.
duffymo
2010-07-15 09:57:59
there is no use of it indeed. OP didn't specify what he wanted to do with its LU decomposition. He just wants to perform one.
Alexandre C.
2010-07-15 10:59:08
Now I understand you.... 8)
duffymo
2010-07-15 11:53:02
I checked Wikipedia and I copy from your link: "...these decompositions can all be generalized to rectangular matrices as well". Btw, Your trick works!, but I wish there were a more straight forward way to do it
gd047
2010-07-15 15:19:31
It's not a trick - it's the linear algebra expression of least squares.
duffymo
2010-07-15 18:32:34
+1
A:
Non-square matricies mean different things.
If it has more rows than columns (more equations than unknowns), it means you need a least squares approximation. You can pre-multiply both sides by the transpose of A and use LU decomp on that. The result is the least squares "best" solution.
If it has fewer rows than columns (more unknowns than equations), you need Singular Value Decomposition (SVD). It'll give you the best solution and the null space as well.
duffymo
2010-07-15 09:38:58
Who is A ? Least square for overdetermined sets of equations is best performed with QR decomposition (stabler).
Alexandre C.
2010-07-15 09:41:34
Assuming the usual form of solving Ax = b, where A is the matrix of coefficients, x is the unknown vector, and b is the known vector. Gil Strang recommends the procedure I cited. I think he's enough of an authority on linear algebra for me.
duffymo
2010-07-15 09:56:07
personal experience shows me QR performs better in the case of more equations than unknowns. Slower though.
Alexandre C.
2010-07-15 11:00:11
Define "performs better" if it's not faster. What metric are you looking at?
duffymo
2010-07-15 12:04:01
Now I see - stability. For all cases, or just some pathological situations?
duffymo
2010-07-15 12:05:10
To be precise: When solving full rank overdetermined systems, I have had better success with QR wrt accuracy and stability (much better than LU wrt accuracy, and it seems stabler with borderline numerical rank, even with small <10 matrices). When not full rank, SVD is your best choice. Whether it is fast or not is irrelevant if you get wrong answers.
Alexandre C.
2010-07-15 12:14:16
@duffymo I also thought that the least squares best solution is performed using the projection matrix A(A'A)^(-1)A, or QQ' (after performing QR decomposition). And I have also seen it on G. Strang's "Linear Algebra and its applications". I'll look for your LU way.
gd047
2010-07-15 15:29:37
@gd047: The actual method you use really depends on what problem you solve. If you use LAPACK for instance, four methods are available depending on the sizes and rank of the problem.
Alexandre C.
2010-07-16 08:07:23