5.1 Forward Substitution

The equation Ly = b is solved by forward substitution as follows.

yi=bi-j=1i-1lijyilii,where1iny_{i}=\frac{b_{i}-\displaystyle\sum_{j=1}^{i-1}l_{ij}y_{i}}{l_{ii}},% \operatorname{where}1\leq i\leq n (46)

Algorithm 4 implements Equation 46.

Algorithm 4: Forward Substitution
for i=1,,ni=1,\cdots,n
   α=bi\alpha=b_{i}
   for j=1,,i-1j=1,\cdots,i-1
      α=α-lijyj\alpha=\alpha-l_{ij}y_{j}
   yi=αliiy_{i}=\displaystyle\frac{\alpha}{l_{ii}}

If L is unit lower triangular, the division by lii is unnecessary (since lii is 1). Notice that the update to yi is accumulated as an inner product in α\alpha.