Condition Number, Well-Conditioned and Ill-Conditioned in Numerical Algorithms 📂Algorithm

Condition Number, Well-Conditioned and Ill-Conditioned in Numerical Algorithms

Definition

Condition Number ¹

For a problem $a$ given as input, suppose an algorithm outputs a solution $w$ as the result of the computation. The data and the solution can be measured in size with respect to a norm $\left\| \cdot \right\|$, and let $\hat{a}$ be an approximation of $a$ satisfying $\left| \hat{a} - a \right| \le \varepsilon \left| a \right|$ for some $\varepsilon > 0$. When the solution for $\hat{a}$ is $\hat{w}$, the value obtained by taking the limit superior of the ratio between the relative error and $\varepsilon$ as follows is called the condition number $\kappa = \kappa (a)$. $$ \kappa(a) = \limsup_{\varepsilon \to 0} \left\{ \frac{\left\| \hat{w} - w \right\|}{\varepsilon \left\| w \right\|} : \left\| \hat{a} - a \right\| \le \varepsilon \left\| a \right\| \right\} $$

Well-Conditioned and Ill-Conditioned

If the condition number $\kappa$ is large, it is called ill-conditioned, and if it is not large, it is called well-conditioned.

Explanation

In a rigorous sense, the condition number can be simply described as a measure of whether the error decreases well as the data approaches the true value. A large condition number means that the error hardly decreases relative to the decrease in the input error $\varepsilon$.

Meanwhile, a mathematician would wonder what the criterion is for the condition number being large or small. As can be seen from the fact that the definition does not specify it, no concrete numerical criterion is presented, and it must be considered differently for each problem. There is no dealing with things like being marginally ill-conditioned due to some threshold, because if it is ill-conditioned, it is generally a case of clearly ill-conditioned. In statistics, 15 is sometimes used as a criterion, but this too is not widely used.