Gaussian Elimination And Gauss Jordan Method English Language Essay

The following are well-known methods of solving a system of linear equations:

Gaussian Elimination Method

Gauss-Seidel Iterative Method

Gaussian Elimination

The simplest method for solving a linear system is Gaussian elimination, which uses three types of elementary row operations:

Multiplying a row by a non-zero constant (kEij)

Adding a multiple of one row to another ( Eij + kEkj)

Exchanging two rows ( Eij <–> kEkj)

Each row operation corresponds to a step in the solution of the system of equations  where the equations are combined together. It is important to note that none of those operations changes the solution. There are two parts to this method: elimination and back-substitution. The purpose of the process of elimination is to eliminate the matrix entries below the main diagonal, using row operations, to obtain a upper triangular matrix with the augmented column. Then, you will be able to proceed with back-substitution to find the values of the unknowns.

Introduction: Gaussian elimination method is an exact method which solves a given system of equations in n unknowns by transforming the coff. Matrix, into an upper triangular matrix and then solve for the unknowns by back substitution.

Consider a system of n equations in n unknowns

a11x1+a12x2+a13x3+……….+a1nxn = an+1

a21x1+a22x2+a23x3+……….+a2nxn=a2,n+1

……………………………………..

an1x1+an2x2+an3x3+………….annxn=an,n+1

eliminate the unknown x1 from the (n-1) equations namely 2,3,……(n-1),n by substracting the multiply ai1/ai1 of the first equation from the ith equation from the ith equation ,for i=2,3,4……,n.Now eliminate x2 from the (n-2) equations of the resultant system. By this procedure, we arrive at a derived system as follows:

a11x1+a12x2+……..+a1nxn=al,n+1

a22+x2+…………..a2nxn=a2,n+1

a33x3+…………..+a3nxn=a3,n+1

……………………………

ann(n-1)xn =an,n+1(n-1)

Gaussian elimination is a method for solving matrix equation of the form:

(1)

To perform Gaussian elimination starting with the system of equations

(2)

compose the “augmented matrix equation”

(3)

Here, the column vector in the variables is carried along for labeling the matrix rows. Now, perform elementary row operations to put the augmented matrix into the upper triangular form

(4)

Solve the equation of the th row for , then substitute back into the equation of the st row to obtain a solution for , etc., according to the formula

(5)

Performs a version of Gaussian elimination, with the equation being solved by Gaussian elimination

L U decomposition of a matrix is frequently used as part of a Gaussian elimination process for solving a matrix equation.

A matrix that has undergone Gaussian elimination is said to be in echelon form.

Example 1, consider the matrix equation:

(6)

In augmented form, this becomes

(7)

Switching the first and third rows (without switching the elements in the right-hand column vector) gives

(8)

Subtracting 9 times the first row from the third row gives

(9)

Subtracting 4 times the first row from the second row gives

(10)

Finally, adding times the second row to the third row gives

(11)

Restoring the transformed matrix equation gives

(12)

which can be solved immediately to give , back-substituting to obtain (which actually follows trivially in this example), and then again back-substituting to find

Solving three-variable, three-equation linear systems is more difficult, at least initially, than solving the two-variable systems, because the computations involved are more messy. You will need to be very neat in your working, and you should plan to use lots of scratch paper. The method for solving these systems is an extension of the two-variable solving-by-addition method, so make sure you know this method well and can use it consistently correctly.

Though the method of solution is based on addition/elimination, trying to do actual addition tends to get very messy, so there is a systematized method for solving the three-or-more-variables systems. This method is called “Gaussian elimination” (with the equations ending up in what is called “row-echelon form”).

Examples-

Solve the following system of equations.

5x + 4y –    z = 0

      10y – 3z = 11

                  z = 3

It’s fairly easy to see how to proceed in this case. I’ll just back-substitute the z-value from the third equation into the second equation, solve the result for y, and then plug z and y into the first equation and solve the result for x.

10y – 3(3) = 11

10y – 9 = 11

10y = 20

y = 2

5x + 4(2) – (3) = 0

5x + 8 – 3 = 0

5x + 5 = 0

5x = -5

x = -1

Then the solution is (x, y, z) = (-1, 2, 3).

The reason this system was easy to solve is that the system was “triangular”; this refers to the equations having the form of a triangle, because of the lower equations containing only the later variables.

The point is that, in this format, the system is simple to solve. And Gaussian elimination is the method we’ll use to convert systems to this upper triangular form, using the row operations we learned when we did the addition method.

Solve the following system of equations using Gaussian elimination.

