Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSC336H1

Homework 3

2022

1.  (30 points) Consider the n × n matrix A defined by the formula

╱ 6     -4     1      0     . . .    . . .     0 、

．(．)   -4     6     -4     1     . . . ．(．)

． ．

．(．)     1     -4     6     -4     1     . . .     0    ．(．)

A = n4 .．(．)    0     . . .    . . .    . . .    . . .    . . .     0    ．(．) .                      (1)

． ．

． ．

． . . .      1      -4      6      -4 ．

( ．

This matrix can be constructed using the ones and diag functions in MATLAB, or the numpy .ones and numpy .diag functions in NumPy.

(a)  Compute the condition number κ(A) of A for n = 10, 20, 40, 80, 160.  How does the condition number of A grow with n? Hint: If κ(A) = O(np ) for some integer p, how much bigger should the condition number become when n is doubled?

(b) Let x be a vector defined by the formula xj  = sin(5j/n) for j = 1, 2, . . . , n, and

let that δx be a random vector such that |δx| = 106|x|, where 6 is machine precision.  Let = x + δx.  What is the relative error |A - Ax|/|Ax| for n = 10, 100, 500, 1000? Why does the error behave this way?

(c)  Repeat part (b), except now, let x be defined by the formula xj  = (-1)j sin(5j/n). Why do you see these results?

(d)  Suppose now that y is a vector defined by the formula yj  = sin(5j/n) for j = 1, 2, . . . , n. Solve the linear system Ax = y, computing the approximate solution .   What is the relative error in the residual,  |A - y|/|y|, for n = 10, 100, 500, 1000? Why does the error behave this way? Hint: What are the eigenvectors and eigenvalues of A− 1 ?

(e)  Repeat part (d), except now, let y be defined by the formula yj  = (-1)j sin(5j/n).

Why do you see these results?

2.  (30 points) Let A be the n × n matrix defined in problem (1), for n = 20. Suppose that B is an n × n defined by Bi,j  = exp(-2(i - j)2 ), and let = AB .

(a)  Suppose that v1 is the eigenvector of corresponding to the largest eigenvalue.

Let xk  denote the approximation to v1  after k steps of power iteration applied to , starting with the vector x0  defined by (x0 )i = sin(i/2) for i = 1, 2, . . . , n.

Suppose that ek  = |v1 - xk|. Fill in the following table:

ek

5

10

15

.

50

100

250

500

Hint: Use the eig function in MATLAB or the scipy .linalg .eig function in SciPy to compute v1 .

(b)  At what rate does this iteration converge?  Why?  Hint:  Examine the ratio ek/ek − 1 .

(c)  Repeat parts (a) and (b) for the matrix − 1 . Why do you see these results?

(d)  Let the matrix Qk  denote the orthogonal matrix resulting from k steps of simultaneous iteration with A, starting with the orthogonal matrix Q0 , Q0R0 = X0, with X0  defined by the formula (X0)i,j  = sin((i - j)/2).  Suppose that Ak  = Qk(T)AQk, and let ek  = |Ak - triu(Ak)|/|Ak|, where triu(Ak) denotes the upper triangular part of Ak .  Fill in table (2).  Why do you see these results? Hint: See the MATLAB functions qr and triu, or the SciPy functions scipy .linalg .qr and scipy .linalg .triu.

(e) In what order do the eigenvalues appear on the diagonal of Ak? Why?

3.  (30 points) Let A be the n×n matrix defined by the formula Ai,j  = 1/(i -j +µ+1/2). Suppose that n = 20.

(a) Implement a function which performs modified Gram-Schmidt orthogonaliza- tion on the columns of A, producing an orthogonal matrix Q. Let R = QT A.

Fill in the following table, where triu(R) denotes the upper triangular part of R.

Why do you see these results?

(b)  Repeat part (a) again, but add an additional reothogonalization step. Why

do you see these results?

(c) Why is only a single reorthgonalization step necessary?

(d) Add pivoting to your Gram-Schmidt code from part (b). Report the last six normalizing factors you encounter when µ = 6. How do the normalizing factors compare to the singular values of A?

(e)  Suppose that µ = 20.  How would you construct a decomposition A ≈ QR,

where Q is an n × k matrix with orthonormal columns and R is a k × n matrix, with k < n? What is the smallest possible k for which A is equal QR to close to machine precision?