Next: Order and rate of Up: Preliminaries Previous: Preliminaries

## Sensitivity and Conditioning

In numerical methods, it is important to know how reliable the numerical results produced by some algorithm are, and how sensitive the algorithm is with respect to the inevitable noise in the input variables and system parameters, due possibly to some observational error and truncation error. We need to know how sensitive the output of a given method is with respect to the various perturbations that may occur in computational process. In general, if a large difference in the output may be caused by a small change in the input, then the result is not reliable. How sensitive a problem is and whether the numerical solution is reliable or not depends on whether the problem is well behaved or ill behaved:

• If a small change in the input causes a small change in the output, the system is well conditioned or well behaved.
• If a small change in the input can cause a large change in the output, the system is ill conditioned or ill behaved.

How well or ill conditioned a system is can be measured quantitatively by the absolute or relative condition numbers:

• The absolute condition number is the upper bound of the ratio between the change in output and change in input:

• The relative condition number is the upper bound of the ratio between the relative change in output and relative change in input:

Here is the norm (representing size'') of any variable (scalar, vector, matrix, function, etc.). In the following, we will use mostly the norm for vectors and the corresponding spectral norm for matrices.

As the relative condition number compares the normalized changes in both the input and output, its value is invariant to the specific units used to measure them. Also the change in input can also be equivalently normalized by the input plus change as well as in input. The same is true for the change in the output.

Obviously, the smaller the condition number, the better conditioned the problem is, the less sensitive the solution is with respect to the perturbation of the data (error, noise, approximation, etc.); and the larger the condition number, the more ill conditioned the problem is. In the following, we specifically consider the condition numbers defined for some different systems.

System with single input and output variables

Consider a system of a single input and single output , which can be described by a function to be evaluated at a given input . The condition number of the function at point is defined as the greatest (worst case) ratio between the changes of the output and the input:

Here is the norm of the scaler variable which is either the absolute value of or modulus of . Note that in general the condition number is a function of .

When the perturbation is small, the Taylor expansion of the function can be approximated as

i.e.,

Taking the absolute value or modulus on both sides, we get

where is the absolute condition number. Dividing both sides by , we get

where is the relative condition number:

The discussion above is for the task of evaluating the output of a system as a function of the input . However, if the task is to solve a given equation , for the purpose of finding treated as the output that satisfies the equation with treated as the input, the problem needs to be converted into the form of evaluating the function at . The absolute condition number of this function is

which is the reciprocal of the absolute condition number of the corresponding evaluating problem. We therefore see that the larger , the smaller , the better conditioned the problem is.

In the figure below, , therefore for the problem of solving , is better conditioned than , but for the problem of evaluating , is more ill-conditioned than .

Example: Consider the function

• at ,

At this point, the problem of evaluating is well-conditioned.

• at ,

At this point, the function is ill-conditioned.
We see the function is well-conditioned at but ill-conditioned at .

Systems with Multiple input and output variables

The results above can be generalized to a system of multiple inputs and multiple outputs represented by a function . A change in the input will cause certain change in the output:

When is small, the output can be approximated by the first two terms of its Taylor series expansion:

and we get

where is the absolute condition number defined as:

Dividing both sides of the equation above by we get

where is the relative condition number defined as:

In particular, consider a linear system of inputs and outputs described by

• For the problem of evaluating the matrix-vector product as output given as the input, the absolute condition number is . To find the relative condition number, consider

But as

Substituting this into the expression above we get the upper bound , which is defined as the relative condition number:

Note that is no less than 1:

• For the problem of solving this linear equation system for as output, given as the input (assuming is a square matrix with for the uniqueness of the solution), we need to consider an inverse function , and get the absolute condition number .

To find the relative condition number, we note that some change in the output may be caused by perturbation in the coefficient matrix as well as in the input .

Expanding the left-hand side we get

Subtracting from the two sides we get

i.e.,

Taking norm on both sides, we get

where we have used , , and .

Substracting from both sides we get

Dividing both sides by , assuming , we get

where we have used , and .

In particular,

• if ,

• if ,

We see that for both evaluation and equation solving problems, we have . If the singular values of are , the singular values of are , and their norms can be written in terms of their greatest and smallest eigenvalues, respectively: and . Now we have

We see that the condition number of is large if its and are far apart, but it is small if otherwise.

In fact, is a measurement of how close is to singularity. When is singular, one or more of its singular values are zero, i.e., , then .

In Matlab, function cond(A,p) generates the condition number of matrix A based on its p-norm. When , this is the ratio between the greatest and smallest singular values. The following will give the same result:

• cond(A,2)
• norm(A,2)*norm(inv(A),2)
• s=svd(A), s(1)/s(n)
where n is the dimension of A.

Let us now consider the worst case scenarios for both evaluating the matrix-vector product and solving the linear equation system . (In both cases, given as the input, we find as the output.) To do so, we first carry out the SVD decomposition of to get with the singular values in sorted in descending order: . The inverse of can also be SVD decomposed: .

• The worst case for evaluating :

If is the minimum right singular vector corresponding to the smallest singular value . The equation becomes:

and

The absolute error may be small if is small, but the relative error may be large as is small when is small (e.g., close to zero).

• The worst case for solving :

If is the maximum left singular vector corresponding to the largest singular value . The equation becomes:

and

The absolute error may be small if is small, but the relative error may be large as is small when is large.

Example 1: Consider solving the linear system with

The singular values of are and , the condition number is

which is small, indicating this is a well-behaved system. Given two similar inputs and with , we find the corresponding solutions:

We have

and

Now consider a different matrix

The singular values of are and , the condition number is

indicating matrix is close to singularity, and the system is ill-conditioned. The solutions corresponding to the same two inputs and are

We can further find

and the condition number is:

We see that a small relative change in the input caused a huge change in the output (2000 times greater).

Example 2: Consider the worst case of the evaluation of with

As is almost singular, its condition number is large:

indicating problems associated with this matrix are ill-conditioned. For example, if , we get

Even for a small change in the input, causing a small change in the output:

the relative error is still large:

Example 3: Consider the worst case while solving the equation , where is the same matrix used in the previous example. If , we get

Even for a small change in the input, causing a small change in the output:

the relative error is still large:

Approximate solution

• The approximate solution corresponds to a small residual.

• The approximate solution is close to the true solution (typically unknown).
The two different criteria are consistent only if the problem is well-conditioned. If the problem is ill-conditioned, they can be very different.

Next: Order and rate of Up: Preliminaries Previous: Preliminaries
Ruye Wang 2015-02-12