线代--矩阵的分解-LU分解n阶方阵

矩阵分解的概念：初中我们接触过数的分解,如: $\ \ 66 = 3*3*11(\color{skyblue} {\small 质因数分解})$ ;推广到矩阵，一个矩阵也可以分解为几个矩阵乘积的形式，矩阵分解具有不同的目的。

矩阵的LU分解的定义是将矩阵 $A$ 分解为一个下三角矩阵( $\small 矩阵的有效信息都在下三角区域$ )和上三角矩阵( $\small 矩阵的有效信息都在上三角区域$ )乘积的方式: $\begin{aligned} &A = L \cdot U \end{aligned}$ ，其目的是为了提高计算效率。

L:Lower Triangle Matrix $\ \ \ \$ U:Upper Triangle Matrix
$\ \ \color{red} {\small 下三角单位矩阵} \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$ 上三角矩阵
$\begin{bmatrix} 1&0&0&0 \\ *&1&0&0 \\ *&*&1&0 \\ *&*&*&1\end{bmatrix} \ \ \ \ \ \ \ \ \ \ \ \begin{bmatrix} *&*&*&* \\ 0&*&*&* \\ 0&0&*&* \\ 0&0&0&*\end{bmatrix}$
在LU分解中，通常将一个矩阵分解成一个下三角单位矩阵和一个上三角矩阵(不保证对角线为 $1$ )

联系"高斯消元"过程:系数矩阵和结果矩阵拼接成的增广矩阵通过一系列初等变换，就是把一个矩阵变成了上三角矩阵的过程。即

E_{p}\cdot ... \cdot E_{3} \cdot E_{2} \cdot E_{1} \cdot A =U

根据这条式子进行拓展有:

\because (E_{p}^{-1}\cdot ... \cdot E_{3}^{-1} \cdot E_{2}^{-1} \cdot E_{1}^{-1})\cdot (E_{p}\cdot ... \cdot E_{3} \cdot E_{2} \cdot E_{1} )\cdot A = (E_{p}^{-1}\cdot ... \cdot E_{3}^{-1} \cdot E_{2}^{-1} \cdot E_{1}^{-1})\cdot U

\therefore I \cdot A = (E_{p}^{-1}\cdot ... \cdot E_{3}^{-1} \cdot E_{2}^{-1} \cdot E_{1}^{-1})\cdot U

从中可以看出，高斯消元过程的逆操作变换矩阵就是下三角矩阵

L

：

\therefore A=L\cdot U \color{red}{\to} L= (E_{p}^{-1}\cdot ... \cdot E_{3}^{-1} \cdot E_{2}^{-1} \cdot E_{1}^{-1})

一个矩阵可以进行LU分解的前提条件：对矩阵 $A$ 的消元过程中不能涉及行交换操作(只有主元位置为0的矩阵在高斯消元过程需要进行行变换)。因为分解得到的 $L$ 矩阵是由单位矩阵得到的，如果消元过程发生了行交换，也就意味着单位矩阵发生了行交换，对应的L矩阵就不是一个下三角矩阵。
证明如下：

假设矩阵 $A= \begin{bmatrix} 0&1 \\ 1&1 \end{bmatrix}$ 可以进行LU分解。
根据LU分解的定义,则矩阵 $A$ 可以分解得到一个下三角矩阵 $L$ 和一个上三角矩阵 $U$
$令 \ L= \begin{bmatrix} l_{11}&0 \\ l_{21}& l_{22} \end{bmatrix} and \ \begin{bmatrix} u_{11}&u_{12} \\ 0& u_{22} \end{bmatrix}$
通过矩阵乘法，可以得出
$\because a_{11} = l_{11} \cdot u_{11}=0, 所以必然存在 l_{11}=0 \ 或 \ u_{11} =0$
${\small 如果是}l_{11}=0 ，{\small 那么就有}a_{12}=l_{11} \cdot u_{12} = 0，{\small 然而这就与矩阵}A 中a_{12}=1{\small 的结果相矛盾}$ .
${\small 如果是}u_{11}=0 ，{\small 那么就有}a_{21}=l_{21} \cdot u_{11} = 0，{\small 然而这就与矩阵}A 中a_{21}=1{\small 的结果相矛盾}$ .
$\therefore{\small \textbf{综上，矩阵A不能进行LU分解} }$

