MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


I'm trying to answer this question, but am completely stuck.

Argue that in analyzing the error in a stationery linear relaxation scheme applied to $Au=f$, it is sufficient to consider $Au=0$ with arbitrary initial guess, (say $v_0$).

Any ideas?

I'm not even sure what the author is trying to say, is he saying when studying the error produced by the relaxation method (eg. the jacobi method) it is sufficient to study the error of the associated homogenous system $Au=0$ with arbitrary initial guesses (say $v_0$). But in this case the error will simply be $e = -v_0$. (since the error is defined as $e=u-v_0$)

Maybe the residual equation plays a part, $Ae=r$ ... ???

Any help, would be much appreciated.

Incidently stationary linear relaxation schemes (eg. gauss seidel and jacobi) have the form

$v^{(k+1)}=(v^{k}+Br^{(0)})$. Not sure if this is usefull. here $r=f-Av$ is the residual vector, and $v^{(k)}$ is the kth iterate of the scheme

share|cite|improve this question
What author? What book or article? – Will Jagy Sep 21 '10 at 2:25
A Multigrid Tutorial by William L. Briggs 2nd ed. chapter 2 question 6. – mark Sep 21 '10 at 3:41
up vote 2 down vote accepted

Relaxation method is a part of the theory of iterative methods for the calculation of approximate solutions to linear systems. It depends on a real or complex parameter $\omega$, the relaxation parameter. I must point out that Jacobi method is not a relaxation method, whereas Gauss-Seidel is one, corresponding to $\omega=1$. A necessary condition for the convergence is $|\omega-1|<1$. The choice $\omega\in(1,2)$ is called over-relaxation.

It is true that in the error analysis, one only needs to consider the case $f=0$. Because of linearity, it is the same to solve $Au=f$, starting from $u_0$, or to solve $Av=0$ (obvious solution) starting from $v_0=u_0-A^{-1}f$. This is why the convergence theory treats only the homogeneous case.

It is not correct to write the iteration in the form $v^{k+1}=v^k+Br^{(0)}$. Such a formula would prevent convergence (obvious). Instead, the iteration writes $v^{k+1}=L_\omega v^k+Bf$. The convergence occurs precisely when the spectral radius of $L_\omega$ is less than $1$. The theory emphasises on the search of the optimal parameter $\omega^*$, for which this spectral radius is minimal, that is, the convergence is the fastest.

For details, see for instance my book Matrices; Theory and Applications, GTM 216. Springer-Verlag (2002).

share|cite|improve this answer
Thank you for your input, although you have raised as many questions as you have answered... For example on p8 the author of the mentioned book above refers to the Jacobi method as a relaxation method. Also when iteration is in the form I quoted (this is formula 2.2 in the same book), the author states the iteration should be effective provided B is chosen "close" to the inverse of A. I think by close he means in some spectral sense. I guess i'll have to consult a more rigourous book such as yours to clear things up. Thanks for the calrification on the error analysis matter. – mark Sep 22 '10 at 16:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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