Show that the eigenvalues of $L^{-1}AL^{-T}$ are clustered around 1 when $R$ is small where $L, L^{T}$ are incomplete Cholesky factors.

Question

The incomplete Cholesky factorisation of a $A$ is $A = LL^T + R$ where $R$ is the remainder and the sparsity pattern of $L$ is the sparsity pattern of lower triangular part of $A$. I need to show that the eigenvalues of $L^{-1}AL^{-T}$ are clustered around 1 when $R$ is small. I was able to show that $|1-\lambda| \leq \|L^{-1}\|\|L^{-T}\|\|R\|$ where $\lambda$ is any eigenvalue of $L^{-1}AL^{-T}$. At this point it will be sufficient to show that $\|L^{-1}\|\|L^{-T}\|$ is small, yet I don't know how to do this. I would appreciate any help.

Answer 1

Consider the following example

$$ A = \begin{bmatrix} 1 & 0 \\ 0 & 2 \epsilon \end{bmatrix},\quad L = \begin{bmatrix}1 & 0 \\ 0 & \sqrt{\epsilon} \end{bmatrix}, \quad \quad R=\begin{bmatrix} 0 & 0 \\ 0 & \epsilon\end{bmatrix}. $$

where $\epsilon > 0$ is small. Then we have $\|A - LL^\top\| = \|R \| = \epsilon$. However,

$$ L^{-1}AL^{-\top} = \begin{bmatrix} 1 &0 \\ 0 & 2\end{bmatrix}. $$

One of the eigenvalues of $A$, $\lambda = 2$, is quite far from $1$! In this case, your bound gives $|\lambda - 1| \le \|L^{-1}\|\|L^{-\top}\|\|R\| = \epsilon^{-1/2} \cdot \epsilon^{-1/2} \cdot \epsilon = 1$; your bound is sharp.

For a more complete answer, you need to precisely describe how you obtain $L$ from $A$. There are many different variants of incomplete Cholesky; which do you use? The results for the stability of Cholesky factorization without pivoting may be useful to you. In general, error bounds in linear algebra depend on the conditioning of the underlying problem. If $A$ is ill-conditioned (as it is in this example), $|\lambda - 1|$ will indeed be quite a bit larger than $\|R\|$.