MAT 343 LAB 3
Example We can generate the three matrices listed in (1) using the following MATLAB commands >>E1eye (4) >> E1( [2,3], :) E1( [3,2], :) % swap rows 2 and 3 E1 = % generate the 4x4 identity matrix 0 0 0 >> E2 eye (4); % generate the 4x4 identity matrix >> E2 (3,3)--3 % change the entry in position (3,3) to -3 % equivalent to multiply row 3 by -3 E2 >> E3 eye (4);% generate the 4x4 identity matrix >> E3 (3,4)-5 % change the entry in position (3,4) to 5 % equivalent to multiply row 4 by 5 and add to row 3 0 0 Important Property: Suppose that E is an n x n elementary matrix obtained from the identity by performing one of the elem entary row operations. If A is an n r matrix, then the matrix EA is obtained by performing the same row operation on A. EXERCISE 1 If you haven't already done so, enter the commands in Example 1 to generate the elementary matrices E1, E2 and E3 (you can suppress these matrices in your lab report) Generate a random 4 x 3 matrix A (with integer entries), by typing Afloor (10 rand (4,3)) Compute the products E1+A. E2+A and E3#A and compare A with each of the products. Describe the effect of each multiplication on the matrix A. Be specific. For each of the three products describe specifically how the rows of A have changed What general pattern do you see? That is, what effect does multiplying a matrix A on the left by an elementary matrix have on the matrix A? EXERCISE 1 If you haven't already done so, enter the commands in Example 1 to generate the elementary matrices E1, E2 and E3 (you can suppress these matrices in your lab report). Generate a random 4 x 3 matrix A (with integer entries), by typing A-floor (10*rand(4,3)) Compute the products E1+A, E2#A and E3*A and compare A with each of the products. Describe the effect of each multiplication on the matrix A. Be specific. For each of the three products, describe specifically how the rows of A have changed What general pattern do you see? That is, what effect does multiplying a matrix A on the left by an elementary matrix have on the matrix A? The LU factorization using elementary matrices EXERCISE 2 Enter the following matrix in MATLAB 8 -24-1 (a) Determine elementary matrices E1, E2, E of Type II such that E3E2E1A U with U an upper triangular matrix. The matrix E1 should turn the element in position (2,1) into a 0. Enter this matrix in MATLAB as E1 using commands similar to the ones in Example 1. The matrix E2 should turn the element in position (3,1) into a zero. Enter this matrix in MATLAB as E2. Note that to zero out the entries in column 1, you need to add or subtract a multiple of row 1. Once you have found the matrices E1 and E2, compute the product E2E1A in MATLAB. Use format rat so that the entries will be given as fractions. Based on the result, determine the matrix E3 that turns the element in position (3,2) into a zero. Enter this matrix as E3 in MATLAB and compute U-E3*E2 E1*A (b) Compute the product L = Ei E,ESI. The matrix L is lower triangular with ones on the diagonal. Enter format short and verify that ALU by computing A - LU in MATLAB NOTE: From part (a) we have E3E2E1A = U and therefore A = (E3E2E)-1 U (EE2 Esp Since the elementary matrices and their inverses are lower triangular and have 1's along the diagonal, as is always true for elementary matrices of the third type, it follows that L is also lower triangular with 1's along the diagonal. Permutation matrices A permutation matrix is a square matrix that has exactly one 1 in every row and column and O's elsewhere. In this section we will look at properties of permutation matrices. One way to construct permutation matrices is to permute the rows (or columns) of the identity matrix. For example, we can construct 0 1 00 0 E 1 0 0 0 0 by using the MATLAB commands p- [2,3,1,5,4] ; % permutation vector that defines the new order of the rows % define E as the identity matrix E eye (length (p)); E E(p, :) % permute the rows of E according to the % permutation vector p The second command creates the 5x5 identity matrix, and the third command uses the vector p to permute its rows, so row p (1)- 2 becomes row 1, row p (2)-3 becomes row 2, row p (3) 1 becomes row 3 and so on (compare these row permutations with the vector p defined above) EXERCISE 3 If you haven't already done so, enter the commands in the example above to generate the permutation matrix E defined in (2) (you can suppress this matrix) Generate a 5 5 matrix A with integer entries using the command Afloor (10 rand (5)) (a) Compute the product EA and compare the answer with the matrix A. How are the two matrices related? Describe the effect on A of left multiplication by the permutation matrix E. Be specific! Compute the product AE and compare the answer with the matrix A. How are the two matrices related? Describe the effect on A of right multiplication by the permutation matrix E. Be specific! (b) Compute E-1 and ET (recall that ET is computed in MATLAB with the command E'), and observe that they are also permutation matrices. What else do you observe about E-1 and ET The LU factorization in MATLAB Not all matrices have an LU factorization because not all matrices can be reduced to upper triangular form using only row operation of Type III. However, if we allow the rows to be interchanged, then all matrices have an LU factorization (but we have to keep track of the rows we permute) Example 2 The matrix A- 125 does not have an LU factorization. Zeroing out the entries below the pivot in the first column yields and it is impossible to put this matrix in triangular form without permuting the rows. However the matrix PA--15 3 (obtained by interchanging row 2 and row 3 of A) does have an LU factorization. Here P is the permutation matrix 1 0 0 P=10 0 1 In general, for any matrix A, it is always possible to find the LU factorization of PA, where P is an appropriate permutation matrix. The MATLAB command [L,U,P] lu(A) returns a lower triangular matrix L (with 1's on the diagonal), an upper triangular matrix U, and a permutation matrix P so that P*ALU For this example we have 3 >[L,U,P]-1u (A) 0 0 1/2 0 0 and we can easily verify that PA LU. Remark: Note that, even if the LU factorization of A does exist, MATLAB will most likely use a permutation matrix anyway. This is because MATLAB permutes the rows so that the pivot is always the largest entry in the column. This technique, called partial pivoting, reduces round-off errors Solving Systems using the LU factorization Given A- LU, we can solve Ax-b in two steps: (a) First solve Ly b (b) then solve Ux = y Both systems are triangular and therefore can be easily solved using backward and forward substitution We can carry out these two steps using the "command in MATLAEB However, in general, as observed before, MATLAB will return the LU factorization of PA rather than A, thus, instead of solving the system Ax- b we will solve the equivalent system To solve (3) using steps (a) and (b) defined above, we only need to replace b with Pb EXERCISE 4 Enter the matrix A and the vector b in MATLAB 4-9 -3 6 1 3 5 4 62 70 19 5 4 9-7 The exact solution to the system Ax b is the vector x = (-5,-5,-5,-3)T. (a) Enter [L,U,P] -lu(A) to find the LU factorization of the matrix PA. Verify that (b) Use the LU factorization you found in part (a) to solve the system Ax -b. Call the (c) Enter the vector x and compare your solution x.lu from part (b) with the exact solution PA = LU by computing PA-LU. computed solution x.lu (don't forget that you will need P*b) x by computing norm(xlu - x) NOTE: the norm function gives the magnitude of the vector, that is, for a vector a - (ai ,a2, , an)T, the norn of a is defined as: norm (a)-[+ a + +af . Thus the command norm(x.lu - x) measures how close the computed solution xlu is to the exact solution x. You should expect a very small number EXERCISE 5 In this exercise we will compare in MATLAB the speed of two methods for solving the system Ax b when A is an invertible square matrix: computing the RREF and computing the LU factorization. Note that, although the number of operations for obtaining the LU factorization is the same as the gaussian elimination, the LU factorization has the advantage that once the matrix A is decomposed, the substitution step can be carried out efficiently for different values of b. Thus the L factorization is certainly preferable when solving the system Ax-b with different values of b for the same A We will use the MATLAB tic and toc command to measure the computation times Enter: A rand(600) ; one s (600 , 1) ; b=A*x; = x = Important: Be sure to use semicolon after each command so that matrices and vectors are not displayed. Do not print or include these large matrices and vectors in your lab write-up. (a) Solve Ax b using the reduced row echelon form and store the solution in x.rref tic; R= rref ([A, b]); x-rref = R(: , end); toc (make sure that all the commands are on the same line) (b) Solve Ax b using the LU factorization as you did in EXERCISE 4(a) (b), and calculate the elapsed time using the tic toc commands. Store the solution in x.lu. Which method is faster? NOTE: Make sure you use semicolon; the only output should be the elapsed time. Also, don't forget that, when using tic toc all the c should find L,U,P, solve for y, and solve for x_lu all on one line should be in one line, so you (c) Compare the solutions from parts (a) and (b) with the exact solution x by computing norm(x rref - x) and norm(x_lu - x). How accurate are the solutions from parts (a) and (b)? Example We can generate the three matrices listed in (1) using the following MATLAB commands >>E1eye (4) >> E1( [2,3], :) E1( [3,2], :) % swap rows 2 and 3 E1 = % generate the 4x4 identity matrix 0 0 0 >> E2 eye (4); % generate the 4x4 identity matrix >> E2 (3,3)--3 % change the entry in position (3,3) to -3 % equivalent to multiply row 3 by -3 E2 >> E3 eye (4);% generate the 4x4 identity matrix >> E3 (3,4)-5 % change the entry in position (3,4) to 5 % equivalent to multiply row 4 by 5 and add to row 3 0 0 Important Property: Suppose that E is an n x n elementary matrix obtained from the identity by performing one of the elem entary row operations. If A is an n r matrix, then the matrix EA is obtained by performing the same row operation on A. EXERCISE 1 If you haven't already done so, enter the commands in Example 1 to generate the elementary matrices E1, E2 and E3 (you can suppress these matrices in your lab report) Generate a random 4 x 3 matrix A (with integer entries), by typing Afloor (10 rand (4,3)) Compute the products E1+A. E2+A and E3#A and compare A with each of the products. Describe the effect of each multiplication on the matrix A. Be specific. For each of the three products describe specifically how the rows of A have changed What general pattern do you see? That is, what effect does multiplying a matrix A on the left by an elementary matrix have on the matrix A? EXERCISE 1 If you haven't already done so, enter the commands in Example 1 to generate the elementary matrices E1, E2 and E3 (you can suppress these matrices in your lab report). Generate a random 4 x 3 matrix A (with integer entries), by typing A-floor (10*rand(4,3)) Compute the products E1+A, E2#A and E3*A and compare A with each of the products. Describe the effect of each multiplication on the matrix A. Be specific. For each of the three products, describe specifically how the rows of A have changed What general pattern do you see? That is, what effect does multiplying a matrix A on the left by an elementary matrix have on the matrix A? The LU factorization using elementary matrices EXERCISE 2 Enter the following matrix in MATLAB 8 -24-1 (a) Determine elementary matrices E1, E2, E of Type II such that E3E2E1A U with U an upper triangular matrix. The matrix E1 should turn the element in position (2,1) into a 0. Enter this matrix in MATLAB as E1 using commands similar to the ones in Example 1. The matrix E2 should turn the element in position (3,1) into a zero. Enter this matrix in MATLAB as E2. Note that to zero out the entries in column 1, you need to add or subtract a multiple of row 1. Once you have found the matrices E1 and E2, compute the product E2E1A in MATLAB. Use format rat so that the entries will be given as fractions. Based on the result, determine the matrix E3 that turns the element in position (3,2) into a zero. Enter this matrix as E3 in MATLAB and compute U-E3*E2 E1*A (b) Compute the product L = Ei E,ESI. The matrix L is lower triangular with ones on the diagonal. Enter format short and verify that ALU by computing A - LU in MATLAB NOTE: From part (a) we have E3E2E1A = U and therefore A = (E3E2E)-1 U (EE2 Esp Since the elementary matrices and their inverses are lower triangular and have 1's along the diagonal, as is always true for elementary matrices of the third type, it follows that L is also lower triangular with 1's along the diagonal. Permutation matrices A permutation matrix is a square matrix that has exactly one 1 in every row and column and O's elsewhere. In this section we will look at properties of permutation matrices. One way to construct permutation matrices is to permute the rows (or columns) of the identity matrix. For example, we can construct 0 1 00 0 E 1 0 0 0 0 by using the MATLAB commands p- [2,3,1,5,4] ; % permutation vector that defines the new order of the rows % define E as the identity matrix E eye (length (p)); E E(p, :) % permute the rows of E according to the % permutation vector p The second command creates the 5x5 identity matrix, and the third command uses the vector p to permute its rows, so row p (1)- 2 becomes row 1, row p (2)-3 becomes row 2, row p (3) 1 becomes row 3 and so on (compare these row permutations with the vector p defined above) EXERCISE 3 If you haven't already done so, enter the commands in the example above to generate the permutation matrix E defined in (2) (you can suppress this matrix) Generate a 5 5 matrix A with integer entries using the command Afloor (10 rand (5)) (a) Compute the product EA and compare the answer with the matrix A. How are the two matrices related? Describe the effect on A of left multiplication by the permutation matrix E. Be specific! Compute the product AE and compare the answer with the matrix A. How are the two matrices related? Describe the effect on A of right multiplication by the permutation matrix E. Be specific! (b) Compute E-1 and ET (recall that ET is computed in MATLAB with the command E'), and observe that they are also permutation matrices. What else do you observe about E-1 and ET The LU factorization in MATLAB Not all matrices have an LU factorization because not all matrices can be reduced to upper triangular form using only row operation of Type III. However, if we allow the rows to be interchanged, then all matrices have an LU factorization (but we have to keep track of the rows we permute) Example 2 The matrix A- 125 does not have an LU factorization. Zeroing out the entries below the pivot in the first column yields and it is impossible to put this matrix in triangular form without permuting the rows. However the matrix PA--15 3 (obtained by interchanging row 2 and row 3 of A) does have an LU factorization. Here P is the permutation matrix 1 0 0 P=10 0 1 In general, for any matrix A, it is always possible to find the LU factorization of PA, where P is an appropriate permutation matrix. The MATLAB command [L,U,P] lu(A) returns a lower triangular matrix L (with 1's on the diagonal), an upper triangular matrix U, and a permutation matrix P so that P*ALU For this example we have 3 >[L,U,P]-1u (A) 0 0 1/2 0 0 and we can easily verify that PA LU. Remark: Note that, even if the LU factorization of A does exist, MATLAB will most likely use a permutation matrix anyway. This is because MATLAB permutes the rows so that the pivot is always the largest entry in the column. This technique, called partial pivoting, reduces round-off errors Solving Systems using the LU factorization Given A- LU, we can solve Ax-b in two steps: (a) First solve Ly b (b) then solve Ux = y Both systems are triangular and therefore can be easily solved using backward and forward substitution We can carry out these two steps using the "command in MATLAEB However, in general, as observed before, MATLAB will return the LU factorization of PA rather than A, thus, instead of solving the system Ax- b we will solve the equivalent system To solve (3) using steps (a) and (b) defined above, we only need to replace b with Pb EXERCISE 4 Enter the matrix A and the vector b in MATLAB 4-9 -3 6 1 3 5 4 62 70 19 5 4 9-7 The exact solution to the system Ax b is the vector x = (-5,-5,-5,-3)T. (a) Enter [L,U,P] -lu(A) to find the LU factorization of the matrix PA. Verify that (b) Use the LU factorization you found in part (a) to solve the system Ax -b. Call the (c) Enter the vector x and compare your solution x.lu from part (b) with the exact solution PA = LU by computing PA-LU. computed solution x.lu (don't forget that you will need P*b) x by computing norm(xlu - x) NOTE: the norm function gives the magnitude of the vector, that is, for a vector a - (ai ,a2, , an)T, the norn of a is defined as: norm (a)-[+ a + +af . Thus the command norm(x.lu - x) measures how close the computed solution xlu is to the exact solution x. You should expect a very small number EXERCISE 5 In this exercise we will compare in MATLAB the speed of two methods for solving the system Ax b when A is an invertible square matrix: computing the RREF and computing the LU factorization. Note that, although the number of operations for obtaining the LU factorization is the same as the gaussian elimination, the LU factorization has the advantage that once the matrix A is decomposed, the substitution step can be carried out efficiently for different values of b. Thus the L factorization is certainly preferable when solving the system Ax-b with different values of b for the same A We will use the MATLAB tic and toc command to measure the computation times Enter: A rand(600) ; one s (600 , 1) ; b=A*x; = x = Important: Be sure to use semicolon after each command so that matrices and vectors are not displayed. Do not print or include these large matrices and vectors in your lab write-up. (a) Solve Ax b using the reduced row echelon form and store the solution in x.rref tic; R= rref ([A, b]); x-rref = R(: , end); toc (make sure that all the commands are on the same line) (b) Solve Ax b using the LU factorization as you did in EXERCISE 4(a) (b), and calculate the elapsed time using the tic toc commands. Store the solution in x.lu. Which method is faster? NOTE: Make sure you use semicolon; the only output should be the elapsed time. Also, don't forget that, when using tic toc all the c should find L,U,P, solve for y, and solve for x_lu all on one line should be in one line, so you (c) Compare the solutions from parts (a) and (b) with the exact solution x by computing norm(x rref - x) and norm(x_lu - x). How accurate are the solutions from parts (a) and (b)
