Linear Systems of Equations

In this chapter, we discuss the solution of systems of n linear equations in n variables. At some stage, most of the more advanced problems in scientific calculations require the solution of linear systems; often these systems are very large and their solution is the most time-consuming part of the computation. Therefore, the efficient solution of linear systems and the analysis of the quality of the solution and its dependence on data and rounding errors is one of the central topics in numerical analysis. A fairly complete reference compendium of numerical linear algebra is Golub and van Loan [31]; see also Demmel [17] and Stewart [89]. An exhaustive source for overdetermined linear systems (that we treat in passing only) is Björck [8]. We begin in Section 2.1 by introducing the triangular factorization as a compact form of the well-known Gaussian elimination method for solving linear systems, and show in Section 2.2 how to exploit symmetry with the LDL T and the Cholesky factorization to reduce work and storage costs. We only touch the savings possible for sparse matrices with many zeros by looking at the simple banded case. In Section 2.3, we show how to avoid numerical instability by means of pivoting. In order to assess the closeness of a matrix to singularity and the worst case sensitivity to input errors, we look in Section 2.4 at norms and in Section 2.5 at condition numbers.