线性方程组求解

3 most important points

1. 线性方程组解的个数
2. 伪逆速查
3. 线性方程组求解方法总结与对比

5 thoughts

Notes

概览

Question

求 $x$，使得线性方程组 $Ax=b$，其中 $A\in {\mathbb{R}}^{m\times n}$

其解的数量可以根据 A 和增广矩阵 $\tilde{A}=[A|b]$ 的秩来讨论：

解的个数	条件	求解
1	$\text{rank}(A)=\text{rank}(\tilde{A})=n$
0	$\text{rank}(A)<\text{rank}(\tilde{A})$
无穷	$\text{rank}(A)=\text{rank}(\tilde{A})<n$

$n$ 是未知数的个数，即矩阵 $A$ 的列数：

解的个数	条件	求解
1	系数矩阵的秩等于增广矩阵的秩，且这个秩等于未知数的个数	逆矩阵
0	系数矩阵的秩小于增广矩阵的秩	最小二乘
无穷	系数矩阵的秩等于增广矩阵的秩，且这个秩小于未知数的个数时	最小范数

最小二乘（Least Squares）和最小范数（Minimum Norm）是线性代数中两个重要的概念，尤其在求解线性方程组、优化问题和机器学习中广泛应用。它们分别用于处理超定方程（无精确解）和欠定方程（解不唯一）的情况，而伪逆（Pseudoinverse）在这两种情况下都能给出最优解。

逆矩阵

对于一个 $n\times n$ 的方阵 $A$，如果存在另一个同样大小的方阵 $B$，使得 $AB=BA=I_n$，其中 $I_n$ 是 $n\times n$ 的单位矩阵，那么矩阵 $B$ 就被称为矩阵 $A$ 的逆矩阵，记作 $A^{-1}$。

矩阵$A$有逆矩阵的条件是其行列式 $\det (A)$ 不为零，即 $\det (A)\ne 0$。如果矩阵 $A$ 的行列式为零，则称矩阵 $A$ 为奇异矩阵，奇异矩阵没有逆矩阵。

求逆矩阵的方法有多种，其中一种常见的方法是使用伴随矩阵和行列式。对于矩阵 $A$，其逆矩阵可以表示为：

$$A^{-1}=\frac{1}{\det (A)}\text{adj}(A)$$

其中 $\text{adj}(A)$ 是矩阵 $A$ 的伴随矩阵，它是 $A$ 的余子式矩阵的转置。余子式矩阵的每个元素是 $A$ 中对应元素的代数余子式。

代数余子式

在 $n$ 阶行列式中，把元素 $a_{ij}$ 所在的第 $i$ 行和第 $j$ 列划去后，留下来的 $n-1$ 阶行列式叫做元素 $a_{ij}$ 的余子式，记作 $M_{ij}$，将余子式 $M_{ij}$ 再乘以 $-1^{i+j}$ 记为 $A_{ij}$，$A_{ij}$ 叫做元素 $a_{ij}$ 的代数余子式。

另一种常见的方法是高斯-若尔当消元法（Gauss-Jordan Elimination）：

这种方法通过将原矩阵 $A$ 与单位矩阵 $I$ 合并成一个增广矩阵 $[A\mid I]$，然后进行行变换，直到增广矩阵的左边变为单位矩阵 $I$，此时右边即为 $A$ 的逆矩阵 $A^{-1}$。

Tip

对于分块矩阵，如果矩阵可以被合理地分块，有时可以直接计算分块的逆矩阵，然后组合得到整个矩阵的逆。

伪逆

普通逆矩阵 $A^{-1}$ 仅适用于满秩方阵（行列式为0），而求解线性方程组时，针对任意矩阵（包括非方阵、奇异矩阵）的一种广义逆矩阵，常用于求解线性方程组、最小二乘问题等。

对于任意矩阵 $A\in {\mathbb{R}}^{m\times n}$，其伪逆 $A^{+}\in {\mathbb{R}}^{n\times m}$ 满足以下 Moore-Penrose 条件：

• $A{A}^{+}A=A$
• $A^{+}A{A}^{+}=A^{+}$
• $(A{A}^{+}{)}^T=A{A}^{+}$ （$A{A}^{+}$ 对称）
• $(A^{+}A{)}^T=A^{+}A$ （$A^{+}A$ 对称）

秩条件	含义	求解
$\text{rank}(A)=n$	列满秩	$A^{+}=(A^{T}A{)}^{-1}{A}^T$
$\text{rank}(A)=m$	行满秩	$A^{+}=A^T(A{A}^T{)}^{-1}$
$\text{rank}(A)\ne m,n$	一般情况，使用 SVD	设 $A=U\Sigma V^T$，则 $A^{+}=V{\Sigma }^{+}{U}^T$，其中 ${\Sigma }^{+}$ 是将 $\Sigma$ 非零元素取倒数后转置

