线性方程组的直接解法总结（线性方程组如何求解）

线性方程组求解

普通最小二乘问题 （ Ax = b )

考虑超定方程 ，其中为m * 1的数据向量，为m * n的数据矩阵，并且m > n。

为了抑制误差对该矩阵方程求解的影响，引入一校正向量 \delta b ，并用它去“扰动”有误差的数据向量 b 。如果我们选择校正向量 \delta b = Ax - b ，并使得校正向量尽可能小，则可以实现无无差的矩阵方程 Ax = b_{0} 的求解。

矩阵方程的这一求解思想可以用下面的优化问题进行描述

min \quad ||\delta b||^{2} = ||Ax-b||_{2}^{2} = (Ax-b)^{T}(Ax-b)

这一方法称为普通最小二乘法，常简称为最小二乘。

矩阵 Ax = b 的普通最小二乘解为

\hat{x} = arg min \quad || Ax - b||_{2}^{2}

为了推导 x 的解析形式，展开得到

\phi = x^{T}A^{T}Ax - x^{T}A^{T}b - b^{T}Ax + b^{T}b

求 \phi 相对于 x 的导数，并令其结果等于零，则有

\frac{d\phi}{dx} = 2A^{T}Ax - 2A^{T}b = 0

也就是说，解 x 必然满足

A^{T}Ax = A^{T}b

当m * n 矩阵A具有不同的秩时，上述方程的解有两种不同的情况：

情况1 超顶方程（m > n）列满秩，即rank(A) = n。

由于 A^{T}A 非奇异，所以方程有唯一的解

x = {(A^{T}A)}^{-1}A^{T}b

这就是最小二乘解。在参数估计理论中，称这种可以唯一确定的参数 x 是唯一可辨识的。

对于秩亏缺rank(A)

x = {(A^{T}A)}^{+}A^{T}b

其中 B^{+} 代表矩阵B的Moore-Penrose逆矩阵。

情况2 欠定方程rank(A) = m < n

在这种情况下，由于x的不同解均得到相同的Ax值。显而易见，虽然数据向量b可以提供有关Ax的某些信息，但是无法区别对应于相同Ax值的哥哥不同的未知参数向量x。因此，称这样的参数向量是不可辨识的。

SVD线性方程组求解

SVD基础知识

奇异值分解（SVD)是一种使用最为广泛的线性方程组求解技术。我们已知一个矩阵A可以分解成如下形式：

A = VDV^{T} \quad (1)

其中，V是一个正交矩阵 ，有 V^{T}V = VV^{T} = I , 代表矩阵V的转置，D是一个对角矩阵，对角矩阵D中的每一个元素都是矩阵A的特征值

对于一个方阵A，总能找到一种特征值分解方式。当矩阵A不是方阵时，我们仍能利用相似的方法进行分解，这就是SVD分解。

对于任意给定的一个m * n的矩阵A，都存在分解：

A = UDV^{T} \quad(2)

其中，U是一个m * m的正交矩阵，D是一个m * n的对角矩阵，V是一个n * n的正交矩阵。D中的每一个对角元素都是矩阵A的一个特征值，叫做矩阵A的奇异值，U中的列向量叫做A的左歧义向量，V中的列向量叫做A的右奇异向量。

SVD求解非齐次线性方程组（ Ax = b )

SVD等各种矩阵分解可以被用来求解诸如 Ax=b 这样的线性方程组。这个问题其实就等价于最小化

min \quad || Ax - b ||^{2} \quad(3)

这是一个非线性优化问题。

我么已知矩阵A可以分解为 A = UDV^{T} ，并且对于一个正交矩阵，满足如下性质：

|| Mv || = || v || \quad (4)

其中，v是一个列向量。把（4）带入（3）中，得到

min(|| Ax - b ||^{2}) = min(|| UDV^{’}x - b ||) = min(DV^{}x - U^{}b) \quad (5)

设 y = Vx ， b = Ub ，（5）式可重新表述为 Dy = b ，其中D是一个对角矩阵，表达成矩阵形式如下：

根据上式，方程组的解很容易得到 y_{i}= b_i^{}/ d_i 。

SVD求解齐次方程组（ Ax = 0 ）

和上面求解非齐次线性方程组的方法类似，先把问题转化为最小化 ||Ax||^{2} 的非线性优化问题，我们已知 x = 0 是该方程组的一个特解，为了避免 x = 0 这种情况，给x增加一个约束 ||x||^{2} = 1 这样问题就转化为：

min(|| Ax ||^{2}) ， || x ||^{2} = 1 \quad 或 \quad min(|| Ax ||) ， || x || = 1 \quad (6)

将奇异值分解带入公式（6）得到：

|| Ax || = || UDV x || = || DV x|| \quad (7)

令 y = Vx ，因此，问题转变为：

min(|| Dy ||)， || y || = 1 \quad (8)

由于D是一个对角矩阵，对角元的元素按照递减的顺序排列，因此最优解在 y = (0, 0,..., 1) 时取得，右因为 x = Vy ，所以最优解就是矩阵A的最小奇异值对应的列向量，比如最小奇异值在第8行8列，那么x就是矩阵V的第8个列向量。即线性方程组 Ax = 0 的解为 A^{T}A 的最小特征值对应的特征向量。

各种分解矩阵求解线性方程组（ Ax = b ）

QR分解

在线性代数中，QR分解是将一个矩阵A分解为如下形式：

A = QR

其中，Q是一个正交矩阵（即 Q^{T}Q = QQ^{T} = I ），R是一个上三角矩阵。QR分解经常被用来求解线性最小二乘问题。

如果矩阵A可逆，且要求矩阵R的对角元素是正的，那么QR分解具有唯一的结果。

