Information Technology Reference
In-Depth Information
Algorithm 7.6
Implicit Method for the Diffusion Equation with u
.0; t /
D
D
0
.t /
and
u
.1; t /
D
D
1
.t /.
SET INITIAL CONDITION
:
u
i
D
I.x
i
/;
for i
D
0;:::;n
t =x
2
˛
D
t
0
D
0
COMPUTE CONSTANT COEFFICIENT MATRIX
:
A
i;j
D
0 for i; j
D
0; 1; : : : ; n
A
0;0
D
1
A
n;n
D
1
for i
D
1;:::;n
1
A
i;i
1
D
˛
,
A
i;i
C
1
D
˛
,
A
i;i
D
1
C
2˛
FACTORIZE MATRIX
:
c
,
d
=
factorize
(
p
,
q
,
r
)
PERFORM TIME SIMULATION
:
for `
D
1; 1; : : : ; m
t
`
D
t
`
1
C
t
FILL RIGHT
-
HAND SIDE
:
b
0
D
D
0
.t
`
/
b
n
D
D
1
.t
`
/
D
for i
1;:::;n
1
t f
`
i
SOLVE LINEAR SYSTEM
:
u=
backsubstitution
(
b
,
r
,
c
,
d
)
u
i
u
u
`
1
i
b
i
D
C
which we factor the matrix. The amount of work is proportional to n, and since we
perform the operations only once, the work is “drowned” in a long time simulation.
We therefore do not consider this part. What matters, is what we do in the time loop.
The explicit scheme contains n
C
1 calls to f.x;t/, in addition to n multiplications,
and 3.n
C
1/ additions/subtractions. We do not bother with the difference between
n
C
1 and n, and say that the work consists of n calls and 3n additions/subtractions.
The explicit scheme also has n calls to f.x;t/, n multiplications and n additions to
form the right-hand side, and n subtractions, n multiplications, and n divisions in
the back-substitution procedure.
We can conclude that the work in the explicit and implicit methods is about the
same. Which algorithm is best depends on whether we can choose a larger time step
t in the implicit algorithm and achieve the same accuracy as that produced by the
maximum time step in the explicit method. It can be shown that the errors in both
the explicit and implicit methods are of the form
C
1
x
2
C
C
2
t;
