Suppose we have a matrix $A$ with is its $LU$-decomposition such that $A=LU$ and suppose that $U$ is ill conditioned ($\left \| U \right \|\left \| U^{-1} \right \|$ is large) , does it mean that $A$ is ill conditioned ?
Is $A$ ill conditioned matrix
lu decompositionmatrix decompositionnumerical methods
Related Solutions
This problem is difficult for numerical rather than computational reasons. Part of the problem is that you really need to be confident that the matrix is full rank, because if it is not, then a single error can make a determinant very large when it should actually be zero. For illustration, suppose we were trying to compute the determinant of
$$A =\begin{bmatrix} M & M \\ M & M \end{bmatrix}$$
where $M$ is very large. This determinant is of course $0$. Let's say some roundoff gave us
$$B = \begin{bmatrix} M & M \\ M & (M+\varepsilon) \end{bmatrix}$$
for some small $\varepsilon$. Now $A$ has determinant $0$ but $B$ has determinant $M\varepsilon$, which may be quite large. The coefficient gets much larger in higher dimensions (though it is always first order, as the determinant is a polynomial in the entries).
If you are confident that the matrix is full rank, then my best suggestion would be to perform an SVD, check to see that all the singular values are nonzero, then if they are not, do it again in higher precision.
Edit: there is one more thing you can do. Because $\text{det}(A)=\text{det}(A^T)$, you can perform column operations. In this case what you should do is rescale the matrix so that the largest entry in each column is $1$. You will multiply column $x_i$ by a number $c_i$, which will also multiply the determinant by $c_i$. Accordingly you will want to divide the final result by $c_i$, so that you get the determinant of the matrix you started with. You will still find that the matrix is extremely ill-conditioned afterward; for example you will still have a column with one entry of order $1$ and another of order $10^{-40}$. But the conflict between the first two columns and the rest will be gone.
Of course. Think of the matrix $A$ defined as $$ A = \mathrm{diag}(1, 2, \ldots, N), $$ where $\mathrm{diag}$ is the diagonal matrix. For any value $N$, the condition number of the matrix will be $K_2(A) = N$ and the smallest singular value $\sigma_{\min} = 1$. The matrix can also be small, for example $$ A = \begin{pmatrix} 1 & 0 \\ 0 & N \end{pmatrix}, $$ has the same spectral properties as the matrix above.
Best Answer
What if simply we consider $$A=\left[\matrix{1&0\cr0&1}\right],\quad L=\left[\matrix{10^n&0\cr0&10^{-n}}\right],\quad U=\left[\matrix{10^{-n}&0\cr0&10^{n}}\right]?$$ Clearly $L$ is lower triangular, $U$ is upper triangular, $A=LU$ and $$\hbox{cond}_2(A)=1,\quad\hbox{cond}_2(L)=\hbox{cond}_2(U)=10^{2n}.$$