# What does $A = L + D + U$ look like?

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!

• You are correct. $L$, $D$ and $U$ are exactly the matrices you wrote and their sum is $A$. – michaelhowes Nov 9 '17 at 11:48
• 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. – P. Siehr Nov 9 '17 at 12:22
• @P.Siehr Thanks! Just one quick question about the gauss-seidel iterations: do you have to calculate $L,D,U$ etc, after each iteration? – titusAdam Nov 9 '17 at 15:20
• 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$. – P. Siehr Nov 9 '17 at 15:56
• @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? – titusAdam Nov 14 '17 at 12:20

## 1 Answer

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).