计算方法01 函数求根

\newcommand\norm[1]{\left\lVert#1\right\rVert} \newcommand\abs[1]{\left\lvert#1\right\rvert}

Fixpoint Theorem

定义函数 $f$ 的不动点 $r$ 为满足 $f(r)=r$ 的所有取值

考虑函数 $f$，定义不动点迭代算法如下：

1. 任取 $X\in D(f)$

2. 计算 $X=f(X)$

3. 重复步骤2 $k$ 次

记出现的所有 $X$ 按顺序构成数列 $\left{x_n\right}$，定理如下

若 $f$ 是连续函数，且 $\lim\limits_{n\rightarrow \infty}x_n=r$，那么 $f(r)=r$

证明：

$f(r)=f\left(\lim\limits_{n\rightarrow\infty}x_n\right)=\lim\limits_{n\rightarrow\infty}f(x_n)=\lim\limits_{n\rightarrow\infty}x_{n+1}=r$

根据定义，$r$ 是一个不动点

具体解释就是，当 $k$ 充分大的时候，我们会得到一个充分接近 $r$ 的近似解（极限的定义）

Convergence Theorem

不动点定理说的是：如果迭代收敛，那么收敛到不动点

收敛定理则给出了迭代收敛的一个充分条件，也就是挑出了一类特殊的可以收敛的函数，给了一个判别条件。

定义 $e_n=\left|x_n-r\right|$，若 $\lim\limits_{n\rightarrow\infty}\frac{e_{n+1} }{e_{n} }=S<1$，那么称这个迭代是线性收敛的，收敛率为 $S$

若函数 $f$ 连续可导，并且 $r$ 是 $f$ 的一个不动点，那么由 $|f’(r)|<1$ 可以推出 $f$ 在以一个足够接近 $r$ 的初值开始迭代时线性收敛，收敛率为 $S$

这句话很难理解，但是结合证明就不太难了：

考虑 $x_{n+1}=f(x_n)$，那么有 $\frac{e_{n+1} }{e_n}=\left|\frac{f(x_n)-r}{x_n-r}\right|=\left|\frac{f(x_n)-f(r)}{x_n-r}\right|=\left|f’(\xi)\right|$，其中 $\xi\in(x_n,r)$，最后一个等号是微分中值定理

取极限就得到了一个 $x=r$ 处的导数，根据条件有这个极限的绝对值小于 $1$

又因为 $f$ 连续可导，所以 $f’$ 连续，所以存在邻域 $U=(r-\delta,r+\delta)$ 使得 $\forall x\in(r-\delta,r+\delta)$ 都有 $|f’(x)|<1$

我们把这类收敛称为局部收敛

具体解释就是，如果函数连续可导并且不动点处的导数比较好，那么存在一个区间 $U$，如果我们在 $U$ 内开始迭代时，就能线性收敛到不动点，并且收敛率是不动点处的导数。

但是定理反过来不成立，意思是一个并非局部收敛的函数可能在别的地方收敛到此，这是完全可行的。

这个定理可以是后验的，即先算出一个收敛的点，然后求导验证是否满足定理前提。

根的敏感性

假设 $f$ 的计算存在误差，例如给定 $x$ 时我们只能计算 $f(x)+\epsilon g(x)$，其中 $\epsilon$ 是一个小常数，$g$ 是一个关于 $x$ 的误差函数。那么我们在求根 $r$ 时引入的误差就会进一步被放大。

不妨设求得的数值根为 $r+\Delta r$，那么我们此时求得的实际上是带误差的函数的根，满足

\begin{aligned}

f(r+\Delta r)+\epsilon g(r+\Delta r)=0

\end{aligned}

两边泰勒展开一下就有

\begin{aligned}

f(r)+\Delta r f’(r) + \epsilon g(r) + \epsilon \Delta r g’(r) + O\left({\Delta r}^2\right)=0

\end{aligned}

舍去高阶无穷小就是

\begin{aligned}

\Delta r=\frac{-\epsilon g(r)-f(r)}{f’(r)+\Delta r g’(r)}

\end{aligned}

注意到 $f(r)=0$ 是 $f$ 的根的定义，且 $\Delta r$ 很小，因此上式约为

\begin{aligned}

\Delta r\approx -\epsilon\frac{g(r)}{f’(r)}

\end{aligned}