为什么要控制中间元素?
在开始解三角方程组之前,高斯(Gauss)消元法先改变矩阵。即使原矩阵的每个元素都不大,中间元素仍可能变得大得多。这种元素增长在浮点误差分析中很重要,因为中间运算会发生舍入。它不同于条件数:后者衡量数学问题本身对扰动的敏感程度。
先研究精确算术。设 非奇异。若有并列,可按任何指明的规则选取,下面的定义对每种规则都适用。
定义 2.2.1
(部分主元选取与增长因子)
在每一列,部分主元选取把当前行与剩余行中该列元素绝对值最大的行交换。令 ,并令 表示第 阶段换行之前尚未消去的活动矩阵。定义
其中最大值遍历所有阶段的活动元素,包括最后的 阶段。 称为这次消元的增长因子。
选出的主元非零:否则第 列的第 行均为零,前 列将属于前 个坐标向量张成的空间,从而线性相关。这与初等行变换保持的非奇异性矛盾。换行不改变元素绝对值的最大值。由于 非奇异, 且 。
一般上界
定理 2.2.2
(部分主元选取的增长界)
对每个非奇异的 和每种并列规则,在精确算术下做部分主元选取,都有
证明
(每个阶段至多使最大元素加倍)
在第 阶段,记选中的主元为 ,其列下方某个元素为 。部分主元选取保证 。剩余子矩阵的每个元素满足
其中 是消元之前活动元素绝对值的最大值。因此 。对 个消元阶段归纳,得到 ,所以每个阶段的每个活动元素的绝对值至多为 。
证明透视
因子二从何而来
非奇异性只用来保证每个阶段的主元非零,使商 有意义且 。选主元规则恰好用了一次,即给出 。关键一步是三角不等式,而不是抵消论证:新元素是 减去 的一个绝对值至多为一的倍数,两项的绝对值各自至多为 ,其差可以达到 。证明得以收尾,是因为无论并列规则如何,每个阶段都有 ,所以 个阶段给出 ;它并没有说明哪些阶段真的加倍。没有选主元规则,这类结论就不再成立:对 ,不选主元时乘数为 ,新元素为 ,当 时无界。
这个界是最坏情况的结论:并不是说所有矩阵每一步都会翻倍,也不是说最终答案的相对误差等于 倍机器精度。
达到上界的矩阵族
对于 ,定义 :对角线和最后一列填 ,前 列中严格位于对角线下方的元素填 ,前 列中对角线上方填 。例如,
命题 2.2.3
(增长达到最大的矩阵族)
对 做部分主元选取,并列规则为:当前行的主元绝对值若并列最大,就保留当前行。则不发生换行, 非奇异,并且 。
证明
(在保留当前行规则下消去 )
初始元素绝对值均不超过一。前 列的每一步中,主元为 、下方元素均为 ,所以乘数为 ,而该规则不换行。具体不变量是:第 阶段的活动矩阵等于把 的最后一列乘以 所得矩阵(约定 )。 时成立。主元行在主元与最后元素之间全为零,所以加到每个下方行时只改变最后一列:下方各行的最后元素 变为 ,这正是第 阶段的不变量。因此并列规则在每一步都适用。最后主元为 ,所以 非奇异;这个元素再结合增长界,便得 。
例题 2.2.4
(不换行地消去 )
第 1 阶段主元为 ,把第 1 行加到每个下方行,得到下方各行 、、。活动的 块为 ,即最后一列加倍的 。第 2 阶段把主元行加到下方两行,得到块 ;第 3 阶段再加一次,得到 。所得上三角矩阵为
由于 而最大的活动元素为 ,所以 。
例题 2.2.5
(对 采用另一种并列规则)
并列时选最下方的行。 的第 1 列所有元素绝对值都是一,所以第 1、3 行交换,得到 。乘数为 和 ,相应相减后得到 和 ,活动块为 。第 2 列的主元为 、乘数为 ,最后主元为 。最大的活动元素绝对值为 ,故这一规则给出 ,而不是 。因此这个矩阵族说明某个允许规则达到最坏情况,而不是每个并列规则都产生相同增长。
反例模式
乘数有界并不保证与维数无关的增长界
在指定的并列规则下, 的乘数全部为 ,其增长因子却为 。因此,控制每个乘数是有用的,但不会得到与维数无关的增长界。
不换行时的小主元
例题 2.2.6
(很小的首个元素)
对于 ,令
若不选主元,第一步乘数为 ,第二个主元为 ;当 时其绝对值无限增大。部分主元选取先交换两行,乘数变为 ,第二个主元变为 。此时所有活动元素的绝对值至多为一,所以 。这个例子说明选主元如何避免巨大的中间元素,但并不能证明选主元总能防止增长。
增长、条件性与计算
增长因子依赖消元路径和选主元规则;条件数依赖原矩阵及所选范数。任意一个数都不能单独决定前向误差。浮点后向误差界涉及舍入、维数、分解因子和中间数值的大小;前向误差还取决于问题的条件性。上面的精确算术计算只分离出其中一种机制,并不为特定实现声称通用的误差证书。
常见错误
(把增长因子当成计算解的误差)
界 比较的是精确消元中中间元素与原元素的大小。它并不表示计算出的解的相对误差是机器精度的 倍;舍入和原问题的条件性另有影响。
常见错误
(把增长因子当成只由矩阵决定的量)
同一个矩阵在不同的允许并列规则下可以有不同增长: 保留当前行时 ,并列时选最下方的行则 。给出 的数值时必须指明选主元规则。
练习与解答
练习 2.2.7
(对 按保留当前行的并列规则消元,求增长因子。)
基础
解答(3)
- 1
消去第 1 列
把第 1 行加到 的第 2、3 行,得到下方各行 和 。
依据: 主元为 ,两个下方元素均为 ,所以乘数为 ,不换行。
- 2
消去第 2 列
活动块为 ,主元为 ;把第 1 行加到第 2 行,最后位置得到 。
- 3
读出增长因子
而 ,所以 。
快速检查
(为什么部分主元选取保证乘数的绝对值至多为一?)
把每个下方元素与主元比较。
解答 · 答案
主元在活动列中的绝对值最大,因此每个下方元素都满足 ,而乘数为 。
快速检查
(在二维例子中取 ,比较换行和不换行时的第二个主元。)
计算 和 。
解答 · 答案
不换行时主元为 ;换行后为 。
快速检查
( 是否声称计算出的解具有相应的相对前向误差?)
回想 比较的是什么。
解答 · 答案
不。这个界控制精确消元中的中间大小相对于原元素的比例;舍入和原问题的条件性还需要另行分析。