Information Technology Reference
In-Depth Information
Algorithm 7.5
Solution of a Tridiagonal Linear System.
p
i
D
A
i
1;i
for
i
D
1;:::;n
q
i
D
A
i;i
for
i
D
0;:::;n
r
i
D
1
ELIMINATION TO UPPER TRIANGULAR MATRIX
:
d
0
D
A
i;i
C
1
for
i
D
0;:::;n
q
0
c
0
D
b
0
for k
1;:::;n
:
m
k
D
D
p
k
=d
k
1
d
k
D
q
k
m
k
r
k
1
m
k
c
k
1
BACK SUBSTITUTION
:
u
n
D
c
k
D
b
k
c
n
=d
n
for k
D
n
1; n
2;:::;0
:
u
k
D
.c
k
r
k
u
k
C
1
/=d
k
We can now formulate the algorithm for solving a linear system
A
u
D b
,where
A
is tridiagonal. The three diagonals of the
A
matrix are supposed to be stored as
three vectors: The diagonal is stored in q
i
, i
D
0;:::;n; the subdiagonal is stored
in p
i
, i
D
1;:::;n; and the superdiagonal is stored in r
i
, i
D
0;:::;n
1.Given
the right-hand side b
i
, i
D
0;:::;n, Algorithm
7.5
can then be used to compute the
solution
u
i
, i
D
0;:::;n.
Calling some function implementation of Algorithm
7.5
to solve for
u
i
, i
D
0;:::;n actually implies unnecessary work: Since the coefficient matrix
A
is con-
stant in time, we can perform the elimination (also known as the factorization) step
once and for all and only call the back substitution procedure at each time level.
That is, we split Algorithm
7.5
into two parts: the elimination (factorization) part
and the back-substitution part. Initially, at t
D
0, we perform the elimination and
store the vectors c
i
and d
i
. At each time level we pass c
i
and d
i
together with b
i
and
r
i
to some function implementing the back substitution algorithm. The two steps are
incorporated in Algorithm
7.6
, which is a refined version of Algorithm
7.4
.Inthe
line c, d = factorize(p, q, r ), we mean that factorize is a function that takes the p, q,
and r vectors as arguments and produces the c and d vectors as a result. A similar
notation is used in the backsubstitution step.
7.5.4
Comparing the Explicit and Implicit Methods
Let us compare the implicit Algorithm
7.6
and the explicit Algorithm
7.1
with
respect to computational efforts. The computation of the initial condition and stor-
ing new values in
u
i
are identical steps in the two algorithms, where the work is
proportional to n. The implicit algorithm needs an additional initialization step in
