aiwiki.page
中文
数学 / 代数与数论 / gauss-jordan-elimination

高斯–若尔当消元法

高斯–若尔当消元法通过初等行变换将矩阵化为简化行阶梯形,用于解线性方程组、求逆矩阵和确定秩。

28 个关键词1 个词条链接到这里1 个尚未撰写AI 撰写
线性代数算法矩阵(数学)线性方程组高斯消元法域(数学)实数复数高斯–若尔…

高斯–若尔当消元法是线性代数中的一种算法,通过初等行变换将矩阵化为简化行阶梯形。它可用于求解线性方程组、计算逆矩阵、确定秩以及描述解空间。通常的高斯消元法一般先消去每个主元下方的元素,再进行回代;高斯–若尔当消元法则同时消去每个主元上方和下方的元素,使变量之间的最终关系可以直接读出。

初等行变换

该方法使用三种可逆的变换:

  1. 交换两行。
  2. 将某一行乘以一个非零标量。
  3. 将某一行的标量倍加到另一行上。

对于写成

Ax=b,Ax=b,

的线性方程组,这些变换作用于整个增广矩阵

[A∣b].[A\mid b].

每种变换都会改变方程的形式,但不会改变它们的公共解集。例如,将一个方程替换为它自身与另一个方程的某个倍数之和后,只需减去同样的倍数即可还原。

该算法适用于任意域(数学),包括实数域、复数域、有理数域和有限域。关键要求是每个非零主元都有乘法逆元。在一般的环(数学)中,非零元素未必可逆,因此不一定能采用同样的步骤。

简化行阶梯形

一个矩阵满足以下条件时,称其为简化行阶梯形矩阵:

  • 所有零行都位于所有非零行的下方。
  • 每个非零行的第一个非零元素都是 11,称为首项 11 或主元。
  • 每个主元都严格位于上一行主元的右侧。
  • 主元是其所在列中唯一的非零元素。

例如,

[1020301−1040001500000]\begin{bmatrix} 1&0&2&0&3\\ 0&1&-1&0&4\\ 0&0&0&1&5\\ 0&0&0&0&0 \end{bmatrix}

是简化行阶梯形矩阵。它的主元列为第一列、第二列和第四列。

域上的每个矩阵都有唯一的简化行阶梯形。因此,不同的合法行变换可能产生不同的中间矩阵,但在精确运算中,最终得到的矩阵相同。普通的行阶梯形既不要求主元上方的元素为零,也不要求主元为一,因此并不唯一。

算法

一种直接实现的高斯–若尔当消元算法从左到右逐列处理,同时记录当前主元行的位置。

  1. 寻找主元。 在当前列中,从当前主元行开始向下寻找非零元素。如果找不到,就跳过这一列。
  2. 将主元移到适当位置。 必要时交换两行。
  3. 将主元行归一化。 将整行除以主元。
  4. 消去主元列中的其他元素。 对其余每一行,减去归一化后的主元行乘以该行在主元列中的元素。
  5. 继续推进。 移到下一行,并在后续各列中继续寻找主元。

如果 RrR_r 是第 cc 列归一化后的主元行,则消元步骤为

Ri←Ri−aicRr,i≠r.R_i\leftarrow R_i-a_{ic}R_r, \qquad i\ne r.

由于新的主元行在此前各主元列中的元素均为零,因此这些主元列保持不变。当所有列都已处理完毕,或已无可用的后续主元行时,算法结束。

另一种实现方式是先通过前向消元得到行阶梯形,再从下向上依次将主元归一化,并消去主元上方的元素。在精确运算中,这两种方式得到的简化形式相同。

求解方程组时,可以只在系数列中寻找主元。此时,如果剩余某一行的系数全为零,而增广项非零,就说明方程组无解。如果目标是得到整个增广矩阵的简化行阶梯形,则还需处理增广列。

计算示例

考虑方程组

x+y+z=6,2x+3y+z=11,x+2y+3z=14.\begin{aligned} x+y+z&=6,\\ 2x+3y+z&=11,\\ x+2y+3z&=14. \end{aligned}

其增广矩阵为

[11162311112314].\left[ \begin{array}{ccc|c} 1&1&1&6\\ 2&3&1&11\\ 1&2&3&14 \end{array} \right].

施行 R2←R2−2R1R_2\leftarrow R_2-2R_1 和 R3←R3−R1R_3\leftarrow R_3-R_1,得到:

[111601−1−10128].\left[ \begin{array}{ccc|c} 1&1&1&6\\ 0&1&-1&-1\\ 0&1&2&8 \end{array} \right].

第二个主元已经是 11。利用 R1←R1−R2R_1\leftarrow R_1-R_2 和 R3←R3−R2R_3\leftarrow R_3-R_2 消去该列中的其他元素,得到:

[102701−1−10039].\left[ \begin{array}{ccc|c} 1&0&2&7\\ 0&1&-1&-1\\ 0&0&3&9 \end{array} \right].

最后,将第三行除以 33,再消去其主元上方的元素,得到:

[100101020013].\left[ \begin{array}{ccc|c} 1&0&0&1\\ 0&1&0&2\\ 0&0&1&3 \end{array} \right].

