Square Matrix Condition Number (and amplification factor) (numerical analysis)¶

Preface¶

We use matrix p-norm 1 and \(\infty\) here. Extra info: Matrix Norms

Definition¶

The condition number for a nonsingular square matrix \(\mathbf{A}\) with respect to a given matrix norm is defined to be

\[ \text{cond}(\mathbf{A}) = ||\mathbf{A}||\cdot ||\mathbf{A}^{-1}|| \]

By convention, \(\text{cond}(\mathbf{A}) = \infty\) if \(\mathbf{A}\) is singular.

The numerical value of the conditional number of an \(n \times n\) matrix depends on the particular norm used, but similar to vector norms, they only differ by at most a constant (dependent on \(n\)). Thus, the 1-norm and \(\infty\)-norm are equally as useful.

Another way is to say that the condition number of a matrix measures the amount of distortion of the unit sphere in the corresponding vector norm under the transformation by the matrix. The larger the condition number, the larger the distortion.

In two dimensions, for example, the unit circle in the 2-norm becomes an increasingly cigar-shaped ellipse, and with the 1-norm or oo-norm, the unit sphere is transformed from a square into an increasingly skewed parallelogram as the condition number increases.

Properties¶

For any matrix \(\mathbf{A}\), \(\text{cond}(\mathbf{A}) \geq 1\)
For the identity matrix, \(\text{cond}(\mathbf{I}) = 1\)
For any matrix \(\mathbf{A}\) and scalar \(\gamma\), \(\text{cond}(\mathbf{\gamma A}) = \text{cond}(\mathbf{A})\)
For any diagonal matrix \(\mathbf{D}= \text{diag}(d_{i}), \ \text{cond}(\mathbf{D})= (\text{max}|d_{i}|) / ()\text{min}|d_{i}|)\)

The condition number is also a measure of how close a matrix is to being singular: a matrix with a large condition number is nearly singular, whereas a matrix that has a condition number close to one is far from being singular.

Error Bounds¶

In addition to being a reliable indicator of near singularity, the condition number also provides a quantitative bound for the error in the computed solution to a linear system.

Let \(\mathbf{x}\) be the solution to a nonsingular linear system \(\mathbf{Ax=b}\). Let \(\mathbf{\hat{x}}\) be the solution to the system \(\mathbf{A\hat{x}=b + \Delta b}\). If we define \(\mathbf{\Delta x} = \mathbf{\hat{x} - x}\), then we have

\[ \mathbf{A(x + \Delta x) = b + \Delta b} \]

Because \(\mathbf{Ax=b}\), we must have it that \(\mathbf{A\Delta x=\Delta b}\), and hence \(\mathbf{\Delta x = A^{-1}\Delta b}\).

We can take the norms:

\[ ||\mathbf{b}|| = ||\mathbf{Ax}|| \leq ||\mathbf{A}|| \cdot ||\mathbf{x}|| \ \ \ \ \text{or} \ \ \ \ ||\mathbf{x}|| \geq ||\mathbf{b}|| \ / \ ||\mathbf{A}||, \]

and

\[ ||\mathbf{\Delta x}|| = ||\mathbf{A}^{-1}\mathbf{\Delta b}|| \leq ||\mathbf{A}^{-1}|| \cdot||\mathbf{\Delta b}|| . \]

We can combine these two inequalities to obtain

\[ \frac{||\mathbf{\Delta x}||}{||\mathbf{x}||} \leq ||\mathbf{A}^{-1}||\cdot||\mathbf{\Delta b}|| \frac{\mathbf{||\mathbf{A}||}}{||\mathbf{b}||} \]

Since we know \(\text{cond}(\mathbf{A}) = ||\mathbf{A}|| \cdot ||\mathbf{A}^{-1}||\)

\[ \frac{||\mathbf{\Delta x}||}{||\mathbf{x}||} \leq \text{cond}(\mathbf{A}) \frac{||\mathbf{\Delta b}||}{||\mathbf{b}||}. \]

This means that the condition number is an amplification factor that bounds the maximum relative change in the solution (\(\mathbf{x}\)) due to a given relative change in the right-hand-side vector \(\mathbf{b}\).

A similar result holds for relative changes in the entries of the matrix \(\mathbf{A}\). If \(\mathbf{Ax=b}\) and \(\mathbf{(A+E)\hat{x} = b}\), then

\[ \mathbf{\Delta x} = \mathbf{\hat{x} - x} = \mathbf{A}^{-1}(\mathbf{A\hat{x} - b})= \mathbf{-A}^{-1}\mathbf{E\hat{x}}. \]

Taking norms, we obtain the equality

\[ ||\mathbf{\Delta x}|| \leq ||\mathbf{A}^{-1}|| \cdot ||\mathbf{E}|| \cdot ||\mathbf{\hat{x}}||, \]

which, upon using the definition of \(\text{cond}(\mathbf{A})\), yields the bound

\[ \frac{||\mathbf{\Delta x}||}{|| \mathbf{x}||} \leq \text{cond}(\mathbf{A}) \frac{||\mathbf{E}||}{||\mathbf{A}||} \]

Geometric Interpretation of Amplification Factor¶

{ width="500" .center }

Visual Example¶

{ width="500" .center } { width="500" .center }

References¶

"What is a nonsingular matrix?" - Existence and Uniqueness of Matrices (and singular matrices) Vector Norms

Properties of matrix norms - Matrix Norms