On the Convergence of the Damped Additive Schwarz Methods and the Subdomain Coloring

Abstract

In this paper, we consider that the subdomains of the domain decomposition are colored such that the subdomains with the same color do not intersect and introduce and analyze the convergence of a damped additive Schwarz method related to such a subdomain coloring for the resolution of variational inequalities and equations. In this damped method, a single damping value is associated with all the subdomains having the same color. We first make this analysis both for variational inequalities and, as a special case, for equations in an abstract framework. By introducing an assumption on the decomposition of the convex set of the variational inequality, we theoretically analyze in a reflexive Banach space the convergence of the damped additive Schwarz method. The introduced assumption contains a constant $C_0$, and we explicitly write the expression of the convergence rates, depending on the number of colors and the constant $C_0$, and find the values of the damping constants which minimize them. For problems in the finite element spaces, we write the constant $C_0$ as a function of the overlap parameter of the domain decomposition and the number of colors of the subdomains. We show that, for a fixed overlap parameter, the convergence rate, as a function of the number of subdomains has an upper limit which depends only on the number of the colors of the subdomains. Obviously, this limit is independent of the total number of subdomains. Numerical results are in agreement with the theoretical ones. They have been performed for an elasto-plastic problem to verify the theoretical predictions concerning the choice of the damping parameter, the dependence of the convergence on the overlap parameter and on the number of subdomains.

1. Introduction

The literature on the domain decomposition methods is very vast and we cite here, just to get an idea, the books [1,2,3,4,5] and the proceedings of the annual conferences dedicated to these methods, the first one, [6], being held in 1988. Multiplicative and additive Schwarz methods were among the first studied ones and then have become the starting point in the study of other domain decomposition methods. It is worth noting that, at least for the symmetric positive definite problems, the analysis of the additive and multiplicative Schwarz methods can be made with rather close approaches (see [7,8], for instance). Furthermore, many iterative substructuring methods or other domain decomposition methods can be viewed as additive Schwarz methods or fit into the framework of these methods (see [9], for instance). However, we will limit ourselves in the following to cite only papers dealing with the additive ones and, evidently, the list can be completed with many other papers. Unlike the case of the multiplicative method, when we directly extend the additive method to more than two subdomains, the domain decomposition should have some properties in order to get a convergent method. This can be an explanation of the fact that the first max-norm bounds of the error have been obtained for a damped additive Schwarz iteration, but not for a directly extended one. These error estimates have been obtained in [10] for algebraic linear systems with symmetric and positive definite matrices or nonsymmetric M-matrices. A slight generalization of the damped method in [10] has been introduced in [11] and weighted max-norm estimates have been obtained for complementarity problems.

Besides the matricial approaches with estimates using max-norms, weighted or not, there also exist approaches where the functional framework is that of the PDEs and the error estimates are given in the Sobolev norms. In [12], the damped additive Schwarz method is introduced for the constrained minimization of functionals in reflexive Banach spaces. When the convex set of the constraints is the whole space, this method was introduced in [13]. Furthermore, multigrid methods for inequalities in reflexive Banach spaces, using iterations of damped additive type, are analyzed in [14]. An additive Schwarz–Richardson method for monotone nonlinear elliptic equations in the framework of the PDEs has been given in [15], with some extensions in [16]. In [17], additive and multiplicative Schwarz methods are introduced to solve inequalities perturbed by a Lipschitz operator.

For molecular problems where the domain is the union of subdomains associated with the atoms of the molecule and each atom corresponds to a subdomain, numerical experiments in [18,19,20] have shown that the additive Schwarz method is scalable, that is the convergence rate does not depend on the number of subdomains. A theoretical justification of the scalability of the additive Schwarz method for such problems in which the domain is a chain of subdomains is given in [21,22,23]. Furthermore, in [24], it is proved that the scalability of the one-level methods strongly depends on the geometry of the domain and on conditions imposed on the boundary of the subdomains.

In this paper, the domain of the problem is fixed and we consider that the subdomains are colored such that the subdomains having the same color do not intersect. We study the dependence of the convergence of the damped additive Schwarz method, applied to the resolution of variational inequalities as well as equations, on the subdomain coloring. In this method, a single damping value is associated with all the subdomains having the same color. In this way, the damped method can be rewritten, in an equivalent form, for the subdomains which are obtained as the union of the subdomains having the same color. The paper is organized as follows. In the next section, we analyze the convergence of a damped additive Schwarz method in an abstract framework. To this end, an assumption, which contains a constant $C_0$, on the decomposition of the convex set of the variational inequality is introduced. We prove general convergence results in a reflexive Banach space and explicitly write the expression of the convergence rate depending on the number of colors and the constant $C_0$. Furthermore, we show that the convergence rate reaches its minimum when the damping constants associated with the colors of the subdomains have the same value and we find this value according to the number of colors. These general results allow us to consider problems in the Sobolev spaces $W^{1,s}$, $1<s<\infty$, but not only in $H^1$. In the finite element spaces, in Section 3, we write the constant $C_0$ as a function of the overlap parameter of the domain decomposition and the number of colors of the subdomains. Then we show that, for a fixed overlap parameter, the convergence rate, as a function of the number of subdomains has an upper limit that depends only on the minimum number of the colors of the subdomains, i.e., this upper limit is independent of the number of subdomains. The numerical results in Section 4 confirm the theoretical ones. They have been performed for an elasto-plastic problem to verify the theoretical predictions concerning the choice of the damping parameter, the dependence of the convergence on the overlap parameter and on the number of subdomains.

We think that similar analyzes can be made for other domain decomposition methods, even if they require damping parameters or not. If we color the subdomains such that the local problems corresponding to each color can be solved simultaneously, then, as we mentioned above, the algorithm could be rewritten for the subdomains which are obtained as the union of the (initial) subdomains having the same color and we can do the analysis using that form of the algorithm.

2. General Convergence Result

In this section, we introduce and analyze the convergence of a damped additive Schwarz method related to a subdomain coloring for the resolution of variational inequalities and equations in an abstract framework. This general framework has been used in [12,14,25,26], for instance, in order to allow us to consider problems in the Sobolev spaces $W^{1,s}$, $1<s<\infty$, but not only in $H^1$. An example of solving such a variational inequality by a domain decomposition method is given [25].

Let us consider a reflexive Banach space V and a $K\subset V$ be a non empty closed convex subset. Furthermore, let $F:V\to \mathbb{R}$ be a Gâteaux differentiable functional, which is assumed to be coercive on K, in the sense that $F\left(v\right)\to \infty ,\mathrm{as}\left|\right|v\left|\right|\to \infty$, $v\in K$, if K is not bounded. Furthermore, we assume that there exist two real numbers $p,q>1$ such that for any real number $M>0$ there exist constants ${\alpha }_M,{\beta }_M>0$ for which

$$\begin{array}{c}{\alpha }_M\left|\right|v-{u\left|\right|}^p\le \langle F^{\prime }\left(v\right)-F^{\prime }\left(u\right),v-u\rangle \mathrm{and}\hfill \\ \left|\right|F^{\prime }\left(v\right)-F^{\prime }{\left(u\right)\left|\right|}_{V^{\prime }}\le {\beta }_M\left|\right|v-{u\left|\right|}^{q-1}\hfill \end{array}$$

(1)

for any $u,v\in V$ with $\left|\right|u\left|\right|,\left|\right|v\left|\right|\le M$. Above, we have denoted by $F^{\prime }$ the Gâteaux derivative of F, and we have marked that the constants ${\alpha }_M$ and ${\beta }_M$ may depend on M. We point out that since F is Gâteaux differentiable and satisfies (1), then F is a convex functional (see Proposition 5.5 in [27], page 25).

It is evident that if (1) holds, then for any $u,v\in V$, $\left|\right|u\left|\right|,\left|\right|v\left|\right|\le M$, we have

$${\alpha }_M\left|\right|v-{u\left|\right|}^p\le \langle F^{\prime }\left(v\right)-F^{\prime }\left(u\right),v-u\rangle \le {\beta }_M\left|\right|v-{u\left|\right|}^q.$$

Following the method in [28], we can prove that for any $u,v\in V$, $\left|\right|u\left|\right|,\left|\right|v\left|\right|\le M$, we have

$$\begin{array}{c}\langle F^{\prime }\left(u\right),v-u\rangle +\frac{{\alpha }_M}{p}\left|\right|v-{u\left|\right|}^p\le F\left(v\right)-F\left(u\right)\le \hfill \\ \langle F^{\prime }\left(u\right),v-u\rangle +\frac{{\beta }_M}{q}\left|\right|v-{u\left|\right|}^q.\hfill \end{array}$$

(2)

Furthermore, using the same techniques, we can prove that if F satisfies (1), then

$$1<q\le 2\le p.$$

(3)

We consider the variational inequality

$$u\in K:\langle F^{\prime }\left(u\right),v-u\rangle \ge 0,\mathrm{for}\mathrm{any}v\in K$$

(4)

and since the functional F is convex and differentiable, it is equivalent to the minimization problem

$$u\in K:F\left(u\right)\le F\left(v\right),\mathrm{for}\mathrm{any}v\in K.$$

(5)

We can use, for instance, [27], Proposition 1.2, page 34, to prove that problem (5), and therefore inequality (4), have a unique solution if F has the above properties. In the view of (2), for a given $M>0$ such that the solution $u\in K$ of (5) satisfies $\left|\right|u\left|\right|\le M$, we have

$$\frac{{\alpha }_M}{p}\left|\right|v-{u\left|\right|}^p\le F\left(v\right)-F\left(u\right)\mathrm{for}\mathrm{any}v\in K,\left|\right|v\left|\right|\le M.$$

(6)

In this general framework, in order to introduce the algorithm corresponding to the damped additive Schwarz method, we first consider some closed subspaces of V, $V_1,\cdots ,V_{m_c}$. For any $i=1,\dots ,m_c$, we introduce the sets $I_i=\{1,\dots ,m_i\}$ and for all $j\in I_i$ let $V_{ij}\subset V_i$ be closed subspaces for which we make the hypothesis

Assumption 1.

$V_i$ is the direct sum of $V_{i1},\dots ,V_{i{m}_i}$

