next up previous

10 Error Bounds for Solving Ax=b     continued...

Gaussian elimination with partial pivoting is almost always numerically stable, so the error bound one expects from solving Ax=b this way is

The notation means something close to . In practice, one sees errors as large as or so, where n is the dimension of A. So for example, if and we compute in IEEE standard single precision, we can expect to get 3 correct decimal places in the answer, since .

We can only say that Gaussian elimination with partial pivoting is almost always numerically stable, because matrices A do exist where is as large as . Since grows very quickly with n, the error bound rapidly becomes enormous (and the actual solution also becomes poor). These examples are found in numerical analysis textbooks [4,5,6], but not in practice.

Rather than formally proving that Gaussian elimination with partial pivoting is generally stable, let us instead illustrate how omitting pivoting can destroy stability. Let us apply Gaussian elimination without pivoting to compute the factorization A=LU of

To keep the example simple, we will use 3 decimal digit floating point arithmetic. Note that , so A is well conditioned and we should expect to be able to solve Ax=b accurately. We will use the notation to mean the rounded, floating point result of , where op is one of the operations +, -, and .