1.7.6. Assessment.

In the above problems the ill-conditioning was easily resolved by using more digits in the floating point numbers. A class of matrices called Hilbert matrices are notoriously ill-conditioned. The condition number of the following indicate this.

		>a:=hilbert(3);
		

		> cond(a);1

		>748

		>a:=hilbert(4);

		

		> cond(a);

		>28375

Next we will describe one of the many versions of condition number, and try to indicate why it is a measure of an ill-conditioned problem. An ill-conditioned problem generates large errors in the computed solution. Let the exact solution be x where Ax = d and let X be the computed solution where AX - d = -r is the nonzero residual. The relative error is given by the ratio of the "size" of x - X and the "size" of x. In ill-conditioned problem this ratio is large.

In order to be more precise about the "size" we define the max norm of a vector, and it is analogous to the absolute value of a single real number.

Definition. The max norm of the vector x is a real number

Basic Properties.

2. || x + y || =< || x || + || y ||.

3. || cx || = | c | || x || where c is any real number.

4. || Ax || =< || A || || x || where || A || = max [[Sigma]]_j| a_i,j |.

Example.

The proofs of the first three are a consequence of the analogous properties of the absolute value. In order to prove the fourth property, apply the definition of max norm to the matrix-vector product Ax

Let us use this notion of "size" in the analysis of the relative error. Note Ax - AX = d - d + r, and so x - X = A^-1r and x = A^-1d. Now apply property four to the last two equations. This gives the following important estimate of the relative error.

This inequality prompts the following definition of condition number of a matrix, as well as the formal statement this inequality as a condition number theorem.

Definition. The condition number of the matrix A with respect to the max norm is

Condition Number Theorem. If A is an n by n matrix, A has an inverse matrix, Ax = d and AX -d = -r , then

Example.

There are other choices for norms, and hence, condition numbers. Note the condition number theorem implies the relative error should be small provided the condition number and the r are small. It does not imply, but does suggest, that the relative error will be large when the condition number is large!

Return to Section TOC
Return to the Previous Subsection
Go to Next Subsection