The Convergence of block and Gauss-Seidel method

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

The task:

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?



Related Questions




Discussion on solving $Ax=b$

Updated January 08, 2018 14:20 PM