On the linear convergence of additive Schwarz methods for the p-Laplacian

Abstract

We consider additive Schwarz methods for boundary value problems involving the |$p$|-Laplacian. While existing theoretical estimates suggest a sublinear convergence rate for these methods, empirical evidence from numerical experiments demonstrates a linear convergence rate. In this paper we narrow the gap between these theoretical and empirical results by presenting a novel convergence analysis. First, we present a new convergence theory for additive Schwarz methods written in terms of a quasi-norm. This quasi-norm exhibits behaviour akin to the Bregman distance of the convex energy functional associated with the problem. Secondly, we provide a quasi-norm version of the Poincaré–Friedrichs inequality, which plays a crucial role in deriving a quasi-norm stable decomposition for a two-level domain decomposition setting. By utilizing these key elements we establish the asymptotic linear convergence of additive Schwarz methods for the |$p$|-Laplacian.

additive Schwarz method, p-Laplacian, linear convergence, quasi-norm, Poincaré–Friedrichs inequality, convergence analysis

1. Introduction

Let |$\varOmega $| be a bounded polygonal domain in |$\mathbb{R}^{2}$| with the Lipschitz boundary |$\partial \varOmega $|⁠. Given |$p \in (1,\infty )$| we consider the following |$p$|-Laplace equation:

$$ \begin{align} - \nabla \cdot \left( |\nabla u |^{p-2} \nabla u \right) = f \quad &\text{ in}\ \varOmega,\nonumber \\ u = 0 \quad &\text{ on } \partial \varOmega, \end{align} $$

(1.1)

where |$f \in L^{p^{*}}(\varOmega )$| with |$p^{*}$| being from the equation |$1/p + 1/p^{*} = 1$|⁠.

The |$p$|-Laplacian is a standard example of nonlinear elliptic problems (Benedikt et al., 2018). Furthermore, it has a number of application areas, including glaciology, non-Newtonian fluids (Shapovalov, 2017), nonlinear diffusion and nonlinear elasticity; see Díaz (1985) and references therein. Thus, there has been extensive research on (1.1), especially for numerical solutions of (1.1). Some important early results can be found in Glowinski & Marrocco (1975); Ciarlet (2002). Finite element methods for the |$p$|-Laplacian were analysed in terms of the quasi-norm in Barrett & Liu (1993, 1994). Further studies on error estimates for the |$p$|-Laplacian in terms of the quasi-norm were conducted in Liu & Yan (2001, 2002); Ebmeyer & Liu (2005); Carstensen et al. (2006). Linear convergence of adaptive finite element methods for (1.1) was shown in Diening & Kreuzer (2008). Numerical homogenization for multiscale |$p$|-Laplacian problems was investigated in Liu et al. (2021).

It is well known that the boundary value problem (1.1) can be formulated in the following weak form (Glowinski & Marrocco, 1975; Ciarlet, 2002): find |$u \in W_{0}^{1,p}(\varOmega )$| such that

$$ \begin{align*}& \int_{\varOmega} |\nabla u|^{p-2} \nabla u \cdot \nabla v \, {\rm{d}}x = \int_{\varOmega} f \, v \,\text{d}x, \quad v \in W^{1,p}_{0}(\varOmega), \end{align*} $$

where |$W_{0}^{1,p} (\varOmega )$| is a usual Sobolev space consisting of the |$L^{p} (\varOmega )$|-functions vanishing on |$\partial \varOmega $| with |$(L^{p} (\varOmega ))^{2}$|-gradient. Equivalently, it is interpreted as the following convex optimization problem:

$$ \begin{align}& \min_{v \in W_{0}^{1,p} (\varOmega)} \left\{ F(v): = \frac{1}{p} \int_{\varOmega} |\nabla v|^{p} \,\text{d}x - \int_{\varOmega} f v \,\text{d}x \right\}.\end{align} $$

(1.2)

That is, one may deal with the convex optimization problem (1.2) to obtain a solution of (1.1). Based on the convex optimization formulation (1.2) multigrid and preconditioned descent methods were proposed in Bermejo & Infante (2000) and Huang et al. (2007), respectively. In particular, the framework of subspace correction methods (Xu, 1992) for (1.2) were considered in Tai & Xu (2002); Park (2020).

This paper is concerned with numerical solutions of boundary value problems involving the |$p$|-Laplacian by additive Schwarz methods. Additive Schwarz methods, also known as parallel subspace correction methods, have been broadly used as efficient numerical solvers for large-scale scientific problems; see Xu (1992); Toselli & Widlund (2005) and references therein for relevant results on linear problems. In additive Schwarz methods the domain of a target problem is decomposed into a union of several subdomains, and optimal local corrections on the subdomains with respect a numerical approximation for the solution are computed in parallel. The numerical approximation for the solution is iteratively updated by collecting all the local corrections. Due to their parallel structures additive Schwarz methods are suitable for massively parallel computation using distributed memory computers. In the past decades there have been a number of results on additive Schwarz methods for large-scale convex optimization problems. The framework of additive Schwarz methods was first considered for convex optimization in Tai & Espedal (1998), and subsequently applied to the |$p$|-Laplacian in Tai & Xu (2002). These methods have since been further investigated in several studies, including Badea (2006, 2019); Park (2020, 2022).

The convergence rate of additive Schwarz methods for the |$p$|-Laplacian problem (1.1) was first analysed in Tai & Xu (2002); the |$\mathcal{O} (n^{-\frac{\underline{p}(\underline{p}-1)}{(\overline{p}-\underline{p})(\overline{p}+\underline{p}-1)}})$| energy convergence of the methods was proven, where |$n$| denotes the number of iterations, |$\underline{p} = \min \{p, 2 \}$|⁠, and |$\overline{p} = \max \{ p, 2 \}$|⁠. Recently, Park (2020) showed that the methods satisfy the improved |$\mathcal{O} (n^{-\frac{\overline{p}(\underline{p}-1)}{\overline{p}-\underline{p}}})$| convergence rate (see Proposition 2.3). The results in both Tai & Xu (2002) and Park (2020) are based on some estimates for the Bregman distance of the energy functional |$F$| in (1.2). Roughly speaking, these estimates are written as

$$ \begin{align}& \mu_{\overline{p}} \| u - v \|_{W^{1,p}(\varOmega)}^{\overline{p}} \leq D_{F} (u,v) \leq L_{\underline{p}} \| u - v \|_{W^{1,p}(\varOmega)}^{\underline{p}}, \quad u, v \in W_{0}^{1,p}(\varOmega),\end{align} $$

(1.3)

where |$\mu _{\overline{p}}$| and |$L_{\underline{p}}$| are positive constants independent of |$u$| and |$v$|⁠, and |$D_{F} (u,v)$| is the Bregman distance of |$F$| defined by

$$ \begin{align}& D_{F} (u,v) = F(u) - F(v) - \left< F^{\prime}(v), u - v \right>, \quad u, v \in W_{0}^{1,p}(\varOmega).\end{align} $$

(1.4)

Here, |$F^{\prime} (v)$| stands for the Frechét derivative of |$F$| at |$v$| given by

$$ \begin{align}& \left< F^{\prime}(v), w \right> = \int_{\varOmega} |\nabla v|^{p-2} \nabla v \cdot \nabla w \,dx - \int_{\varOmega} fw \,dx, \quad w \in W_{0}^{1,p} (\varOmega).\end{align} $$

(1.5)

One may refer to Tai & Xu (2002, Lemma 2.1) and Park (2020, Section 6.1) for details on the estimate (1.3).

While both Tai & Xu (2002) and Park (2020) proved the sublinear convergence of additive Schwarz methods for the |$p$|-Laplacian, it was observed numerically in several works that the methods actually converge linearly; see, e.g., Park (2021, Fig. 2). Indeed, as we will demonstrate in the numerical experiments presented in Section 5 of this paper, additive Schwarz methods for (1.1) exhibit linear convergence empirically under various settings on discretization and domain decomposition. More precisely, each convergence curve of the energy error with respect to the number of iterations seems linear in the |$x$|-linear |$y$|-log scale plot when the number of iterations is sufficiently large, which means that the energy error decays exponentially as the number of iterations increases. This implies that the existing convergence estimates for additive Schwarz methods for the |$p$|-Laplacian may not be optimal.

The main motivation of this paper is to discuss a linear convergence analysis for additive Schwarz methods to solve the |$p$|-Laplacian problem (1.1). As we mentioned above, while the existing theoretical estimates (Tai & Xu, 2002; Park, 2020) for the convergence rate of additive Schwarz methods for the |$p$|-Laplacian are sublinear, the empirical convergence rate observed by numerical experiments is linear. This discrepancy between theoretical and empirical results motivates our work, as we aim to bridge this gap by rigorously proving the asymptotic linear convergence of additive Schwarz methods for the |$p$|-Laplacian.

In (1.3) |$\underline{p}$| and |$\overline{p}$| do not agree if |$p \neq 2$|⁠, so that the lower and upper bounds for |$D_{F} (u,v)$| are expressed in powers of |$\| u - v \|_{W^{1,p}(\varOmega )}$| with different exponents. This discrepancy indicates that a power of norm is not adequate as a tight two-sided approximation for the Bregman distance; whenever we establish a bound for |$D_{F} (u,v)$| in terms of |$\| u - v \|_{W^{1,p}(\varOmega )}$| or vice versa we suffer from a kind of looseness. We claim that the sublinear convergence rates given in the existing works (Tai & Xu, 2002; Park, 2020) are caused by this looseness. To overcome this issue we propose to use the quasi-norm developed in Liu & Yan (2001, 2002); Ebmeyer & Liu (2005); Carstensen et al. (2006), which is relevant to the problem of consideration and approximates the Bregman distance appropriately, and then to derive the convergence estimate in terms of the quasi-norm. This approach is similar to obtain the convergence measure of the iterative method using the energy-like metric relevant to the problem to be solved, as discussed in Lee et al. (2008, 2009). We denote the quasi-norm by |$\| \cdot \|_{(\nabla v)}$| (see (3.1)) and show that

$$ \begin{align}& \mu_{p} \| u-v \|_{(\nabla v)}^{2} \leq D_{F} (u,v) \leq L_{p} \| u - v \|_{(\nabla v)}^{2}, \quad u, v \in W_{0}^{1,p}(\varOmega)\end{align} $$

(1.6)

for some positive constants |$\mu _{p}$| and |$L_{p}$| (see Lemma 3.3), i.e., |$\| u - v \|_{(\nabla v)}^{2}$| approximates |$D_{F} (u,v)$| well up to a multiplicative constant. Meanwhile, we note that the quasi-norm |$\| \cdot \|_{(\nabla v)}$|⁠, along with several alternative versions described in Diening & Růžička (2007), Diening & Kreuzer (2008), do not induce a norm. As a result existing convergence theories for additive Schwarz methods (Tai & Xu, 2002; Park, 2020) cannot directly utilize the estimate (1.6). A novelty in this paper is that, by extending the idea of Park (2020), a new convergence theory for additive Schwarz methods is obtained in terms of the quasi-norm, which utilizes (1.6) to obtain the asymptotic linear convergence rate of additive Schwarz methods for the |$p$|-Laplacian. In our linear convergence analysis a quasi-norm version of the Poincaré–Friedrichs inequality (see Lemmas 3.4 and 3.5) plays a critical role. We validate this asymptotic linear convergence result numerically in Section 5.

The rest of this paper is organized as follows. In Section 2 we present finite element approximations, domain decomposition settings and a two-level additive Schwarz method for the |$p$|-Laplacian problem. An asymptotic linear convergence analysis of the two-level additive Schwarz method is given in Section 3. In Section 4 we present details of the quasi-norm Poincaré–Friedrichs inequality that is used in the convergence analysis of the methods. In Section 5 we provide numerical results of the two-level additive Schwarz method for the |$p$|-Laplacian problem across various settings. Finally, we provide a concluding remark for our paper in Section 6.

2. Additive Schwarz methods

In this section we introduce finite element spaces and domain decomposition settings for the |$p$|-Laplacian problem (1.2). Based on these settings we present a two-level additive Schwarz method for (1.2) and its convergence theory, which explains the asymptotic linear convergence of the algorithm.

In what follows the notation |$A \lesssim B$| means that there exists a constant |$c> 0$| such that |$A \leq c B$|⁠, where |$c$| is independent of the geometric parameters |$H$|⁠, |$h$| and |$\delta $| relying on discretization and domain decomposition. We also write |$A \approx B$| if |$A \lesssim B$| and |$B \lesssim A$|⁠.

2.1 Discretization and domain decomposition

Let |${\mathcal{T}}_{h}$| be a quasi-uniform triangulation of |$\varOmega $| with |$h$| the characteristic element diameter. The collection of continuous and piecewise linear functions on |${\mathcal{T}}_{h}$| vanishing on |$\partial \varOmega $| is denoted by |$V = S_{h} (\varOmega )$|⁠. Clearly, we have |$V \subset W_{0}^{1, \infty } (\varOmega )$|⁠. For continuous functions the nodal interpolation operator |$I_{h}$| onto |$S_{h} (\varOmega )$| is well-defined.

