Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Is it worse an over or an under determined system of linear equations?

  1. Sep 8, 2012 #1
    Hello Forum,

    a system of linear equations can be determined (if there are as many unknowns as equations), overdetermined or underdetermined.

    In general, is it easier to solve an overdetermined or an underdetermined system?

    Am I correct in thinking that both have an infinite number of possibile solutions or no solution at all? In the case they have infinite solutions, are the available linear algebra tools more in favor of underdetermined or overdetermined systems?

    Thanks
    fisico30
     
  2. jcsd
  3. Sep 8, 2012 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    An "over determined system" has NO solution: there is NO x such that Ax= b.
    An "under determied system" has an infinite number of solutions: there exist an infinite number of x such that Ax= b.

    For an over determined system, there are Linear Algebra techniques that would get x that "comes close" to satisfying Ax= b. Most notably the "least squares solutions".

    For an under determined system, there exist Linear Algebra techniques to write a formula for all solutions. As to which is "better", that is a value judgement. Judge it any way you want. Personally, I would prefer a whole lot of correct solutions to some that are "pretty close".
     
  4. Sep 9, 2012 #3
    I beg to differ: If b is in the column space of A then there is a solution x, otherwise there is no solution.
     
  5. Sep 11, 2012 #4
    Hello Vaedoris,
    thanks for the reply.

    I am familiar with columns space and row space: they are the spaces (or subspaces) of vectors formed by the linear combination of the column vectors and row vectors.

    In an equation like Ax=y (say a determined system) how do the solutions x relate what we find inside the column space and/or the row space?

    I am not able to get a sense of what the row and column space truly are and how they can be useful in the resolution of Ax=y.

    Also, in the case of an overdetermined system, there is no exact solution (aside from the special case you mentioned). Can we not get rid of those extra, useless equations and make the system determined?

    Thanks
    fisico30
     
  6. Sep 11, 2012 #5
    You could find the reduced row echelon form of the matrix (of an overdetermined system) to determine which rows are dependent. Then, take them out, but you must also erase the corresponding components of the vector b.

    Edit: However, this does not guarantee that the reduced matrix is square as erasing rows creates an under-determined system for the case where matrix rank is less than number of columns. On the bright side though, erasing dependent rows does not change the row space.

    Personally, I would solve for the solution x by finding the left inverse (using some computer program) if the matrix has full column rank.
     
    Last edited: Sep 11, 2012
  7. Sep 11, 2012 #6
    I'm sorry, but I think you are mistaken.

    An over-determined system has more equations than unknowns. This doesn't mean it is inconsistent. Imagine a whole lot of lines (more than 2) that all happen to intersect at a certain point. This is a solution to the over-determined problem.

    An under-determined system has fewer equations than unknowns. It may have no solutions (parallel planes, for instance). Of course, if it has solutions then it has an infinite number. But it is possible that there be no solutions.
     
  8. Sep 11, 2012 #7
    I don't think you are talking about the same thing.

    Besides, your example of intersection of lines is just one case of overdetermined system (where rank = number of columns - if you write the problem in matrix form). What I explained above is the other case:

    For overdetermined system, mathematically, you can construct an ##m\times n## matrix that has more rows than columns (m>n) and yet you can have rank that is less than the number of columns (r<n).

    Clearly for this case, erasing the dependent rows gets you a new matrix that is under-determined because there are only r independent rows but r is less than n (r<n<m).

    Also, the existence of solution depends on whether the vector b (in the equation Ax=b) is in the column space of A as directly implied by the equation itself. So, there are vectors of an overdetermined system that are not in the column space (e.g. all vectors in left nullspace except the zero vector) and therefore for those vectors they have no solutions. Of course, the same applies to under-determined systems.
     
    Last edited: Sep 11, 2012
  9. Sep 11, 2012 #8
    Nevertheless, my example proves false the statement that overdetermined systems have no solutions.
     
  10. Sep 12, 2012 #9
    Well, that's what HallsofIvy claimed (probably just some unintentional mistake).

    Not me.


    P.S.: You could create unlimited number of counter-examples to that claim by just inspecting Ax=b. "Intersection of straight lines" though may not be obvious to some people.
     
  11. Sep 12, 2012 #10

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    That is NOT what I would call an "over determined sytstem". Given that definition, you could take any system of equations, add some equations that are equivalent to those you already have, and declare it "over determined". To me, and "over determined system" must have more equations than unknowns that cannot be reduced.

     
  12. Sep 12, 2012 #11
    Many textbooks define an overdetermined system as simply a system that has more equations than unknowns. I have yet seen one definition that restricts it to being "irreducible" or that it must have full column rank!

    For example: You can have a matrix that has more rows than columns with its rank less than the number of columns but the matrix equation is still an overdetermined system because it has more equations than unknowns.
     
    Last edited: Sep 12, 2012
  13. Sep 13, 2012 #12
    So, how about schaefera example?
    Is multiple lines intersecting at a single point an example of an overdetermined system having a solution?

    Clearly, a consistent system, with as many equations as unknowns, can always be made overdetermined by adding dependent equations (scaled versions of the already existing equations, sums of the existing equations, etc...).

    I guess I would like to understand why a "true" overdetermine system cannot have a solution in many cases. I feel that it is more about having some extra equations that are in contrast with the other ones: the extra equations have different solution from the other ones which have a common solution....

    thanks
    fisico30
     
  14. Sep 13, 2012 #13

    jasonRF

    User Avatar
    Science Advisor
    Gold Member

    I hate to say this, but the answer to such a general question is, "it depends." Perhaps you can give more detail on what the context is?

    Many other folks have posted replies with the emphasis on finding exact solution to a set of exact equations, so I will give another perspective in case you are interested. In many practical applications we are modeling a phenomenon based upon some set of (imperfect) measurements. If our model is linear in a set of unknown parameters, then we end up with a system of linear equations that in general is inconsistent, due to the imperfect measurements.

    The most common approach to dealing with the inconsistent equations is to use least-squares. If we have at least as many independent measurements as we do unknowns (that is, the rank of the matrix is equal to the number of columns) then the least-squares solution is unique. This case is often referred to as the "full-rank" case. If the rank of the matrix is less than the number of columns then there are an infinite number of least-squares solutions. This case is often referred to as the "rank-deficient" case. One then has to pick the solution that you are most interested in: sometimes you may want the least-squares solution with the fewest nonzero elements, other times you may want the least-squares solution that has the smallest norm, other times you may not even care which solution, etc. In all cases, there are good linear algebra tools that can be used. But most would agree that overdetermined is far better than underdetermined for solving least-squares, and more equations yields better estimates.

    jason
     
  15. Sep 13, 2012 #14
    Hi Jason,
    Thanks for the reply. I can live with "it depends".
    Are you familiar with compressive sampling? It sounds like you are.
    IF so, can I shoot some questions?
    thanks
    fisico30
     
  16. Sep 13, 2012 #15

    jasonRF

    User Avatar
    Science Advisor
    Gold Member

    sorry - I don't know anything about compressive sampling. It is one of many things I would eventually like to learn, though!

    jason
     
  17. Sep 17, 2012 #16
    Hello jasonRF,

    another simple question: in the situation Ax=y, the column space and the row space from A can be different. The rows and columns span different sets of vectors....

    How do the column space and the row space relate to each other and how are they helpful in finding the solutions x?
    Can we derive one from the other?

    thanks
    fisico30
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Is it worse an over or an under determined system of linear equations?
Loading...