LU decomposition

We will study a direct method for solving linear systems: the LU decomposition. Given a matrix A, the aim is to build a lower triangular matrix L and an upper triangular matrix which has the following property: diagonal elements of L are unity and A=LU.

Let $A$ be $n\times n$ matrix .$LU$ factorization is a procedure for decomposing $A$ into a product of a lower triangular matrix $L$(diagonal elements of L are unity) and an upper triangular matrix $U$such as $A=LU$ with

$$L=\left(\begin{array}{c}1\\ l_{21}& 1\\ ⋮& ⋮& \ddots \\ l_{n1}& l_{n2}& \cdots & 1\end{array}\right)$$

and

$$U=\left(\begin{array}{cccc}{u}_{11}& u_{12}& \cdots & u_{1n}\\ & u_{22}& \cdots & u_{2n}\\ & & \ddots & u_{n-1,n}\\ & & & u_{nn}\end{array}\right)$$

Solution of linear system

For the resolution of linear system : $Ax=b$, the system becomes

$$LUx=b\iff \{\begin{array}{cc}Ly=b& (1),\\ Ux=y& (2).\end{array}$$

We solve the system (1) to find the vector $y$, then the system (2) to find the vector $x$. The resolution is facilitated by the triangular shape of the matrices.

$$Ly=b\iff \{\begin{array}{ll}{y}_1=b_1/l_{11}& \\ y_i={\displaystyle \frac{1}{l_{ii}}(b_i-\sum _{j=1}^{i-1}{l}_{ij}{y}_j)}& \mathrm{\forall }i=2,3,\dots ,n.\end{array}$$ $$Ux=y\iff \{\begin{array}{ll}{x}_n=y_n/u_{nn}& \\ x_i={\displaystyle \frac{1}{u_{ii}}(y_i-\sum _{j=i+1}^n{u}_{ij}{x}_j)}& \mathrm{\forall }i=n-1,n-2,\dots ,1.\end{array}$$

Theorems

• if an LU factorization exists, then it is unique.
• An invertible matrix $A$ admits an LU factorization if and only if all its principal minors are non-zero (principal minor of order $k$ is the determiant of the matrix $(A{)}_{1\le i,j\le k}$ ).
• If $A$ is only invertible, then $A$ can be written $A=PLU,$ where $P$ is a permutation matrix.

LU Decomposition algorithm

We suppose that $A$ admits an LU factorization, the LU Decomposition algorithm is:

$$k=1,\dots ,n-1\{\begin{array}{lll}{l}_{ik}=0& i=1,\dots ,k-1& \\ l_{kk}=1& & \\ l_{ik}={\displaystyle \frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}}& i=k+1,\dots ,n& \\ a_{ij}^{(k+1)}=a_{ij}^{(k)}& i=1,\dots ,k& j=1,\dots ,n\\ a_{ij}^{(k+1)}=0& i=k+1,\dots ,n& j=1,\dots ,k\\ a_{ij}^{(k+1)}=a_{ij}^{(k)}-l_{ik}{a}_{kj}^{(k)}& i=k+1,\dots ,n& j=k+1,\dots ,n\end{array}$$ $$\begin{array}{lll}{l}_{in}=0& i=1,\dots ,n-1& l_{nn}=1\\ U=(a_{ij}^{(n)}{)}_{1\le i,j\le n}& L=(l_{ij}{)}_{1\le i,j\le n}& \end{array}$$

Calculating Matrix Determinant

The LU decomposition also makes it possible to calculate the determinant of $A$, which is equal to the product of the diagonal elements of the matrix $U$ if $A$ admits an LU factorization since

$$det(A)=det(L)\times det(U)=1\times det(U)=det(U)$$