next up previous

10 Error Bounds for Solving Ax=b

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: