Problem 1 (qiuzhen-qualify 2025-spring)

(15 points) Assume that $f$ is a periodic function with period $2\pi$. Considering the integration $I(f)=\int_{0}^{2\pi} f(x)\,dx$, prove the following statements on the order of convergence of the composite trapezoidal rule:
$$I^{\mathrm{Tr}}_{h}(f)=h\sum_{i=1}^{n} f(i\cdot h),\quad h=\frac{2\pi}{n}.$$
(i) Assume further that $f\in C^{m}([0,2\pi])$, prove that the above rule achieves $m$–th order convergence, i.e. $\exists\, C>0$ such that $\big|I(f)-I^{\mathrm{Tr}}_{h}(f)\big|\le C\,h^{m}$.
(ii) Assume further that $f$ is analytic, prove that the above rule achieves exponential convergence.

Problem 2 (qiuzhen-qualify 2025-spring)

(15 points) Let $f$ be a continuous function that is $C^{m}$ ($m\ge 1$), such that $f(\alpha)=f^{(1)}(\alpha)=\cdots=f^{(m-1)}(\alpha)=0$ and $f^{(m)}\ne 0$. Answer the following questions:
(i) If $m=1$, i.e. $\alpha$ is a simple zero of the function $f$, prove that there exists a neighborhood of $\alpha$: $D(\alpha,\delta)=\{x:|x-\alpha|\le \delta\}$, such that $\forall x_{0}\in D(\alpha,\delta)$, the sequence generated by Newton's iteration converges to $\alpha$, and the rate of convergence is quadratic.
(ii) If $m>1$, i.e. $\alpha$ is a zero with multiplicity greater than $1$, what is the rate of convergence of Newton's iteration? How about the modified Newton's iteration:
$$x_{k+1}=x_k- m\,\frac{f(x_k)}{f'(x_k)}?$$
Please prove your results.
(iii) If the multiplicity $m$ is greater than $1$ in general but the value is unknown, can you propose an iteration method that achieves superlinear convergence? (You don’t need to prove the result.)

Problem 3 (qiuzhen-qualify 2025-spring)

(20 points) The Sherman-Morrison formula (or the generalized version named Sherman-Morrison-Woodbury formula) is an useful tool in numerical linear algebra. It states: If $A\in\mathbb{R}^{n\times n}$ is an invertible matrix, $u,v\in\mathbb{R}^{n}$ are two vectors satisfying $1+v^{T}A^{-1}u\ne 0$, then the matrix $A+wv^{T}$ is invertible and can be computed by
$$ (A+wv^{T})^{-1}=A^{-1}-\frac{A^{-1}wv^{T}A^{-1}}{1+v^{T}A^{-1}u}\,. $$
(i) Prove the above statement.
(ii) If $\{s_j\}_{j=1}^{n}$ and $\{t_j\}_{j=1}^{n}$ are two sets of points in $[0,1]$, $A\in\mathbb{R}^{n\times n}$ is a matrix defined by
$$A_{j,k}=4n\,\delta_{j,k}+\cos(t_j-s_k)\,, $$
where $\delta_{j,k}$ is the Kronecker delta ($\delta_{j,k}=1$ when $j=k$, $\delta_{j,k}=0$ otherwise). Let $b\in\mathbb{R}^{n}$ be an arbitrary vector. Please give methods for the evaluation of $Ab$, $A^{-1}$, and $|A|$, all with the computational complexity of $O(n)$.

Problem 4 (qiuzhen-qualify 2025-spring)

(15 points) For the system
$$u_t=-v_{xx},\quad v_t=u_{xx},$$
analyse the truncation error and stability of the scheme
$$\frac{u_{j}^{n+1}-u_{j}^{n}}{\tau}=-\frac{1}{2h^{2}}\Big( v_{j+1}^{n+1}-2v_{j}^{n+1}+v_{j-1}^{n+1}+v_{j+1}^{n}-2v_{j}^{n}+v_{j-1}^{n} \Big),$$
$$\frac{v_{j}^{n+1}-v_{j}^{n}}{\tau}=\frac{1}{2h^{2}}\Big( u_{j+1}^{n+1}-2u_{j}^{n+1}+u_{j-1}^{n+1}+u_{j+1}^{n}-2u_{j}^{n}+u_{j-1}^{n} \Big).$$

Problem 5 (qiuzhen-qualify 2025-spring)

(15 points) For the advection equation $u_t+au_x=0$ ($a$ is a constant), the Lax–Wendroff scheme reads as
$$u_{j}^{n+1}= -\frac{1}{2}\nu(1-\nu)u_{j+1}^{n}+(1-\nu^{2})u_{j}^{n}+\frac{1}{2}\nu(1+\nu)u_{j-1}^{n},$$
where $\nu=a\tau/h$.
(i) For the Cauchy problem imposed on the real line, show that
$$\|u^{n+1}\|_{2}^{2}=\|u^{n}\|_{2}^{2}-\frac{1}{2}\nu^{2}(1-\nu^{2})\big(\|\delta_x^{+}u^{n}\|_{2}^{2}-\langle\delta_x^{+}u^{n},\delta_x^{-}u^{n}\rangle\big),$$
where $\|v\|_{2}^{2}=\sum_{j}|v_j|^{2}$, $\langle v,w\rangle=\sum_{j}v_jw_j$, $\delta_x^{-}v_j=v_j-v_{j-1}$, $\delta_x^{+}v_j=v_{j+1}-v_j$.
(ii) Suppose $a>0$, for the problem imposed on $(0,1)$ with homogeneous boundary condition at $x=0$ (i.e., $u_{0}^{n}=0$), give a simple numerical boundary condition for $x=1$ such that the Lax–Wendroff scheme is stable.

Problem 6 (qiuzhen-qualify 2025-spring)

(20 points) Consider a harmonic oscillator with a cubic damping term
$$y''+y+\epsilon(y')^{3}=0,\qquad y(0)=1,\; y'(0)=0,$$
where $y=y(t)$, $t\ge 0$, $\epsilon>0$.
(i) For small $\epsilon$, use the multiple-scale method to study the behavior of $y(t)$ for large $t$, i.e., construct a proper asymptotic solution.
(ii) Make a conclusion on the validity of your asymptotic solution. Briefly justify your conclusion.

Problem 7 (qiuzhen-qualify 2025-spring)

(20 points) Let $K$ be a nonempty closed convex set in $\mathbb{R}^{n}$. For any $z\in\mathbb{R}^{n}$, define $\Pi_{K}(z)$ as the optimal solution of the problem $$\min \tfrac{1}{2}\|y-z\|,\quad \text{s.t. } y\in K.$$ Prove the following statements.
(i) Show that $\Pi_{K}(z)$ satisfies
$$\langle z-\Pi_{K}(z),\, d-\Pi_{K}(z)\rangle\le 0,\quad \forall d\in K.$$
(ii) Define
$$\Theta(z):=\tfrac{1}{2}\|z-\Pi_{K}(z)\|^{2}.$$
Prove that $\Theta(\cdot)$ is continuous differentiable convex function and
$$\nabla\Theta(z)=z-\Pi_{K}(z).$$