Computing

166 ◾ Computing

en, instead of solving Ax = b, we have LUx = b, which can now be com-

puted in two steps. First, using forward substitution, we obtain a vectory,

where Ly = b, and next we use backward substitution to get x, where Ux = y.

In both cases, i.e., solving for y and then for x, the computations are per-

formed in O(n

2

) steps (See Chapter 26). Of course, the initial decomposi-

tion of A into LU itself does require O(n

3

) steps, which is also the running

time of Gaussian elimination. It is easy to see that if we need to solve Ax =

b multiple times for dierent b’s, then the LU decomposition approach is

computationally more ecient than a repeated use of Gaussian elimina-

tion. Several methods can be used to perform the actual fac ...