Tridiagonal Coefficient Matrix

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

d1

e1

0 •

0

0

y1

0

d2

e2 •

0

0

y2

uM =

0

0

d3 •

0

0

y3

0

0

0 •

dn-1

en-1

yn-

0

0

0 •

0

dn

yn

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):

+1 0

Post a comment