消元是一连串可逆的方程变换。LU 分解将变换整理成因子,在右端改变时可重用。主元交换增加了一个细节:计算中途方程的次序可能改变。置换要记录完整次序,已记录的乘数则要随它们所描述的行移动。我们将在精确算术下证明非奇异方阵的分解存在,解释记录方式,并确定因子何时唯一。
我们需要的分解
定理 4.2.1
(带置换的 LU 分解)
设 是域 上的非奇异矩阵,。则存在置换矩阵 、单位下三角矩阵 和上三角矩阵 ,使
定义 4.2.2
(单位下三角与置换矩阵的约定)
“单位”指 的对角项全为 1。对非奇异的 , 的对角项均非零。置换矩阵左乘时重新排列各行。若依时间次序的换行是 ,则 :最后做的操作放在最左边。我们一律使用此约定。有些书以另一个置换写成 ,应先核对其约定,而非猜测是否要转置。
反例模式
没有 LU 分解的可逆矩阵
断言:每个非奇异矩阵都可写成 ,其中 是单位下三角、 是上三角。这是假的。非奇异性对非零主元结论及三角方程求解很重要。奇异矩阵也可能有这种形式的分解,但零主元和非唯一性需要另行处理。即使非奇异,也不保证无须换行: 可逆,但第一主元为零。若不换行,它不可能是单位下三角 与上三角 的乘积: 的第一项必为零,因而 的左下项也为零。
为何能找到非零主元
证明
(每一步都有非零主元)
在第 步开始时,假设第 列的对角线下方已消成零,先前主元均非零。目前矩阵可分块写成
其中 是可逆的 上三角矩阵。先前所有操作均可逆,故目前矩阵仍非奇异。其行列式为 ,因此右下块 非奇异。 的第一列不可能全为零,所以第 列在第 行或其下有非零项;可在这些行之间换行,把它移到主元位置。
对实矩阵,部分选主元法在该列尚可选取的项中选绝对值最大者。上述论证保证所选项非零,且所得乘数的绝对值至多为 1。存在性证明只需要选非零项;它并没有声称部分选主元能消除所有数值困难。选好主元后,从下方各行减去适当倍数的主元行。主元行在较早各列的项为零,故这些操作保持先前的零。经过 步得到上三角矩阵,且主元全非零。最后一步也包括在内:其右下块是非零标量。
记录方式背后的不变式
证明
(在换行与消元中维持 )
在第 步开始时,保持 ,其中 的首 个主元下方已消成零,而
右下角单位矩阵表示这些行在目前主元列的乘数尚未记录。起初 、。假设置换 交换第 行或其下的两行;相对于已处理的行,它可写为 。因此
新因子 仍是相同形状的单位下三角矩阵:已记录的左下块变成 ,右下恒等块则保持不变。所以必须交换 中先前已计算各列的对应行,而尚未处理的对角线上的 1 要留在原位。只交换目前 的行而不移动旧乘数,会破坏不变式。
令 ,其中向量 在第 个位置为零,下方各项是新乘数。消元后矩阵为 。由于 ,有 。因此
乘积 仍是单位下三角矩阵,并把新乘数存入第 列。这逐步证明了不变式,也解释旧乘数为何要移动:它们属于已换位置的方程,而不是固定附在原矩阵行号上。
证明透视
为何旧乘数必须跟着移动
不变式就是整个证明:每一步都必须令 保持成立。关键一步是把换行 写成 :用 对 作共轭,会把已处理各列中存储的乘数连同它们所属的行一起交换,而尾部的单位块仍是单位矩阵;若只更新 ,等式便会被破坏。非零主元来自尾部块 的非奇异性,这是对 的假设起作用之处。消元因子 无害,因为 ,乘上它只是把新乘数写进第 列。过程在 步后完结,因为最后的尾部块是一个非零标量。
唯一性究竟说什么
定理 4.2.3
(固定置换时的唯一性)
对固定的置换矩阵 ,若 非奇异,且 ,其中 为单位下三角、 为上三角,则 且 。
证明
(既是单位下三角又是上三角的矩阵)
对固定的置换 ,假设 ,其中 均为单位下三角, 均为上三角。因 和 可逆, 亦可逆。重排得
左边是单位下三角,右边是上三角。同时具有两种形状的矩阵必为对角矩阵,而其对角项都必为 1,所以它是 ,即 、。这并不表示置换唯一:不同有效选主元方式可能得到不同 ,进而得到不同因子。若移除 的单位对角规范,即使固定 ,仍可对两因子作相反的对角缩放。
这个论证亦解释非零主元的作用。对非奇异的分解,,因此 每个对角项均非零。若 奇异,唯一性证明所需的逆可能不存在,不能不加新假设便沿用结论。
把分解读成一连串步骤
等式 可以从两个方向理解。由 开始,先重新排列行得到 ,再通过消元得到 。反方向看, 重建被消去的线性组合,使 还原重新排列后的各行。 或 本身通常都不是 的行置换;乘积次序很重要。
行列式可提供简洁的额外检查。由 ,得 ,而 是对角项的乘积。每次换行改变 的符号,却不改变 是否奇异。此检查不能取代矩阵乘积:两个错误因子也可能碰巧有正确的行列式。同样,某个数值例子的选主元方式不能决定所有输入矩阵的通用置换;置换记录的是实际进行的操作。
概念视角算法
分解是对 Schur 补的递归
以 表示经过一次交换、使主元 之后的 ,并分块 。则
由于 ,Schur 补 非奇异,同一步骤可再用于它。乘数 构成 的第一列, 是 的第一行。之后在 内的换行会置换这些已记录的乘数,正如不变式所要求。
换行后如何求解
由 ,方程 等价于 。先用前代求 ,再用回代求 。重排 的同一个 必须用来重排 。由于 是单位下三角, 的对角项非零,两个三角方程都有唯一解。若有多个右端,只需分解一次,然后对每个新右端依次置换和求解。
检查应回到原问题:验证 ,再计算 。只检查 虽有帮助,但若没有核对 是否与实际换行一致,一个始终记错的置换仍可能被掩盖。在精确算术中零残差可验证数值解;在浮点算术中,小残差的意义需要进一步分析。
例题
例题 4.2.4
(已存乘数之后才换行)
在 上,对
求分解并解 。
解答。 取第一项 2 为主元。第 2、3 行的乘数为 2、3;相减后分别得 、。第二主元为零,故交换第 2、3 行。它们已存的第一列乘数也须交换,变成 3、2。新第二主元下方的项为零,故最后乘数为零。得到
的各行依次是 、、,正是 。又 ,前代得 。回代得 、、。最后 。若旧乘数 2、3 留在原位置, 的第二、三行便不等于 的相应行。
下面的互动图逐步重放消元,并在每个操作后重新计算 P、L、U 与 PA − LU,让你看到只有已记录的乘数随所属的行一起移动时,不变式才能在每次换行后保持成立。
例题 4.2.5
(必须交换的第一主元)
在 上,设 、。求有主元交换的分解并解方程。
解答。 虽然 ,第一主元却是零。交换第 1、2 行:
此处 ,置换后右端为 。因 ,所以 ;回代给出 及 ,故 。直接相乘得到 。另一个非奇异矩阵可能有多个有效主元选择,但对此固定 和单位对角规范,上述论证保证因子唯一。
例题 4.2.6
(部分选主元取绝对值最大的元素)
令 、。第一列中绝对值最大的元素是 ,所以交换两行:,。乘数是 ,其绝对值不超过一;第二行变成 。因此 、, 的两行是 与 ,所以 。取 ,前代得 ,回代得 ,再由 得 。验算:。
常见错误与细节
常见错误
(只交换 的行而不交换已存的乘数)
在第一个例题中,若把乘数 与 留在原位,则 ,而 的各行为 、、。后两行都不等于 的对应行 与 。
常见错误
(忘记对右端项作置换)
在第二个例题中,若用未置换的 解 ,得 ,再得 。但 ,不是 :这相当于把方程的次序弄错了来解。
习题
快速检查
(利用第一个例题中的分解,求 。)
记得 ,且 只是一次换行。
解答 · 答案
,而一次换行的 ,所以 。沿第一行直接作余因子展开得 。
快速检查
(对 与 ,求 、、 并解 。)
第一主元为零,所以交换两行。
解答 · 答案
,,。于是 ,故 ,由 得 。验算:。
快速检查
(为什么没有单位下三角的 与上三角的 能满足 ?)
先比较左上角的元素。
解答 · 答案
的 元素是 ,所以 。 元素是 ,但它必须等于 。这个矛盾正是需要换行的原因。