算法稳定性

阐述

算法稳定性是指输出的误差积累相对于输入的误差的大小。

一般的定义

对于函数 $f(x)$ 以及它的浮点数算法 $\tilde f(x)$，它是稳定的，如果存在一个邻近的 $\tilde x$ 使得

$$\|\tilde f(x)-f(\tilde x)\|=\|f(x)\|O(\varepsilon); \quad \|\tilde x-x\|=\|x\|O(\varepsilon)$$

也就是说，这样的算法对几乎正确的输入总是给出几乎正确的输出。

后向稳定性

对于函数 $f(x)$ 以及它的浮点数算法 $\tilde f(x)$，它是后向稳定的，如果存在一个邻近的 $\tilde x$ 使得

$$\tilde f(x)=f(\tilde x); \quad \|\tilde x-x\|=\|x\|O(\varepsilon)$$

注意，$O$ 中的常数项可以与问题的大小有关，但是不能与 $x$ 有关。也就是说，这样的算法对几乎正确的输入总是给出正确的输出。

前向稳定性

前向稳定性可以定义为

$$\|\tilde f(x)-f(x)\|=\|f(x)\|O(\varepsilon)$$

但是这个基本上不会成立，而后向稳定性基本上可以满足。

如果是后向稳定的，我们可以用下式来估算前向误差：

$$\frac{\|\tilde f(x)-f(x)\|}{\|f(x)\|}=\frac{\|f(\tilde x)-f(x)\|/\|\tilde x-x\|}{\|f(x)\|/\|x\|}\frac{\|\tilde x-x\|}{\|x\|}\le K_f(x)O(\varepsilon_{\rm machine})$$

这里，$K_f(x)$ 的定义是这一比例在 $\varepsilon\to 0$ 时的上确界，它与具体的算法无关，只与函数本身的性质有关。如果函数可微，那么可以用 Jacobian 来估算 $K$：

$$K_f(x)=\frac{\|J\|}{\|f(x)\|/\|x\|}$$

矩阵的条件数

考虑函数 $f(x)=Ax$，那么

$$K_f(x)=\frac{\|A\|}{\|Ax\|/\|x\|}\le\|A\|\sup_{x\ne 0}\frac{\|x\|}{\|Ax\|}$$

如果 $A$ 是可逆的方阵，那么上式可以简化为

$$\kappa(A)=\|A\|\|A^{-1}\|$$

对于正交矩阵，这个条件数为 1；而对于接近奇异的矩阵，这个条件数非常大。

以下我们主要讨论 2-范数，注意到 2-范数等价于

$$\sqrt{\sup_{x\ne 0}\frac{x^*A^*Ax}{x^*x}}$$

其中 $A^*A=H$ 是 Hermitian 矩阵，其 Rayleigh 商满足 $R_H(x)=x^*Hx/x^*x$。所以，我们得到：

• $L_2$-诱导范数等价于 $A^*A$ 的最大特征值的平方根
• 逆矩阵的诱导范数等价于 $A^*A$ 的最小特征值的平方根倒数

但是，研究 $A^*A$ 还是不够方便，这引出了奇异值分解。

实例

例如，对于简单求和算法来说，

$$|\tilde f(x)-f(x)|\le n\varepsilon_{\rm machine}\sum_i|x_i|+O(\varepsilon^2)$$

也就是说，相对误差大概是

$$\frac{|\tilde f(x)-f(x)|}{|f(x)|}\le n\varepsilon\frac{\sum_i|x_i|}{\left|\sum_ix_i\right|}$$

后一项称为问题的条件数，如果求和项都是正的，则为 1；如果总和接近 0，则条件数很大。

容易证明，上述的简单求和算法是后向稳定的。

性质

相关内容

参考文献