Partial Pivoting

5.3 Partial Pivoting

For the Gauss elimination method to work it is necessary that at each step \(k\) there is a nonzero coefficient at variable \(x_k\) in line \(k\), since otherwise one cannot use the \(k\)-th line to eliminate \(x_k\) in the remaining lines \(i \gt k\). Moreover, since one must divide by the value of this coefficient \(a^{(k)}_{kk}\) (the upper, bracketed index refers to the step number) to determine the multipliers \(m_{ik}\), for a numerical computation it is important that this value is not too close to zero in order to prevent numerical errors becoming large.

Since \(a^{(k)}_{kk}\) plays such a crucial role, it is called the pivot element. If it is zero or too small, one has to interchange the contents of the present row \(k\) with that of another row \(j \gt k\) where the corresponding coefficient (at \(x_k\)) is neither zero nor too small. Numerically best suited for this is the row with the largest absolute coefficient, i.e. the largest of

\(|a_{k+1\,k}^{(k)}|\), \(|a_{k+2\,k}^{(k)}|\), …, \(|a_{nk}^{(k)}|\).

This choice of a new pivot element by a permutation of rows is called partial pivoting. Full pivoting would be to also interchange the columns of \(\mathsf{A}\) in order to possibly obtain an even larger value for the new pivot element. As a result of partial pivoting, besides \(\mathsf{L}\) and \(\mathsf{U}\) one also obtains the row permutation matrix \(\mathsf{P}\) (the result therefore being called an LUP decomposition); it holds that

\begin{equation*} \label{eq:LUP} \mathsf{P}\mathsf{A} = \mathsf{L}\mathsf{U}. \end{equation*}

(5.11)

Example:

\begin{equation*} \mathsf{A} = \left( \begin{array}{ccc} 1&2&3 \\ 1&2&4 \\ 3&8&13 \end{array} \right) =: {\mathsf{A}}^{(1)} \ \rightarrow \ {\mathsf{A}}^{(2)} = \left( \begin{array}{ccc} 1&2&3 \\ 0&0&1 \\ 0&2&4 \end{array} \right) \ \rightarrow \ {\mathsf{P}}{\mathsf{A}}^{(2)} = \left( \begin{array}{ccc} 1&2&3 \\ 0&2&4 \\ 0&0&1 \end{array} \right) =: {\mathsf{U}} \end{equation*}

(5.12)

The first-step multipliers are \(m_{21}=1\) and \(m_{31}=3\). To proceed, \(\mathsf{P}\) has to interchange the 2nd and 3rd row, which also affects the construction of \(\mathsf{L}\). Since further elimination is not necessary, one has \(l_{21}=3\), \(l_{31}=1\), \(l_{32}=0\) (\(l_{kk}=1\)). With these it can be verified that Eq. (5.11) holds.