Engineering at Alberta Courses » Gauss-Jordan Elimination

Direct Methods: Gauss-Jordan Elimination

The Method

Another method that is rooted in the Gauss elimination method is the Gauss-Jordan elimination method. Two steps are added to the previous algorithm. The first step is that each pivot row is normalized by the pivot element. The second step is that the coefficients above the pivot element are also eliminated. This results in not needing the backward substitution step. The following example illustrates the method. Consider the system of equations $Ax=b$ defined as:

$\begin{split} 2x_1+2x_2+2x_3&=6\\ 2x_1+3x_2+4x_3&=4\\ -x_1+2x_2+3x_3&=8\\ \end{split}$

The first row is normalized:

$\begin{split} x_1+x_2+x_3&=3\\ 2x_1+3x_2+4x_3&=4\\ -x_1+2x_2+3x_3&=8\\ \end{split}$

The first (pivot) row is used to eliminate the coefficients of $x_1$ in the second and third rows:

$\begin{split} x_1+x_2+x_3&=3\\ 0+1x_2+2x_3&=-2\\ 0+3x_2+4x_3&=11\\ \end{split}$

The second row is already normalized and can be used to eliminate the coefficients of $x_2$ in the third equation:

$\begin{split} x_1+x_2+x_3&=3\\ 0+1x_2+2x_3&=-2\\ 0+0-2x_3&=17\\ \end{split}$

It will also be used to eliminate the coefficients of $x_2$ in the first equation:

$\begin{split} x_1+0-x_3&=5\\ 0+1x_2+2x_3&=-2\\ 0+0-2x_3&=17\\ \end{split}$

The third pivot element will now be normalized:

$\begin{split} x_1+0-x_3&=5\\ 0+1x_2+2x_3&=-2\\ 0+0+x_3&=-\frac{17}{2}\\ \end{split}$

The third row is used to eliminate the coefficients of $x_3$ in the second and first equations:

$\begin{split} x_1+0+0&=-\frac{7}{2}\\ 0+x_2+0&=15\\ 0+0+x_3&=-\frac{17}{2}\\ \end{split}$

The right hand side is the required solution! In matrix form the following are essentially the steps above:

$\left(\begin{array}{ccc|c}2&2&2&6\\2&3&4&4\\-1&2&3&8\end{array}\right)\Rightarrow \left(\begin{array}{ccc|c}1&1&1&3\\0&1&2&-2\\0&3&4&11\end{array}\right) \Rightarrow \left(\begin{array}{ccc|c}1&0&-1&5\\0&1&2&-2\\0&0&-2&17\end{array}\right) \Rightarrow \left(\begin{array}{ccc|c}1&0&0&-\frac{7}{2}\\0&1&0&15\\0&0&1&-\frac{17}{2}\end{array}\right)$

The same issue of zero pivot applies to this method and another step of “pivoting” could be added to ensure no zero pivot is found in the matrix.

View Mathematica Code

GJElimination[A_, b_] :=
 (n = Length[A];
  G = Transpose[Insert[Transpose[A], b, n + 1]];
  For[k = 1, k <= n, 
   k++, (G[[k]] = G[[k]]/G[[k, k]]; 
    Do[G[[i]] = G[[i]] - G[[i, k]]*G[[k]], {i, 1, k - 1}]; 
    Do[G[[i]] = G[[i]] - G[[i, k]]*G[[k]], {i, k + 1, n}])];
  x = G[[All, n + 1]])
A = {{1, 2, 3, 5}, {2, 0, 1, 4}, {1, 2, 2, 5}, {4, 3, 2, 2}};
b = {-4, 8, 0, 10};
GJElimination[A, b]

View Python Code

import numpy as np
def GJElimination(A,b):
  n = len(A)
  G = (np.vstack([A.astype(np.float).T, b.astype(np.float)])).T
  for k in range(0,n):
    G[k] = G[k]/G[k][k]
    for i in range(k):
      G[i] = G[i] - G[i][k]*G[k]
    for i in range(k+1,n):
      G[i] = G[i] - G[i][k]*G[k]
  x = G[:,n]
  return x
A = np.array([[1, 2, 3, 5], [2, 0, 1, 4], [1, 2, 2, 5], [4, 3, 2, 2]])
b = np.array([-4, 8, 0, 10])
GJElimination(A, b)

The following link provides the MATLAB code for implementing the Gauss-Jordan Elimination Method.

MATLAB file Download

Open Educational Resources

Direct Methods: Gauss-Jordan Elimination

The Method

Lecture video

Leave a Reply Cancel reply