luExample2.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}{luExample2}
%\renewcommand{\dirname}{notes/ece1254/}
%%\newcommand{\dateintitle}{}
%%\newcommand{\keywords}{}
%
%\input{../peeter_prologue_print2.tex}
%
%\beginArtNoToc
%
%\generatetitle{Numerical LU example where pivoting is required}
%\chapter{Numerical LU example where pivoting is required}
%\label{chap:luExample2}
%
%Given some trouble understanding how to apply the LU procedure where pivoting is required.
Proceeding with a factorization where pivots are required, does not produce an LU factorization that is the product of a lower triangular matrix and an upper triangular matrix.  Instead what is found is what looks like a permutation of a lower triangular matrix with an upper triangular matrix.  As an example, consider the LU reduction of
%
\begin{equation}\label{eqn:luExample2:20}
M \Bx =
\begin{bmatrix}
0 & 0 & 1 \\
2 & 0 & 4 \\
1 & 1 & 1
\end{bmatrix}
\begin{bmatrix}
x_1 \\
x_2 \\
x_3 \\
\end{bmatrix}.
\end{equation}
%
Since \( r_2 \) has the biggest first column value, that is the row selected as the pivot
%
\begin{equation}\label{eqn:luExample2:40}
M \Bx \rightarrow M' \Bx'
=
\begin{bmatrix}
2 & 0 & 4 \\
0 & 0 & 1 \\
1 & 1 & 1
\end{bmatrix}
\begin{bmatrix}
x_2 \\
x_1 \\
x_3 \\
\end{bmatrix}.
\end{equation}
%
This permutation can be expressed algebraically as a row permutation matrix operation
%
\begin{equation}\label{eqn:luExample2:60}
M' =
\begin{bmatrix}
0 & 1 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1
\end{bmatrix}
M.
\end{equation}
%
With the pivot permutations out of the way, the row operations remaining for the Gaussian reduction of this column are
%
\begin{equation}\label{eqn:luExample2:80}
\begin{aligned}
r_2 & \rightarrow r_2 - \frac{0}{2} r_1 \\
r_3 & \rightarrow r_3 - \frac{1}{2} r_1 \\
\end{aligned},
\end{equation}
%
which gives
%
\begin{equation}\label{eqn:luExample2:100}
\begin{aligned}
M_1 &=
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
-1/2 & 0 & 1
\end{bmatrix}
M'
\\ &=
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
-1/2 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
2 & 0 & 4 \\
0 & 0 & 1 \\
1 & 1 & 1
\end{bmatrix}
\\ &=
\begin{bmatrix}
2 & 0 & 4 \\
0 & 0 & 1 \\
0 & 1 & -1
\end{bmatrix}.
\end{aligned}
\end{equation}
%
Application of one more permutation operation gives the desired upper triangular matrix
%
\begin{equation}\label{eqn:luExample2:120}
\begin{aligned}
U &= M_1' \\ &=
\begin{bmatrix}
1 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 0 \\
\end{bmatrix}
\begin{bmatrix}
2 & 0 & 4 \\
0 & 0 & 1 \\
0 & 1 & -1
\end{bmatrix}
\\ &=
\begin{bmatrix}
2 & 0 & 4 \\
0 & 1 & -1 \\
0 & 0 & 1
\end{bmatrix}.
\end{aligned}
\end{equation}
%
This new matrix operator applies to the permuted vector
%
\begin{equation}\label{eqn:luExample2:140}
\Bx'' =
\begin{bmatrix}
x_2 \\
x_3 \\
x_1 \\
\end{bmatrix}.
\end{equation}
%
The matrix \( U \) has been constructed by the following row operations
%
\begin{equation}\label{eqn:luExample2:160}
U =
\begin{bmatrix}
1 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 0 \\
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
-1/2 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
0 & 1 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1 \\
\end{bmatrix}
M.
\end{equation}
%
\( L U = M \) is sought, or
%
\begin{equation}\label{eqn:luExample2:180}
L
\begin{bmatrix}
1 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 0 \\
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
-1/2 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
0 & 1 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1 \\
\end{bmatrix}
M
= M,
\end{equation}
%
or
%
\begin{equation}\label{eqn:luExample2:200}
\begin{aligned}
L
&=
\begin{bmatrix}
0 & 1 & 0 \\
1 & 0 & 0 \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 1 & 0 \\
1/2 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 0 \\
\end{bmatrix}
\\ &=
\begin{bmatrix}
0 & 1 & 0 \\
1 & 0 & 0 \\
1/2 & 0 & 1
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
0 & 0 & 1 \\
0 & 1 & 0 \\
\end{bmatrix}
\\ &=
\begin{bmatrix}
0 & 0 & 1 \\
1 & 0 & 0 \\
1/2 & 1 & 0
\end{bmatrix}.
\end{aligned}
\end{equation}
%
The \( L U \) factorization attempted does not appear to produce a lower triangular factor, but a permutation of a lower triangular factor?
%
When such pivoting is required it isn't obvious, at least to me, how to do the clever \( L U \) algorithm that outlined in class.  How can the operations be packed into the lower triangle when there is a requirement to actually have to apply permutation matrices to the results of the last iteration?
%
It seems that a \( LU \) decomposition of \( M \) cannot be performed, but an \( L U \) factorization of \( P M \), where \( P \) is the permutation matrix for the permutation \( 2,3,1 \) that was applied to the rows during the Gaussian operations.
%
Checking that \( L U \) factorization:
%
\begin{equation}\label{eqn:luExample2:220}
P M =
\begin{bmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0 \\
\end{bmatrix}
\begin{bmatrix}
0 & 0 & 1 \\
2 & 0 & 4 \\
1 & 1 & 1
\end{bmatrix}
=
\begin{bmatrix}
2 & 0 & 4 \\
1 & 1 & 1 \\
0 & 0 & 1 \\
\end{bmatrix}.
\end{equation}
%
The elementary row operation to be applied is
%
\begin{equation}\label{eqn:luExample2:240}
r_2 \rightarrow r_2 - \frac{1}{2} r_1,
\end{equation}
%
for
%
\begin{equation}\label{eqn:luExample2:260}
\lr{P M}_1 =
\begin{bmatrix}
2 & 0 & 4 \\
0 & 1 & -1 \\
0 & 0 & 1 \\
\end{bmatrix},
\end{equation}
%
The \( L U \) factorization is therefore
%
\begin{equation}\label{eqn:luExample2:280}
P M =
L U =
\begin{bmatrix}
1 & 0 & 0 \\
1/2 & 1 & 0 \\
0 & 0 & 1 \\
\end{bmatrix}
\begin{bmatrix}
2 & 0 & 4 \\
0 & 1 & -1 \\
0 & 0 & 1 \\
\end{bmatrix}.
\end{equation}
%
Observe that this can also be written as
%
\begin{equation}\label{eqn:luExample2:300}
M = \lr{ P^{-1} L } U.
\end{equation}
%
The inverse permutation is a \( 3,1,2 \) permutation matrix
%
\begin{equation}\label{eqn:luExample2:320}
P^{-1} =
\begin{bmatrix}
0 & 0 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0 \\
\end{bmatrix}.
\end{equation}
%
It can be observed that the product \( P^{-1} L \) produces the not-lower-triangular matrix factor found earlier in \cref{eqn:luExample2:200}.
%
%\EndArticle
%\EndNoBibArticle