LU decompose

LU Decomposition is a kind of matrix decomposition , Decompose a matrix into a Lower triangular matrix And a Upper triangular matrix The product of the , Sometimes you need to multiply by a permutation matrix .
LU Decomposition can be regarded as Gauss elimination Matrix form of . In numerical calculation ,LU Decomposition is often used to solve linear equations 、 And it is a key step in finding the inverse matrix and calculating the determinant .

One 、 Definition

For squares $A$,$A$ Of LU Decomposition is to decompose it into a lower triangular matrix L And upper triangular matrix U The product of the , That is to say $A=LU$.
For example, a $3\times 3$ Matrix $A$ , Its LU The decomposition will be written in the following form ：
$A=\left[\begin{array}{ccc}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33}\end{array}\right]=\left[\begin{array}{ccc}{l}_{11}& 0& 0\\ l_{21}& l_{22}& 0\\ l_{31}& l_{32}& l_{33}\end{array}\right]\left[\begin{array}{ccc}{u}_{11}& u_{12}& u_{13}\\ 0& u_{22}& u_{23}\\ 0& 0& u_{33}\end{array}\right]$

LDU decompose

Matrix A Of LDU Decomposition is to decompose it into a unit lower triangular matrix L、 Diagonal matrix D And unit upper triangular matrix U The product of the , namely $A=LDU$
Among them, the unit is 、 The lower triangular matrix means that the diagonal is full of 1 Above 、 Lower triangular matrix . in fact ,LDU Decomposition can be extended to A It's a general matrix , Not a square matrix .

Existence and uniqueness

1. One Invertible matrix Can be done LU Decompose if and only if its All subexpressions are nonzero .
2. If one of them is required L matrix （ or U matrix ） Is a unit triangular matrix , So decomposition is the only .
3. Even if the matrix is irreversible ,LU There may still be . actually , If a rank is k The front of the matrix k A sequential principal is not zero , Then it can LU decompose , But not the other way around .

Two 、 Algorithm

LU Decomposition is essentially an expression of Gauss elimination method . Is essentially take A It is transformed into an upper triangular matrix by elementary row transformation , Its transformation matrix is a unit lower triangular matrix . This is the so-called durritt algorithm （Doolittle algorithm）, From bottom to top, the matrix A Do elementary line transformation , Change the element at the bottom left of the diagonal to zero , Then it is proved that the effect of these row transformations is equivalent to left multiplying a series of unit lower triangular matrices , The inverse of the product of this series of unit lower triangular matrices is L matrix , It is also a unit lower triangular matrix .

Durritt algorithm

For given N × N matrix $A=(a_{n,n})$ Yes $A^{(0)}:=A$
Then define for $n=1,...,N-1$ The situation is as follows ：
In the n Step , Elimination matrix $A^{(n-1)}$ Of the n The elements below the main diagonal of the column ： take $A^{(n-1)}$ Of the n Line times $l_{i,n}=-\frac{a_{i,n}^{(n-1)}}{a_{n,n}^{(n-1)}}$ Then add to the second $i$ Go up . among $i=n+1,\dots ,N$. This is equivalent to $A^{(n-1)}$ Multiply the left side of by a unit lower triangular matrix ：

$L_n=\left[\begin{array}{cccccc}1& & & & & 0\\ & \ddots & & & & \\ & & 1& & & \\ & & l_{n+1,n}& \ddots & & \\ & & ⋮& & \ddots & \\ 0& & l_{N,n}& & & 1\end{array}\right]$

therefore , set up $A^{(n)}=L_n{A}^{(n-1)}$ after N-1 After wheel operation , All coefficients below the main diagonal are 0 了 , So we get an upper triangular matrix A(N-1), Then there is ：
$A=L_1^{-1}{L}_1{A}^{(0)}=L_1^{-1}{A}^{(1)}=L_1^{-1}{L}_2^{-1}{L}_2{A}^{(1)}=L_1^{-1}{L}_2^{-1}{A}^{(2)}=\dots =L_1^{-1}\dots L_{N-1}^{-1}{A}^{(N-1)}$
At this time , matrix $A^{(N-1)}$ Namely U,$L=L_1^{-1}\dots L_{N-1}^{-1}$. Lower triangular matrix $L_k$ The inverse of is still a lower triangular matrix , And the product of the lower triangular matrix is still the lower triangular matrix , therefore $L$ It's a lower triangular matrix . So we get to decompose ：$A=LU$.

obviously , If the algorithm works , In each step of operation, there must be $a_{n,n}^{(n-1)}\ne 0$. If this condition does not hold , It's going to take the first n One line exchanges with another , There will be a Permutation matrix P. That's why, in general LU The reason why there will be a permutation matrix in the decomposition .

Example ：
Put a simple 3×3 matrix A Conduct LU decompose ：

$A=\left[\begin{array}{ccc}1& 2& 3\\ 2& 5& 7\\ 3& 5& 3\end{array}\right]$
First, put the elements in the first column of the matrix $a_{11}$ All of the following elements become 0, namely
$L_{1}A=\left[\begin{array}{ccc}1& 0& 0\\ -2& 1& 0\\ -3& 0& 1\end{array}\right]\times \left[\begin{array}{ccc}1& 2& 3\\ 2& 5& 7\\ 3& 5& 3\end{array}\right]=\left[\begin{array}{ccc}1& 2& 3\\ 0& 1& 1\\ 0& -1& -6\end{array}\right]$
Then add the elements in the second column of the matrix $a_{22}$ All of the following elements become 0, namely
$L_2(L_{1}A)=\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 1& 1\end{array}\right]\times \left[\begin{array}{ccc}1& 2& 3\\ 0& 1& 1\\ 0& -1& -6\end{array}\right]=\left[\begin{array}{ccc}1& 2& 3\\ 0& 1& 1\\ 0& 0& -5\end{array}\right]=U$
$L=L_1^{-1}{L}_2^{-1}=\left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ 3& 0& 1\end{array}\right]\times \left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& -1& 1\end{array}\right]=\left[\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ 3& -1& 1\end{array}\right]$