Skip to main content

Subsection 5.2.4 Gaussian elimination via Gauss transforms

Definition 5.2.4.1.
A matrix \(L_k \) of the form
\begin{equation*} L_k = \FlaThreeByThreeBR { I_k }{ 0 }{ 0 } { 0 }{ 1 }{ 0 } { 0 }{ l_{21} }{ I }, \end{equation*}
where \(I_k \) is the \(k \times k \) identity matrix and \(I \) is an identity matrix "of appropriate size" is called a Gauss transform.

Gauss transforms, when applied to a matrix, take multiples of the row indexed with \(k \) and add these multiples to other rows. In our use of Gauss transforms to explain the LU factorization, we subtract instead:

Example 5.2.4.2.

Evaluate

\begin{equation*} \left( \begin{array}{c | c c c } 1 \amp 0 \amp 0 \amp 0 \\ \hline 0 \amp 1 \amp 0 \amp 0 \\ 0 \amp - \lambda_{21} \amp 1 \amp 0 \\ 0 \amp - \lambda_{31} \amp 0 \amp 1 \end{array} \right) \left( \begin{array}{c} \widetilde a_0^T \\ \hline \widetilde a_1^T \\ \widetilde a_2^T \\ \widetilde a_3^T \end{array} \right) = \end{equation*}
Solution
\begin{equation*} \left( \begin{array}{c | c c c } 1 \amp 0 \amp 0 \amp 0 \\ \hline 0 \amp 1 \amp 0 \amp 0 \\ 0 \amp - \lambda_{21} \amp 1 \amp 0 \\ 0 \amp - \lambda_{31} \amp 0 \amp 1 \end{array} \right) \left( \begin{array}{c} \widetilde a_0^T \\ \hline \widetilde a_1^T \\ \widetilde a_2^T \\ \widetilde a_3^T \end{array} \right) = \left( \begin{array}{c} \widetilde a_0^T \\ \hline \widetilde a_1^T \\ \left( \begin{array}{c} \widetilde a_2^T\\ \widetilde a_3^T \end{array} \right) - \left( \begin{array}{c} \lambda_{21} \\ \lambda_{31} \end{array} \right) \widetilde a_1^T \end{array} \right) = \left( \begin{array}{c} \widetilde a_0^T \\ \hline \widetilde a_1^T \\ \widetilde a_2^T - \lambda_{21} \widetilde a_1^T\\ \widetilde a_3^T - \lambda_{31} \widetilde a_1^T\\ \end{array} \right). \end{equation*}

Notice the similarity with what one does in Gaussian elimination: take multiples of one row and subtracting these from other rows.

Homework 5.2.4.1.

Evaluate

\begin{equation*} \FlaThreeByThreeBR { I_k }{ 0 }{ 0 } { 0 }{ 1 }{ 0 } { 0 }{ -l_{21} }{ I } \FlaThreeByThreeBR {A_{00}}{a_{01}}{A_{02}} {0}{\alpha_{11}}{a_{12}^T} {0}{a_{21}}{A_{22}} \end{equation*}

where \(I_k \) is the \(k \times k \) identity matrix and \(A_0 \) has \(k \) rows. If we compute

\begin{equation*} \FlaThreeByThreeBR {A_{00}}{a_{01}}{A_{02}} {0}{\alpha_{11}}{a_{12}^T} {0}{\widehat a_{21}}{\widehat A_{22}} := \FlaThreeByThreeBR { I_k }{ 0 }{ 0 } { 0 }{ 1 }{ 0 } { 0 }{ -l_{21} }{ I } \FlaThreeByThreeBR {A_{00}}{a_{01}}{A_{02}} {0}{\alpha_{11}}{a_{12}^T} {0}{a_{21}}{A_{22}} \end{equation*}

how should \(l_{21} \) be chosen if we want \(\widehat a_{21}\) to be a zero vector?

Solution
\begin{equation*} \begin{array}{l} \FlaThreeByThreeBR { I_k }{ 0 }{ 0 } { 0 }{ 1 }{ 0 } { 0 }{ - l_{21} }{ I } \FlaThreeByThreeBR {A_{00}}{a_{01}}{A_{02}} {0}{\alpha_{11}}{a_{12}^T} {0}{a_{21}}{A_{22}} \\ ~~~ = \FlaThreeByThreeBR {A_{00}}{a_{01}}{A_{02}} {0}{\alpha_{11}}{a_{12}^T} {0}{-l_{21} \alpha_{11} + a_{21}}{ -l_{21} a_{12}^T + A_{22}} \\ ~~~ = \FlaThreeByThreeBR {A_{00}}{a_{01}}{A_{02}} {0}{\alpha_{11}}{a_{12}^T} {0}{a_{21} -\alpha_{11} l_{21}} {A_{22} -l_{21} a_{12}^T} \end{array} \end{equation*}

If \(l_{21} = a_{21} / \alpha_{11} \) then \(\widetilde a_{21} = a_{21} - \alpha_{11} a_{21} / \alpha_{11} = 0 \text{.}\)

Hopefully you notice the parallels between the computation in the last homework, and the algorithm in Figure 5.2.1.1.

