高斯–若尔当消元法是线性代数中的一种算法,通过初等行变换将矩阵化为简化行阶梯形。它可用于求解线性方程组、计算逆矩阵、确定秩以及描述解空间。通常的高斯消元法一般先消去每个主元下方的元素,再进行回代;高斯–若尔当消元法则同时消去每个主元上方和下方的元素,使变量之间的最终关系可以直接读出。
初等行变换
该方法使用三种可逆的变换:
- 交换两行。
- 将某一行乘以一个非零标量。
- 将某一行的标量倍加到另一行上。
对于写成
的线性方程组,这些变换作用于整个增广矩阵
每种变换都会改变方程的形式,但不会改变它们的公共解集。例如,将一个方程替换为它自身与另一个方程的某个倍数之和后,只需减去同样的倍数即可还原。
该算法适用于任意域(数学),包括实数域、复数域、有理数域和有限域。关键要求是每个非零主元都有乘法逆元。在一般的环(数学)中,非零元素未必可逆,因此不一定能采用同样的步骤。
简化行阶梯形
一个矩阵满足以下条件时,称其为简化行阶梯形矩阵:
- 所有零行都位于所有非零行的下方。
- 每个非零行的第一个非零元素都是 ,称为首项 或主元。
- 每个主元都严格位于上一行主元的右侧。
- 主元是其所在列中唯一的非零元素。
例如,
是简化行阶梯形矩阵。它的主元列为第一列、第二列和第四列。
域上的每个矩阵都有唯一的简化行阶梯形。因此,不同的合法行变换可能产生不同的中间矩阵,但在精确运算中,最终得到的矩阵相同。普通的行阶梯形既不要求主元上方的元素为零,也不要求主元为一,因此并不唯一。
算法
一种直接实现的高斯–若尔当消元算法从左到右逐列处理,同时记录当前主元行的位置。
- 寻找主元。 在当前列中,从当前主元行开始向下寻找非零元素。如果找不到,就跳过这一列。
- 将主元移到适当位置。 必要时交换两行。
- 将主元行归一化。 将整行除以主元。
- 消去主元列中的其他元素。 对其余每一行,减去归一化后的主元行乘以该行在主元列中的元素。
- 继续推进。 移到下一行,并在后续各列中继续寻找主元。
如果 是第 列归一化后的主元行,则消元步骤为
由于新的主元行在此前各主元列中的元素均为零,因此这些主元列保持不变。当所有列都已处理完毕,或已无可用的后续主元行时,算法结束。
另一种实现方式是先通过前向消元得到行阶梯形,再从下向上依次将主元归一化,并消去主元上方的元素。在精确运算中,这两种方式得到的简化形式相同。
求解方程组时,可以只在系数列中寻找主元。此时,如果剩余某一行的系数全为零,而增广项非零,就说明方程组无解。如果目标是得到整个增广矩阵的简化行阶梯形,则还需处理增广列。
计算示例
考虑方程组
其增广矩阵为
施行 和 ,得到:
第二个主元已经是 。利用 和 消去该列中的其他元素,得到:
最后,将第三行除以 ,再消去其主元上方的元素,得到:
因此,解为
读出解集
对于有 个未知数的方程组,行化简可以区分以下三种情况。
无解
形如
的行表示不可能成立的方程 。
等价地,方程组有解当且仅当
其中矩阵的秩等于主元的个数。
唯一解
有解的方程组具有唯一解,当且仅当每个变量列都含有主元:
此时没有自由变量。
自由变量
如果一个有解方程组的秩为 ,则它有 个自由变量。例如,
给出
在实数域或复数域上,这表示有无穷多个解。而在有 个元素的有限域上,一个有解且具有 个自由变量的方程组恰有 个解。
更一般地,有解方程组的解集是一个仿射空间:
逆矩阵与子空间
计算逆矩阵
对于一个 方阵,将单位矩阵附加在 的右侧,得到增广矩阵:
如果 可逆,高斯–若尔当消元法会得到
将 化为 的那些行变换,也会将单位矩阵化为逆矩阵。如果左侧矩阵块无法化为 ,则 是奇异矩阵。
类似地,具有相同系数矩阵的多个方程组可以合并处理。当 可逆时,有:
求基
行化简还可提供基本子空间的相关信息:
- 化简后矩阵的非零行构成原矩阵行空间的一组基。
- 根据主元列的列号选取原矩阵中的对应列,这些列构成其列空间的一组基。
- 依次将每个自由变量设为 ,同时将其余自由变量设为 ,即可得到齐次方程组零空间的一组基。
必须区分原矩阵的列与化简后矩阵的列:行变换保留列之间的线性相关关系,但通常会改变列空间本身。
计算成本与数值局限
对于稠密的 矩阵,标准高斯–若尔当消元法需要 次算术运算,这里使用的是大O记号。存储该矩阵需要 个存储单元。这些只是算术运算层面的估算;在精确有理数计算中,分子和分母的增长还可能带来可观的额外成本。
求解单个非奇异方程组时,高斯消元结合回代通常需要更少的算术运算。在实际的数值线性代数中,通常采用LU分解,尤其是在同一个系数矩阵对应多个右端项时。求解这类方程组一般无需显式计算逆矩阵。
采用浮点运算时,极小的主元可能放大舍入误差。部分选主元法会在当前列的可用元素中选取绝对值最大的元素,并通过换行将其移到主元位置。这样可以避免除以该列中不必要的小元素,但不能消除所有可能的数值误差来源。
必须区分数值稳定性与问题的条件性。对于病态方程组,即使计算方法稳定,输入的微小变化也可能使解发生很大变化;这种敏感性由其条件数描述。
数值计算中确定矩阵的秩也面临类似困难。计算所得的某个元素接近零,可能只是舍入误差所致,而非存在精确的代数相关关系。因此,判零容差需要根据数值尺度和精度来确定。对于难以判定秩的情况,采用奇异值分解或具有秩揭示能力的QR分解,通常比简单地统计高斯–若尔当消元中看似非零的主元更合适。
对于稀疏矩阵,消元可能使原本为零的位置出现非零元素,这种现象称为填充。因此,同时消去主元上方和下方的元素,不仅可能增加算术运算量,还可能带来较大的存储开销。
名称的历史渊源
这一名称结合了卡尔·弗里德里希·高斯和威廉·若尔当的姓氏。高斯的名字与消元方法密切相关;若尔当则是德国大地测量学家,曾在十九世纪描述过一种相关的消元过程。这里的若尔当并非法国数学家卡米耶·若尔当。
通过消去未知数求解的基本思想,远早于这两位冠名者。在现代术语中,高斯消元法通常止于行阶梯形或三角形,而高斯–若尔当消元法则继续化简,直至得到简化行阶梯形。