Problem 1 (qiuzhen-qualify 2023-fall)
Section: Applied Math

Consider the Newton’s method for finding a solution $x_*$ to $f(x)=0$, where $f\in C^2(a,b)$, $x_*\in(a,b)$.

1: determine $x_0\in(a,b)$.
2: for $k=0,1,2,\ldots$ do
3: $x_{k+1}=x_k-\dfrac{f(x_k)}{f'(x_k)}$.
4: end for

(1). Prove that if $x_0$ is sufficiently close to $x_*$ and $f'(x_*)\ne0$, then $\lim_{k\to\infty}x_k=x_*$ and
$$\lim_{k\to\infty}\frac{x_{k+1}-x_*}{(x_k-x_*)^2}=\frac{f''(x_*)}{2f'(x_*)}.$$

(2). In practice sometimes the derivative is not easy to be obtained. As a result, a difference is used instead:
$$x_{k+1}=x_k-\frac{x_k-x_{k-1}}{f(x_k)-f(x_{k-1})}\,f(x_k).$$
Prove that if $x_0$ is sufficiently close to $x_*$, then $x_k\to x_*$, and
$$\lim_{k\to\infty}\frac{x_{k+1}-x_*}{(x_k-x_*)(x_{k-1}-x_*)}=\frac{f''(x_*)}{2f'(x_*)}.$$

Problem 2 (qiuzhen-qualify 2023-fall)
Section: Applied Math

Consider the explicit shifted QR method for computing eigenvalues of a matrix $A\in\mathbb{C}^{n\times n}$.

1: find an upper Hessenberg matrix $H_0$ and a unitary matrix $U_0$ such that $H_0=U_0^H A U_0$.
2: for $i=0,1,2,\ldots$ do
3: determine a scalar $\mu_k$.
4: compute QR factorization $Q_kR_k=H_k-\mu_k I$.
5: $H_{k+1}=R_kQ_k+\mu_k I$.
6: end for

(1). Prove that $H_i$, $i=1,2,\ldots$ are all upper Hessenberg matrices.

(2). Interpret the purpose to use $H_0$ rather than $A$ in the iteration.

(3). Suppose that $A$ has $n$ distinct eigenvalues and none of the shifts $\mu_i$, $i=1,2,\ldots$ is an eigenvalue of $A$. Prove that $H_i$, $i=0,1,2,\ldots$ are unreduced upper Hessenberg matrices. (An upper Hessenberg matrix $H$ is called unreduced, if $H_{i+1,i}\ne0$ for $i=1,\ldots,n-1.$)

(4). Write
$$H_k=\begin{bmatrix}G_k&u_k\\ \varepsilon_k e^T&\alpha_k\end{bmatrix}$$
where $\alpha_k,\varepsilon_k\in\mathbb{C}$, $u_k,e\in\mathbb{C}^{n-1}$ and $e=\begin{bmatrix}0\\ \vdots\\ 0\\ 1\end{bmatrix}$. Suppose $A$ has $n$ distinct eigenvalues. Prove that
$$|\varepsilon_{k+1}|\le \rho_k^2\,\|u_k\|_2\,|\varepsilon_k|^2+\rho_k\,|\alpha_k-\mu_k|\,|\varepsilon_k|,$$
where $\rho_k=\|\,(G_k-\mu_k I)^{-1}\,\|_2$, provided $\mu_k$ is not an eigenvalue of $G_k$.

Problem 3 (qiuzhen-qualify 2023-fall)
Section: Applied Math

If $p$ is a polynomial of degree $n$ (on $[-1,1]$), it is determined by its values on an $(n+1)$-point grid on $[-1,1]$. The derivative $p'$, a polynomial of degree $(n-1)$, is determined on the same grid. The (classical) differentiation matrix is the $(n+1)$-by-$(n+1)$ matrix $D=(D_{ij})\in\mathbb{R}^{(n+1)\times(n+1)}$ that represents the linear map from the vector of values of $p$ to the vector of values of $p'$, namely:
$$p'(x_i)=\sum_{j=0}^{n} D_{ij}\,p(x_j).$$

(1). Prove that $D_{ij}=l'_j(x_i)$, where $l_j(x)$ is the $j$-th Lagrange basis function.

(2). If a Chebyshev grid $(x_j=\cos(j\pi/n),\;0\le j\le n)$ is adopted, derive explicit formulas for $D_{ij}$.

Problem 4 (qiuzhen-qualify 2023-fall)
Section: Applied Math

Consider a Runge–Kutta method for the ODE $y'=f(t,y)$ ($f$ is Lipschitz continuous in $y$ and uniform in $t$) with the following Butcher tableau:
$$
\begin{array}{c|cc}
0 & 0 & \\
1 & 1 & 0\\\hline
 & \tfrac{1}{2} & \tfrac{1}{2}
\end{array}
$$

(1). Rewrite the scheme in the form of $u_{n+1}=u_n+h\,F(t_n,u_n,h;f)$.

(2). Assume that $f$ is sufficiently smooth. Prove that this method is convergent and determine the order of convergence.

(3). What is the region of absolute stability of this method? Give a description that is as explicit as possible.

Problem 5 (qiuzhen-qualify 2023-fall)
Section: Applied Math

For the equation $u_t+a u_{xxx}=0$ ($a$ is a constant), applying the idea of the Lax–Friedrichs scheme, one can get the scheme
$$u_m^{n+1}=\frac{1}{2}\big(u_{m+1}^n+u_{m-1}^n\big)-\frac{1}{2}a k h^{-3}\big(u_{m+2}^n-2u_{m+1}^n+2u_{m-1}^n-u_{m-2}^n\big),$$
where $k$ and $h$ represent the time step and mesh size, respectively.

(1). Give the leading order term of local trancation error.

(2). Analyze the stability of this scheme.

Problem 6 (qiuzhen-qualify 2023-fall)

Consider the following linear programming problem

$$\max_{x} \langle c, x \rangle \quad \text{s.t.} \quad Ax = b,\ x \ge 0,$$

where $x \in \mathbb{R}^n,\ 0 \le b \in \mathbb{R}^m,\ A \in \mathbb{R}^{m \times n}$ and $c \in \mathbb{R}^n$, $A$ is a full rank matrix and $m < n$.

(1) Prove that the basic feasible solutions are equivalent to the vertices of its feasible region.

(2) Write down the dual problem , and prove that when the optimal solution exists, the dual problem must also have an optimal solution, and the optimal objective values of these two problems are equal.

Problem 7 (qiuzhen-qualify 2023-fall)

Consider the eigenvalue problem with $0 < \epsilon \ll 1$

$$u'' + (\lambda + \epsilon f(x))u = 0,\quad 0 < x < 1$$
$$u(0) = 0,\quad u'(1) = 0.$$

where $f$ is a given smooth function. Give the asymptotic expansion of $\lambda$ such that the accuracy is $O(\epsilon)$.