How can i solve this linear system ?
8 views (last 30 days)
Show older comments
Hello,
I have a linear system of equation composed of 14 equations and 49 unknowns. I know that my system can be writed in the Ax=b form and then performing the division A\b to find the unknown vector x. I'm new to Matlab so sorry if I'm asking trivial questions.
My questions are the following:
1) My system should have multiple solutions since it is underdetermined. A\b only gives 1 solution. Is there any way to get more than 1 solution ?
2) I already know that all my 49 unknown are within the range [0;1]. How can I set this constrains to all my unkown ?
3) I may have some unknown that I already know before solving the system. Is it possible to restrict some value of the x vector without having to rewrite the whole system like it is said in the following thread: http://www.mathworks.fr/matlabcentral/answers/17795-basic-matrix-equation-ax-b-with-restrictions
4) Is it possible to import a matrix from a text file, because my A matrix is quite big ?
Regards, Debzz
0 Comments
Accepted Answer
John D'Errico
on 24 Jul 2014
Edited: John D'Errico
on 25 Jul 2014
Your problem is such that there are infinitely many solutions. backslash will return ONE solution, but you want more. How many more? 2? 37? 454233531211 of them?
The general solution can be written in the form
X = X0 + null(A)*k
where k is any general vector, here of size [49-14,1], and X0 is given by
X0 = A\b
If you further require the solution to fall in the 49-dimensional unit box [0,1]^49, it is entirely possible that no solution exists at all. BUT, lsqlin can solve for A solution if any exists. Then you use the same trick that I showed above to find a new solution.
If you don't have the optimization toolbox, so no lsqlin, then you can use lsqnonneg, employing slack variables to transform the problem into one that it can solve. This will require some minor coding of course.
If some of the parameters are already known, then you could simply eliminate them from the problem. Subtract those terms from the right hand side of the linear system. Or, again, if you have lsqlin, then simply set up equality constraints. (This is a far better solution than setting the lower and upper bounds to the same value, which will probably introduce numerical problem.)
And as far as reading in a text matrix, of course MATLAB can read in a file. 14x49 is not even remotely what anyone would call big though.
0 Comments
More Answers (2)
debzz
on 27 Jul 2014
2 Comments
John D'Errico
on 27 Jul 2014
By the way, you don't need to add answers. Use comments instead. An answer should be exactly that, an answer.
John D'Errico
on 27 Jul 2014
I looked at your problem as posed here. First, the fact that C and d do not conform properly for linear algebra, in the sense that d should be 14x1, not 1x14. So...
d = d.';
Next, your problem is probably poorly scaled. Large disparities in the magnitude of those matrix elements will potentially cause numerical problems with many optimization schemes. So...
r = max(abs(C),[],2);
Chat = bsxfun(@times,C,1./r);
dhat = d'./r;
This may have helped a bit. See that Chat is a bit better behaved than was C. But as importantly, see that C was singular! It has a zero singular value there, so the rank of your matrix was only 13, not 14. RANK would have told us the same thing, but SVD tells us a bit more. Note that a singular matrix tells us that an exact solution need not exist.
[svd(C),svd(Chat)]
ans =
12386 2.9235
12386 2.6458
12386 2.6458
12386 2.6458
12386 2.6458
12386 2.6458
12386 2.6458
2.6458 1.2438
2.6458 1.2438
2.6458 1.2438
2.6458 1.2438
2.6458 1.2438
2.6458 1.2438
1.4763e-13 2.7105e-16
Does any exact solution exist? If we augment Chat with dhat, then test the rank, if that rank were to change, then in fact there is no exact solution, even disregarding the bound constraints.
svd([Chat,dhat])
ans =
4.0219
2.7745
2.6458
2.6458
2.6458
2.6458
2.6458
1.415
1.2438
1.2438
1.2438
1.2438
1.2438
2.093e-07
Ah, so the augmented matrix is no longer rank deficient. So no exact solution exists.
Next, before I ever try lsqlin, use backslash. What does it do? (Besides tell us that C was singular, which we already knew.)
Chat\dhat
Warning: Rank deficient, rank = 13, tol = 1.538691e-14.
ans =
1.1663
0.04008
0.34907
-0.010648
0.11446
-0.67447
0.015243
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
0
0
0
0
0
1
0
BACKSLASH gave a valid answer, although one that fails your constraints.
Remember, that since we already knew there was no exact solution, we cannot expect perfection. Try lsqlin now. I'll be lazy with the options, using the defaults.
xhat = lsqlin(Chat,dhat,[],[],[],[],lb,ub)
Warning: The trust-region-reflective algorithm requires at least as many equations as variables
in C matrix; using active-set algorithm instead.
> In lsqlin at 301
Maximum number of iterations exceeded; increase options.MaxIter.
To continue solving the problem with the current solution as the
starting point, set x0 = x before calling lsqlin.
xhat =
0.12429
0
0.40281
-2.1684e-19
0.19805
0.092399
0.098842
1
-5.0388e-17
0
0
0
-5.1065e-12
-1.548e-16
0.95955
0
0
-1.1297e-16
0
0
0
1
-3.4694e-18
0
1
-1.7347e-18
0
0
0
1
0
0
0
1.1102e-16
0
0
1.7347e-18
1
0
0
0
0
0
0
1
0
0
0
0
Again, it found a solution that satisfies the bounds. But NO exact solution exists, so I doubt that we can do much better here. Allowing it to use an infinite number of iterations will not help. My guess is the singularity of your system is causing LSQLIN to keep looking.
debzz
on 27 Jul 2014
Edited: debzz
on 27 Jul 2014
5 Comments
John D'Errico
on 27 Jul 2014
You have many dimensions to play with. A minor problem is that this gives you little control over which solution is chosen, but unless you know the answer, or you have more information than you supply to the system, then LSQLIN will be pretty arbitrary about what it gives.
Since I don't know what is good or bad here about the solution, I can't offer advice. However an alternative option you might try is to use either LSQLIN or QUADPROG to find that solution which is closest to 0.5*ones(49,1), whiie still satisfying the linear system and the bound constraints.
See Also
Categories
Find more on Linear Least Squares in Help Center and File Exchange
Products
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!