In what follows we consider the following conforming finite element approximation of (1.2) defined on |$V$|⁠:

$$ \begin{align}& \min_{u \in V} F(u).\end{align} $$

(2.1)

A unique solution of (2.1) is denoted by |$u^{*} \in V$|⁠. Convergence properties of (2.1) as |$h \rightarrow 0$| can be found in Barrett & Liu (1993); Ciarlet (2002).

Next, we describe domain decomposition settings for the problem (2.1). We assume that |$\varOmega $| admits another quasi-uniform triangulation |${\mathcal{T}}_{H}$| with |$H$| the characteristic element diameter such that |${\mathcal{T}}_{h}$| is a refinement of |${\mathcal{T}}_{H}$|⁠. A finite element space |$S_{H} (\varOmega )$| is defined in the same manner as |$S_{h} (\varOmega )$|⁠. In the two-level additive Schwarz method for (2.1) |${\mathcal{T}}_{h}$| and |${\mathcal{T}}_{H}$| will play roles of fine and coarse meshes, respectively. Let |$\{ \varOmega _{k} \}_{k=1}^{N}$| be a nonoverlapping domain decomposition of |$\varOmega $| such that each |$\varOmega _{k}$| is the union of several coarse elements in |${\mathcal{T}}_{H}$| and the number of coarse elements consisting of |$\varOmega _{k}$| is uniformly bounded. For each subdomain |$\varOmega _{k}$|⁠, |$1 \leq k \leq N$| we consider an enlarged region |$\varOmega _{k}^{\prime}$| consisting of the elements |$T \in{\mathcal{T}}_{h}$| with |$\operatorname{dist} (T, \varOmega _{k}) \leq \delta $|⁠. Then |$\{ \varOmega _{k}^{\prime}\}_{k=1}^{N}$| forms an overlapping domain decomposition of |$\varOmega $|⁠. We define |$S_{h} (\varOmega _{k} ^{\prime}) \subset W_{0}^{1, \infty }(\varOmega _{k}^{\prime})$| as the piecewise linear finite element space on the |${\mathcal{T}}_{h}|_{\varOmega _{k}^{\prime}}$| with the homogeneous essential boundary condition.

We set

$$ \begin{align*}& V_{0} = S_{H} (\varOmega), \quad V_{k} = S_{h} (\varOmega_{k}^{\prime}), \quad 1 \leq k \leq N. \end{align*} $$

A two-level domain decomposition for |$V$| is given by

$$ \begin{align}& V = \sum_{k=0}^{N} R_{k}^{*} V_{k},\end{align} $$

(2.2)

where |$R_{k}^{*}$|⁠: |$V_{k} \rightarrow V$|⁠, |$1 \leq k \leq N$| is the natural extension-by-zero operator and |$R_{0}^{*}$|⁠: |$V_{0} \rightarrow V$| is the natural interpolation operator. Let |$\{ \theta _{k} \}_{k=1}^{N}$| be the piecewise linear partition of unity for |$\varOmega $| subordinate to the covering |$\{ \varOmega _{k}^{\prime} \}_{k=1}^{N}$| that was presented in Toselli & Widlund (2005, Eq. (3.7)). It is known that |$\{ \theta _{k} \}_{k=1}^{N}$| satisfies the following properties:

$$ \begin{align} \theta_{k} = 0 \quad \text{ on } \varOmega \setminus \varOmega_{k}^{\prime}, \end{align} $$

(2.3a)

$$ \begin{align} \sum_{k=1}^{N} \theta_{k} = 1 \quad \text{ on } \overline{\varOmega}, \end{align} $$

(2.3b)

$$ \begin{align} \| \nabla \theta_{k} \|_{L^{\infty} (\varOmega_{k}^{\prime})} \lesssim \frac{1}{ \delta}, \quad 1 \leq k \leq N. \end{align} $$

(2.3c)

The following lemma summarizes an important result on stable decomposition for the two-level domain decomposition (2.2) (see Tai & Xu (2002, Lemma 4.1)).

Lemma 2.1.

For |$w \in V$|⁠, let |$w_{0} \in V_{0}$| be the |$L^{2} (\varOmega )$|-orthogonal projection of |$w$| onto |$V_{0}$| and let |$w_{k} \in V_{k}$|⁠, |$1 \leq k \leq N$|⁠, such that

$$ \begin{align*}& R_{k}^{*} w_{k} = I_{h} (\theta_{k} (w - R_{0}^{*} w_{0})). \end{align*} $$

For |$s \geq 1$| we have |$w = \sum _{k=0}^{N} R_{k}^{*} w_{k}$| and

$$ \begin{align*}& \sum_{k=0}^{N} | R_{k}^{*} w_{k} |_{W^{1,s} (\varOmega)}^{s} \lesssim \left( 1 + \left( \frac{H}{\delta} \right)^{s-1} \right) | w |_{W^{1,s} (\varOmega)}^{s}. \end{align*} $$

Using the usual colouring technique one can prove that the two-level domain decomposition (2.2) enjoys the strengthened convexity condition (see Park (2020, Assumption 4.2)).

Lemma 2.2.

Let |$N_{c}$| be the minimum number of colours such that |$\{ \varOmega _{k}^{\prime} \}_{k=1}^{N}$| is coloured in a way that the subdomains with the same colour do not intersect with each other, and let |$\tau _{0} = 1/(N_{c} + 1)$|⁠. For any |$v \in V$|⁠, |$w_{k} \in V_{k}$|⁠, |$0 \leq k \leq N$|⁠, and |$\tau \in (0, \tau _{0}]$|⁠, we have

$$ \begin{align*}& (1 - \tau (N+1)) F(v) + \tau \sum_{k=0}^{N} F(v + R_{k}^{*} w_{k} ) \geq F \left( v + \tau \sum_{k=0}^{N} R_{k}^{*} w_{k} \right). \end{align*} $$

Proof.

See Park (2020, Section 5.1). For suitable overlaps we have |$N_{c} = 4$| (Tai & Xu, 2002).

2.2 Two-level additive Schwarz method

The two-level additive Schwarz method for (2.1) based on the space decomposition (2.2) is described in Algorithm 1. It is worth noting that this algorithm has been investigated in several prior works. The algorithm for smooth convex optimization was first considered in Tai & Espedal (1998), and then applied to the |$p$|-Laplacian in Tai & Xu (2002). Later, the framework was generalized to constrained and nonsmooth convex optimization problems in Badea (2006) and Park (2020, 2021), respectively. The constant |$\tau _{0}$| in Algorithm 1 was given in Lemma 2.2.

The following proposition summarizes the sublinear convergence rate of Algorithm 1 analysed in Park (2020, Theorem 6.1). It was discussed in Park (2021, Remark 4.2) that the rate presented in Proposition 2.3 is the sharpest estimate among the existing ones (Tai & Xu, 2002; Badea, 2006; Badea & Krause, 2012; Park, 2020).

Proposition 2.3.

In Algorithm 1, we write |$\zeta _{n} = F (u^{(n)}) - F(u^{*})$| for |$n \geq 0$|⁠. There exist positive constants |$\zeta ^{*}$| and |$c^{*}$|⁠, depending on |$u^{(0)}$|⁠, |$\tau $| and |$H/\delta $|⁠, such that

$$ \begin{align*}& \zeta_{n+1} \leq \begin{cases} \left(1 - \tau \left( 1 - \frac{1}{\underline{p}} \right) \right) \zeta_{n}, & \quad \zeta_{n} \geq \zeta^{*}, \\ \zeta_{n} - c^{*} \zeta_{n}^{\frac{\underline{p} (\overline{p} - 1)}{\overline{p} (\underline{p} - 1)}}, & \quad \zeta_{n} < \zeta^{*}, \end{cases} \end{align*} $$

where |$\underline{p} = \min \{ p, 2\}$| and |$\overline{p} = \max \{p, 2 \}$|⁠. Consequently, we have

$$ \begin{align*}& \zeta_{n} \lesssim \frac{1}{(c^{*} (n+1))^{\frac{\overline{p} (\underline{p} - 1)}{\overline{p} - \underline{p}}}} \end{align*} $$

for sufficiently large |$n \geq 0$|⁠.

Proof.

See Park (2020, Section A.4).

While Proposition 2.3 ensures the sublinear convergence of Algorithm 1, as we will see in Section 5, the actual numerical behaviour indicates linear convergence. This observation motivates us to develop a new convergence theory for Algorithm 1 that can explain the linear convergence. We summarize our main result, the asymptotic linear convergence of Algorithm 1, in Theorem 2.4. The proof of Algorithm 1 will be provided in Section 3. We highlight that Theorem 2.4 stands as the first theoretical result that explains the linear convergence of the additive Schwarz method for the |$p$|-Laplacian.

Theorem 2.4.

If the solution |$u^{*} \in V$| of (2.1) satisfies that |$| \nabla u^{*} |$| does not vanish on |$\varOmega $| then, in Algorithm 1, we have

$$ \begin{align*}& \limsup_{n \rightarrow \infty} \frac{F(u^{(n+1)}) - F(u^{*})}{F(u^{(n)}) - F(u^{*})} \leq 1 - \gamma^{-1}, \end{align*} $$

where |$\gamma $| is a positive constant depending on |$p$|⁠, |$u^{*}$|⁠, |$H$|⁠, |$\delta $| and |$\tau $| such that

$$ \begin{align*}& \gamma \lesssim \left[ 1 + \overline{C}_{p,u^{*}}^{\mathrm{PF}} \left( \frac{H}{\delta} \right)^{p} \right]^{\frac{1}{\min \{p, 2 \} - 1}}, \end{align*} $$

and the constant |$\overline{C}_{p,u^{*}}^{\mathrm{PF}}$| is given in either Lemma 3.4 or Lemma 3.5.

Regarding the condition in Theorem 2.4 that requires the finite element solution |$u^{*}$| to satisfy |$| \nabla u^{*} | \neq 0$| on |$\varOmega $|⁠, we discuss its validity for extreme values of |$p$|⁠, particularly when |$p$| is either very large or close to |$1$|⁠. As we will demonstrate in Section 5, for large |$p$|⁠, the solution may develop a singularity (see Fig. 2(e, f)). Fortunately, this singularity does not violate the condition |$| \nabla u^{*} | \neq 0$|⁠. However, when |$p$| is close to |$1$| the solution may exhibit a flat region, potentially leading to a vanishing gradient (see Fig. 2(a, b)). Consequently, the applicability of Theorem 2.4 to cases near |$p = 1$| may be limited.

Despite the potential limitations in applying Theorem 2.4 to such cases it remains practically relevant, as many real-world applications involving the |$p$|-Laplacian typically utilize moderate values of |$p$|⁠. For instance, in modelling nonlinear Darcy law for fluid flows, as discussed in Benedikt et al. (2018), physically meaningful values for |$p$| are generally greater than |$3/2$|⁠.

We conclude this section by mentioning several acceleration methodologies that can be applied to Algorithm 1. In Park (2021, 2022) acceleration schemes for additive Schwarz methods for convex optimization were proposed. As the energy functional |$F$| is convex these schemes can be directly applied to Algorithm 1 to yield accelerated variants. These accelerated methods show faster convergence behaviours than the vanilla method, while they have essentially the same computational cost per iteration; see Park (2022) for relevant numerical results. We do not deal with the accelerated methods in detail because they are beyond the scope of this paper.

3. Convergence analysis

The main objective of this section is to prove Theorem 2.4, which is the asymptotic linear convergence theorem for the two-level additive Schwarz method for the |$p$|-Laplacian. We begin by presenting some useful properties of the quasi-norm |$\| \cdot \|_{(\nabla v)}$| (Liu & Yan, 2001; Ebmeyer & Liu, 2005), which is defined as

$$ \begin{align}& \| w \|_{(\nabla v)}^{2} = \int_{\varOmega} \left( | \nabla w | + | \nabla v | \right)^{p-2} |\nabla w|^{2} \,dx, \quad v, w \in W^{1,p} (\varOmega).\end{align} $$

(3.1)

Subsequently, we prove Theorem 2.4 by verifying a certain quasi-norm stable decomposition property (Tai & Xu, 2002; Park, 2020).

3.1 Properties of the quasi-norm

The quasi-norm |$\| \cdot \|_{(\nabla v)}$| given in (3.1) satisfies a scaling property in the sense that the |$\| tw \|_{(\nabla v)}$| is bounded by |$\| w \|_{(\nabla v)}$| multiplied by |$t^{\alpha }$| for some |$\alpha \in \mathbb{R}$|⁠, where |$v,w \in W^{1,p} (\varOmega )$| and |$t \in [0,1]$|⁠. Lemma 3.1 summarizes such a property.

Lemma 3.1.

For any |$v,w \in W^{1,p} (\varOmega )$| and |$t \in [0, 1]$|⁠, we have

$$ \begin{align*}& t^{\max \{p, 2\}} \| w \|_{(\nabla v)}^{2} \leq \| tw \|_{(\nabla v)}^{2} \leq t^{\min \{p, 2\}} \| w \|_{(\nabla v)}^{2}. \end{align*} $$

Proof.

Suppose that |$p \in [2, \infty )$|⁠. Since the map |$x \mapsto x^{p-2}$| (⁠|$x \geq 0$|⁠) is increasing we get

