You may not consult anyone other than the instructor or the class TAs regarding this exam. If you do obtain any information about how to do this exam, inadvertently or otherwise, you must disclose it to the course instructor by email or contacting him personally. Generally, disclosing the fact you were informed about a portion of the exam will be viewed favorably, especially in the case where it was inadvertent. The purpose is to help me grade fairly.
The materials you may consult are your notes from class, the course book, the other programs you wrote for the class and the one web site listed right after this paragraph. You may not consult other web sites or google. If you have questions about the math, consult the instructor! The following web site gives a good overview of the process:
http://www.gregthatcher.com/Mathematics ... ordan.aspx
After you create the matrix on this web page, you can edit the entries. To test row-swapping, change the entries in columns 1 and 2 of the second row to be the same as the entries in the first row. This will make the 2, 2 element zero, which will require that two rows be swapped.
The Project:
This project is to write a FORTRAN77 program that uses Gauss-Jordan elimination with row pivoting to solve a system of linear algebraic equations. I decided to break the project into parts to make it more organized. You must do each part and submit a program for each part that asks you to write an F77 program. Your program will solve a system of linear algebraic equations of the form Ax=b, where A and b are given. The dimensions of A and b will also be given as part of the program and it is acceptable to hard-code into your program some assumed limits, e.g.,
Code: Select all
real A(200,200)What to do:
- First, you need to be able to generate your own matrices where you know the answer so you can test your program. Here is one way to do it. In matlab, the command
will generate a matrix of 8x8 integers between 0 and 9. Figure out how to modify the code to generate an nxn matrix with integers between -9 and +9.
Code: Select all
n = 8 A = floor(rand(n,n)*10)
You need to check that the matrix is full rank, which is the case when Ax=b will always have a unique solution. If the determinant is not zero, then it is full rank, so in matlab typeand if it's not zero, then you are good to go. You can make up a random x vector using the same procedure to generate A outlined above, or just type your own. I would recommend typing your own with some sort of pattern in it so it's easy to tell when you are getting the right answer:Code: Select all
det(A)The single quote after the vector takes the transpose, so that the Ax is lined up properly. Then you can compute b byCode: Select all
x = [1 2 3 4 5 6 7 8]'
So, the way the problem is given is that you are given A and b and must compute x.b=A*x - Your program needs to load in A and b from a data file. The data file will have n^2+n+1 numbers in it. They will all look like integers, but when you do all the row reduction stuff it result in floating point numbers, so read the data for A and b in as reals or doubles.
The format of the data file is the very first number is an INTEGER which is n. The next n^2 numbers are A where the first n of those are the first row of A, then second n are the second row, etc. In other words, the numbers go across the rows. Your answer will be different if you read them in as columns instead of rows. In the data files I provide A is in the file in an obvious way. The last n numbers are b.
Put the data for your made-up A and b into a data file in this format.
The files that are provided are called dataX.d: The largest matrix size in these files is 100x100. - The program I showed in the last lecture will read in the data properly. Run it on your data file to make sure it works properly. If it doesn't fix it.
- (20 points) Modify the program provided in the previous step to perform elementary row operations to make the first diagonal element, a(1,1), equal to 1. Then perform elementary row operations so that each of the elements under the diagonal in the first column are equal to zero. Make sure that you do the same operations on b. This is something that is each to check by hand if you print out the matrix after each step. Save this program as program1.f, print it and upload it to the course web page. I do NOT want just the final program that does everything, but each step in the process.
- (20 points) Copy program1.f to program2.f and modify it so that it loops through all the columns and uses elementary row operations to make the elements below the diagonal equal to zero. At this point you do not have to check the size of the element on the diagonal. If your program runs into problems, there is a small chance that is happening, so printing the size of a(i,i) before you divide the row by it may be worth doing. At this point A will be reduced to an upper triangular form with ones on the diagonal. If you are using your own A and b, then the very last element in the reduced b vector should be equal to the last element in x (explain why this is true), and if that is the case, your program is probably working correctly.
- (20 points) Copy program2.f to program3.f and modify it so that it loops through all the columns again and puts zeros above all the diagonal elements. After this step, A should be reduced to the identity matrix and b will be modified to be equal to x, i.e., the answer! Pivoting has not been implemented yet, so, just like above, there is a chance that your program will encounter a zero or very small diagonal element, which would cause problems.
- (20 points) Copy program3.f to program4.f. To deal with small diagonal elements, during the forward reduction phase (which is when you are making the elements below the diagonal zero), row shifting should be used to put the element with the largest magnitude at or below the diagonal element into the pivot position. You should use your subroutine from your previous homework to do the row shifting. So, before you make any diagonal element equal to one, you search down the column below it to find the element with the largest magnitude and switch the rows so that element is on the diagonal. Do this every time, not just when the diagonal term is small.
- (20 points) If the largest magnitude possible for a pivot term is less than 10E-4, i.e., the diagonal element itself and all the elements below it have a very small magnitude, a warning message should be printed that the matrix is ill-conditioned and the program should stop. This will happen mathematically when Ax=b has no solution. You can rig your own matrix to have this feature by deleting a row or column and making it an exact multiple of one of the other ones.
- Test your program on the data files linked above. Your final program should always use row shifting, but for debugging purposes, the first file should work without row shifting. The second file requires row shifting. I don't know what will happen with the third file. The fourth file has a matrix A and vector b for which there is no solution x, so your program should print a warning for that.
The project is due at 5:00pm, Friday December 3, 2010 in my office, 365B Fitzpatrick. I will have a box to submit stuff either right outside my door or in my office. Unless you have an official excuse from the Office of Student Affairs, there will be no extensions. I am leaving for a conference that weekend and plan to grade them when traveling.
- On each program put
- name
- NDID number
- user name on this forum (so I can search for your programs if necessary).
- Submit printouts of all the programs as well as the "answers." For the larger problems, the answers had a pattern to them, so you don't have to submit 100 numbers, just something like the answer was "[10 20 10 20 10 20...]".
- Submit the answer for each of the data files given as well as the one for your own made-up matrix. Also upload your made-up data file so I can check it if necessary.
- Upload all your programs (and your data file) to the course web page.
- Document your program with comments so it is easy to grade.