UNIVERSITY OF HONG KONG DEPARTMENT OF MATHEMATICS MATH4602 Scientific Computing Assignment 2
Due Date: 8 Mar. 2019
1. [The Inverse of the FFT Matrix] The discrete FFT matrix is defined as follows:
w0·0 w0·1 · · · w0·(n−1) nnn
w1·0 w1·1 · · · w1·(n−1) nnn
−2πi/n where wn = e
−1 1 n n n . Show that Fn = n . . .
.
.
Fn = . . . .
w(n−1)·0 w(n−1)·1 · · · w(n−1)·(n−1) nnn
w−0·0 w−0·1 · · · w−0·(n−1) nnn
w−1·0 w−1·1 · · · w−1·(n−1)
2. [Properties of Circulant Matrices] Prove that the inverse of a circulant matrix is still a circulant matrix and the product of any two circulant matrices is again a circulant matrix. [20%]
3. [From LU to Cholesky factorization] In the notes, we have obtained the Dolittle LU
factorization of
2 −1 0 0 0
−1 2 −1 … . A= 0 −1 … … 0 .
… . . . . . . 2 − 1
0 ··· 0 −1 2 Give the Cholesky factorization of A.
4. [A Markov chain problem] Given the following n × n matrix −1 1/2
[20%]
A =
1 −1 1/2 1/2 −1 1/2
1/2 … …
… … 1/2
1/2 −1 1 1/2 −1
(a) Show that A is singular.
(b) Show that the dimension of the null space of A is one. (c) Find the null vector v such that Av = 0 and ni=1 vi = 1.
1
[20%]
w−(n−1)·0 w−(n−1)·1 · · · w−(n−1)·(n−1) nnn
[10%]
5. [Matrix norm] For any n × n matrix A, define nn
||A||F =
21/2 aij .
i=1 j=1
Show that ||A||F is a matrix norm. (This is called the Frobenius norm.)
6. [Properties of a norm] Prove that if a square matrix A satisfies an inequality ||Ax|| ≥ θ||x||
for all x ∈ Rn, with θ > 0, then A is nonsingular and ||A−1||M ≤ θ−1.
[20%]
[10%]
2