| |
 |
|
|
Science Forum Index » Math - Numerical Analysis Forum » symmetric perturbation
Page 1 of 1
|
| Author |
Message |
| Guest |
 Posted: Tue Mar 13, 2007 8:22 pm |
|
|
|
|
Hello,
I am looking for the solution of a system Ax = b with a nonsingular
matrix A. My (e.g. iterative) algorithm does not compute the exact
solution, hence I solve (exactly) the system Ax = b - r, where r is
the residual. It is well known that if I set E=rx^T/||x||^2, I can
write (A+E)x = b. That is I can interpret the inexact solution of Ax =
b as the exact solution of the system with a perturbed matrix A+E
where E is of rank one. It appears that such E is minimal in 2-norm
over all perturbations F such that Fx=r. Since I solve a symmetric
positive definite problem it seems reasonable to look for an optimal
*symmetric* perturbation matrix E so the perturbed problem is still
positive definite (if E is small enough). Does anybody know if there
is an explicit way how to construct such a perturbation (if it exists)
and/or can give me a reference to some book or paper dealing with this
problem?
Thank you.
P.J. |
|
|
| Back to top |
|
| Dave Dodson |
| Posted: Tue Mar 13, 2007 11:41 pm |
|
|
|
Guest
|
On Mar 13, 8:22 pm, pavel.jira...@gmail.com wrote:
Quote: Does anybody know if there
is an explicit way how to construct such a perturbation (if it exists)
and/or can give me a reference to some book or paper dealing with this
problem?
Why not just set E = e e^T and solve for e?
When I did it, I got e = r/sqrt(r^T x) if r^T x != 0.
Dave |
|
|
| Back to top |
|
| Guest |
| Posted: Wed Mar 14, 2007 6:05 pm |
|
|
|
|
On Mar 14, 5:41 am, "Dave Dodson" <dave_and_da...@Juno.com> wrote:
Quote: On Mar 13, 8:22 pm, pavel.jira...@gmail.com wrote:
Does anybody know if there
is an explicit way how to construct such a perturbation (if it exists)
and/or can give me a reference to some book or paper dealing with this
problem?
Why not just set E = e e^T and solve for e?
When I did it, I got e = r/sqrt(r^T x) if r^T x != 0.
Dave
Well I must confess that I have not realized this simple solution. But
unfortunately it is not as useful as simple. If I understand your
proposal is to take E = r * r^T / (r^T * x) but there is a condition
that r is not orthogonal to x. I do not know at the moment how
restrictive this condition (i.e. when it is guaranteed that r and x
are almost colinear). The only thing I know is that ||E|| is at least
(unfortunately not at most) equal to ||r||. My simple example shows
that this is not a right way to go:
I have said to the MATLAB:
A = gallery('poisson',10);
b = A * ones(100,1);
x = pcg(A, b, 1e-3, 20);
The PCG method arives with the relative residual norm about 1.8e-4
which leads to the perturbation matrix (the optimal one) F = r * x^T /
||x||^2 with ||F|| = 3.3e-5. Since ||F||/||A|| = 4.2e-6 < 0.02 = 1 /
cond(A), the perturbed system matrix A + F is quite far from the
nearest singular matrix. But if I take E = r * r^T / (r^T * x), I have
||E||/||A|| = 6.7e+7, which is surely quite large  .
Pavel
PS: Note that r^T x = 0 iff x^T b = x^T A x, but since A x is "almost"
b it follows that r^T x is almost zero. |
|
|
| Back to top |
|
| |
|
Page 1 of 1
All times are GMT - 5 Hours
The time now is Fri Nov 21, 2008 5:56 pm
|
|