# 线性方程组与高斯消元

[[MCS/day8/00 学习指南|day8 学习指南]] · [[MCS/00 MCS学习总览|十一天总览]] · [[MCS/day8/阅读核验与疑问|阅读核验与疑问]] · 下一篇：[[MCS/day8/02 齐次方程、LU 复杂度与病态问题|齐次方程、LU 复杂度与病态问题]]

> 来源：[[MCS/day8线性方程组与消元法|day8线性方程组与消元法]]。用途：主线。原有推导、追问与解答保留；阅读时请结合本日核验说明。

## 为什么解线性方程组

极其关键的运算，求 Hessian H 的逆矩阵
模型有 1 亿个参数
Hessian 矩阵是 1 亿 x 1 亿
Answer：不会去求逆，而是解一个线性方程组
H Δ x = -g ---> 线性方程组
求解出△x，完成牛顿法的迭代
高斯、计算机、《九章算术》

## 历史与计算应用

《九章算术》方程术
算筹摆成矩阵“遍乘直除”
高斯“数学王子”
数学是科学的皇后，数论是数学的皇后
计算机时代的矩阵求解
20 世纪，计算机诞生。第一代计算机主要任务是解线性方程组
电路分析
节点越多，方程组越大
求解电流与电压

计算机求解
图形学：求光线与平面的交点
推荐系统：矩阵分解求解用户和物品的隐向量
机器学习：线性回归的正规方程
优化算法：牛顿法中的 H Δ x = -g

A：n x n 矩阵，O(n³)，需要存储 n²个元素 n = 10000, n² = 100,000,000 内存直接爆炸
高斯消元复杂度是 O(n³)
方程组做行变换
高斯消元数值更稳定，误差更小
标准化、矩阵化、算法化

## 高斯消元示例

Example:
2 x + y - z = 8
-3 x - y + 2 z = -11
-2 x + y + 2 z = -3
简化书写，常把系数与常数提取出来

竖线代表等于号，左边为系数，右边为常数
增广矩阵:
$$
\left[
\begin{array}{ccc|c}
2 & 1 & -1 & 8 \\
-3 & -1 & 2 & -11 \\
-2 & 1 & 2 & -3
\end{array}
\right]
$$

目的：把矩阵变成上三角矩阵，从上往下代回求解

$$
\left[\begin{array}{ccc|c}
2 & 1 & -1 & 8 \\
0 & 1/2 & 1/2 & 1 \\
0 & 0 & -1 & 1
\end{array}\right]
$$

## 主元选择与回代

k = 1 到 n - 1:
1: 选主元，在第 k 列，找到绝对值最大的元素所在的行，与第 k 行交换可以提高数值稳定性
2：消元，按你学过的基础消元即可
**主元 = 当前用来消元的那个非零基准元素**。
记住矩阵的秩其实就是矩阵中啊，线性无关的行，或者是列最大的数目，我们把它叫做秩，他告诉我们啊，方程组当中有多少有效信息。
得到上三角矩阵
解的三种情况：
唯一解：矩阵的秩等于未知数个数 n
无解：矩阵的秩小于 n，且出现矛盾行（0=非零）
矩阵的秩，让我们知道方程组中有多少“有效信息”
高斯消元 2.0：LU 分解
如果我们把矩阵 A 分解为 A=LU
L 是下三角矩阵，U 上三角矩阵

Low traingular
非零元素集中在对角线下方
Upper traingular
非零元素集中在对角线上方


Ax = b
1. 解 Ly = b(前向代入，很快)
2. 解 Ux = y(回代，很快)
好处是：如果 A 不变，只有 b 变了，不需要重新消元，做一次分解，可求解新的 b

啊解方程组本质上就是找两条直线的一个交点，

条件数（condition number） cn 越大，矩阵越病态，解对误差越敏感
DL 极度依赖归一化（Batch Normalization）和正则化（Regularization）正则化可以改善矩阵的 cn,让解不会再飞走
1.不要显式求逆，要高斯消元或者 LU 分解，尽量选绝对值大的主元，降低误差放大 
1. 假设矩阵本身就病态，一定要用正则化（比如岭回归思想），拉回正常区间 
2. 3. 牛顿法 DL 不用， Hessian 极易病态，导致优化飞走’，so Adam 优化器


## 高斯消元法的应用

高斯消元本质上就是通过初等行变换把矩阵化为行阶梯形或行最简形，从而求解线性方程组、矩阵逆、行列式、矩阵秩等问题。

---

### 1. 求解中小规模稠密线性方程组

对于形如：

$$
Ax = b
$$

的线性方程组，如果矩阵 $A$ 是中小规模、稠密矩阵，高斯消元是常用方法。

基本过程：

1. 构造增广矩阵 $[A \mid b]$
2. 通过初等行变换化为行阶梯形
3. 回代求解未知数

适用场景：

- 变量个数不太大
- 矩阵大多数元素非零，即稠密矩阵
- 直接法求解，而不是迭代法

---

### 2. 计算矩阵的逆

要求矩阵 $A$ 的逆 $A^{-1}$，可以构造：

$$
[A \mid I]
$$

然后通过高斯-若尔当消元，把左边化为单位矩阵：

$$
[I \mid A^{-1}]
$$

右边就是矩阵的逆。

前提：

- $A$ 必须是可逆矩阵
- 如果消元过程中出现无法选到非零主元，说明矩阵可能不可逆

---

### 3. 计算行列式

高斯消元也可以用来计算行列式。

因为初等行变换会影响行列式：

- 交换两行：行列式变号
- 某行乘以常数 $k$：行列式乘以 $k$
- 某行加上另一行的倍数：行列式不变

所以可以把矩阵化为上三角矩阵，然后：

$$
\det(A) = \text{主对角线元素乘积}
$$

再根据行变换过程中产生的符号变化和倍数变化进行修正。

---

### 4. 求解等式约束优化中的 KKT 线性方程组

在数值优化、线性规划等问题中，经常会遇到等式约束优化问题。

例如：

$$
\min f(x)
$$

$$
s.t. \quad h(x) = 0
$$

使用拉格朗日乘子法后，会得到 KKT 条件。很多情况下，最终需要求解一个线性方程组，即 KKT 线性方程组。

这个线性方程组的底层求解操作，常常就是高斯消元。

所以高斯消元是以下问题中的基础操作：

- 数值优化
- 线性规划
- 约束优化

---

### 5. 计算矩阵的秩

高斯消元可以用来求矩阵的秩。

原因：

- 初等行变换不改变矩阵的秩
- 把矩阵化为行阶梯形后
- 非零行的数量就是矩阵的秩

即：

$$
\text{rank}(A) = \text{行阶梯形中非零行的个数}
$$

---

### 6. 计算机图形学中求解几何交点

在计算机图形学中，很多几何问题本质上可以转化为线性方程组。

例如：

- 直线与平面求交
- 两个平面求交线
- 光线与三角形求交
- 几何变换中的坐标求解

这些问题本质上都可能是解线性方程组。

因此，高斯消元也可以应用于计算机图形学中的几何交点求解。

---

### 总结

高斯消元法的主要应用包括：

1. 求解中小规模稠密线性方程组
2. 计算矩阵的逆
3. 计算行列式
4. 求解等式约束优化中的 KKT 线性方程组
5. 数值优化、线性规划中的底层线性求解
6. 计算矩阵的秩
7. 计算机图形学中求解几何交点

一句话总结：

高斯消元是线性代数中最基础的算法之一，核心是通过初等行变换把矩阵化为行阶梯形，从而解决线性方程组、矩阵逆、行列式、矩阵秩以及优化和图形学中的相关计算问题。