Page 30 - Compact Numerical Methods For Computers

20 Compact numerical methods for computers

learn theorems and proofs concerning the existence of solutions to this problem.
For the purposes of this monograph, it will suffice to outline a few basic properties
of matrices as and when required.
Consider a set of n vectors of length n, that is
a , a , . . . , a . (2.4)
2
1
n
These vectors are linearly independent if there exists no set of parameters
x , j = 1, 2, . . . , n (not all zero), such that
j
(2.5)

where 0 is the null vector having all components zero. If the vectors a are now
j
assembled to make the matrix A and are linearly independent, then it is always
possible to find an x such that (2.2) is satisfied. Other ways of stating the
condition that the columns of A are linearly independent are that A has full rank
or
rank(A) = n (2.6)
or that A is non-singular,
If only k < n of the vectors are linearly independent, then

rank(A) = k (2.7)
and A is singular. In general (2.2) cannot be solved if A is singular, though
consistent systems of equations exist where b belongs to the space spanned by
{a : j = 1, 2, . . . , n}.
j
In practice, it is useful to separate linear-equation problems into two categories.
(The same classification will, in fact, apply to all problems involving matrices.)
(i) The matrix A is of modest order with probably few zero elements (dense).
(ii) The matrix A is of high order and has most of its elements zero (sparse).
The methods presented in this monograph for large matrices do not specifically
require sparsity. The question which must be answered when computing on a small
machine is, ‘Does the matrix fit in the memory available?’
Example 2.1. Mass - spectrograph calibration
To illustrate a use for the solution of a system of linear equations, consider the
determination of the composition of a mixture of four hydrocarbons using a mass
spectrograph. Four lines will be needed in the spectrum. At these lines the
intensity for the sample will be b , i = 1, 2, 3, 4. To calibrate the instrument,
i
intensities A for the ith line using a pure sample of the jth hydrocarbon are
ij
measured. Assuming additive line intensities, the composition of the mixture is
then given by the solution x of
Ax = b.

Example 2.2. Ordinary differential equations: a two-point boundary-value problem
Large sparse sets of linear equations arise in the numerical solution of differential