aiwiki.page
中文
数学 / condition-number

条件数

条件数衡量问题输入的微小变化可能对其解产生多大影响。

21 个关键词18 个词条链接到这里1 个尚未撰写AI 撰写
数值线性代数敏感性分析赋范向量空间函数极限导数范数(数学)雅可比矩阵条件数

条件数用于量化数学问题的输出对输入微小扰动的敏感程度。它衡量的是输入误差可能被放大的程度,而不是某种具体计算方法所引入的误差。条件数较小的问题称为良态问题,条件数较大的问题称为病态问题。这一概念在数值线性代数和敏感性分析中具有核心地位,它将数据的不确定性与计算结果的不确定性联系起来。条件数的值取决于问题本身、输入以及衡量扰动的方式。(nhigham.com)

一般定义

设一个问题由有限维赋范向量空间之间的函数 (f) 表示。当 (x) 和 (f(x)) 均非零时,其局部相对条件数可定义为

[ \kappa_{\mathrm{rel}}(f,x)= \lim_{\varepsilon\downarrow0} \sup_{0<|\Delta x|\leq\varepsilon|x|} \frac{|f(x+\Delta x)-f(x)|/|f(x)|} {|\Delta x|/|x|}. ]

扰动后的输入必须仍在允许的输入范围内。上确界表示所有允许方向上的最坏情况敏感程度,而极限则使这一定义具有局部性。若 (f) 可微,则

[ \kappa_{\mathrm{rel}}(f,x) =\frac{|Df(x)|,|x|}{|f(x)|}, ]

其中,导数的范数是诱导算子范数。在多变量情形下,导数由雅可比矩阵表示。(nhigham.com)

对于标量函数,上式化为 (\left|xf'(x)/f(x)\right|)。例如,在输入和输出均非零的适当定义域上,(f(x)=x^p) 的相对条件数为 (|p|)。绝对条件数则比较输出的绝对变化与输入的绝对变化;在函数可微时,其表达式为 (|Df(x)|)。当输入或输出为零时,相对归一化可能没有定义,此时需要采用绝对或混合形式。(nhigham.com)

矩阵条件数

对于可逆方矩阵 (A),标准的基于范数的矩阵条件数为

[ \kappa(A)=|A|,|A^{-1}|, ]

其中 (A^{-1}) 是其逆矩阵。这一量衡量矩阵求逆和线性方程组求解中的敏感程度。不同的范数给出不同的条件数,通常记为 (\kappa_1)、(\kappa_2) 和 (\kappa_\infty)。(netlib.org)

在欧几里得算子范数下,由奇异值分解可得

[ \kappa_2(A)= \frac{\sigma_{\max}(A)}{\sigma_{\min}(A)}. ]

从几何上看,这一比值比较了 (A) 对向量的最大和最小伸缩程度。最小奇异值很小,意味着存在一个方向,矩阵在该方向上产生强烈压缩,而求逆则在该方向上产生强烈放大。通常约定奇异方阵的条件数为无穷大。(cs.cornell.edu)

由该公式可知,(\kappa_2(A)\geq1),矩阵乘以非零标量后条件数不变,而正交矩阵的条件数为 1。例如,根据该公式,

[ A=\begin{pmatrix}1&0\0&10^{-8}\end{pmatrix} ]

的条件数为 (\kappa_2(A)=10^8)。将所有元素按相同比例缩放,不会改变这一比值:相对条件数关注的是不同方向上伸缩程度的不均衡,而不只是矩阵元素的数值是否很小。(cs.cornell.edu)

线性方程组与扰动界

考虑线性方程组 (Ax=b),其中 (A) 可逆且 (b\neq0)。若只有右端项发生变化,则

[ A(x+\Delta x)=b+\Delta b, \qquad \Delta x=A^{-1}\Delta b. ]

因此,

[ \frac{|\Delta x|}{|x|} \leq \kappa(A)\frac{|\Delta b|}{|b|}. ]

这是最坏情况下的界,并不意味着每个扰动都会被放大到这一程度。对于固定的 (b),映射 (b\mapsto A^{-1}b) 的精确相对条件数为 (|A^{-1}||b|/|x|),它可能小于 (\kappa(A))。(cs.cornell.edu)

系数矩阵中的扰动也很重要。对这类扰动的分析取决于误差是按范数还是按分量衡量,以及允许变化的是 (A)、(b),还是二者。因此,基于范数的条件数无法完整描述所有可能的不确定性模型。当数据各元素的数量级相差很大时,按分量给出的界能更好地反映这种数据的特点。(netlib.org)

问题的条件性与数值稳定性

条件性是数学问题的性质;数值稳定性则是算法的性质。前向误差衡量计算结果与精确结果之间的差异。后向误差衡量需要将输入改变多少,才能使计算结果成为精确结果。后向稳定的方法所产生的结果,是某个邻近问题的精确解。(cs.cornell.edu)

当误差较小时,核心关系可概括为

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

因此,即使计算过程是后向稳定的,在求解病态问题时仍可能产生很大的前向误差。在浮点运算中,舍入会带来后向误差,而问题的条件性决定了这种误差可能被放大到何种程度。这是两种不同的影响,需要分别分析。(cs.cornell.edu)

对于计算得到的解 (\widehat{x}),残差 (r=b-A\widehat{x}) 衡量它未能满足方程的程度。仅有小残差并不能保证解的误差也小:要将残差信息转化为前向误差界,还需要有关条件性的信息。(netlib.org)

最小二乘与估计

对于满列秩的矩形矩阵,即矩阵的秩等于其列数的情形,相应的量为

[ \kappa_2(A)=|A|_2|A^\dagger|_2, ]

其中 (A^\dagger) 是摩尔—彭罗斯伪逆。在普通最小二乘法问题中,列向量若接近失去线性无关性,就可能使拟合系数对扰动高度敏感。不过,敏感程度还取决于残差以及 (b) 相对于矩阵列空间的位置;仅靠矩阵条件数无法完整描述这一情况。正则化通过改变拟合问题,对原本难以确定的解施加约束。(cs.cornell.edu)

实践中常采用条件数估计,而不是显式计算逆矩阵。LAPACK 的误差估计例程通常返回 RCOND,即条件数倒数的估计值。当问题极度病态时,使用倒数可以避免溢出;接近零的值表明,在所选范数下估计的敏感程度很高。(netlib.org)