Gaussian Elimination

Date: 01/11/2000 at 06:47:18
From: Michael Harper
Subject: Gaussian Elimination

I am attempting to do Gaussian elimination and I am completely stuck.

Date: 01/11/2000 at 13:55:03
From: Doctor Rob
Subject: Re: Gaussian Elimination

Thanks for writing to Ask Dr. Math, Michael.

You are given a system of n or more simultaneous linear equations 
involving n unknowns. Pick one of the unknowns, called the pivot 
variable. Find an equation in which it appears, called the pivot 
equation. Use that equation to eliminate the pivot variable from all 
other equations in the following way. 

If an equation doesn't contain the pivot variable, leave it alone. 

If an equation does contain the pivot variable, subtract the right 
multiple of the pivot equation from that equation to make the pivot 
variable's coefficient zero. 

When you have eliminated the pivot variable from all the rest of the 
equations, set aside the pivot equation, and you will have a system of 
one fewer simultaneous linear equations involving n-1 unknowns. 

Repeat this process, driving down the number of unknowns appearing 
until it reaches 0. Any remaining equations must look like c = c for 
some constant c, and can be discarded (if not, the original system had 
no solution). 

Now look at the equations that you set aside and used as pivot 
equations. The last equation will allow you to solve for the pivot 
variable. Substitute that into all the remaining equations, set it 
aside, and repeat. When you are done with this process, you'll have 
each pivot variable solved for, and you are done.

Example:

     -4*w + 3*x - 4*y -   z = -37
     -2*w       - 5*y + 3*z = -20
       -w -   x - 3*y - 4*z = -27
     -3*w + 2*x + 4*y -   z =   7

Let w be the first pivot variable, and the first equation the first 
pivot equation. w appears in the second equation, so we subtract 
(-2)/(-4) = 1/2 times the first equation from the second, getting

     -2*w           - 5*y +     3*z = -20,
     -2*w + (3/2)*x - 2*y - (1/2)*z = -37/2
     --------------------------------------
           -(3/2)*x - 3*y + (7/2)*z = -3/2

w appears in the third equation so we subtract (-1)/(-4) times the 
first equation from the third. w appears in the fourth equation, so we 
subtract (-3)/(-4) times the first equation from the fourth. This 
leaves

     -4*w +    3*x - 4*y -        z = -37
          -(3/2)*x - 3*y +  (7/2)*z = -3/2
          -(7/4)*x - 2*y - (15/4)*z = -71/4
          -(1/4)*x + 7*y -  (1/4)*z = 139/4

Now the last three equations are a system of three equations in three 
unknowns, and we treat that similarly. Let x be the next pivot 
variable, and the second equation the pivot equation. Since x appears 
in the third equation, we subtract (-7/4)/(-3/2) = 7/6 times the 
second equation from the third. Since x appears in the fourth equation 
we subtract (-1/4)/(-3/2) = 1/6 times the second equation from the 
fourth. This leaves

     -4*w +    3*x -      4*y -        z = -37
          -(3/2)*x -      3*y +  (7/2)*z = -3/2
                      (3/2)*y - (47/6)*z = -16
                     (15/2)*y -     16*z = 35

Now the last two equations are a system of two equations in two 
unknowns, and we treat that similarly. Let y be the next pivot 
variable, and the third equation the next pivot equation. Since y 
appears in the fourth equation, we subtract (15/2)/(3/2) = 5 times the 
third equation from the fourth. This leaves

     -4*w +    3*x -     4*y -         z = -37
          -(3/2)*x -     3*y +   (7/2)*z = -3/2
                     (3/2)*y -  (47/6)*z = -16
                               (115/3)*z = 115

This completes the first phase.

Now we start with the last equation, and solve for z. This gives 
z = 3, and we substitute that into the preceding equations:

     -4*w +    3*x -     4*y = -34
          -(3/2)*x -     3*y = -12
                     (3/2)*y = 15/2

The last remaining equation tells us that y = 5, and we substitute 
that into the preceding equations:

     -4*w +    3*x = -14
          -(3/2)*x = 3

The last remaining equation tells us that x = -2, and we substitute 
that into the preceding equation:

     -4*w = -8

That gives us the value w = 2, and so the solution is

     (w,x,y,z) = (2,-2,5,3)

Understood?

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/