Game Development Reference
In-Depth Information
for (int k = 0; k < n; k++)
m[k * n + i] -= m[k * n + j] * factor;
}
}
// Perform backward substitution.
for ( int i = n - 1; i >= 0; i--)
{
float sum = r[i];
for ( int k = i + 1; k < n; k++) sum -= m[k * n + i] * r[k];
r[i] = sum / m[i * n + i];
}
result = true ;
exit:
delete [] rowNormalizer;
return (result);
}
16.2.3 LU Decomposition
Suppose again that we have a linear system of n equations that can be written as
=
Mxr . If we can find two matrices L and U , where L is a lower triangular ma-
trix and U is an upper triangular matrix, such that
LUM , then the linear system
=
Mxr can be written as
=
(
) =
L Ux
r .
(16.12)
Mxr into the problems of
=
This transforms the problem of solving the system
Ux y . The solutions to
both of these systems is easily calculated using forward substitution (for
Lyr and then solving the system
=
=
solving the system
Lyr )
=
Ux y ).
The pair of triangular matrices L and U whose product yields M is called the
LU decomposition of M . Once determined, the LU decomposition of a matrix can
be repeatedly used to solve linear systems having the same coefficient matrix M
and different constant vectors r . In particular, we can calculate the j -th column of
1
=
and backward substitution (for
M
by setting i
r δ
=
, where δ is the Kronecker delta symbol.
ij
We need an algorithm that determines the matrices L and U such that