矩阵分解 -- LU

应用场景

LU分解可用于求解线性方程组和行列式，以及逆矩阵。

条件

若矩阵A为方阵( n\times n )且可逆(行列式不为0， det(A)\neq 0 )，则可以分解为下三角矩阵L和上三角矩阵U

A=LU

分解公式

上三角矩阵U

1
2
for i -> 0:nRow-1
  for j -> 0:nCol-1

U_{ij} = \begin{cases} A_{ij} - \sum^{i-1}_{k=0}L_{ik}U_{kj}, & \text{if $0<i<=j$} \\\\ A_{ij}, & \text{if $i==0$} \\\\ 0, & \text{if $i>j$} \end{cases}

下三角矩阵L

1
2
for j -> 0:nCol-1
  for i -> 0:nRow-1

L_{ij} = \begin{cases} \frac{A_{ij} - \sum^{j-1}_{k=0}L_{ik}U_{kj}}{U_{jj}}, & \text{if $i>j$} \\\\ 1, & \text{if $i=j$} \\\\ 0, & \text{if $i<j$} \end{cases}

通过分解，我们也可以获得逆矩阵 A^{-1}

A^{-1}=U^{-1}L^{-1}

逆矩阵分解公式

下三角逆矩阵 L^{-1} 

1
2
for j -> 0:nCol-1
  for i -> 0:nRow-1

L^{-1}_{ij} = \begin{cases} \frac{1}{L_{ij}}, & \text{if $i=j$} \\\\ -L^{-1}_{jj} * \sum^{i-1}_{k=j}L_{ik}L^{-1}_{kj}, & \text{if $i>j$} \\\\ 0, & \text{if $i<j$} \end{cases}

上三角逆矩阵 U^{-1} 

1
2
for i -> nRow-1:0
  for j -> nCol-1:0

U^{-1}_{ij} = \begin{cases} \frac{1}{U_{ij}}, & \text{if $i=j$} \\\\ -\frac{\sum^{j}_{k=i+1}U_{ik}U^{-1}_{kj}}{U^{-1}_{ii}}, & \text{if $i<j$} \\\\ 0, & \text{if $i>j$} \end{cases}

缺陷

LU分解对矩阵的限制比较大，不能应用于一般矩阵是其比较大的痛点。当然关于这一点，也是有解决方案的。
即，LU分解的变种:

1, LDU分解， A_{n\times m}=L_{n\times n}D_{n\times n}U_{n\times m} ，其中D为对角矩阵。
2, LUP分解， A_{n\times m}=L_{n\times n}U_{n\times n}P_{n\times m} 。

关于变种，此处不再赘述，后续会作详细讨论。

References:
[1] https://zh.m.wikipedia.org/zh-hans/LU%E5%88%86%E8%A7%A3

算法
#matrix fractorization #LU #矩阵分解 #线性代数
矩阵分解 -- LU
https://r-future.github.io/post/matrix-lu-factorization/
Author
Future
Posted on
July 13, 2022
Licensed under