51 Matrix Factorizations and Direct Solution of Linear Systems s of Linear Systems. Linear Systemsmposition 51.4 Symmetric Factorization 51-19 51.5 Orthogonalization and the QR Factoriation- References 51-20 The need to solve sys of linear ence engin ession "direct solution of lir ear ms”refers and dimension of the coefficient matrix.The evolution of computers has and continues to influence the development of these strategies and has also fostered particular styles of per- turbation analysis suited to illuminating their behavior.Some general themes have become dominant,as a result;others have been pushed aside.For example,Cramer's Rule may be properly thought of as a direct solution strategy for solving linear systems:however as normally manifested,it requires a much larger number of arithmetic operations than Gauss elimination and is generally much more susceptible to the deleterious effects of rounding Most current approaches for the direct solution of a linear system,Ax= b,are patterne after Gauss elimination and favor an initial phase that partially decouples the system of equations:ze into tria 1 Find invertible matrices such that Se ..S2SA=U is triangular;then 2 a modifod right hand side SS b:and then 3.Determine the solution set to the triangular system Ux=y. The matrices S,S2,...S.are typically either row permutations of lower triangular matrices (Gauss transformations)or unitary matrices.In either case,inverses s are readily available.Evidently,A can be written as A=NU,where N=(5...S2S1)-1.A solution framework may be built around the availability of decompositions such as this: 1.Find a decomposition A =NU such that U is triangular and Ny =b is easily =b;ther set to the triangular system Uxy. 51-1 51 Matrix Factorizations and Direct Solution of Linear Systems Christopher Beattie Virginia Polytechnic Institute and State University 51.1 Perturbations of Linear Systems ................... 51-2 51.2 Triangular Linear Systems.......................... 51-5 51.3 Gauss Elimination and LU Decomposition ....... 51-7 51.4 Symmetric Factorizations ........................... 51-13 51.5 Orthogonalization and the QR Factorization .... 51-16 References..................................................... 51-20 The need to solve systems of linear equations arises often within diverse disciplines of sci￾ence, engineering, and finance. The expression “direct solution of linear systems” refers generally to computational strategies that are able to produce solutions to linear systems after a predetermined number of arithmetic operations that depends only on the structure and dimension of the coefficient matrix. The evolution of computers has and continues to influence the development of these strategies and has also fostered particular styles of per￾turbation analysis suited to illuminating their behavior. Some general themes have become dominant, as a result; others have been pushed aside. For example, Cramer’s Rule may be properly thought of as a direct solution strategy for solving linear systems; however as normally manifested, it requires a much larger number of arithmetic operations than Gauss elimination and is generally much more susceptible to the deleterious effects of rounding. Most current approaches for the direct solution of a linear system, Ax = b, are patterned after Gauss elimination and favor an initial phase that partially decouples the system of equations: zeros are introduced systematically into the coefficient matrix, transforming it into triangular form; the resulting triangular system is easily solved. The entire process can be viewed in this way: 1. Find invertible matrices {Si} ρ i=1 such that Sρ . . . S2S1A = U is triangular; then 2. Calculate a modified right-hand side y = Sρ . . . S2S1b; and then 3. Determine the solution set to the triangular system Ux = y. The matrices S1, S2, . . . Sρ are typically either row permutations of lower triangular matrices (Gauss transformations) or unitary matrices. In either case, inverses are readily available. Evidently, A can be written as A = NU, where N = (Sρ . . . S2S1) −1 . A solution framework may be built around the availability of decompositions such as this: 1. Find a decomposition A = NU such that U is triangular and Ny = b is easily solved; 2. Solve Ny = b; then 3. Determine the solution set to the triangular system Ux = y. 51-1