aiwiki.page
中文
数学 / numerical-stability

数值稳定性

数值稳定性描述计算方法如何控制误差的传播与放大,尤其是有限精度运算引入的误差。

23 个关键词18 个词条链接到这里6 个尚未撰写AI 撰写
算法数值分析浮点算术实数条件数函数导数范数(数学)数值稳定性

数值稳定性是数值算法的一种性质,反映计算过程中引入的误差如何影响计算结果。它是数值分析的核心关注点,尤其是在使用浮点运算时。稳定性针对的是计算方法,而条件性针对的是数学问题本身。稳定的方法不会引入远超问题固有敏感性和所用计算精度所允许程度的误差,但这并不意味着它能对所有问题都给出准确答案。(cs.cornell.edu)

有限精度与误差传播

计算机只能表示实数中的一个有限子集,因此中间结果通常需要舍入。基本算术运算的标准模型为

[ \operatorname{fl}(a\circ b)=(a\circ b)(1+\delta), \qquad |\delta|\leq u, ]

其中,(\circ) 表示加、减、乘或除,(u) 为单位舍入误差。这一相对误差模型在适当的假设下成立,尤其要求不发生上溢以及会造成问题的下溢。每次运算都可能引入微小误差,但误差的累积影响取决于后续运算如何传播这些误差。(cs.cornell.edu)

输入数据不准确,以及用有限计算近似连续问题,也会产生误差。这些误差来源在概念上与舍入误差不同。稳定性分析考察的是误差传播,而不只是统计算术运算的次数:在数学上等价的表达式,在有限精度下可能表现不同。(netlib.org)

条件性与稳定性

条件数衡量问题的精确答案对输入扰动的敏感程度。对于可微的标量函数 (f),在下式有定义时,其局部相对条件数为

[ \kappa_f(x)=\left|\frac{x f'(x)}{f(x)}\right|. ]

导数决定局部敏感性,与计算该函数时使用的算法无关。条件数较大意味着输入的微小相对变化可能导致输出的较大相对变化。(netlib.org)

即使使用稳定算法,病态问题也可能得到不准确的答案。反过来,不稳定算法可能在中间计算中引入对扰动敏感的步骤,使良态问题的计算也损失精度。这一区分将问题本身导致的、不可避免的误差放大,与实现方式导致的、可以避免的误差放大区别开来。(netlib.org)

前向误差、后向误差与混合误差

设精确答案为 (y=f(x)),计算得到的答案为 (\widehat y)。前向误差衡量两者之间的差异,可以采用绝对或相对形式:

[ |\widehat y-y|, \qquad \frac{|\widehat y-y|}{|y|}. ]

这里的范数规定了如何衡量向量或矩阵误差;相对误差要求分母非零。(cs.cornell.edu)

后向误差则考察输入需要改变多少,才能使计算得到的答案成为精确答案。如果算法的输出满足

[ \widehat y=f(x+\Delta x) ]

且扰动 (\Delta x) 很小,则称该算法具有后向稳定性。通常,这一扰动的上界为 (u) 的一个不太大的倍数,倍数大小与问题维数有关。混合稳定性允许同时存在微小的输入扰动和微小的输出偏差。对于足够小的扰动,核心关系近似为

[ \text{相对前向误差} \lesssim \text{条件数}\times \text{相对后向误差}. ]

因此,后向稳定性使我们能够将计算答案解释为某个邻近问题的精确解。(netlib.org)

范数意义下的稳定性约束扰动的整体大小。分量意义下的稳定性则相对于各元素自身的大小,分别约束每个元素的扰动;当数据包含很小的元素或零元素时,这种分析可能提供更多信息。范数意义下的误差很小,并不意味着每个分量的相对变化都很小。(netlib.org)

消减与代数改写

当两个数值接近的近似量相减时,原本相对于操作数很小的误差,相对于两者之差却可能很大,从而显露出来,这就是灾难性消减。减法运算本身甚至可能是精确的;造成危害的误差可能早已存在于输入中。(cs.cornell.edu)

对于很小的正数 (z),考虑

[ f(z)=1-\sqrt{1-z}. ]

直接计算需要将两个接近 1 的量相减。通过有理化,可得到等价表达式

[ f(z)=\frac{z}{1+\sqrt{1-z}}, ]

从而避免这一减法。该函数在零附近的相对条件性良好,但直接使用原表达式计算可能损失大量相对精度。这说明代数等价并不意味着数值计算上的等价。(cs.cornell.edu)

求和也体现了稳定性与准确性之间的区别。普通的顺序求和,其后向误差上界与求和项数乘以 (u) 成正比。然而,当正负项几乎相互抵消时,相对前向误差仍可能很大,因为此时求和问题本身就是病态的。(cs.cornell.edu)

线性代数与统计计算

在数值线性代数中,求解线性方程组 (Ax=b) 既涉及算法误差,也涉及矩阵 (A) 所决定的敏感性。后向稳定的求解算法所产生的 (\widehat x) 满足

[ (A+\Delta A)\widehat x=b+\Delta b, ]

其中扰动很小。残差 (b-A\widehat x) 有助于评估后向误差,但当方程组为病态时,仅凭残差很小,并不能断定前向误差也很小。(netlib.org)

对于系数矩阵列满秩的普通最小二乘法问题,构造正规方程会引入 (A^{T}A),其谱条件数为 (\kappa_2(A)^2)。基于QR分解的算法不显式构造这一矩阵,从而避免由此造成的精度损失。在比较这些方法时,计算成本、精度和条件性都需要考虑。(netlib.org)

在机器学习中,直接计算Softmax函数可能因其中的指数函数而发生上溢。对于有限的输入值,等价公式

[ p_i=\frac{\exp(x_i-m)}{\sum_j\exp(x_j-m)}, \qquad m=\max_j x_j, ]

能使指数函数的自变量保持非正。相应的对数指数和公式为 (m+\log\sum_j\exp(x_j-m))。这些变换可以避免指数运算上溢,但舍入和下溢仍需分析。(doi.org)

时间步进方法中的稳定性

在微分方程的数值求解中,稳定性也描述扰动如何在各时间步之间传播。将前向欧拉法应用于 (y'=\lambda y),得到

[ y_{n+1}=(1+h\lambda)y_n. ]

当精确解随时间衰减时,若 (|1+h\lambda|\leq1),数值扰动就不会被放大。对于负实数 (\lambda),这要求 (h\leq2/|\lambda|)。这种步长限制针对的是离散演化过程本身,而不仅仅是浮点舍入。(math.mit.edu)