[Solved] CSE6643 Homework 2

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: Show that (1+ ) and (1+ when
• Problem 2: Consider a matrix

.

• Compute A¹ and
• Given examples for b,b,x and x satisfying

Ax = b, A(x + x) = b + b,

such that is small, but is large.

• Problem 3: Given x C², determine a unitary matrix of the form

,

where c R and c² + |s|² = 1, such that the second component of Qx is zero.

• Problem 4: Modify the Householder QR algorithm so that it can efficiently handle the case when A R^mm has lower bandwidth p and upper bandwidth q. Present you algorithm in a pseudo code fashion, and compute its computational cost in terms of m. Write your own code to perform your algorithm. Use your code to compute the QR factorization for a mm symmetric Toeplitz matrix with first column given by [10,3,2,1,0, ,0]^T. Vary m to confirm your estimate of the computational cost.
• Problem 5: The following experiments are on random matrices and their QR factorizations. Hint: you may want to read Lecture 9 in the reference book by Trefethen and Bau before you work on this part of the project.
  • Design a procedure to create a random matrix A of dimension nn with singular values given as 3¹,3², ,3ⁿ.
  • Write your own code for classical Gram-Schmidt and modified Gram-Schmidtalgorithms. Use your code to compute QR factorizations for the matrix A generated in (a). Compare and comment your results. If you find something interesting, you should try to explain it.
  • Write your own code for Householder transform and perform it to the matrix A.

Form the Q matrix from your procedure and comment on the results.

Run your experiments with n = 100, n = 200 and n = 300 respectively. Repeat the experiments for different random matrices.

2