2
$\begingroup$

As stated in the title, it's said in the book that Gauss-Seidel iterative method is equivalent to successively setting each component of residual vector to zero. After rearranging G-S scheme, I got the following relation regarding the update of residual:

$$ r^{(k+1)} = U(D-L)^{-1}r^{(k)}, $$

but I still can't see why this conclusion holds. Any help?

$\endgroup$
  • 1
    $\begingroup$ If $D,L,U$ mean what I think they mean, it should be $(D-L)^{-1}U$, not $U(D-L)^{-1}$. $\endgroup$ – Federico Poloni Dec 9 '17 at 20:41
  • $\begingroup$ Oh yes, for Ax=b, D, L and U are respectively the diagonal, lower triangular and upper triangular of A! $\endgroup$ – user123 Dec 9 '17 at 21:43
  • $\begingroup$ Can you reference the book you're mentioning? $\endgroup$ – nicoguaro Dec 10 '17 at 1:35
  • $\begingroup$ @nicoguaro Oh yes, I am referring to chapter 2 of the 'A multigrid tutorial‘ book. $\endgroup$ – user123 Dec 10 '17 at 2:44
4
$\begingroup$

Given approximated solution $\mathbf x^{(k)}$, we define the residual vector $\mathbf r^{(k)} := \mathbf b - \mathbf A\,\mathbf x^{(k)} $. Now we want to update $x^{(k)}_i \rightarrow x^{(k+1)}_i$ in such a way so that the $i$th component of the new residual vanishes: $$ r^{(k+1)}_i = b_i - \sum_{j=1}^n a_{ij}\,x^{(k+1)}_j = 0, \\ b_i - \left(\sum_{j=1}^{i-1} a_{ij}\,x^{(k+1)}_j + a_{ii}\,x^{(k+1)}_i + \sum_{j=i+1}^n a_{ij}\,x^{(k+1)}_j\right) = 0, \\ x^{(k+1)}_i = \frac{1}{a_{ii}} \left(b_i - \sum_{j=1}^{i-1} a_{ij}\,x^{(k+1)}_j - \sum_{j=i+1}^n a_{ij}\,x^{(k+1)}_j\right). $$ Assuming that all the other components stay the same, we may rewrite this formula as $$ x^{(k+1)}_i = \frac{1}{a_{ii}} \left(b_i - \sum_{j=1}^{i-1} a_{ij}\,x^{(k)}_j - \sum_{j=i+1}^n a_{ij}\,x^{(k)}_j\right). $$ Now, if we introduce matrix notation $\mathbf A = \mathbf L + \mathbf D + \mathbf U$ with strictly lower, diagonal, and strictly upper parts of the original matrix, we may rewrite the last equation as $$ \mathbf L\,\mathbf x^{(k)} + \mathbf D\,\mathbf x^{(k+1)} + \mathbf U\,\mathbf x^{(k)} = \mathbf b, \\ \mathbf x^{(k+1)} = -\mathbf D^{-1}\left(\mathbf L + \mathbf U\right)\mathbf x^{(k)} + \mathbf D^{-1}\,\mathbf b; $$ this is well-known Jacobi method.

Note that at the $i$th step we have already updated components $1, 2, \dots, i-1$, so let’s use these updated values: $$ x^{(k+1)}_i = \frac{1}{a_{ii}} \left(b_i - \sum_{j=1}^{i-1} a_{ij}\,x^{(k+1)}_j - \sum_{j=i+1}^n a_{ij}\,x^{(k)}_j\right), $$ or $$ \mathbf L\,\mathbf x^{(k+1)} + \mathbf D\,\mathbf x^{(k+1)} + \mathbf U\,\mathbf x^{(k)} = \mathbf b, \\ \mathbf x^{(k+1)} = -(\mathbf D + \mathbf L)^{-1}\,\mathbf U\,\mathbf x^{(k)} + (\mathbf D + \mathbf L)^{-1}\,\mathbf b. $$ This is Gauss–Seidel method.

$\endgroup$
  • $\begingroup$ Thank you for your answer, but I don't think it's right. According to your argument, the Jacobi method would also set the i-th component of residual to zero, but it's not! $\endgroup$ – user123 Dec 10 '17 at 3:07
  • 2
    $\begingroup$ This is true. Jacobi annihilates $i$th component of the residual assuming all the other components of the soln vector stay unchanged; Gauss–Seidel does the same but uses $(k+1)$th step (already updated) components of the soln vector. $\endgroup$ – 56th Dec 10 '17 at 3:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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