5.2 Backward Substitution

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

xi=yi-j=i+1nuijxiuii,wherei=n,n-1,,1x_{i}=\frac{y_{i}-\displaystyle\sum_{j=i+1}^{n}u_{ij}x_{i}}{u_{ii}},% \operatorname{where}i=n,n-1,\cdots,1 (63)

Algorithm 5 implements Equation 63.

Algorithm 5: Backward Substitution
for i=n,,1i=n,\cdots,1
   for j=i+1,,nj=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.