10.3 Partial Pivoting
10.3 Partial Pivoting We can improve the Gaussian elimination algorithm by adding an operation called partial pivoting. Partial pivoting prevents dividing by zero during forward elimination, and it helps with the problem of dividing by a small pivot element. At each elimination step, partial pivoting exchanges the equations in order to choose the best pivot equation. (Full pivoting includes changing the order of the coefficients of the equations and is usually not done.) As we saw in Section 10.1 during forward elimination, we designate one equation the pivot equation, and then we subtract multiples of that equation from the equations below it to eliminate one unknown. The multiplier is a fraction whose divisor is the pivot element, the leading coefficient of the pivot equation. Therefore, if we want to avoid dividing by a small number, we want the pivot element to be the largest possible. To make this happen, we pivot (exchange) equations if necessary. The following is a simple system to illustrate the need for partial pivoting: The solution is approximately x 1 = 1.00005 and x 2 = 0.99995, or, with three significant digits, x 1 = 1.00 and x 2 = 1.00. Forward elimination produces (with three significant digits) and back substitution yields which is completely wrong for x 1 . The error occurred during forward elimination?adividing by the small pivot element 0.000100 generated large values, which were then subtracted from much smaller values, causing magnitude errors like the ones we examined in Chapter 4. Before we try to eliminate x 1 in the first step, we should make the pivot element as large as possible in absolute value. Certainly, the coefficient of x 1 in the second equation, 1.00, is greater than 0.000100, so we do a partial pivot by exchanging the two rows: Now forward elimination yields (with three significant digits) and back substitution gives us the much more accurate solution  |
| |
| Top |
EAN: 2147483647
Pages: 141