Now, assume that the right-looking LU factorization has proceeded to where \(A \) contains

\begin{equation*} \FlaThreeByThreeBR {A_{00}}{a_{01}}{A_{02}} {0}{\alpha_{11}}{a_{12}^T} {0}{a_{21}}{A_{22}}, \end{equation*}

where \(A_{00} \) is upper triangular (recall: it is being overwritten by \(U \text{!}\)). What we would like to do is eliminate the elements in \(a_{21} \) by taking multiples of the "current row"' \(\left( \begin{array}{c| c}\alpha_{11} \amp a_{12}^T \end{array}\right) \) and subtract these from the rest of the rows: \(\left( \begin{array}{c| c} a_{21} \amp A_{22} \end{array}\right) \) in order to introduce zeroes below \(\alpha_{11} \text{.}\) The vehicle is an appropriately chosen Gauss transform, inspired by Homework 5.2.4.1. We must determine \(l_{21} \) so that

\begin{equation*} \FlaThreeByThreeBR {I}{0}{0} {0}{1}{0} {0}{-l_{21}}{I} \FlaThreeByThreeBR {A_{00}}{a_{01}}{A_{02}} {0}{\alpha_{11}}{a_{12}^T} {0}{a_{21}}{A_{22}} = \FlaThreeByThreeBR {A_{00}}{a_{01}}{A_{02}} {0}{\alpha_{11}}{a_{12}^T} {0}{0}{A_{22} - l_{21} a_{12}^T}. \end{equation*}

As we saw in Homework 5.2.4.1, this means we must pick \(l_{21} = a_{21} / \alpha_{11} \text{.}\) The resulting algorithm is summarized in Figure 5.2.4.3. Notice that this algorithm is, once again, identical to the algorithm in Figure 5.2.1.1 (except that it does not overwrite the lower triangular matrix).

\begin{equation*} \newcommand{\routinename}{ A = \mbox{GE-via-Gauss-transforms}( A )} \newcommand{\guard}{ n( A_{TL} ) \lt n( A ) } \newcommand{\partitionings}{ A \rightarrow \FlaTwoByTwo{A_{TL}}{A_{TR}} {A_{BL}}{A_{BR}} % , % L \rightarrow % \FlaTwoByTwo{L_{TL}}{L_{TR}} % {L_{BL}}{L_{BR}} } \newcommand{\partitionsizes}{ A_{TL} {\rm ~is~} 0 \times 0 % , L_{TL} {\rm ~are~} 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}} % , % \FlaTwoByTwo{L_{TL}}{L_{TR}} % {L_{BL}}{L_{BR}} % \rightarrow % \FlaThreeByThreeBR{L_{00}}{l_{01}}{L_{02}} % {l_{10}^T}{\lambda_{11}}{l_{12}^T} % {L_{20}}{l_{21}}{L_{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}} % , % \FlaTwoByTwo{L_{TL}}{L_{TR}} % {L_{BL}}{L_{BR}} % \leftarrow % \FlaThreeByThreeTL{L_{00}}{l_{01}}{L_{02}} % {l_{10}^T}{\lambda_{11}}{l_{12}^T} % {L_{20}}{l_{21}}{L_{22}} } \newcommand{\update}{ \begin{array}{ll} l_{21} \becomes a_{21} / \alpha_{11} \\ \\ \left. \begin{array}{l} \FlaThreeByThreeBR{A_{00}}{a_{01}}{A_{02}} {0}{\alpha_{11}}{a_{12}^T} {0}{a_{21}}{A_{22}} \\ ~~~~~ \becomes \FlaThreeByThreeBR{I}{0}{0} {0}{1}{0} {0}{-l_{21}}{I} \FlaThreeByThreeBR{A_{00}}{a_{01}}{A_{02}} {0}{\alpha_{11}}{a_{12}^T} {0}{a_{21}}{A_{22}} \\ ~~~~~=~ \FlaThreeByThreeBR{A_{00}}{a_{01}}{A_{02}} {0}{\alpha_{11}}{a_{12}^T} {0}{0}{A_{22}-l_{21} a_{12}^T} \end{array} \right\} \begin{array}{l} a_{21} := 0 \\ A_{22} := A_{22} - l_{21} a_{12}^T \end{array} \end{array} } \FlaAlgorithm \end{equation*}
Figure 5.2.4.3. Gaussian elimination, formulated as a sequence of applications of Gauss transforms.
Homework 5.2.4.2.

Show that

\begin{equation*} \FlaThreeByThreeBR { I_k }{ 0 }{ 0 } { 0 }{ 1 }{ 0 } { 0 }{ -l_{21} }{ I }^{-1} = \FlaThreeByThreeBR { I_k }{ 0 }{ 0 } { 0 }{ 1 }{ 0 } { 0 }{ l_{21} }{ I} \end{equation*}

where \(I_k \) denotes the \(k \times k \) identity matrix.

Hint

To show that \(B = A^{-1} \text{,}\) it suffices to show that \(B A = I \) (if \(A \) and \(B \) are square).

