辅导案例-MA117
MA117 Programming for Scientists: Project 3 Deadline: Noon, Monday 4th May 2020 MA117 Project 3: Determinants of Matrices Administrative Details • This project is the third of the three assignments required for the assessment in this course. It is to be submitted by Noon, Monday 4th May 2020. Details of the method of the submission via the Tabula system have been described in the lecture notes and are also available on the course web page. • This assignment will count for 40% of your total grade in the course. • The automated submission system requires that you closely follow instructions about the format of certain files; failure to do so will result in the severe loss of points in this assessment. • You may work on the assignment during the lab session, provided you have completed the other tasks that have been set. You can use the work areas at all times when they are not booked for teaching, 7 days per week. If you are working on the assignment on your home system you are advised to make regular back-up copies (for example by transferring the files to the University systems). You should note that no allowance will be made for domestic disasters involving your own computer system. You should make sure well ahead of the deadline that you are able to transfer all necessary files to the University system and that it works there as well. • The Tabula system will be open for the submission of this assignment starting from 23rd April 2020. You will not be able to test your code for correctness using Tabula but you can resubmit your work several times, until the deadline, if you find a mistake after your submission. A later submission always replaces the older one, but you have to re-submit all files. • Remember that all work you submit should be your own work. Do not be tempted to copy work; this assignment is not meant to be a team exercise. There are both human and automated techniques to detect pieces of the code which have been copied from others. If you are stuck then ask for assistance in the lab sessions. TAs will not complete the exercise for you but they will help if you do not understand the problem, are confused by an error message, need advice on how to debug the code, require further explanation of a feature of Java or similar matters. • If you have more general or administrative problems e-mail me immediately. Always include the course number (MA117) in the subject of your e-mail. 1 Formulation of the Problem Matrices are one of the most important mathematical concepts to be modelled by computer, being used in many problems from solving simple linear systems to modelling complex partial differential equations. Whilst a matrix (in our formulation) is simply an element of the vector space Rm⇥n, it usually possesses some structure which we can exploit to gain computational speed. For example, a matrix-matrix multiplication generally requires of the order of n3 floating-point operations. If the matrix has some special structure which we can exploit using a clever method, then we might be able to reduce this to n operations. For large values of n, this significantly improves the performance of our code. 1 MA117 Programming for Scientists: Project 3 Deadline: Noon, Monday 4th May 2020 In this project, you will write two classes representing matrices of the form: A = 264a11 . . . a1n... . . . ... am1 . . . amn 375 and B = 266664 b11 b12 0 0 0 b21 b22 b23 0 0 0 b32 b33 b34 0 0 0 b43 b44 b45 0 0 0 b54 b55 377775 A is a dense m ⇥ n matrix which, in general, has no special structure and no zero entries. B is a tri-diagonal matrix, where all entries are zero apart from along the diagonal and upper and lower diagonals. Note that although B is only a 5⇥ 5 matrix, your classes should represent a general n⇥ n tri-diagonal matrix. Also, the tri-diagonal matrices you need to represent will always be square. In a similar fashion to Fraction, you will then write functions to perform various matrix operations: 1. addition and subtraction; 2. scalar and matrix-matrix multiplication; 3. calculating the determinant of the matrix. Clearly calculating the determinant is the most tricky task here. Probably you will already have seen expansion by minors as a possible method. Whilst this is an excellent method for calculating determinants by hand, you should not use it for this task. The reason is that calculating the determinant of a n⇥n matrix requires O(n!) operations, since for each n⇥n matrix, we must calculate the values of the n 1 sub-determinants. This is extremely slow. A much better method is called LU decomposition. In this, we write a matrix A as product of two matrices L and U which are lower- and upper- triangular respectively. For example, for a 4⇥4 matrix, we would find matrices so that2664 a11 a12 a13 a14 a21 a22 a23 a24 a31 a32 a33 a34 a41 a42 a43 a44 3775 | {z } A = 2664 l11 0 0 0 l21 l22 0 0 l31 l32 l33 0 l41 l42 l43 l44 3775 | {z } L 2664 u11 u12 u13 u14 0 u22 u23 u24 0 0 u33 u34 0 0 0 u44 3775 | {z } U Such a factorisation is not guaranteed to exist (and indeed is not unique), but typically it does. In this project, you don’t really need to worry about this – your code will be tested with matrices for which the LU decomposition exists. It is up to you to figure out how to calculate the determinant from the LU decomposition! Throughout the formulation, matrices will be represented by indices running between 1 i, j m,n. However, in your code, you should stay consistent with Java notation and indices should start at 0 (i.e. 0 i, j m 1, n 1). 2 Programming Instructions On the course web page for the project you will find files for the following classes. As with the previous projects, the files have some predefined methods that are either complete or come with predefined names and parameters. You must keep all names of public objects and methods as they are in the templates. Other methods have to be filled in and it is up to you to design them properly. There are five classes in this project: • Matrix: a general class defining the basic properties and operations on matrices. 2 MA117 Programming for Scientists: Project 3 Deadline: Noon, Monday 4th May 2020 • MatrixException: a subclass of the RuntimeException class which you should use to throw matrix-related exceptions. This class is complete – you do not need to alter it. • GeneralMatrix: a subclass of Matrix which describes a general m⇥ n real matrix. • TriMatrix: another subclass of Matrix which describes a n⇥ n real tri-diagonal matrix. • Project3: a completely separate class which will use Matrix and its subclasses to collect some basic statistics involving random matrices. Please note that unlike other projects, you may not assume that the data you receive will be valid. Therefore you will need to check, amongst other things, that matrix multiplications are done using matrices of valid sizes, the user is not trying to access matrix elements which are out of bounds, etc. If something goes wrong, you are expected to throw a MatrixException. The classes you need to work on are briefly described below. 2.1 The Matrix class This is the base class from which you will build your specialised subclasses. Matrix is abstract – as described in the lectures, this means that some of the methods are not defined, and they need to be implemented in the subclasses. The general idea is that each subclass of Matrix can implement its own storage schemes, whilst still maintaining various common methods inherent in all matrices. In particular, the following functions are not abstract, and need to be filled in inside Matrix: • the protected constructor function; • toString, which should return a String representation of the matrix. Additionally, the following abstract methods will be implemented by the subclasses of Matrix: • getIJ and setIJ: accessor and mutator methods to get/set the ijth entry of the matrix. • add: returns a new Matrix containing the sum of the current matrix with another. • multiply(double a): multiply the matrix by a constant a 2 R. • multiply(Matrix B): multiply the matrix by another matrix. Note that this is intended to be a left multiplication; i.e. A.multiply(B) corresponds to the multiplication AB. • random(): fills current the matrix with random numbers, uniformly distributed between 0 and 1. For a tri-diagonal matrix, this should fill the three diagonals with random numbers. In subclasses, you should pay attention to what type of matrix needs to be returned from each of the functions. For example, when adding two GeneralMatrix objects the result should be a GeneralMatrix (which is then typecast to a Matrix). 2.2 The GeneralMatrix class GeneralMatrix represents a full m⇥ n matrix and extends Matrix. 1. The matrix will be stored in a private two-dimensional array. 2. You should implement all of the functions mentioned above using the standard formulae from linear algebra to do so, as well as the usual constructors, accessor and mutator methods. 3. You may choose whatever method you want to calculate the determinant of the matrix. However, it is strongly recommended you use the provided decomp function, which will perform LU decomposition for you since the algorithm is quite tricky for n⇥ n matrices. 3 MA117 Programming for Scientists: Project 3 Deadline: Noon, Monday 4th May 2020 To call decomp, you should pass it a double array d of length 1. It will return a new GeneralMatrix storing both L = (lij) and U = (uij). For instance, when n = 5, the matrix returned is266664 u11 u12 u13 u14 u15 l21 u22 u23 u24 u25 l31 l32 u33 u34 u35 l41 l42 l43 u44 u45 l51 l52 l53 l54 u55 377775 The reason we can store it in this compact form is that the algorithm insists that lii = 1 for every i, and so this information can be omitted from the array. On exit, the double inside the array you passed in will have a value of 1 or 1. You should multiply the calculated determinant by this value so that it has the correct sign. This constant arises because the decomposition algorithm will flip rows in the matrix to aid with singular matrices, thus changing the sign of the determinant. As a result, if you explicitly perform the multiplication LU , you probably won’t get the original matrix back again, but rather a permutation of it. For example, consider a matrix J which is a slightly altered identity matrix. J = 2664 1 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 3775 decompose J ! LU = 2664 1 0 0 0 0 1 1 0 0 1 0 0 0 0 0 1 3775 6= J In the algorithm, one row was was swapped, so d[0] will be 1. 2.3 The TriMatrix class TriMatrix represents a tri-diagonal matrix of size n⇥n and extends Matrix. The constructor therefore only accepts a single parameter. 1. Tri-diagonal matrices are never stored in full two-dimensional arrays because they are sparse – that is, most of the entres are zero. Instead, we use three arrays of doubles: diag, upper and lower. These store the diagonal, upper-diagonal and lower-diagonal elements respectively. In this form, the matrix looks like T = 2666666664 d1 u1 l2 d2 u2 l3 d3 u3 l4 d4 . . . . . . . . . un 1 ln dn 3777777775 diag should therefore be of length n, whereas upper and lower should be of length n 1. 2. For this class, you will need to implement your own decompmethod to perform LU decomposition, which should not be copied from GeneralMatrix, since the algorithm for a tri-diagonal matrix is very simple to derive. First, we assume that the diagonal elements of the lower-diagonal matrix 4 MA117 Programming for Scientists: Project 3 Deadline: Noon, Monday 4th May 2020 L are 1. Then, you should show that the matrix product2666664 1 l⇤2 1 l⇤3 1 . . . . . . l⇤n 1 3777775 | {z } L 2666664 d⇤1 u⇤1 d⇤2 u⇤2 . . . . . . d⇤n 1 u⇤n 1 d⇤n 3777775 | {z } U is tri-diagonal. Finally, set the product equal to the matrix T above, and equate co-efficients to find a difference relation for each of the d⇤i , u⇤i and l⇤i . Just like the decomp method above, you can then store the matrix in a compact form inside a TriMatrix. 2.4 The Project3 class The final part of this project is to generate some simple statistics on random matrices. Here, the definition of random is that each co-efficient of the matrix M will have Mij ⇠ U(0, 1) (i.e. a uniformly distributed random number between 0 and 1). X = det(M) is a random variable: the question is, how is X distributed? In particular, you will estimate the variance 2 = var(X) by generating a number of random matrices of various sizes, and then calculate the determinant of each of the samples. Project3 contains two functions to aid you in this endeavour. It is not meant to be challenging – indeed, it is probably the easiest part of the assignment! • matVariance(): This function will be passed a Matrix object and an integer Nsamp. It should generate random matrices Mi for 1 i Nsamp by calling the random function on the passed matrix. The variance is estimated by