Page 32 - Compact Numerical Methods For Computers

22 Compact numerical methods for computers

for an arbitrary complex number c, and
|| r + s || < || r || + || s || (2.19)
where s is a vector of the same order as r (that is, m).
Condition (2.19) is called the triangle inequality since the lengths of the sides of
a triangle satisfy this relationship. While there exist many norms, only a few are of
widespread utility, and by and large in this work only the Euclidean norm
T ½
|| r || = (r r) (2.20)
E
will be used. The superscript T denotes transposition, so the norm is a scalar. The
square of the Euclidean norm of r

(2.21)

is appropriately called the sum of squares. The least-squares solution x of (2.14) is
that set of parameters which minimises this sum of squares. In cases where
rank(A) < n this solution is not unique. However, further conditions may be
imposed upon the solution to ensure uniqueness. For instance. it may be required
that in the non-unique case, x shall be that member of the set of vectors which
T T
minimises r r which has x x a minimum also. In this case x is the unique
minimum-length least-squares solution.
T
If the minimisation of r r with respect to x is attempted directly, then using
(2.15) and elementary calculus gives
T
T
A Ax = A b (2.22)
as the set of conditions which x must satisfy. These are simply n simultaneous
linear equations in n unknowns x and are called the normal equations. Solution of
the least-squares problem via the normal equations is the most common method
by which such problems are solved. Unfortunately, there are several objections to
T
such an approach if it is not carefully executed, since the special structure of A A
and the numerical instabilities which attend its formation are ignored at the peril
of meaningless computed values for the parameters x.
Firstly, any matrix B such that
T
x Bx > 0 (2.23)
for all x 0 is called positive definite. If
T
x Bx > 0 (2.24)
for all x, B is non-negative definite or positive semidefinite. The last two terms are
T
synonymous. The matrix A A gives the quadratic form
T
T
Q = x A Ax (2.25)
for any vector x of order n. By setting
y = Ax (2.26)
T
Q = y y > 0 (2.27)