MATH2019 Introduction to Scientific Computation — Coursework 2 (5%) — Update (12 Nov): Small update in Question 5?. Submission deadline: 4pm, Monday, 18 Nov 2019 This coursework contributes 5% towards the overall grade for the module. Rules: • Each student is to submit their own coursework. • You are allowed to work together and discuss in small groups (2 to 3 people), but you must write your own coursework and program all code by yourself. • Please be informed of the UoN Academic Misconduct Policy (incl. plagiarism, false authorship, and collusion). Coursework Aim & Assessment: • In this coursework you will develop Matlab code related to direct methods for solving linear systems of equations, and you will study some of the methods’ behaviour. • A total of 20 points can be obtained in this coursework. The weighting is enclosed in brackets for each question, e.g. [2 / 20]. • Some marking criteria: Correctness of numerical output, clarity of code and comments, completeness of figures (title, axis labels, legend, etc) and tables, clear and concise answers to open questions, . . . • See Moodle: Assessed Coursework 2 for dedicated grading criteria per question. Some Advice: • You are expected to have basic familiarity with Matlab (in particular: vectors and matrices, plotting, logic and loops, function handles, writing functions and m-files, publishing m-files). • Helpful resources: Matlab Guide (by Tom Wicks), Matlab’s Online Documentation • Write your code as neatly and concisely as possible so that it is easy to follow. • Add some comments to your scripts that indicate what a piece of code does. • Remember to format output using for example disp, num2str or fprintf. • Questions with a “?” are more tedious, but can be safely skipped, as they don’t affect follow- up questions. Getting Started: • Download the contents of the “Coursework 2 Pack” folder from Moodle. • Do the coursework by simply adding MATLAB code to the given files cw2.m, forwardElim.m, forwardElimCP.m and forwardElimLU.m. • Your responses to the numbered questions below should be written in cw2.m, except the responses to questions 1, 4, 6, which involve the completion of the other m-files. Submission Procedure: The coursework is to be submitted using the “Assessed Course- work 2” assignment on Moodle. A complete submission consists of the following files: • 6 m-files: cw2.m, forwardElim.m, forwardElimCP.m, forwardElimLU.m, testMat.m, backwardSub.m • 1 PDF file: cw2.pdf This PDF file is created using Matlab “Publish” on cw2.m. (See for example Section 1.2.9 of the Matlab Guide (by Tom Wicks) for instructions on publishing.) (Other files can be submitted, but only if they are referred to in cw2.m and cw2.pdf, and their relevance is explained.) School of Mathematical Sciences — Version: 12th November, 2019 — Lecturer: Dr Kris van der Zee Page 1 of 5 I Gaussian elimination without pivoting To solve a n × n linear system of equations, consider the Gaussian elimination algorithm consisting of forward elimination without row interchanges and backward substitution. Recall from Lecture 4 that the forward-elimination step consists of n−1 rounds of row-operations: for i = 1, . . . , n− 1 for j = i+ 1, . . . , n Ej − aji aii Ei → Ej end end 1 [5 / 20]Modify the function m-file forwardElim.m. This function m-file should implement the forward-elimination step, and has the following prototype: function Am = forwardElim(A,m) where A is an n × (n+1) augmented matrix, m is an integer with 1 ≤ m ≤ n, and the output Am is the augmented matrix after applying m−1 rounds within the forward-elimination process. Hint: In other words, when m = 1, then Am = A. When m = 2, then Am is the matrix obtained after one round of row-operations, which is the matrix obtained at the end of the above for-loop when i = 1. This matrix has zeros in the first column in all the rows below the pivot a11. When m = 3, then Am is the matrix obtained at the end of the above for-loop when i = 2, and this matrix has zeros in the first and second column under the pivots a11 and a22, respectively. Etcetera. . . When m = n, then Am has the final echelon form obtained at the end of the entire forward-elimination step. 2 [2 / 20]Consider the system of linear equations corresponding to the augmented ma- trix A˜ = A˜(1) given by A˜(1) = 1 −1 2 −1 −8 1 1 1 0 −2 2 0 2 −2 −14 1 −3 6 3 2 • By using your forwardElim.m, compute the augmented matrices A˜(2), A˜(3), and A˜(4), obtained in the forward-elimination step after applying 1, 2 and 3 rounds of row-operations, respectively. Make sure your outputs are visible when “pub- lishing” cw2.m as a PDF. • Then, apply the function m-file backwardSub.m to the echelon matrix A˜(4) to obtain the solution vector x. Note that backwardSub.m already contains a com- plete implementation of the backward-elimination step. Hint: You should verify that the solution is (the column vector) x = [−7; 3; 2; 2]. MATH2019 Coursework 2 Page 2 of 5 I Timing the operations in forwardElim and backwardSub 3 [4 / 20]Consider the matrix A of size n × n and vector b of size n × 1 as provided by the function [A, b] = testMat(n). Take a large range of values for n (for example, n = 50, 100, 150, 200, . . . , 950, 1000, . . . up to some large number that depends on how powerful your computer is, and how much patience you have), and use Matlab to compute the time it takes for your forwardElim.m to obtain the final echelon form for the augmented matrix [A b], as well as the time it takes for backwardSub.m to subsequently obtain the solution vector. • Plot the computed time for forwardElim.m versus n in a figure using loglog, and plot in the same figure the computed time for backwardSub.m. Hint: Use tic and toc to set Matlab’s stopwatch. (Don’t forget to polish your figure: axis labels, legend, grid, . . .) • Based on your plots, provide an explanation for the observed behaviour of the timings for large n. (There is no need to explain the randomn fluctuating behaviour for small n.) I Gaussian elimination with complete pivoting Now consider Gaussian elimination with forward elimination using complete pivoting as discussed in Lecture 5. Recall that the pivoting is carried out at the start of each round before performing the usual row operations. 4? [3 / 20]Complete the function m-file forwardElimCP.m. The function has the following prototype: function Am = forwardElimCP(A,m) where A is an augmented matrix of size n×(n+1), m is an integer with 1 ≤ m ≤ n, and the output Am is the augmented matrix after applying m−1 rounds within the forward-elimination process. Hint: To find a maximum in some vector (or matrix), you can use the Matlab function max (see help max for more info). For the absolute value use abs. 5? [2 / 20]• Repeat Question 2, but now using your forwardElimCP.m and in the case of the augmented matrix B˜ = B˜(1) given by B˜(1) = 0 −1 2 −1 0 1 −1 1 0 −9 2 −2 3 −3 −21 1 −1 4 3 6 Hence, simply obtain B˜(2), B˜(3) and B˜(4), and apply backwardSub.m to B˜(4). There is no need to verify the solution. Note: For this matrix, the previ- ous forwardElim.m (without pivoting) can not be applied. • Repeat Question 2, but now using your forwardElimCP.m and in the case of the same matrix A˜ = A˜(1) given in Question 2. Explain why applying backwardSub.m now to A˜(4) does not give the same result as in Question 2. MATH2019 Coursework 2 Page 3 of 5 I LU factorisation Consider the LU factorisation of a n × n matrix A (see Lecture 6). Theorem 6.19 provides the general form for the matrix L and U . 6 [2 / 20]Use the code that you wrote for forwardElim.m as a starting point for the com- pletion of the function forwardElimLU.m, which has the following prototype: function [L,U] = forwardElimLU(A) This function implements the same algorithm as forwardElim.m and outputs the final echelon form in the variable U. Additionally, it outputs the lower-triangular matrix L as defined in Theorem 6.19
(see Lecture 6). 7 [1 / 20]Apply your forwardElimLU.m to the square matrix: A = 1 −1 2 −1 1 1 1 0 2 0 2 −2 1 −3 6 3 • Output the matrices L, U, and their product LU. 8? [1 / 20]Consider the problem Ax = b, where A is given in Question 7, and b = [−8;−2;−14; 2] (= a column vector). • Use only the matrices L and U from Question 7, the vector b, the func- tion backwardSub.m and permutation matrices to compute the solution x. I Finished! (submit your work using the procedure on page 1) MATH2019 Coursework 2 Page 4 of 5
