# Linear equations with errors

I have a system of $n^2$ homogeneous linear equations in $n^2$ variables. Each equation is sparse and only involves $2n$ variables.

I create a list of equations and use solve(). I only get the "all-zero" solution. This is because of inaccuracies in the equations. I know (from theory) that there is be a nonzero kernel.

So, I'd like to find an approximate solution. That is - a solution of norm 1, which "almost fulfills" the equations. Behind the scenes I probably need the SVD decomposition of the matrix describing the equations (or at least, the input vectors corresponding to the small singular values).

1. Do I have to create a matrix to represent the equations, or can I use my equations directly?
2. Can it be a sparse matrix?
3. Do I have to use an SVD routine, or is there some convenient way to solve my problem directly?
4. Do you have an example of how to do it?
edit retag close merge delete

Indeed, generic matrices are invertible. Before going further, when you speak about the theory, what sort of real numbers are your entries (the coefficients of your equation) ? Integer, rational, algebraic, real symbolic (like pi+sqrt(2), real numeric (like 0.123) ?

( 2014-09-16 22:05:33 +0200 )edit

Could you provide your equations or the code you use to create them?

( 2014-09-17 19:33:33 +0200 )edit

@tmontiel: The numbers are real numeric.

( 2014-09-18 19:45:25 +0200 )edit

Update: I created a matrix $M$ with rows representing the equations, used M.SVD(), and took the vectors corresponding to the very small singular values. It worked.

( 2014-09-18 19:48:41 +0200 )edit

Sort by » oldest newest most voted

sage: m=matrix(RDF,[[1,1],[2,2]],sparse=True)
sage: m
[1.0 1.0]
[2.0 2.0]
sage: m.kernel()
Vector space of degree 2 and dimension 1 over Real Double Field
Basis matrix:
[ 1.0 -0.5]


Of course this will only work if your close to 0 eigenvalues are close enough to 0...

more