University of Maryland College Park
Institute for Advanced Computer Studies TR{92{24
Department of Computer Science TR{2848
On the Perturbation of LU, Cholesky,
and QR Factorizations

G. W. Stewart
y
February 1992
ABSTRACT
In this paper error bounds are derived for a rst order expansion of
the LU factorization of a perturbation of the identity. The results are
applied to obtain perturbation expansions of the LU, Cholesky, and
QR factorizations.

This report is available by anonymous ftp from thales.cs.umd.edu in the directory
pub/reports.
y
Department of Computer Science and Institute for Advanced Computer Studies, University
of Maryland, College Park, MD 20742. This work was supported in part by the Air Force Oce
of Scientic Research under Contract AFOSR-87-0188 and was done while the author was a
visiting faculty member at the Institute for Mathematics and Its Applications, The University
of Minnesota, Minneapolis, MN 55455.
On the Perturbation of LU, Cholesky,
and QR Factorizations
G. W. Stewart
ABSTRACT
In this paper error bounds are derived for a rst order expansion of
the LU factorization of a perturbation of the identity. The results are
applied to obtain perturbation expansions of the LU, Cholesky, and
QR factorizations.
1. Introduction
Let A be of order n, and suppose that the leading principal submatrices of A are
nonsingular. Then A has an LU factorization
A = LU; (1:1)
where L is lower triangular U is upper triangular. The factorization is not unique;
however, any other LU factorization must have the form
A = (LD)(D
BnZr1
U);
where D is a nonsingular diagonal matrix. Thus, if the diagonal elements of L (or
U) are specied, the factorization is uniquely determined.
The purpose of this note is to establish a rst order perturbation expansion for
the LU factorization of A along with bounds on the second order terms. At least
three authors have considered the perturbation of LU, Cholesky, and QR factor-
izations [1, 2, 4]. The chief dierence between their papers and this one is that
the former treat perturbations bounds for the decompositions in question, while
here we treat the accuracy of a perturbation expansion.
Throughout this note k
k will denote a family of absolute, consistent matrix
norms; i.e.,
jAjjBj =) kAk kBk;
and
kABkkAkkBk
whenever the product AB is dened. Thus the bounds of this paper will hold for
the Frobenius norm, the 1-norm, and the 1 norm, but not for the 2-norm (for
more on these norms see [3]).
1
2 The Perturbation of Matrix Factorizations
2. Perturbation of the Identity
The heart of this note is the observation that the LU factorization of the matrix
I +F, where F is small, has a simple perturbation expansion. Specically, write
F = F
L
+F
U
;
where F
L
is strictly lower triangular and F
U
is upper triangular. Then
(I +F
L
)(I +F
U
) = I +F
L
+F
U
+F
L
F
U
= I +F +O(kFk
2
); (2:1)
and the product of the unit lowertriangular matrixI+F
L
and the upper triangular
matrix I+F
U
reproduces I+F up to terms of order kFk
2
. The following theorem
shows that we can move these lower order terms to the right-hand side of (2.1) to
get an LU factorization of I +F.
Theorem 2.1. If
kFk
1
4
then there is a strictly lower triangular matrix G
L
and an upper triangular matrix
G
U
satisfying
kG
L
+G
U
k 
kFk
2
1 BnZr2kFk+
q
1BnZr4kFk
such that
(I +F
L
+G
L
)(I +F
U
+G
U
) = I +F: (2:2)
Proof. From (2.2) it follows that the perturbations G
L
and G
U
must satisfy
G
L
+G
U
= BnZr(F
L
F
U
+F
L
G
U
+G
L
F
U
+G
L
G
U
):
Starting with G
0
L
= 0 and G
0
U
= 0, generate strictly lower triangular and upper
triangular iterates according to the formula
G
k+1
L
+G
k+1
U
= BnZr(F
L
F
U
+F
L
G
k
L
+G
k
U
F
U
+G
k
L
G
k
U
): (2:3)
Because k
k is absolute,
kG
k
L
k;kG
k
U
k kG
k
L
+G
k
U
k:
Hence if we set  = kFk, 
0
= 0, and dene the sequence f
k
g by

k+1
= 
2
+ 2
k
+
2
k
; k = 0;1;:::; (2:4)
The Perturbation of Matrix Factorizations 3
then kG
k
L
+G
k
U
k  
k
.
Now by graphing the right hand side of (2.4), it is easy to see that if  
1
4
then the sequence 
k
converges monotonically to


=

2
1 BnZr2 +
p
1 BnZr4
;
which is therefore an upper bound on kG
k
L
+ G
k
U
k for all k. It remains only to
show that the sequence G
k
L
+G
k
U
converges.
From (2.3) it follows that
(G
k+1
L
+G
k+1
U
)BnZr(G
k
L
+G
k
U
)=F
L
(G
kBnZr1
U
BnZrG
k
U
) + (G
kBnZr1
L
BnZrG
k
L
)F
U
+
(G
kBnZr1
L
BnZrG
k
L
)G
kBnZr1
U
+G
k
L
(G
kBnZr1
U
BnZrG
k
U
):
Hence,
k(G
k+1
L
+G
k+1
U
)BnZr(G
k
L
+G
k
U
)k  2( +

)k(G
k
L
+G
k
U
)BnZr(G
kBnZr1
L
+G
kBnZr1
U
)k:
If 2( + 

) < 1, which is certainly true if  
1
4
, then the series of dierences is
majorized by a geometric series, and the sequence converges.
There are some comments to be made on this theorem. In the rst place
the rst order expansion is particularly simple: split F into its lower and upper
triangular parts. We will take advantage of this simplicity in the next section,
where we will derive perturbation expansions and asymptotic bounds for the LU,
Cholesky, and QR factorization
The condition that kFk
1
4
is perhaps too constraining, since the LU factor-
ization of I +F exists provided that kFk < 1. However, as kFk approaches one,
it is possible for the factors in the decomposition to grow arbitrarily, in which case
the bounds on the second order terms must also grow. Thus the more restrictive
condition can be seen as the price we pay for bounds that do not explode.
As kFk goes to zero, the bound quickly assumes the asymptotic form
kG
L
+G
U
k
<

kFk
2
;
i.e., the order constant for the second order terms is essentially one. If we write
this in the form
kG
L
+G
U
k
kFk
<

kFk;
we see that the relative error in the rst order expansion is of the same order as
the perturbation itself, with order constant one.
4 The Perturbation of Matrix Factorizations
Finally, Theorem 2.1 treats an LU decomposition of I +F in which L is unit
lower triangular. In analyzing symmetric permutations, we may want to take
L = U
T
. In this case, we may work with slightly dierent matrices, illustrated
below for n = 3:
^
F
L
=
0
B
@
1
2
f
11
0 0
f
21
1
2
f
22
0
f
31
f
32
1
2
f
33
1
C
A
and
^
F
U
=
0
B
@
1
2
f
11
f
12
f
13
0
1
2
f
22
f
23
0 0
1
2
f
22
1
C
A
(2:5)
If
^
G
L
and
^
G
U
are dened analogously, the proof of Theorem 2.1 goes through
mutatis mutandis. For these matrices a useful inequality is
k
^
F
L
k
F
;k
^
F
U
k
F

1
p
2
kFk
F
; (2:6)
where k
k
F
denotes the Frobenius norm.
3. Applications
In this section we will apply the results of the previous section to get perturbation
expansions for the LU, the Cholesky, and the QR decompositions. We will present
only rst order terms, since bounds for the second order terms can be derived from
Theorem 2.1, and since the rate of convergence of these bounds to zero, suggests
that the rst order expansions will be satisfactory for all but the most delicate
work. We will also derive asymptotic bounds for the rst order terms.
Our rst application is to the problem we began with: the perturbation of the
LU decomposition. Let A have the LU decomposition (1.1) and let
~
A = A + E.
Then
L
BnZr1
~
AU
BnZr1
= I +L
BnZr1
EU
BnZr1
 I +F:
Let F
L
and F
U
be as in the last section. Then I + F

=
(I + F
L
)(I + F
U
) is the
rst order approximation to the LU factorization of I +F. It follows that
~
A

=
L(I +F
L
)(I +F
U
)U;
is the rst order approximation to the LU factorization of
~
A. Note that because
F
L
is unit lower triangular, this expansions preserves the scaling of the diagonal
elements of L.
By taking norms we can derive the following asymptotic perturbation bound
k
~
LBnZrLk
kLk
<

kL
BnZr1
kkU
BnZr1
kkAk
kEk
kAk
 
LU
(A)
kEk
kAk
: (3:1)
The Perturbation of Matrix Factorizations 5
Thus 
LU
(A) = kL
BnZr1
kkU
BnZr1
kkAk serves as a condition number for the LU de-
composition of A. When A is square, this number is never less than the usual
condition number (A) = kAkkA
BnZr1
k and can be much larger. Bounds on the
U factor can be derived similarly.
An unhappy aspect of the bound (3.1) is that it overestimatesthe perturbation
of the leading part of the LU factorization. Specically, if we partition
 
A
11
A
12
A
21
A
22
!
=
 
L
11
0
L
21
L
22
! 
U
11
U
12
0 U
22
!
;
then A
11
= L
11
U
11
and the condition number for this part of the factorization is

LU
(A
11
), which is in general smaller than 
LU
(A). The perturbation in L
21
, can
then be estimated from the equation L
21
= A
21
U
BnZr1
11
.
1
If A is symmetric and positive denite, then A has the Cholesky factorization
A = R
T
R;
where R is upper triangular. Let
~
A = A+ E, where E is symmetric. Setting, as
above, F = R
BnZrT
ER
BnZr1
and dening
^
F
U
as in (2.5), we have
~
R

=
(I +
^
F
U
)R:
By (2.6) and the consistency of the 2-norm with the Frobenius norm, we have
k
~
RBnZrRk
F
kRk
2
<

1
p
2
kR
BnZrT
k
2
kR
BnZr1
k
2
kEk
F
=

2
(A)
p
2
kEk
F
kAk
2
:
where 
2
(A) = kAk
2
kA
BnZr1
k
2
is the usual condition number in the 2-norm.
1
An alternative approach is to set

L =

L
11
0
L
21
I

so that

L
BnZr1

A
11
A
21

U
BnZr1
11
=

I
0

 J:
The proof of Theorem 2.1 can easily be adapted to give a bound on the perturbation of the
LU factorization of a perturbation of J and hence on the perturbation of the LU factorization
of

A
11
A
21

.
6 The Perturbation of Matrix Factorizations
Finally, let A, now rectangular, be of full column rank, and consider the
QR factorization
A = QR;
whereQhas orthonormal columnsand R is upper triangular with positive diagonal
elements. The key to the derivation of the bounds is the equation
A
T
A = R
T
R;
i.e., R is the Cholesky factor of A
T
A.
As usual, let
~
A = A + E, and let E
A
be the orthogonal projection of E onto
the column space of A. Then A
T
E = A
T
E
A
. It follows that
~
A
T
~
A

=
A
T
A+A
T
E
A
+E
T
A
A  A
T
A+F:
Hence with
^
F
U
as above, we have
~
R

=
(I +
^
F
U
)R:
In particular,
k
~
RBnZrRk
F
kRk
2
<

p
2
2
(A)
kE
A
k
F
kAk
2
;
where 
2
(A) = kRk
2
kR
BnZr1
k
2
. Since
~
Q =
~
A
~
R
BnZr1
, we have
~
Q

=
Q(I BnZr
^
F
U
) +ER
BnZr1
;
from which it follows that
k
~
QBnZrQk
F
<


2
(A)
p
2kE
A
k
F
+kEk
F
kAk
2
: (3:2)
Asymptotically, the bounds derived in this section agree with the bounds in
[1, 4], with the exception of (3.2), which is a little sharper owing to the presence
of kE
A
k
F
.
Acknowledgements. This paper has been muchimprovedby the suggestions
of Jim Demmel and Nick Higham.
The Perturbation of Matrix Factorizations 7
References
[1] A. Baarland. Perturbation bounds for the LDL
H
and the LU factorizations.
BIT, 31:341{352, 1991.
[2] G. W. Stewart. Perturbation bounds for the QR factorization of a matrix.
SIAM Journal on Numerical Analysis, 1977:509{518, 1977.
[3] G. W. Stewart and J.-G. Sun. Matrix Perturbation Theory. Academic Press,
Boston, 1990.
[4] J.-G. Sun. Perturbation bounds for the Cholesky and QR factorizations. BIT,
31:341{352, 1990.