Perturbation Analyses for the QR Factorization.
This paper gives perturbation analyses for $Q_1$ and $R$ in the QR factorization $A=Q_1R$, $Q_1^TQ_1=I$ for a given real $m\times n$ matrix $A$ of rank $n$ and general perturbations in $A$ which are sufficiently small in norm. The analyses more accurately reflect the sensitivity of the problem than previous such results. The condition numbers here are altered by any column pivoting used in $AP=Q_1R$, and the condition number for $R$ is bounded for a fixed $n$ when the standard column pivoting strategy is used. This strategy also tends to improve the condition of $Q_1$, so the computed $Q_1$ and $R$ will probably both have greatest accuracy when we use the standard column pivoting strategy.First-order perturbation analyses are given for both $Q_1$ and $R$. It is seen that the analysis for $R$ may be approached in two ways---a detailed "matrix--vector equation" analysis which provides a tight bound and corresponding condition number, which unfortunately is costly to compute and not very intuitive, and a simpler "matrix equation" analysis which provides results that are usually weaker but easier to interpret and which allows the efficient computation of satisfactory estimates for the actual condition number. These approaches are powerful general tools and appear to be applicable to the perturbation analysis of any matrix factorization.
Introduction
. The QR factorization is an important tool in matrix computations
(see for example [4]): given an m \Theta n real matrix A with full column rank,
there exists a unique m \Theta n real matrix Q 1 with orthonormal columns, and a unique
nonsingular upper triangular n \Theta n real matrix R with positive diagonal entries such
that
The matrix Q 1 is referred to as the orthogonal factor, and R the triangular factor.
Suppose tG has the unique QR factorization
differentiate R(t) T with respect to t and set
which with given A and G is a linear equation for the upper triangular matrix -
R(0).
determines the sensitivity of R(t) at and so the core of any perturbation
analysis for the QR factorization effectively involves the use of (1.1) to determine
bound -
R(0). There are essentially two main ways of approaching this problem. We
now discuss these, together with some very recent history.
Xiao-Wen Chang [1, 2, 3] was the first to realize that most of the published results
on the sensitivity of factorizations, such as LU, Cholesky, and QR, were extremely
School of Computer Science, McGill University, Montreal, Quebec, Canada, H3A 2A7,
(chang@cs.mcgill.ca), (chris@cs.mcgill.ca). The research of the first two authors was supported by
NSERC of Canada Grant OGP0009236.
y Department of Computer Science and Institute for Advanced Computer Studies, University of
Maryland, College Park, MD 20742, U.S.A., (stewart@cs.umd.edu). G. W. Stewart's research was
supported in part by the US National Science Foundation under grant CCR 95503126.
G. W. STEWART
weak for many matrices. He originated a general approach to obtaining provably tight
results and sharp condition numbers for these problems. We will call this the "matrix-
vector equation" approach. For the QR factorization this involves expressing (1.1) as
a matrix-vector equation of the form
where WR and ZR are matrices involving the elements of R, and vec(\Delta) transforms its
argument into a vector of its elements. The notation uvec(\Delta) denotes a variant of vec(\Delta)
defined in Section 5.2. Chang also realized that the condition of many such problems
was significantly improved by pivoting, and provided the first firmly based theoretical
explanations as to why this was so.
G. W. Stewart [11, 3] was stimulated by Chang's work to understand this more
deeply, and present simple explanations for what was going on. Before Chang's work,
the most used approach to perturbation analyses of factorizations was what we will
call the "matrix equation" approach, which keeps equations like (1.1) in their matrix-matrix
form. Stewart [11] (also see [3]) used an elegant construct, partly illustrated by
the "up" and "low" notation in Section 2, which makes the matrix equation approach
a far more usable and intuitive tool. He combined this with deep insights on scaling
to produce new matrix equation analyses which are appealingly clear, and provide
excellent insight into the sensitivities of the problems. These new matrix equation
analyses do not in general provide tight results like the matrix-vector equation analyses
do, but they are usually more simple, and provide practical estimates for the true
condition numbers obtained from the latter.
It was the third author, Chris Paige, who insisted on writing this brief history,
and delineating these exceptional contributions of Chang and Stewart. It requires a
combination of the two analyses to provide a full understanding of the cases we have
examined. The interplay of the two approaches was first revealed in [3], and we hope
to convey it even more clearly here for the QR factorization.
The perturbation analysis for the QR factorization has been considered by several
authors. The first norm-based result for R was presented by Stewart [9]. That was
further modified and improved by Sun [13]. Using different approaches Sun [13] and
Stewart [10] gave first order normwise perturbation analyses for R. A first order
componentwise perturbation analysis for R has been given by Zha [17], and a strict
componentwise analysis for R has been given by Sun [14]. These papers also gave
analyses for Q 1 . More recently Sun [15] gave strict perturbation bounds for Q 1 alone.
The purpose of this paper is to establish new first order perturbation bounds
which are generally sharper than the equivalent results for the R factor in [10, 13],
and more straightforward than the sharp result in [15] for the Q 1 factor.
In Section 2 we define some notation and give a result we will use throughout the
paper. In Section 3 we will survey important key results on the sensitivity of R and Q 1 .
In Section 4 we give a refined perturbation analysis for showing in a simple way
why the standard column pivoting strategy for A can be beneficial for certain aspects
of the sensitivity of Q 1 . In Section 5 we analyze the perturbation in R, first by
the straightforward matrix equation approach, then by the more detailed and tighter
matrix-vector equation approach. We give numerical results and suggest practical
condition estimators in Section 6, and summarize and comment on our findings in
Section 7.
PERTURBATION ANALYSES FOR THE QR FACTORIZATION 3
2. Notation and basics. To simplify the presentation, for any n \Theta n matrix X,
we define the upper and lower triangular matrices
so that up(X). For general X
For symmetric X
F \Gamma2
To illustrate a basic use of "up", we show that for any given n \Theta n nonsingular upper
triangular R and any given n \Theta n symmetric M , the equation of the form (cf. (1.1))
always has a unique upper triangular solution U . Since UR \Gamma1 is upper triangular in
we see immediately that
so UR \Gamma1 and therefore U is uniquely defined. We will describe other uses later.
Our perturbation bounds will be tighter if we bound separately the perturbations
along the columns space of A and along its orthogonal complement. Thus we introduce
the following notation. For real m \Theta n A, let P 1 be the orthogonal projector onto R(A),
and P 2 be the orthogonal projector onto R(A) ? . For real m \Theta n \DeltaA define
so
2 . When ffl ? 0 in (2.5) we also define
so for the QR factorization
We will use the following standard result.
Lemma 2.1. For real m \Theta n A with rank n, real
is the orthogonal projector onto R(A).
4 XIAO-WEN CHANG, CHRIS PAIGE AND G. W. STEWART
Proof. Let A have the QR factorization
which necessarily has full column rank if kQ T
(A), the smallest singular
value of A. But this inequality is just (2.8). 2
Corollary 2.2. If nonzero \DeltaA satisfies (2.8), then for ffl and G defined in (2.5)
and (2.6), A + tG has full column rank and therefore a unique QR factorization for
all jtj - ffl. 2
3. Previous norm-based results. In this section we summarize the strongest
norm-based results by previous authors. We first give a derivation of what is essentially
Sun's [13] and Stewart's [10] first order normwise perturbation result for R, since their
techniques and results will be useful later.
Theorem 3.1. [13]. Let A 2 R m\Thetan be of full column rank, with the QR factorization
be a real m \Theta n matrix.
has a unique QR
factorization
where
Proof. Let G j \DeltaA=ffl (if the theorem is trivial). From Corollary 2.2 A+tG
has the unique QR factorization
for all jtj - ffl, where
Notice that
It is easy to verify that Q 1 (t) and R(t) are twice continuously differentiable for
ffl from the algorithm for the QR factorization. Thus as in (1.1) we have
which (see (2.4)) is a linear equation uniquely defining the elements of -
in terms
of the elements of Q T
G. From upper triangular -
R(0)R \Gamma1 in
we see with (2.1) that
PERTURBATION ANALYSES FOR THE QR FACTORIZATION 5
so with (2.3)
and since from (2.5) to (2.7) kQ T
The Taylor expansion for R(t) about
so that
which, combined with (3.8), gives (3.2). 2
This proof shows that the key point in deriving a first order perturbation bound
for R is the use of (3.5) to give a good bound on the sensitivity k -
we obtained the bounds directly from (3.7), this was a "matrix equation" analysis.
We now show how a recent perturbation result for Q 1 given by Sun [15] can be
obtained in the present setting, since the analysis can easily be extended to obtain a
more refined result in a simple way. Note the hypotheses of the following theorem are
those of Theorem 3.1, so we can use results from the latter theorem.
Theorem 3.2. [15]. Let A 2 R m\Thetan be of full column rank, with the QR factorization
be a real m \Theta n matrix.
holds, then A + \DeltaA has a unique QR factorization
where
Proof. Let G j \DeltaA=ffl (if the theorem is trivial). From Corollary 2.2 A+tG
has the unique QR factorization A(t)
for all jtj - ffl. Differentiating these at
It follows that
so with any Q 2 such that Q
6 XIAO-WEN CHANG, CHRIS PAIGE AND G. W. STEWART
Now using (2.1), we have with (3.7) in Theorem 3.1 that
We see from this, (2.2), (3.11), and kGk from (2.7), that
F
and from the Taylor expansion for
so that k\DeltaQ 1
4. Refined analysis for Q 1 . Note since both Q 1 and are orthonormal
matrices in (3.1), and \DeltaQ 1 is small, \DeltaQ so the following analysis
assumes n ? 1. The results of Sun [15] give about as good as possible overall bounds
on the change \DeltaQ 1 in Q 1 . But by looking at how \DeltaQ 1 is distributed between
and its orthogonal complement, and following the ideas in Theorem 3.2, we are able to
obtain a result which is tight but, unlike the related tight result in [15], easy to follow.
It makes clear exactly where any ill-conditioning lies. From (3.14) with
square and orthogonal,
and the key is to bound the first term on the right separately from the second. Note
from (3.11) with (2.5) to (2.7) that
where G can be chosen to give equality here for any given A. Hence is the true
condition number for that part of \DeltaQ 1 in R(Q 2
Now for the part of \DeltaQ 1 in R(Q 1 ). We see from (3.12) that
which is skew symmetric with clearly zero diagonal. Let R j and S j denote the leading
blocks of R and S respectively, G j the matrix of the first j columns of G, and
PERTURBATION ANALYSES FOR THE QR FACTORIZATION 7
where s j has j-1 elements, then from the upper triangular form of R in (4.2)
ks
ks
F
for any R n\Gamma1 equality is obtained by taking
such that kR \GammaT
It follows that the bound is tight in
so the true condition number for that part of \DeltaQ 1 in R(Q 1 ) is not
In some problems we are mainly interested in the change in Q 1 lying in R(Q 1 ), and
this result shows its bound can be smaller than we previously thought. In particular if
A has only one small singular value, and we use the standard column pivoting strategy
in computing the QR factorization, then R n\Gamma1 will be quite well-conditioned compared
with R, and we will have kR \Gamma1
5. Perturbation analyses for R. In Section 3 we saw the key to deriving first
order perturbation bounds for R in the QR factorization of full column rank A is the
equation (3.5), which has the general form of finding (bounding) X in terms of given
R and F in the matrix equation
upper triangular, R nonsingular:
Sun [13] and Stewart [10] originally analyzed this using the matrix equation approach
to give the result in Theorem 3.1. We will now analyze it in two new ways. The
first, Stewart's [11, 3] refined matrix equation approach, gives a clear improvement on
Theorem 3.1, while the second, Chang's [2, 3] matrix-vector equation approach, gives
a further improvement still - provably tight bounds leading to the true condition
number -R (A) for R in the QR factorization of A. Both approaches provide efficient
condition estimators (see [2] for the matrix-vector equation approach), and nice results
for the special case of permutation matrix giving the standard
column pivoting, but we will only derive the matrix equation versions of these. The
tighter but more complicated matrix-vector equation analysis for the case of pivoting
is given in [2], and only the results will be quoted here.
5.1. Refined matrix equation analysis for R. Our proof of Theorem 3.1 used
(3.5) to produce the matrix equation (3.7), and derived the bounds directly from this.
We now look at this approach more closely, but at first using the general form (5.1)
to keep our thinking clear. From this we see
8 XIAO-WEN CHANG, CHRIS PAIGE AND G. W. STEWART
Let D n be the set of all n \Theta n real positive definite diagonal matrices. For any D =
R. Note that for any matrix B we have
up(BD). Hence if we define B
R
R \GammaT F T D) -
R:
With obvious notation, the upper triangular matrix
. To bound this, we use the
following result.
Lemma 5.1. For n \Theta n B and D 2 D n ,
where
1-i!j-n
Proof. Clearly
But by the Cauchy-Schwarz theorem,
We can now bound the solution X of (5.1)
Since this is true for all D 2 D n , we know that for the upper triangular solution X of
where i D is defined in (5.4). This gives the encouraging result
(5.
PERTURBATION ANALYSES FOR THE QR FACTORIZATION 9
Comparing (3.5) with (5.1), we see for the QR factorization, with (2.5) to (2.7),
Hence
and from (3.9) for a change in A we have
where from (5.11) these are never worse than the bounds in Theorem 3.1.
When we use the standard column pivoting strategy in permutation
matrix, this analysis leads to a very nice result. Here the elements of R
so r 2
nn . If D is the diagonal of R then i D - 1, and from (5.9) and
But then it follows from [6, Theorem 8.13] that
so since k -
Thus when we use the standard pivoting strategy, we see the sensitivity of R is bounded
for any n.
Remark 5.1. Clearly -ME (A) is a potential candidate for the condition number
of R in the QR factorization. From (5.9), -ME (A) depends solely on R, but it will only
be the true condition number if for any nonsingular upper triangular R we can find an
F in (5.1) giving equality in (5.8). From (5.7) this can only be true if every column
of F T lies in the space of the right singular vectors corresponding to the maximum
singular value of -
R \GammaT . Such a restriction is in general too strong for (5.6) to be made
an equality as well (see the lead up to (5.5)). However for a class of R this is possible.
If R is diagonal, we can take
and the first restriction on F
disappears. Let i and j be such that i
, so from
G. W. STEWART
So we see that, at least for diagonal R, the bounds are tight, and in this restricted case
(A) is the true condition number.
This refined matrix equation analysis shows to what extent the solution X of
(5.1), and so the sensitivity of R in the QR factorization, is dependent on the row
scaling in
R. From the term D
R \GammaT F T )D in (5.2), we saw multipliers
occurred only with j ? i. As a result we obtained i D in our bounds rather than
with equality if and only if the minimum element comes before the maximum on the
diagonal. Thus we obtained full cancellation of D \Gamma1 with D in the first term on the
right hand side of (5.2), and partial cancellation in the second.
This gives some insight as to why R in the QR factorization is less sensitive than
the earlier condition estimator
indicated. If the ill-conditioning of R is mostly
due to bad scaling of its rows, then correct choice of D in
R can give - 2 ( -
very near one. If at the same time i D is not large, then -(R; D) in (5.10) can be
much smaller than
pivoting always ensures that such
a D exists, and in fact gives (5.14). However if we do not use such pivoting, then
Remark 5.1 suggests that any relatively small earlier elements on the diagonal of R
could correspond to poor conditioning of the factorization.
We will return to -ME (A) and -(R; D) when we seek practical estimates of the
true condition number that we derive in the next section.
5.2. Matrix-vector equation analysis for R. We can now obtain provably
sharp, but less intuitive results by viewing the matrix equation (5.1) as a large matrix-vector
equation. For any matrix C n\Thetan , denote by c (i)
j the
vector of the first i elements of c j . With this, we define ("u" denotes "upper")
c (1)c (2)\Delta
c (n)
It is the vector formed by stacking the columns of the upper triangular part of C into
one long vector.
To analyze (3.5) we again consider the general form (5.1), repeated here for clarity,
upper triangular, R nonsingular:
which we saw via (2.4) has a unique upper triangular solution X. The upper and
lower triangular parts of (5.1) contain identical information, and we now write the
upper triangular part in matrix-vector, rather than matrix-matrix format. The first
j elements of the jth column of (5.15) are given by
R T
f (j)Tf (j)T\Delta
f (j)T
PERTURBATION ANALYSES FOR THE QR FACTORIZATION 11
and by rewriting this, we can see how to solve for x (j)
(R T
r (1)T
r (j \Gamma1)T
(R T
r (j)T
r (j)T
which, on dividing the last row of this by 2, gives
2 \Theta n(n+1)
r 11
and ZR 2 R n(n+1)
r 11
Since R is nonsingular, WR is also, and from (5.16)
R ZR vec(F
Remembering X is upper triangular, we see
R ZR vec(F )k 2
where for any nonsingular upper triangular R, equality can be obtained by choosing
vec(F ) to lie in the space spanned by the right singular vectors corresponding to the
G. W. STEWART
largest singular value of W \Gamma1
R ZR . It follows that (5.18) is tight, so from (5.8), derived
from the matrix equation approach, and (5.11)
Remark 5.2. Usually the first and second inequalities are strict. For exam-
ple, let
. Then we
solving an optimization
problem). But from Remark 5.1 the first inequality becomes an equality if R
is diagonal, while the second also becomes an equality if R is an n \Theta n identity matrix
with so the upper bound is tight.
The structure of WR and ZR reveals that each column of WR is one of the columns
of ZR , and so W \Gamma1
R ZR has an n(n + 1)=2 square identity submatrix, giving
Remark 5.3. This lower bound is approximately tight for any n, as can be seen
by taking for by taking
and (5.10), we see from Remark 5.1 that
These results, and the analysis in Section 4 for Q 1 , lead to our new first order
normwise perturbation theorem.
Theorem 5.2. Let
be the QR factorization of A 2 R m\Thetan
with full column rank, and let \DeltaA be a real m \Theta n matrix.
holds, then there is a
unique QR factorization
such that
where with WR and ZR as in (5.16), and -ME (A) as in (5.9) and (5.10),
and
where
PERTURBATION ANALYSES FOR THE QR FACTORIZATION 13
Proof. From Corollary 2.2 A+ \DeltaA has the unique QR factorization (5.22). From
(3.5), (5.15), (5.17) with G j \DeltaA=ffl and (2.5) we have
R ZR vec(Q T
so taking the 2-norm gives
Combining this with
and
Thus, from the Taylor series (3.9) of R(t), (5.23) follows. The remaining results are
restatements of (5.20), (5.19), (4.1) and (4.3). 2
Remark 5.4. From (5.24) we know the first order perturbation bound (5.23) is
at least as sharp as (3.2), but it suggests it may be considerably sharper. In fact it can
be sharper by an arbitrary factor. Consider the example in Remark 5.3, where taking
and
We see the first order perturbation bound (3.2) can severely overestimate the effect of
a perturbation in A.
Remark 5.5. If we take
which is close to the upper bound
This shows that relatively
small early diagonal elements of R cause poor condition, and suggests if we do not
use pivoting, then there is a significant chance that the condition of the problem will
approach its upper bound, at least for randomly chosen matrices.
When we use standard pivoting, we see from (5.24) and (5.14)
but the following tighter result is shown in [2, Th. 2.2]
Theorem 5.3. Let A 2 R m\Thetan be of full column rank, with the QR factorization
when the standard column pivoting strategy is used. Then
14 XIAO-WEN CHANG, CHRIS PAIGE AND G. W. STEWART
There is a parametrized family of matrices A('), ' 2 (0; -=2]; for which
R ZR
Theorem 5.3 shows that when the standard column pivoting strategy is used, -R (AP )
is bounded for fixed n no matter how large is. Many numerical experiments
with this strategy suggest that -R (AP ) is usually close to its lower bound of one, but
we give an extreme example in Section 6 where it is not.
When we do not use pivoting, we have no such simple result for -R (A), and it
is, as far as we can see, unreasonably expensive to compute or approximate -R (A)
directly with the usual approach. Fortunately -ME (A) is apparently an excellent
approximation to -R (A), and -ME (A) is quite easy to estimate. All we need to do
is choose a suitable D in -(R; D) in (5.10). We consider how to do this in the next
section.
6. Numerical experiments and condition estimators. In Section 5 we presented
new first order perturbation bounds for the R factor of the QR factorization
using two different approaches, defined
R ZR k 2 as the true condition
number for the R factor, and suggested -R (A) could be estimated in practice by
-(R; D). Our new first order results are sharper than previous results for R, and at
least as sharp for Q 1 , and we give some numerical tests to illustrate both this, and
possible estimators for -R (A).
We would like to choose D such that -(R; D) is a good approximation to the
in (5.9), and show that this is a good estimate of the true condition
number -R (A). Then a procedure for obtaining an O(n 2 ) condition estimator for R
in the QR factorization (i.e. an estimator for -R (A)), is to choose such a D, use a
standard condition estimator (see for example [5]) to estimate - 2 (D \Gamma1 R), and take
-(R; D) in (5.10) as the appropriate estimate.
By a well known result of van der Sluis [16], - 2 (D \Gamma1 R) will be nearly minimal
when the rows of D \Gamma1 R are equilibrated. But this could lead to a large i D in (5.10).
There are three obvious possibilities for D. The first one is choosing D to equilibrate
R precisely. Specifically, take
n. The second one is
choosing D to equilibrate R as far as possible while keeping i D - 1. Specifically,
take
n. The third one is choosing Computations show that the third
choice can sometimes cause unnecessarily large estimates, so we will not give any
results for that choice. We specify the diagonal matrix D obtained by the first method
and the second method by D 1 and D 2 respectively in the following.
We give three sets of examples. The first set of matrices are n \Theta n Pascal matrices,
(with elements a 15. The results are
shown in Table 6.1 without pivoting, giving and in Table 6.2 with pivoting,
giving
~
R. Note in Table 6.1 how
can be far worse than the true
condition number -R (A), which itself can be much greater than its lower bound of
1. In

Table

6.2 pivoting is seen to give a significant improvement on -R (A), bringing
very close to its lower bound, but of course
still. Also
we observe from Table 6.1 that both -(R; D 1 ) and -(R; D 2 ) are very good estimates for
-R (A). The latter is a little better than the former. In Table 6.2 -( ~
(in fact are also good estimates for -R (AP ).
PERTURBATION ANALYSES FOR THE QR FACTORIZATION 15

Table
Results for Pascal matrices without pivoting,
7 6.6572e+02 4.4665e+03 4.2021e+03 2.1759e+05 2.1120e+06
8 2.4916e+03 1.8274e+04 1.6675e+04 2.7562e+06 2.9197e+07
9 9.4091e+03 7.4364e+04 6.6391e+04 3.6040e+07 4.1123e+08
2.0190e+06 1.9782e+07 1.6614e+07 1.2819e+12 1.8226e+13
14 7.7958e+06 7.9545e+07 6.6157e+07 1.8183e+13 2.6979e+14

Table
Results for Pascal matrices with pivoting,
~
R
3 1.2892e+00 2.1648e+00 2.1648e+00 1.2541e+01 8.7658e+01
6 2.2296e+00 4.7281e+00 4.7281e+00 7.5426e+03 1.5668e+05
7 2.0543e+00 5.1140e+00 5.1140e+00 8.4696e+04 2.1120e+06
8 2.6264e+00 6.5487e+00 6.5487e+00 1.1777e+06 2.9197e+07
9 3.4892e+00 8.8383e+00 8.8383e+00 1.4573e+07 4.1123e+08
14 3.6106e+00 1.2386e+01 1.2386e+01 5.3554e+12 2.6979e+14
The second set of matrices are 10 \Theta 8 A j , which are all obtained
from the same random 10 \Theta 8 matrix (produced by the MATLAB function randn), but
with its jth column multiplied by 10 \Gamma8 to give A j . The results are shown in Table 6.3
without pivoting. All the results with pivoting are similar to that for
6.3, and so are not given here. For
(A) are both close to
their upper bound
are significantly
smaller than
these results are what we expected, since the matrix R is
ill-conditioned due to the fact that r jj is very small, but for the rows
of R are already essentially equilibrated, and we do not expect -R (A) to be much
G. W. STEWART
better than
(A). Also for the first seven cases the smallest singular value of the
leading part R n\Gamma1 is close to that of R, so that -Q 1
(A) could not be much better
than
(A). For even though R is still ill-conditioned due to the fact that
r 88 is very small, it is not at all equilibrated, and becomes well-conditioned by row
scaling. Notice at the same time i D is close to 1, so -(R; D1), -(R; D 2 ), and therefore
are much better than
(A). In this case, the smallest singular value of R
is significantly smaller than that of R n\Gamma1 . Thus -Q 1 (A), the condition number for the
change in Q 1 lying in the range of Q 1 , is spectacularly better than
(A). This is a
contrived example, but serves to emphasize the benefits of pivoting for the condition
of both Q 1 and R.

Table
pivoting
5 1.2467e+08 3.1208e+08 2.3992e+08 3.9067e+08 4.2323e+08
6 8.8237e+07 2.2252e+08 1.6584e+08 3.4710e+08 3.9061e+08
7 9.2648e+07 2.1010e+08 1.7127e+08 4.4303e+08 5.4719e+08
8 2.2580e+00 5.4735e+00 4.9152e+00 6.6109e+00 6.2096e+08
The third set of matrices are n \Theta n upper triangular
These matrices were introduced by Kahan [7]. Of course
I here, but the condition numbers depend on R only, and these are all we are
interested in. The results for are shown in Table 6.5.
Again we found D only list the results corresponding to D 1 .

Table
Results for Kahan matrices,
In all these examples we see -(R; D 1 ) and -(R; D 2 ) gave excellent estimates for
-R (A), with -(R; D 2 ) being marginally preferable. For the Kahan matrices, which
correspond to correctly pivoted A, we see that in extreme cases, with large enough n,
-R (A) can be large even with pivoting. This is about as bad a result as we can get
PERTURBATION ANALYSES FOR THE QR FACTORIZATION 17
with pivoting (it gets a bit worse as ' ! 0 in R), since the Kahan matrices are the
parameterized family mentioned in Theorem 5.3. Nevertheless -(R;
still estimate -R (A) excellently.
7. Summary and conclusion. The first order perturbation analyses presented
here show just what the sensitivity (condition) of each of Q 1 and R is in the QR
factorization of full column rank A, and in so doing provide their true condition
numbers (with respect to the measures used, and for sufficiently small \DeltaA), as well
as efficient ways of approximating these. The key norm-based condition numbers we
derived for A are:
for that part of \DeltaQ 1 in R(A) ? , see (4.1),
that part of \DeltaQ 1 in R(A), see (4.3),
R ZR k 2 for R, see Theorem 5.2,
ffl the estimate for -R (A), that is -ME (A) j inf D2Dn -(R; D),
where -(R; D) j
The condition numbers obey
for while for R
see (5.24). The numerical examples, and an analysis of the case (not given here),
suggest that -(R; D), with D chosen to equilibrate -
subject to i D - 1, gives
an excellent approximation to -R (A) in the general case. In the special case of A with
orthogonal columns, so R is diagonal, then Remark 5.1 showed by taking
For general A when we use the standard column pivoting strategy in the QR factor-
ization, we saw from (5.14) and [2] that
As a result of these analyses we see both R and in a certain sense Q 1 can be
less sensitive than was thought from previous analyses. The true condition numbers
depend on any column pivoting of A, and show that the standard pivoting strategy
often results in much less sensitive R, and sometimes leads to a much smaller possible
change of Q 1 in the range of Q 1 , for a given size of perturbation in A.
The matrix equation analysis of Section 5.1 also provides a nice analysis of an
interesting and possibly more general matrix equation (5.1).
By following the approach of Stewart [8, Th. 3.1], see also [12, Th. 2.11], it would
be straightforward, but detailed and lengthy, to extend our first order results to provide
strict perturbation bounds, as was done in [3]. We could also provide new component-wise
bounds, but we chose not to do either of these here, in order to keep the material
and the basic ideas as brief and approachable as possible. Our condition numbers and
resulting bounds are asymptotically sharp, so there is less need for strict bounds. A
new componentwise bound for R is given in [2].
G. W. STEWART

Acknowledgement

. We would like to thank Ji-guang Sun for his suggestions
and encouragement, and for providing us with draft versions of his work.



--R

PhD Thesis
A perturbation analysis for R in the QR factorization
New perturbation analyses for the Cholesky fac- torization
Matrix Computations
A survey of condition number estimation for triangular matrices
Accuracy and Stability of Numerical Algorithms

and perturbation bounds for subspaces associated with certain eigenvalue problems
Perturbation bounds for the QR factorization of a matrix
On the perturbation of LU
On the Perturbation of LU and Cholesky Factors
Matrix perturbation theory
Perturbation bounds for the Cholesky and QR factorization
Componentwise perturbation bounds for some matrix decompositions
On perturbation bounds for the QR factorization
Condition numbers and equilibration of matrices
A componentwise perturbation analysis of the QR decomposition
--TR

--CTR
Younes Chahlaoui , Kyle A. Gallivan , Paul Van Dooren, An incremental method for computing dominant singular spaces, Computational information retrieval, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
matrix equations;pivoting;condition estimation;QR factorization;perturbation analysis