1

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:

  1. $Ly=b$, by forward substitution
  2. $Ux=y$, by backward substitution

where the algorithm for 1. and 2. is:

  1. $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$
  2. $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$?

user340585
  • 11
  • The method only works, if $A$ is invertible. In this case, the diagoanal elements of $U$ are non-zero. – Peter May 18 '16 at 18:28
  • Even for a sparse matrix $A$? – user340585 May 18 '16 at 18:55
  • If one diagonal-element of $U$ is zero , the matrix $A$ must have determinant $0$, so it is not invertible. So, the non-zero condition also holds in the sparse case. – Peter May 18 '16 at 19:10
  • @Peter I think that answers my question to the spot, although the actual trouble-shooting has just begun for me. I obviously get 0-elements on the U diagonal, when there shouldn't be any, as I'm working on with a test case for the Newton-Raphson method, and it is supposed to converge. If $A$ is not invertible, then $Ax=b$ has no solutions? Also, you can put your comments in an answer, although short, this is exactly the piece of information that I needed. – user340585 May 18 '16 at 22:47
  • If $A$ is not invertible, $Ax=b$ can have infinite many solutions and no solution. I am not sure, whether the method is designed for that case. – Peter May 19 '16 at 10:48

0 Answers0