We recall from Section 4 of STEP 12 that the solutions of ill-conditioned systems of linear equations are very sensitive to small changes in their coefficients and constants. We will show now how one may test a system for ill-conditioning.
One of the most common tests for ill-conditioning of a linear system involves the norm of the coefficient matrix. In order to define this quantity, we must consider first the concept of the norm of a vector or matrix, which in some way assesses the size of their elements.
Let x and y be vectors. Then a vector norm ||·|| is a real number with the properties:
There are many possible ways to choose a vector norm with these properties. One vector norm which is probably familiar to the student is the Euclidean or 2-norm. Thus, if x is an n ´ 1 vector, then the 2-norm is denoted and defined by
As an example, if x is the 5 x 1 vector with the components x1 = 1, x2 = -3, x3 = 4, x4 = -6, x5 = 2, then
.
Another possible choice of norm, which is more suitable for our purposes here, is the infinity norm, defined by
.
Thus, we find for the vector in the previous
example 
. It is easily verified that 
has the three
properties above. For 
, the first two properties are readily
verified; the triangle
inequality is somewhat more
difficult and requires the use of the so-called Cauchy-Schwarz
inequality (for example, cf. Cheney
and Kincaid ( 1994)).
The defining properties of a matrix norm are similar, except that it involves an additional property. Let A and M be matrices. Then a matrix norm || · || is a real number with the properties:
1. 
is a matrix with all elements zero;
2. 
3. 
As for vector norms, there are many ways of choosing matrix norms with the four properties above, but we will consider only the infinity norm. If A is an n´n matrix, then the infinity norm is defined by
By this definition, this norm is the maximum of the sums obtained by adding the absolute values of the elements in each row, whence it is commonly referred to as the maximum row sum norm
. As an example, let
.
Then
so that 
A useful property interrelating the matrix and vector infinity norms is
which follows from Property 4 of the matrix norms above.
We will now find out whether or not a system is ill-conditioned by using the condition number of the coefficient matrix. If A is an n x n matrix and A-1 is its inverse, then the condition number of A is defined by
It is bounded below by 1, since || I ||¥ = 1 and
,
where we have used the matrix norm property 4 given in the preceding section. Large values of the condition number usually indicate ill-conditioning. As a justification for this last statement, we state and prove the theorem:
Theorem: Suppose x satisfies the linear
system Ax = b and 
satisfies the linear system 
. Then
Proof: We have 
. Since
,
we see that
.
However, since b = Ax, we have 
, or
.
It then follows that
from which follows the result above.
It is seen from the theorem that even if the
difference between b and 
is small, the change in
the solution, as measured by the `relative error' 
may
be large when the condition
number is large. It follows that a
large condition number is an indication of possible ill-conditioning of a system. A similar theorem for the case when there are small
changes to the coefficients of A may be found in more
advanced texts such as Atkinson (1993). Such a theorem also shows
that a large condition
number is an indicator of ill-conditioning.
There arises the question: How large has the condition number to be for ill-conditioning to become a problem? Roughly speaking, if the condition number is 1m and the machine in use to solve a linear system has kD accuracy, then the solution of the linear system will be accurate to k - m decimal digits.
In Step 12, we had the coefficient matrix
which was associated with an ill-conditioned system. Then
and
This suggests that a numerical solution would not be very accurate, if only 2D accuracy were used in the calculations. Indeed, if the components of A were rounded to two decimal digits, the two rows of A would be identical. Then the determinant of A would be zero, and it follows from the theorem in Step 11 that this system would not have a unique solution.
We recall that the definition of the condition number requires A-1, the computation of
which is expensive. Moreover, even if the inverse were
calculated, this approximation might not be very accurate, if the
system is ill-conditioned. It is therefore common in software
packages to estimate the condition number by obtaining an
estimate of 
, without explicitly finding A-1.
1. For the 5 x 1 vector with elements x1
= 4, x2 = -6, x3 = -5, x4
= 1, and x5 = -1, calculate 
.
2. For each of the matrices in Exercise 1 of Step 14, compute
a. the infinity norm,
b. the condition number.
.
