51-6 Handbook of Linear Algebra Algorithm 1 or 2 is 102 rith solvin r sy system (T+6T)=b,where |6T]< -T and e is the unit roundoff error. 2 satisfios necond(T.) x 6.If T=[t]is a lower triangular matrix satisfying for jsi,the co solution to the line of Algorithm 2 for lower triangular systems satisfies -≤ where are the of the exact solution,Although this bound degrades onentially with i,it sho that early solution components will be computed to high accuracy relative to those components already computed. Examples: 1.Use Algorithm 2 to solve the triangular system k=3 step:Solve for r3=1/3.Update right-hand side 阳-月日月 =2 step:Solve for2=3/2.Update right-hand sides =1 step:Solve for=- 100 2.[Hig02,p.156]For e>0,consider T= cond(T)=5,even though x(四)=22+3≈2+0. Thus,lin ms having T as a coefficient matrix will be solved to high relative ent of both right-hand side and size of des te the poor conditioning of T(as small.However,note that cond(TT)=1+2 and (TT)=(1+e)22+(1)
51-6 Handbook of Linear Algebra 4. The solution of triangular systems using either Algorithm 1 or 2 is component-wise backward stable. In particular the computed result, x˜, produced either by Algorithm 1 or 2 in solving a triangular system, Tx = b, will be the exact result of a perturbed system (T + δT)x˜ = b, where |δT| ≤ n 1 − n |T| and is the unit roundoff error. 5. The error in the solution of a triangular system, Tx = b, using either Algorithm 1 or 2 satisfies kx˜ − xˆk∞ kxˆk∞ ≤ n cond(T, xˆ) 1 − n (cond(T) + 1). 6. If T = [tij ] is a lower triangular matrix satisfying |tii| ≥ |tij | for j ≤ i, the computed solution to the linear system Tx = b produced by either Algorithm 1 or the variant of Algorithm 2 for lower triangular systems satisfies |xˆi − x˜i | ≤ 2 i n 1 − n max j≤i |x˜j |, where ˜xi are the components of the computed solution, x˜, and ˆxi are the components of the exact solution, xˆ. Although this bound degrades exponentially with i, it shows that early solution components will be computed to high accuracy relative to those components already computed. Examples: 1. Use Algorithm 2 to solve the triangular system 1 2 −3 0 2 −6 0 0 3 x1 x2 x3 = 1 1 1 . k = 3 step: Solve for x3 = 1/3. Update right-hand side: 1 2 0 2 0 0 " x1 x2 # = 1 1 1 − (1/3) −3 −6 3 = 2 3 0 . k = 2 step: Solve for x2 = 3/2. Update right-hand side: 1 0 0 x1 = 2 3 0 − (3/2) 2 2 0 = −1 0 0 . k = 1 step: Solve for x1 = −1. 2. [Hig02, p. 156] For > 0, consider T = 1 0 0 ε ε 0 0 1 1 . Then T −1 = 1 0 0 −1 1 ε 0 1 − 1 ε 1 , and so cond(T) = 5, even though κ∞(T) = 2(2 + 1 ε ) ≈ 2 ε + O(1). Thus, linear systems having T as a coefficient matrix will be solved to high relative accuracy, independent of both right-hand side and size of , despite the poor conditioning of T (as measured by κ∞) as becomes small. However, note that cond(T T ) = 1 + 2 ε and κ∞(T T ) = (1 + ε) 2 ε ≈ 2 ε + O(1).
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