12.5 Forward Substitution

Types: N/A
Examples: N/A
Constructions: N/A
Generalizations: N/A

Properties: N/A
Sufficiencies: N/A
Questions: N/A

Forward Substitution: Lower-Triangular

L \vec{x} = \vec{b}

Let $L \vec{x} = \vec{b}$ be a given 12.1 The Square Linear-Systems Problem problem with 8.7 Lower-Triangular Matrix $L \in R^{n \times n}$ and $\vec{b} \in R^{n}$ . If diagonal values $u_{i i} \neq 0$ for all $i \in {1, 2, \dots, n}$ , then our linear-system problem has a unique solution. This solution can be found using the forward substitution algorithm:

\begin{aligned} x_{1} & = \frac{b_{1}}{u_{11}} \\ x_{i} & = \frac{1}{u_{i i}} (b_{i} - \sum_{j = 1}^{i - 1} u_{i j} x_{j}) \end{aligned}

where $i = 2, 3, \dots, n$ .

Remark. In addition to solving problems involving 8.9 Upper-Triangular Matrix, we also use 8.7 Lower-Triangular Matrix for the 12.1 The Square Linear-Systems Problem.

L \cdot \vec{y} = \vec{b}

$⧫$
\begin{proof}[Informal Proof.]
Let's look at a system of 4 linear equations in 4 unknowns with a lower-triangular coefficient matrix $L$ . Suppose

\begin{aligned} [\begin{array}{c} l_{11} & 0 & 0 & 0 \\ l_{21} & l_{22} & 0 & 0 \\ l_{31} & l_{32} & l_{33} & 0 \\ l_{41} & l_{42} & l_{43} & l_{44} \end{array}] [\begin{array}{c} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \end{array}] & = [\begin{array}{c} b_{1} \\ b_{2} \\ b_{3} \\ b_{4} \end{array}] \end{aligned}

Let's look at the individual row entries of the left and right hand side.

\begin{aligned} l_{11} y_{1} & + 0 & + 0 & + 0 & = b_{1} \\ l_{21} y_{1} & + l_{22} y_{2} & + 0 & + 0 & = b_{2} \\ l_{31} y_{1} & + l_{32} y_{2} & + l_{33} y_{3} & + 0 & = b_{3} \\ l_{41} y_{1} & + l_{42} y_{2} & + l_{43} y_{3} & + l_{44} y_{4} & = b_{4} \end{aligned}

Notice that the first equation has only one unknown. Furthermore, if $u_{i i} \neq 0$ for all $i$ , we solve for the unknown

y_{1} = \frac{1}{l_{11}} \cdot (b_{1})

Because we know $y_{1}$ , we can continue and solve for $y_{2}$ and so on.

l_{21} y_{1} + l_{22} y_{2} = b_{2} ⟹ y_{2} = \frac{1}{l_{22}} \cdot (b_{4} - l_{21} y_{1})

We continue with row 3 for $y_{3}$ .

\begin{aligned} l_{31} y_{1} + l_{32} y_{2} + l_{33} y_{3} = b_{3} & ⟹ y_{3} = \frac{1}{l_{33}} (b_{3} - l_{31} y_{1} - l_{32} y_{2}) \\ ⟹ y_{3} = \frac{1}{l_{33}} (b_{3} - \sum_{j = 1}^{2} l_{3 j} y_{j}) \end{aligned}

Finally, we can find $y_{4}$ .

\begin{aligned} l_{41} y_{1} + l_{42} y_{2} + l_{43} y_{3} + l_{44} y_{4} & ⟹ y_{4} = \frac{1}{l_{44}} (b_{4} - l_{41} y_{1} - l_{42} y_{2} - l_{43} y_{3}) \\ ⟹ y_{4} = \frac{1}{l_{44}} (b_{4} - \sum_{j = 1}^{3} u_{4 j} y_{j}) \end{aligned}

We have now solved our linear systems problem for unknowns $y_{i}$ using forward substitution.
\end{proof}