练习题集

函数逼近与插值

2011 Individual

Problem 1. Given a weight function $\rho(x)>0$, let the inner-product corresponding to $\rho(x)$ be defined as follows:

\[ (f,g):=\int_a^b \rho(x) f(x) g(x) dx, \]

and let $\|f\| := \sqrt{(f,f)}$.

(a) Define a sequence of polynomials as follows:

\[ \begin{aligned} &p_0(x)=1,\quad p_1(x)=x-a_1,\\ &p_n(x)=(x-a_n)p_{n-1}(x)-b_n p_{n-2}(x),\quad n=2,3,\ldots \end{aligned} \]

where

\[ \begin{aligned} a_n &= \frac{(x p_{n-1}, p_{n-1})}{(p_{n-1}, p_{n-1})}, \quad n=1,2,\ldots,\\ b_n &= \frac{(x p_{n-1}, p_{n-2})}{(p_{n-2}, p_{n-2})}, \quad n=2,3,\ldots. \end{aligned} \]

Show that $\{p_n(x)\}$ is an orthogonal sequence of monic polynomials.
(b) Let $\{q_n(x)\}$ be an orthogonal sequence of monic polynomials corresponding to the inner product defined by $\rho$. (A polynomial is called monic if its leading coefficient is 1.) Show that $\{q_n(x)\}$ is unique and it minimizes $\|q_n\|$ amongst all monic polynomials of degree $n$.
(c) Hence or otherwise, show that if $\rho(x)=\frac{1}{\sqrt{1-x^2}}$ and $[a,b]=[-1,1]$, then the corresponding orthogonal sequence is the Chebyshev polynomials:

\[ T_n(x)=\cos(n \arccos x), \quad n=0,1,2,\ldots \]

and the following recurrent formula holds:

\[ T_{n+1}(x)=2x T_n(x)-T_{n-1}(x), \quad n=1,2,\ldots. \]
(d) Find the best quadratic approximation to $f(x)=x^3$ on $[-1,1]$ using $\rho(x)=\frac{1}{\sqrt{1-x^2}}$.

证明

$(a)$：结合归纳法注意到

\[ \begin{aligned} (p_n,p_{n-1})&=(x p_{n-1}, p_{n-1}) - a_n (p_{n-1}, p_{n-1}) - b_n (p_{n-2}, p_{n-1}) = (x p_{n-1}, p_{n-1}) - a_n (p_{n-1}, p_{n-1}) = 0.\\ (p_n,p_{n-2})&=(x p_{n-1}, p_{n-2}) - a_n (p_{n-1}, p_{n-2}) - b_n (p_{n-2}, p_{n-2}) = (x p_{n-1}, p_{n-2}) - b_n (p_{n-2}, p_{n-2}) = 0.\\ \end{aligned} \]

即得。

$(b)$：唯一性：我们归纳证明对每个 $n$，$q_n$ 唯一。对于 $n=0$，显然 $q_0(x)=1$ 唯一。假设 $q_0,\cdots,q_{k-1}$ 唯一。若存在两个不同的多项式 $q_k(x)$ 和 $\tilde{q}_k(x)$，则它们的差 $r_k(x)=q_k(x)-\tilde{q}_k(x)$ 是一个次数不超过 $k-1$ 的多项式，并且满足 $(r_k, q_i)=0,i=0,\cdots,k-1$。由归纳假设，$q_i$ 是唯一的，因此 $r_k(x)$ 必须是零多项式，从而 $q_k(x)=\tilde{q}_k(x)$。

最小性：设 $p(x)$ 是任意一个次数为 $n$ 的首一多项式，则 $p(x)-q_n(x)$ 是一个次数不超过 $n-1$ 的多项式，因此 $(p-q_n, q_n)=0$。于是

\[ \|p\|^2 = \|q_n\|^2 + \|p-q_n\|^2 \geq \|q_n\|^2, \]

$(c)$：结合 $(a)$ 的递推和 $(b)$ 的唯一性可知，所求正交多项式序列满足要求。

$(d)$：设最佳二次近似为 $p(x)=c_0 T_0(x)+c_1 T_1(x)+c_2 T_2(x)$，则由正交性条件

\[ \begin{aligned} c_0 &= \frac{(f,T_0)}{(T_0,T_0)} = \frac{\int_{-1}^1 \frac{x^3}{\sqrt{1-x^2}} dx}{\int_{-1}^1 \frac{1}{\sqrt{1-x^2}} dx} = 0,\\ c_1 &= \frac{(f,T_1)}{(T_1,T_1)} = \frac{\int_{-1}^1 \frac{x^4}{\sqrt{1-x^2}} dx}{\int_{-1}^1 \frac{x^2}{\sqrt{1-x^2}} dx} = \frac{3}{4}\\ c_2 &= \frac{(f,T_2)}{(T_2,T_2)} = \frac{\int_{-1}^1 \frac{x^3(2x^2-1)}{\sqrt{1-x^2}} dx}{\int_{-1}^1 \frac{(2x^2-1)^2}{\sqrt{1-x^2}} dx} = 0 \end{aligned} \]

因此最佳二次近似为

\[ p(x)=\frac{3}{4} T_1(x)=\frac{3}{4} x. \]

2011 Individual

Problem 2. If two polynomials $p(x)$ and $q(x)$, both of fifth degree, satisfy

\[ p(i)=q(i)=\frac{1}{i}, \quad i=2,3,4,5,6, \]

and $p(1)=1$, $q(1)=2$. Find $p(0)-q(0)$.

解

注意到 $p(x)-q(x)$ 有五个不同的根 $2,3,4,5,6$，因此

\[ p(x)-q(x)=k(x-2)(x-3)(x-4)(x-5)(x-6) \]

带入 $x=1$ 可得 $k=\frac{1-2}{(1-2)(1-3)(1-4)(1-5)(1-6)}=\frac{1}{5!}$，因此 $p(0)-q(0)=k(0-2)(0-3)(0-4)(0-5)(0-6)=6$。

2012 Individual

Problem 2. Here is the definition of a moving least square approximation of a function $f(x)$ near a point $\overline{x}$ given $K$ points $x_k$ around $\overline{x}$ in $\mathbb{R}, k=1,\ldots,K$:

\[ \min_{P_{\overline{x}} \in \Pi_m} \sum_{k=1}^{K} |P_{\overline{x}}(x_k)-f_k|^2, \]

where $f_k = f(x_k)$, $\Pi_m$ is the space of polynomials of degree less or equal to $m$, i.e.

\[ P_{\overline{x}}(x) = b_{\overline{x}}(x)^T c(\overline{x}), \]

$c(\overline{x}) = [c_0, c_1, \ldots, c_m]^T$ is the coefficient vector to be determined by the minimization, $b_{\overline{x}}(x)$ is the polynomial basis vector, $b_{\overline{x}}(x) = [1, x-\overline{x}, (x-\overline{x})^2, \ldots, (x-\overline{x})^m]^T$. Assume that there are $K > m$ different points $x_k$ and $f(x)$ is smooth.

(a) Prove that there is a unique solution $P_{\overline{x}}(x)$ to the minimization problem.
(b) Denote $h = \max_k |x_k - \overline{x}|$, prove

\[ \left| c_i - \frac{1}{i!} f^{(i)}(\overline{x}) \right| = C(f,i) h^{m+1-i}, \quad i=0,1,\ldots,m, \]

where $f^{(i)}(\cdot)$ is the $i$-th derivative of $f$ and $C(f,i)$ denotes some constant depending on $f$ and $i$.
(c) If $S = \{x_k \mid k=1,2,\ldots,K\}$ are symmetrically distributed around $\overline{x}$, that is, if $x_k \in S$ then $2\overline{x}-x_k \in S$, prove that

\[ \left| c_i - \frac{1}{i!} f^{(i)}(\overline{x}) \right| = C(f,i) h^{m+2-i}, \quad i=0,1,\ldots,m, \]

for $i$ (in $\{0,1,\ldots,m\}$) with the same parity as $m$.

证明

$(a)$：即找 $c_i$ 使得

\[ \min_{c_i} \sum_{k=1}^{K} \left|\sum_{i=0}^m c_i b_i(x_k) - f_k\right|^2. \]

对 $c_j$ 求导并令其为零，得到线性方程组

\[ \mathbf{b}^T \mathbf{b} \mathbf{c} = \sum_{k=1}^{K} f_k \mathbf{b}(x_k), \]

容易得到 $\mathbf{b}^T \mathbf{b}$ 是正定矩阵，因此该方程组有唯一解 $\mathbf{c}=(\mathbf{b}^T \mathbf{b})^{-1} \sum_{k=1}^{K} f_k \mathbf{b}(x_k)$。

$(b)$：设 $f(x)$ 在 $\overline{x}$ 处的 Taylor 展开为

\[ f(x) = \sum_{i=0}^{m} \frac{f^{(i)}(\overline{x})}{i!}b_i(x) + R_{m+1}(x), \]

故

\[ f_k = \sum_{i=0}^{m} \frac{f^{(i)}(\bar{x})}{i!} b_i(x_k) + R_{m+1}(x_k). \]

