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

Let $A \in \mathbb{R}^{n\times n}$ be a non-singular matrix. Let $u, v \in \mathbb{R}^n$ be column vectors. Define the rank 1 perturbation $\hat{A} = A + u w^T$.

(a) Derive a necessary and sufficient condition for $\hat{A}$ to be invertible.

(b) Let $x, z$ and $b$ be column vectors in $\mathbb{R}^n$. Suppose one can solve $A z = b$ with $\mathcal{O}(n)$ floating-point operations (flops). Under the conditions derived in (a), design an algorithm to solve $\hat{A} x = b$ with $\mathcal{O}(n)$ flops, and provide justification for your answer.

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

Consider the integral
$$\int_0^{\infty} f(x)\,dx$$
where $f$ is continuous, $f'(0) \neq 0$, and $f(x)$ decays like $x^{-1-\alpha}$ with $\alpha>0$ in the limit $x\to\infty$.

(a) Suppose you apply the equispaced composite trapezoid rule with $n$ subintervals to approximate
$$\int_0^L f(x)\,dx.$$
What is the asymptotic error formula for the error in the limit $n \to \infty$ with $L$ fixed?

(b) Suppose you consider the quadrature from (a) to be an approximation to the full integral from $0$ to $\infty$. How should $L$ increase with $n$ to optimize the asymptotic rate of total error decay? What is the rate of error decrease with this choice of $L$?

(c) Make the following change of variable $x = \dfrac{L(1+y)}{1-y}$, $\; y = \dfrac{x - L}{x + L}$ in the original integral to obtain
$$\int_{-1}^1 F_L(y)\,dy.$$
Suppose you apply the equispaced composite trapezoid rule; what is the asymptotic error formula for fixed $L$?

(d) Depending on $\alpha$, which method — domain truncation or change-of-variable — is preferable?

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

Consider the Chebyshev polynomial of the first kind
$$T_n(x) = \cos(n\theta), \quad x = \cos(\theta), \quad x \in [-1,1].$$
The Chebyshev polynomials of the second kind are defined as
$$U_n(x) = \frac{1}{n+1} T'(x), \quad n \ge 0.$$

(a) Derive a recursive formula for computing $U_n(x)$ for all $n \ge 0$.

(b) Show that the Chebyshev polynomials of the second kind are orthogonal with respect to the inner product
$$\langle f, g \rangle = \int_{-1}^1 f(x) g(x) \sqrt{1-x^2}\, dx.$$

(c) Derive the 2-point Gaussian Quadrature rule for the integral
$$\int_{-1}^1 f(x) \sqrt{1-x^2}\, dx = \sum_{j=1}^2 w_j f(x_j).$$

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

Consider the boundary value problem
$$-\frac{d}{dx}\left(a(x)\frac{du}{dx}\right) = f(x), \qquad u(0) = u(1) = 0$$
where $a(x) > \delta \ge 0$ is a bounded differentiable function in $[0,1]$. We assume that, although $a(x)$ is available, an expression for its derivative, $\frac{da}{dx}$, is not available.

(a) Using finite differences and an equally spaced grid in $[0,1]$, $x_l = h l$, $l = 0, \ldots, n$ and $h = 1/n$, we discretize the ODE to obtain a linear system of equations, yielding an $\mathcal{O}(h^2)$ approximation of the ODE. After the application of the boundary conditions, the resulting coefficient matrix of the linear system is an $(n-1)\times(n-1)$ tridiagonal matrix. Provide a derivation and write down the resulting linear system (by giving the expressions of the elements).

(b) Utilizing all the information provided, find a disc in $\mathbb{C}$, the smaller the better, that is guaranteed to contain all the eigenvalues of the linear system constructed in part (a).

Problem 5 (yau-contest 2024)

(a) Verify that the PDE $u_t = u_{xxx}$ is well posed as an initial value problem.

(b) Consider solving it numerically using the scheme
$$rac{u(t+k,x)-u(t-k,x)}{2k}=rac{-\tfrac{1}{2}u(x-2h,t)+u(x-h,t)-u(x+h,t)+\tfrac{1}{2}u(x+2h,t)}{h}.$$
Determine this scheme’s stability condition.

Problem 6 (yau-contest 2024)

Consider the diffusion equation
$$\frac{\partial v}{\partial t}=\mu\frac{\partial^2 v}{\partial x^2},\quad v(x,0)=\phi(x),\quad \int_a^b v(x,t)\,dx=0$$
with $x\in[a,b]$ and periodic boundary conditions. The solution is to be approximated using the central difference operator $L$ for the 1D Laplacian,
$$L v_m=\frac{v_{m+1}-2v_m+v_{m-1}}{h^2},$$
and the following two finite difference approximations:
(i) Forward-Euler
$$v_{n+1}=v_n+\mu k L v_n,\tag{1}$$
(ii) Crank-Nicolson
$$v_{n+1}=v_n+\mu k\big(L v_n+L v_{n+1}\big).\tag{2}$$
Throughout, consider $[a,b]=[0,2\pi]$ and the finite difference stencil to have periodic boundary conditions on the spatial lattice $[0,h,2h,\ldots,(N-1)h]$ where $h=\tfrac{2\pi}{N}$ and $N$ is even.

(a) Determine the order of accuracy of the central difference operator $L v$ in approximating the second derivative $v_{xx}$.

(b) Using $v_m^n=\sum_{l=0}^{N-1}\hat v_l^n\exp\!\left(-i\,\frac{2\pi l m}{N}\right)$ give the updates $\hat v_l^{n+1}$ in terms of $\hat v_l^n$ for each of the methods, including the case $l=0$.

(c) Give the solution for $v_m^n$ for each method when the initial condition is $\phi(m\,\Delta x)=(-1)^m$.

(d) What are the stability constraints on the time step $k$ for each of the methods, if any, in equations (1) and (2)? Show there are either no constraints or express them in the form $k\le F(h,\mu)$.