$$V_i=V_{i1}\oplus \dots \oplus V_{i{m}_i}$$

(7)

and if $v\in K$ and ${\displaystyle v_i=\sum _{j\in I_i}{v}_{ij}\in V_i}$ with $v_{ij}\in V_{ij}$ then

$$v+v_i\in Kifandonlyifv+v_{ij}\in Kforanyj\in I_i$$

(8)

Besides that, we assume that

$$\langle F^{\prime }(v+v_{ij}),v_{ik}\rangle =\langle F^{\prime }\left(v\right),v_{ik}\rangle foranyv\in V,v_{ij}\in V_{ij},v_{ik}\in V_{ik},j,k\in I_i,j\ne k$$

(9)

In the case of the additive Schwarz method, the subspaces $V_{ij}$, $i=1,\cdots ,m_c$, $j=1,\cdots ,m_i$, will be Sobolev spaces associated with the subdomains of the domain decomposition. As we said before, the subdomains are colored such that the subdomains having the same color do not intersect. With the above notations, the number of the colors is $m_c$ and the number of the subdomains having the color i is $m_i$. Obviously, in this case, the above assumption is satisfied.

Now we fix a constant s satisfying

$$\frac{p}{p-q+1}\le s\le p$$

(10)

which comes from the space Sobolev $W^{1,s}$, where p and q are given in (1), and make a second hypothesis

Assumption 2.

There exists a constant $C_0>0$ such that for any $w,v\in K$ there exist $v_i\in V_i$, $i=1,\cdots ,m_c$, which satisfy

$${\displaystyle v-w=\sum _{i=1}^{m_c}{v}_i,w+v_i\in Kand\sum _{i=1}^{m_c}\left|\right|v_i{\left|\right|}^s\le C_0^s\left|\right|v-{w\left|\right|}^s.}$$

In general, we can assume that we are using the Sobolev space $W^{1,p}$ and consider $s=p$ in (10) and Assumption 2. Condition (10) has been introduced in [14] to get more variants for the choice of s. The above assumption is satisfied for a large kind of convex sets in Sobolev spaces. Constant $C_0$ will play an important role in evaluation of the rate of convergence of the method. In the convergence proofs, vs. is the exact solution of the inequality, w is the solution of the iterative algorithm at a certain iteration, and $v_i$ are its corrections on the subspaces $V_i$, $i=1,...,m_c$.

To solve problem (4), we introduce the following damped additive subspace correction Algorithm 1 corresponding to the subspaces $V_{ij}$, $i=1,\dots ,m_c$ and $j\in I_i$, and the convex set K.

Algorithm 1.

We start the algorithm with an arbitrary $u^0\in K$. At iteration $n+1$, having $u^n\in K$, $n\ge 0$, we solve the inequalities

$$\begin{array}{c}{w}_{ij}^{n+1}\in V_{ij},u^n+w_{ij}^{n+1}\in K:\langle F^{\prime }(u^n+w_{ij}^{n+1}),v_{ij}-w_{ij}^{n+1}\rangle \ge 0,\hfill \\ forany{v}_{ij}\in V_{ij},u^n+v_{ij}\in K,\hfill \end{array}$$

(11)

for $i=1,\cdots ,m_c$ and $j\in I_i$, and then update ${\displaystyle u^{n+1}=u^n+\sum _{i=1}^{m_c}{\varrho }_i\sum _{j\in I_i}{w}_{ij}^{n+1}}$, where ${\varrho }_i>0$ is chosen such that ${\displaystyle \varrho =\sum _{i=1}^{m_c}{\varrho }_i\le 1}$.

The choice of the constants ${\varrho }_i$, $i=1,\dots ,m_c$, implies $u^{n+1}\in K$ for any $n\ge 0$. Indeed, since $0<\varrho \le 1$ and, in view of (8), we have ${\displaystyle u^{n+1}=(1-\varrho )u^n+\sum _{i=1}^{m_c}{\varrho }_i(u^n+\sum _{i\in I_i}{w}_{ij}^{n+1})\in K}$. In the following, we shall write

$${\varrho }_{min}=\underset{i=1,\dots ,m_c}{min}{\varrho }_i$$

Now, we rewrite this algorithm as Algorithm 2.

Algorithm 2.

We start the algorithm with an arbitrary $u^0\in K$. At iteration $n+1$, having $u^n\in K$, $n\ge 0$, we solve the inequalities

$$\begin{array}{c}{w}_i^{n+1}\in V_i,u^n+w_i^{n+1}\in K:\langle F^{\prime }(u^n+w_i^{n+1}),v_i-w_i^{n+1}\rangle \ge 0,\hfill \\ forany{v}_i\in V_i,u^n+v_i\in K,\hfill \end{array}$$

(12)

and then update ${\displaystyle u^{n+1}=u^n+\sum _{i=1}^{m_c}{\varrho }_i{w}_i^{n+1}}$, where ${\varrho }_i>0$ is chosen such that ${\displaystyle \varrho =\sum _{i=1}^{m_c}{\varrho }_i\le 1}$.

Remark 1.

In view of Assumption 1, for a certain $i=1,\dots ,m_c$, inequality (12) is equivalent with a system of $m_i$ of inequalities (11) and its solution can be written as ${\displaystyle w_i^{n+1}=\sum _{j\in I_i}{w}_{ij}^{n+1}}$, where $w_{ij}^{n+1}$, $j\in I_i$, are the solutions of inequalities (11).

Evidently, problem (12) is equivalent with

$$\begin{array}{c}{w}_i^{n+1}\in V_i,u^n+w_i^{n+1}\in K:F(u^n+w_i^{n+1})\le F(u^n+v_i),\hfill \\ forany{v}_i\in V_i,u^n+v_i\in K.\hfill \end{array}$$

(13)

We now prove the convergence of Algorithm 2 and therefore, of that of Algorithm 1.

Theorem 1.

Let V be a reflexive Banach space, $V_1,\cdots ,V_{m_c}$ are some closed subspaces of V, K is a non empty closed convex subset of V satisfying Assumption 2, and F is a Gâteaux differentiable functional on V which is supposed to be coercive if K is not bounded, and satisfies (1). On these conditions, if u is the solution of problem (4) and $u^n$, $n\ge 0$, are its approximations obtained from Algorithm 2, then there exists an $0<M<\infty$ such that $\left|\right|u^n\left|\right|\le M$, for any $n\ge 0$, and the following error estimations hold

(i)

if $p=q=2$ we haven

$$F\left(u^n\right)-F\left(u\right)\le {\left(\frac{C_1}{C_1+1}\right)}^n\left[F\left(u^0\right)-F\left(u\right)\right],$$

(14)

$$\left|\right|u^n-u{\left|\right|}^p\le \frac{p}{{\alpha }_M}{\left(\frac{C_1}{C_1+1}\right)}^n\left[F\left(u^0\right)-F\left(u\right)\right],$$

(15)

where

$$C_1=\frac{1-{\varrho }_{min}}{{\varrho }_{min}}+\frac{{\beta }_M}{{\left(\frac{{\alpha }_M}{2}\right)}^2}\frac{\varrho }{{\varrho }_{min}^2}\left[\frac{{\alpha }_M}{2}(1+C_0{m}_c^{1/2})+{\beta }_M{C}_0^2{m}_c\right]$$

(16)

and

(ii)

if $p>q$ we have

$$F\left(u^n\right)-F\left(u\right)\le \frac{F\left(u^0\right)-F\left(u\right)}{{\left[1+n{C}_2{\left(F\left(u^0\right)-F\left(u\right)\right)}^{\frac{p-q}{q-1}}\right]}^{\frac{q-1}{p-q}}},$$

(17)

$$\left|\right|u-u^n{\left|\right|}^p\le \frac{p}{{\alpha }_M}\frac{F\left(u^0\right)-F\left(u\right)}{{\left[1+n{C}_2{\left(F\left(u^0\right)-F\left(u\right)\right)}^{\frac{p-q}{q-1}}\right]}^{\frac{q-1}{p-q}}},$$

(18)

where

$$C_2=\frac{p-q}{(p-1){\left(F\left(u^0\right)-F\left(u\right)\right)}^{\frac{p-q}{q-1}}+(q-1)C_3^{\frac{p-1}{q-1}}}$$

(19)

with

$$\begin{array}{c}{\displaystyle C_3=\frac{1-{\varrho }_{min}}{{\varrho }_{min}}{(F\left(u^0\right)-F\left(u\right))}^{(p-q)/(p-1)}+}\hfill \\ {\displaystyle {\beta }_M\frac{{\varrho }^{(p-1)q/p}}{{\varrho }_{min}^q}\left(1+C_0{m}_c^{(s-1)/s}\right)\frac{1}{{\left(\frac{{\alpha }_M}{p}\right)}^{q/p}}{\left(F\left(u^0\right)-F\left(u\right)\right)}^{(p-q)/\left(p\right(p-1\left)\right)}+}\hfill \\ {\displaystyle {\left(\frac{{\beta }_M{C}_0{m}_c^{(s-1)/s}}{{\varrho }_{min}^{q-1}}\right)}^{p/(p-1)}\frac{{\varrho }^{q-1}}{{\left(\frac{{\alpha }_M}{p}\right)}^{q/(p-1)}}.}\hfill \end{array}$$

(20)

Proof. 

In view of the convexity of F and Equation (13), we get

$$\begin{array}{c}{\displaystyle F\left(u^{n+1}\right)=F(u^n+\sum _{i=1}^{m_c}{\varrho }_i{w}_i^{n+1})=F((1-\varrho )u^n+\sum _{i=1}^{m_c}{\varrho }_i(u^n+w_i^{n+1}))\le }\hfill \\ {\displaystyle (1-\varrho )F\left(u^n\right)+\sum _{i=1}^{m_c}{\varrho }_{i}F(u^n+w_i^{n+1})\le F\left(u^n\right)}\hfill \end{array}$$

(21)