\[ \begin{aligned} \mathbf{c} &= (\mathbf{b}^T \mathbf{b})^{-1} \sum_{k=1}^{K} \left( \sum_{j=0}^{m} \frac{f^{(j)}(\bar{x})}{j!} b_j(x_k) + R_{m+1}(x_k) \right) \mathbf{b}(x_k) \\ &= \sum_{j=0}^{m} \frac{f^{(j)}(\bar{x})}{j!} \mathbf{e}_i+ (\mathbf{b}^T \mathbf{b})^{-1}\sum_{k=1}^{K} R_{m+1}(x_k) \mathbf{b}(x_k) \\ \end{aligned} \]

其中 $\mathbf{e}_i=(\mathbf{b}^T \mathbf{b})^{-1} \sum_{k=1}^{K} b_j(x_k) \mathbf{b}(x_k)$ 是单位向量，因此

\[ \begin{aligned} \left| c_i - \frac{1}{i!} f^{(i)}(\overline{x}) \right| &\leq \sum_k\sum_j |(\mathbf{b}^T \mathbf{b})^{-1}_{ij}| |R_{m+1}(x_k)| |b_j(x_k)|\\ &=\sum_k\sum_j O(h^{-i-j})\cdot O(h^{m+1})\cdot O(h^j)=C(f,i) h^{m+1-i}. \end{aligned} \]

$(c)$：设 $f(x)$ 在 $\overline{x}$ 处的 Taylor 展开为

\[ f(x) = \sum_{i=0}^{m} \frac{f^{(i)}(\overline{x})}{i!}b_i(x) + \frac{f^{(m+1)}(\overline{x})}{i!}+ R_{m+2}(x), \]

同理可得

\[ \begin{aligned} \left| c_i - \frac{1}{i!} f^{(i)}(\overline{x}) \right| &\leq \sum_k\sum_j |(\mathbf{b}^T \mathbf{b})^{-1}_{ij}| |R_{m+2}(x_k)| |b_j(x_k)|\\ \end{aligned} \]

2014 Team

Problem 4. Let

\[ V_h = \{ v : v|_{I_j} \in P^k(I_j), \quad 1 \leq j \leq N \}, \]

where

\[ I_j = (x_{j-1}, x_j), \quad 1 \leq j \leq N \]

with

\[ x_j = jh, \quad h = \frac{1}{N}. \]

Here $P^k(I_j)$ denotes the set of polynomials of degree at most $k$ in the interval $I_j$. Recall the $L^2$ projection of a function $u(x)$ into the space $V_h$ is defined by the unique function $u_h \in V_h$ which satisfies

\[ \|u - u_h\| \leq \|u - v\|, \quad \forall v \in V_h, \]

where the norm is the usual $L^2$ norm. We assume $u(x)$ has at least $k+2$ continuous derivatives.

(a) Prove the error estimate

\[ \|u - u_h\| \leq C h^{k+1}. \]

Explain how the constant $C$ depends on the derivatives of $u(x)$.
(b) If another function $\varphi(x)$ also has at least $k+2$ continuous derivatives, prove

\[ \left| \int_0^1 (u(x) - u_h(x)) \varphi(x) dx \right| \leq C h^{2k+2}. \]

Explain how the constant $C$ depends on the derivatives of $u(x)$ and $\varphi(x)$.

证明

$(a)$：对每个子区间 $I_j$，我们将 $u(x)$ 在 $I_j$ 上用 $k$ 次泰勒多项式 $p_j(x)$ 近似，则由泰勒公式可知

\[ u - p_j= \frac{u^{(k+1)}(\xi_j)}{(k+1)!} (x - x_{j-1})^{k+1}, \quad x \in I_j, \]

故

\[ \|u-p_j\|_{L^2(I_j)} \leq \frac{h^{k+1}}{(k+1)!} \max_{x \in I_j} |u^{(k+1)}(x)|. \]

由于 $u_h$ 是 $u$ 在 $V_h$ 上的最佳 $L^2$ 近似多项式，因此

\[ \|u - u_h\|\leq \sum_{j=1}^N \|u - p_j\|_{L^2(I_j)} \leq N \frac{h^{k+1}}{(k+1)!} \max_{x \in [0,1]} |u^{(k+1)}(x)|. \]

$(b)$：设 $\pi_h \varphi$ 是 $\varphi$ 在 $V_h$ 上的最佳 $L^2$ 近似多项式，则

\[ \begin{aligned} \left| \int_0^1 (u(x) - u_h(x)) \varphi(x) dx \right| &= \left| \int_0^1 (u(x) - u_h(x)) (\varphi(x) - \pi_h \varphi(x)) dx \right|\\ &\leq \|u - u_h\| \cdot \|\varphi - \pi_h \varphi\|\\ &\leq C h^{k+1} \max_{x \in [0,1]} |u^{(k+1)}(x)| \cdot C h^{k+1} \max_{x \in [0,1]} |\varphi^{(k+1)}(x)| \end{aligned} \]

2014 Team

For the interval $[0, \pi]$, we divide it into $N + 1$ equally spaced subintervals by using the nodal points:

\[0 = x_0 < x_1 < \cdots < x_{N+1} = \pi,\]

with

\[ \begin{align*} &x_i = i \, h, \quad h = \pi / (N + 1). \end{align*} \]

For any continuous function $w$ on $[0, \pi]$, we define $\Pi_h w$ to be the piecewise linear interpolation of $w$, namely $\Pi_h w$ is linear on each subinterval $(x_i, x_{i+1})$ for $i = 0, 1, \cdots, N$, and it takes the same values as $w$ at all nodal points $x_i, i = 0, 1, \cdots, N + 1$. For any function $w$, we define

\[ \|w\| = \left( \int_0^\pi w^2(x) dx \right)^{1/2}. \]

Prove the following estimates for any function $u \in C^2[0, \pi]$:

\[ \|u - \Pi_h u\| \leq \frac{1}{\pi^2} h^2 \|u''\|, \quad \|u' - (\Pi_h u)'\| \leq \frac{1}{\pi} h \|u''\|. \]

证明

设 $f=u-\Pi_h u$，由柯西不等式我们对 $x\in [x_i,x_{i+1}]$ 有

\[ |f(x)|\le \int_{x_i}^x |f'(t)|dt \le \sqrt{x - x_i} \left( \int_{x_i}^{x_{i+1}} |f'(t)|^2 dt \right)^{1/2} \le \sqrt{h} \|f'\|_{L^2(x_i,x_{i+1})} \]

故

