2
$\begingroup$

For Poisson equation with Dirichlet boundary conditions in 2 dimension: $$ -\Delta u=f, $$ using FDM (centered difference) or FEM discretization, we can obtain a SPD system of linear equations as follows: $$ Ax=b. $$ And if the step size is $h$, then the spectral condition number of matrix $A$ is $O(h^{-2})$.

A conclusion goes that "Given a positive constant $\alpha>0$, then matrix $\alpha I+A$ is well-conditioned". Why the addition of a positive term $\alpha$ to the main diagonal of matrix $A$ can improve the condition number of matrix $A$?

Because in my opinion, the new matrix condition number is

$$ \mathrm{cond}_2(\alpha I+A) = \frac{\alpha+\lambda_{\max}(A)}{\alpha+\lambda_{\min}(A)}>\frac{\lambda_{\max}(A)}{\lambda_{\min}(A)}=\mathrm{cond}_2(A). $$

But the numerical results contrast as follows:

clc;clear;
n=10;
A=gallery('poisson',n);
cond(full(A))

n=10;
A=gallery('poisson',n);
cond(full(A)+speye(n^2))

n=20;
A=gallery('poisson',n);
cond(full(A)+speye(n^2))

The numerical results as follows:


ans =

   48.3742


ans =

    7.6056


ans =

    8.5723

As is seen, the condition number of $I+A$ is less than $A$ (48.3742 > 7.6056).

Furthermore, when the system size increases, the condition number almost do not increase (from 7.6056 to 8.5723), which seems that the condition number of matrix $\alpha I+A$ is independent on $h$. Why this happens? Does it really independent on step size $h$?

$\endgroup$
  • $\begingroup$ You don't need to thank in your questions. $\endgroup$ – nicoguaro Nov 21 '19 at 14:04
6
$\begingroup$

The inequality $\frac{\alpha + \lambda_{max}(A)}{\alpha+\lambda_{min}(A)} > \frac{\lambda_{max}(A)}{\lambda_{min}(A)}$ doesn't hold because $\lambda_{max}(A) > 1 > \lambda_{min}(A) > 0$ and $\alpha > 0$. In fact, the reverse inequality holds in this case. Hence, there is no contradiction here.

EDIT: From the comments, I realized that the question is not answered completely yet.

Also, $\kappa(A+\alpha I) = \frac{\alpha + \lambda_{max}(A)}{\alpha+\lambda_{min}(A)} = \frac{\frac{\alpha}{\lambda_{max}(A)}+1}{\frac{\alpha}{\lambda_{max}(A)}+\frac{\lambda_{min}(A)}{\lambda_{max}(A)}} = \frac{\frac{\alpha}{\lambda_{max}(A)}+1}{\frac{\alpha}{\lambda_{max}(A)}+O(h^2)}$.

Hence, for small enough $h$ and big enough $\alpha$, we have $\kappa(A) \approx 1+\frac{\lambda_{max}(A)}{\alpha}$. One can see that $\lambda_{max}(A)$ changes very little. For example,

poisson = @(n) full(gallery('poisson',n,n));
max(abs(eig(poisson(10))))

ans =

7.837971894457977

max(abs(eig(poisson(40))))

ans =

7.988263204734964

max(abs(eig(poisson(60))))

ans =

7.994696359539318

$\endgroup$
  • $\begingroup$ Thanks for your reply. By the way, Is the condition number of $\alpha I+A$ independent on step size $h$? Why? Because in my numerical examples, when the system size increases, the condition number does not increase much. $\endgroup$ – sunshine Nov 22 '19 at 0:17
  • $\begingroup$ MATLAB's gallery() with the 'poisson' arguement returns a matrix with the stencil values (-1,4,-1) and is independent of the number of discretization points or the grid spacing h. Even if you scale this matrix by multiplying by $1/(h^2)$, both the maximum and minimum eigenvalues get scaled equally and hence, there is no change in the condition number. $\endgroup$ – Aryabhata Bharadwaj Nov 22 '19 at 10:02
  • 1
    $\begingroup$ But, the condition number of matrix $A$ is $O(h^{-2})$, why the condition number of $\alpha I+A$ is independent on mesh size? I cannot understand it, can you give me some more details or some proof? Thanks. $\endgroup$ – sunshine Nov 22 '19 at 11:49
  • 1
    $\begingroup$ You are right about the condition number depending on $h$. Check the answer again. I added a "proof". $\endgroup$ – Aryabhata Bharadwaj Nov 22 '19 at 16:46

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.