$$ \begin{align*} \| tw \|_{(\nabla v)}^{2} &\leq \int_{\varOmega} \left( |\nabla w| + |\nabla v| \right)^{p-2} |t \nabla w|^{2} \,dx = t^{2} \| w \|_{(\nabla v)}^{2}, \\ \| tw \|_{(\nabla v)}^{2} &\geq \int_{\varOmega} \left( t |\nabla w| + t |\nabla v| \right)^{p-2} |t \nabla w|^{2} \,dx = t^{p} \| w \|_{(\nabla v)}^{2}. \end{align*} $$

The case |$p \in (1, 2)$| can be shown by a similar argument using the fact that the map |$x \mapsto x^{p-2}$| (⁠|$x \geq 0$|⁠) is decreasing.

The following lemma states that |$\| u - v \|_{(\nabla v)}$| is bounded by |$\| u - v \|_{(\nabla u)}$| up to a multiplicative constant independent of |$u,v \in W^{1,p} (\varOmega )$|⁠.

Lemma 3.2.

For any |$u,v \in W^{1,p} (\varOmega )$|⁠, we have

$$ \begin{align*}& \| u - v \|_{(\nabla v)}^{2} \leq 2^{|p-2|} \| u - v \|_{(\nabla u)}^{2}. \end{align*} $$

Proof.

Invoking the vector inequality

$$ \begin{align*}& |\xi + \eta| + |\xi| \leq 2 \left( |\xi + \eta| + |\eta| \right), \quad \xi, \eta \in \mathbb{R}^{2} \end{align*} $$

we get

$$ \begin{multline*} \| u - v \|_{(\nabla v)}^{2} = \int_{\varOmega} \left( |\nabla (u-v)| + |\nabla v| \right)^{p-2} |\nabla (u-v)|^{2} \,dx \\ \leq 2^{|p-2|} \int_{\varOmega} \left( |\nabla (v-u)| + |\nabla u| \right)^{p-2} |\nabla (v-u)|^{2} \,dx = 2^{|p-2|} \| u - v \|_{(\nabla u)}^{2}, \end{multline*} $$

which completes the proof.

In Barrett & Liu (1993, 1994) the following vector inequalities were established: there exist two positive constants |$C_{1}$| and |$C_{2}$| such that, for any |$\xi , \eta \in \mathbb{R}^{2}$|⁠, the following hold:

$$ \begin{align} \left| |\xi|^{p-2} \xi - |\eta|^{p-2} \eta \right| &\leq C_{1} |\xi - \eta| \left( |\xi| + |\eta| \right)^{p-2}, \end{align} $$

(3.2a)

$$ \begin{align} \left(|\xi|^{p-2} \xi - |\eta|^{p-2} \eta \right) \cdot \left ( \xi - \eta \right) &\geq C_{2} |\xi - \eta|^{2} \left( |\xi| + |\eta| \right)^{p-2}.\end{align} $$

(3.2b)

Using (3.2) and proceeding similarly to Barrett & Liu (1993, Theorem 2.1) we prove Lemma 3.3, which says that the estimate (1.6) actually holds. Lemma 3.3 will play an important role in proving (3.8); see also Liu et al. (2021, Lemma 2.3).

Lemma 3.3.

There exists positive constants |$\mu _{p}$| and |$L_{p}$| depending on |$p$| such that, for any |$u,v \in W^{1,p} (\varOmega )$|⁠, we have

$$ \begin{align*}& \mu_{p} \| u - v \|_{(\nabla v)}^{2} \leq D_{F} (u,v) \leq L_{p} \| u - v \|_{(\nabla v)}^{2}. \end{align*} $$

Proof.

By the definition of |$D_{F}(u,v)$| given in (1.4) and the fundamental theorem of calculus, we have

$$ \begin{align*}& \begin{split} D_{F} (u,v) &= \int_{0}^{1} \langle F^{\prime}(v + t(u-v)), u-v \rangle \,dt - \langle F^{\prime}(v), u-v \rangle \\ &= \int_{0}^{1} \frac{1}{t} \langle F^{\prime}(v + t(u-v)) - F^{\prime}(v), t(u-v) \rangle \,dt. \end{split} \end{align*} $$

With |$u_{t} = v + t(u-v)$| we see that

$$ \begin{align*}& \begin{split} D_{F}(u,v) &\stackrel{(1.5)}{=} \int_{0}^{1} \frac{1}{t} \int_{\varOmega} \left ( |\nabla u_{t} |^{p-2}\nabla u_{t} - |\nabla v |^{p-2}\nabla v \right )\cdot \nabla (u_{t} - v) \,dx\, dt \\ &\leq \int_{0}^{1} \frac{1}{t} \int_{\varOmega} \left | |\nabla u_{t}|^{p-2}\nabla u_{t} - |\nabla v|^{p-2} \nabla v \right | \left | \nabla (u_{t} - v) \right | \,dx\, dt \\ &\stackrel{(3.2a)}{\lesssim} \int_{0}^{1} \frac{1}{t} \int_{\varOmega} \left ( |\nabla u_{t}| + |\nabla v| \right )^{p-2} \left | \nabla (u_{t} - v) \right |^{2} \, {\rm{d}}x\, dt \\ &= \int_{0}^{1} t \int_{\varOmega} \left ( \left| \nabla \left( v + t(u - v) \right) \right| + |\nabla v| \right )^{p-2} \left | \nabla (u-v) \right |^{2} \, {\rm{d}}x\, dt. \end{split} \end{align*} $$

Now, we invoke the inequality

$$ \begin{align}& \frac{t}{2} \left( |\xi| + |\eta| \right) \leq |\xi + t \eta| + |\xi| \leq 2 \left( |\xi| + |\eta| \right), \quad \xi, \eta \in \mathbb{R}^{2}, \text{} t \in [0,1],\end{align} $$

(3.3)

to obtain that

$$ \begin{align*}& D_{F}(u,v) \lesssim \int_{0}^{1} t \,dt \cdot \int_{\varOmega} \left ( |\nabla v| + |\nabla (u-v)| \right )^{p-2} \left | \nabla (u-v) \right |^{2} \,dx \approx \| u - v \|_{(\nabla v)}^{2}. \end{align*} $$

Hence, we proved |$D_{F} (u,v) \lesssim \| u - v \|_{(\nabla v)}^{2}$|⁠. The inequality |$D_{F} (u,v) \gtrsim \| u - v \|_{(\nabla v)}^{2}$| can be shown in a similar manner using (3.2b) and (3.3).

3.2 Quasi-norm stable decomposition

The core step in the convergence analysis of additive Schwarz methods typically involves verifying a stable decomposition property; see, e.g., Tai & Xu (2002, Eq. (13)) and Park (2020, Assumption 4.1). In this section we derive a quasi-norm stable decomposition property associated with the space decomposition (2.2). A key distinction of the quasi-norm stable decomposition property considered in this section compared with the existing ones is that we use the quasi-norm |$\| \cdot \|_{(\nabla v)}$|⁠, while the existing ones are written in terms of norms. As (1.3) implies a power of norm cannot approximate the Bregman distance of |$F$| by a multiplicative constant if |$p \neq 2$|⁠. Our main insight is that if the quasi-norm can approximate the Bregman distance of |$F$| up to a multiplicative constant, i.e., if it satisfies an estimate of the form (1.6), then we can derive the asymptotic linear convergence of Algorithm 1 using this property.

We recall that two key ingredients for the stable decomposition analysis for linear elliptic problems are the Poincaré–Friedrichs inequality and interpolation error estimate; see Toselli & Widlund (2005, Chapter 3). Therefore, we need to establish these theories with respect to the quasi-norm for the stable decomposition analysis of the |$p$|-Laplacian.

In Lemmas 3.4 and 3.5 we present quasi-norm Poincaré–Friedrichs inequalities for the cases |$p \in (2, \infty )$| and |$p \in (1,2)$|⁠, respectively, that are suitable for our purposes; more general results are proven in Section 4.

Lemma 3.4.

Let |$p \in (2, \infty )$| and |$v \in S_{h} (\varOmega )$|⁠. Assume that every maximal polygonal region |$R \subset \varOmega $| with |$| \nabla v | \neq 0$| satisfies that |$\partial R \cap \partial \varOmega $| contains an element edge. Then there exists a positive constant |$C_{p,v}^{\mathrm{PF}}$| such that

$$ \begin{align*}& \int_{\varOmega} (|w| + |\nabla v|)^{p-2} |w|^{2} \,dx \leq C_{p,v}^{\mathrm{PF}} \| w \|_{(\nabla v)}^{2}, \quad w \in W_{0}^{1,p} (\varOmega). \end{align*} $$

Moreover, if |$| \nabla v |$| does not vanish on |$\varOmega $| then |$C_{p,v}^{\mathrm{PF}}$| has an upper bound |$\overline{C}_{p,v}^{\mathrm{PF}}$| that is continuous at |$v$| in |$S_{h} (\varOmega )$|⁠.

Lemma 3.5.

Let |$p \in (1, 2)$| and |$v \in S_{h} (\varOmega )$|⁠. Assume that every maximal polygonal region |$S \subset \varOmega $| with |$| \nabla v | = 0$| satisfies that |$\partial S \cap \partial \varOmega $| contains an element edge. Then there exists a positive constant |$C_{p,v}^{\mathrm{PF}}$| such that

$$ \begin{align*}& \int_{\varOmega} (|w| + |\nabla v|)^{p-2} | w |^{2} \,dx \leq C_{p,v}^{\mathrm{PF}} \| w \|_{(\nabla v)}^{2}, \quad w \in W_{0}^{1,p} (\varOmega). \end{align*} $$

As stated in Lemmas 3.4 and 3.5 the quasi-norm Poincaré–Friedrichs inequality holds for all choices of |$v$| except for certain exceptional cases, which are detailed in Examples 4.8 and 4.15. Moreover, in most cases, the constant |$C_{p,v}^{\mathrm{PF}}$| demonstrates only a weak dependence on |$v$|⁠. By the quasi-monotone argument (Galvis & Efendiev, 2010; Pechstein & Scheichl, 2013) presented in Section 4 we can ensure that the value of |$C_{p,v}^{\mathrm{PF}}$| is influenced by the local variation of |$| \nabla v |$| only. Consequently, even if |$| \nabla v |$| exhibits significant global variation |$C_{p,v}^{\mathrm{PF}}$| has a moderate value. One may refer to Scheichl et al. (2012) for relevant numerical evidences.

Remark 3.6.

As noted in Lemmas 3.4 and 3.5, the quasi-norm Poincare–Friedrichs inequality may not hold in cases where |$\nabla v$| vanishes in a certain pattern, which makes the convergence analysis of the algorithm challenging. In order to address this issue one may consider regularization techniques as described in Diening et al. (2020); Liu et al. (2021). However, we do not adopt such techniques since they require a delicate convergence analysis for the case when the regularization parameter tends to |$0$|⁠.

Next, we establish a quasi-norm error estimate for the nodal interpolation operator |$I_{h}$| onto the finite element space |$S_{h} (\varOmega )$|⁠, as summarized in Lemma 3.7.

Lemma 3.7.

Let |$w \in W_{0}^{1,p} (\varOmega )$| be a continuous, piecewise quadratic function defined on |${\mathcal{T}}_{h}$| and let |$v \in S_{h} (\varOmega )$|⁠. Then, there exists a positive constant |$C$|⁠, independent of |$w$|⁠, |$v$| and |$h$|⁠, such that

$$ \begin{align*}& \|I_{h} w\|_{(\nabla v)} \leq C \| w \|_{(\nabla v)}. \end{align*} $$

Proof.

Take any |$T \in{\mathcal{T}}_{h}$|⁠. We first prove that |$I_{h}$| achieves the local |$W^{1,1}$|-stability; invoking the inverse inequality (Ern & Guermond, 2021, Lemma 12.1) and the |$H^{1}$|-stability (Toselli & Widlund, 2005, Lemma 3.9) yields

$$ \begin{align}& | I_{h} w |_{W^{1,1}(T)} \lesssim h | I_{h} w |_{H^{1} (T)} \lesssim h | w |_{H^{1} (T)} \lesssim | I_{h} w |_{W^{1,1}(T)}.\end{align} $$

(3.4)

Now, we proceed similarly as in the proof of Diening & Růžička (2007, Theorem 4.5). Recall that |$| \nabla v |$| is constant on |$T$|⁠, say |$a = |\nabla v| \geq 0$|⁠. Since the map |$x \mapsto (x + a)^{p-2} x^{2}$| (⁠|$x \geq 0$|⁠) is increasing and convex, we have

$$ \begin{align} \int_{T} (| \nabla (I_{h} w) | &+ a)^{p-2} | \nabla (I_{h} w)|^{2} \,dx \nonumber \\ &\stackrel{\text{(i)}}{\lesssim} \int_{T} \left( h^{-2} \int_{T} | \nabla (I_{h} w) (y) | \,dy + a \right)^{p-2} \left( h^{-2} \int_{T} |\nabla (I_{h} w)| \,dy \right)^{2} \,dx \nonumber \\ &\stackrel{(3.4)}{\lesssim} h^{2} \left( h^{-2} \int_{T} | \nabla w | \,dy + a \right)^{p-2} \left( h^{-2} \int_{T} | \nabla w | \,dy \right)^{2} \nonumber \\ &\stackrel{\text{(ii)}}{\lesssim} \int_{T} ( | \nabla w | + a )^{p-2} | \nabla w|^{2} \,dy, \end{align} $$

