Gaussian Elimination Method And Gauss Jordan Method Computer Science Essay
Gaussian Elimination is considered as the workhorse of computational science for the solution of a system of the linear equations. In linear algebra, Gaussian elimination is an algorithm for the solving systems of the linear equations, and finding the rank of a matrix, and calculating the inverse of an invertible square matrix. Gaussian elimination is named after the German mathematician and the scientist Carl Friedrich Gauss. The method was invented in Europe independently by Carl Friedrich Gauss when developing the method of least squares in his 1809 publication Theory of Motion of Heavenly Bodies.
Gauss elimination is an exact method which solves a given system of equation in n unknowns by transforming the coefficient matrix, into an upper triangular matrix and the n solve for the unknowns by back substitution.
Solving Method:
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 done through the use of elementary. The second step uses back substitution to find the solution of the system above. 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.
Initially, for the given system, write row, the sum of the coefficients in each row, in the (n+2) nd column. Perform the same operation on the elements of this column also. Now in the absence of computational errors, at any stage, the row sum element in (n+2)nd row, will be equal to the sum of the of the elements of the corresponding transformed row.
Algorithm for Gaussian Elimination:-
Transform the columns of the augmented matrix, one at a time, into triangular echelon form. The column presently being transformed is called the pivot column. Proceed from left to right, letting the pivot column be the first column, then the second column, etc. and finally the last column before the vertical line. For each pivot column, do the following two steps before moving on to the next pivot column:
Locate the diagonal element in the pivot column. This element is called the pivot. The row containing the pivot is called the pivot row. Divide every element in the pivot row by the pivot (ie. use E.R.O. #1) to get a new pivot row with a 1 in the pivot position.
Get a 0 in each position below the pivot position by subtracting a suitable multiple of the pivot row from each of the rows below it (ie. by using E.R.O. #2).
Upon completion of this procedure the augmented matrix will be in triangular echelon form and may be solved by back-substitution.
Steps Taken in Gauss Elimination Method:
Write the augmented matrix for the system of the linear equations.
Use elementary row operations on the augmented matrix [A|b] to the transform of A into the upper triangular form. If the zero is locate on the diagonal, switch the rows until a nonzero is in that place. If we are unable to do so, stop; the system has either infinite or has no solutions.
Use the back substitution going to find the solution of the problem.
Systems Of Linear Equations: Gaussian Elimination:-
It is quite hard to solve non-linear systems of equations, while linear systems are quite easy to study. There are numerical techniques which help to approximate nonlinear systems with linear ones in the hope that the solutions of the linear systems are close enough to the solutions of the nonlinear systems.
The equation
a x + b y + c z + d w = h
Where a, b, c, d, and h are known numbers, while x, y, z, and w are unknown numbers, is called a linear equation. If h =0, the linear equation is said to be homogeneous. A linear system is a set of linear equations and a homogeneous linear system is a set of homogeneous linear equations.
Example: Use Gaussian elimination to solve the system of equations:
Solution: Perform this sequence of E.R.O.’s on the augmented matrix. Set the pivot column to column 1. Get a 1 in the diagonal position (underlined):
Next, get 0’s below the pivot (underlined):
Now, let pivot column = second column. First, get a 1 in the diagonal position:
Next, get a 0 in the position below the pivot:
Now, let pivot column = third column. Get a 1 in the diagonal position:
This matrix, which is now in triangular echelon form, represents:
It is solved by back-substitution. Substituting z = 3 from the third equation into the second equation gives y = 5, and substituting z = 3 and y = 5 into the first equation gives x = 7. Thus the complete solution is:
{x = 7, y = 5, z = 3}.
Gauss Jordan 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.
Solving Method
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.
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.
This method can be used to solve systems of linear equations involving two or
more variables. However, the system must be changed to an augmented matrix.
-This method can also be used to find the inverse of a 2×2 matrix or larger matrices, 3×3,
4×4 etc.
Note: The matrix must be a square matrix in order to find its inverse.
An Augmented Matrix is used to solve a system of linear equations.
a1 x + b1 y + c1z = d1
a2 x + b2 y + c2 z = d2
a3x + b3 y + c3z = d3
System of Equations ƒ
Augmented Matrix ƒ a1 b1 c1 d1
a2 b2 c2 d2
a3 b3 c3 d3
When given a system of equations, to write in augmented matrix form, the coefficients of each variable must be taken and put in a matrix.
For example, for the following system:
3x + 2y – z = 3
x – y + 2z = 4
2x + 3y – z = 3
3 2 -1 3
Augmented matrix ƒ 1 -1 2 4
2 3 -1 3
There are three different operations known as Elementary Row Operations used when solving or reducing a matrix, using Gauss-Jordan elimination method.
1. Interchanging two rows.
2. Add one row to another row, or multiply one row first and then adding it
to another.
3. Multiplying a row by any constant greater than zero.
Identity Matrix-is the final result obtained when a matrix is reduced. This matrix
consists of ones in the diagonal starting with the first number.
-The numbers in the last column are the answers to the system
of equations.
1 0 0 3
0 1 0 2 ←⎯⎯Identity Matrix for a 3×3
0 0 1 5
1 0 0 0 2
0 1 0 0 6
←⎯⎯Identity Matrix for a 4×4
0 0 1 0 1
0 0 0 1 4
The pattern continues for bigger matrices.
Solving a system using Gauss-Jordan
The best way to go is to get the ones first in their respective column, and then
using that one to get the zeros in that column.
It is very important to understand that there is no exact procedure to follow when
using the Gauss-Jordan method to solve for a system.
3x + 2y – z = 3
x – y + 2z = 4 Write as an augmented matrix.
2x + 3y – z = 3
Order Now