Problem 1 (qiuzhen-qualify 2024-spring)

Suppose $k \le m \le n$, and $A \in \mathbb{C}^{m \times n}$.
- find a rank-$k$ matrix $X$ satisfying $\|A - X\|_2 \le \|A - B\|_2$ for any rank-$k$ matrix $B$. Here $\|\cdot\|_2$ is the spectral norm.
- find a rank-$k$ matrix $X$ satisfying $\|A - X\|_F \le \|A - B\|_F$ for any rank-$k$ matrix $B$. Here $\|\cdot\|_F$ is the Frobenius norm.

Problem 2 (qiuzhen-qualify 2024-spring)

Consider the Gauss-Seidel iteration for solving the linear equation $Ax = b$ for $A = [a_{ij}] \in \mathbb{R}^{n \times n}, b = [b_i] \in \mathbb{R}^n$ with $a_{ii} \ne 0$ for $i = 1,\ldots,n$.
1: determine $x^{(0)} \in \mathbb{R}^n$.
2: for $k = 0,1,2,\ldots$ do:
3: $x_i^{(k+1)} = \frac{1}{a_{ii}} \big( b_i - \sum_{j=1}^{i-1} a_{ij} x_j^{(k+1)} - \sum_{j=i+1}^{n} a_{ij} x_j^{(k)} \big)$ for $i = 1,2,\ldots,n$.
4: end for.
- Write $x^{(k)} = [x_i^{(k)}]$ and $A = D - L - U$ where $D,-L,-U$ are the diagonal, strictly lower triangular, strictly upper triangular parts of $A$ respectively. Show that $x^{(k+1)} = (D - L)^{-1} U x^{(k)} + (D - L)^{-1} b$.
- Prove that if $A$ is diagonally dominant, then $A$ is invertible, and the Gauss-Seidel iteration converges, namely $\lim_{k \to \infty} x^{(k)} = A^{-1} b$ for any $x^{(0)}$. (A matrix $A$ is called diagonally dominant, if $|a_{ii}| > \sum_{j \ne i} |a_{ij}|$ for $i = 1,\ldots,n$.)
- Prove that if $A$ is symmetric and positive definite, then $A$ is invertible, and the Gauss-Seidel iteration converges.

Problem 3 (qiuzhen-qualify 2024-spring)

Given the Hilbert matrix $H_n = \big[ \frac{1}{i+j-1} \big]_{i,j=1,\ldots,n}$, Prove:
- $H_n$ is positive definite.
- the spectral radius $\rho(H_n)$ of $H_n$ is strictly monotonically increasing with respect to $n$.
- $\rho(H_n) \to \pi$ as $n \to \infty$.

Problem 4 (qiuzhen-qualify 2024-spring)

Apply the following three-step method with a parameter $\theta \ge 0$ for solving the heat equation $u_t - a^2 u_{xx} = 0$ (Cauchy or periodic problem):
$(1 + \theta) \frac{u_j^{n+1} - u_j^n}{k} = \theta \frac{u_j^n - u_j^{n-1}}{k} = a^2 \frac{u_{j+1}^{n+1} - 2 u_j^{n+1} + u_{j-1}^{n+1}}{h^2}$.
Give its truncation error and stability. Particularly, give the value of $\theta$ such that the truncation error attains its highest order.

Problem 5 (qiuzhen-qualify 2024-spring)

Denote the grid $I_h = \{x_j\}_{j=0}^M$, $x_0 < x_1 < \cdots < x_M$. Set $u = \{u_j\}_{j=0}^M$ as a grid function on $I_h$. Suppose
$$
L u_j = - (a_j u_{j-1} - b_j u_j + c_j u_{j+1}) + q_j u_j,\quad j = 1,\ldots, M-1,
$$
where $a_j, b_j, c_j > 0$, $q_j \ge 0$ and $a_j + c_j \le b_j$.
- Assume $L u_j \le 0$ for all $1 \le j \le M - 1$. Show that $u_j$ can't attain positive maximum at inner points ($1 \le j \le M - 1$) unless $u_j \equiv C$;
- Suppose $d_j = b_j - a_j - c_j + q_j > 0$ ($j = 1,\ldots, M - 1$). Show the solution of the difference equation
$$
L u_j = \varphi_j,\quad j = 1,\ldots, M - 1;\quad u_0 = u_M = 0,
$$
satisfies $\|u\|_\infty = \max |u_j| \le \frac{\max |\varphi_j|}{\min_j d_j}$.

Problem 6 (qiuzhen-qualify 2024-spring)

Let $S \subset \mathbb{R}^n$ be a non-empty closed convex set, $f \in C^2(S)$ is convex. For any $x^0 \in S$, define $L(f(x^0)) = \{x \in S \mid f(x) \le f(x^0)\}$, if there exists some $m > 0$ such that
$$
d^\top \nabla^2 f(x) d \ge m \|d\|^2,\quad \forall x \in L(f(x^0)),\ d \in \mathbb{R}^n.
$$
Prove that $L(f(x^0))$ is a bounded and closed convex set.

Problem 7 (qiuzhen-qualify 2024-spring)

Given a linear programming (LP):
$$
\max\ 3x_1 + 2x_2 + 15x_3
$$
s.t.
$$
x_1 + 2x_2 + x_3 \le 12,\\
2x_1 + x_2 + 5x_3 \le 18,\\
x_1, x_2, x_3 \ge 0.
$$
- Write down the standard LP form.
- Compute the optimal solution and optimal value of the problem.