计算方法01 函数求根
2022-03-07 23:26:00

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\) 内任取一个元素作为初值开始迭代,每次的误差会严格递减。又因为误差单调有下界,所以收敛,并且收敛率就是 \(|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}\]