01 / 20

Choosing
Solution Methods

Learn when to use Elimination, Matrix Inverse, or LU Decomposition to solve \( Ax = b \) efficiently.

Linear Algebra

What Does Solving \( Ax = b \) Mean?

Given a system of \( n \) linear equations in \( n \) unknowns, we can write it as a single matrix equation \( Ax = b \), where \( A \) is the coefficient matrix, \( x \) is the unknown vector, and \( b \) is the right-hand side.

Three dominant approaches exist: Gaussian Elimination, Matrix Inverse, and LU Decomposition. Each excels in different scenarios.

The Three Methods at a Glance

Elimination
Row-reduce \( [A \mid b] \) to echelon form, then back-substitute. The workhorse for one-time solves.
Inverse
Compute \( A^{-1} \), then \( x = A^{-1}b \). Elegant in theory, expensive in practice for large systems.
LU Decomposition
Factor \( A = LU \) once, then solve \( Ly = b \) and \( Ux = y \). Ideal for multiple right-hand sides.

Why the Method Matters

Every algorithm has a computational cost measured in floating-point operations (flops). Choosing poorly can make your computation orders of magnitude slower.

Flops Matrix size n 10 50 100 500 1000 Inverse LU Elim.

Gaussian Elimination

Row-reduce the augmented matrix \( [A \mid b] \) to upper-triangular form \( U \), then solve by back-substitution.

[A | b] * * * | * * * * | * * * * | * Row ops [U | c] * * * | * 0 * * | * 0 0 * | * Back-sub x x₁ x₂ x₃
Cost: \( \sim \frac{2}{3}n^3 \) flops for one solve

The Matrix Inverse Approach

If \( A \) is invertible, the solution is \( x = A^{-1}b \). Computing \( A^{-1} \) requires solving \( n \) systems: \( A \cdot [\text{col}_1 \mid \cdots \mid \text{col}_n] = I_n \).

1
Compute \( A^{-1} \): costs \( \sim 2n^3 \) flops (equivalent to \( n \) elimination solves).
2
Multiply \( A^{-1}b \): costs \( \sim 2n^2 \) flops: fast once you have the inverse.
3
Numerical risk: the inverse amplifies rounding errors more than elimination does.

LU Decomposition

Factor \( A = LU \), where \( L \) is lower-triangular and \( U \) is upper-triangular. Then solve in two cheap triangular steps.

A * * * * * * * * * = L 1 0 0 * 1 0 * * 1 · U * * * 0 * * 0 0 * Ly=b y Ux=y x
Factor: \( \sim \frac{2}{3}n^3 \) (once)
Each solve: \( \sim 2n^2 \)

Key Distinction: One Solve vs. Many

Single Solve
One \( b \) vector: Elimination wins. It solves directly with \( \frac{2}{3}n^3 \) flops and no extra storage.
Multiple Solves
Same \( A \), many \( b \)'s: LU wins. Factor once \( (\frac{2}{3}n^3) \), then each solve is \( O(n^2) \).

How to Choose Your Method

Solve Ax = b Multiple b vectors for same A? Yes No LU Decomposition
Need \( A^{-1} \) explicitly?
No Yes Gauss Elimination
Compute \( A^{-1} \)

Step-by-Step Decision Process

1
Count your right-hand sides. One \( b \)? Go to step 3. Multiple \( b \)'s? Go to step 2.
2
Factor \( A = LU \) (with partial pivoting). Store \( L \) and \( U \). Solve each \( b_i \) via forward/back substitution.
3
Form \( [A \mid b] \) and apply Gaussian elimination with partial pivoting to row-reduce to echelon form.
4
Back-substitute to find \( x \). Verify by computing the residual \( r = b - Ax \).
5
Only compute \( A^{-1} \) if you explicitly need the inverse (e.g., for a formula or theoretical derivation).

Example 1: Single Solve

Solve the system: \( \begin{cases} 2x + y - z = 8 \\ -3x - y + 2z = -11 \\ -2x + y + 2z = -3 \end{cases} \)

1
Augmented matrix: \( \left[\begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{array}\right] \)
2
Eliminate below pivot: \( R_2 \leftarrow R_2 + \tfrac{3}{2}R_1 \), \( R_3 \leftarrow R_3 + R_1 \) to get upper triangular form.
3
Back-substitute: \( z = -1 \), \( y = 3 \), \( x = 2 \). Solution: \( x = (2, 3, -1)^T \).

Example 2: Multiple Right-Hand Sides

A circuit analysis requires solving \( Ax = b_k \) for \( k = 1, 2, \ldots, 100 \), where \( A \) is a fixed \( 50 \times 50 \) matrix representing the circuit topology.

LU cost
Factor: \( \frac{2}{3}(50)^3 \approx 83{,}333 \) flops. Each solve: \( 2(50)^2 = 5{,}000 \) flops. Total: \( \approx 583{,}333 \) flops.
Elimination cost
Each solve: \( \frac{2}{3}(50)^3 \approx 83{,}333 \) flops \( \times 100 = 8{,}333{,}300 \) flops. That is 14× more work!

Example 3: When You Need \( A^{-1} \)

A statistics formula requires the matrix \( (X^TX)^{-1} \) explicitly to compute the covariance matrix of regression coefficients: \( \text{Cov}(\hat{\beta}) = \sigma^2(X^TX)^{-1} \).

Even in this case, the actual computation is typically done via LU: factor \( A = LU \), then solve \( A \cdot e_i = \text{col}_i(A^{-1}) \) for each standard basis vector \( e_i \). Total cost: \( \sim 2n^3 \) flops.

Numerical Stability: Partial Pivoting

In practice, all three methods require pivoting: swapping rows to avoid dividing by small numbers that amplify rounding errors.

Elimination + Pivoting
At each step, swap in the row with the largest absolute value in the pivot column. This is the standard in all modern software.
LU + Pivoting
We actually compute \( PA = LU \), where \( P \) is a permutation matrix encoding the row swaps. Then solve \( Ly = Pb \), \( Ux = y \).

Common Mistakes

✕ Always using the inverse
Computing \( A^{-1} \) for every \( Ax = b \) is 3× slower and less stable. Use elimination or LU instead.
✕ Re-factoring for each \( b \)
If \( A \) stays the same, doing full elimination for each new \( b \) wastes \( O(n^3) \) flops per solve. Factor once with LU.
✕ Skipping pivoting
Without partial pivoting, a zero or near-zero pivot causes division errors or massive numerical inaccuracy.

Method Comparison

Elimination LU Decomp. Inverse
Setup cost \( \sim \frac{2}{3}n^3 \) \( \sim \frac{2}{3}n^3 \) \( \sim 2n^3 \)
Per-solve cost \( \sim \frac{2}{3}n^3 \) \( \sim 2n^2 \) \( \sim 2n^2 \)
Best scenario Single \( b \) Many \( b \)'s Need \( A^{-1} \) itself
Stability Excellent Excellent Weaker
Storage \( O(n^2) \) \( O(n^2) \) \( O(n^2) \)

Question 1 of 5

You need to solve \( Ax = b \) for a single right-hand side \( b \). Which method is most efficient?

Question 2 of 5

A simulation requires solving \( Ax = b_k \) for 500 different vectors \( b_k \), all with the same coefficient matrix \( A \). What is the most efficient approach?

Question 3 of 5

What is the approximate flop count for computing the inverse of an \( n \times n \) matrix?

Question 4 of 5

Why is partial pivoting essential in Gaussian elimination?

Question 5 of 5

In LU decomposition with \( PA = LU \), what does the matrix \( P \) represent?