为什么利用矩阵的结构?
在方程组 中,三对角矩阵只把每个未知数与相邻的未知数联系起来。例如自然三次样条的曲率方程便有这个结构。一般消元法仍然适用,但存储全部 个元素会掩盖其特点:在精确算术下,消去一行只会改动下一行。因此只需存储和处理三条对角线。
用 表示第 行的下对角元素(), 表示对角元素, 表示上对角元素()。方程为
首行及末行不存在的项应省略。以下假设 。推导使用精确算术;主元非零只保证公式有意义,并不自动保证浮点运算准确。
逐个消去相邻未知数
令 、。对 ,只要 ,便定义
变换后第 行是 ,末行没有上对角项。若每个 均非零,回代得到
每步只需固定数目的算术运算。若矩阵不变而右端改变,可保留乘数与主元,只重新计算 并回代。下面的命题把变换后各行的形状与运算次数说得精确。
命题 3.3.1
(消元不会离开三条对角线)
设 为三对角矩阵,且 均非零。依次处理第 行后,变换后方程组的第 行为 (末行没有 项),而且三条对角线以外没有元素变成非零。若再有 ,则分解、前向扫描与回代合计恰好需要 次算术运算,数据只占 存储空间。
证明
(对已处理的行作归纳)
当 时,结论就是首个方程,其中 、。假设结论对第 行成立。该行只在第 列含有 ,而尚未改动的第 行在第 列含有 。从第 行减去第 行的 倍,消去第 列的元素,把 换成 、把 换成 ;第 列不受影响,因为第 行在该列没有元素。其他各行均未改动。由此第 行具有所述形状,而且从不产生带外元素。
至于运算次数: 个消元步骤中,每步用一次除法求 ,用一次乘法和一次减法求 ,求 也一样,共五次运算。回代求 用一次除法,其余 个未知数各用一次乘法、一次减法和一次除法。总数为 。需要存储的只有向量 及算出的 。
同一计算也可以看成矩阵分解;软件正是以这种形式存储它。
概念视角结构
消元即两个双对角矩阵的乘积
设 为单位下双对角矩阵,下对角元素为 ;设 为上双对角矩阵,对角元素为 ,上对角元素为 。展开乘积得
所以 。求 的前向扫描正是解 ,回代则是解 。因此对新右端重用分解,就是解两个双对角方程组;又因 ,有 。
定理 3.3.2
(主元何时存在?)
设 为左上角 主子矩阵,,。若 均非零,则直到 的消元主元均有定义,且 。若再有 ,所有主元均非零,算法给出唯一解。实对称正定矩阵必定满足这些条件。
证明
(行列式递推与继承的正定性)
沿三对角行列式的末行展开,对 有 ,而 。除以 后由归纳法得 。主元非零时,行运算可逆,而最后的三角系统有唯一解。若 对称正定,每个 也正定:把 的非零向量补零后运用正定的定义。由谱定理,每个 的行列式为正,因此所有主元均存在且为正。
证明透视
每个行列式假设用在哪里
关键一步是看出主元递推与行列式递推是同一个三项关系:若 ,则
假设 只用了一次:使 非零,从而第 步可以除以它。因此分解需要的是 ,而 只在回代的第一个除法 中用到。各式相乘后逐项相消,得 。在正定的情形,唯一额外的想法是:把二次型限制在只有前 个坐标非零的向量上,就得到 的二次型,所以每个左上角子块同时继承了正定性。
对称性提供更多结构。令 ,设 的对角线为一、下对角线为 。当之前的主元均非零,且 时,递推式等价于
若矩阵对称正定,所有 。因此也可写成 ,其中下双对角矩阵 。主元为正是由正定性证明的性质;对一般对称矩阵不能先行假设。
完整算例
例题 3.3.3
(三个相互耦合的未知数)
求解
主元为 、、。乘数为 、,所以 、、。回代得 、、。直接相乘可验证 。
矩阵正定,因为对非零 ,
所以计算前已知主元必为正。若换一个 ,三个主元和两个乘数可重用:它们只取决于 。
例题 3.3.4
(同一矩阵的 因子)
上例的矩阵是对称的,。由乘数得 、,由主元得 。逐个元素展开 :
结果正是 。再作检查:,与左上角主子行列式 、、 及 一致。
例题 3.3.5
(边界情形:主元都有定义,但末主元为零)
取 。这里 ,定理说 有定义;事实上 、。分解 存在,其中 、,但回代在第一步 就失败。若 ,变换后末方程为 ,有无穷多个解;若 ,末方程为 ,无解。定理中的条件 正是用来排除这种情形。
结构不能保证什么?
反例模式
非奇异矩阵的首个主元也可能为零
三对角矩阵 的行列式为 ,因此任何右端均有唯一解;然而 ,上述递推无法开始。交换两行可以继续消元。在更大的三对角系统中,行选主元可能造成额外填入,必须用能处理填入的算法。非奇异本身不足以保证不选主元的消元法可行。
常见错误
(对称不等于主元为正)
递推式 看似会使主元保持为正,其实不然。对 ,得 、。分解 存在,但 有负元素,所以 及双对角因子 都不是实矩阵。主元为正以及 都由正定性推出,而正定性必须另行验证。
即使所有精确主元存在,极小主元仍可能放大舍入误差。正定性保证精确算术中主元不为零,却不保证条件数小。例如 在 时正定,但当 ,其二范数条件数为 。因此解读小残差时,最好同时考虑条件数。线性成本只说明运算量,不是准确度证明;溢出、下溢、输入误差和算术舍入仍须考虑。
练习与解答
快速检查
(对角线为 ,上下对角线均为 。求 主元,并不只依赖计算结果解释它们为什么为正。)
把二次型写成平方和。
解答 · 答案
、、。二次型等于 ,非零 时为正。正定性因此保证主元为正。
快速检查
(重用第一个算例中的分解,改以 求解。)
只需重做求 的前向扫描和回代。
解答 · 答案
由 、,新变换右端为 。回代得 、、。与 相乘可得 。
快速检查
(有学生认为每个非奇异三对角矩阵的左上角主子行列式均非零。指出错误,并说明以上哪个更强的条件足够。)
参看上一节的反例。
解答 · 答案
反例中的交换矩阵行列式是 ,但第一个主子行列式为零。非奇异只说明 。对称正定则足够,因为每个左上角主子矩阵也正定,行列式为正。