Problem 1 (qiuzhen-qualify 2025-fall)

(10 points) Except LU-type factorizations, matrix inversion can be obtained by iterations. Given $A \in \mathbb{R}^{n\times n}$, consider the sequence $\{X_k\}$ generated by:
$$X_{k+1} = 2X_k - X_k A X_k,\quad k = 0,1,2,\dots.$$
Prove:
(a) if $\|I - AX_0\| < 1$, then $A$ is nonsingular and $X_k \to A^{-1}$ quadratically.
(b) there exists $X_0$ such that $\|I - AX_0\| < 1$, if and only if $A$ is nonsingular.

Problem 2 (qiuzhen-qualify 2025-fall)

(20 points) For any continuous function $f$, define $\|f\|_\infty = \max_{x \in [-1,1]} |f(x)|$.
Define the $n$-th Chebyshev polynomial by: $T_0(x) = 1$, $T_1(x) = x$, $T_{n+1}(x) = 2xT_n(x) - T_{n-1}(x)$.
(a) Show that $T_n(x) = \begin{cases} \cos(n\arccos x), & |x| \le 1, \\ \cosh(n\operatorname{arccosh} x), & |x| > 1. \end{cases}$
(b) Prove that $\min_{\deg P \le n,\, P(1)=1} \|P\|_\infty = 1$, which is attained at $p = T_n$.
(c) For $f \in C^{n+1}[-1,1]$, choose the interpolation nodes $x_0, x_1, \dots, x_n$ as the $n+1$ zeros of $T_{n+1}(x)$, and denote its degree-$n$ interpolation polynomial by $L_n$. Prove
$$\|f - L_n\|_\infty \le \frac{\|f^{(n+1)}\|_\infty}{(n+1)!\,2^n}.$$
(d) For $f \in C^{2n+2}[-1,1]$, derive the Gauss quadrature formula of $I(f) = \int_{-1}^1 \frac{f(x)}{\sqrt{1 - x^2}}\,dx$ for $n+1$ quadrature nodes, written by $I_{n+1}(f)$, and prove
$$|I(f) - I_{n+1}(f)| \le \frac{\pi\,\|f^{(2n+2)}\|_\infty}{(2n + 2)!\,2^{2n+1}}.$$

Problem 3 (qiuzhen-qualify 2025-fall)

(20 points) In many applications generalized eigenvalue problem is needed to be solved: finding $x \in \mathbb{C}^n$ and $\mu, \lambda \in \mathbb{C}$, s.t. $x \neq 0$, $|\mu|^2 + |\lambda|^2 = 1$, $\mu A x = \lambda B x$ for given $A, B \in \mathbb{C}^{n\times n}$. Here $x$ and $(\lambda, \mu)$ are called the eigenvector and eigenvalue of the pair $(A, B)$ respectively.
If $B$ is nonsingular, this problem is equivalent to the standard eigenvalue problem $AB^{-1} y = \mu^{-1}\lambda\, y$.
For two unitary matrices $Q, Z$, $Q^H A Z = S$, $Q^H B Z = T$ is called a UET performing on $(A, B)$, written as $Q^H(A, B)Z = (S, T)$ for ease.
(a) Give an example that $(A, B)$ has more than $n$ eigenvalues.
(b) Prove that there exists a UET such that $Q^H(A, B)Z = (S, T)$, where $S, T$ are upper triangular.
(c) Can you obtain the eigenvalues of $(A, B)$ from $(S, T)$? How?
(d) Propose a method to construct a UET such that $Q_0^H(A, B)Z_0 = (A_0, B_0)$, where $A_0$ is upper Hessenberg, and $B_0$ is upper triangular. For ease, you may assume $n = 4$.

Problem 4 (qiuzhen-qualify 2025-fall)

(15 points) Construct the Du Fort-Frankel scheme for the diffusion equation in 2D $u_t = u_{xx} + u_{yy}$ and discuss its consistency and stability.

Problem 5 (qiuzhen-qualify 2025-fall)

(15 points) For the wave equation $u_{tt} = u_{xx}$, analyze the stability of the scheme
$$\frac{u_{j}^{n+1} - 2u_{j}^{n} + u_{j}^{n-1}}{\tau^2} = \frac{u_{j+1}^{n+1} - 2u_{j}^{n+1} + u_{j-1}^{n+1}}{4h^2} + \frac{u_{j+1}^{n} + u_{j-1}^{n} - 2u_{j}^{n}}{2h^2} + \frac{u_{j+1}^{n-1} - 2u_{j}^{n-1} + u_{j-1}^{n-1}}{4h^2}.$$

Problem 6 (qiuzhen-qualify 2025-fall)

(20 points) Consider the so-called Rayleigh oscillator
$$y'' + y + \epsilon\Big[\tfrac{1}{3}(y')^3 - y'\Big] = 0,$$
with initial condition
$$y(0) = 0,\quad y'(0) = 2a,$$
where $y = y(t)$, $\epsilon > 0$, $a > 0$.
(a) (14 points) For a small $\epsilon$, construct an approximation of the solution to the above problem which is valid for large $t$.
(b) (4 points) What is the accuracy of this approximation? State a conclusion and briefly explain it.
(c) (2 points) Plot the approximated orbits in the phase plane, i.e., $y - y'$ plane for several different $a$. And explain what you observe.

Problem 7 (qiuzhen-qualify 2025-fall)

(20 points) Consider the minimization
$$\min_{x \in \mathbb{R}^n} \|Ax - b\|_2 + \gamma \|x\|_1,$$
with $A \in \mathbb{R}^{m\times n}$, $b \in \mathbb{R}^m$, and $\gamma > 0$.
(a) (8 points) Derive the Lagrange dual of the equivalent problem:
$$\min_{x,y} \|y\|_2 + \gamma \|x\|_1,\quad \text{s.t. } Ax - b = y,$$
with $x \in \mathbb{R}^n$ and $y \in \mathbb{R}^m$.
(b) (8 points) Suppose $Ax^\star - b \ne 0$ where $x^\star$ is an optimal point. Define $r = \dfrac{Ax^\star - b}{\|Ax^\star - b\|_2}$. Show that
$$\|A^T r\|_\infty \le \gamma,\quad r^T A x^\star + \gamma \|x^\star\|_1 \equiv 0.$$
(c) (4 points) Show that if $\|a_i\|_2 < \gamma$ where $a_i$ is the $i$-th column of $A$, then $x^\star_i = 0.$