Consequently, the sequence ${\left(u^n\right)}_{n\ge 0}$ of u obtained from Algorithm 2 is bounded. Moreover, using again (13), we get that $F(u^n+w_i^{n+1})\le F\left(u^n\right)$, i.e., the sequences ${\left(w_i^{n+1}\right)}_{n\ge 0}$, $i=1,\dots ,m_c$ are bounded. In this proof, Equation (1) are used with u and v replaced only by u, the solution of (4), or by some linear combinations of $u^n$ and $w_i^{n+1}$ whose norm is bounded independently of $n\ge 0$ and $i=1,\dots ,m_c$. Therefore, there exists an $M>0$ which can be used in Equation (1) to prove the error estimations in the statement of the theorem. In the following, we use (1) with such an M.

In view of (2) and (12), we get

$$\frac{{\alpha }_M}{p}\left|\right|w_i^{n+1}{\left|\right|}^p\le F\left(u^n\right)-F(u^n+w_i^{n+1}).$$

Using this equation and (21), we get

$$\begin{array}{c}{\displaystyle F\left(u^{n+1}\right)\le (1-\varrho )F\left(u^n\right)+\sum _{i=1}^{m_c}{\varrho }_{i}F(u^n+w_i^{n+1})\le }\hfill \\ {\displaystyle (1-\varrho )F\left(u^n\right)+\varrho F\left(u^n\right)+\frac{{\alpha }_M}{p}\sum _{i=1}^{m_c}{\varrho }_i\left|\right|w_i^{n+1}{\left|\right|}^p}\hfill \end{array}$$

and therefore,

$${\displaystyle \frac{{\alpha }_M}{p}\sum _{i=1}^{m_c}{\varrho }_i\left|\right|w_i^{n+1}{\left|\right|}^p\le F\left(u^n\right)-F\left(u^{n+1}\right)}$$

(22)

Now, writing

$${\displaystyle {\overline{u}}^{n+1}=u^n+\frac{1}{{\varrho }_{min}}\sum _{i=1}^{m_c}{\varrho }_i{w}_i^{n+1}}$$

in view of the convexity of F, we have

$$\begin{array}{c}{\displaystyle F\left(u^{n+1}\right)=F(u^n+\sum _{i=1}^{m_c}{\varrho }_i{w}_i^{n+1})=F((1-{\varrho }_{min})u^n+{\varrho }_{min}{\overline{u}}^{n+1})\le }\hfill \\ {\displaystyle (1-{\varrho }_{min})F\left(u^n\right)+{\varrho }_{min}F\left({\overline{u}}^{n+1}\right)}\hfill \end{array}$$

(23)

With $v:=u$ and $w:=u^n$, we get a decomposition $v_i^n\in V_i$ of $u-u^n$ satisfying the conditions of Assumption 2. Using this decomposition, the above equation, (2) and inequalities (12), we get

