5.2 Backward Substitution

The equation y = Ux is solved by backward substitution as follows.

$$x_{i}=\frac{y_{i}-\displaystyle\sum_{j=i+1}^{n}u_{ij}x_{i}}{u_{ii}},\mbox{ where }i=n,n-1,\cdots,1$$ (63)

Algorithm 5 implements Equation 63.

Algorithm 5: Backward Substitution
for $i=n,\cdots,1$
   for $j=i+1,\cdots,n$

If U is unit upper triangular, the division by uii is unnecessary (since uii is 1). Notice that the update to xi is accumulated as an inner product in $\alpha$.