SOLVE A LINEAR SYSTEM BY TRIANGULARIZATION (GAUSS) METHOD
E X P L A N A T I O N F I L E
Linear systems, AX = B, can be put in triangular form only if the determinant
of matrix A does not equal zero, that is if a solution exists.
We know that every line of A(I,J) can be replaced by a linear combination of
other lines (without changing the solution).
So it is possible by a series of linear transformations to reduce any given
linear system to an upper triangular associated linear system, this is the
Gauss elimination method.
Let us see it with an example of size N=3:
a11 x1 + a12 x2 + a13 x3 = b1 (1)
a21 x1 + a22 x2 + a23 x3 = b2 (2)
a31 x1 + a32 x2 + a33 x3 = b3 (3)
Let us multiply line (1) by a21/a11:
a21 x1 + a21/a11 a12 x2 + a21/a11 a13 x3 = a21/a11 b1 (1 bis)
By substracting line (1 bis) from line (2), we obtain a new line (2) without
the x1 term:
0 x1 + (a22 - a21/a11 a12) x2 + (a23 - a21/a11 a13) x3 = b2 - a21/a11 b1 (2 bis)
We proceed in the same way to eliminate the x1 term of the third line, and
the system becomes (in matrix notation):
| a'11 a'12 a'13 | | x1 | | b'1 |
| 0 a'22 a'23 | | x2 | = | b'2 |
| 0 a'32 a'33 | | x3 | | b'3 |
with
a'11 = a11, a'12 = a'13, a'13 = a13, b'1 = b1
a'22 = a22 - a21/a11 a12, a'23 = a23 - a21/a11 a13, b'2 = b2 - a21/a11 b1
a'32 = a32 - a31/a11 a12, a'33 = a33 - a31/a11 a13, b'3 = b3 - a31/a11 b1
Now we eliminate the x2 term of the third line in the same way: we multiply the
second line of the new system A'X = B' by a'32/a'22 and we substract this new line
from the third line, a'22, the x2 term, vanishes and our system matrix becomes an
upper triangular matrix:
| a"11 a"12 a"13 | | x1 | | b"1 |
| 0 a"22 a"23 | | x2 | = | b"2 |
| 0 0 a"33 | | x3 | | b"3 |
with
a"11 = a'11, a"12 = a'12, a"13 = a'13, b"1 = b'1
a"22 = a'22, a"23 = a'23, b"2 = b'2
a"33 = a'33 - a'32/a'22 a'23, b"3 = b'3 - a'33/a'22 b'2
Solving the linear system A"X = B" is easy.
NOTES: This is only feasible if a11 <> 0 and a'22 <>0. These particular coefficients
are called pivots. If not so, one can still permutate lines.
This algorithm destroyes the original A matrix.