Print Email Download Reference This Send to Kindle Reddit This
submit to reddit

Gaussian Elimination Gauss Jordon Method English Language Essay

In linear algebra, Gaussian elimination is an algorithm for solving systems of linear equations, finding the rank of a matrix, and calculating the inverse of an invertible square matrix. Gaussian elimination is named after German mathematician and scientist Carl Friedrich Gauss, which makes it an example of Stigler's law.

Elementary row operations are used to reduce a matrix to row echelon form. Gauss–Jordan elimination, an extension of this algorithm, reduces the matrix further to reduced row echelon form. Gaussian elimination alone is sufficient for many applications, and is cheaper than the -Jordan version.

HISTORY:-The method of Gaussian elimination appears in Chapter Eight, Rectangular Arrays, of the important Chinese mathematical text Jiuzhang suanshu or The Nine Chapters on the Mathematical Art. Its use is illustrated in eighteen problems, with two to five equations. The first reference to the book by this title is dated to 179 CE, but parts of it were written as early as approximately 150 BCE.[1] It was commented on by Liu Hui in the 3rd century.

The method in Europe stems from the notes of Isaac Newton.[2] In 1670, he wrote that all the algebra books known to him lacked a lesson for solving simultaneous equations, which Newton then supplied. Cambridge University eventually published the notes as Arithmetical Universalis in 1707 long after Newton left academic life. The notes were widely imitated, which made (what is now called) Gaussian elimination a standard lesson in algebra textbooks by the end of the 18th century. Carl Friedrich Gauss in 1810 devised a notation for symmetric elimination that was adopted in the 19th century by professional hand computers to solve the normal equations of least-squares problems. The algorithm that is taught in high school was named for Gauss only in the 1950s as a result of confusion over the history of the subject.

Algor ithm overview:-The process of Gaussian elimination has two parts. The first part (Forward Elimination) reduces a given system to either triangular or echelon form, or results in a degenerate equation with no solution, indicating the system has no solution. This is accomplished through the use of elementary row operations. The second step uses back substitution to find the solution of the system above.

Stated equivalently for matrices, the first part reduces a matrix to row echelon form using elementary row operations while the second reduces it to reduced row echelon form, or row canonical form.

Another point of view, which turns out to be very useful to analyze the algorithm, is that Gaussian elimination computes a matrix decomposition. The three elementary row operations used in the Gaussian elimination (multiplying rows, switching rows, and adding multiples of rows to other rows) amount to multiplying the original matrix with invertible matrices from the left. The first part of the algorithm computes an LU decomposition, while the second part writes the original matrix as the product of a uniquely determined invertible matrix and a uniquely determined reduced row-echelon matrix.

Example

Suppose the goal is to find and describe the solution(s), if any, of the following system of linear equations:

The algorithm is as follows: eliminate x from all equations below L1, and then eliminate y from all equations below L2. This will put the system into triangular form. Then, using back-substitution, each unknown can be solved for.

In the example, x is eliminated from L2 by adding to L2. x is then eliminated from L3 by adding L1 to L3. Formally:

The result is:

Now y is eliminated from L3 by adding − 4L2 to L3:

The result is:

This result is a system of linear equations in triangular form, and so the first part of the algorithm is complete.

The last part, back-substitution, consists of solving for the known in reverse order. It can thus be seen that

Then, z can be substituted into L2, which can then be solved to obtain

Next, z and y can be substituted into L1, which can be solved to obtain

The system is solved.

Some systems cannot be reduced to triangular form, yet still have at least one valid solution: for example, if y had not occurred in L2 and L3 after the first step above, the algorithm would have been unable to reduce the system to triangular form. However, it would still have reduced the system to echelon form. In this case, the system does not have a unique solution, as it contains at least one free variable. The solution set can then be expressed parametrically (that is, in terms of the free variables, so that if values for the free variables are chosen, a solution will be generated).

In practice, one does not usually deal with the systems in terms of equations but instead makes use of the augmented matrix (which is also suitable for computer manipulations). For example:

Therefore, the Gaussian Elimination algorithm applied to the augmented matrix begins with:

This, at the end of the first part (Gaussian elimination, zeros only under the leading 1) of the algorithm, looks like this:

That is, it is in row echelon form.

At the end of the algorithm, if the Gauss–Jordan elimination (zeros under and above the leading 1) is applied:

That is, it is in reduced row echelon form, or row canonical form.

APPLICATION:-

1. Finding the inverse of a matrix:-

