Conditioning of linear systems¶

We seek to bound \(\| \mathbf \|\) in terms of \(\| \mathbf \|\) :

\[\begin\begin \mathbf\mathbf + \mathbf \mathbf &= \mathbf + \mathbf \\ \mathbf \mathbf &= \mathbf\\ \mathbf &= \mathbf^ \mathbf\\ \| \mathbf \| &\le \| \mathbf^\| \,\| \mathbf \|, \end\end\]

It is possible to show that this bound is tight, in the sense that the inequalities are in fact equalities for some choices of \(\mathbf\) and \(\mathbf\) . Motivated by the definition of the condition number as the ratio of relative changes in solution and data, we define the matrix condition number

Main result¶

The matrix condition number is equal to the condition number of solving a linear system of equations.

The matrix condition number (48) is equal to the condition number of solving a linear system of equations. Although we derived this fact only for perturbations of \(\mathbf\) , a similar statement holds when \(\mathbf\) is perturbed.

Using a traditional \(\Delta\) notation for the perturbation in a quantity, we can write the following.

in the limit \(\| \Delta \mathbf \| \to 0\) .

Note that for any induced matrix norm,

A condition number of 1 is the best we can hope for—in that case, the relative perturbation of the solution has the same size as that of the data. A condition number of size \(10^t\) indicates that in floating point arithmetic, roughly \(t\) digits are lost (i.e., become incorrect) in computing the solution \(\mathbf\) .

Residual and backward error¶

>.\]

But does a small residual mean that the error is also small? We can reconnect with (49) by the definition \(\mathbf = \tilde<\mathbf>-\mathbf\) , in which case \(\mathbf = \mathbf(\mathbf+\mathbf)-\mathbf=\mathbf\mathbf = -\mathbf\) . Hence (49) is equivalent to

(52)¶ \[ \frac-\tilde <\mathbf\|>> \|> \le \kappa(\mathbf) \frac \|> \|>.\]

When solving a linear system, all that can be expected is that the backward error, not the error, is small.

Equation (52) says that the relative error can be much larger than the relative residual when the matrix condition number is large. To put it another way: When solving a linear system, all that can be expected is that the backward error, not the error, be small.

Exercises¶

1. ⌨ A Hilbert matrix is a square matrix whose \((i,j)\) entry is \(1/(i+j-1)\) . The \(n\times n\) version \(\mathbf_n\) can be generated in Julia using

H = [ 1/(i+j-1) for i in 1:n, j in 1:n ] 

\[\frac-\tilde <\mathbf\|>> \|> \le \kappa(\mathbf) \frac \|> \|>.\]

Here \(\tilde<\mathbf>\) is a numerical approximation to the exact solution \(\mathbf\) , and \(\mathbf\) is an unknown perturbation caused by machine roundoff. We will assume that \(\| \mathbf \|/\| \mathbf \|\) is roughly of size eps() . For this problem you will need the MatrixDepot package, which can be installed and loaded via

import Pkg; Pkg.add("MatrixDepot") using MatrixDepot