(3.5)

where (i) is due to the inverse inequality (cf. Diening & Růžička (2007, Eq. (2.4)))

$$ \begin{align*}& | u |_{W^{1, \infty} (T)} \lesssim h^{-2} | u |_{W^{1, 1} (T)}, \quad u \in S_{h} (\varOmega), \end{align*} $$

and (ii) is due to the Jensen inequality. By summing (3.5) over all elements |$T \in{\mathcal{T}}_{h}$| we arrive at the conclusion.

Using Lemmas 3.4, 3.5 and 3.7, we obtain the following quasi-norm stable decomposition result.

Lemma 3.8.

Suppose that |$p \in (1, \infty )$| and |$v \in V$| satisfy either the assumptions in Lemma 3.4 or those in Lemma 3.5. Then there exists a positive constant |$C_{p,v}^{\mathrm{SD}}$| depending on |$p$| and |$v$| such that the following holds: for any |$w \in V$| there exist |$w_{k} \in V_{k}$|⁠, |$0 \leq k \leq N$|⁠, such that

$$ \begin{align*} w &= \sum_{k=0}^{N} R_{k}^{*} w_{k}, \\ \sum_{k=0}^{N} D_{F} (v + R_{k}^{*} w_{k}, v) &\leq C_{p, v}^{\mathrm{SD}} \| w \|_{(\nabla v)}^{2}, \\ C_{p,v}^{\mathrm{SD}} &\lesssim 1 + C_{p, v}^{\mathrm{PF}} \left( \frac{H}{\delta} \right)^{p}, \end{align*} $$

where the constant |$C_{p,v}^{\mathrm{PF}}$| was given in either Lemma 3.4 or Lemma 3.5.

Proof.

Throughout this proof let an index |$k$| runs from |$1$| to |$N$|⁠. Take any |$u, v \in V$|⁠, and let |$w = u - v$|⁠. We define |$w_{0} \in V_{0}$| and |$w_{k} \in V_{k}$| as

$$ \begin{align*}& w_{0} = \tilde{I}_{H} w, \quad R_{k}^{*} w_{k} = I_{h} ( \theta_{k} \tilde{w} ), \end{align*} $$

where |$\tilde{I}_{H}$| is the Scott–Zhang quasi-interpolation operator onto |$S_{H} (\varOmega )$| (Scott & Zhang, 1990), and |$\tilde{w} = w - R_{0}^{*} w_{0}$|⁠. It is clear that |$w = R_{0}^{*} w_{0} + \sum _{k=1}^{N} R_{k}^{*} w_{k}$|⁠. Invoking Lemma 3.3 and Diening & Růžička (2007, Theorem 4.5), we have

$$ \begin{align}& D_{F} ( v + R_{0}^{*} w_{0}, v) \lesssim \| \tilde{I}_{H} w \|_{(\nabla v)}^{2} \lesssim \| w \|_{(\nabla v)}^{2}.\end{align} $$

(3.6)

Similarly, Lemmas 3.3 and 3.7 imply

$$ \begin{align}& D_{F} (v + R_{k}^{*} w_{k}, v) \lesssim \sum_{k=1}^{N} \| I_{h} (\theta_{k} \tilde{w}) \|_{(\nabla v)}^{2} \lesssim \sum_{k=1}^{N} \| \theta_{k} \tilde{w} \|_{(\nabla v)}^{2}.\end{align} $$

(3.7)

Note that the map |$x \mapsto (x + a)^{p-2}x^{2}$| (⁠|$x \geq 0$|⁠) is increasing for any |$a \geq 0$|⁠. It follows that

$$ \begin{align} \| \theta_{k} \tilde{w} \|_{(\nabla v)}^{2} & \leq \int_{\varOmega} \left( \theta_{k} |\nabla \tilde{w} | + |\tilde{w}| |\nabla \theta_{k}| + |\nabla v | \right)^{p-2} \left( \theta_{k} |\nabla \tilde{w} | + |\tilde{w}| |\nabla \theta_{k}| \right)^{2} \,dx \nonumber \\ &\stackrel{\text{(i)}}{\lesssim} \int_{\varOmega} \left( \theta_{k} |\nabla \tilde{w}| + |\nabla v| \right)^{p-2} \left( \theta_{k} |\nabla \tilde{w} | \right)^{2} \,dx + \int_{\varOmega} \left( |\tilde{w}| |\nabla \theta_{k}| + |\nabla v| \right)^{p-2} \left( |\tilde{w} | |\nabla \theta_{k}| \right)^{2} \,dx \nonumber \\ &\stackrel{\text{(ii)}}{\lesssim} \| \tilde{w} \|_{(\nabla v)}^{2} + \frac{1}{\delta^{p}} \int_{\varOmega} \left( |\tilde{w}| + |\nabla v| \right)^{p-2} |\tilde{w}|^{2} \,dx \nonumber \\ &\stackrel{\text{(iii)}}{\leq} \left( 1 + \frac{C_{p, v}^{\mathrm{PF}}}{\delta^{p}} \right) \| \tilde{w} \|_{( \nabla v)}^{2}, \end{align} $$

(3.8)

where (i) is because of the triangle inequality-like result presented in Liu & Yan (2001, Lemma 5.4), (ii) is due to (2.3) and (iii) is due to Lemmas 3.4 and 3.5. Meanwhile, we observe that Diening & Růžička (2007, Theorem 4.6) implies

$$ \begin{align}& \| \tilde{w} \|_{(\nabla v)}^{2} = \| w - \tilde{I}_{H} w \|_{(\nabla v)}^{2} \lesssim H^{p} \| w \|_{(\nabla v)}^{2}.\end{align} $$

(3.9)

Combining (3.6), (3.7), (3.8) and (3.9) yields the desired result.

Remark 3.9.

The estimate presented in Lemma 3.8 is not as sharp as the one in the norm-stable decomposition result given in Lemma 2.1. Specifically, in Lemma 3.8, the power of |$H/\delta $| is |$p$|⁠, while in Lemma 2.1, it is |$p-1$|⁠. The norm-stable decomposition achieves the sharp |$(H/\delta )^{p-1}$|-result using a trace theorem-type argument introduced in Dryja & Widlund (1994); see also Toselli & Widlund (2005, Lemma 3.10). Unfortunately, we were unable to make a similar argument in our quasi-norm analysis because the quasi-norm does not have a notion of trace. To obtain a sharp estimate it will be necessary to define an appropriate trace for the quasi-norm, which is remained as a topic for future research.

3.3 Proof of Theorem 2.4

The proof of Theorem 2.4 presented here uses a similar argument to Park (2020). However, due to the nonlinearity of the quasi-norm |$\| \cdot \|_{(\nabla v)}$|⁠, we have to make a careful consideration on dealing with |$\| \cdot \|_{(\nabla v)}$|⁠. In Lemma 3.10 we state the generalized additive Schwarz lemma (see Park (2020, Lemma 4.5)) applied to Algorithm 1 in a form suitable for our purposes.

Lemma 3.10 (generalized additive Schwarz lemma).

Let |$\{ u^{(n)} \}$| be the sequence generated by Algorithm 1. Then it satisfies

$$ \begin{align*}& u^{(n+1)} \in \operatorname{\arg\min}_{u \in V} \left\{ F (u^{(n)}) + \langle F^{\prime}(u^{(n)}), u-u^{(n)} \rangle + M_{\tau} (u, u^{(n)}) \right\}, \end{align*} $$

where the functional |$M_{\tau } \colon V \times V \rightarrow \mathbb{R}$| is given by

$$ \begin{align*}& M_{\tau}(u,v) = \tau \inf \left\{ \sum_{k=0}^{N} D_{F} ( v + R_{k}^{*} w_{k}, v): u-v = \tau \sum_{k=0}^{N} R_{k}^{*} w_{k}, \text{} w_{k} \in V_{k} \right\}, \quad u,v \in V. \end{align*} $$

Proof.

Here, we provide a simple proof that does not rely on convex analysis tools. We define a functional |$Q_{n} \colon V \rightarrow \mathbb{R}$| as

$$ \begin{align*}& Q_{n} (u) = F( u^{(n)} ) + \langle F^{\prime} (u^{(n)}), u - u^{(n)} \rangle + M_{\tau} (u, u^{(n)} ), \quad u \in V. \end{align*} $$

For any |$u \in V$|⁠, invoking (1.4) with some direct computation yields

$$ \begin{align*}& \begin{split} Q_{n} (u) &= (1 - \tau N) F(u^{(n)}) + \tau \inf \left\{ \sum_{k=0}^{N} F (u^{(n)} + R_{k}^{*} w_{k} ): u - u^{(n)} = \tau \sum_{k=0}^{N} R_{k}^{*} w_{k}, \text{} w_{k} \in V_{k} \right\} \\ &\geq (1 - \tau N) F( u^{(n)}) + \tau \sum_{k=0}^{N} \min_{w_{k} \in V_{k}} F( u^{(n)} + R_{k}^{*} w_{k} ) \\ &= (1 - \tau N) F(u^{(n)}) + \tau \sum_{k=0}^{N} F( u^{(n)} + R_{k}^{*} w_{k}^{(n+1)}) \\ &\geq Q_{n} (u^{(n+1)}). \end{split} \end{align*} $$

That is, |$u^{(n+1)}$| minimizes |$Q_{n}$|⁠, which is our desired result.

In the following text, similar to Park (2020, Lemma 4.6), we prove that |$M_{\tau }$| defined in Lemma 3.10 is bounded below by |$D_{F}$| and above by |$\| \cdot \|_{(\nabla v)}^{2}$| up to a multiplicative constant. We note that Lemma 3.11 can be regarded as a variant of the Lipschitz-like/convexity condition discussed in Teboulle (2018).

Lemma 3.11.

Suppose that |$p \in (1, \infty )$| and |$v \in V$| satisfy either the assumptions in Lemma 3.4 or those in Lemma 3.5. Then we have

$$ \begin{align*}& D_{F}(u,v) \leq M_{\tau}(u,v) \leq \frac{C_{p,v}^{\mathrm{SD}}}{\tau^{\max \{p, 2\} - 1}} \| u -v \|_{(\nabla v)}^{2}, \quad u \in V, \end{align*} $$

where |$C_{p, v}^{\mathrm{SD}}$| and |$M_{\tau }$| were defined in Lemmas 3.10 and 3.8, respectively.

Proof.

We define |$\bar{u} \in V$| by the following:

$$ \begin{align*}& \bar{u}-v = \frac{1}{\tau} (u-v). \end{align*} $$

By Lemma 3.8 there exist |$w_{k} \in V_{k}$|⁠, |$0 \leq k \leq N$|⁠, such that

$$ \begin{align*} \bar{u} - v &= \sum_{k=0}^{N} R_{k}^{*} w_{k}, \\ \sum_{k=0}^{N} D_{F} (v + R_{k}^{*} w_{k}, v) &\leq C_{p, v}^{\mathrm{SD}} \| \bar{u} - v \|_{(\nabla v)}^{2}. \end{align*} $$

Note that |$u - v = \tau \sum _{k=0}^{N} R_{k}^{*} w_{k}$|⁠. It follows by Lemma 3.1 that

$$ \begin{align*}& \tau \sum_{k=0}^{N} D_{F} (v + R_{k}^{*} w_{k}, v) \leq \tau C_{p, v}^{\mathrm{SD}} \| \bar{u} - v \|_{(\nabla v)}^{2} \leq \frac{C_{p, v}^{\mathrm{SD}}}{\tau^{\max \{ p, 2 \} - 1}} \ | u - v \|_{(\nabla v)}^{2}. \end{align*} $$

Meanwhile, invoking Lemma 2.2 yields

$$ \begin{align*}& \tau \sum_{k=0}^{N} D_{F}(v + R_{k}^{*} w_{k}, v) = \tau \sum_{k=0}^{N} F(v + R_{k}^{*} w_{k}) - \tau (N+1) F(v) - \langle F^{\prime}(v), u-v \rangle \geq D_{F} (u,v), \end{align*} $$

which completes the proof.

By closely following the argument in (Park, 2020, Appendix A.4) and manipulating |$\| \cdot \|_{(\nabla v)}$|-terms using the properties of |$\| \cdot \|_{(\nabla v)}$| presented in Lemmas 3.1 to 3.3 we establish the following lemma, which provides an estimate for the ratio of two consecutive energy errors in Algorithm 1.

Lemma 3.12.

In Algorithm 1 suppose that |$v = u^{(n)}$| satisfy either the assumptions in Lemma 3.4 or those in Lemma 3.5 for some |$n \geq 0$|⁠. Then we have

