Intuition The big pictureWe want to solve A x = b A\mathbf{x} = \mathbf{b} A x = b n n n n n n WHY a special method? Solving by hand-substitution or Cramer's rule explodes (n ! n! n ! WHAT Gaussian elimination does: systematically kill the variables below the diagonal so the
matrix becomes upper-triangular, then read off answers by back-substitution .
WHY pivoting: dividing by a tiny (or zero) pivot blows up rounding errors. So before each
elimination step we swap rows to put the largest-magnitude available entry on the diagonal.
That single trick makes the method numerically stable.
A x = b , A ∈ R n × n , b ∈ R n . A\mathbf{x}=\mathbf{b},\qquad A\in\mathbb{R}^{n\times n},\ \mathbf{b}\in\mathbb{R}^n. A x = b , A ∈ R n × n , b ∈ R n . x \mathbf{x} x augmented matrix [ A ∣ b ] [A\,|\,\mathbf{b}] [ A ∣ b ] elementary row operations (which never change the solution set):
Swap two rows.
Multiply a row by a nonzero scalar.
Add a multiple of one row to another.
We want zeros below the diagonal of column k k k k k k k + 1 , … , n k+1,\dots,n k + 1 , … , n
HOW to zero entry a i k a_{ik} a ik i > k i>k i > k k k k i i i Row i ← Row i − m i k Row k . \text{Row}_i \leftarrow \text{Row}_i - m_{ik}\,\text{Row}_k. Row i ← Row i − m ik Row k .
We need the new ( i , k ) (i,k) ( i , k ) 0 0 0 a i k − m i k a k k = 0 ⟹ m i k = a i k a k k . a_{ik} - m_{ik}\,a_{kk} = 0 \;\Longrightarrow\; \boxed{m_{ik} = \dfrac{a_{ik}}{a_{kk}}}. a ik − m ik a k k = 0 ⟹ m ik = a k k a ik .
WHY partial pivoting? The multiplier has a k k a_{kk} a k k a k k a_{kk} a k k m i k m_{ik} m ik
Definition Partial pivoting ruleBefore eliminating column k k k k … n k\dots n k … n largest absolute value
in column k k k p = arg max i ≥ k ∣ a i k ∣ , p=\arg\max_{i\ge k}\,|a_{ik}|, p = arg max i ≥ k ∣ a ik ∣ , swap row k k k p p p . This guarantees every multiplier satisfies ∣ m i k ∣ ≤ 1 |m_{ik}|\le 1 ∣ m ik ∣ ≤ 1
After forward elimination we have an upper-triangular system U x = c U\mathbf{x}=\mathbf{c} U x = c
u n n x n = c n , u n − 1 , n − 1 x n − 1 + u n − 1 , n x n = c n − 1 , … \begin{aligned}
u_{nn}x_n &= c_n,\\
u_{n-1,n-1}x_{n-1}+u_{n-1,n}x_n &= c_{n-1},\ \dots
\end{aligned} u nn x n u n − 1 , n − 1 x n − 1 + u n − 1 , n x n = c n , = c n − 1 , … The last equation has one unknown — solve it. Substitute upward.
Solve
{ 0.0003 x 1 + 3.0000 x 2 = 2.0001 1.0000 x 1 + 1.0000 x 2 = 1.0000 \begin{cases} 0.0003x_1 + 3.0000x_2 = 2.0001\\ 1.0000x_1 + 1.0000x_2 = 1.0000\end{cases} { 0.0003 x 1 + 3.0000 x 2 = 2.0001 1.0000 x 1 + 1.0000 x 2 = 1.0000 x 1 = 1 3 , x 2 = 2 3 x_1=\tfrac{1}{3},\ x_2=\tfrac{2}{3} x 1 = 3 1 , x 2 = 3 2 0.33333 , 0.66667 0.33333,\ 0.66667 0.33333 , 0.66667
Step 1 — Partial pivoting. Column 1 entries: ∣ 0.0003 ∣ |0.0003| ∣0.0003∣ ∣ 1.0000 ∣ |1.0000| ∣1.0000∣ Why this step? 1.0000 1.0000 1.0000 0.0003 0.0003 0.0003 [ 1 1 ∣ 1 0.0003 3 ∣ 2.0001 ] . \begin{bmatrix}1 & 1 & | & 1\\ 0.0003 & 3 & | & 2.0001\end{bmatrix}. [ 1 0.0003 1 3 ∣ ∣ 1 2.0001 ] .
Step 2 — Eliminate. m 21 = 0.0003 / 1 = 0.0003 m_{21}=0.0003/1=0.0003 m 21 = 0.0003/1 = 0.0003 Why: this is the multiplier that zeros a 21 a_{21} a 21 2 ← _2\leftarrow 2 ← 2 − 0.0003 ⋅ _2-0.0003\cdot 2 − 0.0003 ⋅ 1 _1 1 a 22 = 3 − 0.0003 ( 1 ) = 2.9997 , b 2 = 2.0001 − 0.0003 ( 1 ) = 1.9998. a_{22}=3-0.0003(1)=2.9997,\quad b_2=2.0001-0.0003(1)=1.9998. a 22 = 3 − 0.0003 ( 1 ) = 2.9997 , b 2 = 2.0001 − 0.0003 ( 1 ) = 1.9998. [ 1 1 ∣ 1 0 2.9997 ∣ 1.9998 ] . \begin{bmatrix}1 & 1 & | & 1\\ 0 & 2.9997 & | & 1.9998\end{bmatrix}. [ 1 0 1 2.9997 ∣ ∣ 1 1.9998 ] .
Step 3 — Back-substitute.
x 2 = 1.9998 2.9997 = 0.66667 , x 1 = 1 − x 2 1 = 0.33333. ✓ x_2=\frac{1.9998}{2.9997}=0.66667,\qquad x_1=\frac{1-x_2}{1}=0.33333.\ \checkmark x 2 = 2.9997 1.9998 = 0.66667 , x 1 = 1 1 − x 2 = 0.33333. ✓
Worked example Contrast: NO pivoting (the cautionary tale)Keep tiny pivot 0.0003 0.0003 0.0003 m 21 = 1 / 0.0003 ≈ 3333.3 m_{21}=1/0.0003\approx 3333.3 m 21 = 1/0.0003 ≈ 3333.3 a 22 = 3 − 3333.3 ( 3 ) = − 9996.9 a_{22}=3-3333.3(3)=-9996.9 a 22 = 3 − 3333.3 ( 3 ) = − 9996.9 b 2 = 2.0001 − 3333.3 ( 1 ) = − 3331.3 b_2=2.0001-3333.3(1)=-3331.3 b 2 = 2.0001 − 3333.3 ( 1 ) = − 3331.3 3 − 10000 ≈ − 9997 3-10000\approx-9997 3 − 10000 ≈ − 9997 2 − 3333 = − 3331 2-3333=-3331 2 − 3333 = − 3331 x 2 ≈ 0.33334 x_2\approx0.33334 x 2 ≈ 0.33334 x 1 = ( 2.0001 − 3 x 2 ) / 0.0003 x_1=(2.0001-3x_2)/0.0003 x 1 = ( 2.0001 − 3 x 2 ) /0.0003 catastrophic loss of accuracy,
often giving x 1 ≈ 0 x_1\approx0 x 1 ≈ 0 0.3333 0.3333 0.3333 This is why we pivot.
3 × 3 3\times3 3 × 3 [ 2 1 − 1 ∣ 8 − 3 − 1 2 ∣ − 11 − 2 1 2 ∣ − 3 ] \begin{bmatrix}2&1&-1&|&8\\-3&-1&2&|&-11\\-2&1&2&|&-3\end{bmatrix} 2 − 3 − 2 1 − 1 1 − 1 2 2 ∣ ∣ ∣ 8 − 11 − 3 ∣ − 3 ∣ |{-3}| ∣ − 3 ∣ [ − 3 − 1 2 ∣ − 11 2 1 − 1 ∣ 8 − 2 1 2 ∣ − 3 ] \begin{bmatrix}-3&-1&2&|&-11\\2&1&-1&|&8\\-2&1&2&|&-3\end{bmatrix} − 3 2 − 2 − 1 1 1 2 − 1 2 ∣ ∣ ∣ − 11 8 − 3 m 21 = 2 / − 3 = − 0.667 m_{21}=2/-3=-0.667 m 21 = 2/ − 3 = − 0.667 m 31 = − 2 / − 3 = 0.667 m_{31}=-2/-3=0.667 m 31 = − 2/ − 3 = 0.667 [ − 3 − 1 2 ∣ − 11 0 0.333 0.333 ∣ 0.667 0 1.667 0.667 ∣ 4.333 ] \begin{bmatrix}-3&-1&2&|&-11\\0&0.333&0.333&|&0.667\\0&1.667&0.667&|&4.333\end{bmatrix} − 3 0 0 − 1 0.333 1.667 2 0.333 0.667 ∣ ∣ ∣ − 11 0.667 4.333 ∣ 0.333 ∣ |0.333| ∣0.333∣ ∣ 1.667 ∣ |1.667| ∣1.667∣ [ − 3 − 1 2 ∣ − 11 0 1.667 0.667 ∣ 4.333 0 0.333 0.333 ∣ 0.667 ] \begin{bmatrix}-3&-1&2&|&-11\\0&1.667&0.667&|&4.333\\0&0.333&0.333&|&0.667\end{bmatrix} − 3 0 0 − 1 1.667 0.333 2 0.667 0.333 ∣ ∣ ∣ − 11 4.333 0.667 m 32 = 0.333 / 1.667 = 0.2 m_{32}=0.333/1.667=0.2 m 32 = 0.333/1.667 = 0.2 a 33 = 0.333 − 0.2 ( 0.667 ) = 0.2 a_{33}=0.333-0.2(0.667)=0.2 a 33 = 0.333 − 0.2 ( 0.667 ) = 0.2 b 3 = 0.667 − 0.2 ( 4.333 ) = − 0.2 b_3=0.667-0.2(4.333)=-0.2 b 3 = 0.667 − 0.2 ( 4.333 ) = − 0.2 x 3 = − 0.2 / 0.2 = − 1 x_3=-0.2/0.2=-1 x 3 = − 0.2/0.2 = − 1 x 2 = ( 4.333 − 0.667 ( − 1 ) ) / 1.667 = 3 x_2=(4.333-0.667(-1))/1.667=3 x 2 = ( 4.333 − 0.667 ( − 1 )) /1.667 = 3 x 1 = ( − 11 − ( − 1 ) ( 3 ) − 2 ( − 1 ) ) / − 3 = 2 x_1=(-11-(-1)(3)-2(-1))/-3=2 x 1 = ( − 11 − ( − 1 ) ( 3 ) − 2 ( − 1 )) / − 3 = 2 ( 2 , 3 , − 1 ) (2,3,-1) ( 2 , 3 , − 1 ) Why correct? Check eq 1: 2 ( 2 ) + 3 − ( − 1 ) = 8 ✓ 2(2)+3-(-1)=8\ \checkmark 2 ( 2 ) + 3 − ( − 1 ) = 8 ✓
Common mistake "Pivot on the largest entry in the whole row."Why it feels right: big numbers seem more stable everywhere.
The fix: partial pivoting compares only entries down the current column (rows k … n k\dots n k … n scaling a different variable, changing the structure.
(Searching the whole submatrix = complete pivoting , a different, costlier method.)
Common mistake Forgetting to apply the operation tob \mathbf{b} b Why it feels right: the "matrix" is A A A A A A Fix: work on the
augmented matrix [ A ∣ b ] [A|\mathbf b] [ A ∣ b ]
Common mistake Back-substituting top-to-bottom.Why it feels right: we read top-down. Fix: the bottom equation has one unknown; you must
go bottom-up , otherwise the bracket still contains unknowns.
Intuition Operation count (the 80/20 fact)Forward elimination dominates: about 2 3 n 3 \tfrac{2}{3}n^3 3 2 n 3 n 2 n^2 n 2 doubling n n n Partial pivoting adds only O ( n 2 ) O(n^2) O ( n 2 )
If at some step all entries in column k k k k … n k\dots n k … n 0 0 0 A A A singular — no unique solution.
Recall Feynman: explain to a 12-year-oldImagine a staircase of equations. You want to knock out the first variable from every equation
except the top one — like erasing x x x teeny number
in front of x x x pick the equation with the BIGGEST x x x — that's pivoting.
Repeat for the next variable, and so on, until the last equation has only one unknown. Solve it,
then climb back up the staircase plugging in answers.
"Pick the Biggest, Swap, Subtract, then Climb Back Up."
P-B-S-S-C: P ivot column → B iggest ∣ | ∣ ∣ | ∣ S wap → S ubtract multiples → C limb (back-sub).
What is the goal of forward elimination in Gaussian elimination? Transform
A A A into an upper-triangular matrix
U U U (zeros below the diagonal) using row operations.
Why do we use partial pivoting? To avoid dividing by tiny/zero pivots; it keeps all multipliers
∣ m i k ∣ ≤ 1 |m_{ik}|\le 1 ∣ m ik ∣ ≤ 1 , controlling round-off error (numerical stability).
What is the partial-pivoting rule for column k k k Among rows
k … n k\dots n k … n , find the entry of largest absolute value in column
k k k and swap that row into position
k k k .
Formula for the multiplier m i k m_{ik} m ik m i k = a i k / a k k m_{ik}=a_{ik}/a_{kk} m ik = a ik / a k k — chosen so
a i k − m i k a k k = 0 a_{ik}-m_{ik}a_{kk}=0 a ik − m ik a k k = 0 .
The row update during elimination? a i j ← a i j − m i k a k j a_{ij}\leftarrow a_{ij}-m_{ik}a_{kj} a ij ← a ij − m ik a k j and
b i ← b i − m i k b k b_i\leftarrow b_i-m_{ik}b_k b i ← b i − m ik b k (apply to whole augmented row).
Back-substitution formula? x i = 1 u i i ( c i − ∑ j > i u i j x j ) x_i=\frac{1}{u_{ii}}\big(c_i-\sum_{j>i}u_{ij}x_j\big) x i = u ii 1 ( c i − ∑ j > i u ij x j ) , computed from
i = n i=n i = n down to
1 1 1 .
Why bottom-up for back-substitution? The last equation has only one unknown; each earlier
x i x_i x i needs the already-known
x j x_j x j (
j > i j>i j > i ).
Approximate flop count of Gaussian elimination? ∼ 2 3 n 3 \sim \tfrac{2}{3}n^3 ∼ 3 2 n 3 (forward elimination dominates; back-sub is
O ( n 2 ) O(n^2) O ( n 2 ) ).
What does an unavoidable zero pivot indicate? The matrix is singular — no unique solution.
Difference between partial and complete pivoting? Partial: search only the current column (rows
k . . n k..n k .. n ). Complete: search the whole remaining submatrix (more stable, costlier).
LU Decomposition — Gaussian elimination is an LU factorization; pivoting gives P A = L U PA=LU P A = LU Back-substitution and Forward-substitution Condition Number and Numerical Stability Round-off Error in Floating Point Determinants — product of pivots (× ( − 1 ) #swaps \times(-1)^{\text{\#swaps}} × ( − 1 ) #swaps det A \det A det A Cramer's Rule — exact but O ( n ! ) O(n!) O ( n !) Iterative Methods (Jacobi, Gauss-Seidel) — alternative for large sparse systems.
Elementary row operations
Multiplier m = a_ik / a_kk
Huge multipliers, rounding error
Intuition Hinglish mein samjhoDekho, hume solve karna hai A x = b A\mathbf{x}=\mathbf{b} A x = b n n n n n n upper-triangular banao (diagonal ke neeche
sab zero). Phir sabse neeche wali equation me sirf ek unknown bachta hai — usko solve karo, aur
upar ki taraf chadhte hue baaki values plug karte jao. Isko back-substitution kehte hain.
Ab partial pivoting ka funda: jab hum kisi column ko zero karne ke liye multiplier
m i k = a i k / a k k m_{ik}=a_{ik}/a_{kk} m ik = a ik / a k k a k k a_{kk} a k k k k k n n n sabse bada absolute value wala
entry dhoondhte hain aur uski row ko upar swap kar dete hain. Isse har multiplier ∣ m i k ∣ ≤ 1 |m_{ik}|\le 1 ∣ m ik ∣ ≤ 1
Upar wale chhote example (0.0003 wala) me dekha — bina pivoting ke answer galat aata, pivoting laga
ke ekdum sahi 1 / 3 , 2 / 3 1/3, 2/3 1/3 , 2/3 ∼ 2 3 n 3 \sim \tfrac{2}{3}n^3 ∼ 3 2 n 3 n n n Biggest pick karo, Swap, Subtract, phir Climb back up.
