Questions: Gaussian Elimination with Partial Pivoting

Question 1

A student argues: 'Gaussian elimination finds the correct solution by construction, so pivoting is only needed when a diagonal entry is literally zero — otherwise it's just extra bookkeeping.' What is the critical flaw in this reasoning?

• A. Gaussian elimination does not always find the correct solution even with exact arithmetic
• B. A very small but nonzero pivot creates a huge multiplier that amplifies floating-point rounding errors, potentially making the computed answer completely wrong even when the exact solution exists and is unique
• C. Pivoting is needed to reduce the number of row operations and improve speed, not for accuracy
• D. The student is correct — pivoting is only logically required when the pivot is exactly zero

Answer: (B)

With exact arithmetic, the student would be right. The problem is floating-point arithmetic, where every stored number carries a tiny rounding error. If the pivot is 0.0001 and another entry in the column is 500, the elimination multiplier is 5,000,000. Any rounding error in the pivot row is multiplied by this factor before being subtracted from the other row. The resulting error can overwhelm the true solution. A near-zero pivot is as dangerous as a zero pivot in floating-point computation.

Question 2

Before using entry (k, k) as the current pivot, partial pivoting scans column k below that row and swaps the row with the largest absolute value into position k. What is the key numerical consequence?

• A. It guarantees the system has a unique solution by ensuring all pivots are nonzero
• B. It ensures all elimination multipliers in this step have absolute value ≤ 1, so rounding errors in the pivot row cannot be amplified beyond their original magnitude
• C. It reduces the total number of arithmetic operations needed for the elimination
• D. It produces a symmetric factorization that is cheaper to back-substitute

Answer: (B)

By placing the largest entry in the pivot position, every multiplier m_{ij} = a_{ij}/pivot satisfies |m_{ij}| ≤ 1. When you subtract m_{ij} times the pivot row from row j, any rounding errors are scaled by a factor ≤ 1 — they shrink or stay the same, never grow. Without pivoting, multipliers can be arbitrarily large (0.0001 pivot against a 500 entry gives multiplier 5,000,000), turning microscopic floating-point errors into catastrophic ones through n steps of elimination.

Question 3

Even when a linear system Ax = b has a unique exact solution, Gaussian elimination without pivoting can produce a completely wrong numerical answer due to floating-point error amplification.

• T. True
• F. False

Answer: True

This is the core motivation for partial pivoting. The existence and uniqueness of the mathematical solution is not the issue; the question is whether the numerical algorithm finds it accurately. A near-zero pivot creates a large multiplier that amplifies rounding errors. Across multiple elimination steps, these errors compound, potentially making the computed result far from the true solution. Partial pivoting keeps all multipliers ≤ 1, preventing this amplification regardless of the system's condition.

Question 4

Using partial pivoting changes the mathematical solution that Gaussian elimination computes, and should primarily be applied when numerical accuracy matters more than finding the true exact solution.

• T. True
• F. False

Answer: False

Partial pivoting does not change the solution being computed — it finds the same solution more accurately. Row swaps are valid elementary row operations that preserve the solution set of Ax = b. The row swaps are tracked via a permutation matrix P, so the resulting factorization is PA = LU instead of A = LU, but this represents the same system. The mathematical answer is unchanged; only the numerical accuracy of computing it improves. All major numerical libraries apply pivoting by default for this reason.

Question 5

Explain in your own words why a very small pivot entry is dangerous in floating-point Gaussian elimination, and how partial pivoting addresses the problem.

Model answer: A small pivot creates a large elimination multiplier (the ratio by which the pivot row is scaled before subtracting from another row). Every floating-point number carries a tiny rounding error — roughly 10^{-16} for double precision. Multiply that error by a factor of 5,000,000 and it becomes 10^{-9}, which can be large relative to the true answer. Partial pivoting puts the largest available entry in the pivot position, ensuring all multipliers have absolute value at most 1, so rounding errors cannot grow during elimination.

The relationship is direct: multiplier = (entry to eliminate) / (pivot). Small pivot + large entry = huge multiplier = large error amplification. Partial pivoting inverts this: by making the pivot the largest entry, every other entry divided by it gives a multiplier ≤ 1. This bounds error growth throughout the n steps of elimination. The technique has zero cost in terms of the final mathematical answer — only bookkeeping (tracking row swaps in a permutation matrix) is added.