Importance of condition number

Consider a linear system of equations

$$Ax = b$$ (1)

where A is a square matrix. Here we look at the stability of solutions of this equation, and we will see that in some cases it is very important to be aware of how things can go wrong. By stability, we are interested in how the solution x changes when a small change or error is made in A or b (data). We say that the solution is stable if a small error in the data leads to a small error in the solution. The following example illustrates the point:

$$\left[ \begin{array}{rr} 1000 & 999 \\ 999 & 998 \end{array... ...t] = \left[ \begin{array}{c} 1999 \\ 1997 \end{array} \right]$$

The exact solution of this equation is

$$x = \left[ \begin{array}{c} 1 \\ 1 \end{array} \right]$$

Now consider the perturbed system

$$\left[ \begin{array}{rr} 1000 & 999 \\ 999 & 998 \end{array... ...left[ \begin{array}{c} 1998.99 \\ 1997.01 \end{array} \right]$$

where the right handside has been perturbed by an order of 0.0005%, and the exact solution to this equation is

$$\hat{x} = \left[ \begin{array}{r} 20.97 \\ -18.99 \end{array} \right]$$

By any reckoning the perturbation in the solution cannot be considered to be small (It is of the order of 2000%). So what went wrong ?

Let us first derive some relationship between the perturbation of the data and resulting change in the solution. As in the example above, consider a perturbation of the RHS, ie., we now consider the equation

$$A( x + \delta x) = b + \delta b \Longrightarrow \ \delta x = A^{-1} \delta b$$ (2)

and using some suitable norms we get

$$\vert\vert \delta x \vert\vert \le \vert\vert A^{-1} \vert\vert \cdot \vert\vert \delta b \vert\vert$$ (3)

Also since

$$\vert\vert b \vert\vert = \vert\vert Ax \vert\vert \le \vert... ...le \vert\vert A \vert\vert \frac{1}{ \vert\vert b \vert\vert }$$

Multiplying the previous two equations we get

$$\frac{ \vert\vert \delta x \vert\vert }{ \vert\vert x \vert\... ...c{ \vert\vert \delta b \vert\vert }{ \vert\vert b \vert\vert }$$ (4)

This equation gives an upper limit to the error in the solution in terms of the error/perturbation in the data. What makes this important is that the inequality is strict, i.e., there exist b and $\delta b$ for which equality holds. The quantity

$$\kappa(A) = \vert\vert A \vert\vert \cdot \vert\vert A^{-1} \vert\vert$$ (5)

is called the condition number of matrix A. If a matrix has a large condition number then there is a possibility that even a small error in the data can lead to a large error in the solution (Can this be called chaos ? sensitive dependence on data). For the example considered we calculate the condition number in two different vector norms: Since

$$A^{-1} = \left[ \begin{array}{rr} -998 & 999 \\ 999 & -1000 \end{array} \right]$$

$$\vert\vert A \vert\vert _\infty = \vert\vert A \vert\vert _1... ...ert A^{1} \vert\vert _\infty = \vert\vert A^{-1} \vert\vert _1$$

thus giving

$$\kappa_\infty(A) = \kappa_1(A) = (1999)^2 \approx 4 \times 10^6$$

According to the condition number the maximum error that can be expected is

$$0.0005 \times 4 \times 10^6 = 2000\%$$

which agrees with what we have got.

The inaccuracies in the data will always be present because all measurements are finite and because all computers have a finite precision. Hence it is important to be on guard whenever solving ill-conditioned equations.

Geometric picture of ill-conditioning
We again write the numeral example as a set of two equations

$$\begin{eqnarray*} 1000 x_1 + 999 x_2 &=& b_1 \\ 999 x_1 + 998 x_2 &=& b_2 \end{eqnarray*}$$

These two equations represent straight lines in 2-D and the solution is the point where they intersect. The slopes of the equations are

$$m_1 = -\frac{1000}{999} = -1.001001, m_2 = - \frac{999}{998} = -1.001002$$

which indicates that the two lines are close to being parallel as shown in figure.

Now for some value of the RHS the lines intersect at P as shown in figure. If one of the RHS values is perturbed slightly, which just causes that particular line to be shifted parallel to itself (dashed line in figure) the new intersection point Q is seen to be shifted considerably wrt the original solution. Thus ill-conditioning is a result of the fact that the equations are nearly linearly dependent.

Ill conditioning by poor scaling
Consider the system of equations

$$\left[ \begin{array}{rr} 1 & 0 \\ 0 & \epsilon \end{array} ... ...] = \left[ \begin{array}{c} 1 \\ \epsilon \end{array} \right]$$

where $\epsilon \ll 1$ and has condition numbers

$$\kappa_1 = \kappa_2 = \kappa_\infty = 1/\epsilon \gg 1$$

making the above equation ill-conditioned. If we divide the second equation throughout by $\epsilon$ then we get

$$\left[ \begin{array}{rr} 1 & 0 \\ 0 & 1 \end{array} \right]... ... \right] = \left[ \begin{array}{c} 1 \\ 1 \end{array} \right]$$

which is clearly well conditioned. Thus ill-conditioning can arise due to bad scaling.

For further discussions on this topic I recommend the following reference,

Fundamentals of Matrix Computations, by David S Watkins, section 2.3, John Wiley and Sons, 1991.