部分选主元避免除以当前列中比可用元素更小的数,这有助于控制乘子,但消元过程中的每次除法、乘法和减法也都会舍入。计算所得的因子究竟精确分解了什么?我们将证明它们精确分解了一个邻近的已置换矩阵,并说明中间元素增长如何进入误差界。这是关于因子分解的结论;求解三角方程组还会产生额外算术误差。
计算算法与假设
设 ,,其元素是已表示的浮点数。在第 列,部分选主元选择当前列中绝对值最大的活动行,将它与第 行交换,再进行更新
这里 是第 步行交换后的活动矩阵,。行交换是精确置换。交换行时,这些行此前存储的乘子也要交换;否则最终的 无法记录相同的行历史。令 为各次交换的乘积, 为得到的单位下三角乘子矩阵, 为计算所得主元行组成的上三角矩阵。
假设 (1) 中每次除法、乘法和减法都满足标准相对模型
且每个计算出的主元非零。排除溢出、下溢或特殊值使 (2) 失效的运算。我们分析实际舍入运行时的主元选择,而不是另一趟精确算术运行的主元。假设 ,记 。融合乘减并非 (1) 中分别舍入的算法。
定理 2.3.1
(邻近矩阵的因子分解)
存在实矩阵 ,使得
绝对值和不等号均逐元素理解,右侧为普通矩阵乘法。特别地,此界依赖计算所得因子,而不只依赖原始元素。这是对已置换输入矩阵的向后误差,尚不是对 最终解的误差界。
证明
(沿交换和舍入更新追踪一行)
对固定的最终行 ,沿精确交换向前追溯它的来源。在每次交换时,先前存储的乘子也随行交换,保证 对应同一条行历史。一旦第 行成为主元行,其计算元素 便被固定。因此可以追踪每个最终元素在该行成为主元之前的更新,而无需假设物理行号始终不变。
暂时省略指标,(1) 中一次更新具有形式
整理得 。同样,计算除法给出 。反复代入,可将 表示为 各项之和,每项乘上若干舍入因子。对于上三角元素,最终项是存储的 ,其中 ;对于对角线下方元素,最终项是计算出的乘子与主元之积,带一个除法舍入因子的倒数。先前的行交换已由 P 和 L 记录。
每项至多包含 个因子:其分子至多有一个乘积舍入因子 ,其余是先前减法或最终除法产生的倒数 。因此,其合并因子 满足
下界使用 ;上界使用 和 。因此,对非零的三角乘积项,可写 ,其中 。从 中减去此式,再用三角不等式即得 (3)。这里不假设舍入误差互相独立。
证明透视
舍入记账依赖什么
证明是带有两个容易忽略之约定的记账。第一,已存储的乘子与其所在的行一起交换,所以把最终的某一行沿交换逆向追踪时,总是遇到同一串 和 ;否则 (3) 比较的就是 与错误的行历史。第二,每一项至多带有 个舍入因子,乘积中至多一个 ,其余是倒数 ,所以单一常数 同时涵盖两个方向;假设 正是保证 为正的条件。论证没有把误差当作随机量,所以 (3) 是针对实际舍入后的主元选择的最坏情形保证。证明止于因子分解,并不涉及三角求解。
增长对估计的影响
定义 2.3.2
(增长因子)
令 。实际计算过程的增长因子 是所有计算出的活动矩阵或主元行中元素的最大绝对值除以 。
它是实际计算过程的性质,而不是精确算术的性质。
推论 2.3.3
(后向误差的增长因子形式)
在上述假设下,(3) 中的矩阵 满足
证明
(估计乘子与主元行)
部分选主元选择当前列绝对值最大的元素,所以每次除法中的精确商的绝对值不超过一,由 (2) 得 。由 的定义,每个 。 的每个元素是至多 个乘积之和,每个乘积至多为 ,于是由 (3) 得 (4)。
该界可能偏保守,而且增长依赖主元路径。它说明较大的中间元素为什么可能削弱误差保证;它不表示大增长一定造成大的实际误差。要把小向后误差转化为小向前误差,还需要问题本身有良好的条件性。
常见错误
(三种不同的误差不能混为一谈)
式 (3) 讨论计算所得因子对邻近矩阵的表示有多准确。计算三角方程组也会舍入,所以单凭 (3) 不能认证最终解。最后,即使精确求解了一个邻近系统,若原系统病态,其解仍可能与原解相差很大。因子分解误差、求解误差和问题敏感性是不同的问题。
例子与敏感性反例
例题 2.3.4
(精确算术下的行交换)
对 ,第一个主元为 2,所以
在二进制算术中这些运算精确,故 ;计算出的增长因子为 。定理给出上界,不表示每次运行都会达到它。
例题 2.3.5
(一个被舍入的乘子)
取 。第 列最大的元素是 ,所以 。计算出的乘子为 ,。乘积 是精确的,所以 ,。于是 。由于 且 ,
只有第二行被扰动。(3) 右端在 位置为 ,大于 ,所以该界成立且有余地。
例题 2.3.6
(部分选主元下的元素增长)
设 ,故 。第 列的元素绝对值都是 ,取第一个作主元。乘子为 ,活动矩阵变成 。其第一列的两个元素绝对值又都是 ;取第一个作主元,乘子为 ,最后一个元素变成 。因此 、。所有运算都精确,所以 ,但 (),(4) 比 时弱四倍。这个并列的情形说明绝对值相等的元素也可作主元,而且即使没有乘子的绝对值超过一,也可能出现很大的增长。
反例模式
后向误差很小而前向误差很大
一个诱人的说法是:后向误差很小就保证解准确。令 、,;精确解为 。向量 满足 ,所以它精确求解了一个数据与给定数据只相差一个随 趋于零的扰动的方程组。然而 ,相对前向误差为 。即使因子分解完全精确,也不能使一个接近奇异的问题变得不敏感;修正办法是把后向误差与条件数结合起来。此例讨论输入扰动;它并不声称 (3) 中的分解一定产生该扰动。
练习与解答
快速检查
(为什么后来的行交换必须连同此前存储的乘子一起进行?)
想想每一行的历史。
解答 · 答案
乘子属于前几列中的行历史。不交换它们会破坏最终置换与存储的 之间的对应关系。
快速检查
(式 (3) 的 和 有什么区别?)
把 (3) 左乘 。
解答 · 答案
扰动的是 ;将 (3) 左乘 ,可知 是 中对 的相应扰动。
快速检查
(若 ,算法做什么,因子分解误差是多少?)
数一数除法和更新。
解答 · 答案
没有除法或尾块更新:对已存储输入,、、。
快速检查
(仅有 是否保证每个右端项的计算解都准确?解释理由。)
回想三种误差。
解答 · 答案
不保证。(4) 可以界定因子分解误差,但三角求解也会舍入,系统还可能敏感;接近奇异的例子说明了求解舍入之前就有敏感性。