Exercise 2: Why Partial Pivoting Guarantees Multipliers of Magnitude at Most 1 — Possible Solution ==================================================================== WHAT THE MULTIPLIER ACTUALLY IS ------------------------------ During Gaussian elimination, the multiplier used to eliminate an entry below the pivot is computed as (entry to eliminate) / (pivot value) - it's the factor the pivot row gets scaled by before being subtracted from the row below, specifically chosen to make that row's leading entry become exactly zero. WHY THE PIVOTING RULE FORCES THE RATIO TO BE AT MOST 1 ------------------------------ Partial pivoting's rule is: before eliminating a column, swap rows so that the row with the LARGEST available magnitude in that column becomes the pivot row. This means, by construction, the pivot value chosen is always greater than or equal in magnitude to every other entry still available in that column - including the entry about to be eliminated. Since the multiplier is (entry to eliminate) / (pivot), and the pivot's magnitude is guaranteed to be at least as large as the entry to eliminate's magnitude, the ratio's absolute value can never exceed 1: dividing a number by something at least as large as itself always produces a result with absolute value at most 1. WHY THIS MATTERS FOR ERROR AMPLIFICATION ------------------------------ This chapter verified directly that the size of the multiplier determines how much rounding error gets scaled up during the elimination step - the 10^16 multiplier from the unpivoted example amplified error dramatically, while the 10^-16 multiplier that resulted from pivoting the same system didn't. A multiplier bounded by 1 cannot itself amplify the magnitude of whatever value it's applied to - multiplying by a number no larger than 1 in absolute value can only shrink or preserve magnitude, never grow it. This is precisely the mechanism that keeps partial pivoting's rounding error from compounding the way the unpivoted example's did. WHY THIS WORKS AS AN ANSWER ------------------------------ The explanation defines the multiplier precisely, derives the "at most 1" guarantee directly from the pivoting rule's own definition (largest available magnitude becomes the pivot) rather than asserting it, and connects the bound back to this chapter's own verified evidence that multiplier size is what actually drives error amplification during elimination.