Problem 1 (qiuzhen-qualify 2024-fall)

(20 points) The $n$-th Chebyshev polynomial is defined by $T_n(x) = \cos(n\,\arccos(x))$. Answer the following questions related to $T_n(x)$.

(i) (6 points) Prove that $T_n(x)$ is a polynomial of degree $n$.

(ii) (6 points) For any $x$ with $0 < x < 1$, show that $T_n(2x - 1) = T_{2n}(\sqrt{x})$.

(iii) (8 points) Prove that the system of Chebyshev polynomials $\{T_k : 0 \le k < n\}$ is orthogonal with respect to the discrete inner product $(u,v) = \sum_{k=1}^n u(x_k)v(x_k)$, where $\{x_k\}$ are the Chebyshev points $x_k = \cos\!\left(\frac{(2k-1)\pi}{2n}\right)$.

Problem 2 (qiuzhen-qualify 2024-fall)

(15 points) Let $A$ be a symmetric positive definite matrix. Assume that the conjugate gradient method is applied to solve the linear system $Ax = b$, where $x^*$ is the exact solution.

(i) (10 points) Prove the following error estimate:
$$\|x_k - x^*\|_A \le \left( \frac{\sqrt{\kappa_2(A)} - 1}{\sqrt{\kappa_2(A)} + 1} \right)^k \|x_0 - x^*\|_A,$$
where $x_k$ is the solution obtained by the $k$-th iteration, $\|\cdot\|_A$ denotes the $A$-norm defined by $\|x\|_A = \sqrt{x^\top A x}$, and $\kappa_2(A) = \frac{\lambda_{\max}(A)}{\lambda_{\min}(A)}$ denotes the condition number of $A$ under the $l_2$ norm. (If you apply any theorem from approximation theory, please state the theorem clearly. No need to prove that theorem.)

(ii) (5 points) Describe one Krylov subspace method for non-Hermitian matrices $(A \ne A^*)$. You can use pseudo-code or words/formulas as long as the steps are clear.

Problem 3 (qiuzhen-qualify 2024-fall)

(15 points) Consider Kepler’s equation
$$f(x) = x - \epsilon \sin x - \eta, \qquad (0 < |\epsilon| < 1),\; \eta \in \mathbb{R}.$$

(i) (5 points) Show that for each $\epsilon, \eta$, there is exactly one real root $\alpha = \alpha(\epsilon, \eta)$. Furthermore, $\eta - |\epsilon| \le \alpha \le \eta + |\epsilon|$.

(ii) (5 points) Writing the equation in fixed point form:
$$x = \varphi(x), \qquad \varphi(x) = \epsilon \sin x + \eta,$$
show that the fixed point iteration $x_{n+1} = \varphi(x_n)$ converges for arbitrary staring value $x_0$.

(iii) (5 points) Let $m$ be an integer such that $m\pi < \eta < (m + 1)\pi$. Show that Newton’s method with starting value
$$
x_0 = \begin{cases}
(m + 1)\pi, & \text{if } (-1)^m \epsilon > 0, \\
m\pi, & \text{otherwise},
\end{cases}
$$
is guaranteed to converge (monotonically) to $\alpha(\epsilon, \eta)$.

Problem 4 (qiuzhen-qualify 2024-fall)

(15 points) For the system $u_t = v_x$, $v_t = u_x$, analyze the truncation error and stability of the scheme
$$
\frac{1}{\tau}\left(u_j^{n+1} - \frac{1}{2}(u_{j+1}^n + u_{j-1}^n)\right) = \frac{1}{2h}(v_{j+1}^n - v_{j-1}^n),
$$
$$
\frac{1}{\tau}\left(v_j^{n+1} - \frac{1}{2}(v_{j+1}^n + v_{j-1}^n)\right) = \frac{1}{2h}(u_{j+1}^n - u_{j-1}^n).
$$

Problem 5 (qiuzhen-qualify 2024-fall)

(15 points) Write and prove the maximum principle of the centered finite difference scheme for discretizing the equation
$$u_{xx} + u_{yy} + d(x,y)\,u_x + e(x,y)\,u_y + f(x,y)\,u = 0, \qquad f < 0,$$
under some suitable assumptions.

Problem 6 (qiuzhen-qualify 2024-fall)

(20 points) Consider the following boundary value problem for $y = y(x)$ on $[0,1]$ as $0 < \epsilon \ll 1$,
$$\epsilon y'' + \epsilon(1 + x^2) y' - y = x - 1, \qquad y(0) = \alpha, \quad y(1) = -1.$$

(i) (10 points) Suppose $\alpha = 1$. Construct a composite expansion of the above problem and sketch the solution.

(ii) (5 points) Construct a composite expansion of the above problem for $\alpha = 0$.

(iii) (5 points) What is the accuracy of your solution in $\epsilon$? Formally explain your conclusion. Consider the first case only.

Problem 7 (qiuzhen-qualify 2024-fall)

(20 points) Let $f : \mathbb{R}^n \to \mathbb{R}$ be convex and define $\partial f(x)$ to be the subgradient set of $f$ at $x$.

(i) (10 points) If $x \in \operatorname{int} \operatorname{dom} f$, prove that $\partial f(x)$ is nonempty and bounded.

(ii) (5 points) Assume $f = \|x\|_1 = \sum_{i=1}^n |x_i|$, write down the $\partial f(x)$.

(iii) (5 points) Given $y \in \mathbb{R}^n$ and $\lambda > 0$, calculate the closed form solution of the problem:
$$\min_x\ \frac{1}{2}\|x - y\|_2^2 + \lambda\|x\|_1.$$