[Solved] CSE6643 Homework 4

Notice: For the computational problems, you must design your own ways, such as using tables and plots etc, to present the results you obtain. And you must show the procedure you take, and explain the results you get, and draw conclusions if you have any. Computer code is not considered as an explanation. Please upload your code in T-square, and return your HW in class on or before the Due date.

• Problem 1: If one writes the following MATLAB script,

[U,S,V ] = svd(A); S = diag(S); tol = max(size(A)) eps;

r = sum(S > tol);

S = diag(ones(r,1)./S(1 : r));

X = V (:,1 : r) S U(:,1 : r)⁰;

What does this program compute? You must show the steps on how you get your answer. Here eps is the machine precision used in MATLAB. For this question, you may use MATLAB help to find out the meaning of each built-in function if you are not familiar with MATLAB.

• Problem 2: Given two matrices

.

If one uses Jacobi iteration to solve linear systems A~x = ^~b and B~x = ^~b respectively, does it converge? What about Gauss-Seidel? You must justify your answer.

• Problem 3: Let ~r_j be the residual vector computed in the steepest descent algorithm, show that ~r_j and ~r_j+1 are orthogonal.
• Problem 4: Use the symmetric mm Toeplitz matrix T given in Problem 4 of HW2 to perform the following computations. Write your own code for Jacobi, Gauss-Seidel and SOR (with different relaxation parameter ) iterations to solve the linear system

with = 5 and = 5 respectively. b is a randomly generated m-dimensional vector. Compare the solutions and the speed for m = 100,200,400,800,.

• Problem 5: Use the matrix A, with = 0 and = 2 respectively, and the vector ^~b from of Problem 5 in HW1 to finish the following work. Solve the linear system

A~x =^~b

by the following methods:

• Steepest Descent Method,
• Conjugate Gradient Method.

You need to test your code with different size (n = 100,200,400,800,1600,3200 or larger if your computer permits) for both parts and comment on the results you obtain.

Hint: you must find ways to demonstrate how the computation cost is associated the size of the system, and how to compare the numerical solutions with the exact solution if you can find it.

2