Math-Linux.com

Knowledge base dedicated to Linux and applied mathematics.

Home > Mathematics > Linear Systems > LU decomposition

LU decomposition

All the versions of this article: [English] [français]

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 Usuch 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)

Any message or comments?

comments powered by Disqus