矩阵LU分解 | 彩潭有鲤的札记

type

status

date

slug

summary

高斯消元法

三元方程组，其对应的矩阵形式为

消元法的思路：

第一步：希望在第二个方程中消去项

下划线的为第一步的主元（pivot），这里先不管向量，可以做完的消元之后再做的消元

第二步，希望在第三个方程中消去项

第二行第一个非零元素成为了第二个主元：

第三行消元过后仅剩一个非零元素，所以它就成为第三个主元，做到这里就算消元完成了

回代

在矩阵后面加上向量写成增广矩阵（augmented matrix）的形式：

方程组变为，求出，，

消元失效的情形：

主元不能为零

如果在消元时遇到主元位置为零，则需要交换行，使主元不为零

如果第三个方程的系数是，第二步消元时最后一行全部为零，第三个主元就不存在了，这就是不可逆情况。

消元矩阵

三个列向量的矩阵乘以另一个向量，按列的线性组合可以写作

现在希望用矩阵乘法表示行操作：

这是一个行向量从左边乘以矩阵，按行操作矩阵的行向量，将其合成为一个矩阵行向量的线性组合。

可以将消元法所做的行操作写成向量乘以矩阵的形式

消元法第一步操作为将第二行改成，其余两行不变：

这个消元矩阵记作，即将第二行第一个元素变为零

如果三行都不变，消元矩阵就是单位矩阵，之于矩阵运算相当于之于四则运算

求消元矩阵，第三行第二个元素变为零

将这两步综合起来，

从矩阵直接得到矩阵，只需要即可（矩阵乘法满足结合律）。

消元所用的是两个初等矩阵（elementary matrix）

初等变换与初等矩阵

三种初等变换：

交换行/列

行/列乘以非0数

一行/列加到另一行/列

初等变换不影响矩阵的秩

对单位矩阵进行初等变换得到的矩阵称为初等矩阵，初等矩阵一定是可逆的

对矩阵的行变换相当于左乘以一个初等矩阵，列变换相当于右乘以一个初等矩阵

用于置换两行的矩阵：置换矩阵（permutation matrix）

交换两行：交换两列：

为置换矩阵，对任意可逆矩阵有：

对置换矩阵，有，即

阶方阵的置换矩阵有个

3阶方阵的置换矩阵有6个：

逆

现在能将通过行变换写成，那么如何从再变回，也就是求消元的逆运算。某些矩阵并没有逆，这里以有逆的矩阵为例。

以为例，，什么矩阵可以取消这次行变换？

这次变换是从第二行中减去三倍的第一行，那么其逆变换就是给第二行加上三倍的第一行，所以逆矩阵就是

把矩阵的逆记作，所以有

LU分解

L是下三角矩阵（通过初等行变换所使用的的矩阵E的乘积的逆矩阵）

U是上三角矩阵（是经过初等行变换后的行阶梯矩阵）

若有矩阵

前向计算，从到：

后向计算，从到：

其中，和只有一个数有区别，互为逆运算

若是一个维矩阵，则

将一个 阶方阵 变换为 需要的计算量估计：

第一步，将作为主元，需要的运算量约为

以此类推，接下来每一步计算量约为

则将变换为的总运算量应为，即