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 (47)

Algorithm 5 implements Equation 47.

Algorithm 5: Backward Substitution
for i=n,,1i=n,\cdots,1
   α=yi\alpha=y_{i}
   for j=i+1,,nj=i+1,\cdots,n
      α=α-uijxj\alpha=\alpha-u_{ij}x_{j}
   xi=αuiix_{i}=\displaystyle\frac{\alpha}{u_{ii}}

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.