Page 94 - Compact Numerical Methods For Computers

Linear equations—a direct approach 83
Separating these into real and imaginary components gives the real equations
Yu – Zv = g (6.44)
Yv + Zu = h (6.45)
which is a set of linear equations (2.22) with

(6.46)

(6.47)
and

(6.48)

This is how complex systems of linear equations can be solved using real
arithmetic only. Unfortunately the repetition of the matrices Y and Z in (6.46)
2
means that for a set of equations of order n, 2n storage locations are used
unnecessarily. However, the alternative is to recode algorithms 5 and 6 to take
account of the complex arithmetic in (6.43). Bowdler et al (1966) give ALGOL
procedures to perform the Crout variant of the elimination for such systems of
equations, unfortunately again requiring double-length accumulation.

6.5. METHODS FOR SPECIAL MATRICES
The literature contains a number of methods for solving special systems of
equations. For instance, several contributions in Wilkinson and Reinsch (1971)
deal with band matrices, that is, those for which
A = 0 if | i– j | > k (6.49)
ij
for some k. Thus if k = 1, the matrix is tridiagonal. While these methods are
undoubtedly useful and save memory, I have not included them in this mono-
graph because I feel any serious user with enough special problems to warrant a
method tailored to the task is likely to find and implement one. Others may only
find too many special cases tedious or bewildering. Thus no discussion of banded
or other special forms is given, though the user should be alert to triangular forms
since it is very wasteful of effort to apply Gauss elimination to a lower-triangular
matrix when simple forward-substitution will suffice. Likewise, no treatment is
included of the various iteration methods for the systems of equations arising
from partial differential equations (see Varga 1962). It should be pointed out,
however, that the Givens’ reduction can often be organised to take advantage of
patterns of zeros in matrices. Even as it stands, algorithm 3 is quite efficient for
such problems, since very little work is done when zero elements are encountered
and no pivot interchanges are made.
The only special form which will be considered is a symmetric positive definite
matrix. Chapter 7 deals with a decomposition of such a matrix useful for solving
special sets of linear equations. Chapter 8 discusses a very compact algorithm for
inverting such a matrix in situ, that is, on top of itself.