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 c c c } 1\\ l_{21} & 1\\ \vdots & \vdots & \ddots\\ l_{n1} & l_{n2} & \cdots & 1 \end{array} \right)\]

and

\[U=\left( \begin{array}{c c c c } 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 \Leftrightarrow \left\{\begin{array}{cc} Ly = b& (1),\\ Ux = y &(2). \end{array}\right.\]

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 \Leftrightarrow \left\{\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) &\forall i=2,3,\ldots,n. \end{array}\right.\] \[Ux = y \Leftrightarrow \left\{\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) &\forall i=n-1,n-2,\ldots,1. \end{array}\right.\]

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\leq i,j\leq 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,\ldots,n-1\left\{ \begin{array}{l|ll} l_{ik}=0&i=1,\ldots,k-1 & \\ l_{kk}=1& & \\ l_{ik}=\displaystyle\frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}&i=k+1,\ldots,n & \\ a_{ij}^{(k+1)}=a_{ij}^{(k)}&i=1,\ldots,k & j=1,\ldots,n \\ a_{ij}^{(k+1)}=0 &i=k+1,\ldots,n & j=1,\ldots,k \\ a_{ij}^{(k+1)}=a_{ij}^{(k)}-l_{ik}a_{kj}^{(k)} & i=k+1,\ldots,n &j=k+1,\ldots,n \end{array}\right.\] \[\begin{array}{lll} l_{in}=0&i=1,\ldots,n-1&l_{nn}=1\\ U=(a^{(n)}_{ij})_{1\leq i,j\leq n}&L=(l_{ij})_{1\leq i,j\leq 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)\]