9
$\begingroup$

What does numerically unstable mean when inverting a matrix and what are the mathematical conditions that cause this problem to arise?

$\endgroup$
1
  • $\begingroup$ Numerical instability with respect to matrix inversion can be controlled by the matrix's condition number. Wikipedia has an article. $\endgroup$
    – fred
    Jan 22 '16 at 16:38
9
$\begingroup$

"Stability" in numerical computation usually means that small perturbations in the data translate into small perturbation in the result, and numerical problems arise when small perturbations are introduced through the rounding error.

So consider the mapping $A \mapsto A^{-1}$, where $A$ is from the set of square invertible matrices. Stability of this operation could be measured as follows. Take a matrix norm $\|\cdot\|$. Let a matrix $E$ denote a perturbation of $A$, that is a "small" matrix; a common way to measure the stability of the inversion at $A$ would be to determine a constant $C > 0$ such that $$ \| A^{-1} - (A+E)^{-1} \| \leq C \| E \| $$ for all $E$ with $\|E\|$ sufficiently small.

Somewhat more explicitly, one can write $(A + E)^{-1} = (I + A^{-1} E)^{-1} A^{-1}$ and use the series $(I + X)^{-1} = I - X + X^2 - ...$ (ok if $X$ is small) to find $$(A + E)^{-1} = A^{-1} - A^{-1} E A^{-1} + ...$$

Therefore, $$ \| A^{-1} - (A+E)^{-1} \| \leq \| E \| \|A^{-1}\|^2 + \text{higher order terms}. $$

The condition number $$\kappa(A) := \|A\| \|A^{-1}\|$$ comes in if we consider the relative error and the relative perturbation $\|E\| / \|A\|$: $$ \frac{ \| A^{-1} - (A+E)^{-1} \| }{ \|A^{-1}\| } \leq \|A \| \|A^{-1}\| \times \frac{ \|E\| }{ \|A\| } + \text{h.o.t.} $$

In the case of the (operator norm induced by the vector) 2-norm, denoted by $\|\cdot\|_2$, the condition number is the ratio $\sigma_{\max} / \sigma_{\min}$ of the extremal singular values.

That said, "stability" often refers to an intuitive property of an algorithm / a code / ...

So as a tendency or as a rule of thumb, matrices with a large condition number ($\geq 10^{10}$, say; depends on factors such as the size and the sparsity pattern) are more difficult to invert accurately. A well-known exhibit of an ill-conditioned matrix is the "Hilbert matrix".

$\endgroup$
4
$\begingroup$

Numerical stability for linear algebra operations is usually associated with the matrix's condition number. A way of estimating the condition number is the ratio of the largest eigenvalue to the smallest eigenvalue, or the largest singular value to the smallest singular value.

What this tells you is the relative scale of the matrix. When doing Gaussian elimination, you will be dividing by some of these numbers. So if you ever divide a large number by a really small number, not only does the result get large, but you will have amplified the error as well. Thus the condition number is related to error estimates, with the larger condition number being less numerically "good".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.