这里我们将详细阐述如何利用条件数来获得误差界限。为简化讨论,假设我们仅尝试计算一个标量函数 f(x) ,使用算法 alg(x) ,并希望限定误差 alg(x) - f(x) 。进一步假设存在某个“小”的 e 使得 alg(x) = f(x+e) 。如果算法具有特性:对于略微扰动的参数 x+e 能准确得到 f(x+e) ,那么该算法被称为数值稳定,或简称为稳定。在这种情况下,我们可以如下估计误差:
同样的思路也适用于求解特征值问题的误差界限。在这种情况下, x 是一个矩阵, x+e 是扰动后的矩阵,而 f(x+e) 可能是一个特征值、一组特征值、一组特征值/特征向量对或其他量。此外, \vert e\vert 将被矩阵 e 的范数所替代。
因此,要获得误差界限,我们需要一个条件数和一个后向误差 e 的界限。有两种方法来获得 e 的界限。第一种方法是证明算法 alg(x) 始终 具有小的后向误差 e 。对于本书中讨论的变换方法,这是成立的,后向误差矩阵 e 的范数大致被机器精度 \epsilon_M 乘以输入矩阵 x 的范数所限定。这种保证的稳定性不适用于迭代方法。
对于迭代方法,情况更为复杂。这里简要概述,详细内容留待第 4 章至第 9 章。假设 \mu 和单位向量 x 形成一个近似的特征值和特征向量对,即残差向量 Ax - \mu x \equiv r 很小。那么容易证明,使得 (A+E)x = \mu x 成立的最小矩阵 E 为 E = -r x^* ,其范数为 \Vert E\Vert _2 = \Vert r\Vert _2 。因此,要限定后向误差,我们只需计算残差的2-范数 \Vert r\Vert _2 = \Vert Ax - \mu x\Vert _2 。对于单个特征值和特征向量对,限定后向误差非常简单。但对于一组特征值/特征向量对 A x_i \approx \mu_i x_i , i=1,\ldots,m ,情况更为复杂。即使每个 A x_i - \mu_i x_i 都很小,这并不意味着 \mu_i,x_i 是 m 个不同特征对的近似(某些可能近似于同一个真实特征对),或特征向量在应该是正交时是正交的(当 A 是厄米矩阵时),或其他期望的性质。某些迭代方法比其他方法能更有效地保证这些性质(例如,参见第4.5节和第7.6节中描述的隐式重启的Lanczos和Arnoldi方法)。
读者可参考Golub和Van Loan的教材[198]以及Demmel的教材[114]作为数值稳定性的入门学习。Higham的教材[228]和Stewart与Sun的教材[425]则是深入研究线性方程组和特征值问题数值稳定性与条件数的优秀资源。