2 Condition numbers

The condition number of an invertible matrix $A$ is defined to be

$\kappa \left(A\right)=\parallel A\parallel \parallel A^{-1}\parallel .$

This quantity is always bigger than (or equal to) 1.

We must use the same type of norm twice on the right-hand side of the above equation. Sometimes the notation is adjusted to make it clear which norm is being used, for example if we use the infinity norm we might write

${\kappa }_{\infty }\left(A\right)=\parallel A{\parallel }_{\infty }\parallel A^{-1}{\parallel }_{\infty }.$

Example 15

Use the norm indicated to calculate the condition number of the given matrices.

1. $A=\left[\begin{array}{cc}\hfill 2\hfill & \hfill 3\hfill \\ \hfill 1\hfill & \hfill -1\hfill \end{array}\right]$ ; 1-norm.
2. $A=\left[\begin{array}{cc}\hfill 2\hfill & \hfill 3\hfill \\ \hfill 1\hfill & \hfill -1\hfill \end{array}\right]$ ; Euclidean norm.
3. $B=\left[\begin{array}{ccc}\hfill -3\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 4\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 2\hfill \end{array}\right]$ ; infinity-norm.

Solution

1. ${∥A∥}_1=\text{max}\left(2+1,3+1\right)=4$ , $$\begin{array}{rcll}{A}^{-1}& =& \frac{1}{-2-3}\left[\begin{array}{cc}\hfill -1\hfill & \hfill -3\hfill \\ \hfill -1\hfill & \hfill 2\hfill \end{array}\right]=\left[\begin{array}{cc}\hfill \frac{1}{5}\hfill & \hfill \frac{3}{5}\hfill \\ \hfill \hfill & \hfill \hfill \\ \hfill \frac{1}{5}\hfill & \hfill \frac{-2}{5}\hfill \end{array}\right]& \\ \therefore {∥A^{-1}∥}_1& =& \text{max}\left(\frac{1}{5}+\frac{1}{5},\frac{3}{5}+\frac{2}{5}\right)=1.& \end{array}$$

   Therefore ${\kappa }_1\left(A\right)=\parallel A{\parallel }_1\parallel A^{-1}{\parallel }_1=4\times 1=4.$

2. ${∥A∥}_E=\sqrt{2^2+3^2+1^2+{\left(-1\right)}^2}=\sqrt{15}$ . We can re-use $A^{-1}$ from above to see that

   ${∥A^{-1}∥}_E=\sqrt{{\left(\frac{1}{5}\right)}^2+{\left(\frac{3}{5}\right)}^2+{\left(\frac{1}{5}\right)}^2+{\left(\frac{-2}{5}\right)}^2}=\sqrt{\frac{15}{25}}.$

   Therefore ${\kappa }_E\left(A\right)=\parallel A{\parallel }_E\parallel A^{-1}{\parallel }_E=\sqrt{15}\times \sqrt{\frac{15}{25}}=\frac{15}{\sqrt{25}}=\frac{15}{5}=3.$

3. ${∥B∥}_{\infty }=\text{max}\left(3,4,2\right)=4.$

   $B^{-1}=\left[\begin{array}{ccc}\hfill -\frac{1}{3}\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill \frac{1}{4}\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill \frac{1}{2}\hfill \end{array}\right]$

   so ${∥B^{-1}∥}_{\infty }=\text{max}\left(\frac{1}{3},\frac{1}{4},\frac{1}{2}\right)=\frac{1}{2}.$ Therefore ${\kappa }_{\infty }\left(B\right)=\parallel B{\parallel }_{\infty }\parallel B^{-1}{\parallel }_{\infty }=4\times \frac{1}{2}=2.$

Task!

Calculate the condition numbers of these matrices, using the norm indicated

