= Forward substitution
{title2=$y_i=(c_i-\sum_{j<i}l_{ij}y_j)/l_{ii}$}
<Forward substitution> solves a <linear system> $Ly=c$ with a <lower triangular matrix> $L$ and nonzero diagonal, from the first row downward:
$$
y_i=\frac{c_i-\sum_{j=1}^{i-1}l_{ij}y_j}{l_{ii}},\qquad i=1,\ldots,n.
$$
The first <sum> is empty, so $y_1=c_1/l_{11}$. Each subsequent row uses only components already found. For a <unit triangular matrix> $L$, omit the division because $l_{ii}=1$. The complementary procedure, <back substitution>, solves an <upper triangular matrix> system from the last row upward.<Fundamentals of Numerical Computation by Tobin A. Driscoll and others>[§2.3.2, equations (2.3.7)–(2.3.9), and §2.3.3, Algorithms 2.3.1–2.3.2: forward and backward substitution]{ref}
Back to article page
