Information Technology Reference
In-Depth Information
Algorithm 7.4
Implicit Method for the Diffusion Equation with u
.0; t /
D
u
.1; t /
D
0
.
SET INITIAL CONDITION
:
u
i
D
I.x
i
/;
for
i
D
0;:::;n
t =x
2
˛
D
t
0
D
0
for `
1; 1; : : : ; m
t
`
D
D
t
FILL MATRIX AND RIGHT
-
HAND SIDE
:
A
i;j
D
t
`
1
C
0
for
i; j
D
0; 1; : : : ; n
A
0;0
D
1
A
n;n
D
1
b
0
D
D
0
.t
`
/
b
n
D
1
.t
`
/
for i
D
1;:::;n
1
A
i;i
1
D
D
˛
,
A
i;i
C
1
D
˛
,
A
i;i
D
1
C
2˛
t f
`
i
solve the linear system
A
u
u
`
1
i
b
i
D
C
D b
wrt.
u
u
i
u
fact, there are at most three entries in each row that can be different from zero. It
is possible to utilize this fact in the Gaussian elimination procedure and construct
a much more efficient solution algorithm. This algorithm works with the nonzero
elements in
A
only.
Since all entries in row number i are zero, except for the diagonal entry A
i;i
and its two “neighbors” A
i;i1
and A
i;iC1
, we realize that the nonzero entries in
A
appear on the diagonal, the subdiagonal and the superdiagonal, see (7.123). We say
that the coefficient matrix
A
has a
tridiagonal
structure and that
A
is tridiagonal.
Obviously, it suffices to store the three diagonals only in the computer's mem-
ory. This can save much memory compared with storing the complete matrix with
.n
C
1/
2
entries. But even more important is the fact that we can reduce work in
solving
A
u
D b
from the order of n
3
to the order of n.
To derive a tailored Gaussian elimination algorithm for tridiagonal matrices, we
take a look at (7.123). Imagine that we start the standard Gaussian elimination proce-
dure.
18
We first eliminate A
i;0
from i
D
1;:::;n. However, we know that A
i;0
D
0
for i
D
2;:::;n, so it suffices to eliminate A
1;0
only. For a general column num-
ber k, we just eliminate A
i;iC1
, and note that the rest of the column is zero, i.e.,
A
i;k
D
0 for k
D
i
C
2;:::;n.
After having turned
A
into an upper triangular form by the Gaussian elimina-
tion procedure, we find
u
from the so-called back substitution. In addition, in this
process, we can work with the nonzeroes only of the upper triangular matrix.
18
We assume that you know this procedure, but if not, you can just accept the end result of this
section: Algorithm
7.5
.