$A=\left[\begin{array}{cc}\hfill 2\hfill & \hfill -8\hfill \\ \hfill 3\hfill & \hfill 1\hfill \end{array}\right]\text{(1-norm)},B=\left[\begin{array}{cc}\hfill 3\hfill & \hfill 6\hfill \\ \hfill 1\hfill & \hfill 0\hfill \end{array}\right]\text{(infinity-norm)}.$

Answer

2.1 Condition numbers and conditioning

As the name might suggest, the condition number gives us information regarding how well-conditioned a problem is. Consider this example

$\left[\begin{array}{cc}\hfill 1\hfill & \hfill 10^4\hfill \\ \hfill -1\hfill & \hfill 2\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 10^4\hfill \\ \hfill 1\hfill \end{array}\right].$

It is not hard to verify that the exact solution to this problem is

$\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \end{array}\right]=\left[\begin{array}{c}\hfill \frac{10000}{10002}\hfill \\ \hfill \hfill \\ \hfill \frac{10001}{10002}\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 0.999800...\hfill \\ \hfill 0.999900...\hfill \end{array}\right]$ .

Example 16

Using the 1-norm find the condition number of $\left[\begin{array}{cc}\hfill 1\hfill & \hfill 10^4\hfill \\ \hfill -1\hfill & \hfill 2\hfill \end{array}\right]$ .

Solution

Firstly, ${∥A∥}_1=2+10^4$ . Also

$A^{-1}=\frac{1}{2+10^4}\left[\begin{array}{cc}\hfill 2\hfill & \hfill -10^4\hfill \\ \hfill 1\hfill & \hfill 1\hfill \end{array}\right]\therefore {∥A^{-1}∥}_1=\frac{1}{2+10^4}\left(1+10^4\right).$ Hence ${\kappa }_1\left(A\right)=1+10^4=10001.$

The fact that this number is large is the indication that the problem involving $A$ is an ill-conditioned one. Suppose we consider finding its solution by Gaussian elimination, using 3 significant figures throughout. Eliminating the non-zero in the bottom left corner gives

$\left[\begin{array}{cc}\hfill 1\hfill & \hfill 10^4\hfill \\ \hfill 0\hfill & \hfill 10^4\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 10^4\hfill \\ \hfill 10^4\hfill \end{array}\right].$

which implies that $x_2=1$ and $x_1=0$ . This is a poor approximation to the true solution and partial pivoting will not help. We have altered the problem by a relatively tiny amount (that is, by neglecting the fourth significant figure) and the result $\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \end{array}\right]$ has changed by a large amount. In other words the problem is ill-conditioned.

One way that systems of equations can be made better conditioned is to fix things so that all the rows have largest elements that are about the same size. In the matrix $A=\left[\begin{array}{cc}\hfill 1\hfill & \hfill 10^4\hfill \\ \hfill -1\hfill & \hfill 2\hfill \end{array}\right]$ the first row’s largest element is $10^4$ , the second row has largest element equal to 2. This is not a happy situation.

If we divide the first equation through by $10^4$ then we have

$\left[\begin{array}{cc}\hfill 10^{-4}\hfill & \hfill 1\hfill \\ \hfill -1\hfill & \hfill 2\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 1\hfill \end{array}\right]$

then the top row has largest entry equal to 1, and the bottom row still has 2 as its largest entry. These two values are of comparable size.

The solution to the system was found via pivoting (using 3 significant figures) in the Section concerning Gaussian elimination to be $x_1=x_2=1$ , a pretty good approximation to the exact values.

The matrix in this second version of the problem is much better conditioned.

Example 17

Using the 1-norm find the condition number of $\left[\begin{array}{cc}\hfill 10^{-4}\hfill & \hfill 1\hfill \\ \hfill -1\hfill & \hfill 2\hfill \end{array}\right]$ .

Solution

The 1-norm of $A$ is easily seen to be ${∥A∥}_1=3$ . We also need

$A^{-1}=\frac{1}{2\times 10^{-4}+1}\left[\begin{array}{cc}\hfill 2\hfill & \hfill -1\hfill \\ \hfill 1\hfill & \hfill 10^{-4}\hfill \end{array}\right]\therefore {∥A^{-1}∥}_1=\frac{3}{2\times 10^{-4}+1}.$

