矩阵论1：概述和LU分解

九月 23, 2021

math

矩阵论介绍

上位数学系课程：泛函，群

前置课程：高数，线性代数

数是特殊的矩阵 => 矩阵没有部分数的属性（例：乘法交换律）

矩阵的三个层面：

微观层面：数的组合
宏观层面：完全抽象物，符合某些运算的数学对象（上位数学系视角）
中间层面：向量组

LU分解

为了引出 LU 分解的意义和解法，让我们先回顾一下线性方程的基本解法。

线性方程组解法（线性代数范围）

Gauss 消元法
求逆矩阵
1. Gauss 消元法
2. 伴随矩阵
克莱姆法则

其中克莱姆法则和伴随矩阵复杂度为 O(n*n!)；Gauss消元法和求逆矩阵法则为 O(n^3)。

为了之后求解和证明 LU 分解在此先介绍一个定义

主元 pivot ：在矩阵消去（例如Gauss消元法）过程中，每列的要保留的非零元素，用它可以把该列其他消去。

L(D)U 分解定理：

如果方阵 A 的各阶顺序主子式，

$\Delta_k\neq 0\ \ k=1,2...n$

则存在唯一的主对角线上元素全为1的下三角矩阵（称为单位下三角元素）L 与唯一的非奇异上三角矩阵 U，使得

$A = LU$

或者存在唯一的单位下三角元素 L、单位上三角元素 D 和对角矩阵，使得

$A=LDU$

注意，在矩阵乘法结合律和 LU 分解定理的基础上，LDU 分解定理是显然的。

LU 分解求法：

由于 LU 分解定理的证明要涉及到求法，所以先介绍 LU 分解求法。

$\begin{align} &A=LU\ and\ L^{-1}L=I \\ \\ \Rightarrow & L^{-1}A = L^{-1}LU=U \\ \\ \Rightarrow & L^{-1}(A,I) = (L^{-1}A,L^{-1})=(U,L^{-1}) \end{align}$

上面的证明过程表明，通过一系列行初等变换，即 $L^{-1}$ 分解为的初等矩阵，可以将增广矩阵 $(A,I)$ 转化为 $(U,L^{-1})$ ，接下来在求 $L^{-1}$ 的逆即可得到 $L$

⭐ 这里介绍一种简单的 $L$ 求法，每次矩阵消去之前都将主元以及其下方元素记下，最后各列除以其主元，即为 $L$，证明略

⭐ 思考：这里能否使用所有的三类初等变换？

答案：只能使用第三类初等变换，由于 $L^{-1}$ 为单位下三角矩阵，其只由第三类初等变换矩阵构成

LU 分解定理证明

1.必要性 $A=LU\Rightarrow \Delta_k\neq0$

$\begin{pmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{pmatrix} = \begin{pmatrix} L_{11} & 0 \\ L_{21} & L_{22} \end{pmatrix} \begin{pmatrix} U_{11} & U_{12} \\ 0 & U_{22} \end{pmatrix} = \begin{pmatrix} L_{11}U_{11} & L_{11}U_{12} \\ L_{21}U_{11} & L_{21}U_{12}+L_{22}U_{22} \end{pmatrix}$ $\begin{align} \Rightarrow det(A_{11}) &= det(L_{11}U_{11})\\ \\ &=det(L_{11})det(U_{11})\\ \\ &=1\cdot det(U_{11}) \neq 0 \end{align}$

考虑到 $A_{11}$ 阶数的任意性，以上证明显然对 $A$ 的任意顺序主子式都有效。

2.充分性 $A=LU\Leftarrow \Delta_k\neq0$

证明充分性可以从 LU分解求法入手，可以观察到阻碍任意方阵 LU分解的唯一障碍，在于主元为 0。

而 LU分解求法中，主元左侧的元素全为 0，而 $\Delta_k\neq0$ 和初等变换不会改变行列式的非零性，可知主元必不为 0。

所以符合 $\Delta_k\neq0$ 条件的矩阵一定可以通过上述 LU分解求法得到 $A=LU$。

LU 分解用途

当 $A=LU$ 时，方程 $Ax=b$ 可以写成 $L(Ux)=b$ ，令 $Ux=y$ ,则有：

$Ly=b \ \ Ux=y$

即将原本单步问题化为两步，因为矩阵 $L$ 和 $U$ 都是三角矩阵，所以求解上述两个方程比直接求解 $A=LU$ 简单，其复杂度为 O(n^2) 。

然而LU分解的复杂度为 O(n^3)，似乎LU分解并不能减少运算量，但LU分解最大的优点在于复用性，其第一步LU分解，仅与 $A$ 有关，和 $b$ 无关，这意味着不论 $b$ 如何改变，重复做多少次，其增加的复杂度都是 O(n^2)。

当然LU分解法也不是只有好处的，一个明显的缺点为LU只适用于解所有顺序主子式都大于0的，通用性欠缺，但这也可以通过某些方法规避，将在下文介绍。

LU分解的几种推广

带置换的LU分解——PLU分解

如果存在置换矩阵 P、单位下三角矩阵 L 与上三角矩阵 U，使得方阵 A 满足

$PA = LU$

则称上式为 A 的带置换 P 的 LU分解

具体 P 的选择方法可以使用列选主元法：在每列确定主元的时候，都选择该列主元位置及其下方绝对值最大的元素。

这一方法有两个作用：

1.可以解决上文所说的缺陷—— LU 分解只适用于解所有顺序主子式都大于0的；

liexuanzhuyuanbuwei0

上图为 LU 分解求法中的某个步骤，蓝色为已经选择的主元，白色为0，绿色为供选择下一个的主元的区域。

简单证明：若绿色全为0，则红色区域由于不为方阵，一定可以通过初等变换获得一个全为0的行，左侧又全为0，即整个矩阵通过初等变换得到一个全为0的行，与矩阵可逆矛盾，所以绿色区域一定存在一个不为0的元素，通过列选主元法得到的主元一定不为0。

2.由于保证消去时候的乘子都不超过1，抑制了数据误差的放大，提高计算稳定性。

非可逆方阵

分为两种情况：

不满秩（秩为 r ）方阵：方法和可逆方阵完全一致，只是 U 方阵对角线会有 n-r 个 0；
长方形（m, n）矩阵：方法和可逆方阵相似，只是 L、U 不为方阵，L 为（m, min(m,n)），U 为（min(m,n), n）。

Python 库中的 LU 分解

# 调用库
import numpy as np
from scipy.linalg import lu

# 定义矩阵
A = np.array([[3,1],
              [1,1],
              [6,2]])

# 默认使用 PLU 分解，并允许本文中的几种推广 LU 分解
P,L,U = lu(A)

考点

LU 分解求法

查看评论