To complete this assignment, I suggest you download in class demo LSRandom.m from Canvas (lecutre notes...

Transcribed Image Text:

To complete this assignment, I suggest you download in class demo LSRandom.m from Canvas (lecutre notes page). You will need to modify this script suitably in order to complete the assign- ment. Also, you may find the following Matlab commands useful: 1. A=spdiags(rand(N.3), -1:1, N.N); which creates a tridiagonal matrix with random entries along each diagonal. 2. loglog(N_it, Err, 'r*'); which plots the error versus N in a loglog plot. 3. p-polyfit(log10(N_it), log10(Err), 1); which fits a straight line to the loglog data. In class we saw that finite-precision computations with Gaussian Elimination, implemented via Matlab's backslash command, leads to small errors for small matrices but possibly larger errors for larger matrices. The purpose of this assignment is to quantify the growth of this error for tridiagonal matrices. A tridiagonal matrix is a matrix with non-zero entries only on the main diagonal, as well as the diagonals above and below the main diagonal. A = a1,1 42,1 a1,2 0 0 02,2 0 a2,3 an-1,n-2 an-1.n-1 0 an.n-1 0 : 0 an-1.n ann Let A be a random Nx N tridiagonal matrix, = (1, 1.....1) be an N-vector of ones and b = Ar be the right-hand side vector. As in class, let z = (25) € RN be the resulting vector 2 =A\b. computed in finite precision using the backslash command. To measure the error between 2 and z. we let 8 = max |-zjl, j=1,...,N be the maximum componentwise difference between the two vectors. Since A is a matrix with random values, we need to run this calculation a number of times with different realizations of A in order to get a reasonable value for 8. Let M be the number of trials and suppose that for the kth trial the error is (). We define the mean error as follows: EN 5(1)+(2). 2+...+ 8(^)). M The goal of this assignment is to investigate the size of the matrix N = N* at which the mean error for Gaussian Elimination is EN 1. In other words, the point at which round-off error in Gaussian elimination is of the same magnitude as the vector I. In practice, your computer will likely not have the processing power to find N* exactly. Instead. you should extrapolate your data to find an estimate of N". Find Ex for reasonable values of N. make a plot of log10 (N) versus log10(EN) and then perform a suitable extrapolation. Your conclusions should be explained in a one-page report. Your report must include the following: (a) A plot of EN versus N for the values of N you choose. (b) Justification for the values of N and M you chose. (e) Explanation of how you do the extrapolation. (d) An estimation of the number N*. To complete this assignment, I suggest you download in class demo LSRandom.m from Canvas (lecutre notes page). You will need to modify this script suitably in order to complete the assign- ment. Also, you may find the following Matlab commands useful: 1. A=spdiags(rand(N.3), -1:1, N.N); which creates a tridiagonal matrix with random entries along each diagonal. 2. loglog(N_it, Err, 'r*'); which plots the error versus N in a loglog plot. 3. p-polyfit(log10(N_it), log10(Err), 1); which fits a straight line to the loglog data. In class we saw that finite-precision computations with Gaussian Elimination, implemented via Matlab's backslash command, leads to small errors for small matrices but possibly larger errors for larger matrices. The purpose of this assignment is to quantify the growth of this error for tridiagonal matrices. A tridiagonal matrix is a matrix with non-zero entries only on the main diagonal, as well as the diagonals above and below the main diagonal. A = a1,1 42,1 a1,2 0 0 02,2 0 a2,3 an-1,n-2 an-1.n-1 0 an.n-1 0 : 0 an-1.n ann Let A be a random Nx N tridiagonal matrix, = (1, 1.....1) be an N-vector of ones and b = Ar be the right-hand side vector. As in class, let z = (25) € RN be the resulting vector 2 =A\b. computed in finite precision using the backslash command. To measure the error between 2 and z. we let 8 = max |-zjl, j=1,...,N be the maximum componentwise difference between the two vectors. Since A is a matrix with random values, we need to run this calculation a number of times with different realizations of A in order to get a reasonable value for 8. Let M be the number of trials and suppose that for the kth trial the error is (). We define the mean error as follows: EN 5(1)+(2). 2+...+ 8(^)). M The goal of this assignment is to investigate the size of the matrix N = N* at which the mean error for Gaussian Elimination is EN 1. In other words, the point at which round-off error in Gaussian elimination is of the same magnitude as the vector I. In practice, your computer will likely not have the processing power to find N* exactly. Instead. you should extrapolate your data to find an estimate of N". Find Ex for reasonable values of N. make a plot of log10 (N) versus log10(EN) and then perform a suitable extrapolation. Your conclusions should be explained in a one-page report. Your report must include the following: (a) A plot of EN versus N for the values of N you choose. (b) Justification for the values of N and M you chose. (e) Explanation of how you do the extrapolation. (d) An estimation of the number N*.