Ask Your Question

Linear equations with errors

asked 2014-09-16 11:04:30 -0500

oren gravatar image

updated 2015-01-14 03:32:37 -0500

FrédéricC gravatar image

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 flag offensive 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) ?

tmonteil gravatar imagetmonteil ( 2014-09-16 15:05:33 -0500 )edit

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

slelievre gravatar imageslelievre ( 2014-09-17 12:33:33 -0500 )edit

@tmontiel: The numbers are real numeric.

oren gravatar imageoren ( 2014-09-18 12:45:25 -0500 )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.

oren gravatar imageoren ( 2014-09-18 12:48:41 -0500 )edit

1 answer

Sort by » oldest newest most voted

answered 2014-09-17 04:14:08 -0500

how about the following:

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...

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower


Asked: 2014-09-16 11:04:30 -0500

Seen: 65 times

Last updated: Sep 17 '14