3
$\begingroup$

Consider some randomly generated matrix $B\in\mathbb{R}^{100\times100}$ and let $A:=BB^{\top}$

On MATLAB I computed the condition number of $A$, I obtained a value of $2.8377\mathrm{e}+04$

However if I apply the following modification to $A$ $$ A:=A+(\lambda_{min}(A)+10)I_{100}\tag{1} $$ Thus overall we have a symmetric positive-definite (SPD) matrix $A$.

When I run this on MATLAB, the condition number of $A$ is now reduced to $42.173$.

I know for once that originally when $A:=BB^{\top}$, the condion number of $A$ is the square of the condition number of $B$ and since $B$ is randomly generated, then its condition number should be ill and by squaring it, the condition number would further elevate. When applying this precondition technique in $(1)$, I have failed to establish an upper bound to the condition number of $A$ and thus:

Question: I can not seem to understand how this preconditioning technique had effectively reduced the condition number of $A$.

I would be grateful for any comments and/or answers!

$\endgroup$

2 Answers 2

19
$\begingroup$

If the eigenvalues of $A$ are $\lambda_1, \lambda_2, \dots,\lambda_n$, the eigenvalues of $A + \mu I$ are $\lambda_1 + \mu, \lambda_2 + \mu, \dots, \lambda_n + \mu$. It is an easy computation to verify that $$ \frac{\lambda_1 + \mu}{\lambda_n + \mu} < \frac{\lambda_1}{\lambda_n}, $$ when $\lambda_1 > \lambda_n>0$ and $\mu > 0$. In fact the LHS is a decreasing function of $\mu$.

Let me note, though, that this is not a preconditioning technique. It's just solving a different problem.

$\endgroup$
12
$\begingroup$

The accepted answer is right: you are not making a preconditioner.

To elaborate.

For a matrix $A$, a preconditioner is a matrix $B$ such that $B^{-1}A$ has a smaller condition number than $A$. The logic being that the preconditioned system $B^{-1}Ax=B^{-1}y$ is then easier to solve than $Ax=y$.

You're not doing this: you are finding a matrix $A'$ with a smaller condition number. That doesn't help you in solving a linear system with $A$.

$\endgroup$
2
  • $\begingroup$ To hammer it home even more drastically: consider $A' := 0\,A + \mathrm{id}$. This way we produce a matrix with the excellent condition number 1! But what use this is for solving purposes is another matter... $\endgroup$ Aug 4, 2022 at 15:14
  • 1
    $\begingroup$ @leftaroundabout that matrix $\mathbf{A}'$ actually can help solve a system $\mathbf{A}\mathbf{x}=\mathbf{b}$. All we need to do is multiply $\mathbf{x}$ by it ;) $\endgroup$ Aug 4, 2022 at 23:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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