Elimination Methods

• To solve a set of linear equations.
• The term linear equation means an equation in several variables where all of the variables occur to the first power.
• Suppose we have a system of equations that is of a special form, an upper-triangular system, such as
  $$\begin{array}{r} 5x_1+3x_2-2x_3=-3 \\ 6x_2+x_3=-1 \\ 2x_3=10 \\ \end{array}$$
  we have the solution $x_1=2, x_2= - 1, x_3 = 5$
• Change the matrix of coefficients $\Longrightarrow$ upper triangular.
  $$\begin{array}{r} 4x_1-2x_2+ x_3=15 \\ -3x_1 -x_2+4x_3=8 \\ x_1 -x_2+3x_3=13 \\ \end{array}$$
  $$\begin{array}{r} 4x_1-2x_2+ x_3=15 \\ -10x_2+19x_3=77 \\ -2x_2+11x_3=37 \\ \end{array}$$
  $$\begin{array}{r} 4x_1-2x_2+ x_3= 15 \\ -10x_2+19x_3= 77 \\ -72x_3=-216 \\ \end{array}$$

  Now we have a triangular system and the solution is readily obtained;

  1. obviously $x_3=3$ from the third equation,
  2. and back-substitution into the second equation gives $x_2=-2$.
  3. We continue with back-substitution by substituting both $x_2$, and $x_3$ into the first equation to get $x_1=2$.

• Notice to the values in the previous example.
• They are getting bigger!
• The essence of any elimination method is to reduce the coefficient matrix to a triangular matrix and then use back-substitution to get the solution.
• We now present the same problem, solved in exactly the same way, in matrix notation;
  $$\left[ \begin{array}{rrr} 4 & -2 & 1 \\ -3 & -1 & 4 \\ ... ...t[ \begin{array}{r} 15 \\ 8 \\ 13 \\ \end{array} \right]$$

• The arithmetic operations that we have performed affect only the coefficients and the right-hand-side terms.

• So we work with the matrix of coefficients augmented with the right-hand-side vector.
• We perform elementary row transformations to convert A to upper-triangular form:
  $$\left[ \begin{array}{rrrr} 4 & -2 & 1 &15 \\ -3 & -1 & 4 &8 \\ 1 & -1 & 3 &13 \\ \end{array} \right],$$
  $$\begin{array}{r} \\ 3R_1+4R_2 \rightarrow \\ (-1)R_1+4R_3 \rightarrow \\ \end{array}$$
  $$\left[ \begin{array}{rrrr} 4 & -2 & 1 &15 \\ 0 & -10 & 19 &77 \\ 0 & -2 & 11 &37 \\ \end{array} \right],$$
  $$\begin{array}{r} \\ \\ 2R_2-10R_3 \rightarrow \\ \end{array}$$
  $$\left[ \begin{array}{rrrr} 4 & -2 & 1 &15 \\ 0 & -10 & 19 &77 \\ 0 & 0 & 72 &-216 \\ \end{array} \right] \Rightarrow$$
  $$\begin{array}{r} 4x_1-2x_2+ x_3= 15 \\ -10x_2+19x_3= 77 \\ -72x_3=-216 \\ \end{array}$$

• The back-substitution step can be performed quite mechanically by solving the equations in reverse order. That is, $x_3=3,x_2=-2,x_1=2$.
• Same solution with the non-matrix notation.

• Note that there exists the possibility that the set of equations has no solution, or that the prior procedure will fail to find it.
• During the triangularization step, if a zero is encountered on the diagonal, we cannot use that row to eliminate coefficients below that zero element.
• However, in that case, we can continue by interchanging rows and eventually achieve an upper-triangular matrix of coefficients.
• The real trouble is finding a zero on the diagonal after we have triangularized.
• If that occurs, the back-substitution fails, for we cannot divide by zero.
• It also means that the determinant is zero. There is no solution.