Geek Answers Handbook

Removing unsolvable equations from an underdetermined system

My program is trying to solve a system of linear equations. To do this, he collects the matrix coeff_matrix and vector value_vector and uses Eigen to solve them, for example:

 Eigen::VectorXd sol_vector = coeff_matrix .colPivHouseholderQr().solve(value_vector);

The problem is that the system can be either overdetermined or underestimated. In the first case, Eigen either gives the right or the wrong solution, and I check the solution with coeff_matrix * sol_vector - value_vector .

However, consider the following system of equations:

 a + b - c = 0 c - d = 0 c = 11 - c + d = 0

In this particular case, Eigen correctly solves the last three equations and also gives solutions for a and b .

What I would like to achieve is that only equations that have only one solution will be solved, and the rest (the first equation here) will be stored in the system.

In other words, I am looking for a method to find out which equations can be solved in a given system of equations at that time, and which cannot, because there will be more than one solution.

Could you suggest a good way to achieve this?

Edit: note that in most cases the matrix will not be square. I added another line here to note that redefinition can also occur.

+4
source share
3 answers

I think you want a singular value decomposition (SVD) that will give you what you want. After SVD, “equations that have only one solution will be solved,” and the solution is pseudo-reversible. It will also give you empty space (where infinite solutions come from) and leave zero space (where the inconsistency comes from, i.e. there is no solution).

+6
source

Based on the SVD comment, I was able to do something like this:

 Eigen::FullPivLU<Eigen::MatrixXd> lu = coeff_matrix.fullPivLu(); Eigen::VectorXd sol_vector = lu.solve(value_vector); Eigen::VectorXd null_vector = lu.kernel().rowwise().sum();

AFAICS, null_vector strings corresponding to unified solutions, 0 , and those that correspond to undefined solutions, 1 s. I can reproduce this with all my default examples, which Eigen has.

However, I'm not sure if I am doing something right or just noticed a random pattern.

+2
source

You need to calculate the determinant of your system. If the determinant is 0, then you have an infinite number of solutions. If the determinant is very small, a solution exists, but I do not trust the solution found by the computer (this will lead to numerical instabilities).

Here is a link to what the determinant is and how to calculate it: http://en.wikipedia.org/wiki/Determinant

Note that a Gaussian exception should also work: http://en.wikipedia.org/wiki/Gaussian_elimination With this method you will get strings from 0s if there are an infinite number of solutions.

Edit

If the matrix is ​​not square, first you need to extract the square matrix. There are two cases:

  • You have more variables than equations: then you either have no solution, or an infinite number of them.
  • You have more equations than variables: in this case, find the square submatrix of the nonempty determinant. Solve this matrix and check the solution. If the solution does not fit, then you have no solution. If the solution is suitable, this means that the additional equations are linearly dependent on the extracts.

In both cases, before checking the size of the matrix, delete rows and columns with only 0s.

As for the Gaussian exception, it should work directly with non-quadratic matrices. However, this time you should check that the number of nonempty rows (i.e. Rows with some values ​​other than 0) is equal to the number of variables. If it is less, you have an infinite number of solutions, and if it is more, you have no solutions.

+1
source

More articles:


All Articles