I.3.6.1: LU-form

In block relaxation methods, including generalized block methods, we update $x=(x_1,\cdots,x_n)$ to $y=(y_1,\cdots,y_n)$ by the rule $$y_s=F_s(y_1,\cdots,y_{s-1},x_s,x_{s+1},\cdots,x_n).$$ Differentiation gives $$\mathcal{D}_ty_s= \sum_{u<s}(\mathcal{D}_uF_s)(\mathcal{D}_ty_u)+ \begin{cases}0&\text{ if }t<s,\\ \mathcal{D}_tF_s&\text{ if }t\geq s. \end{cases}.\tag{1}$$ It should be emphasized that in many cases of interest in $F_s$ does not depend on $x_s,$ so that $\mathcal{D}_sF_s=0$ for all $s$. It is also important to realize that the derivatives, which we write without arguments in this section, are generally evaluated at points of the form $(y_1,\cdots,y_{s-1},x_s,\cdots,x_p)$. At fixed points, however, $x_s=y_s$ for all $s$, and we can just write $\mathcal{D}_ty_s$ without ambiguity. And for our purposes the derivatives at fixed points are the interesting ones.

Now define $$\mathcal{M}\mathop{=}\limits^{\Delta} \begin{bmatrix} \mathcal{D}_1y_1&\mathcal{D}_2y_1&\cdots&\mathcal{D}_ny_1\\ \mathcal{D}_1y_2&\mathcal{D}_2y_2&\cdots&\mathcal{D}_ny_2\\ \vdots&\vdots&\ddots&\vdots\\ \mathcal{D}_1y_n&\mathcal{D}_2y_n&\cdots&\mathcal{D}_ny_n\\ \end{bmatrix},$$ and $$\mathcal{N}\mathop{=}\limits^{\Delta} \begin{bmatrix} \mathcal{D}_1F_1&\mathcal{D}_2F_1&\cdots&\mathcal{D}_nF_1\\ \mathcal{D}_1F_2&\mathcal{D}_2F_2&\cdots&\mathcal{D}_nF_2\\ \vdots&\vdots&\ddots&\vdots\\ \mathcal{D}_1F_n&\mathcal{D}_2F_n&\cdots&\mathcal{D}_nF_n\\ \end{bmatrix}.$$ Also $$\mathcal{N}_L\mathop{=}\limits^{\Delta} \begin{bmatrix} 0&0&\cdots&0\\ \mathcal{D}_1F_2&0&\cdots&0\\ \vdots&\vdots&\ddots&\vdots\\ \mathcal{D}_1F_n&\mathcal{D}_2F_n&\cdots&0\\ \end{bmatrix},$$ and $$\mathcal{N}_U\mathop{=}\limits^{\Delta} \begin{bmatrix} \mathcal{D}_1F_1&\mathcal{D}_2F_1&\cdots&\mathcal{D}_nF_1\\ 0&\mathcal{D}_2F_2&\cdots&\mathcal{D}_nF_2\\ \vdots&\vdots&\ddots&\vdots\\ 0&0&\cdots&\mathcal{D}_nF_n\\ \end{bmatrix},$$ so that $\mathcal{N}=\mathcal{N}_U+\mathcal{N}_L$. From $(1)$ $$\mathcal{M}=\mathcal{N}_L\mathcal{M}+\mathcal{N}_U,$$ or $$\mathcal{M}=(I-\mathcal{N}_L)^{-1}\mathcal{N}_U.$$ This is the Lower-Upper or LU form of the derivative of the algorithmic map.

For two blocks $\mathcal{M}$ is equal to $$\begin{bmatrix} \mathcal{D}_1F_1&\mathcal{D}_2F_1\\ (\mathcal{D}_1F_2)(\mathcal{D}_1F_1)&(\mathcal{D}_1F_2)(\mathcal{D}_2F_1)+\mathcal{D}_2F_2 \end{bmatrix},$$ and if $\mathcal{D}_1F_1=0$ and $\mathcal{D}_2F_2=0$ this is $$\begin{bmatrix} 0&\mathcal{D}_2F_1\\ 0&(\mathcal{D}_1F_2)(\mathcal{D}_2F_1) \end{bmatrix}.$$ Thus the non-zero eigenvalues are the eigenvalues of $(\mathcal{D}_1F_2)(\mathcal{D}_2F_1)$.