Skip to main content

Unit 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*}
Figure 5.1.1.1. Algorithm that overwrites \(A\) with its LU factorization.
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 \(\hat 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) = \hat A . \end{equation*}