\[ \|f\|_{L^2(x_i,x_{i+1})}^2 \le h^2 \|f'\|_{L^2(x_i,x_{i+1})}^2 \]

又

\[ 0=\int_{x_i}^{x_{i+1}} (ff')' dx =\int_{x_i}^{x_{i+1}} (f')^2 dx + \int_{x_i}^{x_{i+1}} f f'' dx, \]

因此

\[ \|f'\|_{L^2(x_i,x_{i+1})}^2 \le \int_{x_i}^{x_{i+1}} |f f''| dx \le \|f\|_{L^2(x_i,x_{i+1})} \|f''\|_{L^2(x_i,x_{i+1})} \]

综上我们有

\[ \|f\|_{L^2(x_i,x_{i+1})}^2 \le h^4 \|f''\|_{L^2(x_i,x_{i+1})}^2 \]

\[ \|f'\|_{L^2(x_i,x_{i+1})}^2 \le h^2 \|f''\|_{L^2(x_i,x_{i+1})}^2 \]

求和得

\[ \|f\|^2 = \sum_{i=0}^{N} \|f\|_{L^2(x_i,x_{i+1})}^2 \le h^4 \|f''\|^2 \]

\[ \|f'\|^2 = \sum_{i=0}^{N} \|f'\|_{L^2(x_i,x_{i+1})}^2 \le h^2 \|f''\|^2 \]

2012 Team

Problem 1. If the function $u(x)$ is in $C^{k+1}$ (has continuous $(k+1)$-th derivative) on the interval $[0,2]$, and a sequence of polynomials $p_n(x)$ ($n=1,2,3,\ldots$) of degree at most $k$ satisfies

\[ |u(x) - p_n(x)| \leq \frac{C}{n^{k+1}}, \quad \forall 0 \leq x \leq \frac{1}{n}, \]

where the constant $C$ is independent of $n$, prove

\[ |u(x) - p_n(x)| \leq \frac{\tilde{C}}{n^{k+1}}, \quad \forall \frac{1}{n} \leq x \leq \frac{2}{n}, \]

with another constant $\tilde{C}$ which is also independent of $n$.

证明

取 $u(x)$ 在区间 $[0,\frac{1}{n}]$ 上的 $k$ 次插值多项式 $q_n(x)$，记 $x_j^n=\frac{j}{nk}，则

\[ q_n(x) = \sum_{i=0}^{k} u(x_i^n) l_i^n(x), l_j^n(x) = \prod_{\substack{0 \leq i \leq k \\ i \neq j}} \frac{x - x_m^n}{x_j^n - x_m^n}. \]

则对 $\frac{1}{n}\le x\le \frac{2}{n}$，有

\[ |u(x)-q_n(x)|=\left| \frac{u^{(k+1)}(\xi_x)}{(k+1)!} (x - x_0^n)(x - x_1^n) \cdots (x - x_k^n) \right| \leq \frac{C_1}{(k+1)!} \left(\frac{2}{n}\right)^{k+1}\le \frac{C_2}{n^{k+1}}. \]

而对 $\frac{1}{n}\le x\le \frac{2}{n}$，有

\[ |q_n(x)-p_n(x)| = \left| \sum_{i=0}^{k} (u(x_i^n) - p_n(x_i^n)) l_i^n(x) \right| \leq \frac{C}{n^{k+1}} \sum_{i=0}^{k} |l_i^n(x)| \leq \frac{C_3}{n^{k+1}}. \]

其中

\[ C_3 = C \sum_{j=0}^{k}\prod_{0\le i\le k,i\ne j}\frac{2k-i}{|j-i|} \]

最后我们有

\[ |u(x)-p_n(x)| \le |u(x)-q_n(x)| + |q_n(x)-p_n(x)| \le \frac{C_2+C_3}{n^{k+1}}. \]

2017 Individual

Problem 3. Consider a piecewise smooth function

\[ f(x) = \begin{cases} f_1(x), & x \leq 0, \\ f_2(x), & x > 0 \end{cases} \]

where $f_1(x)$ is a $C^\infty$ function on $(-\infty,0]$ and $f_2(x)$ is a $C^\infty$ function on $[0,\infty)$, but $f_1(0) \neq f_2(0)$. Suppose $p(x)$ is a $k$-th degree polynomial ($k \geq 1$) interpolating $f(x)$ at $k+1$ equally-spaced grid points $x_j, j=0,1,2,\ldots,k$ with $x_i < 0 < x_{i+1}$ for some $i$ between $0$ and $k-1$. Prove that, when the grid size $h = x_{j+1} - x_j$ is small enough, $p'(x) \neq 0$ for $x_i \leq x \leq x_{i+1}$, that is, $p(x)$ is monotone in the interval $[x_i, x_{i+1}]$. (Hint: first prove the case when $f_1(x) = c_1, f_2(x) = c_2$ and $c_1 \neq c_2$ are two constants.)

2018 Individual

Problem (Hermite Polynomials). Define the Hermite polynomials as

\[ H_n(x) = (-1)^n \exp\left( \frac{x^2}{2} \right) \frac{d^n}{dx^n} \left[ \exp\left( -\frac{x^2}{2} \right) \right], \quad x \in (-\infty, +\infty), \quad n=0,1,2,\ldots \]

(a) Prove the weighted orthogonality of the Hermite polynomials:

\[ \int_{-\infty}^{+\infty} \rho(x) H_n(x) H_m(x) dx = n! \sqrt{2\pi} \delta_{n,m}, \]

where $\rho(x) = \exp\left( -\frac{x^2}{2} \right)$.
(b) Prove the three-term recurrence formula:

\[ H_n(x) = x H_{n-1}(x) - (n-1) H_{n-2}(x), \quad n \geq 2, \]

and then show that for all $n \geq 1$, $H_n(x)$ and $H_{n-1}(x)$ share no common roots.
(c) Use the recurrence formula and induction to prove the differential relation:

\[ \frac{d}{dx} H_n(x) = n H_{n-1}(x), \quad n \geq 1, \]

and then prove that $H_n$ is an eigenfunction of the following eigenvalue problem

\[ x u'(x) - u''(x) = \lambda u. \]

You need to find the eigenvalue $\lambda_n$ corresponding to $H_n(x)$.

2012 Team

Problem 2. Let $S(x)$ be a cubic spline with knots $\{t_i\}_{i=0}^n$. If it is determined that $S(x)$ is linear over $[t_1, t_2]$ and $[t_3, t_4]$, prove that $S(x)$ is also linear over $[t_2, t_3]$.

数值代数

2015 Drush Team

Problem 1. Find the generalized eigenvalue $\lambda$ and the eigenvector $(x_1, x_2, \cdots, x_n)^T$, such that

\[ \begin{pmatrix} 2 & -1 & & & \\ -1 & 2 & -1 & & \\ & -1 & 2 & \ddots & \\ & & \ddots & \ddots & -1 \\ & & & -1 & 2 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_{n-1} \\ x_n \end{pmatrix} = \lambda \begin{pmatrix} 4 & 1 & & & \\ 1 & 4 & 1 & & \\ & 1 & 4 & \ddots & \\ & & \ddots & \ddots & 1 \\ & & & 1 & 4 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_{n-1} \\ x_n \end{pmatrix}. \]

2015 Drush Team

Problem 2. Find the eigenvalues and eigenvectors of the following $N \times N$ tridiagonal matrix:

\[ A = \begin{pmatrix} b & c & & & \\ a & b & c & & \\ & a & b & c & \\ & & \ddots & \ddots & \ddots \\ & & & a & b & c \\ & & & & a & b \end{pmatrix}, \]

where $a, b, c$ are constants, and $ac > 0$.

2015 Drush Team

Problem 3. Suppose an $n \times n$ matrix $A$ is given by

\[ A = \begin{pmatrix} 1 & r & & & \\ & 1 & r & & \\ & & \ddots & \ddots & \\ & & & 1 & r \\ r & & & & 1 \end{pmatrix}, \quad n \times n. \]

For the linear system $Ax = b$, prove that

\[ \|x\| \leq C \|b\|, \]

where the constant $C$ is independent of the dimension $n$.

2015 Drush Team

Problem 4. (Circulant Matrices) Every circulant matrix $C$ has eigenvectors

\[ y^{(m)} = \frac{1}{\sqrt{n}} \left(1, e^{-2\pi i m/n}, \cdots, e^{-2\pi i m(n-1)/n}\right), \quad m = 0, 1, \cdots, n-1, \]

and corresponding eigenvalues

\[ \psi_m = \sum_{k=0}^{n-1} c_k e^{-2\pi i m k / n}. \]

It can be expressed in the form $C = U \Psi U^*$, where $U$ has the eigenvectors as columns in order and $\Psi = \text{diag}(\psi_k)$. In particular all circulant matrices share the same eigenvectors, the same matrix $U$ works for all circulant matrices, and any matrix of the form $C = U \Psi U^*$ is circulant.

Prove the above theorem.

2015 Drush Team

Problem 5. (Companion Matrix) Let

\[ C = \begin{pmatrix} 0 & 0 & \cdots & 0 & -c_0 \\ 1 & 0 & \cdots & 0 & -c_1 \\ 0 & 1 & \cdots & 0 & -c_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & 1 & -c_{n-1} \end{pmatrix} \]

be a companion matrix with distinct eigenvalues $\lambda_1, \ldots, \lambda_n$. Show that

\[ V C V^{-1} = \text{diag}(\lambda_1, \ldots, \lambda_n), \]

where

\[ V = \begin{pmatrix} 1 & \lambda_1 & \cdots & \lambda_1^{n-1} \\ 1 & \lambda_2 & \cdots & \lambda_2^{n-1} \\ \vdots & \vdots & \ddots & \vdots \\ 1 & \lambda_n & \cdots & \lambda_n^{n-1} \end{pmatrix}. \]

2013 Term

Problem 6. Let $(F_n)_n$ be the Fibonacci sequence, with $F_0 = 0$, $F_1 = 1$, and $F_{n+2} = F_{n+1} + F_n$ for $n \geq 0$.

(a) Establish a relation between $\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^n$ and $F_n$.
(b) Use it to design an efficient algorithm that for a given $n$ computes the $n$-th Fibonacci number $F_n$. In particular, it must be more efficient than computing $F_n$ in $n$ consecutive steps.
(c) Give an estimate on the number of steps of your algorithm.

Hint: Note that if $m$ is even then

\[ \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^m = \left( \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{m/2} \right)^2, \]

and if $m$ is odd then

\[ \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^m = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{m-1} \cdot \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}, \]

and $m-1$ is even.

2018 Term

Problem 7. Take $\sigma_i(A)$ to be the $i$-th singular value of the square matrix $A \in \mathbb{R}^{n \times n}$. Define the nuclear norm of $A$ to be

\[ \|A\|_* \equiv \sum_{i=1}^n \sigma_i(A). \]

(a) Show that $\|A\|_* = \operatorname{tr}(\sqrt{A^T A})$.
(b) Show that $\|A\|_* = \max_{X^T X = I} \operatorname{tr}(AX)$.
(c) Show that $\|A + B\|_* \leq \|A\|_* + \|B\|_*$.
(d) Explain informally why minimizing $\|A - A_0\|_*^2 + \|A\|_*$ over $A$ for a fixed $A_0 \in \mathbb{R}^{n \times n}$ might yield a low-rank approximation of $A_0$.

2018 Term

Problem 8. Suppose $A \in \mathbb{R}^{m \times n}$ with $m \geq n$ and $r = \text{rank}(A) < n$, and assume $A$ has the following SVD:

\[ A = [U_1, U_2] \begin{bmatrix} \Sigma_1 & 0 \\ 0 & 0 \end{bmatrix} [V_1, V_2]^T = U_1 \Sigma_1 V_1^T, \]

where $\Sigma_1$ is $r \times r$ nonsingular and $U_1, V_1$ have $r$ columns. Let $\sigma = \sigma_{\min}(\Sigma_1)$, the smallest nonzero singular value of $A$. Consider the least square problem, for some $b \in \mathbb{R}^m$,

\[ \min_x \|Ax - b\|_2. \]

(a) Show that all solutions $x$ can be written as

\[ x = V_1 \Sigma_1^{-1} U_1^T b + V_2 z_2, \]

with $z_2$ an arbitrary vector.
(b) Show that the solution $x$ has minimal norm $\|x\|_2$ precisely when $z_2 = 0$, and in which case,

\[ \|x\|_2 \leq \frac{\|b\|_2}{\sigma}. \]

2018 Term

Problem 9. Let $C$ and $D$ in $\mathbb{C}^{n \times n}$ be Hermitian matrices. Denote their eigenvalues by

\[ \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n \quad \text{and} \quad \mu_1 \geq \mu_2 \geq \cdots \geq \mu_n, \]

respectively. Then it is known that

\[ \sum_{i=1}^n (\lambda_i - \mu_i)^2 \leq \|C - D\|_F^2. \]

(a) Let $A$ and $B$ be in $\mathbb{C}^{n \times n}$. Denote their singular values by

\[ \sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_n \quad \text{and} \quad \tau_1 \geq \tau_2 \geq \cdots \geq \tau_n, \]

respectively. Prove that the following inequality holds:

\[ \sum_{i=1}^n (\sigma_i - \tau_i)^2 \leq \|A - B\|_F^2. \]
(b) Suppose $A = U \Sigma V^T$, where $U = (u_1, u_2, \ldots, u_n)$, $V = (v_1, v_2, \ldots, v_n)$ are orthogonal matrices, $\Sigma = \text{diag}(\sigma_1, \sigma_2, \ldots, \sigma_n)$ with $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_n \geq 0$. Suppose $\text{rank}(A) > k$ and denote by

\[ U_k = (u_1, u_2, \ldots, u_k), \quad V_k = (v_1, v_2, \ldots, v_k), \quad \Sigma_k = \text{diag}(\sigma_1, \sigma_2, \ldots, \sigma_k), \]

and

\[ A_k = U_k \Sigma_k V_k^T = \sum_{i=1}^k \sigma_i u_i v_i^T. \]

Prove that

\[ \min_{\text{rank}(B) = k} \|A - B\|_F^2 = \|A - A_k\|_F^2 = \sum_{i=k+1}^n \sigma_i^2. \]
(c) Let the vectors $x_i \in \mathbb{R}^n$, $i = 1, 2, \ldots, n$, be in the space $\mathcal{W}$ with dimension $d$, where $d \ll n$. Let the orthonormal basis of $\mathcal{W}$ be $W \in \mathbb{R}^{n \times d}$. Then we can represent $x_i$ by

\[ x_i = c + W r_i + e_i, \quad i = 1, 2, \ldots, n, \]

where $c \in \mathbb{R}^n$ is a constant vector, $r_i \in \mathbb{R}^d$ are coordinates, and $e_i$ is the error. Denote $R = (r_1, r_2, \ldots, r_n)$ and $E = (e_1, e_2, \ldots, e_n)$. Find $W, R$ and $c$ such that the error $\|E\|_F$ is minimized.

Hint: Write $X = [x_1, x_2, \ldots, x_n] = c \mathbf{1}^T + W R + E$, where $\mathbf{1}$ is the vector of all ones.

2018 Term

Problem 10. Let $A \in \mathbb{R}^{n \times m}$ with rank $r < \min(m, n)$. Let $A = U \Sigma V^T$ be the SVD of $A$, with singular values $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > 0$.

(a) Show that, for every $\epsilon > 0$, there is a full rank matrix $A_\epsilon \in \mathbb{R}^{n \times m}$ such that

\[ \|A - A_\epsilon\|_2 = \epsilon. \]
(b) Let $A_k = U \Sigma_k V^T$ where $\Sigma_k = \text{diag}(\sigma_1, \ldots, \sigma_k, 0, \ldots, 0)$ and $1 \leq k \leq r-1$. Show that $\text{rank}(A_k) = k$ and

\[ \sigma_{k+1} = \|A - A_k\|_2 = \min \{ \|A - B\|_2 \mid \text{rank}(B) \leq k \}. \]
(c) Assume that $r = \min(m, n)$. Let $B \in \mathbb{R}^{n \times m}$ and assume that $\|A - B\|_2 < \sigma_r$. Show that $\text{rank}(B) = r$.

Unknown Year

Problem 11. Let $b \in \mathbb{R}^n$. Suppose $A \in M_{n \times n}(\mathbb{R})$ and $B \in M_{n \times n}(\mathbb{R})$ are two $n \times n$ matrices. Let $A$ be non-singular.

(a) Consider the iterative scheme: $A x^{k+1} = b - B x^k$. State and prove the necessary and sufficient condition for the iterative scheme to converge.
(b) Suppose the spectral radius of $A^{-1}B$ satisfies $\rho(A^{-1}B) \neq 0$. Prove that the iterative scheme converges in $n$ iterations.
(c) Consider the following iterative scheme:

\[ x^{(k+1)} = \omega_1 x^{(k)} + \omega_2 (c_1 - M x^{(k)}) + \omega_3 (c_2 - M x^{(k)}) + \ldots + \omega_k (c_{k-1} - M x^{(k)}), \]

where $M$ is symmetric and positive definite, $\omega_1 > 1$, $\omega_2, \ldots, \omega_k > 0$ and $c_1, \ldots, c_{k-1} \in \mathbb{R}^n$. Deduce from (a) that the iterative scheme converges if and only if all eigenvalues of $M$ (denote it as $\lambda(M)$) satisfy:

\[ \frac{\omega_1 - 1}{\sum_{i=2}^k \omega_i} < \lambda(M) < \frac{\omega_1 + 1}{\sum_{i=2}^k \omega_i}. \]
(d) Let $A$ be non-singular. Now, consider the following system of iterative scheme (*):

\[ \begin{aligned} A x_1^{(k+1)} &= b_1 - B x_2^{(k)}, \\ A x_2^{(k+1)} &= b_2 - B x_1^{(k)}. \end{aligned} \]

Find and prove the necessary and sufficient condition for the iterative scheme (*) to converge.

For the iterative scheme (**):

\[ \begin{aligned} A x_1^{(k+1)} &= b_1 - B x_2^{(k)}, \\ A x_2^{(k+1)} &= b_2 - B x_1^{(k+1)}. \end{aligned} \]

Find and prove the necessary and sufficient condition for the iterative scheme () to converge. Compare the rate of convergence of the iterative schemes (*) and ().

Unknown Year

Problem 12. (Richardson Iteration) Let $A$ be an $n \times n$ matrix with real and positive eigenvalues and $b$ be a given vector. Consider the solution of $Ax = b$ by the following Richardson's iteration

\[ x^{(k+1)} = (I - \omega A)x^{(k)} + \omega b, \]

where $\omega$ is a damping coefficient. Let $\lambda_1$ and $\lambda_n$ be the smallest and the largest eigenvalues of $A$. Let $G_\omega = I - \omega A$.

(a) Prove that the Richardson's iteration converges if and only if

\[ 0 < \omega < \frac{2}{\lambda_n}. \]
(b) Prove that the optimal choice of $\omega$ is given by

\[ \omega_{\text{opt}} = \frac{2}{\lambda_1 + \lambda_n}. \]

Prove also that

\[ \rho(G_\omega) = \begin{cases} 1 - \omega \lambda_1, & \omega \leq \omega_{\text{opt}}, \\ \frac{\lambda_n - \lambda_1}{\lambda_n + \lambda_1}, & \omega = \omega_{\text{opt}}, \\ \omega \lambda_n - 1, & \omega \geq \omega_{\text{opt}}. \end{cases} \]

where $\rho(G_\omega)$ is the spectral radius of $G_\omega$.
(c) Prove that, if $A$ is symmetric and positive definite, then

\[ \rho(G_{\omega_{\text{opt}}}) = \frac{\kappa_2(A) - 1}{\kappa_2(A) + 1}, \]

where $\kappa_2(A) = \lambda_n / \lambda_1$.

Unknown Year

Problem 13. (Power Method) Suppose $A$ is an $m \times m$ matrix with a complete set of orthonormal eigenvectors $q_1, \ldots, q_m$ and corresponding eigenvalues $\lambda_1, \ldots, \lambda_m$. Assume that $|\lambda_1| > |\lambda_2| > |\lambda_3|$ and $\lambda_j \geq \lambda_{j+1}$ for $j = 3, \ldots, m$. Consider the power method $\psi^{(k)} = A \psi^{(k-1)} / \lambda_1$, with $\psi^{(0)} = \alpha_1 q_1 + \cdots + \alpha_m q_m$ where $\alpha_1$ and $\alpha_2$ are both nonzero. Show that the sequence $\{\psi^{(k)}\}_{k=0}^{\infty}$ converges linearly to $\alpha_1 q_1$ with asymptotic constant $C = |\lambda_2 / \lambda_1|$.

Unknown Year

Problem 14. (Lanczos Iteration) Let $A \in \mathbb{R}^{n \times n}$ be symmetric and let $\|q_1\|_2 = 1$. Consider the following Lanczos iteration:

\[ \begin{aligned} &r_0 = q_1, \quad \beta_0 = 1, \quad q_0 = 0, \quad k := 0 \\ &\text{while } \beta_k \neq 0 \\ &\quad q_{k+1} := r_k / \beta_k \\ &\quad k := k + 1 \\ &\quad \alpha_k := q_k^T A q_k \\ &\quad r_k := (A - \alpha_k I) q_k - \beta_{k-1} q_{k-1} \\ &\quad \beta_k := \|r_k\|_2 \\ &\text{end} \end{aligned} \]

Let $\mathcal{K}_n = \text{span}\{q_1, A q_1, \cdots, A^{n-1} q_1\}$.

(a) Show that

\[ A Q_k = Q_k T_k + r_k e_k^T, \]

where $e_k$ is the $k$-th unit vector, $Q_k = [q_1 \cdots q_k]$ and

\[ T_k = \begin{bmatrix} \alpha_1 & \beta_1 & & & \\ \beta_1 & \alpha_2 & \beta_2 & & \\ & \beta_2 & \alpha_3 & \ddots & \\ & & \ddots & \ddots & \beta_{k-1} \\ & & & \beta_{k-1} & \alpha_k \end{bmatrix}. \]
(b) Assume that the iteration does not terminate. Show that $Q_k$ has orthonormal columns, and that they span $\mathcal{K}_k$.
(c) Show that the Lanczos iteration will stop when $k = m$, where $m = \text{rank}(\mathcal{K}_n)$.
(d) What is the purpose of this algorithm? Briefly justify your answer.

Unknown Year

Problem 15. (Arnoldi Process) Given a vector $b \in \mathbb{R}^m$ and $A \in \mathbb{R}^{m \times m}$, the Arnoldi process is a systematic way of constructing an orthonormal basis for the successive Krylov subspaces

\[ \mathcal{K}_n = \langle b, Ab, \ldots, A^{n-1} b \rangle, \quad n = 1, 2, \ldots \]

It gives

\[ A Q_n = Q_{n+1} \tilde{H}_n, \]

where $Q_n \in \mathbb{R}^{m \times n}$, $Q_{n+1} \in \mathbb{R}^{m \times (n+1)}$ have orthonormal columns and $\tilde{H}_n \in \mathbb{R}^{(n+1) \times n}$ is upper-Hessenberg. Let $H_n \in \mathbb{R}^{n \times n}$ be obtained by deleting the last row of $\tilde{H}_n$.

(a) Write out the Arnoldi algorithm.
(b) Assume that at step $n$, the $(n+1,n)$-th entry of $\tilde{H}_n$ is zero.
- i. Show that $\mathcal{K}_n$ is an invariant subspace of $A$ and that $\mathcal{K}_n = \mathcal{K}_{n+1} = \mathcal{K}_{n+2} = \ldots$
- ii. Show that each eigenvalue of $H_n$ is an eigenvalue of $A$ for $n > 1$.
(c) Let $\mathcal{P}_n$ be the set of monic polynomials of degree $n$. Show that the minimizer of

\[ \min_{p_n \in \mathcal{P}_n} \|p_n(A) b\|_2 \]

is given by the characteristic polynomial of $H_n$.

Unknown Year

Problem 16. (Steepest Descent) Let $A$ be a positive definite matrix. Consider the quadratic function $g(x) = \frac{1}{2} x^T A x - b^T x$. Suppose the eigenvalues of $A$ are given by $0 < \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$, and $\kappa = \frac{\lambda_n}{\lambda_1}$. Let the sequence $\{x_k\}$ be generated by the steepest descent method:

\[ x_{k+1} = x_k - \alpha_k \nabla g(x_k), \quad k = 0, 1, 2, \ldots, \]

where $\alpha_k$ is selected such that

\[ g(x_k - \alpha_k \nabla g(x_k)) = \min_{\alpha \geq 0} g(x_k - \alpha \nabla g(x_k)). \]

Prove that

\[ g(x_{k+1}) \leq \left( \frac{\kappa - 1}{\kappa + 1} \right)^2 g(x_k) \leq \left( \frac{\kappa - 1}{\kappa + 1} \right)^{2(k+1)} g(x_0). \]

Unknown Year

Problem 17. (Conjugate Gradient Method) Let $A$ be an $N \times N$ symmetric positive definite matrix. The conjugate gradient method can be described as follows:

\[ \begin{aligned} &\mathbf{r}_0 = \mathbf{b} - A \mathbf{x}_0, \quad \mathbf{p}_0 = \mathbf{r}_0, \quad \mathbf{x}_0 = 0 \\ &\text{For } n = 0, 1, \ldots \\ &\quad \alpha_n = \|\mathbf{r}_n\|_2^2 / (\mathbf{p}_n^T A \mathbf{p}_n) \\ &\quad \mathbf{x}_{n+1} = \mathbf{x}_n + \alpha_n \mathbf{p}_n \\ &\quad \mathbf{r}_{n+1} = \mathbf{r}_n - \alpha_n A \mathbf{p}_n \\ &\quad \beta_n = -\mathbf{r}_{n+1}^T A \mathbf{p}_n / \mathbf{p}_n^T A \mathbf{p}_n \\ &\quad \mathbf{p}_{n+1} = \mathbf{r}_{n+1} + \beta_n \mathbf{p}_n \\ &\text{End For} \end{aligned} \]

Show that:

(a) $\alpha_n$ minimizes $f(\mathbf{x}_n + \alpha \mathbf{p}_n)$ for all $\alpha \in \mathbb{R}$, where $f(\mathbf{x}) \equiv \frac{1}{2} \mathbf{x}^T A \mathbf{x} - \mathbf{b}^T \mathbf{x}$.
(b) $\mathbf{p}_i^T \mathbf{r}_n = 0$ for $i < n$ and $\mathbf{p}_i^T A \mathbf{p}_j = 0$ if $i \neq j$.
(c) $\text{Span}\{\mathbf{p}_0, \mathbf{p}_1, \ldots, \mathbf{p}_{n-1}\} = \text{Span}\{\mathbf{r}_0, \mathbf{r}_1, \ldots, \mathbf{r}_{n-1}\} \equiv \mathcal{K}_n$.
(d) $\mathbf{r}_n$ is orthogonal to $\mathcal{K}_n$.

Unknown Year

Problem 18. (GMRES Method) Consider the linear system $Ax = b$. The GMRES method is a projection method which obtains a solution in the $m$-th Krylov subspace $\mathcal{K}_m$ so that the residual is orthogonal to $A \mathcal{K}_m$. Let $r_0$ be the initial residual and let $v_0 = r_0 / \|r_0\|_2$. The Arnoldi process is applied to build an orthonormal system $v_1, v_2, \ldots, v_{m-1}$ with $v_1 = A v_0 / \|A v_0\|_2$. The approximate solution is obtained from the space $\mathcal{K}_m = \text{span}\{v_0, v_1, \ldots, v_{m-1}\}$.

(i) Show that the approximate solution is obtained as the solution of a least-square problem, and that this problem is triangular.
(ii) Prove that the residual $r_k$ is orthogonal to $\{v_1, v_2, \ldots, v_{k-1}\}$.
(iii) Find a formula for the residual norm.
(iv) Derive the complete algorithm.

Unknown Year

Problem 19. (Structured Linear Systems)

(1) Suppose

\[ S = \begin{bmatrix} \sigma & u^T \\ 0 & S_c \end{bmatrix}, \quad T = \begin{bmatrix} \tau & v^T \\ 0 & T_c \end{bmatrix}, \quad b = \begin{bmatrix} \beta \\ b_c \end{bmatrix}, \]

where $\sigma, \tau, \beta$ are scalars, $S_c$ and $T_c$ are $n \times n$ matrices, and $b_c$ is an $n$-vector. Show that if there exists a vector $\mathbf{x}_c$ such that

\[ (S_c T_c - \lambda I) \mathbf{x}_c = b_c, \]

and $\mathbf{w}_c = T_c \mathbf{x}_c$ is available, then

\[ \mathbf{x} = \begin{bmatrix} \gamma \\ \mathbf{x}_c \end{bmatrix}, \quad \gamma = \frac{\beta - \sigma v^T \mathbf{x}_c - u^T \mathbf{w}_c}{\sigma \tau - \lambda}, \]

solves $(ST - \lambda I) \mathbf{x} = b$.
(2) Hence or otherwise, derive an $O(n^2)$ algorithm for solving the linear system $(U_1 U_2 - \lambda I) \mathbf{x} = b$ where $U_1$ and $U_2$ are $n \times n$ upper triangular matrices, and $(U_1 U_2 - \lambda I)$ is nonsingular. Please write down your algorithm and prove that it is indeed of $O(n^2)$ complexity.
(3) Hence or otherwise, derive an $O(p n^2)$ algorithm for solving the linear system $(U_1 U_2 \cdots U_p - \lambda I) \mathbf{x} = b$ where $\{U_i\}_{i=1}^p$ are all $n \times n$ upper triangular matrices, and $(U_1 U_2 \cdots U_p - \lambda I)$ is nonsingular. Please write down your algorithm and prove that it is indeed of $O(p n^2)$ complexity.

数值积分

2012 Individual

Problem 1. An numerical integration formula is given by

\[ \int_{-1}^{1} f(x) \, dx \approx a f(-1) + b f(c), \]

where $a$, $b$, and $c$ are constants to be chosen arbitrarily.

(a) What is the highest degree $k$ such that the formula is exact for all polynomials of degree up to $k$?
(b) Find the constants $a$, $b$, and $c$ for which the formula is exact for all polynomials of degree up to this $k$.

2013 Team

Problem 2. Let $f(x)$ defined on $[0,1]$ be a smooth function with sufficiently many derivatives. Let $x_i = i h$, where $h = \frac{1}{N}$ and $i = 0,1,\cdots,N$ are uniformly distributed points in $[0,1]$. Consider the numerical integration formula

\[ I_N = \frac{1}{N} \left( a_0 \left( f(x_0) + f(x_N) \right) + a_1 \left( f(x_1) + f(x_{N-1}) \right) + \sum_{i=2}^{N-2} f(x_i) \right). \]

(a) What is the highest integer $k$ such that the formula is $k$-th order accurate, i.e.,

\[ |I_N - \int_0^1 f(x) \, dx| \leq C h^k \]

for a constant $C$ independent of $h$?
(b) Describe the procedure to obtain the two constants $a_0$ and $a_1$ for this $k$.

2019 Team

Problem 3. (Chebyshev Quadrature)

(a) (10 points) Show that the quadrature formula

\[ \int_{-1}^1 \frac{f(x)}{\sqrt{1-x^2}} \, dx = \frac{\pi}{n} \sum_{k=0}^{n-1} f \left( \cos \frac{2k+1}{2n} \pi \right) \]

is exact for all polynomials of degree up to and including $2n-1$.
(b) (15 points) Let $x = (x_0, \ldots, x_{N-1}) \in \mathbb{R}^N$, $x \neq 0$ and $\hat{x}$ be its discrete Fourier transform, i.e.,

\[ \hat{x}_\omega = \frac{1}{\sqrt{N}} \sum_{i=0}^{N-1} x_i \exp(-2\pi i \omega i / N), \quad \omega = 0, \ldots, N-1. \]

Prove that $\|x\|_0 \cdot \|\hat{x}\|_0 \geq N$, where $\|x\|_0$ denotes the number of nonzero entries in $x$.

Hint: Show that $\hat{x}$ cannot have $\|x\|_0$ consecutive zeros.

2018 Individual

Problem 4. Consider the definite integral

\[ I = \int_{a}^{b} f(x) \, dx. \]

(a) Construct an approximation to $I$ by using the composite trapezoidal rule with a uniform partition of the interval $[a, b]$.
(b) Suppose $f \in C^2[a, b]$, show that the above approximation is second-order accurate.
(c) Suppose $f$ is periodic and smooth on the interval $[a, b]$, show that the above approximation is spectral order accurate.

Unknown Year

Problem 5. (Error Estimate for Simpson's Rule) Prove the following error estimate for Simpson's rule:

\[ \int_{a}^{b} f(x) \, dx - \frac{b-a}{6} \left( f(a) + 4f \left( \frac{a+b}{2} \right) + f(b) \right) = -\left( \frac{b-a}{2} \right)^5 \frac{f^{(4)}(\xi)}{90}, \]

where $a < \xi < b$.

数值 ODE

2017 Individual

Problem 1. Consider the differential equation

\[ -u'' + \alpha u = f, \quad x \in (0,1), \]

where prime denotes $d/dx$ and $\alpha$ is a constant. We consider a mixed boundary condition

\[ u(0) = 0, \quad u'(1) - b u(0) = 0. \]

This equation is approximated by a standard finite difference method:

\[ \frac{-U_{j-1} + 2U_j - U_{j+1}}{h^2} + \alpha U_j = f_j, \quad j = 1, \ldots, N-1. \]

Here, $N$ is the number of grid points, $h = 1/N$ is the mesh size, $U_j$ is the approximate solution at $x_j := jh$, and $f_j = f(x_j)$. The boundary condition is approximated by

\[ U_0 = 0, \quad \frac{U_N - U_{N-1}}{h} - b U_N = 0. \]

The resulting linear system is $AU = F$ with

\[\begin{bmatrix} \beta & -1 & 0 & \cdots \\ -1 & \beta & -1 & \cdots \\ & & \ddots & \\ & & & -1 \\ & & & 0 \end{bmatrix} \begin{bmatrix} U_1 \\ U_2 \\ \vdots \\ U_{N-1} \\ U_N \end{bmatrix} = \begin{bmatrix} h^2 f_1 \\ h^2 f_2 \\ \vdots \\ h^2 f_{N-1} \\ 0 \end{bmatrix},\]

where $\beta = 2 + \alpha h^2$.

(a) Write down the complete linear system, including the last row corresponding to the boundary condition at $x=1$.
(b) Analyze the stability and convergence of this finite difference scheme.

2017 Individual

Problem 2. For solving the partial differential equation

\[ u_t + f(u)_x = 0, \quad 0 \leq x \leq 1, \]

where $f'(u) \geq 0$, with periodic boundary condition, we can use the following semi-discrete upwind scheme

\[ \frac{d}{dt} u_j + \frac{f(u_j) - f(u_{j-1})}{\Delta x} = 0, \quad j = 1,2,\ldots,N, \]

with periodic boundary condition $u_0 = u_N$, where $u_j = u_j(t)$ approximates $u(x_j,t)$ at the grid point $x = x_j = j \Delta x$, with $\Delta x = \frac{1}{N}$.

(a) Prove the following $L^2$ stability of the scheme:

\[ \frac{d}{dt} E(t) \leq 0, \]

where $E(t) = \sum_{j=1}^N |u_j|^2 \Delta x$.
(b) Do you believe the above inequality is true for $E(t) = \sum_{j=1}^N |u_j|^{2p} \Delta x$ for arbitrary integer $p \geq 1$? If yes, prove the result. If not, give a counterexample.

2019 Team

Problem 3. (Störmer's Method) Consider the following problems.

(i) Determine the order of Störmer's method,

\[ y_{n+2} - 2y_{n+1} + y_n = h^2 f(t_{n+1}, y_{n+1}), \quad n \geq 0, \]

for solving the second order system of ODE's

\[ y'' = f(t, y), \quad t \geq 0, \]

with the initial conditions $y(0) = y_0$ and $y'(0) = y_0'$.
(ii) Using the second order central differences in space and Störmer's method in time, construct a scheme to solve the wave equation,

\[ u_{tt} = u_{xx}. \]
(iii) Determine the condition for its stability.

2020 Team

Problem 4. For the initial value problem $y' = f(t, y)$, $y(0) = y_0$ on the interval $[0, T]$, consider the implicit two-step method

\[ y_{n+1} = \frac{4}{3} y_n - \frac{1}{3} y_{n-1} + \frac{2h}{3} f(t_{n+1}, y_{n+1}), \]

with starting value $y_1 = y_0 + h f(t_1, y_0)$, where $h$ is the step size and $t_n = n h$.

(a) What is the order of accuracy of the scheme?
(b) Check the stability of the scheme by analyzing the stability polynomial.
(c) Find the stability region of the scheme.

2020 Team

Problem 5. Suppose the difference scheme $u^{n+1} = B u^n$ is stable, and $C(\Delta t)$ is a bounded family of operators. Show that the scheme

\[ u^{n+1} = (B + \Delta t C(\Delta t)) u^n \]

is stable.

2021 Team

Problem 6. Consider the family of semi-implicit Runge-Kutta methods

\[ \begin{aligned} k_1 &= f(y_n + \beta h k_1), \\ k_2 &= f(y_n + h k_1 + \beta h k_2), \\ y_{n+1} &= y_n + h \left( \left(\frac{1}{2} + \beta\right) k_1 + \left(\frac{1}{2} - \beta\right) k_2 \right). \end{aligned} \]

(a) Determine the order and the principal part of the local truncation error.
(b) Show that if $\beta > \frac{1}{2}$, then the negative real axis $\{z : \text{Re}(z) < 0, \text{Im}(z) = 0\}$ is contained in the region of absolute stability of the method.

2021 Team

Problem 7. (Beam Equation) Consider the Beam equation from mechanics with boundary conditions that model a cantilever beam:

\[ u^{(4)} = f(x), \quad x \in (0,1), \]

with boundary conditions

\[ u(0) = u'(0) = u''(1) = u'''(1) = 0. \]

(a) Recast this equation into a variational problem, stating the trial and test function spaces.
(b) Interpret the variational problem as an energy minimization problem, clearly stating the energy functional. Prove that the variational problem and the energy minimization problems are equivalent.
(c) Develop a CG(3) (cubic continuous Galerkin method) finite element method for this problem.
(d) Prove an a priori error estimate for this method in the energy norm:

\[ \|e\|_E = \left( \int_0^1 (e'')^2 dx \right)^{1/2}, \]

where $e = u(x) - U(x)$, in which $u(x)$ is the exact solution to the variational problem, $U(x)$ is the FEM solution.
(e) Prove an a priori error estimate for this method in the $L^2$ norm:

\[ \|e\|_{L^2} = \left( \int_0^1 e^2 dx \right)^{1/2}. \]

数值 PDE

2019T

Problem 1. Consider the following problems. * (i) Determine the order of Störmer's method,

$$
y_{n+2}-2y_{n+1}+y_{n}=h^{2}f(t_{n+1},y_{n+1}),\quad n\geq 0,
$$

for solving the second order system of ODE's

$$
y^{\prime\prime}=f(t,y),\quad t\geq 0,
$$

with the initial conditions $y(0)=y_{0}$ and $y^{\prime}(0)=y_{0}^{\prime}$.

(ii) Using the second order central differences in space and Störmer's method in time, construct a scheme to solve the wave equation,

\[ u_{tt}=u_{xx}. \]
(iii) Determine the condition for its stability.

2019I

Problem 2. Consider Richardson's difference scheme for the heat equation $u_t = u_{xx}$:

\[ \frac{1}{2k}(u(x,t+k)-u(x,t-k))=\frac{1}{h^{2}}(u(x-h,t)-2u(x,t)+u(x+h,t)). \]

(i) Show that this scheme has second-order truncation error.
(ii) Use either ODE principles or von Neumann analysis to show that this scheme is unconditionally unstable.
(iii) Demonstrate a minor modification of the left-side of Richardson's scheme that yields a familiar unconditionally stable scheme and prove it.

2018T

Problem 3. For the one-way wave equation

\[ u_{t}+au_{x}=f, \]

consider the multistep scheme given by

\[ \frac{3u_{m}^{n+1}-4u_{m}^{n}+u_{m}^{n-1}}{2k}+a\frac{u_{m+1}^{n+1}-u_{m-1}^{n+1}}{2h}=f_{m}^{n+1}. \]

(i) Show that the scheme is second order accurate.
(ii) Show that the scheme is unconditionally stable.

Hint: (1) apply von Neumann analysis to the scheme with $f\equiv 0$ and find the characteristic polynomial. (2) show that for all $k,h$, the characteristic polynomial satisfies the root condition: all roots reside in the unit disk, and all roots on the unit circle are simple. (3) for a root $r$ of the characteristic polynomial, it would be more convenient to study the form $\frac{1}{r}=X+iY$ and prove that $X^{2}+Y^{2}\geq 1$.

2018I

Problem 4. We consider the following convection-diffusion equation

\[ u_{t}+au_{x}=bu_{xx},\quad 0\leq x<1 \]

with an initial condition $u(x,0)=f(x)$ and periodic boundary condition, where $a$ and $b>0$ are constants. The first order IMEX (implicit-explicit) time discretization and second order central spatial discretization are used to give the following scheme:

\[ \frac{u_j^{n+1}-u_j^n}{\Delta t}+a\frac{u_{j+1}^n-u_{j-1}^n}{2\Delta x}=b\frac{u_{j+1}^{n+1}-2u_j^{n+1}+u_{j-1}^{n+1}}{\Delta x^2} \]

with a uniform mesh $x_j=j\Delta x$ with spatial mesh size $\Delta x$ and time step $\Delta t$. Here $u_j^n$ is the numerical solution approximating the exact solution at $x=x_j$ and $t=n\Delta t$. Prove that the scheme is $L^2$ stable under the very mild time step restriction

\[ \Delta t \leq c, \]

with a constant $c$ which is independent of $\Delta x$. Can you determine the dependency of $c$ on the two constants $a$ and $b$?

2017T

Problem 5. We have the following partial differential equation

\[ u_{t}=H(u)_{xx},\quad 0\leq x<1 \]

with an initial condition $u(x,0)=f(x)$ and periodic boundary condition. Here $0\leq H^{\prime}(u)\leq d$. Consider the following one-step, three-point scheme on a uniform mesh $x_j=j\Delta x$ with spatial mesh size $\Delta x$:

\[ u^{n+1}_{j}=u^{n}_{j}+aH(u^{n}_{j-1})+bH(u^{n}_{j})+cH(u^{n}_{j+1}), \]

where $a,b,c$ are constants which may depend on the mesh ratio $\mu=\Delta t/\Delta x^{2}$, $\Delta t$ is the time step, and $u^{n}_{j}$ approximates the exact solution at $u(x_j,t^n)$ with $t^{n}=n\Delta t$.

(i) Find the constants $a,b,c$ such that the scheme is second order accurate.
(ii) Find the CFL number $\mu_0$ such that the scheme (with the constants determined by (i)) is stable under the time step restriction $\mu\leq\mu_0$. Please specify which norm you are using for stability, and prove this stability result.

2017I, 2014I

Problem 6. For solving the following partial differential equation

\[ u_{t}+f(u)_{x}=0,\quad 0\leq x\leq 1 \]

where $f^{\prime}(u)\geq 0$, with periodic boundary condition, we can use the following semidiscrete upwind scheme

\[ \frac{d}{dt}u_{j}+\frac{f(u_{j})-f(u_{j-1})}{\Delta x}=0,\quad j=1,2,\ldots,N, \]

with periodic boundary condition $u_{0}=u_{N}$, where $u_{j}=u_{j}(t)$ approximates $u(x_j,t)$ at the grid point $x=x_j=j\Delta x$, with $\Delta x=1/N$.

(i) Prove the following $L^{2}$ stability of the scheme

\[ \frac{d}{dt}E(t)\leq 0 \quad \text{where} \quad E(t)=\sum_{j=1}^{N}|u_{j}|^{2}\Delta x. \]
(ii) Do you believe the above inequality is true for $E(t)=\sum_{j=1}^{N}|u_{j}|^{2p}\Delta x$ for arbitrary integer $p\geq 1$? If yes, prove the result. If not, give a counterexample.

2016T

Problem 7. For solving the following partial differential equation

\[ u_{t}+u_{x}=0,\quad -\infty\leq x\leq\infty \]

with compactly supported initial condition, we consider the following one-step, three-point scheme on a uniform mesh $x_{j}=j\Delta x$ with spatial mesh size $\Delta x$:

\[ u^{n+1}_{j}=au^{n}_{j}+bu^{n}_{j-1}+cu^{n}_{j-2},\quad j=\ldots,-1,0,1,\ldots \]

where $a,b,c$ are constants which may depend on the mesh ratio $\lambda=\Delta t/\Delta x$. Here $\Delta t$ is the time step, and $u^{n}_{j}$ approximates the exact solution at $u(x_{j},t^{n})$ with $t^{n}=n\Delta t$.

(i) Find the constants $a,b,c$ such that the scheme is second order accurate.
(ii) Find the CFL number $\lambda_0$ such that the scheme (with the constants determined by (i)) is stable in $L^{2}$ under the time step restriction $\lambda\leq\lambda_0$.
(iii) If the PDE is defined on $(0,\infty)$ with an initial condition compactly supported in $(0,\infty)$ and a boundary condition $u(0,t)=g(t)$, how would you modify the scheme so that it can be applied? Can you prove the stability and accuracy of your modified scheme?

2016I

Problem 8. Consider the implicit leapfrog scheme

\[ \frac{u_{m}^{n+1}-u_{m}^{n-1}}{2k}+a\left(1+\frac{h^{2}}{6}\delta^{2}\right)^{-1}\delta_{0}u_{m}^{n}=f_{m}^{n} \]

for the one-way wave equation $u_{t}+au_{x}=f$. Here $\delta^{2}$ is the central second difference operator, and $\delta_{0}$ is the central first difference operator.

(1) Show that the scheme is of order $(2,4)$ (second order in time, fourth order in space).
(2) Show that the scheme is stable if and only if $|\frac{ak}{h}|<\frac{1}{\sqrt{3}}$.

2015I

Problem 9. Solve the following linear hyperbolic partial differential equation

\[ u_{t}+au_{x}=0,\quad t\geq 0, \]

where $a$ is a constant. Using the finite difference approximation, we can obtain the forward-time central-space scheme as follows,

\[ \frac{u_{m}^{n+1}-u_{m}^{n}}{k}+a\frac{u_{m+1}^{n}-u_{m-1}^{n}}{2h}=0, \]

where $k$ and $h$ are temporal and spatial mesh sizes.

(i) Show that when we fix $\lambda=k/h$ as a positive constant, the forward-time central-space scheme is consistent with equation $u_t + a u_x = 0$.
(ii) Analyze the stability of this method. Is the method stable with $\lambda=k/h$ being fixed as a constant?
(iii) How would the answer change if you are allowed to make $\lambda=k/h$ small?
(iv) Would this be a good scheme to use even if you can make it stable by making $\lambda$ small? If not, please provide a simple modification to make this scheme stable by keeping $\lambda$ fixed.

2014I

Problem 10. For solving the following heat equation on interval

\[ u_{t}=u_{xx},\quad 0\leq x\leq 1 \]

with boundary condition $u(0)=u_{0},\ u(1)=u_{1}$, we first discretize the interval $[0,1]$ into $N$ subintervals uniformly, that is, the mesh size $h=1/N$. We choose a temporal step size $k$ and approximate the solution $u(jh,nk)$ by $U_{j}^{n}$, $j=1,\ldots,N-1,n=0,1,2,\ldots$. Using the backward Euler method in time and central finite difference in space, the discrete function $U_{j}^{n}$ satisfies:

\[ U_{j}^{n+1}-U_{j}^{n}=\lambda(U_{j-1}^{n+1}-2U_{j}^{n+1}+U_{j+1}^{n+1}),\quad j =1,\ldots,N-1, \]

where $\lambda=k/h^{2}$, and $U_0^{n+1}=u_0$, $U_N^{n+1}=u_1$.

Show that

\[ \frac{1}{2}\sum_{j=1}^{N-1}((U^{n+1}_{j})^{2}-(U^{n}_{j})^{2}) \leq-\lambda\sum_{j=1}^{N-2}(U^{n+1}_{j+1}-U^{n+1}_{j})^{2} -\frac{\lambda}{2}((U^{n+1}_{1})^{2}+(U^{n+1}_{N-1})^{2})+\frac{\lambda}{2}(u_{0}^{2}+u_{1}^{2}). \]

2013T

Problem 11. The wave guide problem is defined as

\[ u_{t}+u_{x}=0,\quad v_{t}-v_{x}=0 \]

with the boundary condition

\[ u(-1,t)=v(-1,t),\quad v(1,t)=u(1,t) \]

and the initial condition

\[ u(x,0)=f(x),\quad v(x,0)=g(x). \]

The upwind scheme for the guide problem is defined as

\[ \begin{aligned} \frac{u^{n+1}_{j}-u^{n}_{j}}{\Delta t}+\frac{u^{n}_{j}-u^{n}_{j-1}}{\Delta x}&=0,\quad j=-N+1,\ldots,N;\\[5pt] \frac{v^{n+1}_{j}-v^{n}_{j}}{\Delta t}-\frac{v^{n}_{j+1}-v^{n}_{j}}{\Delta x}&=0,\quad j=-N,\ldots,N-1; \end{aligned} \]

with the boundary condition

\[ u^{n+1}_{-N}=v^{n+1}_{-N},\quad v^{n+1}_{N}=u^{n+1}_{N} \]

where $u^{n}_{j}$ and $v^{n}_{j}$ approximate $u(x_{j},t^{n})$ and $v(x_{j},t_{n})$ respectively at the grid point $(x_{j},t_{n})$, with $x_{j}=j\Delta x$, $t^{n}=n\Delta t$, $\Delta x=\frac{1}{N}$.

(i) For the solution to the wave guide problem with the above boundary condition, prove the energy conservation

\[ \frac{d}{dt}\int_{-1}^{1}(u^{2}+v^{2})dx=0. \]
(ii) For the numerical solution of the the upwind scheme, if we define the discrete energy as

\[ E^{n}=\sum_{j=-N+1}^{N}(u^{n}_{j})^{2}+\sum_{j=-N}^{N-1}(v^{n}_{j})^{2}, \]

prove the discrete energy stability $E^{n+1}\leq E^{n}$ under a suitable time step restriction $\frac{\Delta t}{\Delta x}\leq\lambda_{0}$. You should first find $\lambda_{0}$.
(iii) Under the same time step restriction, is the numerical solution stable in the maximum norm? That is, can you prove

\[ \max_{-N\leq j\leq N}\max(|u^{n+1}_{j}|,|v^{n+1}_{j}|)\leq\max_{-N\leq j\leq N}\max(|u^{n}_{j}|,|v^{n}_{j}|)? \]

2012I

Problem 12. Describe the forward-in-time and center-in-space finite difference scheme for the one-way wave equation:

\[ u_{t}+u_{x}=0. \]

(i) Conduct the von Neumann stability analysis and comment on their stability property.
(ii) Under what condition on $\Delta t$ and $\Delta x$ would this scheme be stable and convergent?
(iii) How many ways you can modify this scheme to make it stable when the CFL condition is satisfied?

2011T

Problem 13. We use the following scheme to solve the PDE $u_{t}+u_{x}=0$:

\[ u^{n+1}_{j}=au^{n}_{j-2}+bu^{n}_{j-1}+cu^{n}_{j} \]

where $a,b,c$ are constants which may depend on the CFL number $\lambda=\frac{\Delta t}{\Delta x}$. Here $x_{j}=j\Delta x$, $t^{n}=n\Delta t$ and $u^{n}_{j}$ is the numerical approximation to the exact solution $u(x_{j},t^{n})$ with periodic boundary conditions.

(i) Find $a,b,c$ so that the scheme is second order accurate.
(ii) Verify that the scheme you derived in Part (i) is exact (i.e. $u^{n}_{j}=u(x_{j},t^{n})$) if $\lambda=1$ or $\lambda=2$. Does this imply that the scheme is stable for $\lambda\leq 2$? If not, find $\lambda_{0}$ such that the scheme is stable for $\lambda\leq\lambda_{0}$.

Recall that a scheme is stable if there exist constants $M$ and $C$, which are independent of the mesh sizes $\Delta x$ and $\Delta t$, such that $\|u^{n}\|\leq Me^{CT}\|u^{0}\|$ for all $\Delta x$, $\Delta t$ and $n$ such that $t^{n}\leq T$. You can use either the $L^{\infty}$ norm or the $L^{2}$ norm to prove stability.

2010T

Problem 14. When considering finite difference schemes approximating partial differential equations (PDEs), for example, the scheme

\[ u^{n+1}_{j}=u^{n}_{j}-\lambda(u^{n}_{j}-u^{n}_{j-1}) \]

where $\lambda=\frac{\Delta t}{\Delta x}$, approximating the PDE $u_{t}+u_{x}=0$, we are often interested in stability, namely

\[ \|u^{n}\|\leq C\|u^{0}\|,\quad n\Delta t\leq T \]

for a constant $C=C(T)$ independent of the time step $\Delta t$ and the spatial mesh size $\Delta x$. Here $\|\cdot\|$ is a given norm, for example the $L^{2}$ norm or the $L^{\infty}$ norm, of the numerical solution vector $u^{n}=(u^{n}_{1},u^{n}_{2},\ldots,u^{n}_{N})$. The mesh points are $x_{j}=j\Delta x$, $t^{n}=n\Delta t$, and the numerical solution $u^{n}_{j}$ approximates the exact solution $u(x_{j},t^{n})$ of the PDE with a periodic boundary condition.

(i) Prove that the scheme $u^{n+1}_{j}=u^{n}_{j}-\lambda(u^{n}_{j}-u^{n}_{j-1})$ is stable in the sense of (14) for both the $L^{2}$ norm and the $L^{\infty}$ norm under the time step restriction $\lambda\leq 1$.
(ii) Since the numerical solution $u^{n}$ is in a finite dimensional space, Student A argues that the stability (14), once proved for a specific norm $\|\cdot\|_{a}$, would also automatically hold for any other norm $\|\cdot\|_{b}$. His argument is based on the equivalency of all norms in a finite dimensional space, namely for any two norms $\|\cdot\|_{a}$ and $\|\cdot\|_{b}$ on a finite dimensional space $W$, there exists a constant $\delta>0$ such that

\[ \delta\|u\|_{b}\leq\|u\|_{a}\leq\frac{1}{\delta}\|u\|_{b}. \]

Do you agree with his argument? If yes, please give a detailed proof of the following theorem: If a scheme is stable, namely (14) holds for one particular norm (e.g. the $L^{2}$ norm), then it is also stable for any other norm. If not, please explain the mistake made by Student A.

2010T

Problem 15. We have the following 3 PDEs

\[ \begin{aligned} u_{t}+Au_{x} &=0, (15)\\ u_{t}+Bu_{x} &=0, (16)\\ u_{t}+Cu_{x} &=0,\quad C=A+B. (17) \end{aligned} \]

Here $u$ is a vector of size $m$ and $A$ and $B$ are $m\times m$ real matrices. We assume $m\geq 2$ and both $A$ and $B$ are diagonalizable with only real eigenvalues. We also assume periodic initial condition for these PDEs.

(i) Prove that (15) and (16) are both well-posed in the $L^{2}$-norm. Recall that a PDE is well-posed if its solution satisfies

\[ \|u(\cdot,t)\|\leq C(T)\|u(\cdot,0)\|,\quad 0\leq t\leq T \]

for a constant $C(T)$ which depends only on $T$.
(ii) Is (17) guaranteed to be well-posed as well? If yes, give a proof; if not, give a counter example.
(iii) Suppose we have a finite difference scheme $u^{n+1}=A_{h}u^{n}$ for approximating (15) and another scheme $u^{n+1}=B_{h}u^{n}$ for approximating (16). Suppose both schemes are stable in the $L^{2}$-norm. If we now form the splitting scheme $u^{n+1}=B_{h}A_{h}u^{n}$ which is a consistent scheme for solving (17), is this scheme guaranteed to be $L^{2}$ stable as well? If yes, give a proof; if not, give a counter example.

练习题集

函数逼近与插值

数值代数

数值积分

数值 ODE

数值 PDE

应用数学

变分法