Problem 1 (yau-contest 2012)

In the numerical integration formula

$$\int_{-1}^{1} f(x)\,dx \approx a f(-1) + b f(c),$$

if the constants $a$, $b$, $c$ can be chosen arbitrarily, what is the highest degree $k$ such that the formula is exact for all polynomials of degree up to $k$? Find the constants $a$, $b$, $c$ for which the formula is exact for all polynomials of degree up to this $k$.

Problem 2 (yau-contest 2012)

Here is the definition of a moving least square approximation of a function $f(x)$ near a point $\bar x$ given $K$ points $x_k$ around $\bar x$ in $\mathbb{R}$, $k \in [1, \cdots, K]$.

$$\min_{P_x \in I_m} \sum_{k=1}^{K} \lvert P_x(x_k) - f_k \rvert^2$$

where $f_k = f(x_k)$, $I_m$ is the space of polynomials of degree less or equal to $m$, i.e.,

$$P_{\bar x}(x) = b_{\bar x}(x)^T c(\bar x),$$

$$c(\bar x) = [c_0, c_1, \cdots, c_m]^T \text{ is the coefficient vector to be determined by (2),}$$

$b_{\bar x}(x)$ is the polynomial basis vector, $b_{\bar x}(x) = [1, x - \bar x, (x - \bar x)^2, \cdots, (x - \bar x)^m]^T$.

Assume that there are $K > m$ different points $x_k$ and $f(x)$ is smooth,

(a) prove that there is a unique solution $\overline{P}_{\bar x}(x)$ to (2)

(b) denote $h = \max_k \lvert x_k - \bar x \rvert$, prove

$$\big\lvert c_i - \frac{1}{i!} f^{(i)}(\bar x) \big\rvert = C(f,i) h^{m+1-i}, \quad i = 0, 1, \ldots, m,$$

where $f^{(i)}(\cdot)$ is the $i$-th derivative of $f$ and $C(f, i)$ denote some constant depending on $f, i$.

(c) if $S = \{x_k\mid k = 1, 2, \ldots, K\}$ are symmetrically distributed around $\bar x$, that is, if $x_k \in S$ then $2\bar x - x_k \in S$, prove that

$$\big\lvert c_i - \frac{1}{i!} f^{(i)}(\bar x) \big\rvert = C(f, i) h^{m+2-i}, \quad i = 0, 1, \ldots, m,$$

for $i$ ($\in \{0, 1, \cdots, m\}$) with the same parity of $m$.

Problem 3 (yau-contest 2012)

Describe the forward-in-time and center-in-space finite difference scheme for the one-wave wave equation:

$$u_t + u_x = 0.$$

(i). Conduct the von Neumann stability analysis and comment on their stability property.

(ii). Under what condition on $\Delta t$ and $\Delta x$ would this scheme be stable and convergent?

(iii). How many ways you can modify this scheme to make it stable when the CFL condition is satisfied.

Problem 4 (yau-contest 2012)

Let $C$ and $D$ in $\mathbb{C}^{n\times n}$ be Hermitian matrices. Denote their eigenvalues by

$$\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n \quad \text{and} \quad \mu_1 \ge \mu_2 \ge \cdots \ge \mu_n,$$

respectively. Then it is known that

$$\sum_{i=1}^{n} (\lambda_i - \mu_i)^2 \le \lVert C - D \rVert_F^2.$$

1) Let $A$ and $B$ be in $\mathbb{C}^{n\times n}$. Denote their singular values by

$$\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_n \quad \text{and} \quad \tau_1 \ge \tau_2 \ge \cdots \ge \tau_n,$$

respectively. Prove that the following inequality holds:

$$\sum_{i=1}^{n} (\sigma_i - \tau_i)^2 \le \lVert A - B \rVert_F^2.$$

2) Given $A \in \mathbb{R}^{n\times n}$ and its SVD is $A = U \Sigma V^T$, where $U = (\mathbf{u}_1, \mathbf{u}_2, \ldots, \mathbf{u}_n)$, $V = (\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_n)$ are orthogonal matrices,

and $\Sigma = \operatorname{diag}(\sigma_1, \sigma_2, \ldots, \sigma_n)$, $\sigma_1 \ge \sigma_2 \ge \cdots \ge \sigma_n \ge 0$.

Suppose $\operatorname{rank}(A) > k$ and denote by

$$U_k = (\mathbf{u}_1, \mathbf{u}_2, \ldots, \mathbf{u}_k), \quad V_k = (\mathbf{v}_1, \mathbf{v}_2, \ldots, \mathbf{v}_k), \quad \Sigma_k = \operatorname{diag}(\sigma_1, \sigma_2, \ldots, \sigma_k),$$

and

$$A_k = U_k \Sigma_k V_k^T = \sum_{i=1}^{k} \sigma_i \, \mathbf{u}_i \mathbf{v}_i^T.$$

Prove that

$$\min_{\operatorname{rank}(B)=k} \lVert A - B \rVert_F^2 = \lVert A - A_k \rVert_F^2 = \sum_{i=k+1}^{n} \sigma_i^2.$$

Problem 3 (yau-contest 2012)

Let the vectors $x_i \in \mathbb{R}^n$, $i = 1, 2, \ldots, n$, be in the space $W$ with dimension $d$, where $d \ll n$. Let the orthonormal basis of $W$ be $W \in \mathbb{R}^{n \times d}$. Then we can represent $x_i$ by

$$x_i = c + W r_i + e_i, \quad i = 1, 2, \ldots, n,$$

where $c \in \mathbb{R}^n$ is a constant vector, $r_i \in \mathbb{R}^d$ is the coordinate of the point $x_i$ in the space $W$, and $e_i$ is the error. Denote $R = (r_1, r_2, \ldots, r_n)$ and $E = (e_1, e_2, \ldots, e_n)$. Find $W$, $R$ and $c$ such that the error $\|E\|_F$ is minimized.

(Hint: write $X = [x_1, x_2, \ldots, x_n] = c(1, 1, \ldots, 1) + W R + E$.)

Problem 5 (yau-contest 2012)

Two primes $p$ and $q$ are called twin primes if $q = p + 2$. For example, 5 and 7, 11 and 13, 29 and 31 are twin primes. There is a still unproven (but extensively numerically verified) conjecture that there are infinitely many twin primes and that they are rather common. Show how to factor an integer $N$ which is a product of two twin primes.