luExample.tex

%
% Copyright © 2014 Peeter Joot.  All Rights Reserved.
% Licenced as described in the file LICENSE under the root directory of this GIT repository.
%
%\input{../blogpost.tex}
%\renewcommand{\basename}{luExample}
%\renewcommand{\dirname}{notes/ece1254/}
%%\newcommand{\dateintitle}{}
%%\newcommand{\keywords}{}
%
%\input{../peeter_prologue_print2.tex}
%
%\usepackage{kbordermatrix}
%
%\beginArtNoToc
%
%\generatetitle{Numeric LU factorization example}
%\chapter{Numeric LU factorization example}
%\label{chap:luExample}
%
Looking at a numeric example is helpful to get a better feel for LU factorization before attempting a Matlab implementation, as it strips some of the abstraction away.
%
\begin{equation}\label{eqn:luExample:20}
M =
\begin{bmatrix}
5 & 1 & 1 \\
2 & 3 & 4 \\
3 & 1 & 2 \\
\end{bmatrix}.
\end{equation}
%
This matrix was picked to avoid having to think of selecting the right pivot row when performing the \( L U \) factorization.  The first two operations give
%
\begin{equation}\label{eqn:luExample:40}
\kbordermatrix{
&  &   & \\
&5 & 1 & 1 \\
\lr{ r_2 \rightarrow r_2 - \frac{2}{5} r_1 } & 0 &13/5  & 18/5 \\
\lr{ r_3 \rightarrow r_3 - \frac{3}{5} r_1 } & 0 &2/5 & 7/5 \\
}.
\end{equation}
%
The row operations (left multiplication) that produce this matrix are
%
\begin{equation}\label{eqn:luExample:60}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
-3/5 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
-2/5 & 1 & 0 \\
0 & 0 & 1 \\
\end{bmatrix}
=
\begin{bmatrix}
1 & 0 & 0 \\
-2/5 & 1 & 0 \\
-3/5 & 0 & 1 \\
\end{bmatrix}.
\end{equation}
%
These operations happen to be commutative and also both invert simply.  The inverse operations are
\begin{equation}\label{eqn:luExample:80}
\begin{bmatrix}
1 & 0 & 0 \\
2/5 & 1 & 0 \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
3/5 & 0 & 1 \\
\end{bmatrix}
=
\begin{bmatrix}
1 & 0 & 0 \\
2/5 & 1 & 0 \\
3/5 & 0 & 1 \\
\end{bmatrix}.
\end{equation}
%
In matrix form the elementary matrix operations that produce the first stage of the Gaussian reduction are
%
\begin{equation}\label{eqn:luExample:100}
\begin{bmatrix}
1 & 0 & 0 \\
-2/5 & 1 & 0 \\
-3/5 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
5 & 1 & 1 \\
2 & 3 & 4 \\
3 & 1 & 2 \\
\end{bmatrix}
=
\begin{bmatrix}
5 & 1 & 1 \\
0 &13/5  & 18/5 \\
0 &2/5 & 7/5 \\
\end{bmatrix}.
\end{equation}
%
Inverted that is
%
\begin{equation}\label{eqn:luExample:120}
\begin{bmatrix}
5 & 1 & 1 \\
2 & 3 & 4 \\
3 & 1 & 2 \\
\end{bmatrix}
=
\begin{bmatrix}
1 & 0 & 0 \\
2/5 & 1 & 0 \\
3/5 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
5 & 1 & 1 \\
0 &13/5  & 18/5 \\
0 &2/5 & 7/5 \\
\end{bmatrix}.
\end{equation}
%
This is the first stage of the LU decomposition, although the U matrix is not yet in upper triangular form.  With the pivot row in the desired position already, the last row operation to perform is
%
\begin{equation}\label{eqn:luExample:140}
r_3 \rightarrow r_3 - \frac{2/5}{5/13} r_2 = r_3 - \frac{2}{13} r_2.
\end{equation}
%
The final stage of this Gaussian reduction is
%
\begin{equation}\label{eqn:luExample:160}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -2/13 & 1 \\
\end{bmatrix}
\begin{bmatrix}
5 & 1 & 1 \\
0 &13/5  & 18/5 \\
0 &2/5 & 7/5 \\
\end{bmatrix}
=
\begin{bmatrix}
5 & 1 & 1 \\
0 &13/5  & 18/5 \\
0 & 0 & 11/13 \\
\end{bmatrix}
= U,
\end{equation}
%
so the desired lower triangular matrix factor is
\begin{equation}\label{eqn:luExample:180}
\begin{bmatrix}
1 & 0 & 0 \\
2/5 & 1 & 0 \\
3/5 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 2/13 & 1 \\
\end{bmatrix}
=
\begin{bmatrix}
1 & 0 & 0 \\
2/5 & 1 & 0 \\
3/5 & 2/13 & 1 \\
\end{bmatrix}
= L.
\end{equation}
%
A bit of Matlab code easily verifies that the above manual computation recovers \( M = L U \)
%
\begin{verbatim}
l = [ 1 0 0 ; 2/5 1 0 ; 3/5 2/13 1 ] ;
u = [ 5 1 1 ; 0 13/5 18/5 ; 0 0 11/13 ] ;
m = l * u
\end{verbatim}
%
%\EndArticle
%\EndNoBibArticle