Consider the solution of Ax = b by Doolittle's decomposition, where A is the n x n tridiagonal matrix

d1 |
e1 |
0 |
0 •• |
0 | |||||||||||||||||||||||||||||||||||

C1 |
d2 |
e2 |
0 •• |
0 | |||||||||||||||||||||||||||||||||||

0 |
C2 |
d3 |
e3 • • |
0 | |||||||||||||||||||||||||||||||||||

0 |
0 |
C3 |
d4 |
As the notation implies, we are storing the nonzero elements of A in the vectors c = cn-1 d1 d2 e1 e2 en-1 The resulting saving of storage can be significant. For example, a 100 x 100 tridiagonal matrix, containing 10,000 elements, can be stored in only 99 + 100 + 99 = 298 locations, which represents a compression ratio of about 33:1. Let us now apply LU decomposition to the coefficient matrix. We reduce row k by getting rid of ck-i with the elementary operation row k <- row k - (ck-1/dk-1) x row (k - 1), k = 2, 3,..., n The corresponding change in dk is dk dk - (Ck-1/dk-1)ek-1 (2.21) whereas ek is not affected. In order to finish up with Doolittle's decomposition of the form [L\U], we store the multiplier k = ck-1 /dk-1 in the location previously occupied by Ck-1: Thus, the decomposition algorithm is for k in range(1,n): lam = c[k-1]/d[k-1] d[k] = d[k] - lam*e[k-1] c[k-1] = lam Next we look at the solution phase, that is, the solution of Ly = b, followed by Ux = y. The equations Ly = b can be portrayed by the augmented coefficient matrix C2 0 Note that the original contents of c were destroyed and replaced by the multipliers during the decomposition. The solution algorithm for y by forward substitution is y[0] = b[0] The augmented coefficient matrix representing Ux = y is
Note again that the contents of d were altered from the original values during the decomposition phase (but e was unchanged). The solution for x is obtained by back substitution using the algorithm x[n-1] = y[n-1]/d[n-1] for k in range(n-2,-1,-1): |

Was this article helpful?

## Post a comment