Problem 1 (yau-contest 2017)

The Chebyshev polynomial of the first kind is defined on $[-1,1]$ by $T_n(x) = \cos(n \arccos x)$. Prove: The envelope for the extremals of $T_{n+1}(x) - T_{n-1}(x)$ forms an ellipse.

Problem 2 (yau-contest 2017)

Consider a fixed point iteration $x_n = g(x_{n-1})$, where $g : \mathbb{R} \to \mathbb{R}$ is a smooth function. Suppose this fixed point method does converge to a fixed point $x^*$. The Steffensen algorithm is an acceleration method to find $x^*$ which reads

$\hat{x}_n = x_{n-2} - \dfrac{(x_{n-1} - x_{n-2})^2}{x_n - 2x_{n-1} + x_{n-2}}$.

or

$x_{n+1} = G(x_n)$

where

$G(x) = x - \dfrac{(g(x) - x)^2}{g(g(x)) - 2g(x) + x}$.

(a) Show that the Steffensen algorithm $\{x_k\}$ converges quadratically.

(b) Can you extend this method to two dimensions?

Problem 3 (yau-contest 2017)

We consider a piecewise smooth function

$$
f(x) = \begin{cases}
f_1(x), & x \le 0, \\
f_2(x), & x > 0.
\end{cases}
$$

where $f_1(x)$ is a $C^\infty$ function on $(-\infty, 0]$ and $f_2(x)$ is a $C^\infty$ function on $[0, \infty)$, but $f_1(0) \ne f_2(0)$. Suppose $p(x)$ is a $k$-th degree polynomial $(k \ge 1)$ interpolating $f(x)$ at $k+1$ equally-spaced grid points $x_j$, $j = 0, 1, 2, \ldots, k$ with $x_i < 0 < x_{i+1}$ for some $i$ between $0$ and $k-1$. Prove that, when the grid size $h = x_{j+1} - x_j$ is small enough, $p'(x) \ne 0$ for $x_i \le x \le x_{i+1}$, that is, $p(x)$ is monotone in the interval $[x_i, x_{i+1}]$. (Hint: first prove the case when $f_1(x) = c_1$, $f_2(x) = c_2$ and $c_1 \ne c_2$ are two constants.)

Problem 4 (yau-contest 2017)

Let $b \in \mathbb{R}^n$. Suppose $A \in M_{n\times n}(\mathbb{R})$ and $B \in M_{n\times n}(\mathbb{R})$ are two $n \times n$ matrices. Let $A$ to be non-singular.

(a) Consider the iterative scheme: $A x^{k+1} = b - B x^k$. State and prove the necessary and sufficient condition for the iterative scheme to converge.

(b) Suppose the spectral radius of $A^{-1}B$ satisfies $\rho(A^{-1}B) = 0$. Prove that the iterative scheme converges in $n$ iterations.

(c) Consider the following iterative scheme:

$x^{(k+1)} = \omega_1 x^{(k)} + \omega_2(c_1 - M x^{(k)}) + \omega_3(c_2 - M x^{(k)}) + \cdots + \omega_k(c_{k-1} - M x^{(k)})$

where $M$ is symmetric and positive definite, $\omega_1 > 1$, $\omega_2, \ldots, \omega_k > 0$ and $c_1, \ldots, c_{k-1} \in \mathbb{R}^n$. Deduce from (a) that the iterative scheme converges if and only if all eigenvalues of $M$ (denote it as $\lambda(M)$) satisfies:

$$
\frac{\omega_1 - 1}{\sum_{i=2}^{k} \omega_i} < \lambda(M) < \frac{\omega_1 + 1}{\sum_{i=2}^{k} \omega_i}.
$$

(d) Let $A$ be non-singular. Now, consider the following system of iterative scheme (*):

$A x_1^{(k+1)} = b_1 - B x_2^{(k)}, \quad A x_2^{(k+1)} = b_2 - B x_1^{(k)}$.

Find and prove the necessary and sufficient condition for the iterative scheme (*) to converge.

For the iterative scheme (**):

$A x_1^{(k+1)} = b_1 - B x_2^{(k)}, \quad A x_2^{(k+1)} = b_2 - B x_1^{(k+1)}$.

Find and prove the necessary and sufficient condition for the iterative scheme (**) to converge. Compare the rate of convergence of the iterative schemes (*) and (**).

Problem 5 (yau-contest 2017)

Consider the differential equation

$-u'' + \alpha u = f, \; x \in (0, 1)$.

Here, prime denotes for $d/dx$ and $\alpha$ is a constant. We consider a mixed boundary condition

$u(0) = 0, \; u'(1) - b u(0) = 0$.

This equation is approximated by a standard finite difference method:

$$
\frac{-U_{j-1} + 2U_j - U_{j+1}}{h^2} + \alpha U_j = f_j, \quad j = 1, \ldots, N-1.
$$

Here, $N$ is the number of grid points, $h = 1/N$ is the mesh size, $U_j$ is the approximate solution at $x_j := jh$, and $f_j = f(x_j)$. The nonduary condition is approximated by

$$
U_0 = 0, \quad \frac{U_N - U_{N-1}}{h} - b U_N = 0.
$$

Problem unknown (yau-contest 2017)

The PDE is

$u_t + a u_x = 0$, $a > 0$.

We discretize this PDE by For solving the following partial differential equation

(1) $u_t + f(u)_x = 0$, \quad $0 \le x \le 1$

where $f'(u) \ge 0$, with periodic boundary condition, we can use the following semi-discrete upwind scheme

(2) $\frac{d}{dt} u_j + \frac{f(u_j) - f(u_{j-1})}{\Delta x} = 0$, \quad $j = 1, 2, \cdots, N,$

with periodic boundary condition

(3) $u_0 = u_N$,

where $u_j = u_j(t)$ approximates $u(x_j, t)$ at the grid point $x = x_j = j\Delta x$, with $\Delta x = \frac{1}{N}$.

(a) Prove the following $L^2$ stability of the scheme

(4) $\frac{d}{dt} E(t) \le 0$,

where $E(t) = \sum_{j=1}^N |u_j|^2 \Delta x$.

(b) Do you believe (4) is true for $E(t) = \sum_{j=1}^N |u_j|^p \Delta x$ for arbitrary integer $p \ge 1$? If yes, prove the result. If not, give a counterexample.