Page 234 -

5.5. SYSTEMS OF LINEAR ALGEBRAIC EQUATIONS 201

The transformed system has the form
1
x 1 + x 2 + 2x 3 = 8,
2
x 2 – 10x 3 =–28,
x 3 = 3.
Hence, we find that
1
x 3 = 3, x 2 =–28 + 10x 3 = 2, x 1 = 8 – x 2 – 2x 3 = 1.
2
4 . Gauss-Jordan elimination of unknown quantities.
◦
This method consists of applying elementary transformations for reducing a system with
a nondegenerate basic matrix to an equivalent system with the identity matrix. On the kth
step (k = 1, 2, ... , n) the rows of the augmented matrix A obtained on the preceding step

1
can be transformed as follows:
a kj b
a = , b = k (j = k, k + 1, ... , n),

kj
k
a a
kk kk
a kj b

a = a – a ik , b = b – a ik k (i = 1, 2, ... , n, i ≠ k, j = k, k + 1, ... , n),
i
ij
i
ij
a a
kk kk
provided that the diagonal element obtained on each step is not equal to zero. After n steps,
the basic matrix is transformed to the identity matrix and the right-hand side turns into the
desired solution.
Example 3. For the linear system from Examples 1 and 2 we have
21 4 16 11/22 8 10 7 22 100 1
⎛ ⎞ ⎛ ⎞ ⎛ ⎞ ⎛ ⎞
⎝ 32 1 10 ⎠ → ⎝ 01/2 –5 –14 ⎠ → ⎝ 01 –10 –28 ⎠ → ⎝ 010 2 ⎠ ,
13 3 16 05/21 8 00 26 78 001 3
and therefore x 1 = 1, x 2 = 2, x 3 = 3.
The diagonal element obtained on some step of the above elimination procedure may
happen to be equal to zero. In this case, the formulas become more complicated and
reindexing of the unknown quantities may be required.
5 . Method of LU-decomposition.
◦
This method is based on the representation of the basic matrix A as the product of a
lower triangular matrix L and an upper triangular matrix U, i.e., in the form A = LU.This
factorization is called a triangular representation or the LU-representation of a matrix (see
also Paragraph 5.2.3-1).
Givensuchan LU-representation of the matrix A, the system AX =B can be represented
in the form LUX =B, and its solution can be obtained by solving the following two systems:
LY = B, UX = Y .

Due to the triangular structure of the matrices L ≡ [l ij ]and U ≡ [u ij ], these systems can be
solved with the help of the formulas

i–n
1
y i = b i – l ij y j (i = 1, 2, ... , n),
l ii
j=i
n

x k = y k – u ks x s (k = n, n – 1, ... , 1),
s=k+1
provided that l ii ≠ 0.