线性代数之——A 的 LU 分解

作者: seniusen | 来源:发表于2018-11-14 19:00 被阅读19次

线性代数之——A 的 LU 分解
矩阵的LU分解2_线性代数_day41
非方正矩阵的LU分解_线性代数_day42
4.3 LU分解
【线性代数启示5】关于矩阵的LU分解
矩阵的LU分解
1.4、A的LU分解
数值分析知识补漏
什么是矩阵的LU分解_线性代数_day40
4. 矩阵的逆及LU分解

1. A = LU

之前在消元的过程中，我们看到可以将矩阵 $A$ 变成一个上三角矩阵 $U$ ， $U$ 的对角线上就是主元。下面我们将这个过程反过来，通一个下三角矩阵 $L$ 我们可以从 $U$ 得到 $A$ ， $L$ 中的元素也就是乘数 $l_{ij}$ 。

如果有一个 3*3 的矩阵，假设不需要进行行交换，那我们需要三个消元矩阵 $E_{21}, E_{31}, E_{32}$ 来分别使矩阵 $A$ 的 (2, 1)、(3, 1) 和 (3, 2) 位置为零，然后我们就有

乘数 $l_{ij}$ 正好就是 $L$ 中 $(i, j)$ 处的元素。因为当我们计算 $U$ 的第三行的时候，实际上是用 $A$ 的第三行减去 $U$ 的前两行的一些倍数。

因此有

下面看一个特殊的例子

如果 $A$ 的某一行以 0 开始，说明该位置不需要进行消元，也即 $L$ 中对应位置的元素为 0。

如果 $A$ 的某一列以 0 开始，该位置元素在消元过程始终不会改变，也即 $U$ 中对应位置的元素为 0。

由于 $L$ 的对角线上都是 1，而 $U$ 的对角线上为主元，因此，这是不对称的。我们可以进一步将 $U$ 进行分解，使得 $U$ 的对角线上元素也都为 1。

这时候， $A$ 的分解就变成了 $A = LU = LDU$ ，其中 $D$ 是一个对角矩阵， $L$ 是一个下三角矩阵， $U$ 是一个上三角矩阵。

当我们从左边的 $A$ 得到 $L$ 和 $U$ 后，我们就对右边的 $b$ 进行同样的消元过程得到 $Lc = b$ ，然后再通过回带 $Ux=c$ 求出方程组的解。

2. 消元过程的计算复杂度

假设我们有一个 $n*n$ 的矩阵，首先我们要将第一列主元以下的元素都变成 $0$ 。这时候，每一个元素变成 $0$ 我们都需要 $n$ 次乘法和 $n$ 次减法，总共有 $n-1$ 个元素需要变成 $0$ ，总的乘法次数为 $n(n-1)$ ，近似为 $n^2$ 。然后，我们要依次将后面列的主元下面的元素变成 $0$ ，需要的总的乘法次数为 $n^2+(n-1)^2+\cdots + 2 + 1 \approx \frac{1}{3}n^3$ 。

也就是说对左边的 $A$ 消元要进行 $\frac{1}{3}n^3$ 次的乘法操作和 $\frac{1}{3}n^3$ 次的加法操作。

再来看右边对 $b$ 进行消元，首先我们需要将 $b_2, b_3 \cdots b_n$ 都减去 $b_1$ ，需要 $n-1$ 次操作，往后我们依次需要 $n-2, n-3 \cdots 1$ 次操作。回带的时候，求解最后一个方程的时候，我们只需要进行 1 次操作，依次往上我们需要 $2, 3 \cdots n$ 次操作。因此，求解的过程总共需要 $n^2$ 次的乘法操作和 $n^2$ 次的加法操作

3. 转置和置换矩阵

$A$ 的转置矩阵称为 $A^T$ ，其中 $A^T$ 的列就是 $A$ 的行，也即 $(A^T)_{ij} = A_{ji}$ 。

$(A+B)^T = A^T + B^T$
$(AB)^T = B^TA^T$

