Consider a matrix equation $Ax=b$. When solving it, I decomposed $A$ with the Doolittle algorithm to its lower and upper triangular matrix, $L$ and $U$ respectively. Now, the above equation can be formulated as $LUx=b$, and solved in two steps:
- $Ly=b$, by forward substitution
- $Ux=y$, by backward substitution
where the algorithm for 1. and 2. is:
- $y_0=\frac{b_0}{L_{00}}$ and $y_i=\frac{b_i-\sum\limits_{j=0}^{i-1}{L_{ij}y_j}}{L_{ii}}$ for $i=1...n$
- $x_n=\frac{y_n}{U_{nn}}$ and $x_i=\frac{y_i-\sum\limits_{j=i}^{n}{U_{ij}x_j}}{U_{ii}}$ for $i=n-1...0$
Given that the Doolittle algorithm guarantees that $L_{ii}$ is always $1$, this element in the first case can be ignored when dividing. However, that is not the case for $U_{ii}$ in case 2. So my question is, how to handle those elements where $U_{ii}=0$? In other words, how should I calculate $x_i$ if $U_{ii}=0$?