Rounding Error and Partial Pivoting in Row Reduction

Take the system 0.0001x + y = 1, x + y = 2. This is a well-posed problem with a unique, stable answer. Solve it by hand with exact fractions and you get x ≈ 1.0001, y ≈ 0.9999. Solve it with a rounding calculator that retains only three decimal digits at each step, and you get x = 0, y = 1. The first solution is correct; the second is wrong by a relative error of roughly 100% in x. The reason is rounding error and partial pivoting in row reduction, or rather the absence of it.

Rounding error is the difference between an exact mathematical result and its floating-point approximation. In Gaussian elimination, every row operation, multiplying, adding, swapping, creates a new number that the machine or the calculator rounds to fit its available digits. Without a strategy to control where those digits go, the error can grow larger than the answer itself.

Partial pivoting is that strategy. Before eliminating below a pivot, it scans the current column of the remaining rows and selects the row with the largest absolute value in that column. Swapping that row into the pivot position keeps the pivot large relative to the multipliers. A large pivot means the multipliers are fractions smaller than one, which limits the growth of rounding error. Burden & Faires' numerical analysis text (10th ed., Section 6.2) formalises this as the standard classroom strategy for stability.

The classic failure case demonstrates this in three-digit decimal arithmetic. The system:

0.0001x + y = 1
x + y = 2

Without pivoting, the first pivot is 0.0001. The multiplier to eliminate the x-term in the second row is 1 / 0.0001 = 10,000. Applying the row operation gives:

Row2 = Row2 − 10,000 × Row1
= (1 − 10,000 × 0.0001, 1 − 10,000 × 1, 2 − 10,000 × 1)
= (0, −9,999, −9,998)

Rounded to three digits, this becomes (0, −10,000, −10,000). Back-substitution: y = (−10,000) / (−10,000) = 1. Then x = (1 − 1 × 1) / 0.0001 = 0 / 0.0001 = 0. The computed solution is (0, 1). The exact solution is x ≈ 1.0001, y ≈ 0.9999. The relative error in x is |0 − 1.0001| / 1.0001 ≈ 1.000, or 100%. The answer is not just slightly off; it is qualitatively wrong, it reports x = 0, which is not even close.

With partial pivoting, the algorithm compares the absolute values in the first column: |0.0001| and |1|. It selects the second row as the pivot row and swaps it to the top. The system becomes:

x + y = 2
0.0001x + y = 1

Now the pivot is 1, and the multiplier is 0.0001 / 1 = 0.0001. The row operation:

Row2 = Row2 − 0.0001 × Row1
= (0.0001 − 0.0001 × 1, 1 − 0.0001 × 1, 1 − 0.0001 × 2)
= (0, 0.9999, 0.9998)

Rounded to three digits: (0, 1.00, 1.00). Back-substitution: y = 1.00, then x = (2 − 1 × 1) / 1 = 1. The computed solution is (1, 1). The error in x is |1 − 1.0001| ≈ 0.0001, a relative error of about 0.01%. Partial pivoting reduced the error by a factor of 10,000.

The calculation itself shows exactly where rounding error enters. In the no-pivot version, the step that amplifies error is the subtraction of two nearly equal numbers after scaling. Row2 after the operation had entries (−9,999, −9,998) before rounding. A three-digit representation cannot capture the difference; both round to −10,000. The subtraction catastrophically cancelled the true values.

The Role of Retained Precision

Retained precision is the number of digits the calculation preserves through each operation. The example used three-digit decimal floating-point, rounding after every arithmetic step. IEEE 754 binary arithmetic uses more digits but is not immune: it rounds after each operation to a fixed number of bits. The same mechanism, catastrophic cancellation when subtracting large, nearly equal numbers, occurs inside a computer, just at finer granularity.

Wilkinson's Bound

Without any pivoting, the growth factor for rounding error can reach 2^(n−1) for an n×n matrix, a result known as Wilkinson's bound. For a 2×2 system, that factor is 2; the error in the example grew by far more because the pivot was extremely small. Partial pivoting reduces the worst-case growth factor dramatically, though it does not eliminate it for pathological cases like Wilkinson's matrix.

The system in the example is well-posed: it has a unique solution, a condition number near 1 (so small coefficient changes produce small solution changes), and no row is a linear combination of another. Theoretically, Gaussian elimination should solve it exactly. The failure is purely numerical, not mathematical. A student who checks their work by substituting back will find that (0, 1) satisfies the first equation (0.0001×0 + 1 = 1) but fails the second (0 + 1 ≠ 2). The mismatch signals the rounding error.

The one thing that most often goes wrong here is that the solver blames the algebra instead of the arithmetic. They conclude the system is inconsistent or that they made a coefficient error, when the real problem is that they performed the elimination with too few digits and no pivot selection.

Rounding error and partial pivoting in row reduction suits college linear algebra students who solve small systems by hand and need to interpret why their calculator answer diverges from the textbook. It also suits numerical methods students who must understand pivoting before using library solvers such as LAPACK's dgesv or NumPy's numpy.linalg.solve.

Anyone solving large sparse systems of 1000+ equations should skip this level of detail and go directly to a dedicated sparse solver like scipy.sparse.linalg.splu. Anyone seeking a deep theoretical treatment of vector spaces or eigenvalues should turn to Strang's Introduction to Linear Algebra or Axler's Linear Algebra Done Right.