How to solve a system of equations in the matlab?

Conservation of cars at the four intersections A, B, C and D imply,

x2 + 520 = x3 + 480
x1 + 450 = x2 + 610
x4 + 640 = x1 + 310
x3 + 390 = x4 + 600

respectively. The augmented matrix for this system is

0 1 −1 0|-40
1 −1 0 0|160
−1 0 0 1|-330
0 0 1 −1| 210

[John BG]

A\b does not work when det(A)=0 but lsqr is more robust. Star Strider has a correct answer but on this one d'Erico deserves the home run.

A is not sparse, a matrix is sparse when most of the components are 0.

Regards

John BG

<mailto:[e-mail] [e-mail]>

Answer 1

[John BG]

when det(A)=0, cond(A) is >>1

A=[0 1 -1 0;1 -1 0 0;-1 0 0 1;0 0 1 -1];b=[-40;160;-330;210]
det(A)

then instead of A\b or linsolve(A,b) try different values of tol and maxit in the following matrix preconditioning functions until A*x-b is small enough for x to be considered a solution to the problem.

To do so, try the following:

format long
tol=0.01;maxit=20
[x,flag,relres,iter]=bicgstab(A,B,tol,maxit)
152.50
         -7.50
         32.50
       -177.50
flag =
             0
relres =
          0.00
iter =
          2.50

or

[x,flag,relres,iter]=bicgstab(A,b,tol,maxit)
x =
   1.0e+02 *
   1.525000000000000
  -0.075000000000000
   0.325000000000000
  -1.775000000000000
flag =
     0
relres =
     1.673835638739069e-17
iter =
   2.500000000000000
or

[x2,flag2,relres2,iter2]=lsqr(A,b,tol,maxit)
x2 =
   1.0e+02 *
   1.525000000000000
  -0.075000000000000
   0.325000000000000
  -1.775000000000000
flag2 =
     0
relres2 =
     8.861080375867882e-17
iter2 =
     2

or

[x3,flag3,relres3,iter3]=bicg(A,b,tol,maxit)
x3 =
   1.0e+02 *
   1.525000000000000
  -0.075000000000000
   0.325000000000000
  -1.775000000000000
flag3 =
     0
relres3 =
     6.695342554956277e-17
iter3 =
     3

or

lsqnonneg(A,b)
=
 1.0e+02 *
   3.299999999999999
   1.700000000000000
   2.100000000000001

check

A*lsqnonneg(A,b)-b
 =
   1.0e-13 *
  -0.568434188608080
  -0.568434188608080
   0.568434188608080
   0.568434188608080

Mathworks Recommended reading on Matrix Preconditioning:

http://uk.mathworks.com/support/books/book48648.html?s_tid=srchtitle

retail price new > £100.- but there are used ones around for half price.

Regards

John BG

<mailto:[e-mail] [e-mail]>

Answer 2

[Star Strider]

You have a sparse matrix, so you need to use sparse matrix functions. One is lsqr:

y = [-40; 160; -330; 210];

m = [0 1 -1 0
      1 -1 0 0
      -1 0 0 1
      0 0 1 -1];

xv = lsqr(m,y)

xv =

          152.5
           -7.5
           32.5
         -177.5

The ‘xv’ variable are ‘x1’ ... ‘x4’.

[John D'Errico]

This matrix is NOT sparse. Sparse is rarely a good desription to be applied to any system that is not at least 99% composed of zeros. Half non-zero is NOT sparse. In fact, defining that matrix as a sparse matrix will take more space, and probably more time to solve the resulting linear system.

As far as the use of lsqr, yes, it can be used here. lsqr is NOT a sparse matrix function, as much as it is an iterative solver, that CAN be applied to sparse problems.

lsqr does generate the same solution as would pinv here, so it does survive the rank deficient case.

Answer 3

[Azzi Abdelmalek]

for the system A*x=b use

x=A\b

[Fahad Husain]

How to write the program in matlab

Answer 4

[John D'Errico]

A = [0  1 -1  0
     1 -1  0  0
    -1  0  0  1
     0  0  1  -1];

b = [-40;160;-330;210];

A is NOT a full rank matrix. This means it cannot be used to solve the problem using backslash. If you try to do so, you will fail:

A\b
Warning: Matrix is singular to working precision. 
ans =
   NaN
   NaN
   NaN
   NaN

The rank function told us that. A 4x4 matrix must have rank 4 for the solve to work.

rank(A)
ans =
     3

Next, verify that the right hand side vector can be represented as a linear combination of the columns of A. If this next test returned 4 instead of 3, then it would say there was no solution to the problem at all.

rank([A,b])
ans =
     3

So a solution exists, and there are infinitely many solutions.

I tend to use pinv for the solution of these singular problems.

x = pinv(A)*b
x =
      152.5
       -7.5
       32.5
     -177.5

You can also use lsqr, as Star Strider points out.

This problem is singular. So there are infinitely many solutions that are equally good. The point is, the equations only say that cars obey a conservation requirement. You cannot have more cars coming out than went in. (Ok, I suppose if there was an accident, the reverse could be true. Do you count those taken away by tow truck?)

Essentially, that conservation argument says that we can add ANY constant to all of the x variables, and still have an equally valid solution. This is verified by mathematics.

null(A)
ans =
       -0.5
       -0.5
       -0.5
       -0.5

The null vector above tells us the same thing. So, we could add 177.5 to all of the x variables, since negative numbers of cars seem to make little sense.

Finally, we could just use a solver that will return a result, constrained to be nonnegative.

lsqnonneg(A,b)
ans =
        330
        170
        210
          0