Solution
\begin{equation*} \begin{array}{l} \FlaThreeByThreeBR { I_k }{ 0 }{ 0 } { 0 }{ 1 }{ 0 } { 0 }{ -l_{21} }{ I_{(n-k-1) \times (n-k-1)} } \FlaThreeByThreeBR { I_k }{ 0 }{ 0 } { 0 }{ 1 }{ 0 } { 0 }{ l_{21} }{ I } \\ ~~~ = \FlaThreeByThreeBR { I_k }{ 0 }{ 0 } { 0 }{ 1 }{ 0 } { 0 }{ -l_{21} + l_{21} }{ I } \\ ~~~ = \FlaThreeByThreeBR { I_k }{ 0 }{ 0 } { 0 }{ 1 }{ 0 } { 0 }{ 0 }{ I } \end{array} \end{equation*}

Starting with an \(m \times m \) matrix \(A \text{,}\) the algorithm computes a sequence of \(m \) Gauss transforms \(L_0 , \ldots , L_{m-1} \text{,}\) each of the form

\begin{equation} L_k = \FlaThreeByThreeBR { I_k }{ 0 }{ 0 } { 0 }{ 1 }{ 0 } { 0 }{ -l_{21} }{ I }, \label{chapter05-gauss-transform-eqn1}\tag{5.2.2} \end{equation}

such that \(L_{m-1} L_{m-2} \cdots L_1 L_0 A = U \text{.}\) Equivalently, \(A = L_0^{-1} L_1^{-1} \cdots L_{m-2}^{-1} L_{m-1}^{-1} U \text{,}\) where

\begin{equation*} L_k^{-1} = \FlaThreeByThreeBR { I_k }{ 0 }{ 0 } { 0 }{ 1 }{ 0 } { 0 }{ l_{21} }{ I }. \end{equation*}

It is easy to show that the product of unit lower triangular matrices is itself unit lower triangular. Hence

\begin{equation*} L = L_0^{-1} L_1^{-1} \cdots L_{n-2}^{-1} L_{n-1}^{-1} \end{equation*}

is unit lower triangular. However, it turns out that this \(L \) is particularly easy to compute, as the following homework suggests.

Homework 5.2.4.3.

Let

\begin{equation*} \tilde L_{k-1} = L_0^{-1} L_1^{-1} \dots L_{k-1}^{-1} = \FlaThreeByThreeBR { L_{00} }{0}{0} { l_{10}^T }{1}{0} { L_{20} }{0}{I} \quad \mbox{and} \quad L_k^{-1} = \FlaThreeByThreeBR { I_k }{0}{0} { 0 }{1}{0} { 0 }{ l_{21} }{I}, \end{equation*}

where \(L_{00} \) is a \(k \times k \) unit lower triangular matrix. Show that

\begin{equation*} \tilde L_{k} = \tilde L_{k-1} L_k^{-1} = \FlaThreeByThreeBR { L_{00} }{0}{0} { l_{10}^T }{1}{0} { L_{20} }{ l_{21}}{I}. \end{equation*}
Solution
\begin{equation*} \begin{array}{rcl} \tilde L_{k} \amp = \amp L_0^{-1} L_1^{-1} \cdots L_{k-1} L_k^{-1} = \tilde L_{k-1} L_k^{-1} \\ \amp = \amp \FlaThreeByThreeBR { L_{00} }{0}{0} { l_{10}^T }{1}{0} { L_{20} }{ 0 }{I} \FlaThreeByThreeBR { I_k }{0}{0} { 0 }{1}{0} { 0 }{ l_{21}}{I} \\ \amp = \amp \FlaThreeByThreeBR { L_{00} }{0}{0} { l_{10}^T }{1}{0} { L_{20} }{ l_{21}}{I}. \end{array} \end{equation*}

What this exercise shows is that \(L = L_0^{-1} L_1^{-1} \cdots L_{n-2}^{-1} L_{n-1}^{-1} \) is the triangular matrix that is created by simply placing the computed vectors \(l_{21} \) below the diagonal of a unit lower triangular matrix. This insight explains the "magic" observed in Homework 5.2.1.3. We conclude that the algorithm in Figure 5.2.1.1 overwrites \(n \times n \) matrix \(A \) with unit lower triangular matrix \(L \) and upper triangular matrix \(U \) such that \(A = L U \text{.}\) This is known as the LU factorization or LU decomposition of \(A \text{.}\)

Ponder This 5.2.4.4.

Let

\begin{equation*} L_k = \left( \begin{array}{c | c c} I_{k \times k} \amp 0 \amp 0 \\ \hline 0 \amp 1 \amp 0 \\ 0 \amp - l_{21} \amp I \end{array} \right). \end{equation*}

Show that

\begin{equation*} \kappa_2( L_k ) \geq \| l_{21} \|_2^2. \end{equation*}

What does this mean about how error in \(A \) may be amplified if the pivot (the \(\alpha_{11} \) by which entries in \(a_{21} \) are divided to compute \(l_{21} \)) encountered in the right-looking LU factorization algorithm is small in magnitude relative to the elements below it? How can we chose which row to swap so as to minimize \(\| l_{21} \|_2 \text{?}\)