假设 $B$ 是一个向量 $x$ ，那么对 $(Ax)^T = x^TA^T$ 的理解就是： $Ax$ 是对 $A$ 的列的线性组合， $x^TA^T$ 则是对 $A^T$ 的行的线性组合， $A$ 的列和 $A^T$ 的行是一样的，所以线性组合后是一样的结果。

如果 $B$ 有多列的话，我们就很容易得到

同理，针对更多的矩阵，我们也有

$(ABC)^T = C^TB^TA^T$

$(A^{-1})^T = (A^T)^{-1}$

$AA^{-1} = I \to (AA^{-1})^T = I \to (A^{-1})^TA^T = I \to (A^{-1})^T = (A^T)^{-1}$

转置形式的内积和外积

对称矩阵的转置等于它本身，也就是 $A^T = A$ 。而且，一个对称矩阵的逆矩阵也是对称的。

$(A^{-1})^T = (A^T)^{-1} = A^{-1}$

对于一个任意的矩阵 $R$ ，可以是矩形的， $R^TR$ 和 $RR^T$ 都是一个对称的方阵。

$(R^TR)^T = R^T(R^T)^T = R^TR$

当 $A=A^T$ 时，如果没有行交换，那么有 $A = LDU = LDL^T$ ，此时 $U$ 变成了 $L^T$ 。

置换矩阵 $P$ 每行每列都只有一个 1，而且 $P^T$ 、 $PP^T$ 和任意两个置换矩阵的乘积 $P_1P_2$ 都还是置换矩阵。此外，所有的置换矩阵都有 $P^T=P^{-1}$ 。

在 $n$ 阶的情况下，置换矩阵的总的个数为 $n!$ 。例如 2 阶置换矩阵只有 2 个，3 阶置换矩阵有 6 个。

如果在需要行交换的情况下，我们可以先引入一个置换矩阵 $P$ 使矩阵 $A$ 的行有正确的顺序，然后再进行消元，这样的话我们就有

$PA=LU$

也可以进行消元，然后再用一个矩阵 $P_1$ 来让主元有一个正确的顺序，这样的话我们就有

$A=L_1P_1U_1$

如果 $A$ 是可逆的，置换矩阵 $P$ 将会使它的行有一个正确的顺序然后分解成 $PA=LU$ 的形式。

获取更多精彩，请关注「seniusen」!

线性代数之——A 的 LU 分解
1. A = LU 之前在消元的过程中，我们看到可以将矩阵变成一个上三角矩阵，的对角线上就是主元。下面我们...
矩阵的LU分解2_线性代数_day41
将矩阵A分解为分解成了LU矩阵 LU分解大概有：
非方正矩阵的LU分解_线性代数_day42
矩阵的LU分解就是将矩阵分解成一个上三角矩阵，和一个下三角矩阵矩阵的LU分解可以用于非方阵的分解矩阵的LU分解...
4.3 LU分解
LU分解的前提：定理3.1 顺序主子式均不为0 ，必有唯一的LU分解定理3.2 非奇异矩阵A，必有PA=LU，...
【线性代数启示5】关于矩阵的LU分解
矩阵的乘法运算规则颇为复杂，但这个规则是从线性方程组，线性变换中抽象而来。标量乘的规则也是基于线性变换。所以我们可...
矩阵的LU分解
前言看了麻省理工的线性代数的一部分课程，主要是补补课，大二线代忘得差不多，主要目的是学习SVD，学习SVD之前补...
1.4、A的LU分解
html与pdf笔记更新链接(Google云盘)
数值分析知识补漏
1、方程组（高斯消元，LU分解，AP=LU分解，误差问题，共轭梯度） 2、最小二乘（模型，正规方程，不相容，QR分...
什么是矩阵的LU分解_线性代数_day40
什么是矩阵的LU分解将矩阵A分解为 L：下三角矩阵U：上三角矩阵image-20200223220923910...
4. 矩阵的逆及LU分解
矩阵的初等变换矩阵的逆矩阵的LU分解