齐次线性方程组 & 非齐次线性方程组求解

齐次线性方程组

求解形如$AX=0$方程组，由于X可乘任意非零因子s，所以我们令$||X||=1$

• 步骤：

  • 对A进行SVD分解$A=U\sum V^T$
  • 取V的最后一列作为方程组的解

• 原理：

  • $AX=0$的求解等价于求解最小二乘问题

    $$min||AX||^2$$

    目标函数可写成：

    $$min ||AX||^2=min X^TA^TAX$$

    其中:

    $$A^TAX=\lambda X$$

    $\lambda$为矩阵$A^TA$的特征值。所以：

    $$min ||AX||^2=min X^TA^TAX=min\lambda ||X||^2=min \lambda$$

    即矩阵$A^TA$的最小特征值对应的特征向量即为方程的解。

  • SVD分解，对A进行SVD分解得：

    $$A=U\sum V^T$$

    其中，U由$AA^T$的特征向量组成，V由$A^TA$的特征向量组成，$\sum$对角线上的元素是$AA^T$及$A^TA$奇异值,并与U和V的列向量相对应。

  • 综上，奇异值矩阵$\sum$中最小奇异值对应的V中的列向量即为解。

非齐次线性方程组

求解形如$AX=b$方程组

• QR分解：

  $$AX=QRX=b\\ RX=Q^Tb$$

  R为上三角矩阵，X易求。

• cholesky分解($LL^T$)

  $$AX=b \rightarrow A^TAX=A^Tb$$

  对$A^TA$进行$LL^T$分解:

  $$A^TAX=A^Tb\rightarrow LL^TX=A^Tb$$

  然后：

  • 求解$Y$：$LY=A^Tb$
  • 求解$X$：$L^TX=Y$