Subsection 5.1.1 Of Gaussian elimination and LU factorization
ΒΆHomework 5.1.1.1.
Reduce the appended system
\begin{equation*}
\begin{array}{r r r | r}
2 \amp -1 \amp 1 \amp 1 \\
-2 \amp 2 \amp 1 \amp -1 \\
4 \amp -4 \amp \phantom{-}1 \amp 5
\end{array}
\end{equation*}
to upper triangular form, overwriting the zeroes that are introduced with the multipliers.
Solution
\begin{equation*}
\begin{array}{r r r | r}
2 \amp -1 \amp 1 \amp 1 \\
-1 \amp 1 \amp 2 \amp 0 \\
2 \amp -2 \amp \phantom{-}3 \amp \phantom{-}3
\end{array}
\end{equation*}
\begin{equation*}
\newcommand{\routinename}{A = \mbox{LU}( A )}
\newcommand{\guard}{
n( A_{TL} ) \lt n( A )
}
\newcommand{\partitionings}{
A \rightarrow
\FlaTwoByTwo{A_{TL}}{A_{TR}}
{A_{BL}}{A_{BR}}
}
\newcommand{\partitionsizes}{
A_{TL} {\rm ~is~} 0 \times 0
}
\newcommand{\repartitionings}{
\FlaTwoByTwo{A_{TL}}{A_{TR}}
{A_{BL}}{A_{BR}}
\rightarrow
\FlaThreeByThreeBR{A_{00}}{a_{01}}{A_{02}}
{a_{10}^T}{\alpha_{11}}{a_{12}^T}
{A_{20}}{a_{21}}{A_{22}}
}
\newcommand{\moveboundaries}{
\FlaTwoByTwo{A_{TL}}{A_{TR}}
{A_{BL}}{A_{BR}}
\leftarrow
\FlaThreeByThreeTL{A_{00}}{a_{01}}{A_{02}}
{a_{10}^T}{\alpha_{11}}{a_{12}^T}
{A_{20}}{a_{21}}{A_{22}}
}
\newcommand{\update}{
\begin{array}{l}
a_{21} := a_{21} / \alpha_{11} \\
A_{22} := A_{22} - a_{21} a_{12}^T
\end{array}
}
\FlaAlgorithm
\end{equation*}
Homework 5.1.1.2.
The execution of the LU factorization algorithm with
\begin{equation*}
A =
\left(
\begin{array}{r r r }
2 \amp -1 \amp 1 \\
-2 \amp 2 \amp 1 \\
4 \amp -4 \amp \phantom{-}1 \\
\end{array} \right)
\end{equation*}
in the video overwrites \(A \) with
\begin{equation*}
\left(
\begin{array}{r r r }
2 \amp -1 \amp 1 \\
-1 \amp 1 \amp 2 \\
2 \amp -2 \amp \phantom{-}3
\end{array} \right).
\end{equation*}
Multiply the \(L \) and \(U \) stored in that matrix and compare the result with the original matrix, let's call it \(\widehat A \text{.}\)
Solution
\begin{equation*}
L =
\left(
\begin{array}{r r r }
1 \amp 0 \amp 0 \\
-1 \amp 1 \amp 0 \\
2 \amp -2 \amp \phantom{-}1
\end{array} \right)
\mbox{ and }
U =
\left(
\begin{array}{r r r }
2 \amp -1 \amp 1 \\
0 \amp 1 \amp 2 \\
0 \amp 0 \amp \phantom{-}3
\end{array} \right).
\end{equation*}
\begin{equation*}
L U =
\left(
\begin{array}{r r r }
1 \amp 0 \amp 0 \\
-1 \amp 1 \amp 0 \\
2 \amp -2 \amp \phantom{-}1
\end{array} \right)
\left(
\begin{array}{r r r }
2 \amp -1 \amp 1 \\
0 \amp 1 \amp 2 \\
0 \amp 0 \amp \phantom{-}3
\end{array} \right)
=
\left(
\begin{array}{r r r }
2 \amp -1 \amp 1 \\
-2 \amp 2 \amp 1 \\
4 \amp -4 \amp \phantom{-}1 \\
\end{array} \right) = \widehat A
.
\end{equation*}