$$ \begin{align*}& \frac{F(u^{(n+1)}) - F(u^{*})}{F(u^{(n)}) - F(u^{*})} \leq 1 - \left( 1 - \frac{1}{\underline{p}} \right) \left( \frac{\tau^{\overline{p}-1} \mu_{p}}{\underline{p} 2^{\hat{p}} C_{p, u^{(n)}}^{\mathrm{SD}}} \right)^{\frac{1}{\underline{p}-1}}, \end{align*} $$

where |$\underline{p} = \min \{ p, 2\}$|⁠, |$\overline{p} = \max \{p, 2 \}$|⁠, |$\hat{p} = |p - 2|$| and |$\mu _{p}$| and |$C_{p, u^{(n)}}^{\mathrm{SD}}$| were given in Lemmas 3.3 and 3.8, respectively.

Proof.

For |$t \in [0,1]$| we write

$$ \begin{align}& u_{t} = u^{(n)} + t(u^{*} - u^{(n)}).\end{align} $$

(3.10)

Then we have

$$ \begin{align*}& \begin{split} F(u^{(n+1)}) &= F(u^{(n)}) + \langle F^{\prime}(u^{(n)}), u^{(n+1)} - u^{(n)} \rangle + D_{F} (u^{(n+1)}, u^{(n)}) \\ &\stackrel{\text{(i)}}{\leq} F(u^{(n)}) + \langle F^{\prime}(u^{(n)}), u^{(n+1)} - u^{(n)} \rangle + M_{\tau} (u^{(n+1)}, u^{(n)}) \\ &\stackrel{\text{(ii)}}{=} \min_{u \in V} \left\{ F(u^{(n)}) + \langle F^{\prime}(u^{(n)}), u - u^{(n)} \rangle + M_{\tau} (u, u^{(n)}) \right\} \\ &\stackrel{\text{(i)}}{\leq} \min_{t \geq 0} \left\{ F(u^{(n)}) + \langle F^{\prime}(u^{(n)}), u_{t} - u^{(n)} \rangle + \frac{C_{p, u^{(n)}}^{\mathrm{SD}}}{\tau^{\overline{p} - 1}} \| u_{t} - u^{(n)} \|_{(\nabla u^{(n)})}^{2} \right\} \\\end{split} \end{align*} $$

$$ \begin{align*}& \begin{split} &\stackrel{\text{(iii)}}{\leq} \min_{t \geq 0} \left\{ F(u^{(n)}) + t \langle F^{\prime}(u^{(n)}), u^{*} - u^{(n)} \rangle + \frac{C_{p, u^{(n)}}^{\mathrm{SD}}} {\tau^{\overline{p} - 1}} t^{\underline{p}} \| u^{*} - u^{(n)} \|_{(\nabla u^{(n)})}^{2} \right\} \\ &\stackrel{\text{(iv)}}{\leq} \min_{t \geq 0} \left\{ F(u^{(n)}) + t \langle F^{\prime}(u^{(n)}), u^{*} - u^{(n)} \rangle + \frac{2^{\hat{p}} C_{p, u^{(n)}}^{\mathrm{SD}}} {\tau^{\overline{p} - 1}} t^{\underline{p}} \| u^{(n)} - u^{*} \|_{(\nabla u^{*})}^{2} \right\} \\ &\stackrel{\text{(v)}}{\leq} \min_{t \geq 0} \left\{ F(u^{(n)}) + t \langle F^{\prime}(u^{(n)}), u^{*} - u^{(n)} \rangle + \frac{2^{\hat{p}} C_{p, u^{(n)}}^{\mathrm{SD}}} {\tau^{\overline{p} - 1} \mu_{p}} t^{\underline{p}} \left(F(u^{(n)}) - F(u^{*}) \right) \right\}, \end{split} \end{align*} $$

where (i)–(v) are due to Lemmas 3.11, 3.10, 3.1, 3.2 and 3.3, respectively. By the convexity of |$F$| we get

$$ \begin{align*}& \begin{split} F(u^{(n+1)}) - F(u^{*}) &\leq \min_{t \geq 0} \left\{ 1 - t + \frac{2^{\hat{p}} C_{p, u^{(n)}}^{\mathrm{SD}}}{\tau^{\overline{p} - 1} \mu_{p}} t^{\underline{p}} \right\} \left(F(u^{(n)}) - F(u^{*}) \right) \\ &= \left[ 1 - \left( 1 - \frac{1}{\underline{p}} \right) \left( \frac{\tau^{\overline{p}-1} \mu_{p}}{\underline{p} 2^{\hat{p}} C_{p, u^{(n)}}^{\mathrm{SD}}} \right)^{\frac{1}{\underline{p}-1}} \right] \left(F(u^{(n)}) - F(u^{*}) \right), \end{split} \end{align*} $$

which completes the proof.

Finally, we are ready to present our proof of Theorem 2.4.

Proof of Theorem 2.4.

Suppose that |$| \nabla u^{*} |$| does not vanish on |$\varOmega $|⁠. Take any |$\epsilon> 0$|⁠. By the continuity of |$\overline{C}_{p, u^{*}}^{\mathrm{PF}}$| stated in Lemmas 3.4 and 3.5 we can find a neighbourhood |$B_{\epsilon }$| of |$u^{*}$| in |$V$| such that, for any |$v \in B_{\epsilon }$|⁠, |$| \nabla v |$| does not vanish on |$\varOmega $| and

$$ \begin{align}& \overline{C}_{p, v}^{\mathrm{PF}} \leq \overline{C}_{p, u^{*}}^{\mathrm{PF}} + \epsilon.\end{align} $$

(3.11)

Meanwhile, by Proposition 2.3 and (1.3) (see Park (2020, Section 6.1) for the precise statement of (1.3)) we deduce that the sequence |$\{ u^{(n)} \}$| converges to |$u^{*}$| in |$V$|⁠. Hence, there exists |$n_{0}$| such that, if |$n \geq n_{0}$|⁠, then |$u^{(n)} \in B_{\epsilon }$|⁠. By Lemma 3.8, for |$n \geq n_{0}$|⁠, we have

$$ \begin{align*}& C_{p, u^{(n)}}^{\mathrm{SD}} \lesssim 1 + C_{p, u^{(n)}}^{\mathrm{PF}} \left( \frac{H}{\delta} \right)^{p} {{\leq 1 + \overline{C}_{p, u^{(n)}}^{\mathrm{PF}} \left( \frac{H}{\delta} \right)^{p} \stackrel{(3.11)}{\leq}}} 1 + \left( \overline{C}_{p, u^{*}}^{\mathrm{PF}} + \epsilon \right) \left( \frac{H}{\delta} \right)^{p}. \end{align*} $$

It follows by Lemma 3.12 that

$$ \begin{align*}& \begin{split} \left( 1 - \frac{F(u^{(n+1)}) - F(u^{*})}{F(u^{(n)}) - F(u^{*})} \right)^{-1} &\leq \frac{\underline{p}}{\underline{p} - 1} \left( \frac{\underline{p} 2^{\hat{p}} C_{p, u^{(n)}}^{\mathrm{SD}}}{\tau^{\overline{p} - 1} \mu_{p}} \right)^{\frac{1}{\underline{p} - 1}} \\ &\lesssim \frac{\underline{p}}{\underline{p} - 1} \left( \frac{\underline{p} 2^{\hat{p}}}{\tau^{\overline{p} - 1} \mu_{p}} \right)^{\frac{1}{\underline{p} - 1}}\left[ 1 + \left( \overline{C}_{p, u^{*}}^{\mathrm{PF}} + \epsilon \right) \left( \frac{H}{\delta} \right)^{p} \right]^{\frac{1}{\underline{p} - 1}}. \end{split} \end{align*} $$

Since |$\epsilon $| is arbitrary we obtain the desired result with

$$ \begin{align*}& \gamma = \frac{\underline{p}}{\underline{p} - 1} \left( \frac{\underline{p} 2^{\hat{p}}}{\tau^{\overline{p} - 1} \mu_{p}} \right)^{\frac{1}{\underline{p} - 1}}\left[ 1 + \overline{C}_{p, u^{*}}^{\mathrm{PF}} \left( \frac{H}{\delta} \right)^{p} \right]^{\frac{1}{\underline{p} - 1}}. \end{align*} $$

This completes the proof.

Remark 3.13.

As stated in Lemma 3.3 the squared quasi-norm |$\| u - v \|_{(\nabla v)}^{2}$| is equivalent to the Bregman distance |$D_{F} (u, v)$| up to multiplicative constants for |$u, v \in W^{1,p} (\varOmega )$|⁠. This equivalence allows us to perform the convergence analysis presented in this section using the Bregman distance instead of the quasi-norm. Indeed, the Bregman distance is frequently utilized in the analysis of convex optimization algorithms; see, e.g., Bauschke et al. (2017); Teboulle (2018). Nevertheless, we opted to present the convergence analysis of Algorithm 1 in terms of the quasi-norm in this paper, because using the quasi-norm has an advantage that we can simplify our proof by borrowing some useful techniques regarding the quasi-norm introduced in from the existing literature (Liu & Yan, 2001, 2002; Ebmeyer & Liu, 2005; Carstensen et al., 2006).

4. Quasi-norm Poincaré–Friedrichs inequality

This section is devoted to the proofs of Lemmas 3.4 and 3.5. Namely, we deal with quasi-norm Poincaré–Friedrichs inequalities of the form

$$ \begin{align}& \int_{\varOmega} (|w| + |\nabla v|)^{p-2} |w|^{2} \,dx \leq C \| w \|_{(\nabla v)}^{2},\end{align} $$

(4.1)

where |$p \in (1, \infty )$| with |$p \neq 2$|⁠. Unfortunately, the inequality (4.1) does not hold for every |$v, w \in W_{0}^{1,p} (\varOmega )$|⁠; see Examples 4.8 and 4.15. Based on a quasi-monotonicity argument introduced in Pechstein & Scheichl (2013) we characterize the conditions on |$v$| such that the inequality (4.1) holds and provide a precise estimate for the Poincaré–Friedrichs constant |$C$| in (4.1). Throughout this section let |$W_{\varGamma }^{1,p} (\varOmega )$| denote the collection of all |$W^{1,p} (\varOmega )$|-functions vanishing on |$\varGamma \subset \partial \varOmega $|⁠. In addition we use the conventions |$0/0 = 1$| and |$1/0 = \infty $|⁠.

Lemma 4.1.

Let |$\varGamma \subset \partial \varOmega $| have nonvanishing one-dimensional measure. Then, there exists a positive constant |$C$| such that

$$ \begin{align*}& \int_{\varOmega} ( |w | + a )^{p-2} |w|^{2} \,dx \leq C \int_{\varOmega} (| \nabla w | + a )^{p-2} |\nabla w|^{2} \,dx, \quad w \in W_{\varGamma}^{1,p} (\varOmega), \text{} a \geq 0. \end{align*} $$

For a non-negative function |$\alpha \in L^{\infty } (\varOmega )$| and a partition |$\mathcal{Y} = \{ Y \}_{l=1}^{m}$| of |$\varOmega $| consisting of nonoverlapping polygonal regions we define two non-negative functions |$\underline{\alpha }_{\mathcal{Y}\,}, \overline{\alpha }^{\mathcal{Y}\,} \in L^{\infty } (\varOmega )$| as follows:

$$ \begin{align*}& \underline{\alpha}_{\mathcal{Y}} (x) = \mathop{\rm ess\, inf}\limits_{Y_{l}} \alpha, \quad \overline{\alpha}^{\mathcal{Y}} (x) = \mathop{\rm ess\, sup}\limits_{Y_{l}} \alpha, \quad x \in Y_{l}, \text{} 1 \leq l \leq m. \end{align*} $$

In the following text we address the cases |$p \in (2, \infty )$| and |$p \in (1, 2)$| separately. We first focus on the case |$p \in (2, \infty )$|⁠. In Definition 4.2 we introduce the concept of quasi-monotone increase. We note that relevant notions were explored in Galvis & Efendiev (2010); Pechstein & Scheichl (2013).

Definition 4.2.

Let |$\alpha \in L^{\infty } (\varOmega )$| be a non-negative function on |$\varOmega $|⁠, and let |$\mathcal{Y}\, = \{ Y \}_{l=1}^{m}$| denote a partition of |$\varOmega $| into nonoverlapping polygonal regions.

We say that the region |$P_ {l_{1}, l_{s}} = ( \overline{Y}_{l_{1}} \cup \dots \cup \overline{Y}_{l_{s}} )^{\circ }$|⁠, |$1 \leq l_{1}, \dots , l_{s} \leq m$|⁠, is a quasi-monotonically increasing path from |$Y_{l_{1}}$| to |$Y_{l_{s}}$| with respect to |$\alpha $| if the following two conditions hold:
- For each |$1 \leq i \leq s-1$| the regions |$\overline{Y}_{l_{i}}$| and |$\overline{Y}_{l_{i+1}}$| share a common edge.
- |$\underline{\alpha }_{\mathcal{Y}\,} (Y_{l_{1}}) \leq \dots \leq \underline{\alpha }_{\mathcal{Y}\,} (Y_{l_{s}})$|⁠.
We say that |$\alpha $| is |$\partial \varOmega $|-quasi-monotonically increasing on |$\mathcal{Y}\,\,$| if, for any |$1 \leq l \leq m$|⁠, there exist an index |$l^{*}$| and a quasi-monotonically increasing path |$P_{l, l^{*}}$| from |$Y_{l}$| to |$Y_{l^{*}}$|⁠, such that |$\partial Y_{l^{*}} \cap \partial \varOmega $| has nonvanishing one-dimensional measure.

