Information Technology Reference
In-Depth Information
The first and last rows are different since these correspond to the boundary condi-
tions. In case of Dirichlet conditions,
u
.0; t /
D
D
0
.t /;
u
.1; t /
D
D
1
.t /;
we get
A
0;0
D
1;
(7.127)
A
0;1
D
0;
(7.128)
A
n1;n
D
0;
(7.129)
A
n;n
D
1:
(7.130)
Similarly, we must derive the elements on the right-hand side
b
:
b
0
D
D
0
.t /;
(7.131)
b
n
D
D
1
.t /;
(7.132)
b
i
D
u
`1
C
t f
`
i
;
(7.133)
i
with i
D
1;:::;n
1.
To solve the linear system at time level `, we need to fill
A
and
b
in a program
with the expressions above and then call some Gaussian elimination routine to solve
the system. Algorithm
7.4
summarizes the details. By the notation
u
i
u
, we indi-
cate that the values of the solution vector of the linear system,
u
, are to be inserted
in the data structure holding the numerical values
u
i
at the grid points. Very often
this will be the same data structure in a program (the vector holding the solution at
the new time level).
Algorithms
7.1
and
7.4
solve the same PDE problem, but apply different numeri-
cal methods. There are more steps and more complicated operations (such as filling
matrices and solving linear systems) in Algorithm
7.4
compared with Algorithm
7.1
.
The advantage of Algorithm
7.4
is that there are no restrictions on the choice of t ,
i.e., Algorithm
7.4
is stable for any choice of t or ˛.
7.5.3
Solution of Tridiagonal Linear Systems
An important step in Algorithm
7.4
is the solution of the linear system of equations
A
u
D b
.When
A
is an .n
C
1/
.n
C
1/ matrix, a standard Gaussian elimination pro-
cedure requires on the order of n
3
operations to compute the solution. The explicit
Algorithm
7.1
involves just on the order of n operations to compute a new solution
at a new time level. That is, the implicit method will be about n
2
computationally
heavier than the explicit scheme!
Fortunately, we can reduce the work in the Gaussian elimination procedure to the
order of n. The key idea is to observe that most of the elements in
A
are zeros. In