当一个矩阵不用发生行交换进行消元过程的时候，那么对应获取它的 $L$ 矩阵直接可以通过 $E$ 矩阵取反得到，发生行交换后， $L$ 矩阵不能直接由 $E$ 矩阵取反得到。

对于主元位置为零的矩阵（也就是发生行交换才能进行LU分解的矩阵，可以使用PLU分解方法 $A=P\cdot L \cdot U$ ，P矩阵是置换矩阵）

$LU$ 分解的时间复杂度的计算 $\ \ \ O(0.5n^{3})$
其中 $n$ 是矩阵 $A_{n*n}$ 下三角区域需要化为 $0$ 的元素的个数(一共约为 $\frac {1}{2}n^{2}$ 个)，完成这些元素的消元约需要进行 $\frac {1}{2}n^{2}$ 次初等变换，而每次初等变换意味着对矩阵内一行的 $n$ 个元素都进行了一次运算，所以由 $A \to U$ 高斯消元过程总共约发生了 $0.5n^{2} \cdot n$ 次数据运算}, $bigO$ 时间复杂度约为 $O(0.5n^{3})$ 。由于高斯消元过程在得到 $U$ 矩阵的同时，每次初等变换操作的值取反往单位矩阵 $I$ 相应的位置进行填充就可以得到 $L$ 矩阵，所以整体上 $LU$ 分解过程的时间消耗近乎等于 $A \to U$ 过程的时间。

$LU$ 分解加速线性系统求解

对于解线性系统 $Ax=b$
$\small{ 矩阵A被分解为A=L\cdot U}$
$\to L \cdot U \cdot x =b$
设 $Ux=y$ , 方程变为 $L \cdot y =b$ ,求出 $y$ 的时间复杂度约为 $O(n^2)$ 。
同样，对于 $U\cdot x$ ,求出 $x$ 的时间复杂度也约为 $O(n^{2})$
从而，将矩阵 $A$ 通过 $LU$ 分解，时间复杂度总体为 $O(0.5n^{3}) + 2O(n^{2})$

$LU$ 分解计算时间复杂度相比求解矩阵的逆的过程求解 $A\cdot x=b \to x = A^{-1}\cdot b$ .
矩阵通过增广矩阵的形式求逆的时间复杂度为 $O{2n^{3}}$ ，增广矩阵有 $2n^{2}$ 个元素要执行消元操作。然后再求解 $A^{-1}\cdot b$ 的时间复杂度有 $O(n^2)$ 次操作，所以通过矩阵的逆的方法求解线性系统的时间复杂度为 $O(2n^{3})+O(n^2) \gt O(0.5n^{3}) + 2O(n^{2})$ 。

综上，LU分解求解线性系统的效率是比较高的。

简单LU过程的python写法

import numpy as np
A = np.array([[1,2,3],[4,5,6],[3,-3,5]]) ### 创建一个用于分解的测试矩阵
L = [[1.0 if i==j else 0 for i in range(n)] for j in range(n)] ### 初始化L矩阵为单位矩阵
n = len(A) ### 创建变量n记录矩阵的行数
for i in range(n): #行遍历
    for j in range(i+1,n): #处理主元行下面的所有行化为0
        p = A[j][i] / A[i][i] ##求算主元行下面行主元列位置的元素是当前主元的倍数
        A[j] = A[j] - p*A[i] ##主元行下面行主元列位置的元素减去p倍主元化为0
        L[j][i] = p ### p直接填充到L矩阵
L

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 203,098评论 5赞 476
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 85,213评论 2赞 380
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 149,960评论 0赞 336
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 54,519评论 1赞 273
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 63,512评论 5赞 364
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 48,533评论 1赞 281
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 37,914评论 3赞 395
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 36,574评论 0赞 256
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 40,804评论 1赞 296
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 35,563评论 2赞 319
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 37,644评论 1赞 329
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,350评论 4赞 318
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 38,933评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 29,908评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,146评论 1赞 259
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 42,847评论 2赞 349
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,361评论 2赞 342

线代--矩阵的分解-LU分解n阶方阵

分解加速线性系统求解

简单LU过程的python写法

推荐阅读更多精彩内容

$LU$ 分解加速线性系统求解