Page 22 - Numerical Methods for Chemical Engineering

Elimination methods for solving linear systems 11

Gaussian elimination

We wish to develop an algorithm for solving the set of N linear equations

a 11 x 1 + a 12 x 2 +· · · + a 1N x N = b 1
a 21 x 1 + a 22 x 2 +· · · + a 2N x N = b 2
.
.
. (1.54)
a N1 x 1 + a N2 x 2 +· · · + a NN x N = b N
The basic strategy is to define a sequence of operations that converts the original system
into a simpler, but equivalent, one that may be solved easily.

Elementary row operations
We first note that we can select any two equations, say j and k, and add them to obtain
another one that is equally valid,
(a j1 x 1 + a j2 x 2 +· · · + a jN x N = b j ) + (a k1 x 1 + a k2 x 2 +· · · + a kN x N = b k )
(1.55)
(a j1 + a k1 )x 1 + (a j2 + a k2 )x 2 + ··· + (a jN + a kN )x N = (b j + b k )

If equation j is satisfied, and the equation obtained by summing j and k is satisfied, it
follows that equation k must be satisfied as well. We are thus free to replace in our system
the equation

(1.56)
a k1 x 1 + a k2 x 2 +· · · + a kN x N = b k
with

(a j1 + a k1 )x 1 + (a j2 + a k2 )x 2 + ··· + (a jN + a kN )x N = (b j + b k ) (1.57)

with no effect upon the solution x. Similarly, we can take any equation, say j, multiply it by
a nonzero scalar c, to obtain
(1.58)
ca j1 x 1 + ca j2 x 2 +· · · + ca jN x N = cb j

which we then can substitute for equation j without affecting the solution. In general, in the
linear system

a 11 x 1 + a 12 x 2 +· · · + a 1N x N = b 1
.
.
.
a j1 x 1 + a j2 x 2 +· · · + a jN x N = b j
.
.
. (1.59)
a k1 x 1 + a k2 x 2 +· · · + a kN x N = b k
.
. .
a N1 x 1 + a N2 x 2 +· · · + a NN x N = b N