Problem 1 (yau-contest 2014)

Given a finite positive (Borel) measure $d\mu$ on $[0,1]$, define its sequence of moments as follows

$$c_j=\int_0^1 x^j\,d\mu(x),\quad j=0,1,\ldots.$$

Show that the sequence is completely monotone in the sense that that

$$(I-S)^k c_j\ge 0\quad \text{for all } j,k\ge 0,$$

where $S$ denotes the backshift operator given by $Sc_j=c_{j+1}$ for $j\ge 0$.

Problem 2 (yau-contest 2014)

We recall that a polynomial

$$f(X)=a_d X^d+a_{d-1}X^{d-1}+\cdots+a_1X+a_0\in \mathbb{Z}[X]$$

is called an Eisenstein polynomial if for some prime $p$ we have

(i) $p\mid a_i$ for $i=0,\ldots,d-1$, 
(ii) $p^2\nmid a_0$, 
(iii) $p\nmid a_d$.

Eisenstein polynomials are well-know to be irreducible over $\mathbb{Z}$, so they can be used to construct explicit examples of irreducible polynomials.

Questions:

(i) Prove that a composition $f(g(X))$ of two Eisenstein polynomials $f$ and $g$ is an Eisenstein polynomial again.

(ii) Suggest a multivariate generalisation of the Eisenstein polynomials. That is, describe a class polynomials $F(X_1,\ldots,X_m)$ in terms of the divisibility properties of their coefficients that are guaranteed to be irreducible.

Problem 3 (yau-contest 2014)

For solving the following partial differential equation

$$u_t+f(u)_x=0,\qquad 0\le x\le 1\tag{1}$$

where $f'(u)\ge 0$, with periodic boundary condition, we can use the following semi-discrete discontinuous Galerkin method: Find $u_h(\cdot,t)\in V_h$ such that, for all $v\in V_h$ and $j=1,2,\cdots,N$,

$$\int_{I_j} (u_h)_t v\,dx-\int_{I_j} f(u_h)\,v_x\,dx+f\big((u_h)_{j+1/2}^{-}\big)\,v_{j+1/2}^{-}-f\big((u_h)_{j-1/2}^{-}\big)\,v_{j-1/2}^{+}=0.\tag{2}$$

with periodic boundary condition

$$(u_h)_{1/2}^{-}=(u_h)_{N+1/2}^{-};\qquad (u_h)_{N+1/2}^{+}=(u_h)_{1/2}^{+}.\tag{3}$$

where $I_j=(x_{j-1/2},x_{j+1/2})$, $0=x_{1/2}<x_{3/2}<\cdots<x_{N+1/2}=1$, $h=\max_j(x_{j+1/2}-x_{j-1/2})$, $v_{j+1/2}^{+}=v(x_{j+1/2}^{+},t)$, and 

$$V_h=\{v: v|_{I_j}\text{ is a polynomial of degree at most }k\text{ for }1\le j\le N\}.$$

Prove the following $L^2$ stability of the scheme

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

where $$E(t)=\int_0^1 \big(u_h(x,t)\big)^2 dx.$$

Problem 4 (yau-contest 2014)

Consider the linear system $Ax=b$. The GMRES method is a projection method which obtains a solution in the $m$-th Krylov subspace $K_m$ so that the residual is orthogonal to $AK_m$. Let $r_0$ be the initial residual and let $v_0=r_0$. The Arnoldi process is applied to build an orthonormal system $v_1,v_2,\cdots,v_{m-1}$ with $v_1=Av_0/\|Av_0\|$. The approximate solution is obtained from the following space

$$K_m=\operatorname{span}\{v_0,v_1,\cdots,v_{m-1}\}.$$

(i) (5 points) Show that the approximate solution is obtained as the solution of a least-square problem, and that this problem is triangular.

(ii) (5 points) Prove that the residual $r_k$ is orthogonal to $\{v_1,v_2,\cdots,v_{k-1}\}$.

(iii) (5 points) Find a formula for the residual norm.

(iv) (5 points) Derive the complete algorithm.

Problem 5 (yau-contest 2014)

(i) Set $x_0=0$. Write the recurrence

$$x_k=2x_{k-1}+b_k,\qquad k=1,2,\cdots,n,$$

in a matrix form $A\vec{x}=\vec{b}$. For $b_1=-\tfrac{1}{3}$, $b_k=(-1)^k$, $k=2,3,\cdots,n$, verify that $x_k=(-1)^k/3$, $k=1,2,\cdots,n$, is the exact solution.

(ii) Find $A^{-1}$ and compute condition number of $A$ in $L^1$ norm.