Hence

${\kappa }_1\left(A\right)=\frac{9}{2\times 10^{-4}+1}\approx 8.998$

This condition number is much smaller than the earlier value of 10001, and this shows us that the second version of the system of equations is better conditioned.

Exercises

1. Calculate the indicated norm of the following matrices
   1. $A=\left[\begin{array}{cc}\hfill 2\hfill & \hfill -2\hfill \\ \hfill 1\hfill & \hfill -3\hfill \end{array}\right]$ ; 1-norm.
   2. $A=\left[\begin{array}{cc}\hfill 2\hfill & \hfill -2\hfill \\ \hfill 1\hfill & \hfill -3\hfill \end{array}\right]$ ; infinity-norm.
   3. $B=\left[\begin{array}{cc}\hfill 2\hfill & \hfill -3\hfill \\ \hfill 1\hfill & \hfill -2\hfill \end{array}\right]$ ; Euclidean norm.
   4. $C=\left[\begin{array}{ccc}\hfill 1\hfill & \hfill -2\hfill & \hfill 3\hfill \\ \hfill 1\hfill & \hfill 5\hfill & \hfill 6\hfill \\ \hfill 2\hfill & \hfill -1\hfill & \hfill 3\hfill \end{array}\right]$ ; infinity-norm.
   5. $C=\left[\begin{array}{ccc}\hfill 1\hfill & \hfill -2\hfill & \hfill 3\hfill \\ \hfill 1\hfill & \hfill 5\hfill & \hfill 6\hfill \\ \hfill 2\hfill & \hfill -1\hfill & \hfill 3\hfill \end{array}\right]$ ; 1-norm.
2. Use the norm indicated to calculate the condition number of the given matrices.
   1. $D=\left[\begin{array}{cc}\hfill 4\hfill & \hfill -2\hfill \\ \hfill 6\hfill & \hfill 0\hfill \end{array}\right]$ ; 1-norm.
   2. $E=\left[\begin{array}{cc}\hfill -1\hfill & \hfill 5\hfill \\ \hfill 4\hfill & \hfill 2\hfill \end{array}\right]$ ; Euclidean norm.
   3. $F=\left[\begin{array}{ccc}\hfill 6\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 4\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right]$ ; infinity-norm.
3. Why is it not sensible to ask what the condition number of $\left[\begin{array}{cc}\hfill -1\hfill & \hfill 3\hfill \\ \hfill 2\hfill & \hfill -6\hfill \end{array}\right]$ is?
4. Verify that the inverse of $G=\left[\begin{array}{ccc}\hfill 2\hfill & \hfill 4\hfill & \hfill -1\hfill \\ \hfill 2\hfill & \hfill 5\hfill & \hfill 2\hfill \\ \hfill -1\hfill & \hfill -1\hfill & \hfill 1\hfill \end{array}\right]$ is $\frac{1}{5}\left[\begin{array}{ccc}\hfill -7\hfill & \hfill 3\hfill & \hfill -13\hfill \\ \hfill 4\hfill & \hfill -1\hfill & \hfill 6\hfill \\ \hfill -3\hfill & \hfill 2\hfill & \hfill -2\hfill \end{array}\right].$

   Hence find the condition number of $G$ using the 1-norm.

5. 1. Calculate the condition number (use any norm you choose) of the coefficient matrix of the system

      $\left[\begin{array}{cc}\hfill 1\hfill & \hfill 10^4\hfill \\ \hfill 2\hfill & \hfill 3\hfill \end{array}\right]\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 3\hfill \end{array}\right]$

      and hence conclude that the problem as stated is ill-conditioned.

   2. Multiply one of the equations through by a suitably chosen constant so as to make the system better conditioned. Calculate the condition number of the coefficient matrix in your new system of equations.

Answer