I'm studying iterative methods for solving linear system, and I find the following setting in Wikipedia:
Consider a matrix splitting $A = M-N$, where $A,M,N$ are all symmetric and positive definite matrices. Define iteration matrix $C=I-M^{-1}A$. We aim to show that the condition number $\kappa(I-C)=\kappa(M^{-1}A)$ is not too large, which ensures that iterative method converges fairly fast. Wikipedia gives the following bound on $\kappa(M^{-1}A)$: $$\kappa(M^{-1}A) \leq \frac{1+\rho(C)}{1-\rho(C)}$$ where $\rho(C)$ denotes the spectral radius of matrix $C$. Here we are taking the condition number with respect to the Euclidean 2-norm. That is to say, we have $\kappa(M^{-1}A) = \frac{\sigma_{max}(M^{-1}A)}{\sigma_{min}(M^{-1}A)}$, where $\sigma_{max},\sigma_{min}$ denote the largest/smallest singular value of any matrix, respectively.
Any ideas on proving this upper bound? Any help/hint would be greatly appreciated!
(Link for reference: https://en.wikipedia.org/wiki/Preconditioner)

  • $\begingroup$ Hint: $\kappa(M^{-1}A)=\kappa(I-(I-M^{-1}A))$. $\endgroup$ – Wolfgang Bangerth Dec 10 '20 at 5:05
  • $\begingroup$ HI Professor Bangerth, Thank you so much for your response! I have tried to use the expression you gave above. However, it seems that I still can't find an ideal upper bound for $\kappa(I-C)$. FYI, I have even tried more advanced tools like Weyl's inequality (bounding the singular values of matrix sums). It seems that it's still pretty hard to characterize $\sigma_{max}(I-C)$ and $\sigma_{min}(I-C)$. I guess here I probably need to use some properties related to $C$? (AS $C$ is a product of two symmetric and positive definite matrices, $C$ probably has some really nice properties?) $\endgroup$ – randombeaver Dec 10 '20 at 5:36
  • $\begingroup$ For instance, I can show that all eigenvalues of $C$ are in the interval $(0,1)$. My guess is that this might imply that the 2-norm $||I-C||$ can't be too large? (ideally upper bounded by $1+\rho(C)$)? $\endgroup$ – randombeaver Dec 10 '20 at 5:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.