1
$\begingroup$

Exercise:

Consider the problem \begin{split} 10u_1 + u_2 &= 1\\ u_1 + 10u_2 &= 10 \end{split} with the solution $(u_1,u_2)^T = (0,1)^T$. For a general system of equations $$Au = b$$ with an $n\times n$ matrix $A$, which consists of a lower triangular submatrix $L$, the diagonal $D$ and the uppertriangular submatrix $U\,(A=L+D+U)$, a Gauss–Seidel iteration is defined by $$u^{i+1} = D^{-1}(b - Lu^{i+1} - Uu^i)$$ and a Jacobi iteration is defined by $$u^{i+1} = D^{-1}(b - Lu^i - Uu^i)$$

Perform:

a) Four Gauss-Seidel iterations.

b) Four Jacobi iterations.

Question:

  • What does $A = L + D + U$ mean? I suppose that I doesn't mean that $a_{ij} = l_{ij} + d_{ij} + u_{ij}$? If that is what it's supposed to mean, do we get $$L = \begin{bmatrix}0 & 0\\ 1 &0 \end{bmatrix}, \,D = \begin{bmatrix}10 & 0\\ 0&10\end{bmatrix},\,U = \begin{bmatrix} 0&1\\ 0&0\end{bmatrix} $$

Thanks in advance!

$\endgroup$
  • $\begingroup$ You are correct. $L$, $D$ and $U$ are exactly the matrices you wrote and their sum is $A$. $\endgroup$ – michaelhowes Nov 9 '17 at 11:48
  • $\begingroup$ Indeed you are absolutely correct. It is nice to see a well formatted question, including your own ideas. If you are interested in a more general approach to Gauß-Seidel and Jacobi-Iteration, have a look at Saad's book. Both methods can be seen in the more general framework of additive splitting. This MSE-Question has also great answers. $\endgroup$ – P. Siehr Nov 9 '17 at 12:22
  • $\begingroup$ @P.Siehr Thanks! Just one quick question about the gauss-seidel iterations: do you have to calculate $L,D,U$ etc, after each iteration? $\endgroup$ – titusAdam Nov 9 '17 at 15:20
  • $\begingroup$ No, since both iterations don't change $A$. And you don't "calculate" them at all, as they are already given. Don't confuse them with a multiplicative decomposition, such as $LU$ or $QR$. $\endgroup$ – P. Siehr Nov 9 '17 at 15:56
  • $\begingroup$ @P.Siehr I'm a bit confused trying to actually perform 4 Jacobi iterations! $u^i$ doesn't change. After each iteration I have $u^i = (0,1)$, is this correct? $\endgroup$ – titusAdam Nov 14 '17 at 12:20
1
$\begingroup$

Your $L$, $D$, and $U$ are correct. Note that $a_{ij} = l_{ij} + d_{ij} + u_{ij}$ is true, however, two of the three terms are always zero; the upper right entry would be $a_{ij} = 0 + 0 + 1$.

In general, $\color{red}A = \color{blue}L + \color{orange}D + \color{green}U$ looks like $$ \color{red}{\begin{pmatrix} a_{1,1} & a_{1,2} & \ldots & a_{1,n-1} & a_{1,n} \\ a_{2,1} & a_{2,2} & \ldots & a_{2,n-1} & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{n-1,1} & a_{n-1,2} & \ldots & a_{n-1,n-1} & a_{n-1,n} \\ a_{n,1} & a_{n,2} & \ldots & a_{n,n-1} & a_{n,n} \end{pmatrix}} =\\ \color{blue}{\begin{pmatrix} 0 & 0 & \ldots & 0 & 0 \\ a_{2,1} & 0 & \ldots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{n-1,1} & a_{n-1,2} & \ldots & 0 & 0 \\ a_{n,1} & a_{n,2} & \ldots & a_{n,n-1} & 0 \end{pmatrix}} +\\ \color{orange}{\begin{pmatrix} a_{1,1} & 0 & \ldots & 0 & 0 \\ 0 & a_{2,2} & \ldots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \ldots & a_{n-1,n-1} & 0 \\ 0 & 0 & \ldots & 0 & a_{n,n} \end{pmatrix}} +\\ \color{green}{\begin{pmatrix} 0 & a_{1,2} & \ldots & a_{1,n-1} & a_{1,n} \\ 0 & 0 & \ldots & a_{2,n-1} & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \ldots & 0 & a_{n-1,n} \\ 0 & 0 & \ldots & 0 & 0 \end{pmatrix}} $$

Note that in this case $L$ and $U$ are strictly triangular matrices. A triangular matrix may have non-zero entries in its diagonal, e.g.: $\begin{pmatrix}1&1\\0&1\end{pmatrix}$ is an upper triangular matrix (but not a strictly upper triangular matrix).

$\endgroup$

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.