Gauss Elimination Method part 1

Posted by Unknown on 10:06 PM with No comments
Gaussian elimination is a method of solving a linear system $ A {\mathbf x}= {\mathbf b}$ (consisting of $ m$ equations in $ n$ unknowns) by bringing the augmented matrix
$\displaystyle [A \;\; {\mathbf b}] = \left[\begin{array}{cccc\vert c} a_{11} & ... ... \vdots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} & b_m \end{array}\right]$
to an upper triangular form
$\displaystyle \left[\begin{array}{cccc\vert c} c_{11} & c_{12} & \cdots & c_{1n... ... \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & c_{mn} & d_m \end{array}\right].$
This elimination process is also called the forward elimination method. The following examples illustrate the Gauss elimination procedure.
EXAMPLE 2.2.11   Solve the linear system by Gauss elimination method.
$\displaystyle y + z$ $\displaystyle =$ $\displaystyle 2$  
$\displaystyle 2 x + 3 z$ $\displaystyle =$ $\displaystyle 5$  
$\displaystyle x+ y + z$ $\displaystyle =$ $\displaystyle 3$  

Solution: In this case, the augmented matrix is $ \begin{bmatrix}0 & 1 & 1 & 2 \\ 2 & 0 & 3 & 5 \\ 1 & 1 & 1 & 3 \end{bmatrix}.$ The method proceeds along the following steps.
  1. Interchange $ 1^{\mbox{st}}$ and $ 2^{\mbox{nd}}$ equation (or $ R_{12}$ ).
    $\displaystyle \begin{array}{cr} 2 x + 3 z &= 5 \\ y + z &= 2 \\ x + y + z &= 3 ... ...} \begin{bmatrix}2 & 0 & 3 & 5 \\ 0 & 1 & 1 & 2 \\ 1 & 1 & 1 & 3 \end{bmatrix}.$
  2. Divide the $ 1^{\mbox{st}}$ equation by $ 2$ (or $ R_1(1/2)$ ).
    $\displaystyle \begin{array}{cr} x + \frac{3}{2} z &= \frac{5}{2} \\ y + z &= 2... ...0 & \frac{3}{2} & \frac{5}{2} \\ 0 & 1 & 1 & 2 \\ 1 & 1 & 1 & 3 \end{bmatrix}. $
  3. Add $ -1$ times the $ 1^{\mbox{st}}$ equation to the $ 3^{\mbox{rd}}$ equation (or $ R_{31}(-1)$ ).
    \begin{displaymath}\begin{array}{cr} x + \frac{3}{2} z &= \frac{5}{2} \\ y + z &... ...1 & 1 & 2 \\ 0 & 1 & -\frac{1}{2} & \frac{1}{2} \end{bmatrix}. \end{displaymath}
  4. Add $ -1$ times the $ 2^{\mbox{nd}}$ equation to the $ 3^{\mbox{rd}}$ equation (or $ R_{32}(-1)$ ).
    $\displaystyle \begin{array}{cr} x + \frac{3}{2} z &= \frac{5}{2} \\ y + z &= 2 ... ...ac{5}{2} \\ 0 & 1 & 1 & 2 \\ 0 & 0 & -\frac{3}{2} & -\frac{3}{2} \end{bmatrix}.$
  5. Multiply the $ 3^{\mbox{rd}}$ equation by $ \frac{-2}{3}$ (or $ R_3(-\frac{2}{3})$ ).
    $\displaystyle \begin{array}{cr} x + \frac{3}{2} z &= \frac{5}{2} \\ y + z &= 2 ... ... 0 & \frac{3}{2} & \frac{5}{2} \\ 0 & 1 & 1 & 2 \\ 0 & 0 & 1 & 1 \end{bmatrix}.$