最小二乘

当线性方程组 $Ax=b$ 无解（即 $b$ 不在 $A$ 的列空间内），我们希望找到一个近似解 $x$，使得误差 $\Vert Ax-b{\Vert }_2$ 最小。

最小二乘解 $x^{\ast }$ 满足：

$$x^{\ast }=\arg \underset{x}{\min }\Vert Ax-b{\Vert }_2^2$$

即，在所有可能的 $x$ 中，选择使得 $Ax$ 最接近 $b$ 的那个。

使用伪逆：$x^{\ast }=A^{+}b$

正规方程

当 $\text{rank}(A)=n$，代入表格得最小二乘解为 $x^{\ast }=(A^{T}A{)}^{-1}{A}^{T}b$

正规方程（Normal Equation）是用于求解线性回归模型参数的一种方法，它直接通过计算公式得到最优解，而不需要像梯度下降法那样进行迭代。

正规方程的公式通常表示为：$\theta =(X^{T}X{)}^{-1}{X}^{T}y$

对于小规模数据集，正规方程计算速度较快，无需迭代，可以直接得到最优解； 然而当特征数量很大时，计算 $X^{T}X$ 的逆矩阵非常耗时，计算复杂度较高，不如梯度下降法

几何意义

最小二乘解 $x^{\ast }$ 使得 $A{x}^{\ast }$ 是 $b$ 在 $A$ 的列空间上的正交投影：

$$A{x}^{\ast }=Pb$$

其中 $P=A{A}^{+}$ 是投影矩阵。

最小二乘的应用场景包括：

• 线性回归：拟合数据点 $(x_i,y_i)$ 到直线 $y=kx+b$。
• 信号处理：滤波、去噪。
• 机器学习：参数估计（如线性回归、岭回归）。

最小范数

当线性方程组 $Ax=b$ 有无穷多解（即 $A$ 行不满秩，$\text{rank}(A)<n$），我们希望从所有解中选择范数最小的解 $x^{\ast }$，即：

$$x^{\ast }=\arg \underset{x}{\min }\Vert x{\Vert }_2\text{s.t.}Ax=b$$

最小范数解 $x^{\ast }$ 满足：

$$x^{\ast }=A^{+}b$$

其中 $A^{+}$ 是 $A$ 的伪逆。

Transclude of 范数#^9b5360

在所有满足 $Ax=b$ 的解中，最小范数解 $x^{\ast }$ 位于 $A$ 的行空间（即 $x^{\ast }$ 与 $A$ 的零空间正交）。

最小范数的应用场景包括：

• 欠定方程组：如传感器校准（方程数少于变量数）。
• 优化问题：在可行解中选择最“简单”的解（如最小能量控制）。
• 压缩感知（Compressed Sensing）：寻找稀疏解（类似 ${\ell }_1$-范数最小化）。

总结

	逆矩阵 $A^{-1}$	最小二乘	最小范数	伪逆 $A^{+}$
使用情况	$A$ 为方阵且满秩 $\text{rank}(A)=n$	$A$ 列满秩或非方阵 方程无解（超定，$m>n$)	$A$ 行满秩或非方阵 方程解不唯一（欠定，$m<n$)	任意矩阵 $A$ （包括非方阵、秩缺陷矩阵）
目标	精确满足 $Ax=b$	最小化 $\Vert Ax-b{\Vert }_2$ （残差范数）	满足 $Ax=b$ 前提下，最小化 $\Vert x{\Vert }_2$ （解范数）	统一实现上述两个目标
求解	$x^{\ast }=A^{-1}b$	$x^{\ast }=(A^{T}A{)}^{-1}{A}^{T}b$	$x^{\ast }=A^T(A{A}^T{)}^{-1}b$	$x^{\ast }=A^{+}b$
几何意义	坐标的线性变换，可完美逆变换	$A{x}^{\ast }$ 是 $b$ 在 $Col(A)$ 上的正交投影	$x^{\ast }$ 位于 $Row(A)$，与 $Null(A)$ 正交	自动实现上述两种几何意义
计算基础	LU分解、高斯消元法等	正规方程（Normal Equation）	类似正规方程	奇异值分解（SVD）
典型应用	求解经典线性方程组、坐标变换、解密算法	线性回归、数据拟合、曲线拟合	欠定系统控制、资源分配、信号重构	机器学习（岭回归、PCA）、数值分析、控制系统、任何不适定问题

Related

• 线性代数

Reference