Results 1 to 9 of 9

Math Help - Alternatives to gaussian elimination?

  1. #1
    Member
    Joined
    Jan 2011
    Posts
    84

    Alternatives to gaussian elimination?

    Hello, are there any alternative ways to solve system of equations other than gaussian elimination?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chisigma's Avatar
    Joined
    Mar 2009
    From
    near Piacenza (Italy)
    Posts
    2,162
    Thanks
    5

    Re: Alternatives to gaussian elimination?

    An elegant but not very comfortable computationally alternative consists in writing the linear system in matrix form...

    A\ \vec{x}= \vec{b} (1)

    If A^{-1} is the inverse of A, then the solution is...

    \vec{x}= A^{-1}\ \vec{b} (2)

    Kind regards

    \chi \sigma
    Last edited by chisigma; January 4th 2012 at 06:03 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member ILikeSerena's Avatar
    Joined
    Dec 2011
    Posts
    733
    Thanks
    121

    Re: Alternatives to gaussian elimination?

    Quote Originally Posted by Riazy View Post
    Hello, are there any alternative ways to solve system of equations other than gaussian elimination?
    LU decomposition
    Cholesky decomposition
    QR decomposition

    Take your pick.

    In particular, Gaussian elimination is numerically a bad method, since it makes significant rounding errors when solving equations that are close to singular, or when they are singular and you want a solution space.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Alternatives to gaussian elimination?

    one should also include Cramer's method, which shows why (if the determinant of the system is close to 0) such large errors can occur with Gaussian elimination (the "common denominator" of the system solutions is very small, so even a small error in rounding can cause a huge variance in results).

    i want to point out that LU decomposition is, in fact, an extension of Gaussian elimination, and that an LU decomposition may not actually exist. furthermore, the Cholesky decomposition only applies to positive-definite Hermitian systems, which is a rather limited special case. the QR decomposition always exists, but using it to solve a system of linear equations eventually involves finding the inverse of the transpose of a submatrix of the "R" part (which typically involves using...Gaussian elimination).

    the solvability of a system Ax = b is intimately bound up with "how singular" A is, so knowing the rank of A is useful.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    Re: Alternatives to gaussian elimination?

    A method that may be useful is some cases is by using a generalized inverse of the matrix (there are plenty of different generalized inverses, this one is very simple): if you have a matrix X such that AXA = A, and an equation Ax = b, then first check whether Xb is a solution. If it's not, then there aren't any solutions. If it is, then the general solution is x = Xb + (I - XA)y for any y in your space.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176

    Re: Alternatives to gaussian elimination?

    Quote Originally Posted by Riazy View Post
    Hello, are there any alternative ways to solve system of equations other than gaussian elimination?
    Why do you want to know? Is it out of interest, or is there a specific thing you want to do? Some methods are faster than others, while others are less suseptible to rounding errors.

    Gaussian elimintation has order n^3 - it gets slower with the cube of the rank. That is, it slows down exponentially. However, there are algorithms which work faster for matrices with lots of zeros ("sparse" matrices). For instance, a frontal solver.

    You might want to read this bit of Wikipedia.

    (I thought there would be some good reading on how to solve linear equations in Knuths "the Art of Computer Programming" (aka "all the algorithms you'll ever need and more, explained") but I can't seem to find anything. There is a bit in the second volume, but it only mentions it in passing...am I being stupid, or does he really not mention this stuff?!?)
    Last edited by Swlabr; January 5th 2012 at 05:39 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jan 2011
    Posts
    84

    Re: Alternatives to gaussian elimination?

    Let me put it this way, I want a faster method than gaussian elimination, we get a lot of problems with parameter solutions coming in the exams, We dont have much time thats the problem, Gauss takes a lot of time to do calculations with.
    I am familiar with cramers rule for solving, but its only applicable for n x n, which I think our teacher wouldnt put any questions, (very small chance).

    So a method thats faster than gauss, but which can handle parameter solutions too(,s,t), is there something like this?, or is gauss the only thing I have go with?, I thought that perhaps some intelligent professor, had come up with some good algorithm by now
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176

    Re: Alternatives to gaussian elimination?

    Quote Originally Posted by Riazy View Post
    Let me put it this way, I want a faster method than gaussian elimination, we get a lot of problems with parameter solutions coming in the exams, We dont have much time thats the problem, Gauss takes a lot of time to do calculations with.
    I am familiar with cramers rule for solving, but its only applicable for n x n, which I think our teacher wouldnt put any questions, (very small chance).

    So a method thats faster than gauss, but which can handle parameter solutions too(,s,t), is there something like this?, or is gauss the only thing I have go with?, I thought that perhaps some intelligent professor, had come up with some good algorithm by now
    But Gaussian elimination is good, and it is fast for small matrices. You only need to do, approximately, n^3/3 calculations, which for a 3x3 matrix means you only need to do three calculations:

    \left( \begin{array}{ccc}a & b & c \\d & e & f \\g & h & i \end{array} \right)

    \rightarrow\left( \begin{array}{ccc}a & b & c \\0 & e_1 & f_1 \\g & h & i \end{array} \right)

    \rightarrow\left( \begin{array}{ccc}a & b & c \\0 & e_1 & f_1 \\0 & h_2 & i_2 \end{array} \right)

    \rightarrow\left( \begin{array}{ccc}a & b & c \\0 & e_2 & f_2 \\0 & 0 & i_3 \end{array} \right)

    Specifically, ar_2-dr_1 then ar_3-gr_1 and finally e_1r_3-h_2r_2.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Feb 2011
    Posts
    147
    Thanks
    3

    Re: Alternatives to gaussian elimination?

    Not only is it quite fast, but it's also a very simple algorithm. And it's a good thing in an exam.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: September 12th 2011, 09:03 PM
  2. [SOLVED] Gaussian elimination help
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: June 28th 2011, 01:23 PM
  3. Replies: 1
    Last Post: February 16th 2011, 02:06 PM
  4. Gaussian Elimination
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: January 25th 2011, 12:12 PM
  5. Gaussian elimination.
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 12th 2010, 05:06 AM

Search Tags


/mathhelpforum @mathhelpforum