next up previous index
Next: Example Program Up: Other Matrix Operations Previous: Other Matrix Operations

Gauss-Jordan Elimination

Consider the following equation:

\begin{displaymath}\boldsymbol{A}\cdot\boldsymbol{x} = \boldsymbol{b}
\end{displaymath} (5.1)

The equation can be solved as follows:
1.
divide the first row by A11, so that the new A11 becomes 1
2.
subtract from the second row A2i the first row multiplied by A21, so that after that subtraction A21 becomes 0
3.
subtract from the third row A3i the first row multiplied by A31, so that after that subtraction A31 becomes 0
4.
$\ldots$
5.
subtract from the $n^{\textrm{{\scriptsize th}}}$ row Ani the first row multiplied by An1, so that after that subtraction An1 becomes 0. Now the first column of matrix A is

\begin{displaymath}\left(
\begin{array}{c}
1 \\
0 \\
0 \\
\vdots \\
0
\end{array} \right)
\end{displaymath}

6.
divide the second row by A22, so that the new A22 becomes 1
7.
subtract from the first row A1i the second row multiplied by A12, so that after that subtraction A12 becomes 0
8.
subtract from the third row A3i the second row multiplied by A32, so that after that subtraction A32 becomes 0
9.
subtract from the fourth row A4i the second row multiplied by A42, so that after that subtraction A42 becomes 0
10.
$\ldots$
11.
subtract from the $n^{\textrm{{\scriptsize th}}}$ row Ani the second row multiplied by An2, so that after that subtraction An2 becomes 0. Now the first two columns of matrix A

\begin{displaymath}\left(
\begin{array}{cc}
1 & 0 \\
0 & 1 \\
0 & 0 \\
\vdots & \vdots \\
0 & 0
\end{array} \right)
\end{displaymath}

12.
$\ldots$
At the same time matching operations must be performed on vector b.

When the process is finished we get the following new equation

\begin{displaymath}\left(
\begin{array}{ccccc}
1 & 0 & 0 & \cdots & 0 \\
0 &...
...1 \\
b_2 \\
b_3 \\
\vdots \\
b_n
\end{array} \right)
\end{displaymath} (5.2)

The coefficients bi are quite different now, but the equation can be solved trivially. And so, we get:

xn = bn (5.3)

In matrix notation the operations performed on A amount to having found such matrix A-1 that

\begin{displaymath}\boldsymbol{A}^{-1} \cdot \boldsymbol{A} \cdot \boldsymbol{x}...
...cdot\boldsymbol{x} = \boldsymbol{A}^{-1}\cdot
\boldsymbol{b}
\end{displaymath} (5.4)

Now, if during the computation we were to perform all the motions not only on vector b, but also on another matrix, which has been initialized to 1, we would end up with A-1 inside that matrix when the whole thing is over.

When these computations are carried out solutions can be found simultaneously to systems of equations with various right hand sides (but always the same left hand side A so vectors b are often aligned into a matrix, which doesn't have to be square, and that matrix is then also accompanied by a square matrix that has been initialized to 1, so as to yield A-1 as well.

Although the above comprises the heart of the method there is one complication that we have to incorporate. It may happen that a particular diagonal term Akk is zero or very small. In that case dividing whatever's left of Aki by Akk may lead to overflows. If this is the case then the solution is to interchange the rows or the columns so as to place the largest element of Aki, which is called a pivot in the Akk position, and get the small one in the pivot's old location. This is an essential part of the Gauss-Jordan Elimination technique and the program must never be written without pivoting.



 
next up previous index
Next: Example Program Up: Other Matrix Operations Previous: Other Matrix Operations
Zdzislaw Meglicki
2001-02-26