Numerical Analysis - May 2022

Problem 1.

(10 points) Let $P\in\mathbb{C}^{m\times m}$ be a nonzero projector. Show that $\lVert P\rVert_2\geq 1$, with equality if $P$ is an orthogonal projector.

Problem 2.

Let $A\in\mathbb{R}^{n\times n}$ be nonsingular. Consider designing an iterative method to solve the following linear system,

$$Ax=b,$$

where $b\in\mathbb{R}^n$ is given and $x\in\mathbb{R}^n$ is unknown.

1. (5 points) Write down the Jacobi iterative method for the above linear system.

2. (5 points) Write down the Gauss-Seidel iterative method for the above linear system.

Problem 3.

(10 points) Let $A\in\mathbb{R}^{n\times n}$ be a symmetric, positive definite matrix. Show that solving the linear system

$$Ax=b$$

is equivalent to finding the minimizer $x\in\mathbb{R}^n$ of the quadratic form,

$$\Phi(y)=\frac{1}{2}y^TAy-y^Tb,$$

where $b\in\mathbb{R}^n$ is a given vector and $x$ is unknown.

Problem 4.

(10 points) Given any symmetric, positive semi-definite matrix $A\in\mathbb{R}^{n\times n}$ and any two symmetric matrices $B\in\mathbb{R}^{n\times n}$ and $C\in\mathbb{R}^{n\times n}$, show that if $C-B$ is positive semi-definite, then

$$\operatorname{trace}(AB)\leq\operatorname{trace}(AC).$$

Problem 5.

(10 points) Let $A\in\mathbb{C}^{2n\times 2n}$, $B\in\mathbb{C}^{n\times n}$ and $I$ be the $n\times n$ identity matrix. Let

$$A=\begin{bmatrix}I&B\\B^H&I\end{bmatrix}$$

with $\lVert B\rVert_2<1$, where $B^H$ is the hermitian conjugate of $B$. Show that

$$\lVert A\rVert_2\lVert A^{-1}\rVert_2=\frac{1+\lVert B\rVert_2}{1-\lVert B\rVert_2}.$$

Problem 6.

Consider the following linear system,

$$Ax=r,$$

where $r\in\mathbb{R}^n$ is given, $x\in\mathbb{R}^n$ is unknown, and

$$A=\begin{bmatrix} b_1&c_1&0&\cdots&\cdots&0\\ a_2&b_2&c_2&0&\cdots&0\\ 0&a_3&b_3&c_3&\ddots&0\\ \vdots&\ddots&\ddots&\ddots&\ddots&\vdots\\ \cdots&\cdots&0&a_{n-1}&b_{n-1}&c_{n-1}\\ \cdots&\cdots&\cdots&0&a_n&b_n \end{bmatrix}$$

is assumed to be strictly diagonally dominant with $a_1=0$ and $c_n=0$:

$$|b_i|>|a_i|+|c_i|,\quad i=1,2,\cdots,n.$$

1. (10 points) Prove that the $n\times n$ tridiagonal matrix $A$ is nonsingular.

2. (10 points) Let $A$ have the LU decomposition in the form of $A=LU$, where $L$ is an lower triangular matrix, and $U$ is an upper triangular matrix with 1’s along its main diagonal. Derive the specific forms of $L$ and $U$ in terms of $a_i$, $b_i$ and $c_i$, where $i=1,2,\cdots,n$.

3. (10 points) Design an $O(n)$ algorithm to solve the linear system $Ax=r$.

Problem 7.

Consider the following integration formula

$$u(x)=\int_0^x G(x,y)f(y)\,dy\qquad\text{if }0\leq x\leq 1,\tag{1}$$

where $f\in C^2[0,1]$ and $G(x,y)$ is given by

$$G(x,y)=\begin{cases}\sqrt{x^2-y^2}&\text{if }0\leq y\leq x\leq 1,\\0&\text{otherwise.}\end{cases}\tag{2}$$

Partition [0,1] into $n$ equal subintervals with mesh size $h=\frac{1}{n}$: $x_j=y_j=jh$, $f_j=f(x_j)$, $\hat{u}_j\approx u_j=u(x_j)$ for $0\leq j\leq n$. We also introduce the following vector notations: $U=(u_1,u_2,\cdots,u_n)^t$, $F=(f_1,f_2,\cdots,f_n)^t$, and $\hat{U}=(\hat{u}_1,\cdots,\hat{u}_n)^t$.

1. (10 points) To evaluate the vector $\hat{U}$, we may approximate the integral formula (1) by the Riemann sum based on the above uniform partition,

   $$\hat{u}_i=\sum_{j=1}^i G(x_i,y_j)f(y_j)h,\qquad i=1,\cdots,n,$$

   which will lead to a matrix-vector product $\hat{U}=\hat{G}F$ in terms of matrix $\hat{G}$ defined by

   $$\hat{G}=\big(hG(x_i,y_j)\big)_{1\leq i\leq n,\;1\leq j\leq n}$$

   and the vector $F$. Write down this matrix-vector product to obtain the vector $\hat{U}$ from the Riemann sum. Show that the complexity of this matrix-vector product is $O(n^2)$.

2. (10 points) Based on the above uniform partition, use the structure of the Green’s function $G$ to design an $O(n)$ algorithm to compute the vector $\hat{U}$ with accuracy $O(h)$. (Hint: split the integral into two parts: $\int_0^{x-h}$ and $\int_{x-h}^x$ for $x>h$.)