Guass Elimination Method

When we solve a linear system using elimination, we first replace the given linear system with a sequence of simpler linear systems by eliminating variables, making sure to only use allowed operations in each step (that is, operations that preserve the solutions of the linear system).

This method is based on the idea of reducing the given system of equations Ax = b, to an upper triangular system of equations Ux = z, using elementary row operations. We know that these two systems are equivalent. That is, the solutions of both the systems are identical. This reduced system Ux = z, is then solved by the back substitution method to obtain the solution vector x.

We illustrate the method using the 3 × 3 system.



We write the augmented matrix [A | b] and reduce it to the following form

The augmented matrix of the system (1.1) is



First stage of elimination :

We assume a11 ≠ 0. This element a11in the 1 × 1 position is called the first pivot. We use this pivot to reduce all the elements below this pivot in the first column as zeros. Multiply the first row in (1.2) by a21/a11 and a31/a11 respectively and subtract from the second and third rows. That is, we are performing the elementary row operations R2 – (a21/a11)R1 and R3 –(a31/a11)R1 respectively. We obtain the new augmented matrix as




Second stage of elimination:

We assume a(1) 22 ≠ 0 . This element a(1)22 in the 2 × 2 position is called the second pivot.We use this pivot to reduce the element below this pivot in the second column as zero. Multiply the second row in (1.3) by a(1)32 / a(1)22 and subtract from the third row. That is, we are performing the elementary row operation R3 – ( a(1)32 / a(1)22 )R2. We obtain the new augmented matrix as



The element a(2)33 ≠ 0 is called the third pivot. This system is in the required upper triangular form [U|z]. The solution vector x is now obtained by back substitution.