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