Back to the on-screen lesson ·
Why a pivot that is merely small is more dangerous than one that is exactly zero, and the swap that keeps every multiplier below one.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to apply partial pivoting to a column, compute the multipliers with and without it, explain what a large multiplier does to the accuracy of an elimination, and say what pivoting does not fix.
You can eliminate a column and you know that the method divides by the pivot, so a zero pivot stops it. You also know that subtracting a large quantity from a small one destroys the small one's digits. This lesson is those two facts meeting.
Partial pivoting chooses, as the pivot for each column, the entry of largest magnitude at or below the diagonal, and swaps its row up. The growth factor is the ratio of the largest entry appearing anywhere during the elimination to the largest entry of the original matrix. Scaled partial pivoting compares each candidate with the largest entry in its own row first.
Elimination divides by the pivot, so the multiplier is $\dfrac{\text{entry below}}{\text{pivot}}$. If the pivot is tiny, that multiplier is huge, and the row below is replaced by itself minus a huge multiple of the pivot row: the pivot row's rounding errors are amplified by the multiplier, and the row's own entries are rounded away beside them. The elimination completes, reports nothing, and returns an answer with no correct digits. Partial pivoting removes this by choosing, for each column, the entry of largest magnitude at or below the diagonal and swapping its row into the pivot position. Then every multiplier satisfies $|m| \le 1$, nothing is amplified, and the growth of the entries is bounded. Three things it is not. It is not only for exact zeros — those stop the method loudly, which is the easy case. It does not make the answer exact: it makes the method stable, and an ill-conditioned system still loses its digits to the problem. And it is not free — it costs a scan of each column and the data movement of the swap, which is why it is the default and not an option.
Another way: steps
Another way: example
$10^{-5}x + y = 1$, $x + y = 2$ in five-digit arithmetic. Without a swap the multiplier is $10^{5}$, the second row becomes $(0, 1 - 10^{5})$ which rounds to $(0, -10^{5})$, and the answer comes out $x = 0$ — wrong in every digit. Swap first and the multiplier is $10^{-5}$; the answer is right to five digits.
The belief that a pivot only needs to be non-zero is the most expensive misunderstanding in numerical linear algebra, because the code that holds it works on every test case anyone thinks to try. Exact zeros are rare and loud; small pivots are common and silent. The rule to hold instead is about the multipliers: if any of them is much larger than one, the elimination is amplifying errors, whatever the pivot happened to be.
A multiplier of $10^{6}$ multiplies the pivot row's last-digit error by a million.
That error is now in the sixth digit.
The row below is added to something a million times larger, so its own entries lose six digits.
Both effects, in one subtraction.
In sixteen-digit arithmetic a few such multipliers exhaust the precision entirely.
And nothing reports it.
Multiply one equation through by $10^{6}$: the system is unchanged.
Same solution, same conditioning.
Its entries now dominate every column, so partial pivoting selects it at every step.
A choice driven by scaling.
Scaled partial pivoting compares each candidate with the largest entry in its own row first, and is not fooled.
The fix is to normalise the comparison.
The first column holds $2$ and $5$.
$5$ is the larger in magnitude, and it is below the diagonal.
So yes: swap, and the multiplier becomes $\tfrac25$ rather than $\tfrac52$.
The system has first column $\left(0.01,\; 4\right)$. Give the pivot and the multiplier, first taking the rows as they are and then after swapping them.
| Pivot | Multiplier | |
|---|---|---|
| Rows as they are | ||
| After swapping the rows |
A pivot is $10^{-9}$ while the entry below it is of ordinary size. The pivot is not zero, so the elimination can proceed. Why swap the rows anyway?
Put the five steps of eliminating one column of an $4 \times 4$ system with partial pivoting into order.
Number the steps in order (write the number in the box):
Partial pivoting is applied to the first column of $\begin{pmatrix} 0.001 & 3 \\ 4 & 1 \end{pmatrix}$. Write the matrix that results.
This task has no paper form; do it on a device.
Partial pivoting is applied to the first column in four situations. Match each to what happens.
| Swap, and the elimination proceeds: the system was only badly ordered | Swap, and without it the run finishes quietly with a meaningless answer | Scan, swap nothing, and carry on: the rule costs a comparison | No swap helps: there is no non-zero candidate and the matrix is singular | |
|---|---|---|---|---|
| A pivot of exactly zero, with a large entry below | ||||
| A pivot of about $10^{-4}$, with an ordinary entry below | ||||
| A diagonal entry that is already the largest in its column | ||||
| A column that is entirely zero from the diagonal down |
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
The pivot is $0.001$ and the entry below it is $4$. What is the multiplier if the rows are not swapped?
Answer:
You can choose a pivot, perform the swap and say what the multipliers become. Say in your own words why a tiny pivot is more dangerous than a zero one.
8. Your turn: should the rows of $\begin{pmatrix} 2 & 7 \\ 5 & 1 \end{pmatrix}$ be swapped?, step 3