-3x + 2y – 6z = 6

  5x + 7y – 5z = 6

     x + 4y – 2z = 8

No equation is solved for a variable, so I’ll have to do the multiplication-and-addition thing to simplify this system. In order to keep track of my work, I’ll write down each step as I go. But I’ll do my computations on scratch paper. Here is how I did it:

The first thing to do is to get rid of the leading x-terms in two of the rows. For now, I’ll just look at which rows will be easy to clear out; I can switch rows later to get the system into “upper triangular” form. There is no rule that says I have to use the x-term from the first row, and, in this case, I think it will be simpler to use the x-term from the third row, since its coefficient is simply “1”. So I’ll multiply the third row by 3, and add it to the first row. I do the computations on scratch paper:

…and then I write down the results:

(When we were solving two-variable systems, we could multiply a row, rewriting the system off to the side, and then add down. There is no space for this in a three-variable system, which is why we need the scratch paper.)

Warning: Since I didn’t actually do anything to the third row, I copied it down, unchanged, into the new matrix of equations. I used the third row, but I didn’t actually change it. Don’t confuse “using” with “changing”.

To get smaller numbers for coefficients, I’ll multiply the first row by one-half:

Now I’ll multiply the third row by -5 and add this to the second row. I do my work on scratch paper:

…and then I write down the results: Copyright © Elizabeth Stapel 1999-2009 All Rights Reserved

I didn’t do anything with the first row, so I copied it down unchanged. I worked with the third row, but I only worked on the second row, so the second row is updated and the third row is copied over unchanged.

Okay, now the x-column is cleared out except for the leading term in the third row. So next I have to work on the y-column.

Warning: Since the third equation has an x-term, I cannot use it on either of the other two equations any more (or I’ll undo my progress). I can work on the equation, but not with it.

If I add twice the first row to the second row, this will give me a leading 1 in the second row. I won’t have gotten rid of the leading y-term in the second row, but I will have converted it (without getting involved in fractions) to a form that is simpler to deal with. (You should keep an eye out for this sort of simplification.) First I do the scratch work:

…and then I write down the results:

Now I can use the second row to clear out the y-term in the first row. I’ll multiply the second row by -7 and add. First I do the scratch work:

…and then I write down the results:

I can tell what z is now, but, just to be thorough, I’ll divide the first row by 43. Then I’ll rearrange the rows to put them in upper-triangular form:

Now I can start the process of back-solving:

y – 7(1) = -4

y – 7 = -4

y = 3

x + 4(3) – 2(1) = 8

x + 12 – 2 = 8

x + 10 = 8

x = -2

Then the solution is (x, y, z) = (-2, 3, 1).

Note: There is nothing sacred about the steps I used in solving the above system; there was nothing special about how I solved this system. You could work in a different order or simplify different rows, and still come up with the correct answer. These systems are sufficiently complicated that there is unlikely to be one right way of computing the answer. So don’t stress over “how did she know to do that next?”, because there is no rule. I just did whatever struck my fancy; I did whatever seemed simplest or whatever came to mind first. Don’t worry if you would have used completely different steps. As long as each step along the way is correct, you’ll come up with the same answer.

This way, I can just read off the values of x, y, and z, and I don’t have to bother with the back-substitution. This more-complete method of solving is called “Gauss-Jordan elimination” (with the equations ending up in what is called “reduced-row-echelon form”). Many texts only go as far as Gaussian elimination, but I’ve always found it easier to continue on and do Gauss-Jordan.

Note that I did two row operations at once in that last step before switching the rows. As long as I’m not working with and working on the same row in the same step, this is okay. In this case, I was working with the first row and working on the second and third rows.

Gauss Jordan elimination method

Gauss-Jordan Elimination is a variant of Gaussian Elimination. Again, we are transforming the coefficient matrix into another matrix that is much easier to solve, and the system represented by the new augmented matrix has the same solution set as the original system of linear equations. In Gauss-Jordan Elimination, the goal is to transform the coefficient matrix into a diagonal matrix, and the zeros are introduced into the matrix one column at a time. We work to eliminate the elements both above and below the diagonal element of a given column in one pass through the matrix.

The general procedure for Gauss-Jordan Elimination can be summarized in the following steps:

Gauss-Jordan Elimination Steps

Write the augmented matrix for the system of linear equations.

Use elementary row operations on the augmented matrix [A|b] to transform A into diagonal form. If a zero is located on the diagonal, switch the rows until a nonzero is in that place. If you are unable to do so, stop; the system has either infinite or no solutions.

By dividing the diagonal element and the right-hand-side element in each row by the diagonal element in that row, make each diagonal element equal to one.

