How accurately can we expect to solve Ax=b? In this section we will
outline the answer to this question, and refer to standard textbooks
for details [4,5,6]. The answer depends both on
the matrix A, and on the algorithm we use. To derive a useful error
bound, the property of the matrix we need to know is its condition
number 
, and the property we require of the algorithm is numerical
stability.
Library software also exists for evaluating all the error bounds described here, for dense and band matrices. We list the LAPACK routines for computing these error bounds below.
To define the condition number 
of A, we need to introduce some more
notation. Let 
denote solution of the linear system
, where E is a small perturbation of A.
We want to measure the difference between 
and 
.
Let 
; this is called the
infinity-norm of x.
We will derive a bound on
When this quantity is significantly less than 1, we say that
is a good approximation to x. For example, if
it is 
, we say 
and x agree to six
decimal places (note that only the largest components of
and x agree to six decimal places; the smaller
components may agree to fewer). Supposing that
X is an n-by-n matrix, define
is called the infinity-norm of the
matrix X.
Note that 
is always within a factor of n of
the absolute value of the largest entry of X. Using this
notation, we can now define the condition number of a matrix as
Using 
, we can bound the
difference between 
and 
as follows:
