Skip to content
Tutorials Center
My learning

Topics

Lesson 14 of 37 ยท Linear Systems

Gaussian Elimination

Solve linear systems Ax = b with Gaussian elimination: forward elimination, back substitution, partial pivoting, operation counts and a NumPy comparison, with runnable code.

A linear system is a set of equations in which every unknown appears only to the first power, such as

2x + y - z = 8, -3x - y + 2z = -11, -2x + y + 2z = -3.

Written in matrix form this is A x = b. Linear systems are everywhere: circuit analysis, structural engineering, least-squares fitting, finite-difference and finite-element methods, and each step of Newton's method for systems. Real problems may have thousands or millions of unknowns, so the algorithm must be both reliable and efficient.

The classic direct method is Gaussian elimination. You probably did it by hand in school; here you will turn it into a robust program and learn what its cost and weak points are.

The idea

Gaussian elimination has two phases:

  1. Forward elimination. Use row operations to turn A into an upper triangular matrix U (zeros below the diagonal), applying the same operations to b.
  2. Back substitution. Solve the triangular system from the last equation upwards: the last equation has one unknown, then the one above has two but one is known, and so on.
flowchart LR
    A["A x = b"] --> B["Forward elimination<br/>zeros below the diagonal"]
    B --> C["U x = c<br/>upper triangular"]
    C --> D["Back substitution<br/>x_n, x_n-1, ..., x_1"]

Two phases: make the system triangular, then solve it from the bottom up.

The row operation used is: subtract a multiple m = a_ik / a_kk of row k from row i. The number a_kk is the pivot, and m is the multiplier.

Implementation

Python Gaussian elimination without pivoting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The answer is x = 2, y = 3, z = -1. The check A @ x - b is the residual; for any linear solver you should look at it, because a small residual shows the computed x really satisfies the equations.

Why you need pivoting

The naive version divides by A[k, k], which may be zero, or tiny. A tiny pivot makes the multipliers huge, and huge multipliers magnify rounding errors. Take

0.0001 x + y = 1, x + y = 2.

The true solution is close to x = 1.0001, y = 0.9999.

Python A tiny pivot wrecks the answer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Without a row swap, the multiplier is 1e17, the arithmetic loses all information about the second equation and the computed x is 0 (wrong). After swapping rows so that the larger entry becomes the pivot, the answer is correct to full precision.

Partial pivoting: at step k, look down column k for the entry with the largest absolute value, and swap that row into the pivot position. It keeps all multipliers at most 1 in absolute value and makes Gaussian elimination backward stable in practice.

Python Gaussian elimination with partial pivoting

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The random 50x50 system matches NumPy to rounding level, and the matrix with a zero in the corner, which defeats the naive version, is solved easily.

What can go wrong: singular systems

A system can have no solution or infinitely many. In terms of A:

Case What elimination shows
Unique solution n non-zero pivots
No solution a row 0 = c with c โ‰  0
Infinitely many a zero row and more unknowns than independent equations

With floating point, a singular matrix may show a pivot of 1e-17 rather than exactly 0. Do not test for equality with zero; compare the pivot with a tolerance relative to the size of the matrix, or better, estimate the condition number (see Matrix Norms and Condition Numbers).

Operation count

For an n ร— n system, forward elimination takes about (2/3) nยณ floating-point operations and back substitution about nยฒ. The cubic term dominates, so doubling n makes the solve about eight times slower.

Python Cubic growth of the work

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The time rises steeply as n doubles, approaching a factor of eight for large n (small sizes are dominated by overhead and timings are noisy in a browser). Back substitution alone is only O(nยฒ), which is why reusing a triangular factorisation (next lesson) is so valuable.

Never solve A x = b by computing inv(A) @ b. It costs about three times as much and is usually less accurate. Use np.linalg.solve or a factorisation.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What are the two phases of Gaussian elimination?

    Elimination creates zeros below the diagonal; back substitution then solves for the unknowns from the last to the first.
  2. 2. Why is partial pivoting used?

    Choosing the largest entry in the column as pivot keeps the multipliers at most 1 in size.
  3. 3. Roughly how many operations does Gaussian elimination need for an n x n system?

    The triple loop of forward elimination dominates and gives a cubic cost.
  4. 4. What is the residual of a computed solution x?

    The residual measures how well x satisfies the equations; it is computable without knowing the exact solution.
  5. 5. Why should you avoid inv(A) @ b?

    Forming the inverse costs more and adds error; solve() or a factorisation is better.

Summary

  • Gaussian elimination turns A x = b into an upper triangular system and then back-substitutes.
  • Without pivoting a zero or tiny pivot ruins the answer; partial pivoting (swap in the largest entry of the column) makes it reliable.
  • The cost is about (2/3) nยณ operations; back substitution is only nยฒ.
  • Check the residual b - A x; use tolerances, not == 0, to detect singular matrices.
  • Prefer np.linalg.solve over computing an inverse.

Next: LU Decomposition and Pivoting