看似安全的主元并非全部
高斯(Gauss)消元法把方程组化为三角形式。在精确算术中这是等价变换,但计算机运算会舍入;中间数值的大小会影响舍入的作用。部分选主元在目前的列中选绝对值最大的元素作主元,并把其所在行交换至主元位置。这控制了消去乘数,却不能保证后续所有元素都小。另一方面,残差小本身亦不能保证近似解的误差小;这是另一个问题。
本文设 非奇异,。讨论误差时,向量用欧氏(Euclidean)范数,矩阵用其诱导范数。除非特别说明,以下消去及残差等式均在精确算术下成立。
乘数与中间数值增长
第 步选主元并交换行后,以 表示当前元素,并做更新
初始矩阵记作 ;公式右侧的第 步元素是交换行之后的值。非奇异性保证每一步有非零主元:否则剩余子矩阵的主元列全为零,它便是奇异的,原矩阵亦随之奇异。由主元的选法,。若出现并列,可按指定规则选行。
定义 1.4.1
(增长因子)
令 。消去过程的增长因子 ,是所有活动子矩阵 (,包括原矩阵)中元素的最大绝对值除以 。特别地,。
只用乘数的界,就可以估计增长因子。
命题 1.4.2
(最坏情况的增长上界)
对非奇异 ,精确算术下的部分选主元高斯消元法的增长因子满足 。
证明
(每一步至多使最大元素加倍)
设 是第 步开始时活动子矩阵中最大的绝对值,故 。交换行不改变它;对每个更新的元素,三角不等式及 给出
故 ,归纳得 。最多有 次更新;已放进 的元素也曾是较早步骤的活动元素,因而同样受此界限制。这是最坏情况上界,并非说每个矩阵都达到它。
证明透视
因子二从哪里来?
证明只追踪一个数,即活动元素的最大绝对值 ,并且只在一处用到部分选主元:,这是因为交换行后主元是该列中绝对值最大的元素。交换行本身无害,因为它只排列元素而不改变 。
关键一步是用两个旧元素 与 去界每个新元素,而两者都不超过 。没有任何东西迫使减法出现抵消,两个绝对值可以相加,因子二完全来自这里。每一步从活动子矩阵中去掉一行一列,而 的每个元素在被固定时都曾是活动元素,所以归纳经过 步后完成。论证从未利用抵消,因此只有特殊矩阵才会达到此界;下面的三阶例子恰好达到。
一个完整的增长例子
例题 1.4.3
(三阶方程组的主元增长)
出现并列时选最先出现的行。取
第一列三个元素的绝对值都是一,故不交换行,两个乘数都是 。把第一行分别加到第二、三行,得
第二步又出现并列;将第二行加到第三行,得到
原矩阵最大绝对值为 ,过程中最大值为 ,所以 。 的对角元素非零,也证明矩阵非奇异。乘数有界并没有阻止增长。
例题 1.4.4
(舍入算术中为何需要交换行)
解 ,其精确解为 、。采用把每个结果舍入到三位有效数字的十进制算术。
不交换行时,乘数为 ,第二个方程变成 。 与 都舍入为 ,所以 ,再得 。增长因子是 ,计算得到的 完全错误。
采用部分选主元时,两行先交换,乘数为 。新的第二个方程是 ;两边都舍入为 ,所以 ,。两个分量在所保留的位数内都正确,而 。这里不交换行的消去是合法的,因为首元素非零;失败来自巨大的中间元素与舍入的结合。
常见错误
(忘记对右端项作置换)
部分选主元分解的是 ,而不是 ,所以前代必须使用 。取 、,交换行后 、。用 求得 ,它满足 。若改为解 ,得到 ,而 。
残差、后向误差与前向误差
对近似解 ,令 ;真解 的前向误差为 。由 和非奇异性,。因此,绝对残差给出的绝对误差上界还需乘上 。除以 与 的大小,就得到相对形式。
命题 1.4.5
(相对前向误差的残差界)
若 ,则 ,而且
证明
(两个范数不等式)
由 得 。由 得 ,所以 且 。两个不等式相乘即得所求上界。
条件数大会使此上界不精细;它并不意味着每个右端向量都必定造成大误差。
例题 1.4.6
(条件良好而残差非零的系统)
设 、 和 。则 ,。相对前向误差为 ,相对残差则为 。由于 ,上界给出 。这里残差虽然非零,但条件数不大,使上界具有参考价值。两个相对量使用不同分母,不一定相等。
另一个有用的解读是:残差度量 需要改变多少,才能使 成为精确解。
命题 1.4.7
(矩阵扰动的后向误差)
设 ,只扰动 而固定 。则
并且最小值由 达到。
证明
(由秩一矩阵达到的下界)
约束条件就是 ,因此 ,即 。秩一矩阵 满足 ;对每个 ,由 Cauchy–Schwarz 不等式,,在 时取等号。所以其范数恰为 ;再除以 即得公式。
这是只允许扰动 的后向误差;它不允许同时扰动 ,数值上也不同于相对残差。
常见错误
(相对残差不是后向误差)
与 只在 时相等。在上面条件良好的例子中,;而 、,后向误差约为 。报告时要说明指的是哪一个;两者都不是前向误差。
反例模式
残差小可以掩盖大误差
取 、,则 。若 ,残差是 ,但相对前向误差为 。此问题病态:。小残差说明它是相近问题的精确解,并不自动确保它准确解出原问题。
浮点运算中,残差本身也可能经过舍入,消去过程的增长可能放大所造成的扰动。上述精确上界只谈中间元素,并非完整的浮点后向稳定性定理。可靠的数值判断还须考虑精度、所计算的残差和条件数估计。
练习与解答
快速检查
(对 作部分选主元消去。写出行交换、 和增长因子。)
选主元前先看第一列。
解答 · 答案
第一列是 ,部分选主元交换第一、二行,得 。乘数为 ,所以 。最大绝对值始终为 ,故 。
快速检查
(设 ,其中 ,,。求相对残差及相对前向误差,并讨论 的情形。)
真解可以直接读出。
解答 · 答案
残差为 ,真解为 。相对残差为 ,相对前向误差为 。前者趋于零,后者保持不变,这与 一致。
快速检查
(设 、、。求使 成为精确解的最小谱范数扰动,并求其相对范数。)
使用后向误差命题中的秩一矩阵。
解答 · 答案
此时 。秩一构造给出 ,它把 映到 。其谱范数为 ,而 ;上述命题证明它最小。真解为 ,故相对前向误差为 ,不同于相对后向误差 :两者衡量不同对象的变化,分母也不同。