Let's manually find the solution to the following simultaneous linear algebraic equations Ax=b by Gaussian elimination. For the purpose of understanding the underlying computer algorithm, it is important to work systematically as a computer would.
x2 + 2 x3 = 0 (1.1)
4 x1 + x2 = 1 (1.2)
x1 + 2 x2 + 3 x3 = 0 (1.3)
Re-write missing coefficients explicitly with 1 and missing terms with 0.
0 x1 + 1 x2 + 2 x3 = 0 (1.1)
4 x1 + 1 x2 + 0 x3 = 1 (1.2)
1 x1 + 2 x2 + 3 x3 = 0 (1.3)
Pivoting: swap 1st & 2nd eqn, because eqn (1.2) has the largest leading coefficient:
4 x1 + 1 x2 + 0 x3 = 1 (1.2)
0 x1 + 1 x2 + 2 x3 = 0 (1.1)
1 x1 + 2 x2 + 3 x3 = 0 (1.3)
* (1.2) by 0/4 & subtract it from (1.1) --> (2.2)
* (1.2) by 1/4 & subtract it from (1.3) --> (2.3)
4 x1 + 1 x2 + 0 x3 = 1 (2.1)
0 x1 + 1 x2 + 2 x3 = 0 (2.2)
0 x1 + 7/4 x2 + 3 x3 = -1/4 (2.3)
Pivoting: swap 2nd & 3rd eqn:
4 x1 + 1 x2 + 0 x3 = 1 (2.1)
0 x1 + 7/4 x2 + 3 x3 = -1/4 (2.3)
0 x1 + 1 x2 + 2 x3 = 0 (2.2)
* (2.3) by 1/(7/4) & subtract it from (2.2) --> (3.3)
4 x1 + 1 x2 + 0 x3 = 1 (3.1)
0 x1 + 7/4 x2 + 3 x3 = -1/4 (3.2)
0 x1 + 0 x2 +2/7 x3 = 1/7 (3.3)
* (3.3) by 3/(2/7) & subtract it from (3.2) --> (4.2)
* (3.3) by 0/(2/7) & subtract it from (3.1) --> (4.1)
4 x1 + 1 x2 + 0 x3 = 1 (4.1)
0 x1 + 7/4 x2 + 0 x3 = -7/4 (4.2)
0 x1 + 0 x2 +2/7 x3 = 1/7 (4.3)
* (4.2) by 1/(7/4) & subtract it from (4.1) --> (5.1)
4 x1 + 0 x2 + 0 x3 = 2 (5.1)
0 x1 + 7/4 x2 + 0 x3 = -7/4 (5.2)
0 x1 + 0 x2 +2/7 x3 = 1/7 (5.3)
divide each eqn by the non-zero coefficient
1 x1 + 0 x2 + 0 x3 = 1/2 (6.1)
0 x1 + 1 x2 + 0 x3 = -1 (6.2)
0 x1 + 0 x2 + 1 x3 = 1/2 (6.3)
The answer is :
x1 = 0.5
x2 = -1
x3 = 0.5
Matrix A:
| 0 1 2 |
| 4 1 0 |
| 1 2 3 |
The vector b for this problem is:
Vector b:
| 0 |
| 1 |
| 0 |
Repeat the process in matrix-vector notation.
Original matrix-vector: | A | b |
| 0 1 2 | 0 | (1.1)
| 4 1 0 | 1 | (1.2)
| 1 2 3 | 0 | (1.3)
Pivoting: swap 1st & 2nd row, because eqn (1.2) has the largest leading coefficient:
| 4 1 0 | 1 | (1.2)
| 0 1 2 | 0 | (1.1)
| 1 2 3 | 0 | (1.3)
* (1.2) by 0/4 & subtract it from (1.1) --> (2.2)
* (1.2) by 1/4 & subtract it from (1.3) --> (2.3)
| 4 1 0 | 1 | (2.1)
| 0 1 2 | 0 | (2.2)
| 0 7/4 3 | -1/4 | (2.3)
Pivoting: swap 2nd & 3rd row:
| 4 1 0 | 1 | (2.1)
| 0 7/4 3 | -1/4 | (2.3)
| 0 1 2 | 0 | (2.2)
* (2.3) by 1/(7/4) & subtract it from (2.2) --> (3.3)
| 4 1 0 | 1 | (3.1)
| 0 7/4 3 | -1/4 | (3.2)
| 0 0 2/7 | 1/7 | (3.3)
* (3.3) by 3/(2/7) & subtract it from (3.2) --> (4.2)
* (3.3) by 0/(2/7) & subtract it from (3.1) --> (4.1)
| 4 1 0 | 1 | (4.1)
| 0 7/4 0 | -7/4 | (4.2)
| 0 0 2/7 | 1/7 | (4.3)
* (4.2) by 1/(7/4) & subtract it from (4.1) --> (5.1)
| 4 0 0 | 2 | (5.1)
| 0 7/4 0 | -7/4 | (5.2)
| 0 0 2/7 | 1/7 | (5.3)
divide each row by the diagonal element
| 1 0 0 | 1/2 | (6.1)
| 0 1 0 | -1 | (6.2)
| 0 0 1 | 1/2 | (6.3)
The answer is given by the new vector b on the RHS:
x1 = 1/2
x2 = -1
x3 = 1/2
Original matrix: | A | I |
| 0 1 2 | 1 0 0 | (1.1)
| 4 1 0 | 0 1 0 | (1.2)
| 1 2 3 | 0 0 1 | (1.3)
Pivoting: swap 1st & 2nd row, because eqn (1.2) has the largest leading coefficient:
| 4 1 0 | 0 1 0 | (1.2)
| 0 1 2 | 1 0 0 | (1.1)
| 1 2 3 | 0 0 1 | (1.3)
* (1.2) by 0/4 & subtract it from (1.1) --> (2.2)
* (1.2) by 1/4 & subtract it from (1.3) --> (2.3)
| 4 1 0 | 0 1 0 | (2.1)
| 0 1 2 | 1 0 0 | (2.2)
| 0 7/4 3 | 0 -1/4 1 | (2.3)
Pivoting: swap 2nd & 3rd row:
| 4 1 0 | 0 1 0 | (2.1)
| 0 7/4 3 | 0 -1/4 1 | (2.3)
| 0 1 2 | 1 0 0 | (2.2)
* (2.3) by 1/(7/4) & subtract it from (2.2) --> (3.3)
| 4 1 0 | 0 1 0 | (3.1)
| 0 7/4 3 | 0 -1/4 1 | (3.2)
| 0 0 2/7 | 1 1/7 -4/7| (3.3)
* (3.3) by 3/(2/7) & subtract it from (3.2) --> (4.2)
* (3.3) by 0/(2/7) & subtract it from (3.1) --> (4.1)
| 4 1 0 | 0 1 0 | (4.1)
| 0 7/4 0 |-21/2 -7/4 7 | (4.2)
| 0 0 2/7 | 1 1/7 -4/7| (4.3)
* (4.2) by 1/(7/4) & subtract it from (4.1) --> (5.1)
| 4 0 0 | 6 2 -4 | (5.1)
| 0 7/4 0 |-21/2 -7/4 7 | (5.2)
| 0 0 2/7 | 1 1/7 -4/7| (5.3)
divide each row by the diagonal element
| 1 0 0 | 3/2 1/2 -1 | (6.1)
| 0 1 0 | -6 -1 4 | (6.2)
| 0 0 1 |7/2 1/2 -2 | (6.3)
The inverse matrix (A-1) is:
| 1.5 0.5 -1 |
| -6 -1 4 |
| 3.5 0.5 -2 |
Note that the linear equation and the inverse problem do not need
to be solved separately. In particular, since the b
vector is the same as the second column of the identity matrix
I, the answer to the linear equation is given by the
second column of A-1
x1=0.5
x2=-1
x3=0.5
Lets work on another problem.
x2 + 2 x3 = 1
3 x1 + 4 x2 + 5 x3 = 2
8 x1 + 6 x2 + 6 x3 = 3
The matrix A is:
| 0 1 2 |
| 3 4 5 |
| 8 6 6 |
The vector b is:
| 1 |
| 2 |
| 3 |
Given the matrix A and vector b above, we wish to
find both the solution to the algebraic equations and inverse
A-1.
Write Ax=b with only the coefficients: | A | b |
| 0 1 2 | 1 |
| 3 4 5 | 2 |
| 8 6 6 | 3 |
Finding inverse of A is the same as finding the solution to
the linear system of equations represented by: Ax=I, where I is
the identity matrix.
Write Ax=I with only the coefficients: | A | I |
| 0 1 2 | 1 0 0 |
| 3 4 5 | 0 1 0 |
| 8 6 6 | 0 0 1 |
Since matrix A is the same in both cases, we can solve both Ax=b
and Ax=I simultaneously by combining them together:
Original matrix: | A | b | I |
| 0 1 2 | 1 | 1 0 0 | (1.1)
| 3 4 5 | 2 | 0 1 0 | (1.2)
| 8 6 6 | 3 | 0 0 1 | (1.3)
Pivoting: swap 1st & 3rd row, because the 3rd row has the largest coefficient in the 1st column.
| 8 6 6 | 3 | 0 0 1 | (1.1)
| 3 4 5 | 2 | 0 1 0 | (1.2)
| 0 1 2 | 1 | 1 0 0 | (1.3)
* (1.1) by 3/8 & subtract it from (1.2) --> (2.2)
* (1.1) by 0/8 & subtract it from (1.3) --> (2.3)
| 8 6 6 | 3 | 0 0 1 | (2.1)
| 0 7/4 11/4 | 7/8 | 0 1 -3/8 | (2.2)
| 0 1 2 | 1 | 1 0 0 | (2.3)
Pivoting: no need to swap, because the 2nd row already has the largest coefficient in the 2nd column.
| 8 6 6 | 3 | 0 0 1 | (2.1)
| 0 7/4 11/4 | 7/8 | 0 1 -3/8 | (2.2)
| 0 1 2 | 1 | 1 0 0 | (2.3)
* (2.2) by 1/(7/4) & subtract it from (2.3) --> (3.3)
| 8 6 6 | 3 | 0 0 1 | (3.1)
| 0 7/4 11/4 | 7/8 | 0 1 -3/8 | (3.2)
| 0 0 3/7 | 1/2 | 1 -4/7 3/14 | (3.3)
Now, reverse the elimination process backward.
* (3.3) by (11/4)/(3/7) & subtract it from (3.2) --> (4.2)
* (3.3) by 6/(3/7) & subtract it from (3.1) --> (4.1)
| 8 6 0 | -4 | -14 8 -2 | (4.1)
| 0 7/4 0 |-7/3 | -77/12 14/3 -7/4 | (4.2)
| 0 0 3/7 | 1/2 | 1 -4/7 3/14 | (4.3)
* (4.2) by 6/(7/4) & subtract it from (4.1) --> (5.1)
| 8 0 0 | 4 | 8 -8 4 | (5.1)
| 0 7/4 0 |-7/3 | -77/12 14/3 -7/4 | (5.2)
| 0 0 3/7 | 1/2 | 1 -4/7 3/14 | (5.3)
Divide each row by the diagonal element
| 1 0 0 | 1/2 | 1 -1 1/2| (6.1)
| 0 1 0 |-4/3 | -11/3 8/3 -1 | (6.2)
| 0 0 1 | 7/6 | 7/3 -4/3 1/2| (6.3)
Thus, the second part gives the answer to the linear equation.
x1=1/2
x2=-4/3
x3=7/6
And the third part is the inverse matrix (A-1):
| 1 -1 1/2|
| -11/3 8/3 -1 |
| 7/3 -4/3 1/2|
|
