NUMERICAL ANALYSIS + MATLAB (Assignment)

MACM 316 { Computing Assignment 2 ˆ Please read the Guidelines for Assignments rst.

ˆ Submit a one-page PDF report to Canvas and upload you Matlab scripts (as m- les). Do not use any other le formats.

ˆ Keep in mind that Canvas discussions are open forums.

ˆ Acknowledge any collaborations and assistance from colleagues, TAs, instructors etc.

Gaussian Elimination in oating point arithmetic Note: Download the in-class demo LSRandom.mbefore completing this assignment.

As seen in class, Gaussian elimination in oating point arithmetic may incur errors due to round-o for large matrices. In this assignment you will investigate this error.

Let Abe a random n nmatrix, x = (1 ;1 ; : : : ; 1)> be an n-vector of ones and b = Ax be the right-hand side vector. As in class, let z = ( z j) 2 Rn be the result of solving the system Ax = b in nite precision using the backslash command. To measure the error between x and z , we let = max j=1 ;:::;n j x j z jj ; be the maximum componentwise di erence between the two vectors. Since Ais a random matrix, we need to run this calculation a number of times with di erent realizations of Ain order to get a reasonable value for . Let Mbe the number of trials and suppose that for the kth trial the error is ( k ) . We de ne the mean error as follows:

En = 1 M (1) + (2) +: : : + ( M ) :

Your goal is to determine the approximate size of matrix n= n at which the mean error for Gaussian Elimination is E n 1. In other words, the point at which round-o error in Gaussian elimination is of the same magnitude as the vector x .

In practice, your computer will not have the memory or processing power to nd n exactly. Instead, you should extrapolate your data. Find E n for reasonable values of n, make a plot of log 10( E n) versus log 10( n ) and then perform a suitable extrapolation.

Your conclusions should be explained in a one-page report. Your report should include the following:

(a)A plot of log 10( E n) versus log 10( n ).

(b)Justi cation for the values of nand Myou chose.

(c)Explanation of how you do the extrapolation.

(d)An estimation of the number n .

Finally, replace Abe an random upper-triangular matrix and repeat the process. Hint: you should not need to do the extrapolation step here. You may also wish to plot log 10( E n) against nhere, rather than log 10( n ).

1