Elimination Methods

• Solve a set of linear (variables with first power) equations.
• If we have a system of equations that is of an upper- triangular form
  
  Then, we have the solution as: $x_1=2,~x_2= - 1,~x_3 = 5$
• If NOT: Change the matrix of coefficients $\Longrightarrow$ upper- triangular. Consider this example of three equations:

  

  

  

  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 this 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;
  

• 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:

  

  

  

  

  

  

• 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.
• 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.

Possible approaches for the solution of the following system of equations with coefficient matrix $A$.

1

Cramer's rule. $$6x_1-3x_2+ x_3 = 11$$ $$2x_1+ x_2 -8x_3 = -15$$ $$x_1 -7x_2+x_3 = 10$$ Let's denote the matrix by $A_j$ in which the right-hand-side vector are substituted to the $j^{th}$ column of $A$ matrix. e.g., the solution for $x_1$ is expressed as: Similarly, the solutions $x_2$ and $x_3$ can be written.

This method is very convenient when the number of unknowns is as few as 3-5. However, it is not feasible for systems with a large number of unknowns since determinant calculation requires many multiplication operations. For example, calculating a $20 \times 20$ determinant with Cramer's rule requires $\approx 10^{20}$ multiplications!

2

Inverse matrix. Another solution is to use the $A^{-1}$ matrix, which is the inverse of the A matrix. Multiplying both sides of the equation $A\vec{x}=\vec{b}$ by $A^{-1}$ and considering that $A^{-1}$$A=1$, $$A^{-1} A\vec{x} = A^{-1} \vec{b}$$ $$\underbrace{A^{-1} A}_1\vec{x} = A^{-1} \vec{b}$$ $$\vec{x} = A^{-1} \vec{b}$$ However, this approach is also not reasonable since calculating matrix inverses requires a large number of operations.