Gauss Elimination

Solving of a system of linear algebraic equations appears frequently in many engineering problems. Most of numerical techniques which deals with partial differential equations, represent the governing equations of physical phenomena in the form of a system of linear algebraic equations. Gauss elimination technique is a well-known numerical method which is employed in many scientific problems.

Consider an arbitrary system of linear algebraic equations as follows:

 

a11x1 + a12x2 + … + a1nxn = c1

a21x1 + a22x2 + … + a2nxn = c2

.

.

.

an1x1 + an2x2 + … + annxn = cn

where xi are unknowns and aij are coefficients of unknowns and ci are equations’ constants. This system of algebraic equation can be written in the matrix form as follows:

[A]{x}={C}

Where [A] is the matrix of coefficient and {x} is the vector of unknowns and {C} is the vector of constants. Gauss elimination method eliminate unknowns’ coefficients of the equations one by one. Therefore the matrix of coefficients of the system of linear equations is transformed to an upper triangular matrix. The last transformed equation has only one unknown which can be determined easily. This evaluated unknown can be used in the upper equation for determining the next unknown and so on. Finally the system of linear equations can be solved by back substitution of evaluated unknowns. For example consider the following system of algebraic equations:

If the first equation is multiplied by -2 and is added to the second equation and if the first equation is added to the third equation, the system of linear equation can be written as follows:

The x’s coefficient of the last two equations has be eliminated. This technique can be used for the last equation again. If the second equation is multiplied by 3 and is added to the third one, the system of linear equation is transformed to the following one:

Using the third equation, z can be evaluated easily and then y can be determined by the second equation and x can be determined by using the first one. 

The algorithm of the Gauss elimination method can be written as follows:

 

Step 1: For k = 1 to n-1 do step 2 to step 5

Step 2: For i = k+1 to n do step 3 to step 5

Step 3: For j = k+1 to n do step 4

Step 4: aij = aij – aik.akj / akk

Step 5: ci = ci – aik.ck / akk

Step 6: xn = cn / ann

Step 7: For i = n-1 to 1 do step 8 to step 11

Step 8: s = 0

Step 9: For j = i+1 to n do step 10

Step 10: s = s + aijxj

Step 11: xi = (ci-s) / aii

Step 12: End.

System of Linear Equations                                             
         (Source Code in C++)                                                  

o        Gauss Elimination Method                                                         

o        Gauss-Seidel Method                                                                 

o        Jacobi Method                                                                            

o        LU Decomposition Method                                                        

o        Relaxation Methods                                                                   
                                                                                 
 
 

Comments