Fixpoint Theorem
定义函数 \(f\) 的不动点 \(r\) 为满足 \(f(r)=r\) 的所有取值
考虑函数 \(f\)，定义不动点迭代算法如下：
任取 \(X\in D(f)\)
计算 \(X=f(X)\)
重复步骤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\) 内任取一个元素作为初值开始迭代，每次的误差会严格递减。又因为误差单调有下界，所以收敛，并且收敛率就是 \(|f'(r)|<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}\]