5 Solving Triangular Systems 5.1 Forward Substitution 5.3 Outer Product Formulation

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$

$\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 u_ii is unnecessary (since u_ii is 1). Notice that the update to x_i is accumulated as an inner product in $\alpha$.