1    Problems (100 pts)

For this chapter, you will write scripts to compute the solution to the linear equation Ax = b. First, write a script to perform Gaussian elimination without pivoting and a separate script to perform back substitution.  Next, write a third function to determine the LU factorization of a matrix and a fourth to solve LUx = b via forward and backwards sovlves (you should re-use your backsovle algorithm in this).

First, apply these scripts to the matrix you studied in problem 3 in the second problem set to confirm their correctness with b = [3, 2, 1]T . Report the factored matrices and the

x you find with each method.                         

Next, define a (n × n) matrix A =  (5^n)I + R where R is a matrix with random entries from the normal distribution centered at 0 with a standard deviation of 1 and I is the identity matrix. Define b as a (n × 1) vector with random entries drawn from the same random distribution. For n = 50, 100, 250, 500, solve the system Ax = b using your code. Then fill in the table below with the residual error ||Ax − b||2 . Please report these  errors using scientific notation.  Finally, plot the time needed to solve the system vs.  n for each method (please include both methods on the same graph).  Do not include the time to create the matrix A in your experminets.

Describe the pattern you observe in the errors and wallclock time graph and how that relates to the theory which we’ve developed in class.

Lastly, try a few experiments with the matrix family Aˆ = R (with R defined as above) and write a sentence or two on your observations. You do no need to submit any code or figures for this, but you should explain what you observe and why this happens.

Table 1: Error for ||Ax − b||2  for different sized matrices GE, and LU factorizations

Hint 1:You can time a block of code in Matlab with

t i c ;

### YOUR CODE HERE ###

total _ time  =  t o c ;