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