 Triangular solves for LU decomposition

Given Pivoted LU decomposition $PA=LU$, the linear system $Ax=b$ is equivalent to $LUx=Pb$. Introduce the intermediate vector $y=Ux$: first use forward substitution to solve $Ly=Pb$, then back substitution to solve $Ux=y$. With unpivoted LU decomposition, $P=I$ is the identity matrix, so the first right-hand side is simply $b$.^[ref]

For the factors in Computed three-by-three LU decomposition and $b=(7,23,26{)}^T$, forward substitution givesThen back substitution givesDirect matrix multiplication verifies $A(1,2,3{)}^T=(7,23,26{)}^T$. More generally, the back substitution recurrence isThe direction matters: the last row contains only $x_n$, whereas the first row generally involves every unknown. No dense matrix inverse is needed for either triangular solve.