By hand you swap rows only when a pivot is $0$. In floating point that is not enough: a pivot that is merely tiny produces huge multipliers, and the huge numbers swamp the information in the other rows. It is Round-Off and Cancellation again, this time inside elimination.
Key idea
Partial pivoting: before eliminating in column $k$, find the row at or below the diagonal whose entry in column $k$ is largest in absolute value, and swap it into the pivot position. Then every multiplier satisfies $|m| \le 1$.
Why it works
With pivot $\epsilon$ and multiplier $m = a_{21}/\epsilon$, the update $a_{22} - m\,a_{12}$ is dominated by $-m\,a_{12}$ when $|m|$ is huge. After rounding, the original $a_{22}$ (and the matching entry of $\mathbf{b}$) may vanish completely: the computer is now solving a different system. Choosing the largest available pivot keeps $|m| \le 1$, so no row is ever multiplied up before it is added to another, and entries cannot grow much from one step to the next. With partial pivoting, elimination is backward stable for practically every matrix met in practice.
Worked example: A tiny pivot
Solve $10^{-4}x + y = 1$, $x + y = 2$ in 3-digit decimal arithmetic, without and with a row swap. (The true solution is $x \approx 1.0001$, $y \approx 0.9999$.)
- No swap: the multiplier is $1/10^{-4} = 10^{4}$. Row 2 becomes $(1 - 10^{4})y = 2 - 10^{4}$; both $-9999$ and $-9998$ round to $-1.00 \times 10^{4}$, so $y = 1.00$.
- Then $x = \frac{1 - 1.00}{10^{-4}} = 0$. Completely wrong: the 1 and the 2 in row 2 were rounded away.
- Swap first: the multiplier is $10^{-4}$. Row 2 becomes $(1 - 10^{-4})y = 1 - 2 \times 10^{-4}$, which rounds to $1.00y = 1.00$: $y = 1.00$, and $x = 2 - 1.00 = 1.00$. Right to 3 digits.
Answer: $x = 0$ without the swap, $x = 1.00$ with it
Worked example: Choosing pivots in a 3 × 3 matrix
Carry out the first step of partial pivoting on $A = \begin{bmatrix} 2 & 1 & -1 \\ -6 & 3 & 2 \\ 4 & -2 & 5 \end{bmatrix}$.
- Column 1 sizes: $|2|, |-6|, |4|$. The largest is in row 2, so swap rows 1 and 2.
- Multipliers: $\frac{2}{-6} = -\frac{1}{3}$ and $\frac{4}{-6} = -\frac{2}{3}$, both at most 1 in size.
- Eliminate: the new rows 2 and 3 are $(0, 2, -\frac{1}{3})$ and $(0, 0, \frac{19}{3})$.
- Column 2 below the diagonal: $|2|$ and $|0|$, so no further swap is needed.
Answer: $\begin{bmatrix} -6 & 3 & 2 \\ 0 & 2 & -\frac{1}{3} \\ 0 & 0 & \frac{19}{3} \end{bmatrix}$
Common mistake
Swapping rows only when a pivot is exactly $0$. In floating point a pivot of $10^{-20}$ does just as much damage as $0$ does by hand, only silently: no division by zero warns you. Compare sizes with absolute values ($-6$ beats $4$), and swap whenever a larger entry sits below.
The row swaps are recorded in a permutation matrix $P$, giving the factorization $PA = LU$; the next topic, Solving with PA = LU, shows how to use it.