Notes for NTU MH3700 Numerical Analysis I.
可选太多学不完了。
趁着暑假对着 ppt 复习一下。
尽管上课时候讲这玩意儿还是很严谨的，但时间原因以及毕竟选这门课纯属玩，很多情况下就不给出严格证明或者一笔带过了。
首先登场的是二分法，不讲。
接下来说 fixed-point iteration。就是我们要解决 \(g(x)-x=0\) 也就是 \(g(x)=x\) 的问题。
那么首先很显然的是如果 \(x\in[a, b]\) 时，\(g(x)\in[a, b]\)，那么在 \([a, b]\) 里铁定有一个解的。
那啥时候不动点唯一呢？如果存在 \(k<1\) 使得 \(\forall x\in[a, b], \left\lvert g'(x)\right\rvert \le k\)，那么我们说是唯一的。
感性理解是可以嘟，严格证明用 Largrange 中值定理搞搞。
然后 fixed-point iteration 就是我们一开始选个 \(p_0\)，然后 \(p_{n+1}=g(p_n)\)，蹲着他收敛就行。
一定收敛吗？我们有一个定理就是如果存在一个 \(k\in(0, 1)\) 使得 \(\left\lvert g'(x)\right\rvert \le k\)，那么就一定收敛。
证明的话因为我们有 Largrange 中值定理
\[\left|p_{n+1}-p\right|=\left|g(p_n)-g(p)\right|=\left|g'(\xi_n)\right|\cdot\left|p_n-p\right|\le k\cdot\left|p_n-p\right|\]也就是说 \(k\) 越小收敛得越快。
然后我们考虑我们要解 \(f(x)=0\)，我们要构造一个 \(g(x)\) 使得
\[f(x)=0\Leftrightarrow g(x)=x\]我们可以有：
\[g(x)=x-\phi(x)f(x)\]咱现在需要做的就是找到一个合适得 \(\phi(x)\) 让他收敛的尽量快。
那怎么看收敛的尽量快呢，我们假设有个序列 \(\{p_n\}_{n=0}^\infty\)，如果存在 \(\alpha, \lambda>0\) 使得
\[\lim_{n\to\infty}\frac{\left|p_{n+1}-p\right|}{\left|p_n-p\right|^\alpha}=\lambda\]我们定义 \(\{p_n\}_{n=0}^\infty\) converge to \(p\) with order \(\alpha\).
我们转到 \(g(x)\) 上的时候，我们发现 \(g'(p)=0\) 意味着这个序列的收敛速度一定是大于 \(1\) 的。我们考虑泰勒展开：
\[\lim_{n\to\infty}\frac{\left|p_{n+1}-p\right|}{\left|p_n-p\right|}=\lim_{n\to\infty}\frac{\left|g(p_n)-g(p)\right|}{\left|p_n-p\right|}=\left|g'(p)\right|=0\]也就是说 \(\alpha=1\) 的时候 \(\lambda=0\)，而定义里说 \(\lambda>0\)，也就是我们得让下面的阶数更大，即 \(\alpha>1\)。
那我们导一下 \(g(x)\)：
\[g'(x)=1-\phi(x)f'(x)-\phi'(x)f(x)\]考虑到 \(f(p)=0\)，我们有
\[g'(p)=1-\phi(p)f'(p)\]当 \(f'(p)=0\) 时，方程无解，否则我们可以让 \(\phi(p)=\frac{1}{f'(p)}\)。
于是我们就推出了 Newton’s method：
\[p_{n+1}=p_n-\frac{f(p_n)}{f'(p_n)}\]另一种 secant method 是因为有时候 \(f'(x)\) 很难求，我们可以用两个点的斜率代替：
\[p_{n+1}=p_n-f(p_n)\cdot\frac{p_n-p_{n-1}}{f(p_n)-f(p_{n-1})}\]尽管这玩意儿的 rate of convergence 是 \(\frac{1+\sqrt{5}}{2}\approx1.618\)，但不需要求导，通常情况下 have better convergence than Newton per evaluation of \(f\)。
然后现在问题是我们需要求解更高维度的方程，那我们就可以构造一个 \(\mathbb{R}^n\to\mathbb{R}^n\) 的函数 \(\boldsymbol{f}\) 求解
\[\boldsymbol{f}(\boldsymbol{x})=\boldsymbol{0}\]大概感性理解一下，我们对 \(\boldsymbol{f}\) 做泰勒展开：
\[\boldsymbol{f}(\boldsymbol{a}+\boldsymbol{\delta})=\boldsymbol{f}(\boldsymbol{a})+\mathsf{D}\boldsymbol{f}(\boldsymbol{a})\cdot\boldsymbol{\delta}+\mathcal{O}\left(\left\|\boldsymbol{\delta}\right\|^2\right)\]其中 \(\mathsf{D}\boldsymbol{f}(\boldsymbol{a})\) 是 Jacobian matrix，我们通常记作 \(\mathsf{J}(\boldsymbol{x})\)：
\[\mathsf{J}(\boldsymbol{x})=\mathsf{D}\boldsymbol{f}(\boldsymbol{x})=\begin{bmatrix} \frac{\partial f_1}{\partial x_1} & \frac{\partial f_1}{\partial x_2} & \cdots & \frac{\partial f_1}{\partial x_n} \\ \frac{\partial f_2}{\partial x_1} & \frac{\partial f_2}{\partial x_2} & \cdots & \frac{\partial f_2}{\partial x_n} \\ \vdots & \vdots & \ddots & \vdots \\ \frac{\partial f_n}{\partial x_1} & \frac{\partial f_n}{\partial x_2} & \cdots & \frac{\partial f_n}{\partial x_n} \end{bmatrix}\]于是我们有迭代公式：
\[\boldsymbol{x}_{n+1}=\boldsymbol{x}_n-\mathsf{J}^{-1}(\boldsymbol{x}_n)\cdot\boldsymbol{f}(\boldsymbol{x}_n)\]我们有一组点 \((x_0, y_0), (x_1, y_1), \cdots, (x_n, y_n)\)，我们要找一个多项式 \(\mathcal{P}(x)\) 使得 \(\mathcal{P}(x_i)=y_i\)。
最直接的方法是解方程：
\[\boldsymbol{a}=\mathcal{V}^{-1}\boldsymbol{y}\]其中 \(\mathcal{V}\) 是 Vandermonde matrix：
\[\mathcal{V}=\begin{bmatrix} 1 & x_0 & x_0^2 & \cdots & x_0^n \\ 1 & x_1 & x_1^2 & \cdots & x_1^n \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \cdots & x_n^n \end{bmatrix}\]复杂度 \(\mathcal{O}(n^3)\)。
在历史上的话欧陆这边最有名的是 Lagrange 插值，以及 Newton 那边的 divided difference。
Lagrange 插值是一种 \(\mathcal{O}(n^2)\) 的算法。
我们想要的是构造一组基：
\[\mathcal{L}_{n, k}(x_i)=[i=k]\]那我们就可以有：
\[\mathcal{P}_n(x)=\sum_{k=0}^n y_k\cdot \mathcal{L}_{n, k}(x)\]而基的构造方式是：
\[\mathcal{L}_{n, k}(x)=\prod_{j\neq k}\frac{x-x_j}{x_k-x_j}\]关于准确性我们用 Rolle 定理可以证明，对于 \((x_0, x_1, \cdots, x_n)\in[l, r]^n\)，如果 \(x\in[l, r]\)，我们有存在 \(\xi\in[l, r]\) 使得：
\[f(x)=\mathcal{P}_n(x)+\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^n(x-x_i)\]接下来讲的是 Neville’s scheme，我们令 \(\mathcal{P}_{n-1, i}\) 表示用 \(x_0, x_1, \cdots, x_{i-1}, x_{i+1}, \cdots, x_n\) 插值出的多项式，我们有：
\[\mathcal{P}_n(x)=\frac{(x-x_j)\cdot\mathcal{P}_{n-1, j}(x)-(x-x_i)\cdot\mathcal{P}_{n-1, i}(x)}{x_i-x_j}\]于是乎我们就能用这种方法进行 dp，令 \(\mathcal{P}_{l, r}(x)\) 表示通过 \(x_l, x_{l+1}, \cdots, x_r\) 插值出的多项式。我们就有：
\[\mathcal{P}_{l, r}(x)=\frac{(x-x_l)\cdot\mathcal{P}_{l+1, r}(x)-(x-x_r)\cdot\mathcal{P}_{l, r-1}(x)}{x_r-x_l}\]这个做法的一个好处是可以在线性时间内增加一个点。
另外一种方法叫做 Newton’s divided difference，我们定义：
\[\begin{aligned} f[x_i]&=f(x_i) \\ f[x_i, x_{i+1}]&=\frac{f[x_{i+1}]-f[x_i]}{x_{i+1}-x_i} \\ f[x_i, x_{i+1}, \cdots, x_{i+k}]&=\frac{f[x_{i+1}, x_{i+2}, \cdots, x_{i+k}]-f[x_i, x_{i+1}, \cdots, x_{i+k-1}]}{x_{i+k}-x_i} \end{aligned}\]我们有：
\[\mathcal{P}_n(x)=f[x_0]+\sum_{k=1}^n\left(f[x_0, x_1, \cdots, x_k]\cdot\prod_{j=0}^{k-1}(x-x_j)\right)\]