8
$\begingroup$

In my courses on numerical analysis, I have been taught that the main and principal motivation for preconditioning linear systems of equations is to increase the convergence rate of iterative solvers for that LSE.

But, is there any effect on the precision of the computed solution?

I can remember a result on the precision of computed solution of Gaussian elimination, which can be found in Matrix Computations by Golub and Van Loan (p. 122). The condition number (with respect to some particular norm) does indeed affect the precision of the numerical solution computed by that algorithm.

One might expect that something similar holds for solutions obtained by, e.g., Conjugate Gradients. I think that I have observed this in a computational experiment. When I had the Conjugate gradient method run on an unpreconditioned system for a (long) time until some stopping criterion was met, the computed solution still displayed a high residual. So I wonder whether lower condition numbers not only lead to lower run-times, but also to a lower residual (or error) in the computed solution. Note that this is necessarily a question of numerical stability, which requires that we work in inprecise arithmetics.

(I have asked the same question on math.SE, but I think that this site might be more appropriate.)

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ In fact Golub and Van Loan do give a short note n the effect of your matrix's $\kappa$ on the convergence rate; see this. Geometrically, you can think of it as the iteration struggling to proceed on a very narrow hyperellipsoid. $\endgroup$
    – J. M.
    May 14, 2013 at 17:18
  • $\begingroup$ You missed the point of my question, which might be due to left out word by me. I corrected it, please reread the question again now. - Note, that I do not ask for the convergence rate, but for the 'quality' of the solution, however one may define this. $\endgroup$
    – shuhalo
    May 14, 2013 at 19:31

1 Answer 1

Reset to default
5
$\begingroup$

The accuracy of Gaussian elimination is not bounded in terms of condition number. There is an example of a well-conditioned matrix in Trefethen and Bau (and probably elsewhere) for which Gaussian Elimination is exponentially unstable with respect to matrix size.

Now for iterative methods: CG finds the best approximation over the subspace in the energy norm of the preconditioned operator. If the preconditioner is effective, then you can usually evaluate this norm more accurately. This is not guaranteed: the preconditioner is also ill-conditioned and in general, we can only evaluate $ A B x$ with accuracy proportional to $\kappa(A) \kappa(B)$, not $\kappa(A B)$.

Anyway, preconditioning does two things:

  1. It makes the solution well-represented in a small number of vectors that appear early in the iteration.
  2. It makes the norm in which we evaluate optimality over a subspace closer to the norm of the error than the norm of the residual.

It is up to you whether you want the error to be small or the residual to be small.

Improve this answer
$\endgroup$

Your Answer

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

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