While solving a problem numerically, there are two sources of possible errors. First, there may be errors due to inaccurate input data. Second, there are errors caused by the algorithm itself because of used approximations made within the calculations. In order to estimate the errors in the computed answers from both these sources, we need to understand how much the solutions are changed (in this case we say that they are perturbed) if the input data are slightly perturbed.

Condition Numbers

Let us consider a linear system of equations that we write in concise form A x = b, where A is a square invertible matrix (this condition guarantees a unique solution), x is a column vector of unknowns, and b is a given column vector. Now suppose we add a small vector δb to b and consider the perturbed system A z = b + δb. This system also has a unique solution z, which we hope is not far away from x. Let δx denote the difference between z and x, so z = x + δx.

In order to quantify the size of vectors, we introduce vector norm, ∥⋅∥. It does not matter which norm you use---all norms are equivalent in finite dimensional vector spaces. We mostly will use the Euclidean norm, denoted ∥⋅∥₂. It make sense to speak about small quantity δx by using relative terms: when we say that δx is small, we mean that it is small in comparison with x. Then its size δx relative to x is given by ∥δx∥ / ∥x∥, and the size of δb is given by ∥δb∥ / ∥b∥

The equations A x = b and A(x + δx) = b + δb imply that A(δx) = δb. Since matrix A is invertible, we get δx = A⁻¹(δb). Whatever vector norm has been chosen, we can use the induced matrix norm to measure matrices. The latter equation leads to

where matrix norm is Similarly, from equation b = A x, we get the inequality ∥b∥ &leq ∥A∥ ∥x∥, which is equivalent to Multiplying these two inequalities, we obtain The latter provides a bound for ∥δx∥ / ∥x∥ in terms of ∥δb∥ / ∥b∥. The factor ∥A∥ ∥A⁻¹∥ is called the condition number of A and denoted as where This allows us to rewrite the last inequality in succinct form Till some extend, the condition number is (very roughly) the rate at which the solution x will change with respect to a change in b. From this inequality \eqref{EqCond.2}, it follows that if κ(A) is not too large, then small (relative) perturbation in the coefficient b imply small values of ∥δx∥ / ∥x∥. That is, the linear system A x = b is not overly sensitive to perturbation in input data b. As a rule of thumb, if the condition number κ(A) = 10^k, then you may lose up to k digits of accuracy on top of what would be lost to the numerical method due to loss of precision from arithmetic method.

If condition number of matrix A is not too large, then the matrix is called well-conditioned. Otherwise, a small value of ∥δb∥ / ∥b∥ does not guarantee that ∥δx∥ / ∥x∥ will be small. This means that the system A x = b is potentially very sensitive to perturbations of b. Thus, if κ(A) is large, matrix A is said to be ill-conditioned.

Proof of Theorem 1:     Example 1: Ill-conditioned matrix

Of course, the condition number depends on the choice of vector norm---they all are equivalent, so these norms differ by a nonzero constant multiple. The most appropriate for our needs is the Euclidean norm, or 2-norm inherited from Hilbert space ℓ², which leads to

where σ_max and σ_min are maximal and minimal singular values of A, respectively. Recall that the spectral norm (or 2-norm) of matrix A is Hence, when A is normal (comutes with its adjoint) or positive definite symmetric matrix, then where λ_max and λ_min are maximal and minimal (by module) eigenvalues of A, respectively. For vector 1-norm, the corresponding matrix norm (A = [𝑎_i,j]) is maximum absolute column sum Matrix norm corresponding to vector (Chebyshev) ∞-norm is maximum absolute row sum, The Frobenius norm of matrix A is

There are many different condition numbers. In general, a condition number applies not only to a particular matrix, but also to the problem being solved. For instance, let f(x) be a real-valued differentiate function of a real variable x. Suppose we are given f(x + δx) for some perturbed value of x instead of required value f(x). The best that we can do (without more information) is to try to bound the absolute error |f(x + δx) − f(x)|. We may use a simple linear approximation to f to get the estimate f(x + δx) ≈ f(x) + δx f'(x) and so the error becomes |f(x + δx) − f(x)| ≈ |δx| ⋅ |f′(x)|. We call |f′(x)| the absolute condition number of f at x. If |f′(x)| is large enough, then the error may be large even if δx is small; in this case, we call f ill-conditioned at x.

We can similarly estimate the relative error and define the relative condition number (or often just condition number for short).

The condition number κ(A) also appears in the bound for how much a change E = δA in a matrix A can affect its inverse.

 

Subsection: Exercises

 

References