I'm really confused about the Doolittle algorithm, so I need some help.
At the end of the description at wikipedia, it says
It is clear that in order for this algorithm to work, one needs to have $a_{n,n}^{(n-1)}\not=0$ at each step (see the definition of $l_{i,n}$).
And also all the book says this, so I think I'm wrong somewhere, but take a look at the following example:
$$A:= \left[ \begin {array}{cccc} 1&2/3&1/2&2/5\\ 3/2&1&3 /4&3/5\\ 2&4/3&1&4/5\\ 5/2&5/3&5/4 &1\end {array} \right]. $$
In $A$ each column and each row has linear dependence, so for example we can get each row with a constant multiplication of the first row. To make it clear, if we denote the $i$-th row with $r_i$, then $r_2=(3/2)r_1$, $r_3=2r_1$ and $r_4=(5/2)r_1$.
So let's try to run the Doolittle algorithm! $A^{(0)}:=A$, $a_{1,1}^{(0)} = 1\neq 0$. It' ok. Now compute $L_1$. $$ L_1 = \left[ \begin {array}{cccc} 1&0&0&0\\ -a_{2,1}^{(0)}/a_{1,1}^{(0)}&1&0&0 \\ -a_{3,1}^{(0)}/a_{1,1}^{(0)}&0&1&0\\ -a_{4,1}^{(0)}/a_{1,1}^{(0)}&0&0&1 \end {array} \right] = \left[ \begin {array}{cccc} 1&0&0&0\\ -3/2&1&0&0 \\ -2&0&1&0\\ -5/2&0&0&1 \end {array} \right]. $$ Now if we take a step in the iteration, we get \begin{align} A^{(1)}=L_1 A^{(0)} &= \left[ \begin {array}{cccc} 1&0&0&0\\ -3/2&1&0&0 \\ -2&0&1&0\\ -5/2&0&0&1 \end {array} \right] \cdot \left[ \begin {array}{cccc} 1&2/3&1/2&2/5\\ 3/2&1&3 /4&3/5\\ 2&4/3&1&4/5\\ 5/2&5/3&5/4 &1\end {array} \right] \\ \\ &= \left[ \begin {array}{cccc} 1&2/3&1/2&2/5\\ 0&0&0&0 \\ 0&0&0&0\\ 0&0&0&0\end {array} \right]. \end{align} And here the Doolittle algorithm stops, because $a_{2,2}^{(1)} = 0$, and that's why we couldn't compute $L_2$.
And there are theorems about it, that $a_{n,n}^{(n-1)}$ must be nonzero $n=1,\dots,N-1$ (where $A$ is an $N \times N$ matrix) or equivalently all the principal subminors have to be nonzero from $n=1,\dots,N-1$. You can find a related question here.
We obtain that all these statements are false in our $4 \times 4$ size $A$ matrix.
But why we need to run $n$ from $1$ to $N-1$, if get an upper triangle matrix $A^{(\ell)}$ for an $\ell < N-1$ ?
Because we've got an upper triangle matrix for $A^{(1)}$, and as we see $$ L_1^{-1} = \left[ \begin {array}{cccc} 1&0&0&0\\3/2&1&0&0 \\ 2&0&1&0\\ 5/2&0&0&1\end {array} \right] $$ is a lower triangle matrix.
So it seems to me with $L:=L_1^{-1}$, and $U:=A^{(1)}$, we've got an $LU$ decomposition of $A$.
Questions.
- Am I wrong somewhere?
- If I'm right, then is there a modified Doolittle algorithm, which do the job for the example given above? I'm really need a citation too.
- Is this true, that in the example $L$ and $U$ gives a unique $LU$ decomposition of $A$, if we restrict that the diagonal of $L$ in the decomposition contains only ones? If it is or not, why?