# Why $\alpha I +A$ can improve the condition nubmer of a SPD matrix $A$?

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$$?

• You don't need to thank in your questions. Nov 21 '19 at 14:04

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

• 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. Nov 22 '19 at 0:17
• 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. Nov 22 '19 at 10:02
• 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. Nov 22 '19 at 11:49
• You are right about the condition number depending on $h$. Check the answer again. I added a "proof". Nov 22 '19 at 16:46