Linear Algebra - LU Decomposition

LU Decomposition

Divide a matrix to L(lower triangular matrix) and U(upper triangular matrix), such that A = LU
unit lower triangular matrix L : a square matrix with diagonal equals to 1 and elements above diagonal are all zeros; lower triangular matrix: a square matrix with elements above diagonal are all zero, diagonal not necessary be 1
upper triangular matrix: a square matrix with diagonal below are all zeros; If the diagonal of upper triangular matrix is 1, then it is unit upper triangular matrix

$$\begin{array}{rl}Ax=LUx\to & L=\left[\begin{array}{ccc}1& 0& 0\\ l_{21}& 1& 0\\ l_{31}& l_{32}& 1\end{array}\right],U=\left[\begin{array}{ccc}{u}_{11}& u_{12}& u_{13}\\ 0& u_{22}& u_{23}\\ 0& 0& u_{33}\end{array}\right]\end{array}$$ $$\begin{array}{rl}& a_{11}{x}_1+a_{12}{x}_2+a_{13}{x}_3=b_1\\ & a_{21}{x}_1+a_{22}{x}_2+a_{23}{x}_3=b_2\\ & a_{31}{x}_1+a_{32}{x}_2+a_{33}{x}_3=b_3\end{array}$$

These can be written in the form of $AX=B$ as:

$$\left[\begin{array}{lll}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33}\end{array}\right]\left[\begin{array}{l}{x}_1\\ x_2\\ x_3\end{array}\right]=\left[\begin{array}{l}{b}_1\\ b_2\\ b_3\end{array}\right]$$

Here,

$$A=\left[\begin{array}{lll}{a}_{11}& a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31}& a_{32}& a_{33}\end{array}\right],X=\left[\begin{array}{l}{x}_1\\ x_2\\ x_3\end{array}\right],B=\left[\begin{array}{l}{b}_1\\ b_2\\ b_3\end{array}\right]$$

1. find U(REF, Gaussian Elimination)
2. find L, look at the multipliers that are used to eliminate entries below the main diagonal when transforming A into U.

$$A=\left[\begin{array}{l}4,3\\ 6,3\end{array}\right]$$

To transform A into an upper triangular matrix U, we eliminate the 6 in the position a21​ by subtract 1.5 times Row 1 from the Row 2

$$L=\left[\begin{array}{c}1,0\\ 1.5,1\end{array}\right]$$

3. set LZ = B to get Z
4. set Ux=Z to get x

Example of 4x4 matrix: