Chapter 2 Direct Methods for Solving Linear Systems0 Introduction,Consider the system: (1),Using matrix form Ax=b (2),2017/12/14,1,where A is a n-order square matrix, x and b are n-dimensional vectors. According to the Cramers rule, if det(A) 0,system (2) has a unique solutionwhere D=det(A), and Dj is the determinant of the matrix obtained by substituting j-th column of A with the right hand side b.,There exist two classes of methods for solving linear systems: direct methods and iterative methods。,2017/12/14,2,2 Gaussian Elimination Method 2.1 The Idea of GEM,Eg.2.1 Solve the following linear system of equations,The 1st step, the first equation times by -2 and adds to the second equation, and the first equation times by -1 and adds to the third equation.,2017/12/14,3,The 2nd step: the second equation times by -2/3and adds to the third equation, we have,The 3rd step: solve the linear system by backward substituting, we have x*=(2,1,-1)T,The above process can be described by matrix form as,2017/12/14,4,2.2 GEM Denote Ax=b as A(1)x=b(1),where A(1) and b(1) with entries and , respectively. The goal in the first elimination process is changing the n-1 entries below into 0. We denote the resulting system by A(2)x=b(2).,2017/12/14,5,2017/12/14,6,After k-1th eliminations(suppose 0),we have,2017/12/14,7,Like the first elimination process, the goal of k-th is eliminating the entries below . The operations in detail are as follows:,If 0,(k=1,2,n-1), the process can continue. Finally, we obtain the following matrix,2017/12/14,8,Because the matrix A(n) is an upper triangular matrix, the linear system of equations is changed into a triangular system of equations. If 0,we obtain the solution,(i=n-1,n-2,1),In a word, we can get the algorithm of GEM: step 1elimination process set (i,j=1,2,n),2017/12/14,9,(i,j=k+1,k+2,n),(i=k+1,k+2,n),2backward substitution ( 0),(i=n-1,n-2,1),for k=1 to n-1,if 0 ,do (i=k+1,k+2,n),2017/12/14,10,2.3 A Condition on GEMFrom the previous algorithm, we need assume the entry 0 in the k-th elimination process. In order to finish the GEM, the condition 0 for all k. But we hope decide only according to A whether the GEM can finish or not. So, we have the theorem:,Theorem 2.1 GEM can continue iff all principal minor determinants in order of A dont equal 0.,To compute elimination 2(n-1)n(n+1)/6 + n(n-1) flops are required, plus n2 flops to backward substitution. Therefore, about (n3/3 + 2n2 ) flops are needed to solve the linear system using GEM.,2017/12/14,11,3 Gaussian Elimination with Pivoting In the previous section, the GEM perhaps get a solution with a great error when 1,because multipliers perhaps are very huge and the computation error is amplified largely.,Eg. 2.2 Solve the following linear system of equation using 3 significant digits.,2017/12/14,12,Method I: normal GEM,Solution. ( The accurate solution x*=(-2.6, 1, 2)T.),The solution x=(-5.80, 2.40, 2.02)T. l21=4, l31=10. l32=-100.,2017/12/14,13,Method II: GEM with Column Pivoting,The solution x=(-2.60, 1.00, 2.00)T. l21=0.4, l31=0.1. l32=0.24272.,2017/12/14,14,From the example, we can find that the simple exchange between rows can better the precision of algorithm.,1. GEM with Column Pivoting Suppose that GEM with column pivoting is done k-1 times(1kn-1), the system Ax=bA(k)x=b(k),2017/12/14,15,Before kth elimination, the step 、 need be done:determine ik according to . If =0,we have det(A)=A(k）=0,namely,system Ax=b doesnt satisfy the Cramers rule.,If ikk, exchange row ik and row k, namely,(k j n),After this process, we solve the resulting system using normal GEM.,2017/12/14,16,Algorithm of GEM with column pivotingFind the pivot element，select ik to satisfy if =0，then A is a singular matrix，break.if，go to step 3. Else do Elimination process,(k j n),2017/12/14,17,if，break,backward substitution,output（b1,b2,bn)T,2017/12/14,18,4 Gauss-Jordan Elimination method,1.4. Gauss-Jordan elimination method GJEM is a modified method of GEM. The elimination process in GEM changes the matrix A into a triangular matrix. If we also change all entries on top of the diagonal entries into 0 and change the diagonal entries into 1, we will get the GJEM.,Suppose we have conduct k-1th GJEM,then system Ax=b is changed into system A(k)x=b(k).,2017/12/14,19,In the kth elimination process, we eliminate all entries on top and below the entry akk. Meanwhile, change akk into 1.(k=1,2,n) 1select pivot and determine ik such that,2If , exchange row k and row ik,(j=k,k+1,n),2017/12/14,20,3compute multipliers,