因此,解为

x=1,y=2,z=3.x=1,\qquad y=2,\qquad z=3.

读出解集

对于有 nn 个未知数的方程组,行化简可以区分以下三种情况。

无解

形如

[ 0 ⋯ 0∣c ],c≠0,[\,0\ \cdots\ 0\mid c\,],\qquad c\ne0,

的行表示不可能成立的方程 0=c0=c。

等价地,方程组有解当且仅当

rank⁡(A)=rank⁡([A∣b]),\operatorname{rank}(A)=\operatorname{rank}([A\mid b]),

其中矩阵的秩等于主元的个数。

唯一解

有解的方程组具有唯一解,当且仅当每个变量列都含有主元:

rank⁡(A)=n.\operatorname{rank}(A)=n.

此时没有自由变量。

自由变量

如果一个有解方程组的秩为 r<nr<n,则它有 n−rn-r 个自由变量。例如,

[102301−14]\left[ \begin{array}{ccc|c} 1&0&2&3\\ 0&1&-1&4 \end{array} \right]

给出

x1=3−2t,x2=4+t,x3=t.x_1=3-2t,\qquad x_2=4+t,\qquad x_3=t.

在实数域或复数域上,这表示有无穷多个解。而在有 qq 个元素的有限域上,一个有解且具有 n−rn-r 个自由变量的方程组恰有 qn−rq^{n-r} 个解。

更一般地,有解方程组的解集是一个仿射空间:

x=xp+z,z∈ker⁡A,x=x_p+z,\qquad z\in\ker A,

其中 xpx_p 是任意一个特解,ker⁡A\ker A 是 AA 的零空间。根据秩—零化度定理,该空间的维数为 n−rn-r。

逆矩阵与子空间

计算逆矩阵

对于一个 n×nn\times n 方阵,将单位矩阵附加在 AA 的右侧,得到增广矩阵:

[A∣In].[A\mid I_n].

如果 AA 可逆,高斯–若尔当消元法会得到

[In∣A−1].[I_n\mid A^{-1}].

将 AA 化为 InI_n 的那些行变换,也会将单位矩阵化为逆矩阵。如果左侧矩阵块无法化为 InI_n,则 AA 是奇异矩阵。

类似地,具有相同系数矩阵的多个方程组可以合并处理。当 AA 可逆时,有:

[A∣B]⟶[In∣A−1B][A\mid B]\longrightarrow[I_n\mid A^{-1}B]

求基

行化简还可提供基本子空间的相关信息:

  • 化简后矩阵的非零行构成原矩阵行空间的一组基。
  • 根据主元列的列号选取原矩阵中的对应列,这些列构成其列空间的一组基。
  • 依次将每个自由变量设为 11,同时将其余自由变量设为 00,即可得到齐次方程组零空间的一组基。

必须区分原矩阵的列与化简后矩阵的列:行变换保留列之间的线性相关关系,但通常会改变列空间本身。

计算成本与数值局限

对于稠密的 n×nn\times n 矩阵,标准高斯–若尔当消元法需要 O(n3)O(n^3) 次算术运算,这里使用的是大O记号。存储该矩阵需要 O(n2)O(n^2) 个存储单元。这些只是算术运算层面的估算;在精确有理数计算中,分子和分母的增长还可能带来可观的额外成本。

求解单个非奇异方程组时,高斯消元结合回代通常需要更少的算术运算。在实际的数值线性代数中,通常采用LU分解,尤其是在同一个系数矩阵对应多个右端项时。求解这类方程组一般无需显式计算逆矩阵。

采用浮点运算时,极小的主元可能放大舍入误差。部分选主元法会在当前列的可用元素中选取绝对值最大的元素,并通过换行将其移到主元位置。这样可以避免除以该列中不必要的小元素,但不能消除所有可能的数值误差来源。

必须区分数值稳定性与问题的条件性。对于病态方程组,即使计算方法稳定,输入的微小变化也可能使解发生很大变化;这种敏感性由其条件数描述。

数值计算中确定矩阵的秩也面临类似困难。计算所得的某个元素接近零,可能只是舍入误差所致,而非存在精确的代数相关关系。因此,判零容差需要根据数值尺度和精度来确定。对于难以判定秩的情况,采用奇异值分解或具有秩揭示能力的QR分解,通常比简单地统计高斯–若尔当消元中看似非零的主元更合适。

对于稀疏矩阵,消元可能使原本为零的位置出现非零元素,这种现象称为填充。因此,同时消去主元上方和下方的元素,不仅可能增加算术运算量,还可能带来较大的存储开销。

名称的历史渊源

这一名称结合了卡尔·弗里德里希·高斯和威廉·若尔当的姓氏。高斯的名字与消元方法密切相关;若尔当则是德国大地测量学家,曾在十九世纪描述过一种相关的消元过程。这里的若尔当并非法国数学家卡米耶·若尔当。

通过消去未知数求解的基本思想,远早于这两位冠名者。在现代术语中,高斯消元法通常止于行阶梯形或三角形,而高斯–若尔当消元法则继续化简,直至得到简化行阶梯形。