$$\begin{array}{c}F\left(u^{n+1}\right)-F\left(u\right)+{\varrho }_{min}\frac{{\alpha }_M}{p}\left|\right|{\overline{u}}^{n+1}-u{\left|\right|}^p\le \hfill \\ {\displaystyle (1-{\varrho }_{min})(F\left(u^n\right)-F\left(u\right))+{\varrho }_{min}\left(F\left({\overline{u}}^{n+1}\right)-F\left(u\right)+\frac{{\alpha }_M}{p}\left|\right|{\overline{u}}^{n+1}-u{\left|\right|}^p\right)\le }\hfill \\ {\displaystyle (1-{\varrho }_{min})(F\left(u^n\right)-F\left(u\right))+{\varrho }_{min}\langle F^{\prime }\left({\overline{u}}^{n+1}\right),{\overline{u}}^{n+1}-u\rangle =}\hfill \\ {\displaystyle (1-{\varrho }_{min})(F\left(u^n\right)-F\left(u\right))+\sum _{i=1}^{m_c}\langle F^{\prime }\left({\overline{u}}^{n+1}\right),{\varrho }_i{w}_i^{n+1}-{\varrho }_{min}{v}_i^n\rangle \le }\hfill \\ {\displaystyle (1-{\varrho }_{min})(F\left(u^n\right)-F\left(u\right))+}\hfill \\ {\displaystyle \sum _{i=1}^{m_c}\langle F^{\prime }(u^n+w_i^{n+1})-F^{\prime }\left({\overline{u}}^{n+1}\right),{\varrho }_{min}{v}_i^n+(1-{\varrho }_i)w_i^{n+1}-w_i^{n+1}\rangle \le }\hfill \\ {\displaystyle (1-{\varrho }_{min})(F\left(u^n\right)-F\left(u\right))+}\hfill \\ {\displaystyle {\beta }_M\sum _{i=1}^{m_c}{\left((\frac{{\varrho }_i}{{\varrho }_{min}}-1)\left|\right|w_i^{n+1}\left|\right|+\sum _{j=1,j\ne i}^{m_c}\frac{{\varrho }_j}{{\varrho }_{min}}\left|\right|w_j^{n+1}\left|\right|\right)}^{q-1}\left|\right|{\varrho }_{min}{v}_i^n-{\varrho }_i{w}_i^{n+1}\left|\right|\le }\hfill \\ {\displaystyle (1-{\varrho }_{min})(F\left(u^n\right)-F\left(u\right))+{\beta }_M{\left(\sum _{i=1}^{m_c}\frac{{\varrho }_i}{{\varrho }_{min}}\left|\right|w_i^{n+1}\left|\right|\right)}^{q-1}\sum _{i=1}^{m_c}\left|\right|{\varrho }_{min}{v}_i^n-{\varrho }_i{w}_i^{n+1}\left|\right|\le }\hfill \\ {\displaystyle (1-{\varrho }_{min})(F\left(u^n\right)-F\left(u\right))+{\beta }_M\frac{{\varrho }^{(p-1)(q-1)/p}}{{\varrho }_{min}^{q-1}}{\left(\sum _{i=1}^{m_c}{\varrho }_i\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{(q-1)/p}·}\hfill \\ {\displaystyle \left({\varrho }_{min}\sum _{i=1}^{m_c}\left|\right|v_i^n\left|\right|+\sum _{i=1}^{m_c}{\varrho }_i\left|\right|w_i^{n+1}\left|\right|\right)}\hfill \end{array}$$

Above, we have used the fact that ${\varrho }_{\min }{v}_i^n+(1-{\varrho }_i)w_i^{n+1}\in V_i$ and $u^n+{\varrho }_{\min }{v}_i^n+(1-{\varrho }_i)w_i^{n+1}=(1-{\varrho }_i)(u^n+w_i^{n+1})+{\varrho }_{\min }(u^n+v_i^n)+({\varrho }_i-{\varrho }_{\min })u^n$ which, in view of the fact that $(1-{\varrho }_i)+{\varrho }_{\min }+({\varrho }_i-{\varrho }_{\min })=1$, belongs to K. Therefore, we can replace $v_i$ by ${\varrho }_{\min }{v}_i^n+(1-{\varrho }_i)w_i^{n+1}$ in (12). Now, given Assumption 2, we have

$$\begin{array}{c}{\displaystyle {\varrho }_{min}\sum _{i=1}^{m_c}\left|\right|v_i^n\left|\right|+\sum _{i=1}^{m_c}{\varrho }_i\left|\right|w_i^{n+1}\left|\right|\le }\hfill \\ {\displaystyle {\varrho }_{min}{m}_c^{(s-1)/s}{\left(\sum _{i=1}^{m_c}\left|\right|v_i^n{\left|\right|}^s\right)}^{1/s}+{\varrho }^{(p-1)/p}{\left(\sum _{i=1}^{m_c}{\varrho }_i\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{1/p}\le }\hfill \\ {\displaystyle C_0{\varrho }_{min}{m}_c^{(s-1)/s}\left|\right|u-u^n\left|\right|+{\varrho }^{(p-1)/p}{\left(\sum _{i=1}^{m_c}{\varrho }_i\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{1/p}\le }\hfill \\ {\displaystyle C_0{\varrho }_{min}{m}_c^{(s-1)/s}\left|\right|u-{\overline{u}}^{n+1}\left|\right|+{\varrho }^{(p-1)/p}\left(1+C_0{m}_c^{(s-1)/s}\right){\left(\sum _{i=1}^{m_c}{\varrho }_i\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{1/p}}\hfill \end{array}$$

From the above two equations, we get

$$\begin{array}{c}F\left(u^{n+1}\right)-F\left(u\right)+{\varrho }_{min}\frac{{\alpha }_M}{p}\left|\right|{\overline{u}}^{n+1}-u{\left|\right|}^p\le \hfill \\ {\displaystyle (1-{\varrho }_{min})(F\left(u^n\right)-F\left(u\right))+{\beta }_M\frac{{\varrho }^{(p-1)(q-1)/p}}{{\varrho }_{min}^{q-1}}{\left(\sum _{i=1}^{m_c}{\varrho }_i\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{(q-1)/p}·}\hfill \\ {\displaystyle \left[C_0{\varrho }_{min}{m}_c^{(s-1)/s}\left|\right|u-{\overline{u}}^{n+1}\left|\right|+{\varrho }^{(p-1)/p}\left(1+C_0{m}_c^{(s-1)/s}\right)\right.}\hfill \\ {\displaystyle ·\left.{\left(\sum _{i=1}^{m_c}{\varrho }_i\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{1/p}\right]=}\hfill \\ {\displaystyle (1-{\varrho }_{min})(F\left(u^n\right)-F\left(u\right))+{\beta }_M\frac{{\varrho }^{(p-1)q/p}}{{\varrho }_{min}^{q-1}}}\hfill \\ {\displaystyle ·\left(1+C_0{m}_c^{(s-1)/s}\right){\left(\sum _{i=1}^{m_c}{\varrho }_i\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{q/p}+}\hfill \\ {\displaystyle {\beta }_M{C}_0{\varrho }^{(p-1)(q-1)/p}{\varrho }_{min}^{2-q}{m}_c^{(s-1)/s}\left|\right|u-{\overline{u}}^{n+1}\left|\right|{\left(\sum _{i=1}^{m_c}varrh{o}_i\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{(q-1)/p}}\hfill \end{array}$$

(24)

However, for any $\epsilon >0$ $r>1$ and $x,y\ge 0$, we have $x^{\frac{1}{r}}y\le \epsilon x+\frac{1}{{\epsilon }^{\frac{1}{r-1}}}{y}^{\frac{r}{r-1}}$. Consequently, we get

$$\begin{array}{c}F\left(u^{n+1}\right)-F\left(u\right)+{\varrho }_{min}\frac{{\alpha }_M}{p}\left|\right|{\overline{u}}^{n+1}-u{\left|\right|}^p\le (1-{\varrho }_{min})(F\left(u^n\right)-F\left(u\right))+\hfill \\ {\displaystyle {\beta }_M\frac{{\varrho }^{(p-1)q/p}}{{\varrho }_{min}^{q-1}}\left(1+C_0{m}_c^{(s-1)/s}\right){\left(\sum _{i=1}^{m_c}{\varrho }_i\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{q/p}+}\hfill \\ {\displaystyle {\beta }_M{C}_0{\varrho }^{(p-1)(q-1)/p}{\varrho }_{min}^{2-q}{m}_c^{(s-1)/s}\frac{1}{{\epsilon }^{\frac{1}{p-1}}}{\left(\sum _{i=1}^{m_c}{\varrho }_i\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{(q-1)/(p-1)}+}\hfill \\ {\beta }_M{C}_0{\varrho }^{(p-1)(q-1)/p}{\varrho }_{min}^{2-q}{m}_c^{(s-1)/s}\epsilon \left|\right|u-{\overline{u}}^{n+1}{\left|\right|}^p\hfill \end{array}$$

With

$$\epsilon =\frac{{\alpha }_M}{p}\frac{{\varrho }_{min}^{q-1}}{{\beta }_M{C}_0{\varrho }^{(p-1)(q-1)/p}{m}_c^{(s-1)/s}},$$

the above equation becomes,

$$\begin{array}{c}{\displaystyle F\left(u^{n+1}\right)-F\left(u\right)\le \frac{1-{\varrho }_{min}}{{\varrho }_{min}}(F\left(u^n\right)-F\left(u^{n+1}\right))+}\hfill \\ {\displaystyle {\beta }_M\frac{{\varrho }^{(p-1)q/p}}{{\varrho }_{min}^q}\left(1+C_0{m}_c^{(s-1)/s}\right){\left(\sum _{i=1}^{m_c}{\varrho }_i\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{q/p}+}\hfill \\ {\displaystyle {\left(\frac{{\beta }_M{C}_0{m}_c^{(s-1)/s}}{{\varrho }_{min}^{q-1}}\right)}^{p/(p-1)}\frac{{\varrho }^{q-1}}{{\left(\frac{{\alpha }_M}{p}\right)}^{1/(p-1)}}{\left(\sum _{i=1}^{m_c}{\varrho }_i\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{(q-1)/(p-1)}.}\hfill \end{array}$$

In view of this equation and (22), we have

$$\begin{array}{c}{\displaystyle F\left(u^{n+1}\right)-F\left(u\right)\le \frac{1-{\varrho }_{min}}{{\varrho }_{min}}(F\left(u^n\right)-F\left(u^{n+1}\right))+}\hfill \\ {\displaystyle {\beta }_M\frac{{\varrho }^{(p-1)q/p}}{{\varrho }_{min}^q}\left(1+C_0{m}_c^{(s-1)/s}\right)\frac{1}{{\left(\frac{{\alpha }_M}{p}\right)}^{q/p}}{\left(F\left(u^n\right)-F\left(u^{n+1}\right)\right)}^{q/p}+}\hfill \\ {\displaystyle {\left(\frac{{\beta }_M{C}_0{m}_c^{(s-1)/s}}{{\varrho }_{min}^{q-1}}\right)}^{p/(p-1)}\frac{{\varrho }^{q-1}}{{\left(\frac{{\alpha }_M}{p}\right)}^{q/(p-1)}}{\left(F\left(u^n\right)-F\left(u^{n+1}\right)\right)}^{(q-1)/(p-1)}.}\hfill \end{array}$$

(25)

Using (6), we see that error estimations in (15) and (18) can be obtained from (14) and (17), respectively. Now, in view of (3) and (10), if $p=q=2$, from the above equation, we easily get Equation (14) where $C_1$ given in (16). Finally, if $p>q$, from (25), we have

$$F\left(u^{n+1}\right)-F\left(u\right)\le C_3{\left(F\left(u^n\right)-F\left(u^{n+1}\right)\right)}^{\frac{q-1}{p-1}}$$

(26)

where $C_3$ is given in (20). From (26), we get

$$F\left(u^{n+1}\right)-F\left(u\right)+\frac{1}{C_3^{\frac{p-1}{q-1}}}{\left(F\left(u^{n+1}\right)-F\left(u\right)\right)}^{\frac{p-1}{q-1}}\le F\left(u^n\right)-F\left(u\right),$$

and we know (see Lemma 3.2 in [13]) that for any $r>1$ and $c>0$, if $x\in (0,x_0]$ and $y>0$ satisfy $y+c{y}^r\le x$, then $y\le {\left(\frac{c(r-1)}{cr{x}_0^{r-1}+1}+x^{1-r}\right)}^{\frac{1}{1-r}}$. Consequently, we have

$$F\left(u^{n+1}\right)-F\left(u\right)\le {\left[C_2+{\left(F\left(u^n\right)-F\left(u\right)\right)}^{\frac{q-p}{q-1}}\right]}^{\frac{q-1}{q-p}},$$

from which,

$$\begin{array}{c}F\left(u^{n+1}\right)-F\left(u\right)\le {\left[(n+1)C_2+{\left(F\left(u^0\right)-F\left(u\right)\right)}^{\frac{q-p}{q-1}}\right]}^{\frac{q-1}{q-p}},\hfill \end{array}$$

(27)

where $C_2$ is given in (19). Equation (27) is another form of Equation (17). □

Remark 2.

(1) Given Remark 1 and the above theorem, we conclude that the convergence rate of Algorithm 1 depends on $m_c$ and on the constant $C_0$ introduced in Assumption 2. In the case of the finite element spaces of the next section we shall write the constant $C_0$ as a function of $m_c$ and of the overlap parameter of the domain decomposition. Consequently, for a fixed overlap parameter, the convergence rate, as a function of the number of subdomains can be bounded by an expression that depends only on $m_c$ but not on the total number of subdomains $m=m_1+\dots +m_{m_c}$.

(2) Since $C_1$ in (16) is decreasing in function of ${\varrho }_{min}$ and $C_2$ in (19) is increasing in function of ${\varrho }_{min}$, it follows from error estimations in the above theorem that the minimum convergence rate, as a function of the damping parameters, of Algorithms 1 and 2 is obtained for ${\varrho }_{min}=\varrho /m_c={\varrho }_1=\dots ={\varrho }_{m_c}$. For this value of ${\varrho }_{min}$, denoted by ρ, the value of the constants $C_1$ and $C_3$ in (16) and (20), respectively, become

$$C_1=\frac{1-\rho }{\rho }+\frac{{\beta }_M}{\frac{{\alpha }_M}{2}}\frac{m_c}{\rho }\left[1+C_0{m}_c^{1/2}+\frac{{\beta }_M}{\frac{{\alpha }_M}{2}}{C}_0^2{m}_c\right]$$

(28)

and

$$\begin{array}{c}{\displaystyle C_3=\frac{1-\rho }{\rho }{(F\left(u^0\right)-F\left(u\right))}^{(p-q)/(p-1)}+}\hfill \\ {\displaystyle {\beta }_M\frac{m_c^{(p-1)q/p}}{{\rho }^{q/p}}\left(1+C_0{m}_c^{(s-1)/s}\right)\frac{1}{{\left(\frac{{\alpha }_M}{p}\right)}^{q/p}}{\left(F\left(u^0\right)-F\left(u\right)\right)}^{(p-q)/\left(p\right(p-1\left)\right)}+}\hfill \\ {\displaystyle {\left(\frac{{\beta }_M{C}_0{m}_c^{(s-1)/s}}{{\rho }^{(q-1)/p}}\right)}^{p/(p-1)}\frac{m_c^{q-1}}{{\left(\frac{{\alpha }_M}{p}\right)}^{q/(p-1)}}.}\hfill \end{array}$$

(29)

We also notice that the method with a single damping constant introduced in [10] should converge faster than the methods using several damping constants.

In the case of equations, i.e., when $K=V$, we can get some better error estimations than those in Theorem 1. For completeness, we prove this result when $\rho ={\varrho }_{min}=\varrho /m_c={\varrho }_1=\dots ={\varrho }_{m_c}$. The proof is similar to that of Theorem 1 with the only difference being that, this time, since $K=V$, we are not forced anymore to introduce ${\overline{u}}^{n+1}$ and we use $u^{n+1}$ in the place of it.

Theorem 2.

In the case of equations, i.e., when $K=V$, if we consider Algorithms 1 and 2 with $\rho ={\varrho }_{min}=\varrho /m_c={\varrho }_1=\dots ={\varrho }_{m_c}$, then error estimations (14) and (15) hold with

$$C_1=\frac{{\beta }_M}{\frac{{\alpha }_M}{2}}(1-\rho )m_c\left[C_0^2\frac{{\beta }_M}{\frac{{\alpha }_M}{2}}(1-\rho )m_c+\rho \left(1+C_0{m}_c^{1/2}\right)\right]$$

(30)

and, also, error estimations (17) and (18) hold with

$$\begin{array}{c}{\displaystyle C_3={\left(C_0\frac{{\beta }_M}{{\left(\frac{{\alpha }_M}{p}\right)}^{q/p}}{(1-\rho )}^{(q-1)}{m}_c^{(q-1)(p-1)/p}{m}_c^{(s-1)/s}\right)}^{p/(p-1)}+}\hfill \\ {\displaystyle {\beta }_M\rho {(1-\rho )}^{q-1}{m}_c^{q(p-1)/p}\left(1+C_0{m}_c^{(s-1)/s}\right)\frac{1}{{\left(\frac{{\alpha }_M}{p}\right)}^{q/p}}{\left(F\left(u^0\right)-F\left(u\right)\right)}^{(p-q)/\left(p\right(p-1\left)\right)}}\hfill \end{array}$$

(31)

Proof. 

With $v:=u$ and $w:=u^n$, we get a decomposition $v_i^n\in V_i$ of $u-u^n$ satisfying the conditions of Assumption 2. Using this decomposition, (2), the equations corresponding to inequalities (12) and the fact that $\rho \le \frac{1}{m_c}\le \frac{1}{2}$, we get

$$\begin{array}{c}F\left(u^{n+1}\right)-F\left(u\right)+\frac{{\alpha }_M}{p}\left|\right|u^{n+1}-u{\left|\right|}^p\le \langle F^{\prime }\left(u^{n+1}\right),u^{n+1}-u\rangle =\hfill \\ {\displaystyle \sum _{i=1}^{m_c}\langle F^{\prime }\left(u^{n+1}\right),\rho w_i^{n+1}-v_i^n\rangle =\sum _{i=1}^{m_c}\langle F^{\prime }(u^n+w_i^{n+1})-F^{\prime }\left(u^{n+1}\right),v_i^n-\rho w_i^{n+1}\rangle \le }\hfill \\ {\displaystyle {\beta }_M\sum _{i=1}^{m_c}{\left((1-\rho )\left|\right|w_i^{n+1}\left|\right|+\rho \sum _{j=1,j\ne i}^{m_c}\left|\right|w_j^{n+1}\left|\right|\right)}^{q-1}\left|\right|v_i^n-\rho w_i^{n+1}\left|\right|\le }\hfill \\ {\displaystyle {\beta }_M{(1-\rho )}^{q-1}{\left(\sum _{i=1}^{m_c}\left|\right|w_i^{n+1}\left|\right|\right)}^{q-1}\sum _{i=1}^{m_c}\left|\right|v_i^n-\rho w_i^{n+1}\left|\right|\le }\hfill \\ {\displaystyle {\beta }_M{(1-\rho )}^{q-1}{m}_c^{(q-1)(p-1)/p}{\left(\sum _{i=1}^{m_c}\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{(q-1)/p}\left(\sum _{i=1}^{m_c}\left|\right|v_i^n\left|\right|+\rho \sum _{i=1}^{m_c}\left|\right|w_i^{n+1}\left|\right|\right)}\hfill \end{array}$$

Now, given Assumption 2, we have

$$\begin{array}{c}{\displaystyle \sum _{i=1}^{m_c}\left|\right|v_i^n\left|\right|+\rho \sum _{i=1}^{m_c}\left|\right|w_i^{n+1}\left|\right|\le }\hfill \\ {\displaystyle m_c^{(s-1)/s}{\left(\sum _{i=1}^{m_c}\left|\right|v_i^n{\left|\right|}^s\right)}^{1/s}+\rho m_c^{(p-1)/p}{\left(\sum _{i=1}^{m_c}\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{1/p}\le }\hfill \\ {\displaystyle C_0{m}_c^{(s-1)/s}\left|\right|u-u^n\left|\right|+\rho m_c^{(p-1)/p}{\left(\sum _{i=1}^{m_c}\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{1/p}\le }\hfill \\ {\displaystyle C_0{m}_c^{(s-1)/s}\left|\right|u-u^{n+1}\left|\right|+\rho m_c^{(p-1)/p}\left(1+C_0{m}_c^{(s-1)/s}\right){\left(\sum _{i=1}^{m_c}\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{1/p}}\hfill \end{array}$$

From the above two equations, we get

$$\begin{array}{c}F\left(u^{n+1}\right)-F\left(u\right)+\frac{{\alpha }_M}{p}\left|\right|u^{n+1}-u{\left|\right|}^p\le \hfill \\ {\displaystyle {\beta }_M{(1-\rho )}^{q-1}{m}_c^{(q-1)(p-1)/p}{\left(\sum _{i=1}^{m_c}\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{(q-1)/p}·}\hfill \\ {\displaystyle \left[C_0{m}_c^{(s-1)/s}\left|\right|u-u^{n+1}\left|\right|+\rho m_c^{(p-1)/p}\left(1+C_0{m}_c^{(s-1)/s}\right){\left(\sum _{i=1}^{m_c}\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{1/p}\right]=}\hfill \\ {\displaystyle {\beta }_M{(1-\rho )}^{q-1}{m}_c^{(q-1)(p-1)/p}\left[C_0{m}_c^{(s-1)/s}\left|\right|u-u^{n+1}\left|\right|{\left(\sum _{i=1}^{m_c}\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{(q-1)/p}+\right.}\hfill \\ {\displaystyle \left.\rho m_c^{(p-1)/p}\left(1+C_0{m}_c^{(s-1)/s}\right){\left(\sum _{i=1}^{m_c}\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{q/p}\right]}\hfill \end{array}$$

(32)

However, for any $\epsilon >0$ $r>1$ and $x,y\ge 0$, we have $x^{\frac{1}{r}}y\le \epsilon x+\frac{1}{{\epsilon }^{\frac{1}{r-1}}}{y}^{\frac{r}{r-1}}$. Consequently, we get

$$\begin{array}{c}F\left(u^{n+1}\right)-F\left(u\right)+\frac{{\alpha }_M}{p}\left|\right|u^{n+1}-u{\left|\right|}^p\le \hfill \\ {\displaystyle {\beta }_M{(1-\rho )}^{q-1}{m}_c^{(q-1)(p-1)/p}\left[C_0{m}_c^{(s-1)/s}\epsilon \left|\right|u-u^{n+1}{\left|\right|}^p+\right.}\hfill \\ {\displaystyle C_0{m}_c^{(s-1)/s}\frac{1}{{\epsilon }^{1/(p-1)}}{\left(\sum _{i=1}^{m_c}\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{(q-1)/(p-1)}+}\hfill \\ {\displaystyle \left.\rho m_c^{(p-1)/p}\left(1+C_0{m}_c^{(s-1)/s}\right){\left(\sum _{i=1}^{m_c}\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{q/p}\right]}\hfill \end{array}$$

With

$$\epsilon =\frac{{\alpha }_M}{p}\frac{1}{{\beta }_M{C}_0{(1-\rho )}^{q-1}{m}_c^{(q-1)(p-1)/p}{m}_c^{(s-1)/s}},$$

the above equation becomes,

$$\begin{array}{c}F\left(u^{n+1}\right)-F\left(u\right)\le \hfill \\ {\displaystyle {\left(C_0\frac{{\beta }_M}{{\left(\frac{{\alpha }_M}{p}\right)}^{1/p}}{(1-\rho )}^{(q-1)}{m}_c^{(q-1)(p-1)/p}{m}_c^{(s-1)/s}\right)}^{p/(p-1)}}{\left({\displaystyle \sum _{i=1}^{m_c}}\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{(q-1)/(p-1)}+\hfill \\ {\beta }_M\rho {(1-\rho )}^{q-1}{m}_c^{q(p-1)/p}\left(1+C_0{m}_c^{(s-1)/s}\right){\left({\displaystyle \sum _{i=1}^{m_c}}\left|\right|w_i^{n+1}{\left|\right|}^p\right)}^{q/p}\hfill \end{array}$$

In view of this equation and (22), we have

$$\begin{array}{c}{\displaystyle F\left(u^{n+1}\right)-F\left(u\right)\le {\left(C_0\frac{{\beta }_M}{{\left(\frac{{\alpha }_M}{p}\right)}^{q/p}}{(1-\rho )}^{(q-1)}{m}_c^{(q-1)(p-1)/p}{m}_c^{(s-1)/s}\right)}^{p/(p-1)}·}\hfill \\ {\displaystyle {\left(F\left(u^n\right)-F\left(u^{n+1}\right)\right)}^{(q-1)/(p-1)}+}\hfill \\ {\displaystyle {\beta }_M\rho {(1-\rho )}^{q-1}{m}_c^{q(p-1)/p}\left(1+C_0{m}_c^{(s-1)/s}\right)\frac{1}{{\left(\frac{{\alpha }_M}{p}\right)}^{q/p}}{\left(F\left(u^n\right)-F\left(u^{n+1}\right)\right)}^{q/p}}\hfill \end{array}$$

(33)

As in the proof of Theorem 1, using (6), we get that error estimations in (15) and (18) can be obtained from (14) and (17), respectively. Furthermore, in view of if (3) and (10), if $p=q=2$, from the above equation, we easily get Equation (14) where $C_1$ given in (30). Finally, if $p>q$, from (33), we have

$$F\left(u^{n+1}\right)-F\left(u\right)\le C_3{\left(F\left(u^n\right)-F\left(u^{n+1}\right)\right)}^{\frac{q-1}{p-1}}$$

(34)

where $C_3$ is given in (31), and with this $C_3$, similarly with the proof of Theorem 1, we get (17). □

Remark 3.

From error estimations (14), (15), (17) and (18), we get that the convergence rates of Algorithms 1 and 2 are increasing functions of $C_1$ and $C_3$. Furthermore, in the case when $\rho ={\varrho }_{min}=\varrho /m_c={\varrho }_1=\dots ={\varrho }_{m_c}$, these constants are decreasing functions of ρ, and consequently, in this case, Algorithms 1 and 2 have a minimum convergence rate for $\varrho =1$, i.e., the value of the expression of $C_1$ and $C_3$ is calculate with $\rho =1/m_c$. In this way, in the case of the inequalities, from (28) and (29), we get

$$C_1=m_c-1+\frac{{\beta }_M}{\frac{{\alpha }_M}{2}}{m}_c^2\left[1+C_0{m}_c^{1/2}+\frac{{\beta }_M}{\frac{{\alpha }_M}{2}}{C}_0^2{m}_c\right]$$

(35)

and

$$\begin{array}{c}{\displaystyle C_3=(m_c-1){(F\left(u^0\right)-F\left(u\right))}^{(p-q)/(p-1)}+}\hfill \\ {\displaystyle {\beta }_M\left(1+C_0{m}_c^{(s-1)/s}\right)\frac{m_c^q}{{\left(\frac{{\alpha }_M}{p}\right)}^{q/p}}{\left(F\left(u^0\right)-F\left(u\right)\right)}^{(p-q)/\left(p\right(p-1\left)\right)}+}\hfill \\ {\displaystyle {\left({\beta }_M{C}_0{m}_c^{(s-1)/s}\right)}^{p/(p-1)}\frac{m_c^{p(q-1)/(p-1)}}{{\left(\frac{{\alpha }_M}{p}\right)}^{q/(p-1)}}.}\hfill \end{array}$$

(36)

and, also, in the case of the equations, from (30) and (31), we get

$$C_1=\frac{{\beta }_M}{\frac{{\alpha }_M}{2}}(m_c-1)\left[C_0^2\frac{{\beta }_M}{\frac{{\alpha }_M}{2}}(m_c-1)+\frac{1}{m_c}\left(1+C_0{m}_c^{1/2}\right)\right]$$

(37)

and

$$\begin{array}{c}{\displaystyle C_3={\left(C_0\frac{{\beta }_M}{{\left(\frac{{\alpha }_M}{p}\right)}^{q/p}}{(m_c-1)}^{(q-1)}{m}_c^{(q-1)(2p-1)/p}{m}_c^{(s-1)/s}\right)}^{p/(p-1)}+}\hfill \\ {\displaystyle {(m_c-1)}^{q-1}{m}_c^{q(2p-1)/p-2}\left(1+C_0{m}_c^{(s-1)/s}\right)\frac{{\beta }_M}{{\left(\frac{{\alpha }_M}{p}\right)}^{q/p}}}\hfill \\ {\displaystyle ·{\left(F\left(u^0\right)-F\left(u\right)\right)}^{(p-q)/\left(p\right(p-1\left)\right)}}\hfill \end{array}$$

(38)

3. Damped Additive Schwarz Methods in Finite Element Spaces

Let $\Omega \subset {\mathbb{R}}^d$, $d=1,2$ or 3, be an open bounded domain which is polygonal if $d=2$, or polyhedral, if $d=3$, and we consider a simplicial mesh partition ${\mathcal{T}}_h$ of mesh size h of $\Omega$. Let

$$\Omega =\bigcup _{i=1,\dots ,m_c,j\in I_i}{\Omega }_{ij}$$

(39)

be an overlap subdomain decomposition of $\Omega$, where $I_i=\{1,\dots ,m_i\}$, $i=1,\dots ,m_c$. We assume that ${\mathcal{T}}_h$ supplies a mesh partition for each subdomain ${\Omega }_{ij}$, $j\in I_i$, $i=1,\dots ,m_c$. Furthermore, we assume that the subdomains have been colored with $m_c$ colors, $i=1,\dots ,m_c$, the subdomains ${\Omega }_{ij}$, $j\in I_i$, having the color i do not intersect with each other,

$${\Omega }_{i{j}_1}\cap {\Omega }_{i{j}_2}=\varnothing \mathrm{for}\mathrm{any}i=1,\dots ,m_c\mathrm{and}{j}_1,j_2\in I_i$$

(40)

and a given subdomain has not been colored with two colors,

$$\Omega i_1{j}_1\ne \Omega i_2{j}_2\mathrm{for}\mathrm{any}{i}_1\ne i_2,i_1,i_2=1,\dots ,m_c\mathrm{and}{j}_1\in I_{i_1},j_2\in I_{i_2}.$$

(41)

Evidently, the subdomains obtained as the union of the subdomains of the same color

$${\Omega }_i={\cup }_{j\in I_i}{\Omega }_{ij}\mathrm{for}\mathrm{all}i=1,\dots ,m_c$$

(42)

provide another overlapping domain decomposition of $\Omega$,

$$\Omega ={\cup }_{i=1,\dots ,m_c}{\Omega }_i$$

(43)

From (40) and (42), we get

$$\partial {\Omega }_i={\cup }_{j\in I_i}\partial \Omega ij\mathrm{for}\mathrm{all}i=1,\dots ,m_c$$

(44)

We consider the piecewise linear finite element space

$$V=\{v\in C^0\left(\overline{\Omega }\right):v{|}_{\tau }\in P_1\left(\tau \right),\tau \in {\mathcal{T}}_h,v=0\mathrm{on}\partial \Omega \},$$

(45)

and, for $i=1,\cdots ,m_c$, we define the subspaces of V

$$V_i=\{v\in V:v=0\mathrm{in}\Omega \backslash {\Omega }_i\}$$

(46)

corresponding to the domain decomposition (43). Furthermore, for any $i=1,\cdots ,m_c$ and $j\in I_i$, we introduce the subspaces of V,

$$V_{ij}=\{v\in V:v=0\mathrm{in}\Omega \backslash {\Omega }_{ij}\}$$

(47)

which are associated with the domain decomposition (39). In view of (42), for a given $i=1,\cdots ,m_c$, the spaces $V_{ij}$, $j\in I_i$, are also subspaces of $V_i$. The spaces V, $V_i$ and $V_{ij}$, $i=1,\cdots ,m_c$, $j\in I_i$, are considered as subspaces of $W^{1,s}$, for some fixed $1<s<\infty$.

We consider problem (4) associated with the above space V and the convex set of two-obstacle type,

$$K=\{v\in V:\phi \le v\le \psi \}$$

(48)

where $\phi ,\psi \in V$. The equivalent Algorithms 1 and 2 represent additive Schwarz methods for the solution of this problem. To apply Theorem 1, in order to prove the convergence of these algorithms, we have to show that Assumptions 1 and 2 hold in the context of this section.

It is clear, from (40) and (42), that the spaces $V_i$, $i=1,\cdots ,m_c$, can be written as the direct sums (7) and, since the convex set is of two-obstacle type, property (8) holds true. Besides that, assuming that functional $F:V\to \mathbb{R}$ is represented by an integral over $\Omega$, using the same Equation (40), we get that (9) holds, too. Therefore, we conclude that Assumption 1 is satisfied.

The verification of Assumption 2 is similar with that in the case of multiplicative algorithms (see [26], for instance). We consider a unity partition ${\theta }_i\in C^1\left(\overline{\Omega }\right)$, $i=1,\dots ,m_c$, associated with the domain decomposition (43) with the property

$$|{\partial }_{x_k}{\theta }_i|\le C/{\delta }_{m_c},\mathrm{for}\mathrm{any}i=1,\cdots ,m_c\mathrm{and}k=1,\cdots ,d$$

(49)

where ${\delta }_{m_c}$ is depends on the number of colors $m_c$ and on the overlap parameter, which will be denoted by $\delta$, of the domain decomposition (43) and C is a generic constant, independent of the mesh parameter and the domain decomposition. For $v,w\in K$, we define

$$v_i=L_h\left({\theta }_i(v-w)\right),i=1,\dots ,m_c,$$

where $L_h$ is the P1-Lagrangian interpolation operator which uses the function values at the nodes of the mesh ${\mathcal{T}}_h$. It is evident that for any $i=1,\dots ,m_c$, $v_i\in V_i$, and, taking into account the definition of K, we have $w+v_i\in K$. Furthermore, we can easily get that ${\sum }_{i=1}^{m_c}{v}_i=v-w$. Using the properties of the interpolation operator, we get (see [26], for instance)

$$\begin{array}{c}\left|\right|v_i{\left|\right|}^s=\left|\right|L_h\left({\theta }_i(v-w)\right){\left|\right|}^s\le C^s\left|\right|{\theta }_i(v-w){\left|\right|}^s\hfill \\ =C^s\left(\left|\right|{\theta }_i{(v-w)\left|\right|}_{L^s(\Omega )}^s+{\left|{\theta }_i(v-w)\right|}_{W^{1,s}(\Omega )}^s\right)\hfill \end{array}$$

(50)

for all $i=1,\dots ,m_c$, where $\left|\right|·\left|\right|$ is the norm of $W^{1,s}(\Omega )$ and $\left|\right|·{\left|\right|}_{L^s(\Omega )}$ and ${|·|}_{W^{1,s}(\Omega )}$ are the norm in $L^s(\Omega )$ and the seminorm of $W^{1,s}(\Omega )$, respectively. Since ${\left({\theta }_i\right)}_{i=1}^{m_c}$ is a unity partition, we have

$$\sum _{i=1}^{m_c}\left|\right|{\theta }_i{(v-w)\left|\right|}_{L^s(\Omega )}^s=\sum _{i=1}^{m_c}{\int }_{\Omega }{\theta }_i^s{|v-w|}^s\le \sum _{i=1}^{m_c}{\int }_{\Omega }{\theta }_i{|v-w|}^s=\left|\right|v-{w\left|\right|}_{L^s(\Omega )}^s$$

(51)

In view of (49), we have

$$\begin{array}{c}{\displaystyle |{\theta }_i{(v-w)|}_{W^{1,s}(\Omega )}^s\le C^s\sum _{j=1}^d\left({\int }_{\Omega }|(v-w)\frac{\partial {\theta }_i}{\partial x_j}{|}^s+{\int }_{\Omega }{\theta }_i^s{\left|\frac{\partial (v-w)}{\partial x_j}\right|}^s\right)}\hfill \\ {\displaystyle \le C^s\left({\int }_{\Omega \backslash [{\theta }_i=cst]}{|v-w|}^s\sum _{j=1}^d|\frac{\partial {\theta }_i}{\partial x_j}{|}^s+{\int }_{\Omega }{\theta }_i\sum _{j=1}^d{\left|\frac{\partial (v-w)}{\partial x_j}\right|}^s\right)}\hfill \\ {\displaystyle \le C^s\left(\frac{1}{{\delta }_{m_c}^s}{\int }_{\Omega \backslash [{\theta }_i=cst]}{|v-w|}^s+{\int }_{\Omega }{\theta }_i\sum _{j=1}^d{\left|\frac{\partial (v-w)}{\partial x_j}\right|}^s\right)}\hfill \end{array}$$

where ${\theta }_i$ has been considered extended with 0 outside ${\Omega }_i$ and $[{\theta }_i=cst]$ is the subset of $\Omega$ where ${\theta }_i$ is constant almost everywhere. Writing

$${\displaystyle {\Omega }_{{\delta }_{m_c}}={\cup }_{i=1}^{m_c}\left({\Omega }_i\backslash [{\theta }_i=cst]\right)}$$

(52)

we get from the above equation

$$\sum _{i=1}^{m_c}{\left|{\theta }_i(v-w)\right|}_{W^{1,s}(\Omega )}^s\le C^s\left(\frac{m_c}{{\delta }_{m_c}^s}\left|\right|v-{w\left|\right|}_{L^s\left({\Omega }_{{\delta }_{m_c}}\right)}^s+{|v-w|}_{W^{1,s}(\Omega )}^s\right)$$

(53)

From (50), (51) and (53), we have

$$\begin{array}{c}{\displaystyle \sum _{i=1}^{m_c}\left|\right|v_i{\left|\right|}^s\le C^s\left[\left(1+\frac{m_c}{{\delta }_{m_c}^s}\frac{\left|\right|v-{w\left|\right|}_{L^s\left({\Omega }_{{\delta }_{m_c}}\right)}^s}{\left|\right|v-{w\left|\right|}_{L^s(\Omega )}^s}\right)\left|\right|v-{w\left|\right|}_{L^s(\Omega )}^s+{|v-w|}_{W^{1,s}(\Omega )}^s\right]}\hfill \\ \le C^s\left(1+\frac{m_c}{{\delta }_{m_c}^s}\frac{\left|\right|v-{w\left|\right|}_{L^s\left({\Omega }_{{\delta }_{m_c}^s}\right)}^s}{\left|\right|v-{w\left|\right|}_{L^s(\Omega )}^s}\right)\left|\right|v-{w\left|\right|}_{W^{1,s}(\Omega )}^s\hfill \end{array}$$

i.e.,

$${\left(\sum _{i=1}^{m_c}\left|\right|v_i{\left|\right|}^s\right)}^{1/s}\le C_{{\Omega }_{{\delta }_{m_c}}\left|\right|v-w\left|\right|}\left|\right|v-{w\left|\right|}_{W^{1,s}(\Omega )}$$

(54)

where

$$C_{{\Omega }_{{\delta }_{m_c}}\left|\right|v-w\left|\right|}=C{\left(1+\frac{m_c}{{\delta }_{m_c}^s}\frac{\left|\right|v-{w\left|\right|}_{L^s\left({\Omega }_{{\delta }_{m_c}}\right)}^s}{\left|\right|v-{w\left|\right|}_{L^s(\Omega )}^s}\right)}^{1/s}$$

(55)

Furthermore, let us write

$$C_0=C{(1+\frac{m_c}{{\delta }_{m_c}^s})}^{1/s}$$

(56)

Remark 4.

1. Since we have ${\Omega }_{{\delta }_{m_c}}={\cup }_{i=1}^{m_c}\left(\Omega \backslash [{\theta }_i=cst]\right)=\Omega \backslash \left({\cap }_{i=1}^{m_c}[{\theta }_i=cst]\right)\subseteq \Omega$ we get

$$C_{{\Omega }_{{\delta }_{m_c}}\left|\right|v-w\left|\right|}\le C_{0}foranyv,w\in V$$

(57)

Therefore, it follows from (54) that the constant $C_0$ in Assumption 2 can be taken as that given in (56). In this way, the estimations of the convergence rates in Theorems 1 and 2 do not depend on the number of the subdomains, but only on the number $m_c$ of the colors and on the overlap parameter δ (since ${\delta }_{m_c}$ depends on this).

2. Even if δ and $m_c$ are fixed, ${\Omega }_{{\delta }_{m_c}}$ given in (52) depends on the number of subdomains of each color, i.e., it depends on the number $m={\sum }_{i=1}^{m_c}{m}_i$ of subdomains of the domain decomposition. Consequently, $C_{{\Omega }_{{\delta }_{m_c}}\left|\right|v-w\left|\right|}$ depends on the actual number m of subdomains even if δ, $m_c$, v and w are fixed.

3. In the proofs of Theorems 1 and 2, Assumption 2 is used only with $v=u^n$ and $w=u$, and therefore, we can use $C_{{\Omega }_{{\delta }_{m_c}}\left|\right|u^n-u\left|\right|}$ instead of $C_0$ in these proofs.

When $p=q=2$, we get

$$F\left(u^{n+1}\right)-F\left(u\right)\le \frac{C_{1,{\Omega }_{{\delta }_{m_c}}\left|\right|u^n-u\left|\right|}}{C_{1,{\Omega }_{{\delta }_{m_c}}\left|\right|u^n-u\left|\right|}+1}\left(F\left(u^n\right)-F\left(u\right)\right)$$

for all $n\ge 0$, where $C_{1,{\Omega }_{{\delta }_{m_c}}\left|\right|u^n-u\left|\right|}$ is obtained by replacing $C_0$ with $C_{{\Omega }_{{\delta }_{m_c}}\left|\right|u^n-u\left|\right|}$ in the expressions of $C_1$ in the statement of the theorems. Consequently, we have

$$F\left(u^n\right)-F\left(u\right)\le {\left(\frac{{max}_{0\le k\le n-1}{C}_{1,{\Omega }_{{\delta }_{m_c}}\left|\right|u^k-u\left|\right|}}{{max}_{0\le k\le n-1}{C}_{1,{\Omega }_{{\delta }_{m_c}}\left|\right|u^k-u\left|\right|}+1}\right)}^n{\left(F\left(u^0\right)-F\left(u\right)\right)}^n$$

(58)

Since $C_{1,{\Omega }_{{\delta }_{m_c}}\left|\right|u^k-u\left|\right|}$ is an increasing function of $C_{{\Omega }_{{\delta }_{m_c}}\left|\right|u^n-u\left|\right|}$, the value ${\max }_{0\le k\le n-1}{C}_{1,{\Omega }_{{\delta }_{m_c}}\left|\right|u^n-u\left|\right|}$ is obtained for ${\max }_{0\le k\le n-1}{C}_{{\Omega }_{{\delta }_{m_c}}\left|\right|u^n-u\left|\right|}$.

Similarly, when $p>q$, if we use the constant $C_{{\Omega }_{{\delta }_{m_c}}\left|\right|u^n-u\left|\right|}$ instead of $C_0$ in the proofs of the two theorems, we get that

$$F\left(u^{n+1}\right)-F\left(u\right)\le {\left[C_{2,{\Omega }_{{\delta }_{m_c}}\left|\right|u^n-u\left|\right|}+{\left(F\left(u^n\right)-F\left(u\right)\right)}^{\frac{q-p}{q-1}}\right]}^{\frac{q-1}{q-p}}$$

for any $n\ge 0$, where $C_{2,{\Omega }_{{\delta }_{m_c}}\left|\right|u^n-u\left|\right|}$ is obtained by replacing $C_0$ with $C_{{\Omega }_{{\delta }_{m_c}}\left|\right|u^n-u\left|\right|}$ in the expressions of $C_2$ in the statement of the theorems. Therefore,

$$F\left(u^n\right)-F\left(u\right)\le \frac{F\left(u^0\right)-F\left(u\right)}{{\left[1+n{min}_{0\le k\le n-1}{C}_{2,{\Omega }_{{\delta }_{m_c}}\left|\right|u^k-u\left|\right|}{\left(F\left(u^0\right)-F\left(u\right)\right)}^{\frac{p-q}{q-1}}\right]}^{\frac{q-1}{p-q}}}$$

(59)

Constant $C_2$ being a decreasing function of $C_0$, it follows that ${\min }_{0\le k\le n-1}{C}_{2,{\Omega }_{{\delta }_{m_c}}\left|\right|u^k-u\left|\right|}$ is obtained for ${\max }_{0\le k\le n-1}{C}_{{\Omega }_{{\delta }_{m_c}}\left|\right|u^k-u\left|\right|}$.

4. In conclusion, if the domain decompositions are colored with the same number $m_c$ of colors and have the same overlap parameter δ, the convergence rates in error estimations (58) and (59) depend on the actual number of subdomains of the domain decomposition but, in view of (57), these rates of convergence are bounded above by the convergence rates given in Theorems 1 and 2 with $C_0$ in (56) which are independent of the actual number of subdomains and depends only on $m_c$ and δ.

4. Numerical Results

Numerical experiments have been performed for the variational inequality

$$u\in K:\langle \nabla \left(u\right),\nabla (v-u)\rangle \ge f{\int }_{\Omega }(v-u)\mathrm{for}\mathrm{any}v\in K,$$

with the convex set

$$K=\{v\in H_0^1(\Omega ):|v\left(p\right)|\le \mathrm{dist}(p,\partial \Omega )\mathrm{for}\mathrm{almost}\mathrm{all}p=(x,y)\in \Omega \}$$

where $\Omega \subset {\mathbb{R}}^2$, and f is a real positive constant. The inequality represents the problem of the elasto-plastic torsion of a cylindrical bar with the section $\Omega$ (see [28], for instance). In our experiments, $\Omega =(0,1)\times (0,1)$ and $f=15.0$. We have triangulated the domain $\Omega$ by constructing first a square grid on it and then, each square element was divided into two rectangular triangles by considering its diagonal from the lower-left corner to the upper right corner. The edges of $\Omega$ have been divided into 100 equal segments and we have used the linear finite elements. The algorithm has been stopped when the relative error between two consecutive approximations, calculated with the norm of $H^1(\Omega )$, has been less than $1.0\times {10}^{-7}$.

To see the plastic and elastic regions of the solution, we have plotted in Figure 1 the difference between the distance to the boundary $\mathrm{dist}(p,\partial \Omega )$ and the value of the obtained finite element solution $u\left(p\right)$ of the problem, $dist(p,\partial \Omega )-u\left(p\right)$, $p\in \Omega$. Consequently, the region with zero values corresponds to the plastic region and the nonzero values of the elastic region represent the distance from the elastic value $u\left(p\right)$ to the plasticity limit $dist(p,\partial \Omega )$.

Now, we introduce some notation regarding the subdomain decomposition. First, let us write $h=0.01$ and $nd=100$. The domain $\Omega$ is covered with identical square subdomains $(md·h)\times (md·h)$ which have an overlap parameter of $nro·h=\delta$ in both directions x and y. Furthermore, if the number and the dimension of the subdomains do not match the dimension of the domain, a subdomain may be of the form $(mdr·h)\times (md·h)$ if it is the last on a line, or $(md·h)\times (mdr·h)$ if it is the last on a column, or $(mdr·h)\times (mdr·h)$ if it lies at the upper right corner of the domain, where $mdr\le md$. Denoting with $nbd$ the number of subdomains in each direction, x and y, we have

$$nd=(nbd-1)(md-nro)+mdr$$

(60)

Furthermore, in the case of our numerical example, if the subdomains can be colored with $2^2=4$ colors, i.e., a subdomain intersects only its neighboring subdomains, then

$$md-nro<md\le 2(md-nro)$$

If the subdomain coloring has $3^2=9$ colors, then

$$2(md-nro)<md\le 3(md-nro)$$

In general, if the subdomains can be colored with $m_c$ colors, then it is easy to verify that

$$(m_c^{1/2}-1)(md-nro)<md\le m_c^{1/2}(md-nro)$$

or,

$$\frac{m{c}^{1/2}}{m{c}^{1/2}-1}nro\le md<\frac{m{c}^{1/2}-1}{m{c}^{1/2}-2}nro$$

(61)

The numerical experiments have been made to verify the theoretical predictions concerning: (1) the choice of the damping parameter, (2) the convergence depending on the overlap parameter and (3) the convergence depending on the number of subdomains.

(1) It is shown in Remark 3 that the best convergence is obtained when ${\varrho }_1=\dots ={\varrho }_{m_c}=\frac{1}{m_c}$. To verify this, we have performed numerical experiments for an example with $md=12$, $nbd=12$ and $nro=4$. Therefore, the number of colors is $mc=2^2$.

First, we give in

Table 1. Number of iterations depending on the various damping parameters associated with the colors.

${\mathit{\varrho }}_1$	${\mathit{\varrho }}_2$	${\mathit{\varrho }}_3$	${\mathit{\varrho }}_4$	Number of Iterations
0.10	0.10	0.35	0.45	451
0.10	0.15	0.25	0.50	406
0.10	0.15	0.40	0.35	396
0.10	0.20	0.30	0.40	377
0.10	0.25	0.20	0.45	383
0.10	0.25	0.35	0.30	365
0.10	0.30	0.25	0.35	366
0.20	0.20	0.55	0.35	292
0.20	0.30	0.20	0.30	288
0.25	0.25	0.25	0.25	275

the number of iterations depending on various values of ${\varrho }_1,\cdots ,{\varrho }_4$. We see that the minimum number of iterations is obtained for ${\varrho }_1=\dots ={\varrho }_4=0.25$, which is consistent with the prediction of Remark 3.

Then, in Figure 2, we have plotted the number of iterations depending on the various values of the damping parameter $\rho ={\rho }_1=\cdots ={\rho }_4$, $\rho =$ 0.005, 0.007, 0.01, 0.05, 0.1, 0.15, 0.2, 0.25, 0.3, 0.35, 0.4 and 0.45. In Remarks 2 and 3, we have showed that the convergence rate decreases as a function of $\rho$. From Figure 2 we see that the numerical results are in agreement with the theoretical ones. Since the solution must theoretically belong to the convex set, we have imposed the condition $\rho \le 1/m_c$ in Algorithms 1 and 2. However, we notice that the algorithm converged for larger values than $0.25$ of $\rho$, but it failed to converge for $\rho >0.45$. A possible explanation would be the fact that during the iteration of Algorithms 1 or 2 we could get $u^{n+1}\in K$ for $\rho >1/mc$.

(2) In Figure 3, we have plotted the number of iterations depending on the size of the overlap parameter $\delta =nro·h$. The domain decomposition contains only one type of subdomains, squares with the size $(0.01·28)\times (0.01·28)$. The experiments have been performed for the size of the overlap parameter of $\delta =1·h,2·h,\cdots ,21·h,22·h$, with $h=0.01$. According with (61), for $\delta =1·h,\cdots ,14·h$, the subdomains can be colored with $2^2$ colors, for $\delta =15·h,\cdots ,18·h$ with $3^2$ colors, for $\delta =19·h,\cdots ,21·h$ with $4^2$ colors and for $\delta =22·h$ with $5^2$ colors.

(a) In Figure 3, (left), we have used damping parameters which correspond to the number of colors of the subdomains of the experiment, $\rho =1/2^2,1/3^2,1/4^2$ and $1/5^2$, respectively. We see that the number of iterations corresponding to a color is greater than that of the previous color. This is in concordance with the error estimation in Remark 3 where the convergence rate is an increasing function of the number $m_c$ of the subdomain colors. Experiments of Figure 3 (right) are performed with a constant value of the damping parameter, $\rho =0.04$. In this case, the error estimation is given in Remark 2 and the convergence rate depends on $m_c$ and also, on the chosen $\rho$. In our case, the convergence rate decreases as $m_c$ increases.

(b) In both cases in Figure 3, with constant damping parameter or not, for a fixed number $m_c$ of colors, the number of iterations decreases when the overlap parameter $\delta$ increases and consequently, the number of iterations corresponding to a fixed $m_c$ is bounded. In view of error estimations in Remarks 2 and 3, $m_c$ being constant, we can conclude that $C_0$ should be a decreasing function of $\delta$. Constants $C_{{\Omega }_{{\delta }_{m_c}}\left|\right|u^n-u\left|\right|}$ in (55) and $C_0$ in (56) are decreasing functions of ${\delta }_{m_c}$ and therefore, for the domain decompositions of the experiments in Figure 3, there exist unity partitions and ${\delta }_{m_c}$ satisfying (49) such that ${\delta }_{m_c}$ increases when $\delta$ increases. We illustrate in Figure 4 and Figure 5 some unity partitions having this property.

In Figure 4, we have plotted sections in the direction of a coordinate axis (the sections in the x and y directions are identical) passing through the center of the functions of a unity partition corresponding to the domain decompositions in Figure 3 having the overlap parameters: $\delta =0.01$ (left) and $\delta =0.14$ (right). These domain decompositions can be colored with $2^2$ colors and we see that ${\delta }_{m_c}=\delta$.

In Figure 5, we have plotted sections in the direction of a coordinate axis passing through the center of the functions of a unity partition corresponding to the domain decomposition in Figure 3 with the overlap parameter: $\delta =0.15$ (left) and $\delta =0.18$ (right). These domain decompositions can be colored with $3^2$ colors and we see that ${\delta }_{m_c}=0.04$ in both cases.

Evidently, other unity partitions can be imagined, but we shall assume that, in general, according with the results of the numerical experiments, the parameter ${\delta }_{m_c}$ defined in (49) depends on the number of colors $m_c$ and, for a fixed color, is an increasing function on the overlap parameter $\delta$, i.e., the number of iterations decreases when the overlap parameter $\delta$ increases.

(3) Experiments in Figure 6, where we plotted the number of iterations depending on the number of subdomains, have been performed to verify the conclusions of Remark 4. As above, in the left plots, the damping parameter is associated with the color of the decomposition and in the right plots the damping parameter is constant, $\rho =0.04$. The overlap parameter has been the same in these experiments, $\delta =0.04$, the domain decompositions contained $2^2,4^2,6^2,\cdots ,{22}^2,{24}^2,{25}^2,{28}^2,{31}^2,\cdots ,{43}^2,{46}^2,{48}^2,$${49}^2,{54}^2,{59}^2,{64}^2,\cdots ,{89}^2,{94}^2$ and ${96}^2$. square subdomains. Obviously, the subdomains have different sizes from one experiment to another. The decompositions whose number of subdomains is between $2^2$ and ${24}^2$ can be colored with $mc=2^2$ colors, those whose number of subdomains is between ${25}^2$ and ${48}^2$ can be colored with $mc=3^2$ colors and decompositions having the number of subdomains between ${49}^2$ and ${96}^2$ can be colored with $mc=5^2$ colors.

(a) As in the case of the $\delta$ variable, we see in Figure 6 that, when the numerical experiments are performed with variable damping parameters (corresponding to the colors of the domain decompositions), the number of iterations corresponding to the colors increases as the number of subdomains $nb{d}^2$ increases, but the number of iterations decreases when the damping parameters associated with the colors have the same value.

(b) Furthermore, from this figure, we see that the number of iterations as a function of the number of the subdomains confirm the conclusions of Remark 4, i.e., by keeping the parameters of the experiments constant, with the exception of the number and the size of the subdomains, the convergence rates are bounded above by the convergence rate of the experiment whose convergence depends only on the number of colors. As in the case of variable $\delta$, we illustrate this by four numerical experiments among those plotted in Figure 6, namely, when the number of subdomains in the direction of x or y is: $nbd=2$, $nbd=24$, $nbd=25$ and $nbd=48$.

In Figure 7, we have plotted sections in the direction of a coordinate axis passing through the center of the functions of the unity partitions corresponding to the domain decomposition for $nbd=2$ and $nbd=24$. These unity partitions satisfy (49) with ${\delta }_{m_c}=0.04$ and the subdomains of the domain the decompositions can be colored with $m_c=2^2$ colors. In Figure 6 we see that the number of iterations increases when the number of subdomains increases between $2^2$ and ${24}^2$. Even if the experiments have the same ${\delta }_{m_c}=0.04$, $|{\Omega }_{{\delta }_{m_c}}|$ increases as the number of subdomains increases and consequently, $C_{{\Omega }_{{\delta }_{m_c}}\left|\right|u^n-u\left|\right|}$ given in (55) increases, i.e., the convergence rate of the experiments increases as the number of the subdomains increases. These experiments are therefore in agreement with the theoretical results.

In Figure 8, we have plotted sections in the direction of a coordinate axis passing through the center of the functions of unity partitions corresponding to the domain decomposition for $nbd=25$ and $nbd=48$. The subdomains of the domain the decompositions having the number of the subdomains between ${25}^2$ and ${48}^2$ can be colored with $m_c=3^2$ colors. In Figure 6, we see that, in the case of these experiments, the number of iterations decreases when the number of subdomains increases. In view of the expression of $C_{{\Omega }_{{\delta }_{m_c}}\left|\right|u^n-u\left|\right|}$ given in (55), this fact is in agreement with the theoretical results because, on the one hand, ${\delta }_{m_c}$ increase from $0.02$ to $0.04$, and on the other hand, $|{\Omega }_{{\delta }_{m_c}}|$ decreases. Therefore $C_{{\Omega }_{{\delta }_{m_c}}}$ decreases, i.e., the convergence rate of the experiments decreases as the number of the subdomains increases.

Finally, let us mention that even if, in general, the Schwarz methods are not scalable (see [1], for instance), in the case of the damped additive one, the number of iterations depends on the number of subdomains but it has an upper bound depending on the minimum number of colors used for the coloring of the subdomains.