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

Consider $\{p_i(x)\}_{i=0}^{\infty}$, a family of orthogonal polynomials associated with the inner product

$$\langle f,g\rangle = \int_{-1}^1 f(x)g(x)\,w(x)\,dx, \qquad w(x) > 0 \text{ for } x\in(-1,1),$$

where $p_i(x)$ is a polynomial of degree $i$. Let $x_0, x_1, \ldots, x_n$ be the roots of $p_{n+1}(x)$. Construct an orthonormal basis in the subspace of the polynomials of degree no more than $n$ such that, for any polynomial in this subspace, the coefficients of its expansion into the basis are equal to the scaled values of this polynomial at the nodes $x_0, x_1, \ldots, x_n$.

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

Consider a 2D fixed point iteration of the form

$$x_{k+1} = f(x_k, y_k), \qquad y_{k+1} = g(x_k, y_k). \tag{1}$$

Assume that the vector-valued function $\tilde H(x,y) = (f(x,y), g(x,y))^T$ is continuously-differentiable, and the infinity norm of the Jacobian matrix is less than $1$ at a unique fixed point $(x_\infty, y_\infty)$.

Now consider a new iteration:

$$x_{k+1} = f(x_k, y_k), \qquad y_{k+1} = g(x_{k+1}, y_k). \tag{2}$$

Prove that iteration (2) is convergent, to the same fixed point as iteration (1), for the initial conditions sufficiently close to the fixed point.

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

Let $A \in \mathbb{R}^{m\times m}$ be a matrix with entries $a_{ij}$ which satisfy
$$ a_{ii} \ge \sum_{j\ne i} |a_{ij}| + 2, \qquad a_{ii} \le 7. $$

(a) Prove that $A^{-1}$ exists.

(b) Prove that $\|A\|_\infty$ is the max row sum (of absolute values) of $A$.

(c) Find both a lower and upper bound for $\|A\|_\infty$.

(d) Now assume $A = A^T$. Find bounds for $\|A\|_2$ and $\|A^{-1}\|_2$.

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

Consider a system of ODE initial value problems of the form:
$$\frac{d}{dt}u = f(u), \qquad u(0) = u_0.$$

Assume that $f(u)$ has the property that the forward Euler (FE) method:
$$U^{n+1} = U^n + k f(U^n),$$

satisfies
$$\|U^{n+1}\| \le \|U^n\|$$
for some norm $\|\cdot\|$ and for all time-steps $k$, $0 < k \le k_{FE}$. Now consider the 2-stage Runge-Kutta method:
$$ U^{(1)} = U^n + k\beta_{10} f(U^n), $$
$$ U^{n+1} = \{\alpha_{20} U^n + k\beta_{20} f(U^n)\} + \{\alpha_{21} U^{(1)} + k\beta_{21} f(U^{(1)})\}, $$
where
$$ \beta_{10} \ge 0,\quad \beta_{20} \ge 0,\quad \beta_{21} \ge 0,\quad \alpha_{20} \ge 0,\quad \alpha_{21} \ge 0,\quad \alpha_{20} + \alpha_{21} = 1.$$

(a) Prove that the above 2-stage Runge-Kutta method also satisfies the inequality:
$$\|U^{n+1}\| \le \|U^n\|$$
under some appropriate time-step restriction: $0 \le k \le k^*$, where you need to explicitly determine $k^*$ in terms of $k_{FE}$.

(b) Explicitly determine the coefficients $\beta_{10}, \beta_{20}, \beta_{21}, \alpha_{20}, \alpha_{21}$ so that
(i) the method is second-order accurate; and
(ii) the maximum allowed time-step, $k^*$, is as large as possible.

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

Construct a third-order accurate Lax-Wendroff-type method for $u_t + a\,u_x = 0$ ($a > 0$ is a constant) in the following way:

(a)
- Expand $u(t+k, x)$ in a Taylor series and keep the first four terms. Replace all time derivatives by spatial derivatives using the equation.
- Construct a cubic polynomial passing through the points $U_{j-2}^n$, $U_{j-1}^n$, $U_j^n$, $U_{j+1}^n$.
- Approximate the spatial derivatives in the Taylor series by the exact derivatives of the above constructed cubic polynomial.

(b) Verify that the truncation error is $O(k^3)$ if $h = O(k)$.

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

Suppose you have $60\text{K}$ to invest and there are 3 investment options available. You must invest in multiples of $10\text{K}$. If $d_i$ dollars are invested in investment $i$ then you receive a net value (as the profit) of $r_i(d_i)$ dollars. For $d_i > 0$ we have
$$r_1(d_1) = (7d_1 + 2)\times 10, \qquad r_2(d_2) = (3d_2 + 7)\times 10, \qquad r_3(d_3) = (4d_3 + 5)\times 10,$$
and $d_1(0) = d_2(0) = d_3(0)$.
All are measured in $10\text{K}$ dollars. The objective is to maximize the net value of your

Problem unknown (yau-contest 2022)

investments. This can be formulated as a linear programming problem:

$$
\max_{d_1, d_2, d_3}\; r_1(d_1) + r_2(d_2) + r_3(d_3),
$$

such that

$$
d_1 + d_2 + d_3 \le 6,
$$

$$
d_i \ge 0 \quad i = 1, 2, 3 \text{ are integers}.
$$