Robin-Robin iteration contracts to the monolithic trace

For each $i$, $S_i+\alpha I$ is self-adjoint positive definite because $⟨(S_i+\alpha I)z,z⟩=⟨S_{i}z,z⟩+\alpha \mathrm{\parallel }z{\mathrm{\parallel }}^2>0$ for every $z\mathrm{\ne }0$. It is therefore invertible on the finite-dimensional space $\mathrm{\Lambda }$; its inverse and the operators $R_i$ have finite norms, and $\mathrm{\parallel }(\alpha I+S_1{)}^{-1}\mathrm{\parallel }>0$ because $\mathrm{\Lambda }\mathrm{\ne }\{0\}$. Each first solve uniquely determines ${\lambda }_1^{m+1}$, the first exchange uniquely determines $r_2^{m+1}$, the second solve uniquely determines ${\lambda }_2^{m+1}$, and the last exchange uniquely determines $r_1^{m+1}$. Since $M$ is finite, these operations define all passes up to $M$; the tests either return converged at the first pass that satisfies them or, if none does, return budget_exhausted with the last trace. Thus the algorithm is well-defined and terminates within its stated budget.

By [F1] and [F2], $S:=S_1+S_2$ is positive definite, so the monolithic trace ${\lambda }_{\ast }=S^{-1}(f_1+f_2)$ exists uniquely. Set $p_i^{\ast }:=S_i{\lambda }_{\ast }-f_i$; then $p_1^{\ast }+p_2^{\ast }=0$. Define $r_1^{\ast }:=\alpha {\lambda }_{\ast }+p_1^{\ast }$ and $r_2^{\ast }:=\alpha {\lambda }_{\ast }+p_2^{\ast }$.

The first Robin equation in [F3] is equivalent to $r_1=\alpha {\lambda }_1+p_1$, and its exchange is $r_2=\alpha {\lambda }_1-p_1$; the second equation and exchange have the same forms with indices 1 and 2 reversed. Since $p_2^{\ast }=-p_1^{\ast }$, the pair $(r_1^{\ast },r_2^{\ast })$ is unchanged by both exchanges, so ${\lambda }_{\ast }$ gives a fixed point.

Conversely, at any fixed point the two exchange equalities give $r_2=\alpha {\lambda }_1-p_1=\alpha {\lambda }_2+p_2$ and $r_1=\alpha {\lambda }_1+p_1=\alpha {\lambda }_2-p_2$. Adding the equalities for $r_2$ and $r_1$ yields $2\alpha ({\lambda }_1-{\lambda }_2)=0$, hence ${\lambda }_1={\lambda }_2$; subtracting yields $p_1+p_2=0$. Thus the common trace solves the unique monolithic equation from step 1.2, proving the fixed point is unique.

By [F2] and [F4], in an orthonormal eigenbasis of $S_i$, $R_i$ has eigenvalues $(\alpha -\sigma )\mathrm{/}(\alpha +\sigma )$ with $\sigma >0$. Each has absolute value strictly below $1$, so $q_i<1$. Subtracting the fixed-point equations from the iteration equations in [F3] gives $r_2^{m+1}-r_2^{\ast }=R_1(r_1^m-r_1^{\ast })$ and then $r_1^{m+1}-r_1^{\ast }=R_2(r_2^{m+1}-r_2^{\ast })$. Therefore the displayed error map holds and $q=q_1{q}_2<1$.

Put $e_m=r_1^m-r_1^{\ast }$ and $d_m=r_1^{m+1}-r_1^m$. The error map in step 3.1 gives $d_m=(R_2{R}_1-I)e_m$. Since $\mathrm{\parallel }{R}_2{R}_1\mathrm{\parallel }\le q<1$, the reverse triangle inequality yields $\mathrm{\parallel }{d}_m\mathrm{\parallel }\ge (1-q)\mathrm{\parallel }{e}_m\mathrm{\parallel }$. The first solve in [F3] gives ${\lambda }_1^{m+1}-{\lambda }_{\ast }=(\alpha I+S_1{)}^{-1}{e}_m$. Therefore the stop test in [F3] implies $\mathrm{\parallel }{\lambda }_1^{m+1}-{\lambda }_{\ast }\mathrm{\parallel }\le \mathrm{\parallel }(\alpha I+S_1{)}^{-1}\mathrm{\parallel }\mathrm{\parallel }{d}_m\mathrm{\parallel }\mathrm{/}(1-q)\le \epsilon$. If the finite pass budget is exhausted without this test, no trace certificate has been issued.