Game Development Reference
In-Depth Information
By substituting into preceding rows, we obtain the general backward substitution
formula
1
n
.
x
=
r
Ur
(16.10)
i
i
ik
k
U
ii
ki
=+
1
In the remainder of this section, we examine two methods for solving general
linear systems. Each method transforms the problem into one in which triangular
systems appear. Forward and backward substitution can then be used to obtain a
solution.
16.2.2 Gaussian Elimination
Suppose we have a nonhomogeneous linear system of n equations having n un-
knowns
Mxr . By performing elementary
row operations (see Definition 3.3) on the coefficient matrix M , we can reduce
the linear system to
,
x
,
that can be written as
,
=
x
12
n
Ux
=
r ,
(16.11)
where U is an upper triangular matrix, and the new constant vector
r is the result
of performing the same row operations on r . The values of x are then calculated
using the backward substitution formula given by Equation (16.10).
The process of transforming the linear system
Mxr into the linear system
=
r is known as Gaussian elimination . For each column
=
1, 2,
, we
,
n
Ux
=
j
eliminate the entries
i M below the main diagonal by adding row j multiplied by
, we must exchange row j with anoth-
er row below it before performing the eliminations in column j . It is generally
true that the best numerical stability is achieved by exchanging rows so that the
absolute value of j M is maximized, so we search for the largest entry on or be-
low the main diagonal as we process each column. As mentioned in Chapter 3,
this is called pivoting .
Since multiplying any row of the matrix M and the corresponding entry of
the vector r by a nonzero scalar does not alter the solution to the linear system,
we can normalize each row of M so that its largest coefficient is 1
to row i for each i
. If
M
M
>
M
=
0
j
ij
jj
jj
. This im-
proves numerical stability by placing all of the rows on equal ground, avoiding
the possibility that one row dominates the others during pivoting because it has
been scaled by a large value. Normalizing the rows for this reason is called im-
plicit pivoting .
±