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$
3
$\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)
$\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$ – Kerem 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$ – Kerem 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

Not the answer you're looking for? Browse other questions tagged or ask your own question.