Chapter 2 The Solution of Linear Systems AX= B 2.1 Upper-triangular Linear Systems We will now develop the back-substitution algorithm, which is useful for solving a lin ear system of equations that has an upper-triangular coefficient matrix. This algorithm will be incorporated in the algorithm for solving a general linear system in Section 2.4 Definition 2.2. An N X N matrix A=aii is called upper triangular provided that the elements satisfy ai;=0 whenever i>j. The N X N matrix A=[ai] is called lower triangular provided that aii=0 whenever i< j We will develop a method for constructing the solution to upper-triangular lin- ear systems of equations and leave the investigation of lower-triangular systems to the reader. If A is an upper-triangular matrix, then AX= B is said to an upper-
Chapter 2 The Solution of Linear Systems AX = B 2.1 Upper-triangular Linear Systems We will now develop the back-substitution algorithm, which is useful for solving a linear system of equations that has an upper-triangular coefficient matrix. This algorithm will be incorporated in the algorithm for solving a general linear system in Section 2.4. Definition 2.2. An N × N matrix A = [aij ] is called upper triangular provided that the elements satisfy aij = 0 whenever i > j. The N × N matrix A = [aij ] is called lower triangular provided that aij = 0 whenever i < j. We will develop a method for constructing the solution to upper-triangular linear systems of equations and leave the investigation of lower-triangular systems to the reader. If A is an upper-triangular matrix, then AX = B is said to an upper- 2
triangular system of linear equations and has the form a1x1+a12x2+a13x3+…+a1N-1xN-1+a1NN=b1 a2xX2+a23x3+……+a2N-1xN-1+a2NN=b2 a3r3+…+a3N-1N-1+a3NN=b3 aN___1+aN-ININ= bN-1 annen=b Theorem 2.5(Back Substitution). Suppose that AX=B is an upper-triangular system with the form given in(2. 1). If ak≠0fork=1,2,……,N, (22) then there exists a unique solution to(2.1) Constructive Proof. The solution is easy to find. The last equation involves only N, so we solve it first b N aNN Now tN is known and it can be used in the next-to-last equation bN-1-aN-ININ (2.4) Now CN and N-i are used to find CN-2 bN-2-aN-2N-ICN-1-aN-2NCN Once the value IN, N-1,., Ck+1 are known, the general step is b->}=k+10k可 for k=N-1.N (26) The uniqueness of the solution is easy to see. The Nth equation implies that bn/aNn is the only possible value of N. Then finite induction is used to establish that N-1,N-2,…1 are unique Example 2. 12. Use back substitution to solve the linear system 4x1-x2+2x3+3x4 2x2+7x3-4x4 6r3+5
triangular system of linear equations and has the form a11x1 + a12x2 + a13x3 + · · · + a1N−1xN−1 + a1N xN = b1 a22x2 + a23x3 + · · · + a2N−1xN−1 + a2N xN = b2 a33x3 + · · · + a3N−1xN−1 + a3N xN = b3 . . . . . . aN−1N−1xN−1 + aN−1N xN = bN−1 aNN xN = bN . (2.1) Theorem 2.5 (Back Substitution). Suppose that AX = B is an upper-triangular system with the form given in (2.1). If akk 6= 0 for k = 1, 2, · · · , N, (2.2) then there exists a unique solution to (2.1). Constructive Proof. The solution is easy to find. The last equation involves only xN , so we solve it first: xN = bN aNN . (2.3) Now xN is known and it can be used in the next-to-last equation: xN−1 = bN−1 − aN−1N xN aN−1N−1 . (2.4) Now xN and xN−1 are used to find xN−2: xN−2 = bN−2 − aN−2N−1xN−1 − aN−2N xN aN−2N−2 . (2.5) Once the value xN , xN−1, . . . , xk+1 are known, the general step is xk = bk − PN j=k+1 akjxj akk for k = N − 1, N − 2, . . . , 1. (2.6) The uniqueness of the solution is easy to see. The N th equation implies that bN /aNN is the only possible value of xN . Then finite induction is used to establish that xN−1, xN−2, . . . , x1 are unique. Example 2.12. Use back substitution to solve the linear system 4x1 − x2 + 2x3 + 3x4 = 20 2x2 + 7x3 − 4x4 = −7 6x3 + 5x4 = −4 3x4 = −6. 3
Solving for a in the last equation yields Using 2 in the third equation, we obtain 5( Now I3=-l and a4=2 are used to find 2 in the second equation 7-7(-1)+4(2) Finally, 1 is obtained using the first equation 20+1(-4)-2(-1)-3(2) The condition that akk#0 is essential because equation(2. 6)involves division by akk. If this requirement is not fulfilled, either no solution exists or infinitely many solutions exist Example 2. 13. Show that there is no solution to the linear system 4x1-x2+2x3+3x4=20 0x2+7x3-4x4=-7 6r3+54 Using the last equation in(2.7), we must have I4= 2, which is substituted into the econd and third equations to obtain 7x3-8=-7 6x3+10=-4 The first equation in(2. 8)implies that r3=1/7, and the second equation implies that 3=-1. This contradiction leads to the conclusion that there is no solution to the linear system(2.7) Example 2.14. Show that there are infinitely many solutions to +2r3+3r4=2 0x2+7x3-04=-7 6r3+ (2.9)
Solving for x4 in the last equation yields x4 = 6 3 = 2. Using x2 in the third equation, we obtain x3 = 6 − 5(2) 6 = −1. Now x3 = −1 and x4 = 2 are used to find x2 in the second equation: x2 = 7 − 7(−1) + 4(2) 2 = −4. Finally, x1 is obtained using the first equation: x1 = 20 + 1(−4) − 2(−1) − 3(2) 4 = 3. The condition that akk 6= 0 is essential because equation (2.6) involves division by akk. If this requirement is not fulfilled, either no solution exists or infinitely many solutions exist. Example 2.13. Show that there is no solution to the linear system 4x1 − x2 + 2x3 + 3x4 = 20 0x2 + 7x3 − 4x4 = −7 6x3 + 5x4 = −4 3x4 = −6. (2.7) Using the last equation in (2.7), we must have x4 = 2, which is substituted into the second and third equations to obtain 7x3 − 8 = −7 6x3 + 10 = −4. (2.8) The first equation in (2.8) implies that x3 = 1/7, and the second equation implies that x3 = −1. This contradiction leads to the conclusion that there is no solution to the linear system (2.7). Example 2.14. Show that there are infinitely many solutions to 4x1 − x2 + 2x3 + 3x4 = 20 0x2 + 7x3 − 0x4 = −7 6x3 + 5x4 = −4 3x4 = −6. (2.9) 4
Using the last equation in(2.9), we must have a4= 2, which is substituted into the second and third equations to get 3=-l, which checks out in both equations. But only two values T3 and 4 have been obtained from the second through fourth equations and when they are substituted into the first equation of(2.9), the result x2=4x1-16 which has infinitely many solutions: hence(2.9) has infinitely many solutions. If we choose a value of T1 in(2.10), then the value of x2 is uniquely determined. For exampl if we include the equation a1=2 in the system(2.9), then from(2.10) we compute Theorem 2.4 states that the linear system AX=B, where A is an N X N matrix has a unique solution if and only if det(A)+0. The following theorem states that if any entry on the main diagonal of an upper-or lower-triangular matrix is zero ther det(a)=0. Thus, by inspecting the coefficient matrices in the previous three exam- ples, it is clear that the system in Example 3 12 has a unique solution, and the systems in Examples 2. 13 and 2.14 do not have unique solutions. The proof of Theorem 2.6 can be found in most introductory linear algebra textbooks Theorem 2.6. If the N XN matrix A=aijl is either upper or lower triangular, then det(4)=a1122…am=Iaa The value of the determinant for the coefficient matrix in Example 2. 12 is det(A) 4(-2)(6)(3)=-144. The value of the determinants of the coefficient matrices in Example 2.13 and 2.14 are both 4(0)(6) 3)=0 The following program will solve the upper-triangular system(1) by the method of back substitution, provided akk#0 for k= 1, 2 Program 2.1(Back Substitution). To solve the upper-triangular system AX= B by the method of back substitution. Proceed with the method only if all the diagonal elements are nonzero. First compute tN =bN/aNN and the use the rule k=N-1.N-2 function X=backsub(A, B) A is an n x n upper-triangular nonsingular matrix %Output -X is the solution to the linear system AX=B %Find the dimension of b and initialize x n=length(B) X=zeros(n, 1)
Using the last equation in (2.9), we must have x4 = 2, which is substituted into the second and third equations to get x3 = −1, which checks out in both equations. But only two values x3 and x4 have been obtained from the second through fourth equations, and when they are substituted into the first equation of (2.9), the result is x2 = 4x1 − 16, (2.10) which has infinitely many solutions: hence (2.9) has infinitely many solutions. If we choose a value of x1 in (2.10), then the value of x2 is uniquely determined. For example, if we include the equation x1 = 2 in the system (2.9), then from (2.10) we compute x2 = −8. Theorem 2.4 states that the linear system AX = B, where A is an N × N matrix, has a unique solution if and only if det(A) 6= 0. The following theorem states that if any entry on the main diagonal of an upper-or lower-triangular matrix is zero then det(A) = 0. Thus, by inspecting the coefficient matrices in the previous three examples, it is clear that the system in Example 3.12 has a unique solution, and the systems in Examples 2.13 and 2.14 do not have unique solutions. The proof of Theorem 2.6 can be found in most introductory linear algebra textbooks. Theorem 2.6. If the N ×N matrix A = [aij] is either upper or lower triangular, then det(A) = a11a22 · · · ann = Y N i=1 aii. (2.11) The value of the determinant for the coefficient matrix in Example 2.12 is det(A) = 4(−2)(6)(3) = −144. The value of the determinants of the coefficient matrices in Example 2.13 and 2.14 are both 4(0)(6)(3) = 0. The following program will solve the upper-triangular system (1) by the method of back substitution, provided akk 6= 0 for k = 1, 2, . . . , N. Program 2.1 (Back Substitution). To solve the upper-triangular system AX = B by the method of back substitution. Proceed with the method only if all the diagonal elements are nonzero. First compute xN = bN /aNN and the use the rule xk = bk− P j=k+1 akjxj akk k = N − 1, N − 2, . . . , 1. function X=backsub(A,B) %Input − A is an n × n upper-triangular nonsingular matrix % − B is an n × 1 matrix %Output − X is the solution to the linear system AX=B %Find the dimension of B and initialize X n=length(B); X=zeros(n,1); 5
X(n)=B(n)/A(n, n) fork=n-1:-1:1 X(k)=(B(k-A(k, k+1: n *X(k+1: n)/A(k, k) d 2.1.1 Exercises for Upper-Triangular Linear Systems in Exercises 1 through 3, solve the upper-triangular system and find the value of the determinant of the coefficient matrix
X(n)=B(n)/A(n,n); for k=n-1:-1:1 X(k)=(B(k)-A(k,k+1:n)*X(k+1:n))/A(k,k); end 2.1.1 Exercises for Upper-Triangular Linear Systems in Exercises 1 through 3, solve the upper-triangular system and find the value of the determinant of the coefficient matrix. 6
2.2 Gaussian Elimination and Pivoting In this section we develop a scheme for solving a general system AX=B N equations and N unknowns. The goal is to construct an equivalent upper-triangular system UX=Y that can be solved by the method of Section 2.3 Two linear systems of dimension N x N are said to be equivalent provided that their solution sets are the same. Theorems from linear algebra show that when certain transformations are applied to a given system the solution sets do not chan
2.2 Gaussian Elimination and Pivoting In this section we develop a scheme for solving a general system AX = B of N equations and N unknowns. The goal is to construct an equivalent upper-triangular system UX = Y that can be solved by the method of Section 2.3. Two linear systems of dimension N × N are said to be equivalent provided that their solution sets are the same. Theorems from linear algebra show that when certain transformations are applied to a given system the solution sets do not change. 7
Theorem 2.7.(Elementary Transformations). The following operations applied to a linear system yield an equivalent system Interchange: The order of two equations can be changed (212) g Multiplying an equation by a nonzero constant Replacement: An equation can be replaced by the sum of itself and a nonzero multiple of any other equation (214) It is common to use(2. 14) by replacing an equation with the difference of that tion and Itiple of another equation. There concepts are illustrated in the next example Example 2.15. Find the parabola y= A+ Br Ca that passes through the three points(1,1),(2,-1),and(3,1) For each point we obtain an equation relating the value of to the value of y. The resu llt is the linear system A+B+C=1 A+2B+4c A+3B+9C=1 The variable A is eliminated from the second and third equations by subtractin the first equation from them. This is an application of replacement transformation 3) and the resulting equivalent linear system is A+B+C=1 B+3C=2 2B+8C=0 The variable B is eliminated from the third equation in(5)by subtracting from it two times the second equation. We arrive at the equivalent upper-triangular system A+b+C=1 B+3C=2 The back-substitution algorithm is now used to find the coefficients C=4/2=1,B 2-3(2) (-8)-2=7 +2x2 2.3 Triangular factorization In Section 3. 3 we saw how easy it is to solve an upper-triangular system. Now we introduce the concept of factorization of given matrix A into the product of a lower- triangular matrix L that has 1s along the main diagonal and an upper-triangular ma- trix U with nonzero diagonal elements. For ease of notation we illustrate the concepts
Theorem 2.7. (Elementary Transformations). The following operations applied to a linear system yield an equivalent system: Interchange: The order of two equations can be changed. (2.12) Scaling: Multiplying an equation by a nonzero constant. (2.13) Replacement: An equation can be replaced by the sum of itself and a nonzero multiple of any other equation. (2.14) It is common to use (2.14) by replacing an equation with the difference of that equation and a multiple of another equation. There concepts are illustrated in the next example. Example 2.15. Find the parabola y = A + Bx + Cx2 that passes through the three points (1, 1),(2, −1), and (3, 1). For each point we obtain an equation relating the value of x to the value of y. The result is the linear system A + B + C = 1 at (1, 1) A + 2B + 4C = −1 at (2, −1) A + 3B + 9C = 1 at (3, 1). (2.15) The variable A is eliminated from the second and third equations by subtracting the first equation from them. This is an application of replacement transformation (3), and the resulting equivalent linear system is A + B + C = 1 B + 3C = 2 2B + 8C = 0. The variable B is eliminated from the third equation in (5) by subtracting from it two times the second equation. We arrive at the equivalent upper-triangular system: A + B + C = 1 B + 3C = 2 2C = 4. The back-substitution algorithm is now used to find the coefficients C = 4/2 = 1, B = −2 − 3(2) = −8, and A = 1 − (−8) − 2 = 7, and equation of the parabola is y = 7 − 8x + 2x 2 . 2.3 Triangular Factorization In Section 3.3 we saw how easy it is to solve an upper-triangular system. Now we introduce the concept of factorization of given matrix A into the product of a lowertriangular matrix L that has 1’s along the main diagonal and an upper-triangular matrix U with nonzero diagonal elements. For ease of notation we illustrate the concepts 8
with matrices of dimension 4x 4, but they apply to an arbitrary system of dimension Definition 3.4. The nonsingular matrix A has a triangular factorization if it can be expressed as the product of a low-triangular matrix L and an upper-triangular matrix A= LU In matrix form. this is written as u11a12a13a14 000 u11u12u1314 u21a22a23a14 1000 a31a32a3a34 m3210 00 a41a42a43a44 m41m42m4131 000 The condition that A is nonsingular implies that ukk#0 for all k. The notation for the entries in L is mij, and the reason for the choice of mij instead of lij will be pointed out soon 2.3.1 Solution of a Linear System Suppose that the coefficient matrix A for the linear system AX=B has a triangular factorization(1), then the solution to LUX= B can be obtained by defining Y =UX and then solving two systems first solve LY=B forY: then solve UX=Y for X In equation form, we must first solve the lower triangular system 2.3.2 Triangular Factorization We now discuss how to obtain the triangular factorization If row interchanges are not necessary when using Gaussian elimination, the multipliers mij are the subdiagonal entries in L Example 3.21 Use Gaussian elimination to constant the triangular factorization of the matrix 431 Theorem 3.10(Direct Factorization A=LU. No Row Interchanges). Suppose that Gaussian elimination, without row interchanges, can be successfully performed to
with matrices of dimension 4 × 4, but they apply to an arbitrary system of dimension N × N. Definition 3.4. The nonsingular matrix A has a triangular factorization if it can be expressed as the product of a low-triangular matrix L and an upper-triangular matrix U: A = LU. In matrix form, this is written as a11 a12 a13 a14 a21 a22 a23 a14 a31 a32 a33 a34 a41 a42 a43 a44 = 1 0 0 0 m21 1 0 0 m31 m32 1 0 m41 m42 m43 1 u11 u12 u13 u14 0 u22 u23 u14 0 0 u33 u34 0 0 0 u44 The condition that A is nonsingular implies that ukk 6= 0 for all k. The notation for the entries in L is mij , and the reason for the choice of mij instead of lij will be pointed out soon. 2.3.1 Solution of a Linear System Suppose that the coefficient matrix A for the linear system AX = B has a triangular factorization (1), then the solution to LUX = B can be obtained by defining Y = UX and then solving two systems: first solve LY = B for Y : then solve UX = Y for X. In equation form, we must first solve the lower triangular system 2.3.2 Triangular Factorization We now discuss how to obtain the triangular factorization. If row interchanges are not necessary when using Gaussian elimination, the multipliers mij are the subdiagonal entries in L. Example 3.21 Use Gaussian elimination to constant the triangular factorization of the matrix A = 4 3 1 2 4 5 1 2 6 . Theorem 3.10 (Direct Factorization A=LU. No Row Interchanges). Suppose that Gaussian elimination, without row interchanges, can be successfully performed to 9
solve the general linear system AX= B. Then the matrix A can be factored as the product of a lower-triangular matrix L and an upper-triangular matrix U A= LU Furthermore L can be constructed to have 1's on its diagonal and u will have nonzero diagonal elements. After finding L and U the solution X is computed in two steps 1. Solve LU =b for Y using forward substitution 2. Solve UX=Y for X using back substitution 2.3.3 Computational Complexity 2.3. 4 Permutation matrices 2.3.5 Extending the Gaussian Elimination Process 10
solve the general linear system AX = B. Then the matrix A can be factored as the product of a lower-triangular matrix L and an upper-triangular matrix U: A = LU. Furthermore L can be constructed to have 1’s on its diagonal and U will have nonzero diagonal elements. After finding L and U the solution X is computed in two steps: 1. Solve LU = B for Y using forward substitution. 2. Solve UX = Y for X using back substitution. 2.3.3 Computational Complexity 2.3.4 Permutation matrices 2.3.5 Extending the Gaussian Elimination Process 10
2.4 Iterative Methods for Linear Systems The goal of this chapter is extend some of the iterative methods introduced in Chapter 2 to higher dimensions. We consider an extension of fixed-point iteration that applies to systems of linear equations 2. 4.1 Jacobi iteration Example 3.26. Consider the system of equations 4. T-y+2 4x-8y+z=21 2x+y+5z=15 These equations can be written in the form 7+y 4 21+4x+ 15+2x Table 3.2 Convergence Jacobi iteration for the Linear System(1 队k 2.0 2.0 1.75 3.375 3.0 21.843 3.875 3.025 1.9625 3.925 2.9625 4|190625003.9765625030000 51.994140633.99531250300093750 151.999993999989592999999 92.00000004.00000003.000000 This suggests the following Jacobi iterative process
2.4 Iterative Methods for Linear Systems The goal of this chapter is extend some of the iterative methods introduced in Chapter 2 to higher dimensions. We consider an extension of fixed-point iteration that applies to systems of linear equations. 2.4.1 Jacobi Iteration Example 3.26. Consider the system of equations 4x − y + z = −7 4x − 8y + z = 21 −2x + y + 5z = 15 These equations can be written in the form x = 7 + y − z 4 y = 21 + 4x + z 8 z = 15 + 2x − y 5 . Table 3.2 Convergence Jacobi iteration for the Linear System (1) k xk yk zk 0 1.0 2.0 2.0 1 1.75 3.375 3.0 2 1.84375 3.875 3.025 3 1.9625 3.925 2.9625 4 1.99062500 3.97656250 3.00000000 5 1.99414063 3.99531250 3.00093750 . . . . . . . . . . . . 15 1.99999993 3.99999985 2.99999993 . . . . . . . . . . . . 19 2.00000000 4.00000000 3.00000000 This suggests the following Jacobi iterative process: 11