solutions to under- and over-determined systems

Posted on 2007-09-19 12:53 By Shawn Bauldry (2)

Categories:

I have a project where I'm trying to establish the identification of systems of equations (usually 10 or so equations). The systems can be under- exactly- or over-determined. If over-determined, I would like to know what constraints would need to be made to identify the system. For example, with the system:

x + y = a
x - y = b
2x + 2y = c

Is there a way to have Maple return that c = 2a?

Also, in some cases when the system is under-determined I get parametric solutions but in other cases I get {} (which is the same result returned for over-determined equations). Does anyone know why Maple will provide solutions for some under-determined systems and not others (i.e., where I might look to diagnose this problem with my systems)?

solution for linear systems

Comment on 2007-09-19 14:33 from Doug Meade ( Maple Rating 4

1132)

Shawn,

If, as in your example, the equations are linear then you can use the theory of linear algebra to get an answer to your question. Here's one way that this could be done:

with( LinearAlgebra ):
EQS := {
  x   + y   = a,
  x   - y   = b,
  2*x + 2*y = c
};
A,b := GenerateMatrix( EQS, [x,y] );
M := < A | b >;
GaussianElimination( M );

Now, if each row has a pivot entry, then the system is consistent for every right-hand side. If there is a row that does not have a pivot entry, then the RHS must be zero for the system to be consistent. Setting these elements of the RHS to zero gives the constraints that must be satisfied in order for the system to be consistent.

Depending on the specific form of your equations, you can get fancier.

Does this help you to answer your question?

Doug

---------------------------------------------------------------------
Douglas B. Meade
Math, USC, Columbia, SC 29208  E-mail: mailto:meade@math.sc.edu       
Phone:  (803) 777-6183         URL:    http://www.math.sc.edu/~meade/

solution for linear systems

Comment on 2007-09-19 18:19 from gkokovidis ( Maple Rating 4

888)

Greetings Doug. Using your code as posted, since you are declaring b as a variable in the original equation, you cannot use it again in your assignment to GenerateMatrix. Maple complains as follows:

Error, recursive assignment

Changing the lower case b to something else (I used upper case), gives the proper result.

>restart:
>with( LinearAlgebra ):
>EQS := {
x + y = a,
x - y = b,
2*x + 2*y = c
};
>A,B := GenerateMatrix( EQS, [x,y] );
>M := < A | B >;
>GaussianElimination( M );

Regards,
Georgios Kokovidis
Dräger Medical

solutions to under- and over-determined systems

Comment on 2007-09-19 19:04 from Robert Israel ( Maple Rating 4

2610)

In solving a system such as this, you want to be careful about what is considered to be a variable and what is a parameter. Maple will give you solutions expressing a set of basic variables in terms of the other variables and the parameters; these will be valid for "generic" values of the parameters, but perhaps not for special values of the parameters. Thus:

> sys := {x + y = a,
     x - y = b,
    2*x + 2*y = c}:
> solve(sys, {x,y});

This is treating x and y as the variables and a,b,c as parameters.
It returns nothing since for generic values of parameters a, b and c, there are no solutions. But

> solve(sys, {x,y,c});

Now x,y and c are considered as variables, so you pick up the solutions that depend on c having a specific relation to a and b:

{c = 2*a, y = 1/2*a-1/2*b, x = 1/2*a+1/2*b}

You might also try Groebner[Solve]:

> Groebner[Solve](map(rhs-lhs,sys),[x,y,a,b,c]);

Note that in the second argument, I list the variables first and then the parameters.

<br />
{[[2*a-c, 4*y-c+2*b, -c-2*b+4*x], plex(x,y,a,b,c), {}]}

The first item in the returned list indicates that in order to have a solution, you need 2*a-c=0 .

Here's a system where the parameters enter the coefficients of x and y as well as the right sides:

> sys2:= { a*x + y = b, b*x + y = c, x - y = a }:
> G:= Groebner[Solve](map(rhs-lhs,sys2),[x,y,a,b,c]);

$={[[-b*a+c+a^2-b+a*c-b^2, b*a+b*y-c+y, y+y*a+b*a-c-a*c+b^2, -a+x-y], plex(x,y,a,b,c), {}]}$

Again, the first item in the list shows a condition on a,b,c that is needed in order to have a solution.

Thanks everyone for your

Comment on 2007-09-20 19:01 from Shawn Bauldry (2)

Thanks everyone for your responses.

My systems, unfortunately, are not linear and I'm not certain ahead of time which of the parameters (a,b,c in the example I gave), if any, may require a constraint. With this in mind, it looks like the Groebner approach is most promising.

Thanks,
Shawn

solutions to under- and over-determined systems

solution for linear systems

solution for linear systems

solutions to under- and over-determined systems

Thanks everyone for your

Comment viewing options