| Version 4 |
Version 3 |
| \begin{definition} |
Any non-singular matrix $A$ can be expressed as a product $A = LU$; there exists exactly one lower triangular matrix $L$ and exactly one upper triangular matrix $U$ of the form: |
| Let $A$ be an $n\times m$ matrix. An LU factorization of $A$, if it |
|
| exists, is an $n\times n$ unit lower triangular matrix $L$ and an |
$$ A = |
| $n\times m$ matrix U, in (upper) echelon form, such that |
\begin{bmatrix} |
| \[ A = LU \] |
a_{11} & a_{12} & \cdots & a_{1n} \\ |
| \end{definition} |
a_{21} & a_{22} & \cdots & a_{2n} \\ |
| The LU factorization is closely related to the row reduction |
\vdots & \vdots & \; & \vdots \\ |
| algorithm. In a very real sense, the factorization is a record of the |
a_{n1} & a_{n2} & \cdots & a_{nn} |
| steps taken in row reducing a matrix to echelon form. The matrix |
\end{bmatrix} = \begin{bmatrix} |
| $L$ ``encodes'' the sequence of row replacement operations that row |
1 & 0 & \cdots & 0 \\ |
| reduce the given matrix $A$ to echelon form $U$. |
l_{21} & 1 & \cdots & 0 \\ |
| \begin{proposition} |
\vdots & \vdots & \ddots & \vdots \\ |
| Suppose that $A=LU$ is an LU factorization, and let $L_{ij}$ denote |
l_{n1} & l_{n2} & \cdots & 1 |
| the entries of $L$. Then, the row reduction |
\end{bmatrix} |
| $A\stackrel{\rho}{\Longrightarrow} U$ is accomplished by the |
\begin{bmatrix} |
| following sequence $\rho$ of $\tfrac{1}{2}n(n-1)$ row replacement |
u_{11} & u_{12} & \cdots & u_{1n} \\ |
| operations: |
0 & a_{22} & \cdots & u_{2n} \\ |
| \begin{align*} |
\vdots & \vdots & \ddots & \vdots \\ |
| \hskip 2em & \row_j \mapsto \row_j-L_{j1}\; \row_1,\quad |
0 & 0 & \cdots & u_{nn} |
| j=2,\ldots, n;\\ |
\end{bmatrix} $$ |
| & \row_j \mapsto \row_j-L_{j2}\; \row_2,\quad j=3,\ldots, n;\\ |
|
| & \hskip 3em \vdots \\ |
if row exchanges (partial pivoting) are not necessary. With pivoting, we have to introduce a permutation matrix $P$. Instead of $A$ one then decomposes $PA$: |
| & \row_j \mapsto \row_j-L_{jk}\; \row_k,\quad j=k+1,\ldots, |
|
| n,\quad k=1,\ldots,n-1 \\ |
$$ PA = LU $$ |
| & \hskip 3em \vdots |
|
| \end{align*} |
The LU decomposition can be performed in a way similar to Gaussian elimination. |
| \end{proposition} |
|
| Note: the first $n-1$ steps clear out column $1$, the next $n-2$ steps |
LU decomposition is useful, e.g. for the solution of the exactly determined system of linear equations $Ax = b$, when there is more than one right-hand side $b$. With $A = LU$ the system becomes |
| clear out column $2$, etc. |
|
| \begin{proposition} |
$$ LUx = b $$ |
| Not every matrix admits an LU factorization. Indeed, an LU |
|
| factorization exists if and only if $A$ can be reduced to echelon |
or |
| without using row exchange operations. However, if an LU |
|
| factorization exists, then it is unique. |
$$ Lc = b \;\text{and}\; Ux = c $$ |
| \end{proposition} |
|
|
$c$ can be computed by forward substitution and $x$ by back substitution. |
|
|
| In the most general case, one has to employ row exchange operations. |
|
| \begin{proposition} |
|
| Let $A$ be an $n\times m$ matrix. Then, there exists an $n\times n$ |
|
| permutation matrix $P$ (indeed, many such) such that the matrix $PA$ |
|
| admits an LU factorization, i.e., there exist matrices $P, L, U$ |
|
| such that |
|
| \[ PA=LU. \] |
|
| \end{proposition} |
|
| The key idea behind LU factorization is that one does not need to |
|
| employ row scalings to do row reduction until the second half (the |
|
| back-substitution phase) of the algorithm. This has significant |
|
| implication for numerical stability of the algorithm. |
|
|
|
| The LU decomposition of a given matrix $A$ is useful for the solution |
|
| of the systems of linear equations of the form $Ax = b$. Indeed, it |
|
| suffices to first solve the linear system $Ly=b$, and second, to solve |
|
| the system $Ux=y$. This two-step procedure is easy to implement, |
|
| because owing to the lower and upper-triangular nature of the |
|
| matrices $L$ and $U$, the required row operations are determined, more |
|
| or less, directly from the entries of $L$ and $U$. Indeed, the first |
|
| step, |
|
| \[ [\, L\; b\, ] \stackrel{\rho_1}{\Longrightarrow} [\, I \; y \,] \] |
|
| a sequence of row operations $\rho_1$, and the second step |
|
| \[ [\, U\; y\, ] \stackrel{\rho_2}{\Longrightarrow} [\, E \; x_0 \,] \] |
|
| a sequence of row operations $\rho_2$, are exactly the same row operations |
|
| one has to perform to row reduce $A$ directly to reduced echelon form $E$: |
|
| \[ |
|
| [\, A\; b\, ] \stackrel{\rho_1}{\Longrightarrow} [\, U\; y \, ] |
|
| \stackrel{\rho_2}{\Longrightarrow} [\, E\; x_0 \, ] . |
|
| \] |
|
| Note: $x_0$ is the particular solution of $Ax=b$ that sits in the |
|
| rightmost colulmn of the augmented matrix at the termination of the |
|
| row-reduction algorithm. |
|