The last equation gives $ z=1,$ the second equation now gives $ y=1.$ Finally the first equation gives $ x = 1.$ Hence the set of solutions is $ (x, y, z)^t = (1, 1, 1)^t,$ A UNIQUE SOLUTION.
EXAMPLE 2.2.12   Solve the linear system by Gauss elimination method.
$\displaystyle x+ y + z$ $\displaystyle =$ $\displaystyle 3$  
$\displaystyle x + 2 y + 2 z$ $\displaystyle =$ $\displaystyle 5$  
$\displaystyle 3 x + 4 y + 4 z$ $\displaystyle =$ $\displaystyle 11$  

Solution: In this case, the augmented matrix is $ \begin{bmatrix}1 & 1 & 1 & 3 \\ 1 & 2 & 2 & 5 \\ 3 & 4 & 4 & 11 \end{bmatrix}$ and the method proceeds as follows:
  1. Add $ -1$ times the first equation to the second equation.
    $\displaystyle \begin{array}{cr} x + y + z &= 3 \\ y + z &= 2 \\ 3 x +4 y +4 z ... ...begin{bmatrix} 1 & 1 & 1 & 3 \\ 0 & 1 & 1 & 2 \\ 3 & 4 & 4 & 11 \end{bmatrix}. $
  2. Add $ -3$ times the first equation to the third equation.
    $\displaystyle \begin{array}{cr} x + y + z &= 3 \\ y + z &= 2 \\ y + z &= 2 \en... ...\begin{bmatrix} 1 & 1 & 1 & 3 \\ 0 & 1 & 1 & 2 \\ 0 & 1 & 1 & 2 \end{bmatrix}. $
  3. Add $ -1$ times the second equation to the third equation
    $\displaystyle \begin{array}{cr} x + y+ z &= 3 \\ y + z &= 2 \end{array} \hspace... ... \begin{bmatrix}1 & 1 & 1 & 3 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{bmatrix}. $
Thus, the set of solutions is $ (x, y, z)^t = (1, 2-z, z)^t = (1, 2, 0)^t + z (0, -1, 1)^t,$ with $ z$ arbitrary. In other words, the system has INFINITE NUMBER OF SOLUTIONS.
EXAMPLE 2.2.13   Solve the linear system by Gauss elimination method.
$\displaystyle x+ y + z$ $\displaystyle =$ $\displaystyle 3$  
$\displaystyle x + 2 y + 2 z$ $\displaystyle =$ $\displaystyle 5$  
$\displaystyle 3 x + 4 y + 4 z$ $\displaystyle =$ $\displaystyle 12$  

Solution: In this case, the augmented matrix is $ \begin{bmatrix}1 & 1 & 1 & 3 \\ 1 & 2 & 2 & 5 \\ 3 & 4 & 4 & 12 \end{bmatrix}$ and the method proceeds as follows:
  1. Add $ -1$ times the first equation to the second equation.
    $\displaystyle \begin{array}{cr} x + y + z &= 3 \\ y + z &= 2 \\ 3 x +4 y +4 z ... ...begin{bmatrix} 1 & 1 & 1 & 3 \\ 0 & 1 & 1 & 2 \\ 3 & 4 & 4 & 12 \end{bmatrix}. $
  2. Add $ -3$ times the first equation to the third equation.
    $\displaystyle \begin{array}{cr} x + y + z &= 3 \\ y + z &= 2 \\ y + z &= 3 \en... ...\begin{bmatrix} 1 & 1 & 1 & 3 \\ 0 & 1 & 1 & 2 \\ 0 & 1 & 1 & 3 \end{bmatrix}. $
  3. Add $ -1$ times the second equation to the third equation
    $\displaystyle \begin{array}{cr} x + y+ z &= 3 \\ y + z &= 2 \\ 0 & = 1 \end{arr... ... \begin{bmatrix}1 & 1 & 1 & 3 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 1 \end{bmatrix}. $
The third equation in the last step is
$\displaystyle 0 x + 0 y + 0 z = 1.$
This can never hold for any value of $ x, y, z.$ Hence, the system has NO SOLUTION.