By a similar argument, as in the proof of Pechstein & Scheichl (2013, Theorem 2.9), we prove the following lemma.

Lemma 4.3.

Assume that |$p \in (2, \infty )$|⁠. Let |$\alpha \in L^{\infty } (\varOmega )$| be a non-negative function on |$\varOmega $|⁠, and let |$\mathcal{Y}\, = \{ Y \}_{l=1}^{m}$| denote a partition of |$\varOmega $| into nonoverlapping polygonal regions. If |$\alpha $| is |$\partial \varOmega $|-quasi-monotonically increasing on |$\mathcal{Y}\,$| then, for each |$1 \leq l \leq m$|⁠, there exists a positive constant |$c_{p, \mathcal{Y}\,, l}$|⁠, independent of |$\alpha $|⁠, such that

$$ \begin{align*}& \int_{Y_{l}} ( |w| + \alpha )^{p-2} |w|^{2} \,dx \leq c_{p, \mathcal{Y}, l} \left( \frac{\overline{\alpha}^{\mathcal{Y}} (Y_{l})}{\underline{\alpha}_{\mathcal{Y}} (Y_{l})} \right)^{p-2} \int_{P_{l, l^{*}}} ( | \nabla w| + \alpha )^{p-2} |\nabla w|^{2} \,dx, \quad w \in W_{0}^{1,p} (\varOmega), \end{align*} $$

where the region |$P_{l,l^{*}}$| was given in Definition 4.2.

Proof.

Note that the map |$x \mapsto x^{p-2}$| (⁠|$x \geq 0$|⁠) is increasing. Take any |$l$| such that |$1 \leq l \leq m$|⁠. Since |$\alpha \leq \overline{\alpha }^{\mathcal{Y}\,} (Y_{l})$| on |$Y_{l}$| and |$Y_{l} \subset P_{l, l^{*}}$| we get

$$ \begin{align} \int_{Y_{l}} (|w| + \alpha)^{p-2} |w|^{2} \,dx &\leq \int_{Y_{l}} \left( |w| + \overline{\alpha}^{\mathcal{Y}} (Y_{l}) \right)^{p-2} |w|^{2} \,dx \nonumber \\ &\leq \int_{P_{l, l^{*}}} \left( |w| + \overline{\alpha}^{\mathcal{Y}} (Y_{l}) \right)^{p-2} |w|^{2} \,dx. \end{align} $$

(4.2)

Since |$\partial P_{l, l^{*}} \cap \partial \varOmega $| has nonvanishing one-dimensional measure Lemma 4.1 ensures that we have a positive constant |$c_{p, \mathcal{Y}\,, l}$|⁠, independent of |$w$| and |$\alpha $|⁠, such that

$$ \begin{align}& \int_{P_{l, l^{*}}} \left( |w| + \overline{\alpha}^{\mathcal{Y}} (Y_{l}) \right)^{p-2} |w|^{2} \,dx \leq c_{p, \mathcal{Y}, l} \int_{P_{l, l^{*}}} \left( |\nabla w| + \overline{\alpha}^{\mathcal{Y}} (Y_{l}) \right)^{p-2} |\nabla w|^{2} \,dx.\end{align} $$

(4.3)

Invoking the inequality

$$ \begin{align*}& \frac{a + \overline{\alpha}^{\mathcal{Y}} (Y_{l})}{a + \underline{\alpha}_{\mathcal{Y}} (Y_{l})} \leq \frac{\overline{\alpha}^{\mathcal{Y}} (Y_{l})}{\underline{\alpha}_{\mathcal{Y}} (Y_{l})}, \quad a \geq 0, \end{align*} $$

we have

$$ \begin{align} \int_{P_{l, l^{*}}} &\left( |\nabla w| + \overline{\alpha}^{\mathcal{Y}} (Y_{l}) \right)^{p-2} |\nabla w|^{2} \,dx \nonumber \\ &\leq \left( \frac{\overline{\alpha}^{\mathcal{Y}} (Y_{l})}{\underline{\alpha}_{\mathcal{Y}} (Y_{l})} \right)^{p-2} \int_{P_{l, l^{*}}} \left( |\nabla w| + \underline{\alpha}_{\mathcal{Y}} (Y_{l}) \right)^{p-2} |\nabla w|^{2} \,dx \nonumber \\ &\leq \left( \frac{\overline{\alpha}^{\mathcal{Y}} (Y_{l})}{\underline{\alpha}_{\mathcal{Y}} (Y_{l})} \right)^{p-2} \int_{P_{l, l^{*}}} \left( |\nabla w| + \underline{\alpha}_{\mathcal{Y}} \right)^{p-2} |\nabla w|^{2} \,dx \nonumber \\ &\leq \left( \frac{\overline{\alpha}^{\mathcal{Y}} (Y_{l})}{\underline{\alpha}_{\mathcal{Y}} (Y_{l})} \right)^{p-2} \int_{P_{l, l^{*}}} \left( |\nabla w| + \alpha \right)^{p-2} |\nabla w|^{2} \,dx, \end{align} $$

(4.4)

where the penultimate inequality is because |$\underline{\alpha }_{\mathcal{Y}\,}$| increases along |$P_{l,l^{*}}$|⁠. Combining Lemmas 4.2, 4.3 and 4.4 yields the desired result.

Due to Lemma 4.3 we are able to define the quasi-monotone increase constant |$C_{p, \alpha }^{\mathrm{QM}}$| for |$p \in (2, \infty )$|⁠, as presented in Definition 4.4.

Definition 4.4.

Assume that |$p \in (2, \infty )$|⁠. Let |$\alpha \in L^{\infty } (\varOmega )$| be a non-negative function on |$\varOmega $|⁠. The quasi-monotone increase constant |$C_{p, \alpha }^{\mathrm{QM}} \in [0, \infty ]$| is defined by

$$ \begin{align*}& C_{p, \alpha}^{\mathrm{QM}} = \inf_{\mathcal{Y}} \left\{ \max_{1 \leq l \leq m} \left( \frac{\overline{\alpha}^{\mathcal{Y}} (Y_{l})}{\underline{\alpha}_{\mathcal{Y}} (Y_{l})} \right)^{p-2} \cdot \sum_{l=1}^{m} c_{p, \mathcal{Y}, l} \right\}, \end{align*} $$

where the constants |$c_{p, \mathcal{Y}\,, l}$|’s were given in Lemma 4.3 and the infimum is taken over every nonoverlapping polygonal partition |$\mathcal{Y}\, = \{ Y_{l} \}_{l=1}^{m}$| of |$\varOmega $| such that |$\alpha $| is |$\partial \varOmega $|-quasi-monotonically increasing on |$\mathcal{Y}\,$|⁠.

Note that the infimum in Definition 4.2 is well-defined because |$\alpha $| is |$\partial \varOmega $|-quasi-monotonically increasing on the trivial partition |$\{ \varOmega \}$|⁠. In terms of the quasi-monotone increase constant |$C_{p, \alpha }^{\mathrm{QM}}$| we present a quasi-norm Poincaré–Friedrichs inequality for |$p \in (2, \infty )$| in Theorem 4.5.

Theorem 4.5.

Assume that |$p \in (2, \infty )$|⁠. Let |$\alpha \in L^{\infty } (\varOmega )$| be a non-negative function on |$\varOmega $|⁠. Then we have

$$ \begin{align*}& \int_{\varOmega} (|w| + \alpha )^{p-2} |w|^{2} \,dx \leq C_{p, \alpha}^{\mathrm{QM}} \int_{\varOmega} (|\nabla w| + \alpha)^{p-2} |\nabla w|^{2} \,dx, \quad w \in W_{0}^{1,p} (\varOmega), \end{align*} $$

where the quasi-monotone increase constant |$C_{p, \alpha }^{\mathrm{QM}} \in [0, \infty ]$| was given in Definition 4.4.

Proof.

We fix any nonoverlapping polygonal partition |$\mathcal{Y}\,$| such that |$\alpha $| is |$\partial \varOmega $|-quasi-monotonically increasing on |$\mathcal{Y}\,$|⁠. By Lemma 4.3, we have

$$ \begin{align} \int_{Y_{l}} (|w| + \alpha)^{p-2} |w|^{2} \,dx &\leq c_{p, \mathcal{Y}, l} \left( \frac{\overline{\alpha}^{\mathcal{Y}} (Y_{l})}{\underline{\alpha}_{\mathcal{Y}} (Y_{l})} \right)^{p-2} \int_{P_{l, l^{*}}} ( | \nabla w| + \alpha )^{p-2} |\nabla w|^{2} \,dx \nonumber \\ &\leq c_{p, \mathcal{Y}, l} \max_{1 \leq l \leq m} \left( \frac{\overline{\alpha}^{\mathcal{Y}} (Y_{l})}{\underline{\alpha}_{\mathcal{Y}} (Y_{l})} \right)^{p-2} \int_{\varOmega} ( | \nabla w| + \alpha )^{p-2} |\nabla w|^{2} \,dx. \end{align} $$

(4.5)

Summing (4.5) over all |$l$| followed by taking the infimum over all |$\mathcal{Y}\,$| completes the proof.

Let |$W_{h} (\varOmega )$| be the space of piecewise constant functions on the triangulation |${\mathcal{T}}_{h}$|⁠. Under an additional assumption that |$\alpha \in W_{h} (\varOmega )$| we can characterize the condition when the quasi-monotone increase constant |$C_{p, \alpha }^{\mathrm{QM}}$| is finite.

Lemma 4.6.

Assume that |$p \in (2, \infty )$|⁠. Let |$\alpha \in W_{h} (\varOmega )$| be a non-negative piecewise constant function on |${\mathcal{T}}_{h}$|⁠. Then, the quasi-monotone increase constant |$C_{p, \alpha }^{\mathrm{QM}}$| is finite if and only if every maximal polygonal region |$R \subset \varOmega $| with |$\alpha> 0$| satisfies that |$\partial R \cap \partial \varOmega $| has nonvanishing one-dimensional measure.

Proof.

We first assume that every maximal polygonal region |$R \subset \varOmega $| with |$\alpha> 0$| satisfies that |$\partial R \cap \partial \varOmega $| has nonvanishing one-dimensional measure. We consider the partition |$\mathcal{Y}\,^{*}$| of |$\varOmega $| consisting of all maximal polygonal regions |$\{ R_{i} \}$| with |$\alpha> 0$| and all maximal polygonal regions |$\{ S_{i} \}$| with |$\alpha = 0$|⁠. It is obvious that each |$R_{i}$| forms a quasi-monotonically increasing path with respect to |$\alpha $| from |$R_{i}$| to itself. For each |$S_{i}$|⁠, if |$\partial S_{i} \cap \partial \varOmega $| has nonvanishing one-dimensional measure, then |$S_{i}$| forms a quasi-monotonically increasing path with respect to |$\alpha $| from |$S_{i}$| to itself. Otherwise, the maximality of |$S_{i}$| implies there exists some |$R_{j}$| such that |$\overline{S}_{i}$| and |$\overline{R}_{j}$| share a common edge. Then we readily deduce that |$(\overline{S}_{i} \cup \overline{R}_{j})^{\circ }$| forms a quasi-monotonically increasing path with respect to |$\alpha $| from |$S_{i}$| to |$R_{j}$|⁠. Meanwhile, since |$\alpha $| is piecewise constant, we have

$$ \begin{align*}& \frac{\overline{\alpha}^{\mathcal{Y}^{*}} (R_{i})}{\underline{\alpha}_{\mathcal{Y}^{*}} (R_{i})} < \infty, \quad \frac{\overline{\alpha}^{\mathcal{Y}^{*}} (S_{i})}{\underline{\alpha}_{\mathcal{Y}^{*}} (S_{i})} = \frac{0}{0} = 1, \end{align*} $$

for every |$R_{i}$| and |$S_{i}$|⁠. Hence, we conclude that |$C_{p, \alpha }^{\mathrm{QM}} < \infty $|⁠.

Next, we suppose that there exists a maximal polygonal region |$R^{*} \subset \varOmega $| with |$\alpha> 0$| such that |$\partial R^{*} \cap \partial \varOmega $| is a null set. That is, every edge of |$R^{*}$| is shared with a region with |$\alpha = 0$|⁠. Take any nonoverlapping polygonal partition |$\mathcal{Y}\,$| of |$\varOmega $|⁠. If |$\mathcal{Y}\,$| has an element |$Y$| such that |$Y \subset R^{*}$| then it is impossible to find any quasi-monotonically increasing path with respect to |$\alpha $| starting from |$Y$|⁠, since any such path would necessarily have to pass through a region where |$\alpha = 0$|⁠. Otherwise, |$\mathcal{Y}\,$| must contain an element |$Y$| such that both |$Y \cap R^{*}$| and |$Y \setminus R^{*}$| are nontrivial, which implies that

