MATLAB: Solving large overdetermined system of equations

overdetermined system

I am trying to solve an overdetermenind system of equations (45 equations with 18 unknowns) in the form of A*X = B; where: A = [8.19 0.3; 12.39 0.86; 16.15 1.68; 17.7 2.16; 24.6 8.33]; A is 5 rows, 2 columns

B = [0.85 3.8 0.225 0.175 0.05 0.05 0 1.919 0.165; 1.5 6.825 0.45 0.4 0.175 0.125 0.025 2.907 0.315; 3 7.625 0.9 1.05 0.475 0.225 0.1 3.823 0.544; 3.05 7.9 1.1 1.8 1.225 0.25 0.45 4.153 0.881; 5.1 12.95 1.975 3.65 3.075 0.25 1.075 4.045 1.217]; B is 5 rows, 9 columns

X = [a1 b1 c1 d1 e1 f1 g1 h1 i1;a2 b2 c2 d2 e2 f2 g2 h2 i2]; X is 2 rows, 9 columns

I need to solve X with the following constraints: sum (a1 to i1) = 1 & sum (a2 to i2) = 1 & all elements in X shall be higher than or equal to zero (non negative).

Best Answer

I almost always need to laugh out loud, when someone says they have a "large" system. That is not even close to large, by factors of thousands at least in the number of variables. If you said a million unknowns, yep, that is large. :)

But you seem confused even at that. First, you say 45x18. Then you say 5x2. Neither is large.

Actually, what you seem to have is a 5x2 system of equations, with 9 distinct right hand sides. So you have 9separate problems, each of which shares the same matrix A, so the same left hand side. You don't have 45 equations. Just 5 equations, solved 9 times, all essentially in one call.

And, wanting to do this?

X = [a1 b1 c1 d1 e1 f1 g1 h1 i1;a2 b2 c2 d2 e2 f2 g2 h2 i2]; X is 2 rows, 9 columns

A godawful bad idea.

Anyway, the way to solve ANY linear system of equations of the form A*X=B, large or small, is

X = A\B;

Note that this solves your problem, all 9 right hand sides at once. The result will be a 2x9 array.

Related Solutions

MATLAB: Using the linprog function for two constraints

If you are in the stage of optimization, you don't know the 154.8 in the equation 60.44x+13.8y+8.4z = 154.8, but only the power consumption of each bulb. So you will have to remove the equality constraint from your problem formulation.

One more thing is that your solution variables must be integers - so you will have to use "intlinprog" instead of "linprog".

Best wishes

Torsten.

MATLAB: Solution is not matching with actual equation

That the solution is not exact is not even remotely surprising, for several reasons. First, an over-determined system will generally not have an exact solution. The best you can do is to minimize the residuals of all of the errors in combination. This is what is done. Don't believe me? Try a simple example.

A = [1 1;1 2;3 1]
A =
   1     1
   1     2
   3     1
b = [-8;7;6];

Surely, how easy can this 2 variable system be to solve? I can hardly imagine something easier that that. And even if the answer is not exact, it will surely be close, no?

x = A\b
x =
          1
          1
[A*x,b]
ans =
          2           -8
          3            7
          4            6

Hmm. So when we multiply A*x, we are pretty far off indeed. But then, I did say this is not even remotely a surprise. In fact, it is easily shown that any other choice for a solution vector x will yield residuals with a larger norm.

norm(A*x - b)
ans =
       10.954
norm(A*(x + randn(2,1)) - b)
ans =
       11.235
norm(A*(x + randn(2,1)) - b)
ans =
       11.021

Now, this silly example is not a proof. Merely a counter-example to the idea that it is trivial to create a system of over-determined equations where the solution still has significantly large residual errors. In the case of a 12x5 system, so 12 equations, 5 unknowns, that is just as trivial.

Ok, now as far as the spreadsheet that you show, again, you seem to be a bit clueless. (Sorry, but true.)

    A
    A =
                        770.55                    776.45                    765.05                       771                     772.3
                        636.05                       641                     630.8                       634                    636.95
                       1404.95                    1409.3                      1382                    1397.3                      1401
                        894.65                     897.4                     886.8                    889.35                    894.65
                       1421.96                      1438                      1418                    1429.9                    1433.4
    >> b
    b =
                           784                     766.5                     773.5
                           639                     631.2                    633.65
                          1401                      1371                   1375.25
                        907.25                     881.1                     896.9
                        1441.4                   1416.95                    1420.7

So, first, you show a 5x5 matrix, NOT a 12x5 matrix. A is not even close to singular, so a solution will exist that will be reasonably accurate.

x = A\b
x =
          1.34306951538017        -0.735590758162936         0.825063315954427
         -2.83318049316987          1.94002770486605         -1.22605398297668
          4.17833546820366           2.5252718327165          5.24318794991482
          3.10947548609037         0.720519361180246          1.63716711244305
         -4.71982438285554         -3.44491091004859         -5.41737628875096

Be careful. Do NOT copy only a 5 digit approximation to that solution. I would guess that is what you did. It is also perhaps the most common novice mistake that people make.

A*x - b
ans =
                         0                         0      9.09494701772928e-13
      4.54747350886464e-13      6.82121026329696e-13      1.02318153949454e-12
                         0                         0                         0
                         0     -1.13686837721616e-13       5.6843418860808e-13
     -4.54747350886464e-13     -2.27373675443232e-13      6.82121026329696e-13

So the residuals here are tiny, as I predicted. Had you copied rounded 5 digit approximations to x into a spreadsheet,

xhat = round(x,5)
xhat =
                   1.34307                  -0.73559                   0.82506
                  -2.83318                   1.94003                  -1.22605
                   4.17834                   2.52527                   5.24319
                   3.10948                   0.72052                   1.63717
                  -4.71982                  -3.44491                  -5.41738
A*xhat - b
ans =
        0.0110884999994596       0.00215949999983422       0.00146600000061881
       0.00913649999938571       0.00178199999913886       0.00120399999980236
        0.0200864999997066       0.00393449999955919       0.00262300000213145
        0.0128304999998363       0.00249499999961245       0.00167349999958333
        0.0205611999986104       0.00399759999959315       0.00272860000109176

Still not immense errors, but consistent with my expectations.

Best Answer

Related Solutions

MATLAB: Using the linprog function for two constraints

MATLAB: Solution is not matching with actual equation

Related Question