Relaxation Scheme for $Au=f$ error analysis - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T00:11:10Z http://mathoverflow.net/feeds/question/39454 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/39454/relaxation-scheme-for-auf-error-analysis Relaxation Scheme for $Au=f$ error analysis aukm 2010-09-21T01:02:51Z 2010-09-21T05:22:52Z <p>Hello </p> <p>I'm trying to answer this question, but am completely stuck. </p> <p>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$).</p> <p>Any ideas?</p> <p>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$)</p> <p>Maybe the residual equation plays a part, $Ae=r$ ... ???</p> <p>Any help, would be much appreciated.</p> <p>Incidently stationary linear relaxation schemes (eg. gauss seidel and jacobi) have the form</p> <p>$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 </p> http://mathoverflow.net/questions/39454/relaxation-scheme-for-auf-error-analysis/39468#39468 Answer by Denis Serre for Relaxation Scheme for $Au=f$ error analysis Denis Serre 2010-09-21T05:22:52Z 2010-09-21T05:22:52Z <p>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 <em>relaxation parameter</em>. 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|&lt;1$. The choice $\omega\in(1,2)$ is called <em>over-relaxation</em>.</p> <p>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. </p> <p>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.</p> <p>For details, see for instance my book <em>Matrices; Theory and Applications</em>, GTM <strong>216</strong>. Springer-Verlag (2002).</p>