The pivot or pivot element is the element of a matrix, or an array, which is selected first by an algorithm (e.g. Gaussian elimination, simplex algorithm, etc.), to do certain calculations. In the case of matrix algorithms, a pivot entry is usually required to be at least distinct from zero, and often distant from it; in this case finding this element is called pivoting. Pivoting may be followed by an interchange of rows or columns to bring the pivot to a fixed position and allow the algorithm to proceed successfully, and possibly to reduce round-off error. It is often used for verifying row echelon form. Pivoting might be thought of as swapping or sorting rows or columns in a matrix, and thus it can be represented as multiplication by permutation matrices. However, algorithms rarely move the matrix elements because this would cost too much time; instead, they just keep track of the permutations. Overall, pivoting adds more operations to the computational cost of an algorithm. These additional operations are sometimes necessary for the algorithm to work at all. Other times these additional operations are worthwhile because they add numerical stability to the final result.
Examples of systems that require pivoting In the case of Gaussian elimination, the algorithm requires that pivot elements not be zero. Interchanging rows or columns in the case of a zero pivot element is necessary. The system below requires the interchange of rows 2 and 3 to perform elimination.
[ 1 − 1 2 8 0 0 − 1 − 11 0 2 − 1 − 3 ] {\displaystyle \left[{\begin{array}{ccc|c}1&-1&2&8\\0&0&-1&-11\\0&2&-1&-3\end{array}}\right]}
The system that results from pivoting is as follows and will allow the elimination algorithm and backwards substitution to output the solution to the system.
[ 1 − 1 2 8 0 2 − 1 − 3 0 0 − 1 − 11 ] {\displaystyle \left[{\begin{array}{ccc|c}1&-1&2&8\\0&2&-1&-3\\0&0&-1&-11\end{array}}\right]}
Furthermore, in Gaussian elimination it is generally desirable to choose a pivot element with large absolute value. This improves the numerical stability. The following system is dramatically affected by round-off error when Gaussian elimination and backwards substitution are performed.
[ 0.00300 59.14 59.17 5.291 − 6.130 46.78 ] {\displaystyle \left[{\begin{array}{cc|c}0.00300&59.14&59.17\\5.291&-6.130&46.78\\\end{array}}\right]}
This system has the exact solution of x1 = 10.00 and x2 = 1.000, but when the elimination algorithm and backwards substitution are performed using four-digit arithmetic, the small value of a11 causes small round-off errors to be propagated. The algorithm without pivoting yields the approximation of x1 ≈ 9873.3 and x2 ≈ 4. In this case it is desirable that we interchange the two rows so that a21 is in the pivot position
[ 5.291 − 6.130 46.78 0.00300 59.14 59.17 ] . {\displaystyle \left[{\begin{array}{cc|c}5.291&-6.130&46.78\\0.00300&59.14&59.17\\\end{array}}\right].}
Considering this system, the elimination algorithm and backwards substitution using four-digit arithmetic yield the correct values x1 = 10.00 and x2 = 1.000.
… excerpt ends here. Continue reading the full article.