Suppose A is a matrix and you need to calculate its inverse. The identity matrix is augmented to the right of A, forming a matrix (the block matrix B = [A,I]). Through application of elementary row operations and the Gaussian elimination algorithm, the left block of B can be reduced to the identity matrix I, which leaves A − 1 in the right block of B.

If the algorithm is unable to reduce A to triangular form, then A is not invertible.

2. General algorithm to compute ranks and bases:-

The Gaussian elimination algorithm can be applied to any matrix A. If we get "stuck" in a given column, we move to the next column. In this way, for example, some matrices can be transformed to a matrix that has a reduced row echelon form like

(The *'s are arbitrary entries). This echelon matrix T contains a wealth of information about A: the rank of A is 5 since there are 5 non-zero rows in T; the vector space spanned by the columns of A has a basis consisting of the first, third, fourth, seventh and ninth column of A (the columns of the ones in T), and the *'s tell you how the other columns of A can be written as linear combinations of the basis columns.

3. Systems of Linear Equations.

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").

Let's start simple, and work our way up to messier 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.

In the above example, I could have gone further in my computations and been more thorough-going in my row operations, clearing out all the y-terms other than that in the second row and all the z-terms other than that in the first row. This is what the process would then have looked like:

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 Method is like a tool to solve large linear equation numerically. It is done by manipulating the given matrix using elementary row operations. It puts zero both above and below each pivot element as it goes from top row of the matrix to the bottom. This method is also known as back substitution.

                                                          Consider three linear equations to be solved

                                                    a1x+b1y+c1z=d1

                                                   a2x+b2y+c2z=d2

                                                  a3x+b3y+c3z=d3

                 Augmented matrix is given by

                    [[a1,b1,c1,d1],[a2,b2,c2,d2],[a3,b3,c3,d3]] 

Has to be transformed to

αβγ

Procedure of Gauss Jordan Elimination Method:

                      For solving a system of three linear equations in three unknowns by Gauss Jordan elimination method, elementary row operation are performed on the augmented matrix as follow

STEP 1:

Transform the element at a11 position to 1, by a suitable elementary row transformation using the element at a21 or a31            

       Position or otherwise.

Transform the non-zero elements, if any, at a21,a31 position as zeros(other elements of the first column) by using the element 1 at a11 position.  If at the end of step 1, there is a non-zero element at a22 or a32 position, go to step 2.Otherwise skip it. 

Step 2:

Transform the element at a22 position as 1 by a suitable elementary row transformation using the element at a32 position or otherwise.

Transform the other non-zero elements, if any, of the second column (i.e., the non-zero elements, if any, at a12 and a32 positions) as zeros, by using the element 1 at a22 position.  At the end of step 2 or after skipping it for reasons specified above, examine the element at a33 position. If it is non-zero, go tostep3.Otherwise, stop. 

Step 3:

Transform the element at a33 position as 1 by dividing R3 with a suitable number.

Transform the other non-zero elements if any of the third column (i.e., the non-zero elements, if any, at a13 , a23 position) as zeros by using the 1 present at a33 position.

Example Problems on Gauss Jordan Elimination Method:

Problem: Solve the following equations by Gauss- Jordan Elimination method

                               3x+4y+5z=18

                               2x-y+8z=13

                                5x-2y+7z=20

Solution: The augmented Matrix is

                    [[3,4,5,18],[2,-1,8,13],[5,-2,7,20]

   On applying operation R1 --> R1 - R2, we get

         [[1,5,-3,5],[2,-1,8,13],[5,-2,7,20]]

     On applying  R2 -->R2 - 2R1,R3 --> R3 - 5R1 ,we get

          [[1,5,-3,5],[0,-11,14,3],[0,-27,22,-5]]

       On applying R2 --> -5R2+2R3, we get

         [[1,5,-3,5],[0,1,-26,-25],[0,-27,22,-5]

On applying R1 --> R1 - 5R2, R3 --> R3+27R2, we obtain

[[1, 0,127, 130], [0, 1,-26,-25],[0,0,-680,-680]]

      On applying R3 -->R3/(-680), we get

  [[1,0,127,130],[0,1,-26,-25],[0,0,1,1]]

On applying R1 --> R1-127R3, R2 --> R2+26R3 ,we obtain

                    [[1,0,0,3],[0,1,0,1],[0,0,1,1]]

             Hence the solution is x=3,y=1,z=1.

Print Email Download Reference This Send to Kindle Reddit This

Share This Essay

To share this essay on Reddit, Facebook, Twitter, or Google+ just click on the buttons below:

Request Removal

If you are the original writer of this essay and no longer wish to have the essay published on the UK Essays website then please click on the link below to request removal:

Request the removal of this essay.


More from UK Essays

Doing your resits? We can help!