下一节:直接平衡法 上一级:非厄米特特征值问题 上一节:引言

平衡矩阵
  T. Chen and J. Demmel

计算非对称矩阵 A 特征值的数值算法通常会产生大小约为 \epsilon_M\Vert A\Vert 的舍入误差,其中 \epsilon_M 是机器精度。 因此,应用一个简单且准确的相似变换
DAD^{-1} 来减小矩阵 A 的范数,或者减小 A 某些特征值的条件数, 可以使计算出的 A 的特征值更加精确。

例如,考虑矩阵

A = \left[ \begin{array}{ccc}1&0&10^{-4}\\ 1&1&10^{-2}\\ 10^4&10^2&1 \end{array} \right].
选择 D = \mathrm{diag}(100, 1, .01) 得到
B=DAD^{-1}=\left[\begin{array}{ccc}1&0&1\\ 10^{-2}&1&1\\ 1&1&1\end{array}\right].
\vert\vert A\vert\vert _F 大约为 10^4\vert\vert B\vert\vert _F 大约为 2.6。 此外,B 的特征值的条件数都大约为 1,而 A 的特征值的条件数大小范围从 10^110^3

奥斯本(Osborne) [346] 首先注意到,矩阵 A 的范数通常可以通过以下形式的相似变换来减小

B=DAD^{-1}, \tag{7.4}
其中 D 是一个对角矩阵。 奥斯本在考虑不可约矩阵并忽略其对角元素的情况下,还证明了使 \vert\vert B\vert\vert _F 最小的 D 也在 2-范数下平衡了 B:如果对于任何 i,行 i\alpha-范数与列 i\alpha-范数相同,则矩阵在 \alpha-范数下是平衡的。 他引入了第一个平衡算法,该算法反复遍历 D 的对角线元素,更新 D_{ii} 以平衡第 i 行和第 i 列。

尽管在 2-范数下平衡等价于最小化 Frobenius 范数,但在任意范数下平衡矩阵对矩阵范数的影响可能没有这么简单。 其他工作讨论了使用对角缩放来平衡矩阵和最小化矩阵范数的数学性质 [81,82]。 我们在这里关注实践而非理论,介绍两种平衡稀疏矩阵的算法风格。 这些算法在 [81] 和 [82] 中有更彻底的分析; 软件可以通过本书的主页 ETHOME 访问。



小节

下一节:直接平衡法 上一级:非厄米特特征值问题 上一节:引言
Susan Blackford 2000-11-20