An Example.

We will apply Gauss-Jordan Elimination to the same example that was used to demonstrate Gaussian Elimination. Remember, in Gauss-Jordan Elimination we want to introduce zeros both below and above the diagonal.

1. Write the augmented matrix for the system of linear equations.

As before, we use the symbol to indicate that the matrix preceding the arrow is being changed due to the specified operation; the matrix following the arrow displays the result of that change.

2. Use elementary row operations on the augmented matrix [A|b] to transform A into diagonal form.

At this point we have a diagonal coefficient matrix. The final step in Gauss-Jordan Elimination is to make each diagonal element equal to one. To do this, we divide each row of the augmented matrix by the diagonal element in that row.

3. By dividing the diagonal element and the right-hand-side element in each row by the diagonal element in that row, make each diagonal element equal to one.

Hence,

Our solution is simply the right-hand side of the augmented matrix. Notice that the coefficient matrix is now a diagonal matrix with ones on the diagonal. This is a special matrix called the identity matrix.

When performing calculations by hand, many individuals choose Gauss-Jordan Elimination over Gaussian Elimination because it avoids the need for back substitution. However, we will show later that Gauss-Jordan elimination involves slightly more work than does Gaussian elimination, and thus it is not the method of choice for solving systems of linear equations on a computer.

Example 2: Using Gauss-Jordan Elimination

(1) We start with a system of linear equations:

x1 – 2×2 + 4×3 = 12

2×1 – x2 + 5×3 = 18

-x1 + 3×2 – 3×3 = -8

(2) We represent them in augmented matrix form:

(3) We use elementary row operations to put this matrix into reduced echelon form (I will use R1, R2, R3 for Row 1, Row 2, and Row 3):

(a) Let R2 = R2 + (-2)R1 [Operation #3]

(b) Let R3 = R3 + R1 [Operation #3]

(c) Let R2 = (1/3)R2 [Operation #2]

(d) Let R1 = R1 + 2*R2 [Operation #3]

(e) Let R3 = R3 + (-1)*R2 [Operation #3]

(f) Let R3 = (1/2)R3 [Operation #2]

(g) Let R1 = R1 + (-2)*R3 [Operation #3]

(h) Let R2 = R2 + R3 [Operation #3]

(4) We now write down the system of linear equations corresponding to the reduced echelon form:

x1 = 2

x2 = 1

x3 = 3

Of course, we need to be sure that we can always get to reduced echelon form. Here is the theorem that guarantees this:

Theorem 1: Every matrix is row equivalent to a reduced echelon form matrix

Proof:

(1) The Gauss-Jordan Elimination Algorithm works for any 1 x n matrix.

(a) Let A = 1 x n matrix

(b) Assume that A is not all zeros (if it were, then A is already in reduced echelon form)

(c) Let a1,i be the first nonzero element in A.

(d) Let A = (1/a1,i)*A

(f) A now has a leading 1 and since this is a one-row matrix, A is now in reduced echelon form.

(2) Assume that the Gauss-Jordan Elimination Algorithm works for any matrix up to k rows.

(3) We can now show that it will work for a matrix with k+1 rows.

(a) Let A = a nonzero matrix with k+1 rows [We can assume it is nonzero since if it were zero, it would already be in reduced echelon form]

(b) Assume that we’ve run the Gauss-Jordan Elimination Algorithm up to the kth row so that if we define B such that:

(c) We can see that B is in reduced echelon form since

(i) B has k rows

(ii) We can assume by our assumption in step #2 that the algorithm works for any matrix of k rows or less

(iii) The algorithm leaves B unchanged if we run it again.

(d) We can also see that Ak+1 consists of a single row which is zero for every column where there is a leading 1 in B. [Since these are zero’d out by the algorithm above]

(e) If there is a nonzero column in Ak+1, it must therefore be to the right of all the leading 1s in B.

(f) Assume that there is a nonzero column in Ak+1 [If there were not, we would be done, since then Ak+1 would consist of all zero’s and A would then be in reduced echelon form]

(g) In this case, none of the rows in B are all zeros. [In order for Ak+1 to be nonzero, each of the previous rows must have had at least one nonzero column. If one was all zeros, it would have been exchanged with Ak+1 and then Ak+1 would be all zeros which it is not]

(h) Let ak+1,x = the first nonzero element in Ak+1

(i) Let Ak+1 = (1/ak+1,x)Ak+1

(j) For all rows i, 1 thru k, let Ri = Ri + (-ai,x)*Rk+1.

(k) Clearly, this will zero out each of the remaining rows.

(l) A is now in reduced echelon form