Problem 1 (yau-contest 2023)

Consider the forward and the centered finite difference formulas

$$D_h^+ f(x_0) = \frac{f(x_0 + h) - f(x_0)}{h},$$
$$D_h^0 f(x_0) = \frac{f(x_0 + h) - f(x_0 - h)}{2h},$$

to approximate the derivative of $f$ at a point $x_0$. Assume $f$ is a smooth function in a neighborhood of $x_0$ containing the points $x_0 + h$ and $x_0 - h$.

(a) Prove that $D_h^+ f(x_0)$ and $D_h^0 f(x_0)$ approximate $f'(x_0)$ to $O(h)$ and $O(h^2)$, respectively.

(b) Derive an $O(h^2)$ approximation to $f'(x_0)$ from $D_h^+ f(x_0)$ by doing Richardson extrapolation.

(c) Take $f(x) = \sin x$ and $x_0 = 0$. Prove that both $D_h^+ f(x_0)$ and $D_h^0 f(x_0)$ converge quadratically to $f'(x_0)$ as $h \to 0$ and that in fact they produce the same approximation to $f'(x_0)$ in this particular case.

Problem 2 (yau-contest 2023)

For functions defined on a closed interval $[0,1]$, we want to compute the following definite integral,

$$I[f] = \int_0^1 f(x)\,\log(1/x)\,dx.$$

Here we consider the weight function $\log(1/x)$, and denote $P_n(x)$ as the monic orthogonal polynomials for the corresponding weighted inner product.

(a) Let $P_0 = 1$. Find $P_1(x)$, and the corresponding node $x_1^1$ and weight $\omega_1^1$ for the 1-point Gaussian quadrature rule.

(b) Derive a recursive formula for $P_{n+1}(x)$ using $P_n(x)$ and $P_{n-1}(x)$.

(c) Consider the normalized orthogonal polynomials $Q_n(x) = P_n(x)/\|P_n\|$, where

$$\|P_n\| = \sqrt{\int P_n(x)^2 \log(1/x) \, dx}.$$

Derive a recursive formula for $Q_{n+1}(x)$ using $Q_n(x)$ and $Q_{n-1}(x)$.

(d) Use the above recursive formula to show that $x = \lambda$ is a node of the 4-point Gaussian quadrature if and only if it is an eigenvalue of a symmetric, tridiagonal matrix. Write out the form of the symmetric and tridiagonal matrix explicitly.

Problem 3 (yau-contest 2023)

Let $A$ be a real $n \times n$ matrix with distinct eigenvalues such that

$$|\lambda_1| > |\lambda_2| \ge |\lambda_3| \ge \cdots \ge |\lambda_n| \ge 0,$$

with corresponding eigenvectors $\{v_j\}_{j=1}^n.

(a) Show that the power iteration

$$z_m = \frac{A^m z_0}{\|A^m z_0\|_\infty} \longrightarrow \pm \frac{v_1}{\|v_1\|_\infty}, \quad \forall z_0 \in \mathbb{R}^n.$$

(b) Consider the following iteration with initial guess $x_0 = y_0 = 1$,

$$x_{n+1} = x_n + y_n, \quad y_{n+1} = x_{n+1} + x_n.$$

Show that $y_n/x_n \to \sqrt{2}$ as $n \to \infty$.

Problem 4 (yau-contest 2023)

Consider the initial value problem

$$y' = f(t, y), \qquad 0 < t \le T,$$
$$y(0) = y_0.$$

Assume $f$ is continuous and Lipschitz in $y$ in $[0, T] \times (-\infty, \infty)$. Denote $y_n \approx y(t_n)$, $t_n = n h$, and $h = T/N$, with $N$ a positive integer, and consider the one-step method

$$y_{n+1} = y_n + \alpha h f(t_n, y_n) + \beta h f(t_n + \gamma h, y_n + \gamma h f(t_n, y_n)),$$

where $\alpha$, $\beta$ and $\gamma$ are real parameters.

(a) Prove that the method is consistent if and only if $\alpha + \beta = 1$, and the order of the method can not exceed 2.

(b) Suppose that a second-order method of the above form is applied to $f(t, y) = -\lambda y$ with $\lambda > 0$, and the initial condition $y_0 = 1$. Show that the sequence $(y_n)_{n \ge 0}$ is bounded if and only if $h \le \frac{2}{\lambda}$. Show further that for such $h$,

$$|y(t_n) - y_n| \le \frac{1}{6} \lambda^3 h^2 t_n, \quad n \ge 0.$$

Problem 5 (yau-contest 2023)

Let $u(t, x)$ be the solution of the initial-boundary value problem

$u_t = D u_{xx},\quad 0 < x < L,\quad 0 < t \le T,$ (5)

$u(0, x) = f(x)$ (6)

$u(t, 0) = u(t, L) = 0,$ (7)

where $L > 0$ and $D > 0$. Consider the finite difference scheme

$\dfrac{u_j^{n+1} - u_j^{n}}{\Delta t} = D \dfrac{u_{j+1}^{n} - 2u_j^{n} + u_{j-1}^{n}}{(\Delta x)^2},\quad j = 1, \ldots, M-1,\ \ n = 0, 1, \ldots, N-1$ (8)

with $u_0^{n} = u_M^{n} = 0$ for all $n$ and $u_j^{0} = f(j\Delta x)$, $j = 0, \ldots, M$. Here $\Delta t = T/N$ and $\Delta x = L/M$ and $u_j^{n} \approx u(n\Delta t, j\Delta x)$.

(a) Prove that (8) is consistent with (5).

(b) Prove that if $\Delta t \le \dfrac{1}{2D}(\Delta x)^2$ the finite difference scheme (8) is stable under the $L^{\infty}$ norm.

(c) Prove that if $\Delta t \le \dfrac{1}{2D}(\Delta x)^2$ the finite difference scheme (8) converges in the $L^{\infty}$ norm to the exact solution of (5)–(7).

Problem 6 (yau-contest 2023)

Let $\psi^{\varepsilon}(t, x)$ be the solution to the following Schrödinger equation:

$i\varepsilon\, \dfrac{\partial \psi^{\varepsilon}}{\partial t} = - \dfrac{\varepsilon^{2}}{2} \nabla_{x}^{2} \psi^{\varepsilon} + V(x)\, \psi^{\varepsilon},\quad x = (x_{1}, \cdots, x_{n})^{\mathrm{T}} \in \mathbb{R}^{n},$

where $i = \sqrt{-1}$, $\varepsilon \ll 1$ is a small positive real number (rescaled Planck constant), $\nabla_{x}^{2} = \sum_{j=1}^{n} \partial_{x_j}^{2}$, and $V(x) \in C^{\infty}(\mathbb{R}^{n})$ is the potential function.

Consider the WKB expansion

$\psi^{\varepsilon}(t, x) = A(t, x) e^{i S(t, x)/\varepsilon},$

(a) Derive equations for $A(t, x)$ and $S(t, x)$ by asymptotic expansion. (Here both $A(t, x)$ and $S(t, x)$ are real-valued functions, and do not depend on $\varepsilon$.)

(b) Define $u(t, x) = \nabla_{x} S(t, x) \in \mathbb{R}^{n}$. Derive an equation for $u(t, x)$. Suppose $u(0, x) \in C^{\infty}(\mathbb{R}^{n})$, will $u(t, x)$ always be in $C^{\infty}(\mathbb{R}^{n})$ for all $t > 0$? Explain why.