§4.1 Elementary Row Operations
As has been mentioned in class, there are three different types of elementary row operation. They are as follows:Type 1:
Multiply row i by a constant c.Type 2:
Exchange row i and row j.Type 3:
Add a multiple of row i to row j.For a simple example, let us consider the matrix [ 1 2 3; 4 5 6 ; 7 8 9]. If we apply a type 1 operation to row 2, with constant 3, we get the matrix [ 1 2 3; 12 15 18 ; 7 8 9 ]. If we apply operation 2 to rows 1 and 2 then we obtain [ 4 5 6 ; 1 2 3 ; 7 8 9 ]. And if we add 3 times row 2 to row 3 we obtain [ 1 2 3; 4 5 6 ; 19 23 27 ]. Associated with each elementary row operation is an elementary matrix which is obtained by performing the elementary row operation on the identity matrix. So elementary matrices give us a way of storing information about row operations.
|
|
Exercise 4.1
What are the elementary matrices associated with the above operations?
|
§4.2 Finding Inverses
As you have also seen in class, it is possible to use row reduction to find the inverse of a matrix. In this section, we are going to verify this using MATLAB, and we are also going to see what happens if we attempt this on a matrix which is not invertible.Enter the following matrix:
>>A = [ 3 3 6 ; 5 9 3 ; 9 -7 10 ]
| Exercise 4.2 | |
|
(a) Type into MATLAB a 3x6 matrix B which is obtained by joining the 3x3 identity matrix to A (on the right). This can be done in MATLAB using the code B = [A eye(3)]. |
|
|
(b) Using the MATLAB function rref(), find the reduced row echelon form of B. Call it C. This can be done by using the MATLAB code C = rref(B). |
|
|
(c) Verify that the matrix consisting of the last three columns of C is the inverse of A, using the MATLAB function inv(). There is an easy way to extract the last three columns of the matrix C: Use the MATLAB code D = C(:,4:6) |
Now we are going to see what happens if we attempt the above on a singular matrix.
| Exercise 4.3 | |
|
|
(a)
Let E be the singular matrix >>E = [ -1 7 -3 ; 1 -7 3 ; -2 6 -4 ] Using MATLAB or otherwise, verify that E is singular. |
|
|
(b) Repeat the steps in Exercise 4.2 (a) and (b) using the above matrix E. |
|
|
(c) Verify that the matrix consisting of the last three columns of the 3x6 matrix obtained above is not the inverse of E. |
§4.3 LU-Factorization
Let A be a matrix. Then it is possible to find a lower-triangular matrix L and an upper-triangular matrix U such that A = LU. For a more in-depth discussion of how this factorization is obtained see section 2.5 in Linear Algebra and its Applications by David C. Lay. We need not worry too much about how the factorization is obtained, since we are going to use MATLAB to compute them for us, using the function lu().This function can be executed in a few different ways; below are the two we are going to use. Let A be a matrix. Then typing
>> [L,U] = lu(A)
will return a lower-triangular matrix L with its rows permuted (possibly), and an upper-triangular matrix U such that A = LU. Typing
>> [L, U, P] = lu(A)
will return a lower-triangular matrix L; an upper-triangular matrix U; and a permutation matrix P such that PA = LU. If you do not know what a permutation matrix is then do not worry - you will still be able to complete this lab.
| Exercise 4.4 | |
|
|
(a)
Let A be the matrix >> A = [2 8 2; -3 -8 0 ; 3 9 2 ] Use the first method described above to obtain L and U. Verify that A = LU. |
|
|
(b) Using the same matrix as above, use the second method to obtain L, U, and P. Verify that PA = LU. |
|
|
(c)
Let B be the matrix >> B = [1 0 -2 ; -3 1 4 ; 2 -3 4 ] (b) Use the second method to obtain L, U, and P. Verify that PB - LU does not equal zero. Why do you think this is? |
§4.4 Solving Ax=b
We have already seen that if A is non-singular then we can row reduce the matrix [ A b ] to obtain the solution. It is also possible to first find L and U such that A = LU, then solve Ly = b and Ux = y. The second thing seems a great deal more cumbersome--let us see why it is not:| Exercise 4.5 | |
|
|
(a)
Let A be the matrix >> A = [ 5 9 2 ; 2 6 3 ; -3 -8 1 ] Find the LU-factorization of A, using MATLAB. |
|
|
(b)
Let b be the vector >> b = [-5 ; 2 ; 2 ] By hand, solve Ly = b and Ux = y. What makes it easier than expected? |
Let us see how using rref() compares to using LU-factorization with regards to execution time and accuracy.
To calculate execution time we are going to use the MATLAB function clock which, when called, gives the contents of the computer clock at that moment; and the function etime(x,y) which calculates the time elapsed between time y and time x, in seconds.
| Exercise 4.6 | |
|
|
(a)
Enter the command >> N=20 Using the following commands, create a random NxN matrix A containing integers between 0 and 10, and a random vector b with N components containing integers between 0 and 10:
>> A = round(10*rand(N)) |
|
|
(b)
To calculate the time taken using rref(),
use the commands >> t0 = clock; B = rref([A b]); x = B(:, N+1); rreftime = etime(clock, t0) Note that all of the above must be on the same line. rreftime is the time it took for rref to solve Ax=b. |
Instead of constructing a program which uses LU-factorization to solve Ax=b we are going to make use of the fact that there is already a built-in program which does just that. Typing the following
>> A\b
returns the solution (if it exists) computed using LU -factorization.
| Exercise 4.7 | |
|
|
(a)
To calculate the time taken using LU-factorization, use the command >> t0 = clock; y = A\b; lutime = etime(clock , t0) lutime is the time take by the LU-factorisation method to solve Ax=b. |
|
|
(c) Which of the two methods is quicker? Repeat the experiment for a few different values of N. How does the difference in time vary with N? |
To compare the accuracy of the solutions we are going to use the MATLAB function norm() to compute the 'distance' between b and Ax; and b and Ay . The solution which is 'further' away is less accurate.
| Exercise 4.8 | |
|
|
(a)
Ask MATLAB to compute >> norm(b-Ax) and >> norm(b-Ay) |
|
|
(b) Which method is more accurate? Repeat the experiment for a few different N. How does the accuracy vary with N? |
Last Modified:
09/18/04