Problem 1 (yau-contest 2021)
Section: Computational and Applied Mathematics

(a) Show that
$$T_n(x) = \cos(n\,\arccos x), \quad x \in [-1,1],$$
is a polynomial of degree $n$ with extrema at
$$x_k = \cos\!\left(\frac{k\pi}{n}\right), \quad k = 0,1,\ldots,n,$$
and leading coefficient $2^{n-1}$.

(b) Show that if $f \in C^{n+1}[-1,1]$ and if $P(x)$ is the polynomial with degree at most $n$ that interpolates $f$ at $x_k$, $k = 0,1,\ldots,n$, then
$$\|f(x) - P(x)\|_\infty \le \frac{1}{2^{n-1}(n+1)!}\,\|f^{n+1}\|_\infty.$$

Problem 2 (yau-contest 2021)
Section: Computational and Applied Mathematics

Let $S(x)$ be a cubic spline with knots $\{t_i\}_{i=0}^n$. If it is determined that $S(x)$ is linear over $[t_1,t_2]$ and $[t_3,t_4]$. Prove that $S(x)$ is also linear over $[t_2,t_3]$.

Problem 3 (yau-contest 2021)
Section: Computational and Applied Mathematics

Let $f : \mathbb{R} \to \mathbb{R}$ be defined by $f(x) = 2x - \cos x$.

(a) Prove that the equation $f(x) = 0$ has a unique solution $x^* \in \mathbb{R}$ that lies in the interval $\left(\tfrac{1}{4}, \tfrac{1}{2}\right)$.

(b) Prove that the sequence defined by the fixed point iteration
$$x_0,$$
$$x_n = \tfrac{1}{2}\cos x_{n-1}, \quad n = 1,2,\ldots,$$
converges to $x^*$ with any initial guess $x_0$.

(c) For the fixed point iteration in (b) with $x_0 = \tfrac{\pi}{6}$, determine an $n$ that guarantees $|x_n - x^*| < \tfrac{1}{2} \times 10^{-8}$. For the fixed point iteration in (b) with $x_0 = 20$, determine an $n$ that guarantees $|x_n - x^*| < \tfrac{1}{4}$.

Problem 4 (yau-contest 2021)
Section: Computational and Applied Mathematics

Let matrix $A \in \mathbb{R}^{m\times n}$ with $m \ge n$ and $r = \operatorname{rank}(A) < n$, and assume $A$ has the following SVD decomposition
$$A = [U_1, U_2]\begin{bmatrix}\Sigma_1 & 0\\ 0 & 0\end{bmatrix}[V_1, V_2]^T = U_1\Sigma_1 V_1^T,$$
where $\Sigma_1$ is $r \times r$ nonsingular and $U_1$ and $V_1$ have $r$ columns. Let $\sigma = \sigma_{\min}(\Sigma_1)$, the smallest nonzero singular value of $A$. Consider the following least square problem, for some $b \in \mathbb{R}^m$,
$$\min_{x \in \mathbb{R}^n} \|Ax - b\|_2.$$

(a) Show that all solutions $x$ can be written as
$$x = V_1 \Sigma_1^{-1} U_1^T b + V_2 z_2,$$
with $z_2$ an arbitrary vector.

(b) Show that the solution $x$ has minimal norm $\|x\|_2$ precisely when $z_2 = 0$, and in which case,
$$\|x\|_2 \le \frac{\|b\|_2}{\sigma}.$$

Problem 5 (yau-contest 2021)
Section: Computational and Applied Mathematics

Consider the family of semi-implicit Runge-Kutta methods
$$k_1 = f(y_n + \beta h k_1), \quad k_2 = f(y_n + h k_1 + \beta h k_2),$$
$$y_{n+1} = y_n + h\Big(\big(\tfrac{1}{2} + \beta\big)k_1 + \big(\tfrac{1}{2} - \beta\big)k_2\Big).$$

(a) Determine the order and the principal part of the local truncation error.

(b) Show that if $\beta > \tfrac{1}{2}$, then the negative real axis $\{ z : \operatorname{Re}(z) < 0, \operatorname{Im}(z) = 0 \}$ is contained in the region of absolute stability of the method.

Problem 6 (yau-contest 2021)
Section: Computational and Applied Mathematics

Consider the Beam equation from mechanics with boundary conditions that model a cantilever beam:
$$u^{(4)} = f(x), \quad x \in (0,1),$$
$$u'' = f(x), \quad x \in (0,1),$$
$$u(0) = u'(0) = u''(1) = u'''(1) = 0.$$
(1)

(a) Recast this equation into a variational problem, stating the trial and test function spaces.

(b) Interpret the variational problem as an energy minimization problem, clearly stating the energy functional. Prove that the variational problem and the energy minimization problems are equivalent.

(c) Develop a CG(3) (cubic continuous Galerkin method) finite element method for this problem.

(d) Prove an a priori error estimate for this method in the energy norm:
$$\|e\|_E = \left( \int_0^1 (e'')^2\,dx \right)^{\tfrac{1}{2}},$$
Where $e = u(x) - U(x)$, in which, $u(x)$ is the exact solution to VP (variational problem), $U(x)$ is the FEM (finite element method) solution.

(e) Prove an a priori error estimate for this method in the $L_2$ norm:
$$\|e\|_{L_2} =: \|e\| = \left( \int_0^1 e^2\,dx \right)^{\tfrac{1}{2}}.$$