Subsection 6.4.5 Is LU with Partial Pivoting Stable?
ΒΆ VIDEO The last unit gives a backward error result regarding LU factorization (and, by extention, LU factorization with pivoting):
\begin{equation*}
( A + \Delta \!\!\ A ) = \check L \check U
\quad \mbox{with} \quad
\vert \Delta\!\!A \vert \leq \gamma_n \vert \check L \vert \vert
\check U \vert. .
\end{equation*}
The question now is: does this mean that LU factorization with partial pivoting is stable? In other words, is \(\Delta\!A \text{,}\) which we bounded with \(\vert \Delta\!A \vert \leq \gamma_n \vert \check L \vert \vert
\check U \vert
\text{,}\) always small relative to the entries of \(\vert
A \vert \text{?}\) The following exercise gives some insight:
Homework 6.4.5.1 .
Apply LU with partial pivoting to
\begin{equation*}
A =
\left( \begin{array}{r r r r r r}
1 \amp 0 \amp 1 \\
-1 \amp 1 \amp 1 \\
-1 \amp -1 \amp 1
\end{array}
\right).
\end{equation*}
Pivot only when necessary.
Solution
Notice that no pivoting is necessary. Eliminating the entries below the diagonal in the first column yields:
\begin{equation*}
\left( \begin{array}{r r r r r r}
1 \amp 0 \amp 1 \\
0 \amp 1 \amp 2 \\
0 \amp -1 \amp 2
\end{array}
\right).
\end{equation*}
Eliminating the entries below the diagonal in the second column again does not require pivoting and yields:
\begin{equation*}
\left( \begin{array}{r r r r r r}
1 \amp 0 \amp 1 \\
0 \amp 1 \amp 2 \\
0 \amp 0 \amp 4
\end{array}
\right).
\end{equation*}
Homework 6.4.5.2 .
Generalize the insights from the last homework to a \(n
\times n \) matrix. What is the maximal element growth that is observed?
Solution
Consider
\begin{equation*}
A =
\left( \begin{array}{r r r r r r}
1 \amp 0 \amp 0 \amp \cdots \amp 0 \amp 1 \\
-1 \amp 1 \amp 0 \amp \cdots \amp 0 \amp 1 \\
-1 \amp -1 \amp 1 \amp \cdots \amp 0 \amp 1 \\
\vdots \amp \vdots \amp \vdots \amp \ddots \amp \vdots \amp \vdots \\
-1 \amp -1 \amp \amp \cdots \amp 1 \amp 1 \\
-1 \amp -1 \amp \amp \cdots \amp -1 \amp 1 \\
\end{array}
\right).
\end{equation*}
Notice that no pivoting is necessary when LU factorization with pivoting is performed.
Eliminating the entries below the diagonal in the first column yields:
\begin{equation*}
\left( \begin{array}{r r r r r r}
1 \amp 0 \amp 0 \amp \cdots \amp 0 \amp 1 \\
0 \amp 1 \amp 0 \amp \cdots \amp 0 \amp 2 \\
0 \amp -1 \amp 1 \amp \cdots \amp 0 \amp 2 \\
\vdots \amp \vdots \amp \vdots \amp \ddots \amp \vdots \amp \vdots \\
0 \amp -1 \amp \amp \cdots \amp 1 \amp 2 \\
0 \amp -1 \amp \amp \cdots \amp -1 \amp 2 \\
\end{array}
\right).
\end{equation*}
Eliminating the entries below the diagonal in the second column again does not require pivoting and yields:
\begin{equation*}
\left( \begin{array}{r r r r r r}
1 \amp 0 \amp 0 \amp \cdots \amp 0 \amp 1 \\
0 \amp 1 \amp 0 \amp \cdots \amp 0 \amp 2 \\
0 \amp 0 \amp 1 \amp \cdots \amp 0 \amp 4 \\
\vdots \amp \vdots \amp \vdots \amp \ddots \amp \vdots \amp \vdots \\
0 \amp 0 \amp \amp \cdots \amp 1 \amp 4 \\
0 \amp 0 \amp \amp \cdots \amp -1 \amp 4 \\
\end{array}
\right).
\end{equation*}
Continuing like this for the remaining columns, eliminating the entries below the diagonal leaves us with the upper triangular matrix
\begin{equation*}
\left( \begin{array}{r r r r r r}
1 \amp 0 \amp 0 \amp \cdots \amp 0 \amp 1 \\
0 \amp 1 \amp 0 \amp \cdots \amp 0 \amp 2 \\
0 \amp 0 \amp 1 \amp \cdots \amp 0 \amp 4 \\
\vdots \amp \vdots \amp \vdots \amp \ddots \amp \vdots \amp \vdots \\
0 \amp 0 \amp \amp \cdots \amp 1 \amp 2^{n-2} \\
0 \amp 0 \amp \amp \cdots \amp 0 \amp 2^{n-1} \\
\end{array}
\right).
\end{equation*}
From these exercises we conclude that even LU factorization with partial pivoting can yield large (exponential) element growth in \(U \text{.}\)
In practice, this does not seem to happen and LU factorization is considered to be stable.
