Solving triangular systems

How to solve triangular systems.

$Lx=b$ with $L$ lower triangular. Algebraic equation:

$$\sum _{j=1}^i{l}_{ij}{x}_j=b_i$$

Solve for $x_i$:

$$\begin{array}{c}{l}_{ii}{x}_i=b_i-\sum _{j=1}^{i-1}{l}_{ij}{x}_j\\ x_i=l_{ii}^{-1}(b_i-\sum _{j=1}^{i-1}{l}_{ij}{x}_j)\end{array}$$

We can solve iteratively starting from $x_1$, then $x_2$, $x_3$, …, $x_n$.

This is possible because $L$ is lower triangular.

This process is fast and accurate.

The same process applies to upper triangular matrices: $Ux=b$.

$$\begin{array}{c}\sum _{j=i}^n{u}_{ij}{x}_j=b_i\\ x_i=u_{ii}^{-1}(b_i-\sum _{j=i+1}^n{u}_{ij}{x}_j)\end{array}$$

We solve iteratively in the reverse order: $x_n$, $x_{n-1}$, …, $x_1$.

The computational cost of solving a triangular system is $O(n^2)$.