Page 153 - Matrices theory and applications

8
Matrix Factorizations

The direct solution (by Cramer’s method) of a linear system Mx = b,
n
where M ∈ GL n (k)(b ∈ k ) is computationally expensive, especially if
one wishes to solve the system many times with various values of b.In the
next chapter we shall study iterative methods for the case k = IR or CC.
Here we concentrate on a simple idea: To decompose M as a product PQ
in such a way that the resolution of the intermediate systems Py = b and
Qx = y is “cheap.” In general, at least one of the matrices is triangular.
For example, if P is lower triangular (p ij =0 if i< j), then its diagonal
entries p ii are nonzero, and one may solve the system Py = b step by step:

b 1
= ,
y 1
p 11
.
.
.
b i − p i1 y 1 − ··· − p i,i−1 y i−1
y i = ,
p ii
.
.
.
b n − p n1 y 1 − ··· − p n,n−1y n−1
= .
y n
p nn
The computation of y i needs 2i−1 operations and the final result is obtained
2
in n operations. This is not expensive if one notes that computing the
product x = M −1 b (assuming that M −1 is computed once and for all, an
2
expensive task) needs 2n − n operations.