Page 31 - Numerical methods for chemical engineering

Elimination methods for solving linear systems 17

Solving triangular systems by substitution

The equations defined by A (N,N−1) x = b (N,N−1) (1.88) are

a 11 x 1 + a 12 x 2 + a 13 x 3 +· · · + a 1N x N = b 1
(2, 1) (2, 1) (2, 1) (2, 1)
a x 2 + a x 3 +· · · + a x N = b
22 23 2N 2
.
.
. (1.90)
(N−1,N−2) (N−1,N−2) (N−1,N−2)
a x N−1 + a x N = b
N−1,N−1 N−1,N N−1
(N,N−1) (N,N−1)
a N,N x N = b N
For (1.89), these equations are
x 1 + x 2 + x 3 = 4
−x 2 + x 3 =−1 (1.91)
x 3 =−8

From the last equation, we obtain immediately the last unknown,
(N,N−1) (N,N−1)
x N = b a (1.92)
N NN
For the example, x 3 =−8/1 =−8.
We then work backwards, next solving for x N−1 ,

(N−1,N−2) (N−1,N−2) (N−1,N−2)
x N−1 = b N−1 − a N−1,N x N a N−1,N−1 (1.93)
then for x N−2 ,

(N−2,N−3) (N−2,N−3) (N−2,N−3) (N−2,N−3)
x N−2 = b − a x N−1 − a a (1.94)
N−2 N−2,N−1 N−2,N x N N−2,N−2
until we obtain the values of all unknowns through this procedure of backward substitution.
For our example, we have

x 2 = [(−1) − (1)(−8)]/(−1) =−7
(1.95)
x 1 = [4 − (1)(−7) − (1)(−8)]/1 = 19

so that a solution to the example system (1.70) is

   
x 1 19
x =  x 2  =  −7  (1.96)
x 3 −8
While we have found a solution, it remains to be established that this is the only solution.

Basic algorithm for solving Ax = b by Gaussian elimination
The following algorithm transforms a linear system to upper triangular form by Gaussian
elimination: