What Is a Condition Number?

A condition number of a problem measures the sensitivity of the solution to small perturbations in the input data. The condition number depends on the problem and the input data, on the norm used to measure size, and on whether perturbations are measured in an absolute or a relative sense. The problem is defined by a function, which may be known explicitly or may be only implicitly defined (as when the problem is to solve an equation).

The most well known example of a condition number is the condition number of a nonsingular square matrix A, which is \kappa(A) = \|A\| \|A^{-1}\|. More correctly, this is the condition number with respect to inversion, because a relative change to A of norm \epsilon can change A^{-1} by a relative amount as much as, but no more than, about \kappa(A)\epsilon for small \epsilon. The same quantity \kappa(A) is also the condition number for a linear system Ax = b (exactly if A is the data, but only approximately if both A and b are the data).

It is easy to see that \kappa(A) \ge 1 for any norm for which \|I\| = 1 (most common norms, but not the Frobenius norm, have this property) and that \kappa(A) tends to infinity as A tends to singularity.

A general definition of (relative) condition number, for a function f from \mathbb{R}^n to \mathbb{R}^n, is

\mathrm{cond}(f,x) = \lim_{\epsilon\to0} \displaystyle\sup_{\|\Delta x\| \le \epsilon \|x\|} \displaystyle\frac{\|f(x+\Delta x) - f(x)\|}{\epsilon\|f(x)\|}.

Taking a small, nonzero \epsilon, we have

\displaystyle\frac{\|f(x+\Delta x) - f(x)\|}{\|f(x)\|} \lesssim \mathrm{cond}(f,x) \displaystyle\frac{\|\Delta x\|}{\|x\|}

for small \|\Delta x\|, with approximate equality for some \Delta x.

An explicit expression for \mathrm{cond}(f,x) can be given in terms of the Jacobian matrix, J(x) = (\partial f_i/\partial x_j):

\mathrm{cond}(f,x) = \displaystyle\frac{ \|x\| \| J(x) \| }{ \| f(x) \|}.

We give two examples.

  • If f is a scalar function then J(x) = f'(x), so \mathrm{cond}(f,x) = |xf'(x)/f(x)|. Hence, for example, \mathrm{cond}(\log,x) = 1/|\log x|.
  • If z is a simple (non-repeated) root of the polynomial p(t) = a_n t^n + \cdots + a_1 t + a_0 then the data is the vector of coefficients a = [a_n,\dots,a_0]^T. It can be shown that the condition number of the root z is, for the \infty-norm,

    \mathrm{cond}(z,a) = \displaystyle\frac{ \max_i |a_i| \sum_{i=0}^n |z|^i } { |z p'(z)| }.

A general theory of condition numbers was developed by Rice (1966).

A problem is said to be well conditioned if the condition number is small and ill conditioned if the condition number is large. The meaning of “small” and “large” depends on the problem and the context. This diagram illustrates a well-conditioned function f: small changes in x produce small changes in f.

cond-fig-0.jpg

The next diagram depicts an ill-conditioned function f: small changes in x can produce large changes in f (but do not necessarily do so, as the closeness of f(x_2) and f(x_3) illustrates).

cond-fig-1.jpg

Here are a few key points about condition numbers.

  • Even though an explicit expression may be available for it, computing \mathrm{cond}(f,x) is usually as expensive as computing f(x), so a lot of research has focused on obtaining inexpensive estimates of the condition number or bounds for it.
  • While \kappa(A) \ge 1, it is not true for all functions that \mathrm{cond}(f,x) is bounded below by 1.
  • For a range of functions that includes the matrix inverse, matrix eigenvalues, and a root of a polynomial, it is known that the condition number is the reciprocal of the relative distance to the nearest singular problem (one with an infinite condition number).
  • As the condition number is itself a function, one can ask: What is the condition number of the condition number? For a variety of problems, including those mentioned in the previous point, the condition number of the condition number is (approximately) the condition number!

References

This is a minimal set of references, which contain further useful references within.

Related Blog Posts

This article is part of the “What Is” series, available from https://nhigham.com/category/what-is and in PDF form from the GitHub repository https://github.com/higham/what-is.

5 thoughts on “What Is a Condition Number?”

  1. Thank you for your “What is” blog.

    As far as I understand, the usual way to compute the condition number for the matrix A is to take the ratio of the largest to the smallest singular value of A. How is this related to “the reciprocal of the relative distance to the nearest singular problem”?

    One more question: if A is the diagonal matrix with 1 and 1e-10 on its diagonal, A’s condition number is 1e10, but the bound on cond(f,x) way overestimates the error computing the solution of Ax=b. Can you comment on whether there exists a tighter estimate of the sensitivity to perturbations?

    Reply

  2. What you’re referring to is the matrix condition number with respect to inversion for the 2-norm. The reciprocal of that is the relative distance in the 2-norm to the nearest singular matrix.

    On the second point, componentwise perturbaton theory and componentwise condition numbers handle this. See Chapter 7 of my book “Accuracy and Stability of Numerical Algorithms”.

    Reply

    1. What is the nearest singular matrix of [1 0; 0 1/2]? Is there an explicit formula for its computation?

      Reply

  3. Dear Sir!
    Thank you so much for your blog. Using the condition number cond$(f,x)$ of the function $f$ at $x$ , we can find the bound for relative forward error $\frac{\|f(x+\Delta x)-f(x)\|}{\|f(x)\|}$ if the backward error $\Delta x$ belongs to some neighborhood $N(x)$ of $x$. In genearl we don’t know the size of $N(x)$. Let $\Delta x$ be a backward error of an approximated solution $f(x+\Delta x)$. How can one check that $\Delta x$ belongs to $N(x)$ or not ?

    Thank you,
    Kannan R.

    Reply

    1. his isn’t normally a problem. If the backward error is so large that a perturbation expansion is not valid then that usually means we have a very poor approximate solution. In any case, there is often a computable expression for \Delta x and so we can check its size

      Reply

Leave a comment