# The Convergence of block and Gauss-Seidel method

by gaazkam   Last Updated November 18, 2018 19:20 PM

To solve a system of equations with a nonsingular block matrix: $$\begin{bmatrix}A&B\\B^{\operatorname{T}}&-\mathrm{I}\end{bmatrix}\begin{bmatrix}x\\y\end{bmatrix}=\begin{bmatrix}f\\g\end{bmatrix}$$ where $$A,B\in\mathbb{R}^{N\times N}$$ and $$A=A^{\operatorname{T}}>0$$ we use the following block Gauss-Seidel method: $$Ax_{n+1}+By_n=f,\\B^{\operatorname{T}}x_{n+1}-y_{n+1}=g$$ Prove that if $$\left|\left|B^{\operatorname{T}}x_{n+1}-y_{n+1}\right|\right|_2<1$$, then the iteration converges to the solution of the system of equations for any initial $$x_0,y_0$$.

# Solution attempt:

In the general case: An iterative method $$M\mathcal{X}_{n+1}=\mathcal{B}+Z\mathcal{X}_n$$, solving a system of equations $$\mathcal{A}\mathcal{X}=\mathcal{B}$$, where $$\mathcal{A}=M-Z$$, converges for any $$\mathcal{X_0}$$ if $$\left|\left|\mathfrak{B}\right|\right|<1$$, for $$\mathfrak{B}:=\mathrm{I}-M^{-1}\mathcal{A}$$.

Here we have $$\mathcal{A}=\begin{bmatrix}A&B\\B^{\operatorname{T}}&-\mathrm{I}\end{bmatrix},\mathcal{X}=\begin{bmatrix}x\\y\end{bmatrix},\mathcal{B}=\begin{bmatrix}f\\g\end{bmatrix}$$. Sorry for using fonts to distinguish tokens, but as you can see we have crazy conflicts here! Firstly let's try to find $$M$$:

$$\begin{cases}Ax_{n+1}+By_n=f\\B^{\operatorname{T}}x_{n+1}-y_{n+1}=g\end{cases}\iff\begin{cases}Ax_{n+1}=f-By_n\\B^{\operatorname{T}}x_{n+1}-y_{n+1}=g\end{cases}$$ In matrix form: $$\begin{bmatrix}A&0\\B^{\operatorname{T}}&-\mathrm{I}\end{bmatrix}\begin{bmatrix}x_{n+1}\\y_{n+1}\end{bmatrix}=\begin{bmatrix}f\\g\end{bmatrix}+\begin{bmatrix}0&-B\\0&0\end{bmatrix}\begin{bmatrix}x_n\\y_n\end{bmatrix}$$

Since clearly $$\begin{bmatrix}A&0\\B^{\operatorname{T}}&-\mathrm{I}\end{bmatrix}-\begin{bmatrix}0&-B\\0&0\end{bmatrix}=\begin{bmatrix}A&B\\B^{\operatorname{T}}&-\mathrm{I}\end{bmatrix}=A$$,

we can conclude that $$\begin{cases}M=\begin{bmatrix}A&0\\B^{\operatorname{T}}&-\mathrm{I}\end{bmatrix}\\Z=\begin{bmatrix}0&-B\\0&0\end{bmatrix}\end{cases}$$.

Now let's try to find $$M^{-1}$$. We have $$M^{-1}M=\operatorname{I}$$, so: $$\begin{bmatrix}M^{-1}_{1,1}&M^{-1}_{1,2}\\M^{-1}_{2,1}&M^{-1}_{2,2}\end{bmatrix}\begin{bmatrix}A&0\\B^{\operatorname{T}}&-\mathrm{I}\end{bmatrix}=\begin{bmatrix}\mathrm{I}&0\\0&\mathrm{I}\end{bmatrix}$$

Filling in the blanks we easily get: $$\begin{bmatrix}A^{-1}&0\\B^{\operatorname{T}}A^{-1}&-\mathrm{I}\end{bmatrix}\begin{bmatrix}A&0\\B^{\operatorname{T}}&-\mathrm{I}\end{bmatrix}=\begin{bmatrix}\mathrm{I}&0\\0&\mathrm{I}\end{bmatrix}$$ So $$M^{-1}=\begin{bmatrix}A^{-1}&0\\B^{\operatorname{T}}A^{-1}&-\mathrm{I}\end{bmatrix}$$.

Now let's compute $$\mathfrak{B}$$:

$$\mathfrak{B}=\mathrm{I}-M^{-1}\mathcal{A}=\mathrm{I}-\begin{bmatrix}A^{-1}&0\\B^{\operatorname{T}}A^{-1}&-\mathrm{I}\end{bmatrix}\begin{bmatrix}A&B\\B^{\operatorname{T}}&-\mathrm{I}\end{bmatrix}=\begin{bmatrix}\mathrm{I}&0\\0&\mathrm{I}\end{bmatrix}-\begin{bmatrix}\mathrm{I}&A^{-1}B\\0&\mathrm{I}+B^{\operatorname{T}}A^{-1}B\end{bmatrix}=\begin{bmatrix}0&-A^{-1}B\\0&-B^{\operatorname{T}}A^{-1}B\end{bmatrix}$$

Now don't really know what to do next. It would seem I have to somehow show that $$\left|\left|B^{\operatorname{T}}A^{-1}B\right|\right|_2\geq\left|\left|\begin{bmatrix}0&-A^{-1}B\\0&-B^{\operatorname{T}}A^{-1}B\end{bmatrix}\right|\right|_2$$, but I don't know how to do this.

I'm not sure if this is correct, but I think I remember that for any matrix $$\mathfrak{A}$$, either all $$p$$-norms are $$<1$$, $$=1$$ or $$>1$$. If this holds, then we could perhpas do something like this: $$\left|\left|\begin{bmatrix}0&-A^{-1}B\\0&-B^{\operatorname{T}}A^{-1}B\end{bmatrix}\right|\right|_2<1\iff\left|\left|\begin{bmatrix}0&-A^{-1}B\\0&-B^{\operatorname{T}}A^{-1}B\end{bmatrix}\right|\right|_\infty<1\iff\max\left(\left|\left|0\right|\right|_\infty+\left|\left|A^{-1}B\right|\right|_{\infty},\left|\left|0\right|\right|_\infty+\left|\left|B^{\operatorname{T}}A^{-1}B\right|\right|_{\infty}\right)<1\iff\\\max\left(\left|\left|A^{-1}B\right|\right|,\left|\left|B^{\operatorname{T}}A^{-1}B\right|\right|\right)<1$$

So if this reasoning is correct (I wouldn't bet a penny on that), the task would boil down to proving that $$\left|\left|A^{-1}B\right|\right|\leq\left|\left|B^{\operatorname{T}}A^{-1}B\right|\right|$$, but I don't know how to prove it nor if it even holds.

And I haven't yet used the fact that $$A$$ is positive definite!

How to proceed?

Tags :