The Lack of Influence of the Right-Hand Side on the Accuracy of Linear System Solution.
It is commonly believed that a fortunate right-hand side b can significantly reduce the sensitivity of a system of linear equations Ax=b. We show, both theoretically and experimentally, that this is not true when the system is solved (in floating point arithmetic) with Gaussian elimination or the QR factorization: the error bounds essentially do not depend on b, and the error itself seems to depend only weakly on b.  Our error bounds are exact (rather than first-order); they are tight; and they are stronger than the bound of Chan and Foulser.We also present computable lower and upper bounds for the relative error. The lower bound gives rise to a stopping criterion for iterative methods that is better than the relative residual.  This is because the relative residual can be much larger, and it may be impossible to reduce it to a desired tolerance.
Introduction
. When a system of linear equations solved numeri-
cally, the accuracy of the computed solution generally depends on the sensitivity of
the linear system to perturbations. In this paper we examine how the right-hand side
b affects the sensitivity of the linear system and the error estimates.
Suppose the matrix A is non-singular and b 6= 0, so x 6= 0. Then the accuracy of a
computed solution -
x can be determined from the norm-wise relative error
xk=kxk.
This error is often estimated from an upper bound of the form
xk=kxk - condition number   backward error:
The 'backward error', very informally, reflects the accuracy of the input data A and
b, and how well the computed solution -
x solves the linear system
is in contrast to the 'forward error'
xk=kxk, which reflects the accuracy of the
output.) The condition number is interpreted as a measure for the sensitivity of the
linear system because it amplifies the inaccuracy of the input. The condition number
in most error bounds depends only on A but not b.
A stable, accurate linear system solver, such as Gaussian elimination with partial
pivoting or the QR factorization, usually produces a backward error that is proportional
to, among other factors, the product of the machine precision ffl mach and a
slowly growing function of the matrix size n. For instance, in IEEE single precision
the backward error cannot be smaller than 10 \Gamma7 because the
y Department of Mathematics, North Carolina State University, Box 8205, Raleigh, NC 27695-
8205, USA (jmbanocz@unity.ncsu.edu). The research of this author was supported in part by NSF
grant DMS-9321938.
x Operations Research Program, North Carolina State University, Box 7913, Raleigh, NC 27695-
7913, USA (njchiu@eos.ncsu.edu).
z Department of Mathematics, North Carolina State University, Box 8205, Raleigh, NC 27695-
8205, USA (ehcho@eos.ncsu.edu).
- Center for Research in Scientific Computation, Department of Mathematics, North Carolina
State University, Box 8205, Raleigh, NC 27695-8205, USA (ipsen@math.ncsu.edu). The research of
this author was supported in part by NSF grant CCR-9400921.
J.M. BANOCZI, N. CHIU, G.E. CHO, I.C.F. IPSEN
data A and b cannot be represented more accurately. For a linear system with condition
number of about 10 7 , the above error bound is on the order of one. In this case
we should be prepared to expect a complete loss of accuracy in at least one component
of - x.
In this paper we assume that solved by a general-purpose linear system
solver: Gaussian elimination with partial pivoting or the QR factorization. Excluding
from consideration special-purpose linear system solvers designed to exploit structure
in the matrix, such as the fast sine solvers considered in [5]; or Toeplitz, Cauchy
or Vandermonde solvers [4] relieves us from assuming additional properties of the
backward error.
The question we are trying to answer is whether the error bound depends on
properties of the right-hand side b. Why is this important? Of course, the influence
of b is important when the linear system is ill-conditioned (i.e. when the condition
number is on the order of 1=ffl mach ). If a fortunate right-hand side could decrease the
condition number, then the error may decrease. This means the computed solution
associated with a fortunate right-hand side is more accurate than one associated with
an unfortunate right-hand side.
But the influence of b is also important for general linear systems as they become
large, because condition numbers usually grow with n. Although a large linear system
may look well-conditioned because the condition number is merely a small multiple
of n, it may be ill-conditioned on our machine because the condition number is on
the order of 1=ffl mach . According to the above error bound, the matrix size n must
be significantly smaller than 1=ffl mach if - x is to have any accuracy at all. But if
a fortunate right-hand side could make the condition number very small, then this
soothing effect would become more pronounced as n increases. This implies that we
could solve linear systems with fortunate right-hand sides that are much larger than
systems with unfortunate right-hand sides.
The paper is organised as follows. Section 2 starts with exact (rather than first-
residual bounds on the relative error. The condition number in the upper bound
is much smaller for some right-hand sides than for others. However, the backward
error depends on the condition number. Therefore it is difficult to say anything
about the product of condition number and backward error. Section 3 shows that
the error bound as a whole does not depend on b. We express the bound in terms of
an alternative condition number and backward error that are also independent of b.
Section 4 presents a computable, a posteriori version of the error bound; and x5 uses
this bound to evaluate stopping criteria for iterative methods. Section 6 expresses
the error bound in terms of a third backward error, because this error is the basis for
another popular stopping criterion. Section 7 presents Chan and Foulser's 'effective
condition number', and shows that it is weaker than our condition number from x2.
Section 8 shows that the relative error does not behave like the error bound, because
it appears to be weakly dependent on b. After the conclusion in x9, Appendix A
briefly discusses how the numerical experiments were carried out.
2. Dependence on the Right-Hand Side. We present a residual bound for
the relative error that contains a condition number dependent on the right-hand
side. This condition number can be significantly smaller than the traditional matrix
condition number.
Let A be a n \Theta n non-singular, complex matrix and b 6= 0 be a n \Theta 1 complex
vector. Then the system of linear equations has the exact solution x 6= 0. We
measure the accuracy of a computed solution - x by means of the norm-wise relative
RIGHT-HAND SIDE AND CONDITIONING OF LINEAR SYSTEMS 3
error
xk=kxk, where k \Delta k is a p-norm. The relative error can be bounded in terms
of the residual
as follows [11, Theorem 7.2]:kAk
krk
xk
krk
These are exact, as opposed to first-order, bounds. Although the bounds to follow
in x2 and x3 represent different interpretations, they are all identical to (2.1).
2.1. Interpretation of the Bounds. Writing
shows that -
x is the solution to a linear system with perturbed right-hand side. Thus,
we compensate for the error in -
x by changing the right-hand side. Expressing (2.1)
in terms of the corresponding backward error krk=kbk gives [16, Theorem III.2.13]:
krk
kbk
krk
where
is the traditional matrix condition
is a condition number that depends on the right-hand side. In particular, -(A; b) is
invariant under scalar multiplication of b, but it does depend on the direction of b:
For instance, consider the case when b is a multiple of a left singular vector u k of A.
If oe k is a corresponding singular value and v k a corresponding right singular vector
(see x7), i.e.
then the two-norm version of -(A; b) equals
Thus, a right-hand side b lying along a singular vector with a small oe k has a smaller
condition number than a b lying along a singular vector with a large oe k . In general,
when then there are right-hand sides b for which -(A; b) is significantly
smaller than -(A).
4 J.M. BANOCZI, N. CHIU, G.E. CHO, I.C.F. IPSEN
The bounds on -(A; b) imply the traditional residual bounds for the relative error
[15, Theorem 4.3]:-(A)
krk
kbk
xk
krk
If the error in -
x can be attributed solely to input perturbations of the right-hand side
then krk=kbk reflects the accuracy of the input data and it is an appropriate measure
for the size of these perturbations. Hence there are right-hand sides for which the
bounds (2.2) are tighter than the traditional bounds (2.4). Therefore the error bounds
depend on b; and a fortunate right-hand side can reduce the sensitivity of the linear
system and increase the accuracy.
2.2. Related Work. The potentially soothing effect of the right-hand side has
been known for some time.
In the context of special-purpose linear system solvers designed to exploit structure
in a matrix, a fortunate right-hand side can significantly reduce the sensitivity
of the linear system. This is the case, for instance, when A is a triangular M-matrix,
all components of b are non-negative and solved by backsubstitution [9,
Theorem 3.5]; or when A is a Vandermonde matrix derived from real, non-negative
points arranged in increasing order, the elements of b alternate in sign, and
is solved by the Bj-orck-Pereyra algorithm [8, x3]. A component-wise infinity-norm
version 1 of -(A; b),
is introduced in [4, x4] to explain the high relative accuracy of certain algorithms
for solving linear systems whose matrix is a totally-positive Cauchy or Vandermonde
matrix.
In the context of general purpose algorithms, the situation is not as clear due to
the lack of hard results. For instance, when
k. In this case Stewart says: 'the solution of the system reflects the
condition of A' [16, p 126]; and 'a problem that reflects the condition of A is insensitive
to perturbations in b, even if -(A) is large' [15, p 194].
Chan and Foulser [5] define an 'effective condition number' [5, Theorem 1] that is
small when b is related to A in a special way. They conclude that for appropriate right-hand
sides 'the sensitivity of x can be substantially smaller than that predicted by
(However, in x7 we show that the effective condition number is
never smaller than -(A; b) and can, in fact, be much larger than -(A).) In the context
of linear systems arising from a boundary collocation method for solving Laplace's
equation on a two-dimensional domain, Christiansen and Hansen [7] confirm that 'the
ordinary condition number is orders of magnitude larger than the effective condition
Thus there is evidence that a fortunate right-hand side may be able to reduce
the sensitivity of a linear system to perturbations in the right-hand side. Can we
therefore conclude that well-conditioned whenever -(A; b) is small - even if
-(A) is large?
Here jAj denotes the matrix whose elements are the absolute values of the corresponding elements
of A.
RIGHT-HAND SIDE AND CONDITIONING OF LINEAR SYSTEMS 5
2.3. Numerical Experiments. To answer this question, we compute krk 2 =kbk 2
in the two-norm.
We chose sixteen matrices from the MATLAB test matrix suite [10]. The matrices
are real and have various properties: non-symmetric, symmetric, indefinite, positive
definite, triangular or tridiagonal. The triangular matrices R(Compan) and R(Dorr)
are upper triangular matrices from QR factorizations of the matrices Compan and
Dorr, respectively.
The order n of a matrix A is determined so that its two-norm condition number
. Thus the matrix orders range from 5 to 1000.
The purpose is to push the limits of single precision accuracy (about 10 \Gamma7
condition number of 10 7 and a relative residual on the order of single precision, the
upper bound on the traditional relative error (2.4) equals one. This means at least
one component of the computed solution -
x may have no correct digits. We designed
these extreme cases to see clearly whether a fortunate right-hand side is capable of
providing relief in the worst case.
We choose the right-hand sides for the linear systems as follows. Each matrix
A is paired up in turn with nine different right-hand sides. To obtain a range of
values we forced the right-hand sides to lie along three different directions: one
direction maximises - 2 another direction minimises - 2 (A; b):
a third direction falls in between: b is a random vector. For each
direction, the right-hand sides come in three different lengths, long: kbk
short
Each linear system was solved by two different direct methods: Gaussian elimination
with partial pivoting (GE) and the QR factorization (QR). The solutions were
computed in single precision, with machine precision on the order of 10 \Gamma7 . More
details about the experiments are given in Appendix A.
In all tables to follow, the first column represents the direction of b (in terms of
while the second column represents the length of b (in terms of kbk 2 ). For
each of the nine different right-hand sides, we display the results from GE and from
QR.

Tables

2.1, 2.2 and 2.3 show the following: When - 2 (A; b) is large then krk 2 =kbk 2
is on the order of machine precision (except for the Chow, Fiedler and Minij matrices,
where QR produces krk 2 =kbk 2 as large as small then
The numerical experiments suggest that krk 2 =kbk 2 is inversely proportional to
both condition number and backward error depend on b we cannot
draw any conclusions about their product, the error bound.
Therefore we forego krk=kbk as a backward error and -(A; b) as a condition num-
ber, and look for alternatives.
3. Independence From the Right-Hand Side. We show that the lower and
upper bounds (2.1) essentially do not depend on the direction of b when -
x is computed
by Gaussian elimination or QR factorization. We rewrite the bounds in terms of a
condition number and a backward error that are independent of b. We also explain
why krk=kbk varies with -(A; b).
3.1. Another Interpretation of the Bounds. We ended up with krk=kbk
as a backward error because we multiplied and divided the bounds in (2.1) by kbk.
The result (2.2) is a somewhat arbitrary separation of (2.1) into backward error and
condition number. If we focus instead on the bounds (2.1) as a whole then an obvious
6 J.M. BANOCZI, N. CHIU, G.E. CHO, I.C.F. IPSEN
choice for backward error is the lower bound
krk
This makes sense because unless j is small, the relative error isn't going to be small.
Expressing (2.1) in terms of j allows us to bracket the relative error in terms of j and
a condition number independent of b,
xk
The numerical experiments below suggest that j is essentially independent of b.
3.2. Numerical Experiments. We compute
norm version of j.

Tables

3.1, 3.2 and 3.3 show the following: Regardless of - 2 tends to be
on the order of machine precision (except for the Chow, Fiedler and Minij matrices
where QR produces values for j 2 as large as 10 \Gamma5 ). Thus, Gaussian elimination and
QR factorization produce solutions whose backward error j 2 is usually on the order
of machine precision.
We conclude that in the case of Gaussian elimination and QR factorization the
bounds (3.1) are essentially independent of b. The independence of general-purpose
algorithms from the right-hand side is also confirmed in [4, x5].
3.3. Relation Between Backward Errors. To reconcile the two different in-
terpretations, (2.2) and (3.1), of the bounds (2.1) we relate the backward errors
krk=kbk and j. The relation was already derived in [6, p 99] and is alluded to in
krk
kbk
This confirms the observation in x2.3 that krk=kbk is inversely proportional to -(A; b),
does not depend on b. Relation (3.2) implies together with (2.3):
kbk
That is, when -(A; b) is maximal, krk=kbk can be as small as machine precision. But
when -(A; b) is minimal then krk=kbk can be large because it hides the condition
number inside.
Therefore, j appears to be preferable as a backward error over krk=kbk.
4. Computable Error Bounds. We present computable, a posteriori error
bounds that do not depend on the direction of b, when solved by Gaussian
elimination or QR factorization. The computable version of j is optimal in a well-defined
sense.
To obtain bounds that are computable, we measure the relative error instead with
regard to the computed
krk
krk
(4.
RIGHT-HAND SIDE AND CONDITIONING OF LINEAR SYSTEMS 7
Expressing (4.1) in terms of the computable version of j,
krk
yields an interval for the relative error [16, Theorem III.2.16]:
xk
k-xk
The numerical experiments below confirm that -
j is as good a measure of accuracy as
j.
4.1. Numerical Experiments. We compute - j 2 , the two-norm version of -
j.

Tables

4.1, 4.2 and 4.3 show the following: Regardless of - 2 (A; b), -
2 is on the
order of machine precision (except for the Chow and Fiedler matrices where QR
produces values for -
as large as 10 \Gamma6 ). In case of the Minij matrix, - j 2 is on the
order machine precision while j 2 can be as large as 10 \Gamma5 . Thus, Gaussian elimination
and the QR factorization tend to produce a computed solution whose backward error
2 is on the order of machine precision.
We conclude that in case of Gaussian elimination and QR factorization the bounds
(4.2) are essentially independent of b.
4.2. Minimal Matrix Backward Error. Another justification for the bounds
(4.1) is the optimality of -
j in the following sense: -
j represents the best possible
(norm-wise) backward error when perturbations are confined to the matrix.
Whenever -
Theorem III.2.16]
Thus - x is the solution to a linear system with a perturbed matrix. Here we compensate
for the error in - x by changing the matrix. Moreover, among all E satisfying
b there is a matrix E 0 in (4.3) with minimal norm, i.e. In case of the
two-norm, for instance, one can choose 2. Therefore,
is the smallest norm-wise matrix backward error.
Moreover, -
j has a similar relation to krk=kbk as j:
krk
kbk
kbk
Consequently, krk=kbk AE -
means krk=kbk is going
to be large whenever -
x reflects the condition of A. Arioli, Duff and Ruiz confirm
this by observing that 'even an - x that is a good approximation to x can have a large
residual' [2, p 139].
4.3. Bounds on -
j. The numerical experiments in x4.1 provide a heuristic justification
why -
j is small. A theoretical justification comes from the following round-off
error bounds.
Gaussian elimination with partial pivoting computes a solution -
x for a system
whose matrix perturbation in the infinity-norm is bounded by [11,
Theorem 9.5]
8 J.M. BANOCZI, N. CHIU, G.E. CHO, I.C.F. IPSEN
where ae is the growth factor in Gaussian elimination, and ffl is the machine precision.
Unless ae is large, -
is small in the infinity-norm:
kAk1
kAk1
ffl:
The QR factorization computes a solution -
x for a system whose
matrix perturbation is bounded by [11, inequalities (18.7)]
where c is a small positive integer. Again, - j is small in the two-norm:
ffl:
The fact that -
j is usually small is applied in the following section to determine a
realistic stopping criterion for iterative methods.
5. Stopping Criteria for Iterative Methods. An iterative method solves a
linear system by computing a succession of iterates. The method terminates once an
iterate satisfies a stopping criterion. Popular stopping criteria require the residual to
be sufficiently small. For instance two such stopping criteria are [11, x16.5],
x is the current iterate and tol is a user-supplied tolerance. The first criterion
requires that krk=kbk should not exceed tol, while the second requires that -
should
not exceed tol.
The first criterion can be harder to satisfy than the second [11, x16.5]. To see
this, suppose an iterate - x satisfies krk - tol kAk k-xk. This implies
krk
kbk
kbk tol:
Hence -
x can be very far from satisfying krk - tol kbk when kbk - kAk k-xk. This
confirms the observation in [2, p 139] that krk=kbk 'can be misleading in the case
Therefore, if at all feasible, stopping criteria in iterative methods should be based
on -
rather than on krk=kbk. Preliminary experiments with the matrices from xx2.3,
3.2 and 4.1 indicate that solutions computed by GMRES [14] do satisfy the criterion
based on -
j.
Issues regarding the appropriate choice of stopping criteria have also been discussed
in the context of linear systems arising from discretizations of partial differential
equations [3, 13].
6. A Third Interpretation of the Error Bound. We present a third interpretation
of the error bounds (2.1) based on a backward error ! that is a mixture
of the previous two backward errors. The computable version of ! is optimal in a
well-defined sense, and represents the basis for another stopping criterion for iterative
methods.
RIGHT-HAND SIDE AND CONDITIONING OF LINEAR SYSTEMS 9
Expressing (2.1) in terms of
krk
gives
xk
The definitions of j and ! imply the relation
and j differs from ! by a factor of at most two:
The computable version of ! is
krk
It represents the smallest (norm-wise) backward error [11, Theorem 7.1]:
Moreover, -
resembles the backward error from [2],
The experiments in [2, x3] suggest that ! 2 behaves much like -
j.
The two computable backward errors -
are related by
kbk
Hence
and -
is small whenever -
j is small. In particular, if kbk - kAk k-xk then2
Hence the round-off error bounds from x4.3 are also valid for -
!.
A stopping criterion based on -
terminates an iterative method once an iterate
x satisfies
This criterion is recommended in [11, x16.5], and a version based on ! 2 is recommended
in [2, x5].
J.M. BANOCZI, N. CHIU, G.E. CHO, I.C.F. IPSEN
7. The Effective Condition Number. We present Chan and Foulser's 'effec-
tive condition number' - eff [5] and show that it is weaker than - 2 (A; b). That is, the
effective condition number is never smaller than - 2 (A; b) but can be much larger than
be a singular value decomposition, where U and V are unitary
matrices, \Sigma is a diagonal matrix, and   denotes the conjugate transpose. The diagonal
elements of \Sigma,
are the singular values of A. The columns of U and V ,
are the left and right singular vectors, respectively.
Partition the columns of U ,
k be the orthogonal projector onto range(U k ). If P k b 6= 0 then
is the kth effective condition number of the linear system stating Chan
and Foulser's error bound, we show that - eff (k) can never be smaller than -(A; b). A
similar inequality is stated in [4, (5.2)].
Theorem 7.1. If P k b 6= 0; then
Proof. Partition V and \Sigma conformally with U ,
and
Therefore
The following bound is a direct consequence of (2.2) and Theorem 7.1, and is
therefore weaker than (2.2).
RIGHT-HAND SIDE AND CONDITIONING OF LINEAR SYSTEMS 11
Corollary 7.2 (Theorem 1 in [5]).
Chan and Foulser [5, p 964, x1] seem to imply that - eff (k) can be much smaller
than the traditional condition number when b is close to the direction of un ,
i.e. when kPn bk 2 =kbk 2 - 1. In other cases, however, - eff (k) can be much larger than
as the example below illustrates.
Remark 1. - eff (k) can be arbitrarily much larger than - 2 (A).
A simple 2 \Theta 2 matrix illustrates this.
has a condition number singular value decomposition is
with
Hence
If
then the condition number associated with the smallest
singular value is
Choosing large makes - eff (2) arbitrarily large, while remains fixed.
8. The Relative Error. Sections 3-6 argued that the error bounds (2.1) essentially
do not depend on the direction of b. Can we conclude that the same is true
for the accuracy of the computed solution? That is, does the relative error also not
depend on the direction of b?
Suppose for a moment that the accuracy of the computed solution did indeed
depend on b. Then the magnitude of the relative error should change with the direction
of b. In particular, consider the two linear systems
-(A). If we also assume that the error behaves in the same
way as the bounds (2.2) then we would expect the relative error for the first system
to be -(A) times smaller than the error of the second system. Since our matrices are
constructed so that -(A) is close to the inverse of machine precision, the relative error
for should be close to machine precision.
8.1. Numerical Experiments. We compute the two-norm relative error

Tables

8.1, 8.2 and 8.3 provide only an inconclusive answer. Unlike its lower and
upper bounds, the relative error does seem to depend on the right-hand side. But
this dependence appears to be weak. It is stronger for some matrices than for others.
12 J.M. BANOCZI, N. CHIU, G.E. CHO, I.C.F. IPSEN
Dependence on the Direction of b. The relative errors tend to be smaller
1, and larger when - (A). The Dorr matrices are an
exception: Both GE and QR produce errors for - 2 1 that can be a factor of
ten larger than the errors for - 2 (A). Similarly for the Fiedler matrix: GE
produces the smallest relative error for the random right-hand side, although it does
not have the smallest -(A; b) value.
In case of the Kahan matrix, for instance, the relative errors vary by a factor as
high as 10 4 . This variation is not too far away from . Since the
Kahan matrix is triangular, no factorization is performed (that's why GE and QR
produce exactly the same errors).
Does this mean that triangular matrices exhibit a stronger dependence on the
direction of b, or that a factorization can destroy the relation between A and b? To
answer these questions we computed the upper triangular factors R(Compan) and
R(Dorr) in the QR factorizations of the Compan and Dorr matrices, respectively. In
exact arithmetic, the matrix R(A) has the same singular values as A, hence the same
matrix condition number. If a factorization did indeed destroy the relation between
A and b, then we would expect R(A) to depend more on the right-hand side than A.
However, the variation in errors is about the same for the Dorr and R(Dorr) matrices;
and the variation in errors for R(compan) is about a factor of ten higher than for the
Compan matrix. Thus there is no definite indication that the error of a triangular
system depends more strongly on the right-hand side than the error of a general,
square system.
Now consider the size of the relative errors when - 1. The relative error
for the Kahan matrix is on the order of machine precision, but the error produced by
the QR factorization of the Minij matrix is on the order of 10 \Gamma1 , significantly larger
than machine precision.
We conclude that the variation in errors for different values of - 2 (A; b) is usually
much smaller than - 2 (A); and that the error is significantly larger than machine
precision when - 1. Therefore, the error appears to depend only weakly on
the direction of the right-hand side. The independence of the relative error from the
right-hand side in the case of Gaussian elimination is also observed in [4, x5].
Dependence on the Length of b. Although the bounds in x2 and x3 are
invariant under the length of b, the computable bounds in x4 do change with kbk.
Sometimes the magnitude of the errors changes with kbk and sometimes it does not.
Usually the variation in errors is limited to a factor of about ten. For some matrices,
such as the Fiedler, Dorr and Minij matrices, the magnitude of the errors does not
change with kbk. But in other cases, such as the Clement matrix, the magnitude of
the errors can differ by a factor of 100.
Dependence on Algorithms. The relative error also depends on the algo-
rithms. Gaussian elimination produces a smaller relative error than QR: The difference
in errors can be as high as a factor of 10 6 , e.g., for the Minij matrix when
1. This could be due to the higher operation count of QR and the larger
amount of fill in the triangular factor.
The error for QR is often of the same magnitude as the upper bound (2.1), e.g.,
for the Minij and Fiedler matrices. Thus the upper bounds for the error are realistic.
9. Conclusion. We have investigated how the direction of the right-hand side b
affects the error bounds for a system of linear equations
If the error in - x is due solely to input perturbations of the right-hand side then
RIGHT-HAND SIDE AND CONDITIONING OF LINEAR SYSTEMS 13
krk=kbk reflects the accuracy of the input data. The norm-wise relative error can be
estimated from the bounds
krk
kbk
krk
where the condition number
is interpreted as a measure for the sensitivity to perturbations in the right-hand side.
The error bounds depend on the right-hand side because a fortunate choice of b can
significantly reduce the condition number -(A; b) and may thus increase the accuracy.
If, however, perturbations are not confined exclusively to the right-hand side then
krk=kbk can be much larger than the inaccuracy in the data and the backward error
from a linear system solver. To account for perturbations in the matrix, the error
bounds are expressed in terms of
xk
According to numerical and theoretical evidence, j tends to be on the order of machine
precision when -
x is computed by Gaussian elimination with partial pivoting or by the
QR factorization. Hence the lower and upper error bounds are essentially independent
of b.
Our numerical experiments suggest that the upper error bound is realistic because
it is often achieved by the QR factorization.
In the context of iterative methods we recommend krk - tolkAkk-xk as a stopping
criterion over krk - tolkbk. This is because krk=kbk is much larger than -
experiments indicate that GMRES (without preconditioning)
can produce solutions -
x that satisfy krk - tol kAk k-xk with tol equal to machine
precision. However they can be far from satisfying krk - tol kbk. A third stopping
criterion, krk - tol very much like krk - tol kAk k-xk. Hence
it is preferable to krk=kbk, as well.

Acknowledgement

. We thank Iain Duff and especially Stan Eisenstat for many
helpful suggestions.


Appendix

A. Implementation of the Numerical Experiments. We chose
the two-norm because it is easy to determine right-hand sides with particular - 2
values: Let oe min be the smallest singular value of A and oe max be the largest; and
denote the corresponding left and right singular vectors by umin , umax , and v min ,
respectively. This implies for the smallest singular value
and for the largest singular value
takes on its extreme values when b is a left singular vector associated
with an extreme singular value. Therefore, we enforced - 2 choosing
14 J.M. BANOCZI, N. CHIU, G.E. CHO, I.C.F. IPSEN
b to be a non-zero multiple of umax , and - 2 choosing b to be a non-zero
multiple of umin .
We generated the matrices and right-hand sides in double precision in MATLAB
(version 4.2c) [12] and then converted them to single precision, so that A and b
admit exact representations in single precision. The triangular matrices R(Compan)
and R(Dorr) were computed from the MATLAB QR factorizations of the matrices
Compan and Dorr, respectively. To ensure that the right-hand sides lie along the
desired directions, we computed for the unit-norm right-hand sides
The remaining calculations were done in HP FORTRAN 77 (version 9.16). A
computed solution -
x is represented by the single precision solution of the following
subroutines [1]: SGETRF and SGETRS for Gaussian elimination with
partial pivoting; and SGEQRF, SORMQR and STRTRS for the QR factorization.
To get a representation for the exact solution x, we extended the single precision
versions of A and b to double precision and solved the resulting system in double
precision by Gaussian elimination (subroutines DGETRF and DGETRS). Note: The
exact representations of A and b in single precision ensure that both -
x and x, are
computed from the same input data.
The data in Tables 2.1-8.3, krk 2 =kbk 2 ,
were computed
in double precision, after conversion of single precision quantities to double precision.
All computations were performed on a HP9000 Model 712/60 workstation running
HP-UX operating system version E release A.09.05.



--R


Stopping criteria for iterative solvers
Vector stopping criteria for iterative methods: Applications for PDE's
The fast Bj-orck-Pereyra-type algorithm for parallel solution of Cauchy linear equations
Effectively well-conditioned linear systems
On the sensitivity of solution components in linear systems of equations
The effective condition number applied to error analysis of certain boundary collocation methods
analysis of the Bj-orck-Pereyra algorithms for solving Vandermonde systems



The MathWorks
Vector stopping criteria for iterative methods: Theoretical tools
GMRES: A generalized minimal residual algorithm for solving nonsymmetric linear systems
Introduction to Matrix Computations
Matrix Perturbation Theory
--TR
condition number;right-hand side;stopping criterion;backward error;linear system