| Version 5 |
Version 4 |
| \begin{definition} |
\begin{definition} |
| Let $A$ be an $n\times m$ matrix. An LU factorization of $A$, if it |
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 |
exists, is an $n\times n$ unit lower triangular matrix $L$ and an |
| $n\times m$ matrix U, in (upper) echelon form, such that |
$n\times m$ matrix U, in (upper) echelon form, such that |
| \[ A = LU \] |
\[ A = LU \] |
| \end{definition} |
\end{definition} |
| The LU factorization is closely related to the row reduction |
The LU factorization is closely related to the row reduction |
| algorithm. In a very real sense, the factorization is a record of the |
algorithm. In a very real sense, the factorization is a record of the |
| steps taken in row reducing a matrix to echelon form. The matrix |
steps taken in row reducing a matrix to echelon form. The matrix |
| $L$ ``encodes'' the sequence of row replacement operations that row |
$L$ ``encodes'' the sequence of row replacement operations that row |
| reduce the given matrix $A$ to echelon form $U$. |
reduce the given matrix $A$ to echelon form $U$. |
| \begin{proposition} |
\begin{proposition} |
| Suppose that $A=LU$ is an LU factorization, and let $L_{ij}$ denote |
Suppose that $A=LU$ is an LU factorization, and let $L_{ij}$ denote |
| the entries of $L$. Then, the row reduction |
the entries of $L$. Then, the row reduction |
| $A\stackrel{\rho}{\Longrightarrow} U$ is accomplished by the |
$A\stackrel{\rho}{\Longrightarrow} U$ is accomplished by the |
| following sequence $\rho$ of $\tfrac{1}{2}n(n-1)$ row replacement |
following sequence $\rho$ of $\tfrac{1}{2}n(n-1)$ row replacement |
| operations: |
operations: |
| \begin{align*} |
\begin{align*} |
| \hskip 2em & \row_j \mapsto \row_j-L_{j1}\; \row_1,\quad |
\hskip 2em & \row_j \mapsto \row_j-L_{j1}\; \row_1,\quad |
| j=2,\ldots, n;\\ |
j=2,\ldots, n;\\ |
| & \row_j \mapsto \row_j-L_{j2}\; \row_2,\quad j=3,\ldots, n;\\ |
& \row_j \mapsto \row_j-L_{j2}\; \row_2,\quad j=3,\ldots, n;\\ |
| & \hskip 3em \vdots \\ |
& \hskip 3em \vdots \\ |
| & \row_j \mapsto \row_j-L_{jk}\; \row_k,\quad j=k+1,\ldots, |
& \row_j \mapsto \row_j-L_{jk}\; \row_k,\quad j=k+1,\ldots, |
| n,\quad k=1,\ldots,n-1 \\ |
n,\quad k=1,\ldots,n-1 \\ |
| & \hskip 3em \vdots |
& \hskip 3em \vdots |
| \end{align*} |
\end{align*} |
| \end{proposition} |
\end{proposition} |
| Note: the first $n-1$ steps clear out column $1$, the next $n-2$ steps |
Note: the first $n-1$ steps clear out column $1$, the next $n-2$ steps |
| clear out column $2$, etc. |
clear out column $2$, etc. |
| \begin{proposition} |
\begin{proposition} |
| Not every matrix admits an LU factorization. Indeed, an LU |
Not every matrix admits an LU factorization. Indeed, an LU |
| factorization exists if and only if $A$ can be reduced to echelon |
factorization exists if and only if $A$ can be reduced to echelon |
| without using row exchange operations. However, if an LU |
without using row exchange operations. However, if an LU |
| factorization exists, then it is unique. |
factorization exists, then it is unique. |
| \end{proposition} |
\end{proposition} |
|
|
|
|
| In the most general case, one has to employ row exchange operations. |
In the most general case, one has to employ row exchange operations. |
| \begin{proposition} |
\begin{proposition} |
| Let $A$ be an $n\times m$ matrix. Then, there exists an $n\times n$ |
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$ |
permutation matrix $P$ (indeed, many such) such that the matrix $PA$ |
| admits an LU factorization, i.e., there exist matrices $P, L, U$ |
admits an LU factorization, i.e., there exist matrices $P, L, U$ |
| such that |
such that |
| \[ PA=LU. \] |
\[ PA=LU. \] |
| \end{proposition} |
\end{proposition} |
| The key idea behind LU factorization is that one does not need to |
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 |
employ row scalings to do row reduction until the second half (the |
| back-substitution phase) of the algorithm. This has significant |
back-substitution phase) of the algorithm. This has significant |
| implication for numerical stability of the algorithm. |
implication for numerical stability of the algorithm. |
|
|
| The LU decomposition of a given matrix $A$ is useful for the solution |
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 |
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 |
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, |
the system $Ux=y$. This two-step procedure is easy to implement, |
| because owing to the lower and upper-triangular nature of the |
because owing to the lower and upper-triangular nature of the |
| matrices $L$ and $U$, the required row operations are determined, more |
matrices $L$ and $U$, the required row operations are determined, more |
| or less, directly from the entries of $L$ and $U$. Indeed, the first |
or less, directly from the entries of $L$ and $U$. Indeed, the first |
| step, |
step, |
| \[ [\, L\; b\, ] \stackrel{\rho_1}{\Longrightarrow} [\, I \; y \,] \] |
\[ [\, L\; b\, ] \stackrel{\rho_1}{\Longrightarrow} [\, I \; y \,] \] |
| a sequence of row operations $\rho_1$, and the second step |
a sequence of row operations $\rho_1$, and the second step |
| \[ [\, U\; y\, ] \stackrel{\rho_2}{\Longrightarrow} [\, E \; x_0 \,] \] |
\[ [\, U\; y\, ] \stackrel{\rho_2}{\Longrightarrow} [\, E \; x_0 \,] \] |
| a sequence of row operations $\rho_2$, are exactly the same row operations |
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$: |
one has to perform to row reduce $A$ directly to reduced echelon form $E$: |
| \[ |
\[ |
| [\, A\; b\, ] \stackrel{\rho_1}{\Longrightarrow} [\, U\; y \, ] |
[\, A\; b\, ] \stackrel{\rho_1}{\Longrightarrow} [\, U\; y \, ] |
| \stackrel{\rho_2}{\Longrightarrow} [\, E\; x_0 \, ] . |
\stackrel{\rho_2}{\Longrightarrow} [\, E\; x_0 \, ] . |
| \] |
\] |
| Note: $x_0$ is the particular solution of $Ax=b$ that sits in the |
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 |
rightmost colulmn of the augmented matrix at the termination of the |
| row-reduction algorithm. |
row-reduction algorithm. |