如果矩阵A是一个复数方块矩阵，那么QR分解得到的矩阵Q是一个酉矩阵（即 Q^{*}Q = QQ^{*} = I ）。

对于一个m*n的矩阵A，其中m > n，可以分解为m*m的酉矩阵Q和一个m*n的上三角矩阵R

对于欠定的(m < n) 线性问题 Ax = b，其中矩阵A的维度为m*n，且秩为m。可以得到Ａ的转置的QR分解为： A^{T} = QR 。其中Q是一个正交矩阵（ Q^{T} = Q^{-1} ），矩阵R具有如下形式：

{ R=\begin{bmatrix}R_{1}\\0\end{bmatrix}}

其中，R1是一个右三角矩阵，那么问题的求解为：

对于超顶(m >= n)方程Ax = b, 就是最小化 || A \hat{x} - b || ，首先对矩阵A进行QR分解得到：A = QR。那么解为：

\hat{x} = R_{1}^{-1} (Q_{1}^{T}b)

其中 Q_{1} 是一个m * n的矩阵，包含整个正交矩阵Q的前n行， R_{1} 和上面是一致的。

LU矩阵分解

在数值分析和线性代数中，LU(lower-upper)分解将一个矩阵分解为一个下三角矩阵和一个上三角矩阵。

利用LU分解求解线性方程组 Ax = b：

假设我们已经获得了矩阵A的LUP分解PA = LU，那么 LUx = Pb. 整个求解过程分为两个步骤：通过方程Ly = Pb 求解出y;通过方程Ux = y求解出x。

Cholesky decomposition

在线性代数中，Cholesky decomposition是将一个Hermitian, positive-definite matrix分解为一个下三角矩阵和其共轭转置的乘积。广泛应用于数值求解。对于求解线性系统方程，Cholesky decomposition的求解效率是LU decomposition 的两倍。

注意Choleskey decomposition的条件：

Hermitian：矩阵与它的共轭转置相等。对应到实数阈，就是对称矩阵。positive-definite：对任何非零列向量x，标量 x^{-T}Ax 是严格大于零的，那么矩阵A就是正定矩阵。

一个埃尔米特正定矩阵A的Choleskey decomposition是如下的分解形式：

A = LL^{*}

其中， L 是一个lower triangular matrix，具有real and positive diagonal entries. L^{*} 是矩阵 L 的共轭转置。每一个埃尔米特正定矩阵都有一个独一无二的Cholesky decomposition。但是，当矩阵A是半正定时，分解就不具有独一无二的性质。

如果矩阵A是埃尔米特半正定矩阵，那么矩阵A仍然具有 A = LL^{*} 的分解形式，但是需要允许矩阵L的对角块为零。

当矩阵A只有实数项时，矩阵L也只有实数项，那么分解可以被写为：

A = LL^{T}

我们也可以得出：如果矩阵A能够被表达为LL*的形式，且L可逆，下三角，那么矩阵A是埃尔米特正定矩阵。

利用Cholesky分解求解方程组Ax = b：

The Cholesky decomposition is mainly used for the numerical solution of linear equations Ax = b . If A is symmetric and positive definite, then we can solve Ax = b by first computing the Cholesky decomposition A = LL^{*} , then solving Ly = b for y by forward substitution, and finally solving L^{*}x = y for x by back substitution.

利用Cholesky分解进行矩阵求逆：

对于埃尔米特矩阵的逆可以直接通过Cholesky分解求出，使用 n^{3} 次计算。

A^{-1} = (LL^{*})^{-1} = (L^{*})^{-1}L^{-1} 对于非埃尔米特矩阵B仍然能够通过Cholesky分解求出，因为 BB* 是埃尔米特矩阵：

B^{-1} = B^{*}(BB^{*})^{-1}

Choleskey分解计算的时间复杂度为 O(n^{3}) 。下面给出的算法需要 n^{3}/3 次操作（ n^{3}/6 次乘法和相同的加法运算。其中，n是矩阵A的大小。LU分解需要 2n^{3}/3 次操作。

具体的Cholesky分解的计算步骤详见 *** 和eigen库的代码：

1https://en. *** .org/wiki/Cholesky_decomposition#Statement

LDLT分解

经典Cholesky decomposition的一个变型是 LDL decomposition,

A = LDL^{*}

其中，L是一个下单位三角矩阵（lower unit triangular matrix），D是一个对角矩阵。

LDL分解和经典Cholesky decomposition的关系为：

A = LDL^{*} = LD^{1/2}(D^{1/2})^{*}L^{*} = LD^{1/2}(LD^{1/2})^{*}

或者，给定经典Cholesky分解 L^{Cholesky} ， LDL^{*} 能够通过矩阵L的对角线必须为1，Cholesky和 LDL^{T} 都是下三角形式等特性获得。如果S是对角矩阵，并且包含 L^{Cholesky} 的主要对角，那么可得：

D = S^{2}

L = L^{Cholesky}S^{-1}

这种变形，和Cholesky分解需要相同的空间和计算复杂度，但是不需要平方根。对于不存在Cholesky分解的不定矩阵存在LDL分解，但是矩阵D中存在负的项。由此，LDL分解应用更加广泛。对于实数矩阵，LDL分解具有 A = LDL^{T} 形式，通常被称为LDLT分解。它和实对称矩阵的特征分解 A = Q \Lambda Q^{T} 很相近。

利用LDL分解求解方程组Ax = b：

An alternative way to eliminate taking square roots in the LL^{*} decomposition is to compute the Cholesky decomposition A = LDL^{*} , then solving Ly = b for y, and finally solving DL^{*}x = y.

Eigen库调用：

const Vector6d dT(A.ldlt().solve(b));