$$ \begin{align*}& \frac{\overline{\alpha}^{\mathcal{Y}} (Y)}{\underline{\alpha}_{\mathcal{Y}} (Y)} = \infty. \end{align*} $$

Hence, we conclude that |$C_{p, \alpha }^{\mathrm{QM}} = \infty $|⁠, which completes the proof.

Combining Theorem 4.5 and Lemma 4.6 yields Corollary 4.7, in which Lemma 3.4 is a particular case |$\alpha = |\nabla v |$| of this result.

Corollary 4.7.

Assume that |$p \in (2, \infty )$|⁠. Let |$\alpha \in W_{h} (\varOmega )$| be a non-negative piecewise constant function on |${\mathcal{T}}_{h}$|⁠. If every maximal polygonal region |$R \subset \varOmega $| with |$\alpha> 0$| satisfies that |$\partial R \cap \partial \varOmega $| has nonvanishing one-dimensional measure, then we have

where |$C_{p, \alpha }^{\mathrm{QM}}$| is a finite constant given in Definition 4.4. Moreover, if |$\alpha $| does not vanish on |$\varOmega $|⁠, then |$C_{p,\alpha }^{\mathrm{QM}}$| has an upper bound |$\overline{C}_{p,\alpha }^{\mathrm{QM}}$| that is continuous at |$\alpha $| in |$W_{h} (\varOmega )$|⁠.

Proof.

It suffices to find a continuous upper bound of |$C_{p, \alpha }^{\mathrm{QM}}$| under the given condition. We assume that |$\alpha $| does not vanish on |$\varOmega $|⁠. By Definition 4.4, we have

$$ \begin{align*}& C_{p, \alpha}^{\mathrm{QM}} \leq \frac{\max_{\varOmega} \alpha}{\min_{\varOmega} \alpha} c_{p, \{ \varOmega \}, 1} =: \overline{C}_{p, \alpha}^{\mathrm{QM}}, \end{align*} $$

where the inequality is obtained by taking |$\mathcal{Y}\, = \{ \varOmega \} = \{ Y_{1} \} $| in Definition 4.4. As |$\alpha> 0$| in |$\varOmega $| it is clear that |$\overline{C}_{p, \alpha }^{\mathrm{QM}}$| is continuous at |$\alpha $| in |$W_{h} (\varOmega )$|⁠, which completes the proof.

We show that, under the condition presented in Lemma 4.6 for the quasi-monotone increase constant |$C_{p, \alpha }$| to be infinite, the quasi-norm Poincaré–Friedrichs inequality of the form (4.1) is not valid. For simplicity we provide a counterexample in one-dimension; we note that the construction can be generalized to higher dimensions.

Example 4.8.

Let |$p \in (2, \infty )$| and |$\varOmega = (0, 1) \subset \mathbb{R}$|⁠. We define |$w \in W_{0}^{1,p} (\varOmega )$| and |$\alpha \in L^{\infty } (\varOmega )$| as

$$ \begin{align*}& w(x) = \begin{cases} 3x, & \text{ if} 0 < x < \frac{1}{3}, \\ 1 & \text{ if} \frac{1}{3} \leq x < \frac{2}{3}, \\ -3x+3, & \text{ if} \frac{2}{3} \leq x < 1, \end{cases} \quad \alpha (x) = \begin{cases} 1, & \text{ if} \frac{1}{3} \leq x < \frac{2}{3}, \\ 0, & \text{ otherwise.} \end{cases} \quad \end{align*} $$

We observe that the quasi-monotone increase constant |$C_{p, \alpha }$| becomes infinite because the interval |$(1/3, 2/3)$| where |$\alpha $| is nonzero does not touch |$\partial \varOmega $|⁠. For any |$\epsilon> 0$| direct calculation yields

$$ \begin{align*}& \frac{\int_{0}^{1} ( |(\epsilon w)^{\prime}| + \alpha)^{p-2} |(\epsilon w)^{\prime}|^{2} \,dx}{\int_{0}^{1} (|\epsilon w| + \alpha)^{p-2} |\epsilon w|^{2} \,dx} \rightarrow 0 \quad \text{ as} \quad \epsilon \rightarrow 0^{+}, \end{align*} $$

which implies that (4.1) does not hold.

Definition 4.9.

We say that the region |$P_{l_{1}, l_{s}} = ( \overline{Y}_{l_{1}} \cup \dots \cup \overline{Y}_{l_{s}} )^{\circ }$|⁠, |$1 \leq l_{1}, \dots , l_{s} \leq m$|⁠, is a quasi-monotonically decreasing path from |$Y_{l_{1}}$| to |$Y_{l_{s}}$| with respect to |$\alpha $| if the following two conditions hold:
- For each |$1 \leq i \leq s-1$| the regions |$\overline{Y}_{l_{i}}$| and |$\overline{Y}_{l_{i+1}}$| share a common edge.
- |$\overline{\alpha }_{\mathcal{Y}\,} (Y_{l_{1}}) \geq \dots \geq \overline{\alpha }_{\mathcal{Y}\,} (Y_{l_{s}})$|⁠.
We say that |$\alpha $| is |$\partial \varOmega $|-quasi-monotonically decreasing on |$\mathcal{Y}\,$| if, for any |$1 \leq l \leq m$|⁠, there exist an index |$l^{*}$| and a quasi-monotonically decreasing path |$P_{l, l^{*}}$| from |$Y_{l}$| to |$Y_{l^{*}}$|⁠, such that |$\partial Y_{l^{*}} \cap \partial \varOmega $| has nonvanishing one-dimensional measure.

One can prove the following lemma using the fact that the map |$x \mapsto x^{p-2}$| (⁠|$x \geq 0$|⁠) is decreasing and by following a similar argument to that used in the proof of Lemma 4.3.

Lemma 4.10.

Assume that |$p \in (1, 2)$|⁠. Let |$\alpha \in L^{\infty } (\varOmega )$| be a non-negative function on |$\varOmega $|⁠, and let |$\mathcal{Y}\, = \{ Y \}_{l=1}^{m}$| denote a partition of |$\varOmega $| into nonoverlapping polygonal regions. If |$\alpha $| is |$\partial \varOmega $|-quasi-monotonically decreasing on |$\mathcal{Y}\,$| then, for each |$1 \leq l \leq m$|⁠, there exists a positive constant |$c_{p, \mathcal{Y}\,, l}$|⁠, independent of |$\alpha $|⁠, such that

$$ \begin{align*}& \int_{Y_{l}} ( |w| + \alpha )^{p-2} |w|^{2} \,dx \leq c_{p, \mathcal{Y}, l} \left( \frac{\underline{\alpha}_{\mathcal{Y}} (Y_{l})}{\overline{\alpha}^{\mathcal{Y}} (Y_{l})} \right)^{p-2} \int_{P_{l, l^{*}}} ( | \nabla w| + \alpha )^{p-2} |\nabla w|^{2} \,dx, \quad w \in W_{0}^{1,p} (\varOmega), \end{align*} $$

where the region |$P_{l,l^{*}}$| was given in Definition 4.9.

Similar to Definition 4.4 we present the definition of the quasi-monotone decrease constant |$C_{p, \alpha }^{\mathrm{QM}}$| for |$p \in (1, 2)$| in the following text.

Definition 4.11.

Assume that |$p \in (1, 2)$|⁠. Let |$\alpha \in L^{\infty } (\varOmega )$| be a non-negative function on |$\varOmega $|⁠. The quasi-monotone decrease constant |$C_{p, \alpha }^{\mathrm{QM}} \in [0, \infty ]$| is defined by

$$ \begin{align*}& C_{p, \alpha}^{\mathrm{QM}} = \inf_{\mathcal{Y}} \left\{ \max_{1 \leq l \leq m} \left( \frac{\underline{\alpha}_{\mathcal{Y}} (Y_{l})}{\overline{\alpha}^{\mathcal{Y}} (Y_{l})} \right)^{p-2} \cdot \sum_{l=1}^{m} c_{p, \mathcal{Y}, l} \right\}, \end{align*} $$

where the constants |$c_{p, \mathcal{Y}\,, l}$|’s were given in Lemma 4.10 and the infimum is taken over every nonoverlapping polygonal partition |$\mathcal{Y}\,$| of |$\varOmega $| such that |$\alpha $| is |$\partial \varOmega $|-quasi-monotonically decreasing on |$\mathcal{Y}\,$|⁠.

In terms of the quasi-monotone decrease constant |$C_{p, \alpha }^{\mathrm{QM}}$|⁠, we present a quasi-norm Poincaré–Friedrichs inequality for |$p \in (1, 2)$| in Theorem 4.12, which can be proven in a similar manner to Theorem 4.5.

Theorem 4.12.

Assume that |$p \in (1, 2)$|⁠. Let |$\alpha \in L^{\infty } (\varOmega )$| be a non-negative function on |$\varOmega $|⁠. Then we have

where the quasi-monotone decrease constant |$C_{p, \alpha }^{\mathrm{QM}} \in [0, \infty ]$| was given in Definition 4.11.

The following lemma characterizes the condition when the quasi-monotone decrease constant |$C_{p, \alpha }$| is finite, under an additional assumption that |$\alpha \in W_{h} (\varOmega )$|⁠, i.e., |$\alpha $| is a non-negative piecewise constant function on the triangulation |${\mathcal{T}}_{h}$|⁠.

Lemma 4.13.

Assume that |$p \in (1, 2)$|⁠. Let |$\alpha \in W_{h} (\varOmega )$| be a non-negative piecewise constant function on |${\mathcal{T}}_{h}$|⁠. Then, the quasi-monotone decrease constant |$C_{p, \alpha }^{\mathrm{QM}}$| is finite if and only if every maximal polygonal region |$S \subset \varOmega $| with |$\alpha = 0$| satisfies that |$\partial S \cap \partial \varOmega $| has nonvanishing one-dimensional measure.

Proof.

The proof is analogous to that of Lemma 4.6.

We obtain Corollary 4.14, in which Lemma 3.5 is a particular case |$\alpha = |\nabla u |$|⁠, as a direct consequence of Theorem 4.12 and Lemma 4.13.

Corollary 4.14.

Assume that |$p \in (1, 2)$|⁠. Let |$\alpha \in W_{h} (\varOmega )$| be a non-negative piecewise constant function on |${\mathcal{T}}_{h}$|⁠. If every maximal polygonal region |$S \subset \varOmega $| with |$\alpha = 0$| satisfies that |$\partial S \cap \partial \varOmega $| has nonvanishing one-dimensional measure, then we have

where |$C_{p, \alpha }^{\mathrm{QM}}$| is a finite constant given in Definition 4.11. Moreover, if |$\alpha $| does not vanish on |$\varOmega $| then |$C_{p,\alpha }^{\mathrm{QM}}$| has an upper bound |$\overline{C}_{p,\alpha }^{\mathrm{QM}}$| that is continuous at |$\alpha $| in |$W_{h} (\varOmega )$|⁠.

Finally, we present a counterexample of the quasi-norm Poincaré–Friedrichs inequality (4.1) under the condition presented in Lemma 4.13 for the quasi-monotone decrease constant |$C_{p, \alpha }^{\mathrm{QM}}$| to be infinite.

Example 4.15.

Let |$p \in (1, 2)$| and |$\varOmega = (0, 1) \subset \mathbb{R}$|⁠. We define |$w \in W_{0}^{1,p} (\varOmega )$| and |$\alpha \in L^{\infty } (\varOmega )$| as

$$ \begin{align*}& w(x) = \begin{cases} 3x, & \text{ if}\ 0 < x < \frac{1}{3}, \\ 1 & \text{ if}\ \frac{1}{3} \leq x < \frac{2}{3}, \\ -3x+3, & \text{ if}\ \frac{2}{3} \leq x < 1, \end{cases} \quad \alpha (x) = \begin{cases} 0, & \text{ if}\ \frac{1}{3} \leq x < \frac{2}{3}, \\ 1, & \text{ otherwise.} \end{cases} \quad \end{align*} $$

We observe that the quasi-monotone increase constant |$C_{p, \alpha }^{\mathrm{QM}}$| becomes infinite because the interval |$(1/3, 2/3)$| where |$\alpha $| vanishes does not touch |$\partial \varOmega $|⁠. For |$\epsilon> 0$| direct calculation yields

which implies that (4.1) does not hold.

5. Numerical experiments

In this section we present numerical results of the two-level additive Schwarz method for the |$p$|-Laplacian, which support our theoretical findings. All the algorithms were implemented in MATLAB R2022b. They were executed on a desktop equipped with AMD Ryzen 5 5600X CPU (3.7GHz, 6C), 40GB RAM and the operating system Windows 10 Pro.

