Game Development Reference

In-Depth Information

that
β
is never zero, which is guaranteed to be true if the matrix
M
is diagonally

dominant. The fact that a diagonally dominant matrix is always invertible is

summarized by the following theorem.

Theorem 16.5.
Let
M
be an
nn

×

diagonally dominant tridiagonal matrix. Then

Mxr
is always solvable, and as a corollary, the matrix
M
is

=

the linear system

invertible.

Proof.
Let the entries of
M
be named as shown in Equation (16.26). Since
M
is

diagonally dominant,

bac

>+

for all
i
. We will show that the value of

β

i

i

i

given by Equation (16.32) always satisfies

β c

>

and is therefore never zero.

i

i

For

=

1

, this is trivially true since

β bc

=>

. Now assume that for any

>

1

i

i

1

1

1

that

β c

>

. For

β
, we have

i

−

1

i

−

1

c

β ba
β

i

−

1

=−

i

i

i

i

−

1

c

i

−

1

≥−

ba
β

i

i

i

−

1

c

aca
β

c

ca
β

i

−

1

>+−

i

i

i

i

−

1

i

−

1

=+

1

−

.

(16.35)

i

i

i

−

1

Since

β c

>

, the quantity

−

c β

is positive, and thus

β c

>

. By in-

1

i

−

1

i

−

1

i

−

1

i

−

1

i

i

duction, this shows that

for all
i
. Consequently, the value of each
x
can

always be calculated using Equation (16.34). The inverse of the matrix
M
can be

found by solving the system
n
times, producing the columns of

β c

>

i

i

−

1

one at a time.

M

The
j
-th column of

−

1

is found by setting
i

.

M

r δ

=

ij

Search Nedrilad ::

Custom Search