Problem 1 (yau-contest 2019)

Show that the quadrature formula
$$\int_{-1}^{1} \frac{f(x)}{\sqrt{1-x^2}}\,dx = \frac{\pi}{n} \sum_{k=0}^{n-1} f\!\left(\cos\frac{(2k+1)\pi}{2n}\right)$$
is exact for all polynomials of degree up to and including $2n-1$.

Problem 2 (yau-contest 2019)

Let $x=\{x_0,\ldots,x_{N-1}\}\in\mathbb{R}^N$, $x\neq 0$ and $\hat{x}$ be its discrete Fourier transform, i.e.
$$\hat{x}_w=\frac{1}{\sqrt{N}}\sum_{t=0}^{N-1} x_t\,\exp\!\left(-\frac{2\pi iwt}{N}\right),\quad w=0,\ldots,N-1.$$
Prove that $\|x\|_0\,\|\hat{x}\|_0\ge N$ where $\|x\|_0$ denotes the number of nonzero entries in $x$. (Hint: show that $\hat{x}$ cannot have $\|\hat{x}\|_0$ consecutive zeros.)

Problem 3 (yau-contest 2019)

Let $m\le n$. Consider the $(n+m)\times(n+m)$ real matrix defined by
$$A=\begin{pmatrix} I & X \\ X^{\top} & O \end{pmatrix},$$
where $I$ is the $n\times n$ identity matrix, $X$ is a full-rank $n\times m$ matrix, $O$ is the $m\times m$ zero matrix.

(i) Show that $A$ is nonsingular.

(ii) Find the eigenvalues of $A$, some of which are in terms of the singular values of $X$.

(iii) Under what conditions on $X$ would the iteration
$$x_{n+1}=x_n-(Ax_n-b)$$
converge to the solution of $Ax=b$ for any $(n+m)\times(n+m)$ real vector $b$?

Problem 4 (yau-contest 2019)

Let $f$ be a continuously differentiable convex function defined on $\mathbf{R}^n$, i.e., $f: \mathbf{R}^n\to \mathbf{R}$ is continuously differentiable and for any $x,y\in \mathbf{R}^n$ and any $\alpha\in(0,1)$, $f(\alpha x+(1-\alpha)y)\le \alpha f(x)+(1-\alpha)f(y)$. Suppose that the gradient of $f$ is Lipschitz continuous, i.e., there exists a constant $L>0$ such that
$$\|\nabla f(x)-\nabla f(y)\|_2\le L\|x-y\|_2.$$
Prove the following inequalities:
(i) $f(y)\le f(x)+ (\nabla f(x))^T(y-x)+ \tfrac{L}{2}\|y-x\|_2^2$, $\forall x,y\in \mathbf{R}^n$;
(ii) $f(y)\ge f(x)+ (\nabla f(x))^T(y-x)+ \tfrac{1}{2L}\|\nabla f(y)-\nabla f(x)\|_2^2$, $\forall x,y\in \mathbf{R}^n$;
(iii) $\|\nabla f(y)-\nabla f(x)\|_2^2\le (\nabla f(y)-\nabla f(x))^T(y-x)$, $\forall x,y\in \mathbf{R}^n$.

Problem 5 (yau-contest 2019)

(i) Determine the order of Störmer’s method,
$$y_{n+2}-2y_{n+1}+y_n=h^2 f(t_{n+1},y_{n+1}),\quad n\ge 0,$$
for solving the second order system of ODEs
$$y''=f(t,y),\quad t\ge 0,$$
with the initial conditions $y(0)=y_0$ and $y'(0)=y_0'$.

(ii) Using the second order central differences in space and Störmer’s method in time, construct a scheme to solve the wave equation,
$$u_{tt}=u_{xx}.$$

(iii) Determine the condition for its stability.