1
$\begingroup$

I have a question regarding the condition number of two different perturbation matrices. To start with let $A$ be a spd matrix with elements defined by $a_{i,j} = \int\limits_{\Omega\subset \mathbb{R}^d} \nabla \varphi_i\cdot \nabla\varphi_j \,d\Omega$ arising in Finite Element Methods with $\varphi_i$ basis functions of the approximation space. Furthermore let $cond_2(A)$ be the condition number of $A$.

  1. My first question is regarding the numerical integration of the matrix elements and how do they affect the condition number. My Idea was to write $\tilde A = A + E$ where the elements of $E$ illustrate the error between the numerical integration and the exact integration. Is there any way to give a inequality relation between $cond_2(\tilde{A})$ and $cond_2(A)$?

  2. My second question is about the limit inside the condition number. Assuming a matrix $E$ with elements $e_{i,j} = \int\limits_{\tilde{\Omega}\subset \mathbb{R}^d} \nabla \tilde{\varphi}_i\cdot \nabla\tilde{\varphi}_j \,d\Omega$ with $\tilde{\Omega}\cap\Omega = \emptyset$. How does the condition number reacts to limit of matrices i.e. does it hold that $cond_2(A + \lim_{\alpha\to 0} \alpha E) = cond_2(A)$ or is there any inequality relation between these two? I first tried to use $$ cond_2(A + \lim_{\alpha\to 0} \alpha E) \leq cond_2(A) + cond_2(\lim_{\alpha\to 0} \alpha E)$$ but I realized that the condition number of zero Matrix is defined as $\infty$. And therefore the inequality is useless.

$\endgroup$
2
$\begingroup$

1. For a matrix $A$ with distinct eigenvalues, adding a perturbation $\delta A$ results [1] in a change to eigenvalues of magnitude (to first order) $$ \delta\lambda_i = (X^{-1}\delta A X)_{ii}, $$ so $|\delta \lambda_i| \leq \kappa(X)\|\delta A\|$. The change in condition number $\kappa(A)$ is then given by $$ \delta(\kappa(A)) = \kappa(A)\big(\delta(\log \lambda_n) - \delta(\log \lambda_1)\big) \leq \kappa(A)\|\delta A\|\big(|\lambda_n|^{-1} + |\lambda_1|^{-1}\big),$$ where $\lambda_1,\lambda_n$ are the smallest and largest eigenvalues by absolute value. Since this is proportional to $\|\delta A\|$, the only issue you can get is if your matrix is almost singular and the perturbation turns it singular, then $\delta(\kappa(A))$ would be large.

2. It isn't true that $\kappa(A+B)\leq \kappa(A) + \kappa(B)$. Consider $A=\mathrm{diag}(1,1+\epsilon)$ and $B=\mathrm{diag}(1,-1)$, then both are well-conditioned, $\kappa(A)=1+\epsilon$, $\kappa(B)=1$, but $\kappa(A+B)=\epsilon^{-1}$.

  • [1] An extended collection of matrix derivative results for forward and reverse mode automatic differentiation, M. Giles, (pdf)
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ For 1: Is there also an upper bound for $\delta cond_2(A)$? For 2: I understand your counter example. But it should be true that: $cond_2(A +\lim_{\alpha \ to 0} E) = cond_2(A)$ $\endgroup$ – user29088 Dec 15 '18 at 16:02
  • 1
    $\begingroup$ @Kerem (1) You might be able to get a rigorous bound instead of the first-order expansion by looking more carefully at the perturbation theory of eigenvalues. (2) Of course it is true that $\lim_{\epsilon\to0}\kappa(A+\epsilon E) = \kappa(A)$ (the way you placed the limits in that expression doesn't make sense btw), because $\kappa(A)$ is a continuous function of the entries of $A$. $\endgroup$ – Kirill Dec 15 '18 at 20:23
  • $\begingroup$ could you tell me where to find the proof of your inequality in (1) @Kirill $\endgroup$ – user29088 Dec 17 '18 at 18:35

Your Answer

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