Why triangular is the easy case
In the previous guide you watched Gaussian elimination grind a dense matrix A down into a factorization A = L U, where L is lower triangular (zeros above the diagonal) and U is upper triangular (zeros below it). That felt like a lot of work, and it was — about two-thirds of n^3 operations. The natural question is: why bother? Why is a triangular system any better than the original tangle? This guide is the answer, and it is a satisfying one: a triangular system can be solved almost for free, in a single tidy sweep, and that sweep is what actually delivers your x.
Here is the picture. A general system A x = b couples every unknown to every other one: row 1 mentions x_1 through x_n all at once, and you cannot pin down any single unknown without untangling the rest. A triangular system breaks that knot. In an upper-triangular system U x = b, the very last equation involves only one unknown — it reads (something) times x_n = (something), so x_n falls out immediately by a single division. Once you know x_n, the second-to-last equation has only x_{n-1} left unknown, so it too divides out. You climb the staircase one step at a time, and at every step exactly one new unknown is waiting alone for you.
Back substitution, walked through
The algorithm that climbs that staircase from the bottom up is called back substitution, and it solves the upper-triangular half U x = b. The name is literal: you find the last unknown, then substitute it back into the equation above, which leaves one fresh unknown there, and repeat. Let us do a tiny 3-by-3 by hand so the motion is unmistakable.
Solve U x = b :
2 x1 + 1 x2 - 1 x3 = 3
3 x2 + 2 x3 = 5
4 x3 = 8
Row 3: 4 x3 = 8 -> x3 = 2
Row 2: 3 x2 + 2(2) = 5 -> 3 x2 = 1 -> x2 = 1/3
Row 1: 2 x1 + (1/3) - 2 = 3 -> 2 x1 = 3 - 1/3 + 2 = 14/3 -> x1 = 7/3- Start at the bottom row, which contains a single unknown x_n; divide its right-hand side by the diagonal entry to get x_n. (That diagonal entry is the pivot — it must not be zero, which is exactly what the next guide on pivoting guarantees.)
- Move up one row. Every unknown below it is now known, so plug those values in; what remains is one equation in one unknown again.
- Subtract the known terms from the right-hand side, then divide by this row's diagonal entry to release the next unknown.
- Repeat until you reach the top row and the last unknown x_1 falls out. You now have the whole vector x, top to bottom.
Forward substitution is the mirror image. It solves a lower-triangular system L y = b, but now the easy equation is the first one (it mentions only y_1), so you start at the top and walk down. The motion is identical, just upside down. The reason we care about both is that A = L U splits one hard solve into two easy ones, which the next section makes precise.
Two triangular solves replace one hard one
Now we can see why the factorization was worth its sweat. To solve A x = b once you have A = L U, you do not touch A again. You substitute: A x = b becomes L U x = b. Name the inner piece y = U x. Then L y = b is lower triangular — solve it by forward substitution to get y. Then U x = y is upper triangular — solve it by back substitution to get x. One genuinely hard problem has become two genuinely easy ones, in sequence.
A x = b with A = L U step 1 (forward substitution): L y = b -> y [lower triangular] step 2 (back substitution): U x = y -> x [upper triangular]
Count the cost and the strategy explains itself. A triangular solve touches each entry of the triangle about once: for an n-by-n triangle that is roughly n^2/2 multiply-add operations, so two of them cost about n^2 — an operation count of O(n^2). Compare that to the O(n^3) of the elimination that built L and U. For n = 1000, n^3 is a thousand times bigger than n^2. The expensive step is the factorization; the triangular solves that actually produce x are cheap by comparison.
This cost gap is the whole reason the LU factorization is stored and kept around. Suppose you must solve A x = b for the same A but many different right-hand sides b — different loads on the same bridge, different days of the same circuit. You factor A into L U exactly once, paying the O(n^3) bill a single time, and then each new b costs only an O(n^2) pair of triangular sweeps. This is the celebrated factor-once-solve-many pattern, and triangular solves are the cheap second half that makes it pay off.
Is the sweep trustworthy? Stability and the pivots
A fair worry: we are doing a long chain of divisions and subtractions in floating point, where arithmetic is not exact — 0.1 has no exact binary form and addition is not even associative. Does the error pile up dangerously as we climb? The reassuring honest answer is no, for triangular solves specifically. Back and forward substitution are backward stable: the computed x is the exact solution of a triangular system whose entries differ from the true ones only by a whisker, on the order of the unit roundoff. That is the realistic gold standard in numerical computing — not an exactly right answer, but the exactly right answer to a problem a hair's breadth away from yours.
There is one absolute requirement the sweep depends on: every diagonal entry you divide by — every pivot — must be nonzero. If U has a zero on its diagonal, the matrix is singular and there is no unique x to find; the division would blow up to infinity or NaN, and that is the algorithm honestly reporting that the problem has no answer. Even a pivot that is merely tiny (not exactly zero) is a warning sign, because dividing by a near-zero number magnifies error. Keeping pivots safely away from zero is precisely the job of partial pivoting, the subject of the very next guide — so the triangular factors you feed into back substitution are arranged to have well-behaved diagonals in the first place.
Why this is also the reason you never invert
Beginners often write x = A^{-1} b in code, copying the textbook formula literally. Triangular solves are exactly why you should not. To form A^{-1} you would solve A X = I — that is n separate right-hand sides (the columns of the identity), so n triangular-solve pairs on top of the factorization, more work than you need. Then multiplying A^{-1} by b is yet another O(n^2) step that adds its own rounding error. Solving directly with one forward and one back substitution is cheaper and more accurate, because you never built and stored the error-prone inverse in between.
One last connection looking forward. Because a triangular solve is so cheap and so stable, it becomes a reusable building block far beyond this rung. When matrices are sparse or banded — say a tridiagonal system, where the Thomas algorithm is nothing but forward-then-back substitution stripped down to three diagonals — the same sweep runs in O(n) instead of O(n^2). And in later rungs, preconditioners and iterative refinement repeatedly lean on a fast triangular solve as their inner step. The humble staircase climb you just learned is one of the most-used kernels in all of scientific computing.