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
.

±

Search Nedrilad ::

Custom Search