# 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}},% \operatorname{where}i=n,n-1,\cdots,1$ (47)

Algorithm 5 implements Equation 47.

Algorithm 5: Backward Substitution
 for $i=n,\cdots,1$ $\alpha=y_{i}$ for $j=i+1,\cdots,n$ $\alpha=\alpha-u_{ij}x_{j}$ $x_{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$.