TABLE OF CONTENTS This chapter discusses perturbation theory, algorithms, and error analysis for solving the linear equation Ax = b. The algorithms are all variations on Gaussian elimination. They are called direct methods, because in the absence of roundoff error they would give the exact solution of Ax = b after a finite number of steps. In contrast, Chapter 6 discusses iterative methods, which compute a sequence x 0, x 1, x 2, of ever better approximate solutions of Ax = b; one stops iterating (computing the next x i+1) when x i is accurate enough. Depending on the matrix A and the speed with which x i converges to x = A ?1 b, a direct method or an iterative method may be faster or more accurate. We will discuss the relative merits of direct and iterative methods at length in Chapter 6. For now, we will just say that direct methods are the methods of choice when the user has no special knowledge about the source [7] of matrix A or when a solution is required with guaranteed stability and in a guaranteed amount of time.
The rest of this chapter is organized as follows. Section 2.2 discusses perturbation theory for Ax = b; it forms the basis for the practical error bounds in section 2.4. Section 2.3 derives the Gaussian elimination algorithm for dense...
