Skip to main content

Subsection 6.4.5 Is LU with Partial Pivoting Stable?

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 0 \\ -1 \amp 1 \amp 0 \\ -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 in the \((n-1) \)st column 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.