In many situations we need to estimate or bound the norm of the inverse of a matrix, for example to compute an error bound or to check whether an iterative process is guaranteed to converge. This is the same problem as bounding the condition number , assuming is easy to compute or estimate. Here, we focus on triangular matrices. The bounds we derive can be applied to a general matrix if an LU or QR factorization is available.
We denote by any matrix norm, and we take the consistency condition as one of the defining properties of a matrix norm.
It will be useful to note that
and that more generally the inverse of the upper triangular matrix with
is given by
First, we consider a general matrix and let be an eigenvalue with (the spectral radius) and a corresponding eigenvector. With , where is the vector of ones, , so
which implies since . Hence
Let be a triangular matrix. Applying the latter bound to , whose eigenvalues are its diagonal entries , gives
Combining this bound with the analogous bound for gives
We note that commonly used norms satisfy , which yields another proof of (3) and (4).
For any and such that we have the lower bound . We can choose and then solve the triangular system for to obtain the lower bound. Condition number estimation techniques, which we will describe in another article, provide ways to choose that usually yield estimates of correct to within an order of magnitude.
For the -norm, we can choose and then compute by repeated triangular solves, obtaining the lower bound . This bound is simply the power method applied to .
Let be an upper triangular matrix. The upper bounds for that we will discuss depend only on the absolute values of the elements of . This limits the ability of the bounds to distinguish between well-conditioned and ill-conditioned matrices. For example, consider
The bounds for and will be the same, yet the inverses are of different sizes (the more so as the dimension increases).
Let and write
where is strictly upper triangular and hence nilpotent with . Then
Taking absolute values and using the triangle inequality gives
where the inequalities hold elementwise.
The comparison matrix associated with a general is the matrix with
It is not hard to see that is upper triangular with and so the bound (5) is
If we replace every element above the diagonal of by the most negative off-diagonal element in its row we obtain the upper triangular matrix with
Then , where , so
Finally, let , where is strictly upper triangular with every element above the diagonal equal to the maximum element of , that is,
We note that , , and are all nonsingular -matrices. We summarize the bounds.
If is a nonsingular upper triangular matrix then
We make two remarks.
- The bounds (6) are equally valid for lower triangular matrices as long as the maxima in the definitions of and are taken over columns instead of rows.
- We could equally well have written . The comparison matrix is unchanged, and (6) continues to hold as long as the maxima in the definitions of and are taken over columns rather than rows.
It follows from the theorem that
for the 1-, 2-, and -norms and the Frobenius norm. Now , , and all have nonnegative inverses, and for a matrix with nonnegative inverse we have . Hence
where the big-Oh expressions show the asymptotic cost in flops of evaluating each term by solving the relevant triangular system. As the bounds become less expensive to compute they become weaker. The quantity can be explicitly evaluated for , using . It has the same value for , and since we have
This bound is an equality for for the matrix in (1).
For the Frobenius norm, evaluating , and using , gives
For the -norm, either of (7) and (8) can be the smaller bound depending on .
For the special case of a bidiagonal matrix it is easy to show that , and so can be computed exactly in flops.
These upper bounds can be arbitrarily weak, even for a fixed , as shown by the example
As , . On the other hand, the overestimation is bounded as a function of for triangular matrices resulting from certain pivoting strategies.
Suppose the upper triangular matrix satisfies
Then, for the -, -, and -norms,
Proof. The first four inequalities are a combination of (3) and (6). The fifth inequality is obtained from the expression (7) for with .
Condition (9) is satisfied for the triangular factors from QR factorization with column pivoting and for the transpose of the unit lower triangular factors from LU factorization with any form of pivoting.
The upper bounds we have described have been derived independently by several authors, as explained by Higham (2002).
- Nicholas J. Higham, Accuracy and Stability of Numerical Algorithms, second edition, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2002. (Chapter 8.)