Matrix Condition Numbers
Nicholas John Higham · MIMS EPrints (University of Southampton) · 1983
Several properties of matrix norms and condition numbers are described. The sharpness of the norm bounds in the standard perturbation results for $Ax = b$ is investigated. For perturbations in $A$ the bounds are sharp and quite likely to be realistic. For perturbations in $b$ the usual bound is not sharp and can be unduly pessimistic; a more suitable measure of the conditioning than cond(A) is suggested. Some important concepts relating to the problem of condition estimation are discussed, careful consideration being given to the reliability and computational cost of condition estimators. The LINPACK condition estimation algorithm is described, its weaknesses, including two counter-examples, pointed out, and some observations given. Let $A$ be an $n\\times n$ tridiagonal matrix. We show that it is possible to compute $\\| A^{-1} \\|_{\\infty}$, and hence $\\mathrm{cond}_{\\infty}(A)$, in $O(n)$ operations. Several algorithms which perform this task are given. All but one of the algorithms apply to irreducible tridiagonal matrices: those having no zero elements on the subdiagonal and superdiagonal. It is shown how these algorithms may be employed in the computation of $\\| A^{-1} \\|_{\\infty}$ when $A$ is reducible. If $A$ is, in addition, positive definite then it is possible to compute $\\| A^{-1} \\|_{\\infty}$ as the $\\ell_{\\infty}$ norm of the solution to a linear system involving $A$'s comparison matrix, $M(A)$, which is also positive definite and tridiagonal. Utilising a relation between the $\\mathrm{LDL^T}$ factors of $A$ and $M(A)$ we show how the LINPACK routine SPTSL, which solves $Ax = b$ for positive definite tridiagonal matrices $A$, can be modified so that it also computes $\\mathrm{cond}_{\\infty}(A)$, the increase in computational cost being 00 approximately 60 percent