算法的数值稳定性

内容来源
数值分析第五版 清华大学出版社

定义

一个算法如果输入数据有误差，而在计算过程中舍入误差不增长，则称此算法是数值稳定的，否则是不稳定的

（感觉应该是初始误差限不增长）

例

计算 $I_n=e^{-1}{\int }_0^1{x}^n{e}^x\mathrm{d}x(n=0,1,\cdots )$ 并估计误差

由分部积分得

$$\{\begin{array}{l}{I}_n=1-n{I}_{n-1},n>0\\ I_0=1-e^{-1}\end{array}$$

用泰勒多项式展开部分和估计 $e^{-1}$

$$e^{-1}\approx 1+(-1)+\frac{(-1{)}^2}{2!}+\cdots +\frac{(-1{)}^k}{k!}$$

取 $k=7$ ，用 $4$ 位小数计算，$I_0\approx 0.6321={\tilde{I}}_0$ ，用上面的递推公式计算结果如下

表中 ${\tilde{I}}_8$ 为负值，与 $I_n>0$ 相矛盾

这里计算公式与每步计算都是正确的，正是误差在计算过程中被逐步放大才导致错误的计算结果

设初始误差为 $E_0$ 根据递推公式得

$$E_n=-n{E}_{n-1},n>0$$

所以

$$E_n=(-1{)}^{n}n!E_0$$

这表明这种计算方法是数值不稳定的

换一种计算方案

由积分估值得（注意到）

$$\frac{e^{-1}}{n+1}=e^{-1}(\underset{0⩽x⩽1}{\min }{e}^x){\int }_0^1{x}^n\mathrm{d}x<I_n<e^{-1}(\underset{0⩽x⩽1}{\max }{e}^x){\int }_0^1{x}^n\mathrm{d}x=\frac{1}{n+1}$$

取 $n=9$ 得

$$\frac{e^{-1}}{10}<I_9<\frac{1}{10}$$

取 $\frac{1}{2}\left(\frac{e^{-1}}{10}+\frac{1}{10}\right)\approx 0.0684=\widetilde{I_9}$ ，再将递推公式倒过来

$$\{\begin{array}{l}{\tilde{I}}_{n-1}=\frac{1}{n}(1-{\tilde{I}}_n),n<9\\ {\tilde{I}}_9=0.0684\end{array}$$

${\tilde{I}}_0$ 与 $I_0$ 的误差已经小于 $10^{-4}$

在这种计算方案中，误差是逐步缩小的，因而是数值稳定的

$$E_{n-1}=-\frac{1}{n}{E}_n$$