4.3 Pivoting strategies
Algorithm 4.2.3 interchanges rows only when a pivot is exactly zero. In finite-digit arithmetic a pivot that is merely small is just as dangerous, because it produces large multipliers, and large multipliers magnify round-off errors.
Example 4.3.1. The system \begin {align*} 0.003000x_1+59.14x_2 &= 59.17,\\ 5.291x_1-6.130x_2 &= 46.78 \end {align*}
has the exact solution \(x_1 = 10.00\), \(x_2 = 1.000\). Solve it by Gaussian elimination in four-digit rounding arithmetic.
Solution. The pivot \(a_{11} = 0.003000\) is small, and the multiplier is \[m_{21} = \frac {5.291}{0.003000} = 1763.\overline {6}\ \to \ 1764 .\] Then, rounding each product and difference to four digits, \begin {align*} a_{22}&: -6.130-1764(59.14) = -6.130-104300 = -104300,\\ b_2&: 46.78-1764(59.17) = 46.78-104400 = -104400 . \end {align*}
So \(x_2 = \frac {-104400}{-104300} = 1.001\), close to the true value, but \[x_1 = \frac {59.17-59.14(1.001)}{0.003000} = \frac {59.17-59.20}{0.003000} = -10.00 ,\] which has the wrong sign. The small error of \(0.001\) in \(x_2\) was multiplied by \(\frac {59.14}{0.003000}\approx 20000\) in the computation of \(x_1\).
The remedy is to choose as pivot the entry of largest magnitude available.
Definition 4.3.2. In partial pivoting (or maximal column pivoting), at stage \(i\) we find the smallest \(p\geq i\) with \[|a_{pi}| = \max _{i\leq k\leq n}|a_{ki}|\] and interchange rows \(i\) and \(p\) before eliminating. Then every multiplier satisfies \(|m_{ji}|\leq 1\).
Example 4.3.3. Solve the system of Example 4.3.1 with partial pivoting, in four-digit rounding arithmetic.
Solution. In column \(1\), \(|5.291|>|0.003000|\), so the equations are interchanged: \begin {align*} 5.291x_1-6.130x_2 &= 46.78,\\ 0.003000x_1+59.14x_2 &= 59.17 . \end {align*}
Now \(m_{21} = \frac {0.003000}{5.291} = 0.0005670\), and \(a_{22} = 59.14+0.0005670(6.130) = 59.14\), \(b_2 = 59.17-0.0005670(46.78) = 59.14\). Hence \(x_2 = 1.000\) and \(x_1 = \frac {46.78+6.130(1.000)}{5.291} = 10.00\), both correct to four digits.
Partial pivoting compares the sizes of entries in one column, and it can be fooled when the equations are on very different scales.
Example 4.3.4. Multiply the first equation of Example 4.3.1 by \(10^4\): \begin {align*} 30.00x_1+591400x_2 &= 591700,\\ 5.291x_1-6.130x_2 &= 46.78 . \end {align*}
The solution is unchanged. Solve the system with partial pivoting in four-digit arithmetic.
Solution. Now \(|30.00|>|5.291|\), so partial pivoting does not interchange the rows. The multiplier is \(m_{21} = \frac {5.291}{30.00} = 0.1764\), and the computation repeats that of Example 4.3.1 with every number in the first row scaled by \(10^4\): it produces \(x_2 = 1.001\) and \(x_1 = -10.00\) again. The pivot \(30.00\) is not small in absolute terms, but it is small compared with the other entry \(591400\) of its own row, and that is what matters.
Definition 4.3.5. In scaled partial pivoting, before elimination we compute for each row the scale factor \[s_i = \max _{1\leq j\leq n}|a_{ij}| .\] At stage \(i\) we choose as pivot row the smallest \(p\geq i\) with \[\frac {|a_{pi}|}{s_p} = \max _{i\leq k\leq n}\frac {|a_{ki}|}{s_k},\] and interchange rows \(i\) and \(p\) (together with their scale factors). The scale factors are computed only once, at the start.
Example 4.3.6. Solve the system of Example 4.3.4 with scaled partial pivoting.
Solution. The scale factors are \[s_1 = \max \{30.00,\ 591400\} = 591400,\qquad s_2 = \max \{5.291,\ 6.130\} = 6.130 ,\] so the scaled candidates for the pivot are \[\frac {|a_{11}|}{s_1} = \frac {30.00}{591400} = 0.5073\times 10^{-4},\qquad \frac {|a_{21}|}{s_2} = \frac {5.291}{6.130} = 0.8631,\] so the rows are interchanged. Elimination now uses the multiplier \(m_{21} = \frac {30.00}{5.291} = 5.670\), giving \(a_{22} = 591400+5.670(6.130) = 591400\) and \(b_2 = 591700-5.670(46.78) = 591400\). Hence \(x_2 = 1.000\) and \(x_1 = \frac {46.78+6.130}{5.291} = 10.00\): the correct solution.
Note. Partial pivoting adds about \(\frac {n^2}{2}\) comparisons to the work, which is negligible beside the \(\frac {n^3}3\) operations of elimination, and it is used in essentially all practical software. Scaled partial pivoting adds about \(\frac {n^2}{2}\) divisions as well. Complete (or total) pivoting searches the whole remaining submatrix for the largest entry and interchanges columns as well as rows; it is more robust but adds about \(\frac {n^3}{3}\) comparisons, and is used only when the extra safety is essential. For matrices of the special kinds met in the next subsection (diagonally dominant or positive definite), no pivoting is needed at all.
Questions on this section
Stuck on something here? Ask below and it stays attached to this topic.