Matrix Factorizations and Direct Solution of Linear Systems 51-7 So.linear systems having TT as a coefficient matrix may have solutions that are sensitive to perturbations and indeed,cond(TT,)cond(TT)for any right-hand side b with b30 yielding solutions that are sensitive to perturbations for small e. 51.3 Gauss Elimination and LU Decomposition entary app os th of th h.yet it transform nation matrix M mation"）is designed s into A- ally into a rtion of theth without harming eros that bave heen introdu ps.Typically,successive applications of Gauss transformation are interleaved with row intercha as producing a decon matrix and n is a row permutation of a lower triangular matrix. Definitions: For each indexk a Gau ector is 4=包044 ntri +1,....In are Ga ulti ML=I-ELel is called a Gauss transformation. For the pair of indices (i j),with ij the associated permutation matrix,is an nxn identity matrix with the i row and row interchanged.Note that IIii is the identity matrix. A matrix U E C is in row-echelon form if (1)the first nonzero entry of each row has a strictly small n than all nonzer ntries with strictly larger r x and (2)zer rows occ at th nonzero entry in each ro is called a pivot. determining eature ots occur of a onzer L∈Cmxm =0 for Facts:[GV96] 1.Let a e cr be a vector with a ent in the re entrv a.≠0.Defn the Gauss vector,0 M=I-eT introduces zeros into the last n-r entries of a Ma=[a,....r0..... MpMp-1…MA=U with U upper triangular.Each Gauss transformation M,introduces zeros into the rth column. 3.Gauss transformations are unit lower triangular matrices.They are invertible,and for the Gauss transformation.M=I-ee. M1=I+ereT Matrix Factorizations and Direct Solution of Linear Systems 51-7 So, linear systems having T T as a coefficient matrix may have solutions that are sensitive to perturbations and indeed, cond(T T , xˆ) ≈ cond(T T ) for any right-hand side b with b3 6= 0 yielding solutions that are sensitive to perturbations for small . 51.3 Gauss Elimination and LU Decomposition Gauss elimination is an elementary approach to solving systems of linear equations, yet it still constitutes the core of the most sophisticated of solution strategies. In the k th step, a transformation matrix, Mk, (a “Gauss transformation”) is designed so as to introduce zeros into A — typically into a portion of the k th column — without harming zeros that have been introduced in earlier steps. Typically, successive applications of Gauss transformations are interleaved with row interchanges. Remarkably, this reduction process can be viewed as producing a decomposition of the coefficient matrix A = NU, where U is a triangular matrix and N is a row permutation of a lower triangular matrix. Definitions: For each index k, a Gauss vector is a vector in C n with the leading k entries equal to zero: `k = [0, . . . , 0 | {z } k , `k+1, . . . , `n] T . The entries `k+1, . . . , `n are Gauss multipliers. The related matrix Mk = I − `ke T k is called a Gauss transformation. For the pair of indices (i, j), with i ≤ j the associated permutation matrix, Πi,j is an n × n identity matrix with the i th row and j th row interchanged. Note that Πi,i is the identity matrix. A matrix U ∈ C m×n is in row-echelon form if (1) the first nonzero entry of each row has a strictly smaller column index than all nonzero entries with strictly larger row index and (2) zero rows occur at the bottom. The first nonzero entry in each row is called a pivot. The determining feature of row echelon form is that pivots occur to the left of all nonzero entries in lower rows. A matrix A ∈ C m×n has an LU decomposition if there exists a unit lower triangular matrix L ∈ C m×m (Li,j = 0 for i < j and Li,i = 1 for all i) and an upper triangular matrix U ∈ C m×n (Ui,j = 0 for i > j) such that A = LU. Facts: [GV96] 1. Let a ∈ C n be a vector with a nonzero component in the r th entry, ar 6= 0. Define the Gauss vector, `r = [0, . . . , 0 | {z } r , ar+1 ar , . . . , an ar ] T . The associated Gauss transformation Mr = I − `re T r introduces zeros into the last n − r entries of a: Mra = [a1, . . . , ar, 0, . . . , 0]T . 2. If A ∈ C m×n with rank A = ρ ≥ 1 has ρ leading principal submatrices nonsingular, A1:r,1:r, r = 1, . . . , ρ, then there exist Gauss transformations M1, M2, . . . , Mρ so that MρMρ−1 · · · M1A = U with U upper triangular. Each Gauss transformation Mr introduces zeros into the r th column. 3. Gauss transformations are unit lower triangular matrices. They are invertible, and for the Gauss transformation, Mr = I − `re T r , M−1 r = I + `re T r