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

Let $f\in C^{k+1}[-1,1]$ and $[-1,1]$ be partitioned into subintervals $I_j=[(j-1)h,jh]$ of width $h$. Assume $p$ is a polynomial of degree $k$ which approximates $f$ in $I_j$ with
$$\max_{x\in I_j} |p_j(x)-f(x)|\le C_0 h^{k+1},$$
where $C_0$ is a constant independent of $j$. Show that there exists another constant $C$, independent of $j$, such that
$$\max_{x\in I_{j\pm 1}} |p_j(x)-f(x)|\le C h^{k+1}.$$
(as long as $I_{j\pm1}\subset [-1,1]$, of course).

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

Consider the iteration
$$x_{n+1}=x_n-\left(\frac{x_n-x_0}{f(x_n)-f(x_0)}\right)f(x_n)$$
for finding the roots of a two times continuous differentiable function $f(x)$. Assuming the method converges to a simple root $x^*$, what is the rate of convergence? Justify your answer.

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

Suppose $A$ is an $m\times m$ matrix with a complete set of orthonormal eigenvectors $\mathbf{q}_1,\ldots,\mathbf{q}_m$ and corresponding eigenvalues $\lambda_1,\ldots,\lambda_m$. Assume that $|\lambda_1|>|\lambda_2|>|\lambda_3|$ and $\lambda_j\ge \lambda_{j+1}$ for $j=3,\ldots,m$. Consider the power method $v^{(k)}=Av^{(k-1)}/\lambda_1$, with $v^{(0)}=\alpha_1\mathbf{q}_1+\cdots+\alpha_m\mathbf{q}_m$ where $\alpha_1$ and $\alpha_2$ are both nonzero. Show that the sequence $\{v^{(k)}\}_{k=0}^{\infty}$ converges linearly to $\alpha_1\mathbf{q}_1$ with asymptotic constant $C=|\lambda_2/\lambda_1|.$

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

For the initial value problem $y'=f(t,y)$, $y(0)=y_0$ on the interval $[0,T]$, consider the implicit two-step method
$$y_{n+1}=\tfrac{4}{3}y_n-\tfrac{1}{3}y_{n-1}+\tfrac{2h}{3}f(t_{n+1},y_{n+1}),$$
$$y_1=y_0+h f(t_1,y_0),$$
where $h$ is the step size and $t_n=nh$.

(a) What is the order of the accuracy of the scheme?

(b) Check the stability of the scheme by analyzing the stability polynomial?

(c) Find the stability region of the scheme.

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

Suppose the difference scheme $u^{n+1}=Bu^n$ is stable, and $C(\Delta\tau)$ is a bounded family of operators. Show that the scheme
$$u^{n+1}=(B+\Delta\tau\,C(\Delta\tau))u^n$$
is stable.

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

Let $A$ be an $m\times m$ nonsingular matrix. Suppose $\inf_{p_n\in P^n}\|p_n(A)\|=\|p^*(A)\|>0$ where $P^n$ denotes the set of all degree-$n$ monic polynomials:
$$P^n=\{\,p:\ p\text{ is a polynomial of degree }n,\ p(z)=z^n+\cdots\,\}.$$
Prove that $p^*$ is unique.