In the model |$p$|-Laplacian problem (1.1) we set |$p \in \{ 1.05, 1.1, 1.5, 5, 10, 20 \}$|⁠, |$\varOmega = [0,1]^{2} \subset \mathbb{R}^{2}$| and |$f = 1$|⁠. The domain |$\varOmega $| is partitioned into |$2 \times 1/H \times 1/H$| uniform triangles to form a coarse triangulation |${\mathcal{T}}_{H}$| of |$\varOmega $|⁠. We further refine |${\mathcal{T}}_{H}$| to obtain a fine triangulation |${\mathcal{T}}_{h}$|⁠, which consists of total |$2 \times 1/h \times 1/h$| uniform triangles. Each subdomain |$\varOmega _{k}$|⁠, |$1 \leq k \leq N$| (⁠|$N = 1/H \times 1/H$|⁠) is defined by a rectangular region consisting of two coarse triangles sharing a diagonal edge. Then we extend |$\varOmega _{k}$| by adding its surrounding layers of fine triangles in |${\mathcal{T}}_{h}$| with the width |$\delta $| to construct |$\varOmega _{k}^{\prime}$|⁠, so that |$\{ \varOmega _{k}^{\prime} \}_{k=1}^{N}$| becomes an overlapping domain decomposition for |$\varOmega $|⁠. If |$\delta \in (0, H/2)$| then |$\{ \varOmega _{k}^{\prime} \}_{k=1}^{N}$| can be coloured with four colours in the way described in Lemma 2.2. The discretization and domain decomposition settings described above are illustrated in Fig. 1.

$Discretization and domain decomposition settings when $h = 1/2^{4}$, $H = 1/2^{2}$ and $\delta = h$. (a) Coarse triangulation ${\mathcal{T}}_{H}$ and fine triangulation ${\mathcal{T}}_{h}$. (b) Nonoverlapping domain decomposition $\{ \varOmega _{k} \}_{k=1}^{N}$. (c) Overlapping domain decomposition $\{ \varOmega _{k} ^{\prime} \}_{k=1}^{N}$.$

Fig. 1.

Discretization and domain decomposition settings when |$h = 1/2^{4}$|⁠, |$H = 1/2^{2}$| and |$\delta = h$|⁠. (a) Coarse triangulation |${\mathcal{T}}_{H}$| and fine triangulation |${\mathcal{T}}_{h}$|⁠. (b) Nonoverlapping domain decomposition |$\{ \varOmega _{k} \}_{k=1}^{N}$|⁠. (c) Overlapping domain decomposition |$\{ \varOmega _{k} ^{\prime} \}_{k=1}^{N}$|⁠.

Open in new tab Download slide

$Reference solutions of the $p$-Laplacian problem (2.1) ($p \in \{ 1.05, 1.1, 1.5, 5, 10, 20 \}$) computed by the adaptive Newton method (Mishchenko, 2023) ($h = 2^{-5}$).$

Fig. 2.

Reference solutions of the |$p$|-Laplacian problem (2.1) (⁠|$p \in \{ 1.05, 1.1, 1.5, 5, 10, 20 \}$|⁠) computed by the adaptive Newton method (Mishchenko, 2023) (⁠|$h = 2^{-5}$|⁠).

Open in new tab Download slide

In Algorithm 1 we set |$u^{(0)} = 0$| and |$\tau = \tau _{0} = 1/5$|⁠. Local problems defined on |$V_{k}$|⁠, |$1 \leq k \leq N$|⁠, and coarse problems defined on |$V_{0}$| are solved by the adaptive Newton method proposed in Mishchenko (2023, Algorithm 2.1). We use the stop criterion

$$ \begin{align*}& \left| \frac{F_{k} (w_{k}^{(n+1)}) - F_{k} (w_{k}^{(n)})}{F_{k} (w_{k}^{(n+1)})} \right| < 10^{-12} \end{align*} $$

for both local and coarse problems, where |$F_{k}$| represents the energy functional corresponding to the local or coarse problems on |$V_{k}$|⁠.

Remark 5.1.

As alternatives to the adaptive Newton method used in this paper, which is a second-order optimization algorithm, first-order optimization algorithms (Teboulle, 2018) can be adopted to solve the local and coarse problems. These algorithms are generally easier to implement as they do not require the Hessian information of the energy functional, but known to converge slower than second-order algorithms. To accelerate the convergence rate of a first-order algorithm several techniques such as the FISTA momentum (Beck & Teboulle, 2009), restart scheme (O’Donoghue & Candes, 2015) and backtracking (Scheinberg et al., 2014) can be employed.

A reference solution |$u^{*} \in V$| for each |$p$| and |$h$| is computed by sufficiently many iterations of the adaptive Newton method applied to the full-dimension problem (2.1). The computed reference solutions for |$p \in \{ 1.05, 1.1, 1.5, 5, 10, 20 \}$| are plotted in Fig. 2. One can observe that for cases where |$p$| is close to |$1$| the reference solutions exhibit flat regions where the gradient vanishes. This observation implies that when |$p$| is close to |$1$| the assumption in Theorem 2.4 that |$\nabla u^{*}$| does not vanish may not hold. On the other hand, for cases where |$p$| is large, the reference solutions display peaks, leading to singular behaviour in the solution.

In Figs 3, 4, 5, 6, 7, 8, we depict the relative energy errors

$$ \begin{align}& \frac{F(u^{(n)}) - F(u^{*})}{ F(u^{(0)}) - F(u^{*})}\end{align} $$

(5.1)

$Decay of the relative energy error (5.1) in the two-level additive Schwarz method (Algorithm 1) for the $p$-Laplacian problem (2.1) ($p = 1.05$). Parameters $h$, $H$ and $\delta $ stand for the characteristic element size, subdomain size and overlapping width among subdomains, respectively ($H/h = 2^{3}$).$

Fig. 3.

Decay of the relative energy error (5.1) in the two-level additive Schwarz method (Algorithm 1) for the |$p$|-Laplacian problem (2.1) (⁠|$p = 1.05$|⁠). Parameters |$h$|⁠, |$H$| and |$\delta $| stand for the characteristic element size, subdomain size and overlapping width among subdomains, respectively (⁠|$H/h = 2^{3}$|⁠).

Open in new tab Download slide

$Decay of the relative energy error (5.1) in the two-level additive Schwarz method (Algorithm 1) for the $p$-Laplacian problem (2.1) ($p = 1.1$). Parameters $h$, $H$ and $\delta $ stand for the characteristic element size, subdomain size and overlapping width among subdomains, respectively ($H/h = 2^{3}$).$

Fig. 4.

Decay of the relative energy error (5.1) in the two-level additive Schwarz method (Algorithm 1) for the |$p$|-Laplacian problem (2.1) (⁠|$p = 1.1$|⁠). Parameters |$h$|⁠, |$H$| and |$\delta $| stand for the characteristic element size, subdomain size and overlapping width among subdomains, respectively (⁠|$H/h = 2^{3}$|⁠).

Open in new tab Download slide

$Decay of the relative energy error (5.1) in the two-level additive Schwarz method (Algorithm 1) for the $p$-Laplacian problem (2.1) ($p = 1.5$). Parameters $h$, $H$ and $\delta $ stand for the characteristic element size, subdomain size and overlapping width among subdomains, respectively ($H/h = 2^{3}$).$

Fig. 5.

Decay of the relative energy error (5.1) in the two-level additive Schwarz method (Algorithm 1) for the |$p$|-Laplacian problem (2.1) (⁠|$p = 1.5$|⁠). Parameters |$h$|⁠, |$H$| and |$\delta $| stand for the characteristic element size, subdomain size and overlapping width among subdomains, respectively (⁠|$H/h = 2^{3}$|⁠).

Open in new tab Download slide

$Decay of the relative energy error (5.1) in the two-level additive Schwarz method (Algorithm 1) for the $p$-Laplacian problem (2.1) ($p = 5$). Parameters $h$, $H$ and $\delta $ stand for the characteristic element size, subdomain size and overlapping width among subdomains, respectively ($H/h = 2^{3}$).$

Fig. 6.

Decay of the relative energy error (5.1) in the two-level additive Schwarz method (Algorithm 1) for the |$p$|-Laplacian problem (2.1) (⁠|$p = 5$|⁠). Parameters |$h$|⁠, |$H$| and |$\delta $| stand for the characteristic element size, subdomain size and overlapping width among subdomains, respectively (⁠|$H/h = 2^{3}$|⁠).

Open in new tab Download slide

$Decay of the relative energy error (5.1) in the two-level additive Schwarz method (Algorithm 1) for the $p$-Laplacian problem (2.1) ($p = 10$). Parameters $h$, $H$ and $\delta $ stand for the characteristic element size, subdomain size and overlapping width among subdomains, respectively ($H/h = 2^{3}$).$

Fig. 7.

Decay of the relative energy error (5.1) in the two-level additive Schwarz method (Algorithm 1) for the |$p$|-Laplacian problem (2.1) (⁠|$p = 10$|⁠). Parameters |$h$|⁠, |$H$| and |$\delta $| stand for the characteristic element size, subdomain size and overlapping width among subdomains, respectively (⁠|$H/h = 2^{3}$|⁠).

Open in new tab Download slide

$Decay of the relative energy error (5.1) in the two-level additive Schwarz method (Algorithm 1) for the $p$-Laplacian problem (2.1) ($p = 20$). Parameters $h$, $H$ and $\delta $ stand for the characteristic element size, subdomain size and overlapping width among subdomains, respectively ($H/h = 2^{3}$).$

Fig. 8.

Decay of the relative energy error (5.1) in the two-level additive Schwarz method (Algorithm 1) for the |$p$|-Laplacian problem (2.1) (⁠|$p = 20$|⁠). Parameters |$h$|⁠, |$H$| and |$\delta $| stand for the characteristic element size, subdomain size and overlapping width among subdomains, respectively (⁠|$H/h = 2^{3}$|⁠).

Open in new tab Download slide

of Algorithm 1 under various settings on |$p$|⁠, |$h$|⁠, |$H$| and |$\delta $|⁠. More precisely, in Figs 5 and 6 we choose |$p$| as moderate values |$1.5$| and |$5$|⁠, in Figs 3 and 4 |$p$| is chosen very close to |$1$| (⁠|$p = 1.05, 1.1$|⁠) and in Figs 7 and 8 |$p$| is chosen large (⁠|$p = 10, 20$|⁠). In all figures |$h$| and |$H$| vary such that |$H/h = 2^{3}$|⁠, and |$\delta $| is chosen as |$\delta \in \{ 2^{0}h, 2^{1}h, 2^{2} h \}$|⁠.

In every case we observe that the convergence curve of the relative energy error with respect to the number of iterations |$n$| appears linear in the |$x$|-linear |$y$|-log scale plot when |$n$| is large enough, consistent with our theoretical result presented in Theorem 2.4. It is noteworthy that even in cases where |$p$| is very close to |$1$| (see Figs 3 and 4), where Theorem 2.4 cannot be applied due to the flat region in the solution |$u^{*}$| as shown in Fig. 2(a, b), the convergence curve still appears linear. However, a theoretical explanation for the linear convergence in these cases is currently lacking.

On the other hand, for each |$p$|⁠, we observe that the asymptotic convergence rate of Algorithm 1 shown in Figs 3, 4, 5, 6, 7, 8 remains bounded when |$h$| decreases keeping |$H / \delta $| constant. This behaviour aligns with the dependence of |$\gamma $| to |$H/ \delta $| explained in Theorem 2.4. Moreover, this observation implies that Algorithm 1 is numerically scalable; the asymptotic linear convergence rate is uniformly bounded when the ratio of the subdomain size to the overlapping width is fixed.

6. Conclusion

In this paper we developed a new convergence theory for additive Schwarz methods for boundary value problems involving the |$p$|-Laplacian. To the best of our knowledge our theory is the first theoretical result that explains the asymptotic linear convergence of additive Schwarz methods for the |$p$|-Laplacian. Our work successfully bridges the gap between theory and practice by demonstrating that our theoretical findings align well with numerical results.

While the convergence theory of subspace correction methods for linear problems appears to be well-developed (Xu & Zikatanov, 2002; Lee et al., 2008), there remains a need for further research on the theory of subspace correction methods for nonlinear problems. We believe that our result can serve as a foundation for the sharp convergence theory of general subspace correction methods for complex nonlinear problems.

Funding

NSF-DMS (2208499 to Y.-J.L.); Shapiro Fellowship from Penn State University in the Spring of 2022; REP grant for the year of 2022, from Texas State University; National Research Foundation of Korea (NRF) grant funded by the Korean government (MSIT) (No. 2021R1C1C2095193 to J.P.).

References

Badea

(

2006

)

Convergence rate of a Schwarz multilevel method for the constrained minimization of nonquadratic functionals

SIAM J. Numer. Anal.

449

–

477

Month:	Total Views:
September 2024	16
October 2024	150
November 2024	44
December 2024	39
January 2025	19
February 2025	31
March 2025	45
April 2025	19

Article Contents

On the linear convergence of additive Schwarz methods for the p-Laplacian

Abstract

1. Introduction

2. Additive Schwarz methods

2.1 Discretization and domain decomposition

2.2 Two-level additive Schwarz method

3. Convergence analysis

3.1 Properties of the quasi-norm

3.2 Quasi-norm stable decomposition

3.3 Proof of Theorem 2.4

4. Quasi-norm Poincaré–Friedrichs inequality

5. Numerical experiments

6. Conclusion

Funding

References

Citations

Views

Altmetric

Email alerts

Citing articles via

Latest

Most Read

Most Cited

This Feature Is Available To Subscribers Only