3
$\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$
4
  • 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$ Dec 9, 2017 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, 2017 at 21:43
  • $\begingroup$ Can you reference the book you're mentioning? $\endgroup$
    – nicoguaro
    Dec 10, 2017 at 1:35
  • $\begingroup$ @nicoguaro Oh yes, I am referring to chapter 2 of the 'A multigrid tutorial‘ book. $\endgroup$
    – user123
    Dec 10, 2017 at 2:44

1 Answer 1

5
$\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$
2
  • $\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, 2017 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, 2017 at 3:22

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.