# A Convergence Study of Multisubdomain Schwarz Waveform Relaxation for a Class of Nonlinear Problems

Authors: Liping Zhang; Shu-Lin Wu
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Schwarz waveform relaxation (SWR) is a new type of domain decomposition methods, which is suited for solving time-dependent PDEs in parallel manner. The number of subdomains, namely,N, has a significant influence on the convergence rate. For the representative nonlinear problem ∂
t
u
=
∂
x
x
u
+
f
(
u
), convergence behavior of the algorithm in the two-subdomain case is well-understood. However, for the multisubdomain case (i.e., N
≥
3), the existing results can only predict convergence when f
′
(
u
)
≤
0
(
∀
u
∈
R
). Therefore, there is a gap between N
≥
3 and f
′
(
u
)
>
0. In this paper, we try to finish this gap. Precisely, for a specified subdomain number N, we find that there exists a quantity d
max such that convergence of the algorithm on unbounded time domains is guaranteed if f
′
(
u
)
≤
d
max
(
∀
u
∈
R
). The quantity d
max depends on N and we present concise formula to calculate it. We show that the analysis is useful to study more complicated PDEs. Numerical results are provided to support the theoretical predictions.


---

## Body

## 1. Introduction

LetΩ
=
(
0
,
L
) be a bounded spatial domain of interest. We are interested in the Schwarz waveform relaxation (SWR) algorithm applied to compute solution u
=
u
(
x
,
t
)
:
Ω
×
(
0
,
T
)
→
R of the initial-boundary value problem (IBVP):(1)
∂
t
u
=
∂
x
x
u
+
f
u
,
x
∈
0
,
L
,
t
>
0
,
u
x
,
0
=
u
0
x
,
x
∈
0
,
L
,
u
0
,
t
=
g
1
t
,
u
L
,
t
=
g
2
t
,
t
>
0
,where f
∈
C
1
(
R
) denotes a function which in general depends in a nonlinear manner on u. This is a fundamental model for analyzing the convergence properties of the SWR algorithm and some important results are revisited as follows.Gander [1] studied the SWR algorithm on bounded and unbounded time intervals in the two-subdomain case. Particularly, the author proved linear convergence of the algorithm on unbounded time intervals, if the derivative of f
(
u
) can be bounded from above by a constant d, which satisfies d
<
π
/
L
2 (other related or similar studies can be found in [2–4]). In the case of N subdomains with N
≥
3, Gander and Stuart [5] analyzed the convergence behavior of the SWR algorithm for the linear heat equation ∂
t
u
=
∂
x
x
u on unbounded time intervals. It was shown that the convergence rate depends on N and deteriorates as N increases. For IBVP (1) with f
′
u
<
d and d
<
0, the work in [6] can be generalized to obtain a similar convergence result in the case of N
≥
3. In summary, in the multisubdomain case, the convergence behavior of the SWR algorithm for (1) on unbounded time domains is well-understood, when f
′
u
≤
0. For f
′
u
>
0 and N
≥
3, however, we know nothing up to now.In this paper, we try to finish this gap. After a brief description of the multisubdomain SWR algorithm in Section2, we perform a convergence analysis for the multisubdomain SWR algorithm in Section 3. For given N, we present concise formula to calculate the allowed upper bound of f
′
u, namely, d
m
a
x, which guarantees convergence of the algorithm on unbounded time domains. We show that the analysis for (1) can be used to study the multisubdomain domain decomposition methods [7, 8] for more complicated PDEs: ∂
t
u
=
∂
x
(
θ
(
u
)
∂
x
u
)
+
f
(
u
). Section 4 provides numerical results to support the theoretical prediction and we finish this paper by giving some concluding remarks in Section 5.


## 2. The Schwarz Waveform Relaxation Algorithm

For the initial-boundary value problem (IBVP) (1), we decompose the whole space domain Ω
=
[
0
,
L
] into N subdomains: Ω
i
=
[
α
i
L
,
β
i
L
], where i
=
1,2
,
…
,
N, α
1
=
0, β
N
=
1, and 0
<
α
i
+
1
<
β
i
<
1 for i
=
1,2
,
…
,
N
-
1. We assume that β
i
<
α
i
+
2 so that all the subdomains overlap but domains which are not adjacent do not overlap, as shown in Figure 1. Then, the N-subdomain SWR algorithm for IBVP (1) can be written as(2)
∂
u
i
k
x
,
t
∂
t
=
∂
2
u
i
k
x
,
t
∂
x
2
+
f
u
i
k
x
,
t
,
x
,
t
∈
Ω
i
×
R
+
,
u
i
k
α
i
L
,
t
=
u
i
-
1
k
-
1
α
i
L
,
t
,
t
∈
R
+
,
u
i
k
β
i
L
,
t
=
u
i
+
1
k
-
1
β
i
L
,
t
,
t
∈
R
+
,
u
i
k
x
,
0
=
u
0
x
,
x
∈
Ω
i
,where u
0
k
=
g
1
(
t
) and u
N
+
1
k
=
g
2
(
t
) for all k
≥
0. Let e
i
k
=
u
i
k
-
u
i (u
i
=
u
|
x
∈
Ω
i) be the error function at the kth iteration. Then, we have(3)
∂
e
i
k
x
,
t
∂
t
=
∂
2
e
i
k
x
,
t
∂
x
2
+
f
′
u
^
i
k
e
i
k
x
,
t
,
x
,
t
∈
Ω
i
×
R
+
,
e
i
k
α
i
L
,
t
=
e
i
-
1
k
-
1
α
i
L
,
t
,
t
∈
R
+
,
e
i
k
β
i
L
,
t
=
e
i
+
1
k
-
1
β
i
L
,
t
,
t
∈
R
+
,
e
i
k
x
,
0
=
0
,
x
∈
Ω
i
,where we have used the remainder term in Taylor’s expansion f
(
u
i
k
)
-
f
(
u
i
)
=
f
′
(
u
^
i
k
)
e
i
k for some function u
^
i
k which lies between u
i
k and u
i. In (3), e
0
k
=
0 and e
N
+
1
k
=
0 for all k
≥
0. Following in this section, we define α
0
=
β
0
=
0, α
N
+
1
=
β
N
+
1
=
1, and e
-
1
k
=
e
N
+
2
k
=
0.Figure 1
An illustration of domain decomposition withN overlapping subdomains.Hypothesis 1.
Assume that (1)N is an even integer; (2) the subdomains which are not adjacent do not overlap; (3) all the overlap sizes are equal to l; (4) all the lengths of the subdomains are equal to s.Under this hypothesis, we have(4)
N
s
-
N
-
1
l
=
L
,
β
i
-
α
i
L
=
s
,
i
=
1,2
,
…
,
N
,
β
i
-
1
-
α
i
L
=
l
,
β
i
-
β
i
-
1
L
=
s
-
l
,
α
i
-
α
i
-
1
L
=
s
-
l
,
i
=
2,3
,
…
,
N
.The following two lemmas are useful to analyze the convergence properties of the SWR algorithm in the multisubdomain case.Lemma 1 (see [1]).
Assume that the functionw
∈
C
(
[
0
,
L
]
×
[
0
,
∞
)
)
∩
C
2,1
(
(
0
,
L
)
×
(
0
,
∞
)
) satisfies the following differential inequalities:(5)
w
t
-
c
2
x
,
t
w
x
x
+
a
x
,
t
w
≥
0
,
0
<
x
<
L
,
t
>
0
,
w
0
,
t
≥
0
,
t
>
0
,
w
L
,
t
≥
0
,
t
>
0
,
w
x
,
0
≥
0
,
0
≤
x
≤
L
,where a
(
x
,
t
) is a function bounded from below by some constant C (i.e., a
(
x
,
t
)
≥
C) and c
2
(
x
,
t
)
>
0 for all x
∈
(
0
,
L
) and t
>
0. Then, it holds that w
(
x
,
t
)
≥
0, ∀
(
x
,
t
)
∈
[
0
,
L
]
×
[
0
,
∞
).Lemma 2.
Assume that the functionf in (1) satisfies f
′
(
u
)
≤
d
(
∀
u
∈
R
) and 0
<
d
<
π
/
L
2. Then, the error functions e
i
k in (3) decay on the interfaces x
=
β
i
-
1
L and x
=
α
i
+
1
L at the rate(6)
e
i
k
β
i
-
1
L
,
·
∞
≤
r
i
r
i
+
1
e
i
+
2
k
-
2
β
i
+
1
L
,
·
∞
+
r
i
p
i
+
1
e
i
k
-
2
α
i
+
1
L
,
·
∞
+
p
i
q
i
-
1
e
i
k
-
2
β
i
-
1
L
,
·
∞
+
p
i
s
i
-
1
e
i
-
2
k
-
2
α
i
-
1
L
,
·
∞
,for i
=
2,3
,
…
,
N, and(7)
e
i
k
α
i
+
1
L
,
·
∞
≤
q
i
r
i
+
1
e
i
+
2
k
-
2
β
i
+
1
L
,
·
∞
+
q
i
p
i
+
1
e
i
k
-
2
α
i
+
1
L
,
·
∞
+
s
i
q
i
-
1
e
i
k
-
2
β
i
-
1
L
,
·
∞
+
s
i
s
i
-
1
e
i
-
2
k
-
2
α
i
-
1
L
,
·
∞
,for i
=
1,2
,
…
,
N
-
1, where(8)
r
i
=
sinh
⁡
β
i
-
1
-
α
i
L
d
sinh
⁡
β
i
-
α
i
L
d
,
p
i
=
sinh
⁡
β
i
-
β
i
-
1
L
d
sinh
⁡
β
i
-
α
i
L
d
,
q
i
=
sinh
⁡
α
i
+
1
-
α
i
L
d
sinh
⁡
β
i
-
α
i
L
d
,
s
i
=
sinh
⁡
β
i
-
α
i
+
1
L
d
sinh
⁡
β
i
-
α
i
L
d
.Proof.
Lete
~
i
k
(
x
,
t
) be the solution of the following differential equation: (9)
∂
e
~
i
k
x
,
t
∂
t
=
∂
2
e
~
i
k
x
,
t
∂
x
2
+
d
e
~
i
k
x
,
t
,
e
~
i
k
α
i
L
,
t
=
e
i
-
1
k
-
1
α
i
L
,
·
∞
,
e
~
i
k
β
i
L
,
t
=
e
i
+
1
k
-
1
β
i
L
,
·
∞
,
e
~
i
k
x
,
0
=
sin
⁡
x
-
α
i
L
d
sin
⁡
β
i
-
α
i
L
d
e
i
+
1
k
-
1
β
i
L
,
·
∞
+
sin
⁡
β
i
L
-
x
d
sin
⁡
β
i
-
α
i
L
d
e
i
-
1
k
-
1
α
i
L
,
·
∞
,where (
x
,
t
)
∈
Ω
i
×
R
+. The solution e
~
i
k can be written down as(10)
e
~
i
k
x
,
t
=
sin
⁡
x
-
α
i
L
d
sin
⁡
β
i
-
α
i
L
d
e
i
+
1
k
-
1
β
i
L
,
·
∞
+
sin
⁡
β
i
L
-
x
d
sin
⁡
β
i
-
α
i
L
d
e
i
-
1
k
-
1
α
i
L
,
·
∞
,which is a time-independent function of t. Since d
<
π
/
L
2 and α
i
,
β
i
∈
[
0,1
], we have (
x
-
α
i
L
)
d, (
β
i
L
-
x
)
d
∈
[
0
,
π
) for x
∈
[
α
i
L
,
β
i
L
], and this implies e
~
i
k
(
x
,
t
)
≥
0. Therefore, the difference w
=
e
~
i
k
-
e
i
k satisfies(11)
∂
w
x
,
t
∂
t
=
∂
2
w
x
,
t
∂
x
2
+
d
e
~
i
k
x
,
t
-
f
′
u
^
i
k
e
i
k
x
,
t
,
x
,
t
∈
Ω
i
×
R
+
,
w
α
i
L
,
t
≥
0
,
t
∈
R
+
,
w
β
i
L
,
t
≥
0
,
t
∈
R
+
,
w
x
,
0
≥
0
,
x
∈
Ω
i
.We have (12)
d
e
~
i
k
x
,
t
-
f
′
u
^
i
k
e
i
k
x
,
t
=
d
e
~
i
k
x
,
t
-
f
′
u
^
i
k
e
~
i
k
x
,
t
+
f
′
u
^
i
k
e
~
i
k
x
,
t
-
f
′
u
^
i
k
e
i
k
x
,
t
=
d
-
f
′
u
^
i
k
e
~
i
k
x
,
t
+
f
′
u
^
i
k
w
≥
f
′
u
^
i
k
w
,since f
′
(
u
^
i
k
)
≤
d and e
~
i
k
(
x
,
t
)
≥
0. Then, from (11) we get (13)
∂
w
x
,
t
∂
t
≥
∂
2
w
x
,
t
∂
x
2
+
f
′
u
^
i
k
w
x
,
t
,
x
,
t
∈
Ω
i
×
R
+
,
w
α
i
L
,
t
≥
0
,
t
∈
R
+
,
w
β
i
L
,
t
≥
0
,
t
∈
R
+
,
w
x
,
0
≥
0
,
x
∈
Ω
i
.Now, by using Lemma 1 we have w
=
e
~
i
k
-
e
i
k
≥
0; that is, e
~
i
k
(
x
,
t
)
≥
e
i
k
(
x
,
t
) for (
x
,
t
)
∈
Ω
i
×
R
+. A similar argument holds for the sum w
¯
(
x
,
t
)
=
e
~
i
k
(
x
,
t
)
+
e
i
k
(
x
,
t
), and thus(14)
e
i
k
x
,
·
∞
≤
sin
⁡
x
-
α
i
L
d
sin
⁡
β
i
-
α
i
L
d
e
i
+
1
k
-
1
β
i
L
,
·
∞
+
sin
⁡
β
i
L
-
x
d
sin
⁡
β
i
-
α
i
L
d
e
i
-
1
k
-
1
α
i
L
,
·
∞
.It is easy to find that this inequality holds on all the subdomains and any iteration index k. Hence, it holds that (15a)
e
i
+
1
k
-
1
β
i
L
,
·
∞
≤
sin
⁡
β
i
-
α
i
+
1
L
d
sin
⁡
β
i
+
1
-
α
i
+
1
L
d
e
i
+
2
k
-
2
β
i
+
1
L
,
·
∞
+
sin
⁡
β
i
+
1
-
β
i
L
d
sin
⁡
β
i
+
1
-
α
i
+
1
L
d
e
i
k
-
2
α
i
+
1
L
,
·
∞
,
(15b)
e
i
-
1
k
+
1
α
i
L
,
·
∞
≤
sin
⁡
α
i
-
α
i
-
1
L
d
sin
⁡
β
i
-
1
-
α
i
-
1
L
d
e
i
k
β
i
-
1
L
,
·
∞
+
sin
⁡
β
i
-
1
-
α
i
L
d
sin
⁡
β
i
-
1
-
α
i
-
1
L
d
e
i
-
2
k
α
i
-
1
L
,
·
∞
.Substituting these two inequalities back into the right hand side of (14) and then evaluating (14) at x
=
β
i
-
1
L leads to inequality (6). Evaluating (14) at x
=
α
i
+
1
L leads to (7).


## 3. Convergence Analysis

Based on Hypothesis1 and Lemmas 1 and 2, here we perform a convergence analysis for the SWR algorithm (2) in the N-subdomain case. We then generalize the analysis to more general nonlinear problems. The following notations are used throughout this section: (16a)
r
=
sin
⁡
l
d
s
i
n
L
+
N
-
1
l
/
N
d
,
p
=
sin
⁡
L
-
l
/
N
d
sin
⁡
L
+
N
-
1
l
/
N
d
,
ϕ
=
l
L
π
,
φ
=
L
-
l
N
L
π
,
ρ
d
,
N
=
p
2
+
2
p
r
cos
⁡
π
N
+
min
⁡
N
-
2,1
r
2
,
σ
=
cos
⁡
π
N
,
K
ω
,
N
=
sin
2
⁡
φ
ω
+
2
σ
sin
⁡
ϕ
ω
sin
⁡
φ
ω
+
min
⁡
N
-
2,1
sin
2
⁡
ϕ
ω
sin
2
⁡
ϕ
+
φ
ω
,
(16b)
D
=
p
2
p
r
p
r
p
2
p
r
r
2
r
2
p
r
p
2
p
r
p
r
p
2
p
r
r
2
r
2
p
r
p
2
p
r
⋱
⋱
⋱
p
r
p
2
p
r
r
2
p
r
p
2
,
ξ
k
=
e
1
k
α
2
L
,
·
∞
e
3
k
β
2
L
,
·
∞
e
3
k
α
4
L
,
·
∞
⋮
e
N
-
1
k
β
N
-
2
L
,
·
∞
e
N
-
1
k
α
N
L
,
·
∞
N
-
1
×
1
,
E
=
p
2
p
r
r
2
p
r
p
2
p
r
p
r
p
2
p
r
r
2
r
2
p
r
p
2
p
r
⋱
⋱
⋱
p
r
p
2
p
r
r
2
r
2
p
r
p
2
p
r
p
r
p
2
,
η
k
=
e
2
k
β
1
L
,
·
∞
e
2
k
α
3
L
,
·
∞
e
4
k
β
3
L
,
·
∞
⋮
e
N
-
2
k
α
N
-
1
L
,
·
∞
e
N
k
β
N
-
1
L
,
·
∞
N
-
1
×
1
.


### 3.1. Convergence Analysis for (2)

From (6) and (7), we see that the error at a given boundary interface depends on the errors at different boundary interfaces; this leads to the following two independent linear systems of inequalities:(17)
ξ
k
+
2
≤
D
ξ
k
,
η
k
+
2
≤
E
η
k
,where each inequality should be interpreted in the component sense. The vectors ξ
k and η
k and the matrices D and E are slightly different if the number of subdomains N is even or odd. Under Hypothesis 1 (i.e., N is an even integer and r
i
=
s
i
=
r, p
i
=
q
i
=
p
), the vectors ξ
k and η
k and the matrices D and E are defined by (16b). For N odd, these vectors and matrices can be defined similarly.To study the diminution of the vectorsξ
k and η
k, we focus on the spectral norms of D and E. To this end, we first recall the common definition for the spectral norm; namely,(18)
v
2
=
∑
j
=
1
n
v
j
2
,
A
2
=
sup
v
2
=
1
⁡
A
v
2
,
∀
v
∈
R
n
,
A
∈
R
n
×
n
.Lemma 3.
With the argumentρ
(
d
,
N
) defined by (16a), the spectral norms of D and E satisfy (19)
D
2
,
E
2
≤
ρ
d
,
N
.Proof.
We prove the bound forD. The bound for the matrix E can be obtained similarly. Clearly, the matrix D can be partitioned as D
=
J
+
r
2
F, where J is a tridiagonal matrix (20)
J
=
p
2
p
r
p
r
p
2
p
r
⋱
⋱
⋱
p
r
p
2
p
r
p
r
p
2
N
-
1
×
N
-
1
,and F is a matrix which has only O
(
N
-
2
) nonzero entries and these are equal to 1. In fact, it is easy to verify F
2
≤
m
i
n
{
N
-
2,1
} for N
≥
2. From Lemma 3.8 given in [5], we know that the eigenvalues of J are given by λ
j
J
=
p
2
+
2
p
r
cos
⁡
π
j
/
N. The spectral norm of D then can be estimated by D
2
≤
J
2
+
r
2
F
2
=
p
2
+
2
p
r
cos
⁡
π
/
N
+
min
⁡
{
N
-
2,1
}
r
2
=
ρ
(
d
,
N
).Clearly, to proveξ
k
,
η
k
→
0 as k
→
+
∞, it suffices to prove ρ
(
d
,
N
)
<
1. However, as we will show a little later, this in general does not hold for all choices of d and N. Let(21)
d
=
ω
π
L
,
ω
∈
0,1
.Then, the arguments p and r defined by (16a) can be regarded as functions of ω; that is,(22)
r
=
r
ω
≔
sin
⁡
l
/
L
π
ω
sin
⁡
L
+
N
-
1
l
/
N
L
π
ω
,
p
=
p
ω
≔
sin
⁡
L
-
l
/
N
L
π
ω
sin
⁡
L
+
N
-
1
l
/
N
L
π
ω
.Clearly, with K
(
ω
,
N
) defined by (16a), it holds that(23)
ρ
d
,
N
=
K
ω
,
N
=
p
ω
+
r
ω
2
-
p
ω
r
ω
sin
2
⁡
π
2
N
,
∀
N
≥
3
.Moreover, Hypothesis 1 implies s
>
2
l, and therefore by using N
s
-
(
N
-
1
)
l
=
L we get (
N
+
1
)
l
<
L. Hence, the quantities ϕ and φ defined by (16a) satisfy(24)
ϕ
+
φ
=
L
+
N
-
1
l
N
L
<
L
+
N
-
1
/
N
+
1
L
N
L
π
≤
π
2
,
∀
N
≥
3
,
ϕ
,
φ
∈
0
,
π
2
,
ϕ
<
φ
.For the case d
≤
0, the functions p
(
ω
) and r
(
ω
) are changed to(25)
r
ω
=
sinh
⁡
l
/
L
π
ω
sinh
⁡
L
+
N
-
1
l
/
N
L
π
ω
,
p
ω
=
sinh
⁡
L
-
l
/
N
L
π
ω
sinh
⁡
L
+
N
-
1
l
/
N
L
π
ω
,
with
ω
=
L
-
d
π
.Hence, it is easy to get r
(
ω
)
+
p
(
ω
)
<
1
(⇒K
(
ω
,
N
)
<
1
), since the hyperbolic-sine function satisfies s
i
n
h
(
x
1
)
+
s
i
n
h
(
x
2
)
≤
s
i
n
h
(
x
1
+
x
2
), ∀
x
1,2
∈
R. On the contrary, for the sine function, it holds that s
i
n
(
x
1
)
+
s
i
n
(
x
2
)
>
s
i
n
(
x
1
+
x
2
), ∀
x
1,2
∈
0
,
π
/
2 and x
1
+
x
2
≤
π
/
2. This, together with (24), gives (26)
r
ω
+
p
ω
=
sin
⁡
l
/
L
π
ω
+
sin
⁡
L
-
l
/
N
L
π
ω
sin
⁡
L
+
N
-
1
l
/
N
L
π
ω
>
sin
⁡
l
/
L
π
ω
+
L
-
l
/
N
L
π
ω
sin
⁡
L
+
N
-
1
l
/
N
L
π
ω
=
1
.Therefore, for d
>
0 it is not obvious to see K
(
ω
,
N
)
<
1.Lemma 4.
Under Hypothesis1, for given N
≥
3 the function K
(
ω
,
N
) defined by (16a) is increasing for ω
∈
(
0,1
) and satisfies K
(
0
,
N
)
<
1 and K
(
1
,
N
)
>
1.Proof.
The proof is divided into two parts.
Part I (K
(
0
,
N
)
<
1 and K
(
1
,
N
)
>
1). It is easy to get l
i
m
ω
→
0
K
(
ω
,
N
)
=
ϕ
2
+
φ
2
+
2
σ
ϕ
φ
/
(
ϕ
+
φ
)
2
<
1, since σ
<
1. We next prove K
(
1
,
N
)
>
1. To this end, we define (27)
R
~
ϕ
,
φ
≔
sin
2
⁡
ϕ
+
sin
2
⁡
φ
+
2
σ
sin
⁡
ϕ
sin
⁡
φ
sin
2
⁡
ϕ
+
φ
,
R
^
ϕ
,
φ
≔
sin
⁡
ϕ
+
φ
sin
⁡
ϕ
cos
⁡
ϕ
+
σ
cos
⁡
ϕ
sin
⁡
φ
-
sin
2
⁡
ϕ
+
sin
2
⁡
φ
+
2
σ
sin
⁡
ϕ
sin
⁡
φ
cos
⁡
ϕ
+
φ
.Then, it holds that K
(
1
,
N
)
=
R
~
(
ϕ
,
φ
) and(28)
∂
R
~
ϕ
,
φ
∂
ϕ
=
2
R
^
ϕ
,
φ
sin
3
⁡
ϕ
+
φ
.Moreover, a routine calculation yields(29)
R
^
ϕ
,
φ
=
sin
⁡
ϕ
cos
⁡
φ
+
cos
⁡
ϕ
sin
⁡
φ
sin
⁡
ϕ
cos
⁡
ϕ
+
σ
cos
⁡
ϕ
sin
⁡
φ
-
cos
⁡
ϕ
cos
⁡
φ
-
sin
⁡
ϕ
sin
⁡
φ
sin
2
⁡
ϕ
+
sin
2
⁡
φ
+
2
σ
sin
⁡
ϕ
sin
⁡
φ
=
sin
⁡
φ
cos
⁡
ϕ
σ
cos
⁡
ϕ
sin
⁡
φ
-
cos
⁡
φ
sin
⁡
φ
+
sin
⁡
ϕ
cos
⁡
ϕ
-
σ
sin
⁡
ϕ
cos
⁡
φ
+
sin
⁡
ϕ
sin
⁡
φ
sin
2
⁡
ϕ
+
sin
2
⁡
φ
+
2
σ
sin
⁡
ϕ
sin
⁡
φ
=
sin
⁡
φ
cos
⁡
ϕ
σ
sin
⁡
φ
-
ϕ
+
sin
⁡
2
ϕ
-
sin
⁡
2
φ
2
+
sin
⁡
ϕ
sin
⁡
φ
sin
2
⁡
ϕ
+
sin
2
⁡
φ
+
2
σ
sin
⁡
ϕ
sin
⁡
φ
.Since ϕ
=
l
/
L
π and φ
=
L
-
l
/
N
L
π, we have(30)
σ
sin
⁡
φ
-
ϕ
+
sin
⁡
2
ϕ
-
sin
⁡
2
φ
2
=
V
l
,
V
l
≔
cos
⁡
π
N
sin
⁡
L
-
N
+
1
l
N
L
π
+
sin
⁡
2
l
/
L
π
-
sin
⁡
2
L
-
l
/
N
L
π
2
.It is easy to get ∂
V
(
l
)
/
∂
l
=
π
V
1
(
l
) and ∂
2
V
(
l
)
/
∂
l
2
=
π
2
V
2
(
l
), where (31)
V
1
l
≔
-
N
+
1
N
L
cos
⁡
π
N
cos
⁡
L
-
N
+
1
l
N
L
π
+
1
L
cos
⁡
2
l
L
π
+
1
N
L
cos
⁡
2
L
-
l
N
L
π
,
V
2
l
≔
-
N
+
1
N
L
2
cos
⁡
π
N
sin
⁡
L
-
N
+
1
l
N
L
π
-
2
L
2
sin
⁡
2
l
π
L
-
sin
⁡
2
L
-
l
π
/
N
L
N
2
.By using (
N
+
1
)
l
<
L, we get L
+
(
N
-
1
)
l
/
N
L
π
<
L
+
(
N
-
1
)
L
/
N
+
1
/
N
L
π = 2
π
/
N
+
1
≤
π
/
2
(
∀
N
≥
3
); this implies(32)
V
2
l
<
V
^
2
l
≔
-
cos
⁡
π
N
N
+
1
N
L
2
sin
⁡
L
-
N
+
1
l
N
L
π
-
2
L
2
sin
⁡
2
l
π
L
+
4
N
L
2
sin
⁡
L
-
l
+
N
l
N
L
π
.For any N
≥
3, we have c
o
s
π
/
N
N
+
1
/
N
L
2
≥
1
/
2
N
+
1
/
N
L
2
>
4
/
(
N
L
)
2; this, together with 2
/
L
2
>
4
/
(
N
L
)
2, gives(33)
V
^
2
l
≤
4
N
L
2
-
sin
⁡
L
-
N
+
1
l
N
L
π
-
sin
⁡
2
l
L
π
+
sin
⁡
L
-
l
+
N
l
N
L
π
<
0
,where in the last inequality we have used L
-
(
N
+
1
)
l
/
N
L
π
+
2
l
/
L
π
=
L
+
(
N
-
1
)
l
/
N
L
π
∈
(
0
,
π
/
2
] and s
i
n
(
x
1
)
+
s
i
n
(
x
2
)
>
s
i
n
(
x
1
+
x
2
) for any x
1
,
x
2
∈
0
,
π
/
2 and x
1
+
x
2
≤
π
/
2.
From (32) and (33), we have ∂
2
V
(
l
)
/
∂
l
2
<
0,∀
l
∈
0
,
L
/
N
+
1. Therefore, V
(
l
) does not have local minimum(s) for l
∈
0
,
L
/
N
+
1. Moreover, by noticing (34)
V
0
=
cos
⁡
π
N
sin
⁡
π
N
-
cos
⁡
π
N
sin
⁡
π
N
=
0
,
V
L
N
+
1
=
0
,we have V
(
l
)
>
0 for all l
∈
0
,
L
/
N
+
1. This, together with (28)–(30), gives ∂
R
~
(
ϕ
,
φ
)
/
∂
ϕ
>
0, ∀
ϕ
∈
(
0
,
φ
). Hence, K
(
1
,
N
)
=
R
~
(
ϕ
,
φ
)
>
R
~
(
0
,
φ
)
=
1.
Part II (K
(
ω
,
N
) is an increasing function for ω
∈
[
0,1
]). From the second equality in (23), we know that the function K
(
ω
,
N
) can be represented as (35)
K
ω
,
N
=
r
2
ω
+
2
r
ω
p
ω
σ
+
p
2
ω
,where r
(
ω
) and p
(
ω
) are defined by (22) and σ
=
c
o
s
(
π
/
N
). Let 0
≤
A
<
B
≤
π be two constants and H
(
ω
)
=
s
i
n
(
A
ω
)
/
s
i
n
(
B
ω
). Then, it is easy to prove H
′
(
ω
)
>
0
(
∀
ω
∈
(
0,1
)
). (We have sign
⁡
(
H
′
(
ω
)
)
=
sign
⁡
(
H
1
(
ω
)
) with H
1
ω
=
A
cos
⁡
A
ω
s
i
n
B
ω
-
B
cos
⁡
(
B
ω
)
s
i
n
(
A
ω
). Moreover, we have H
1
′
(
ω
)
=
(
B
2
-
A
2
)
s
i
n
(
A
ω
)
s
i
n
(
B
ω
)
>
0; this, together with B
>
A
≥
0 and H
1
(
0
)
=
0, gives H
1
(
ω
)
>
0. Hence, H
′
(
ω
)
>
0 for ω
∈
(
0,1
).) Therefore, it is easy to understand that r
′
ω
,
p
′
ω
>
0 for ω
∈
(
0,1
). Since r, p, and σ are positive, we finally get ∂
ω
K
>
0 for ω
∈
(
0,1
).Now, we are in a position to present one of the main results of this section.Theorem 5.
Under Hypothesis1, assume that the function f in (1) satisfies f
′
(
u
)
≤
d
(
∀
u
∈
R
) with 0
<
d
<
π
/
L
ω
∗
2, where for specified integer N
≥
2 the argument ω
∗
∈
(
0,1
] is the unique root of K
(
ω
,
N
)
=
1. Then, the N-subdomain SWR algorithm (2) with N
≥
2 is convergent. In particular, the error functions can be bounded in infinity norm in time and space, as(36)
max
1
≤
2
i
≤
N
⁡
e
2
i
2
k
+
1
·
,
·
∞
,
∞
≤
C
ρ
k
d
,
N
ξ
0
2
,
max
1
≤
2
i
+
1
≤
N
⁡
e
2
i
+
1
2
k
+
1
·
,
·
∞
,
∞
≤
C
ρ
k
d
,
N
η
0
2
,where(37)
C
=
max
i
=
1,2
,
…
,
N
⁡
max
x
∈
α
i
L
,
β
i
L
⁡
sin
⁡
x
-
α
i
L
d
sin
⁡
β
i
-
α
i
L
d
+
sin
⁡
β
i
L
-
x
d
sin
⁡
β
i
-
α
i
L
d
.Proof.
From (14), for all x
∈
[
α
i
L
,
β
i
L
] we have (38)
e
i
k
x
,
·
∞
≤
sin
⁡
x
-
α
i
L
d
sin
⁡
β
i
-
α
i
L
d
+
sin
⁡
β
i
L
-
x
d
sin
⁡
β
i
-
α
i
L
d
max
⁡
e
i
+
1
k
-
1
β
i
L
,
·
∞
,
e
i
-
1
k
-
1
α
i
L
,
·
∞
.With the constant C given above, this implies (39)
max
1
≤
2
i
≤
N
⁡
e
2
i
2
k
+
1
·
,
·
∞
,
∞
≤
C
ξ
2
k
∞
,
max
1
≤
2
i
+
1
≤
N
⁡
e
2
i
+
1
2
k
+
1
·
,
·
∞
,
∞
≤
C
η
2
k
∞
.Since the infinity norm is bounded by the spectral norm, we have (40)
max
1
≤
2
i
≤
N
⁡
e
2
i
2
k
+
1
·
,
·
∞
,
∞
≤
C
ξ
2
k
2
,
max
1
≤
2
i
+
1
≤
N
⁡
e
2
i
+
1
2
k
+
1
·
,
·
∞
,
∞
≤
C
η
2
k
2
.Then, by using ξ
2
k
2
≤
D
2
k
ξ
0
2 and η
2
k
2
≤
E
2
k
η
0
2 and Lemma 3, we get (36). Finally, by using Lemma 4 (i.e., ρ
(
d
,
N
)
<
1 for 0
<
d
<
π
/
L
ω
∗
2), convergence of the SWR algorithm in the multisubdomain case follows.Remark 6.
ForN
=
2, that is, the two-subdomain case, we have ϕ
+
2
φ
=
π; hence, K
(
ω
,
2
)
=
s
i
n
2
(
φ
ω
)
/
s
i
n
2
[
(
ϕ
+
φ
)
ω
]
=
s
i
n
2
(
φ
ω
)
/
s
i
n
2
[
(
π
-
φ
)
ω
]. Since φ
∈
(
0
,
π
/
2
), it is easy to know that K
(
ω
,
2
) is an increasing function of ω
∈
[
0,1
]; this, together with K
(
ω
,
2
)
ω
=
1
=
1, implies ω
∗
=
1. Therefore, Theorem 5 actually includes Theorem 4.1 given by Gander [1].


### 3.2.  Application to More General Nonlinear Problems

We now consider the following IBVP:(41)
∂
t
u
=
∂
x
θ
u
∂
x
u
+
f
u
,
x
,
t
∈
0
,
L
×
R
+
,
u
0
,
t
=
g
1
t
,
u
L
,
t
=
g
2
t
,
t
∈
R
+
,
u
x
,
0
=
u
0
x
,
x
∈
0
,
L
,where the functions θ and f satisfy(42)
f
′
u
≤
d
∀
u
∈
R
,
f
∈
C
1
R
,
θ
u
≥
θ
m
i
n
>
0
∀
u
∈
R
,
θ
∈
C
R
.We can also assume that θ and f depend on x and t, but this only makes a trivial difference. Here, we are interested in applying the domain decomposition strategy to (41) from time step to time step. Assume that (41) is discretized by the backward Euler method:(43)
u
n
-
Δ
t
n
∂
x
θ
u
n
∂
x
u
n
+
f
u
n
=
u
n
-
1
,where Δ
t
n denotes the step size and u
n
(
x
)
≈
u
(
t
n
,
x
). We can also consider some other time integrators, such as Trapezoidal, Runge-Kutta methods, but the analysis is similar. Now, with u
n
-
1
(
x
) known from the previous computation step, we focus on calculating u
n
(
x
) through the domain decomposition method [7, 8]:(44)
x
∈
Ω
i
:
U
i
k
x
-
Δ
t
n
∂
x
θ
U
i
k
x
∂
x
U
i
k
x
+
f
U
i
k
x
=
u
n
-
1
x
,
U
i
k
α
i
L
=
U
i
-
1
k
-
1
α
i
L
,
U
i
k
β
i
L
=
U
i
+
1
k
-
1
β
i
L
,where U
0
k
≡
g
1
(
t
n
) and U
N
+
1
k
≡
g
2
(
t
n
). Upon convergence, we get U
∞
(
x
)
=
u
n
(
x
).To analyze the convergence of the sequence{
U
j
k
}
k
=
0
∞, we need the following lemma.Lemma 7 (see [9]).
LetL
u
≔
a
u
′
′
+
b
u
′
+
c
u be a linear, elliptic operator with c
<
0 in a bounded domain Ω. Suppose that, in Ω, L
u
≥
0
(
≤
0
) with u
∈
C
2
(
Ω
)
∩
C
0
(
Ω
¯
). Then, it holds that s
u
p
x
Ω
u
≥
s
u
p
x
∈
∂
Ω
m
a
x
{
u
,
0
}
(
i
n
f
x
Ω
u
≤
i
n
f
x
∈
∂
Ω
m
i
n
{
u
,
0
}
).Define(45)
e
i
k
x
=
∫
U
i
x
U
i
k
x
θ
v
d
v
with
U
i
x
=
U
x
x
∈
Ω
i
.Then, we have(46)
∂
x
e
i
k
x
=
θ
U
i
k
x
∂
x
U
i
k
x
-
θ
U
i
x
∂
x
U
i
x
,
e
i
k
x
=
θ
U
¯
i
k
U
i
k
x
-
U
i
x
,where for the second equality we have used the mean value theorem for integrals with some U
¯
i
k lying between U
i
k and U
i. Subtracting U
i from (44) and then using (46), we get(47)
x
∈
Ω
i
:
∂
x
2
e
i
k
x
+
Δ
t
n
f
′
U
^
i
k
-
1
Δ
t
n
θ
U
¯
i
k
e
i
k
x
=
0
,
e
i
k
α
i
L
=
e
i
-
1
k
-
1
α
i
L
,
e
i
k
β
i
L
=
e
i
+
1
k
-
1
β
i
L
,where e
0
k
(
x
)
=
e
N
+
1
k
(
x
)
≡
0. Let(48)
d
^
=
Δ
t
n
d
-
1
Δ
t
n
θ
min
⁡
.Then, from (42) we have Δ
t
n
f
′
(
U
^
i
k
)
-
1
/
Δ
t
n
θ
(
U
¯
i
k
)
≤
d
^. Now, by using Lemma 7 and a similar procedure as we did in the proof of Lemma 2, it holds that(49)
e
i
k
x
≤
e
~
i
k
x
,
∀
x
∈
Ω
i
,provided d
^
<
(
π
/
L
)
2, where e
~
i
k
(
x
)
≥
0 is defined by(50)
e
~
i
k
x
=
sinh
⁡
x
-
α
i
L
-
d
^
sinh
⁡
β
i
-
α
i
L
-
d
^
e
i
+
1
k
-
1
β
i
L
+
sinh
⁡
β
i
L
-
x
-
d
^
sinh
⁡
β
i
-
α
i
L
-
d
^
e
i
-
1
k
-
1
α
i
L
.Here, for d
^
=
0 or d
^
>
0 the quantity s
i
n
h
A
-
d
^
/
s
i
n
h
B
-
d
^ should be understood as(51)
sinh
⁡
A
-
d
^
sinh
⁡
B
-
d
^
=
A
B
,
if
d
^
=
0
,
sinh
⁡
A
-
d
^
sinh
⁡
B
-
d
^
=
sin
⁡
A
d
^
sin
⁡
B
d
^
,
if
d
^
>
0
.Define(52)
r
^
=
sinh
⁡
l
-
d
^
sinh
⁡
L
+
N
-
1
l
/
N
-
d
^
,
p
^
=
sinh
⁡
L
-
l
/
N
-
d
^
sinh
⁡
L
+
N
-
1
l
/
N
-
d
^
,
ρ
^
d
^
,
N
=
p
^
2
+
2
p
^
r
^
cos
⁡
π
N
+
r
^
2
.Then, following the analysis in Section 3.1, Theorem 8 can be derived directly.Theorem 8.
Letθ and f satisfy (42). Let d
^
=
Δ
t
n
d
-
1
/
Δ
t
n
θ
m
i
n
<
(
π
/
L
ω
∗
)
2, where ω
∗
∈
(
0,1
] is the unique root of K
(
ω
,
N
)
=
1 and K is defined by (16a). Then, for N
≥
2 iterations (44) are convergent and the error functions {
e
i
k
(
x
)
}
i
=
1,2
,
…
,
N defined by (45) uniformly decay to zero with a rate ρ
^
(
d
^
,
N
)
<
1.For specifiedN, l, d, θ
m
i
n, and L, Theorem 8 can be used to select a safe step size Δ
t
n and therefore it is instructive for designing anadaptive-step-size computation.Remark 9 (monotonicity ofρ
^).
At the end of this section, we claim thatρ
^ is an increasing function of d
^ and N and is a decreasing function of l. We show the increasing monotonicity with respect to d
^ and the others can be proved similarly. Indeed, for d
^
∈
(
0
,
(
π
/
L
)
2
) it holds(53)
r
^
=
sin
⁡
l
d
^
sin
⁡
L
+
N
-
1
l
/
N
d
^
,
p
^
=
sin
⁡
L
-
l
/
N
d
^
sin
⁡
L
+
N
-
1
l
/
N
d
^
,and we have already proved in Lemma 4 (Part II) that both r
^ and p
^ are increasing functions of d
^ (and therefore they are increasing functions of d
^). It remains to consider d
^
≤
0. Let B
>
A
>
0 be two constants and H
(
z
)
=
s
i
n
h
(
A
z
)
/
s
i
n
h
(
B
z
). Then, it is easy to get sign
⁡
H
′
z
=
sign
⁡
(
H
1
(
z
)
), where (54)
H
1
z
=
A
cosh
⁡
A
z
sinh
⁡
B
z
-
B
cosh
⁡
B
z
sinh
⁡
A
z
.We have H
1
′
(
z
)
=
(
A
2
-
B
2
)
s
i
n
h
(
A
z
)
s
i
n
h
(
B
z
)
<
0
(
∀
z
>
0
) and this, together with H
1
(
0
)
=
0, implies H
′
(
z
)
>
0 for z
>
0. Hence, for d
^
≤
0 the arguments r
^ and p
^ are also increasing functions of d
^. Since r
^
,
p
^
≥
0, it is easy to understand that ρ
^ is an increasing function of d
^.


## 3.1. Convergence Analysis for (2)

From (6) and (7), we see that the error at a given boundary interface depends on the errors at different boundary interfaces; this leads to the following two independent linear systems of inequalities:(17)
ξ
k
+
2
≤
D
ξ
k
,
η
k
+
2
≤
E
η
k
,where each inequality should be interpreted in the component sense. The vectors ξ
k and η
k and the matrices D and E are slightly different if the number of subdomains N is even or odd. Under Hypothesis 1 (i.e., N is an even integer and r
i
=
s
i
=
r, p
i
=
q
i
=
p
), the vectors ξ
k and η
k and the matrices D and E are defined by (16b). For N odd, these vectors and matrices can be defined similarly.To study the diminution of the vectorsξ
k and η
k, we focus on the spectral norms of D and E. To this end, we first recall the common definition for the spectral norm; namely,(18)
v
2
=
∑
j
=
1
n
v
j
2
,
A
2
=
sup
v
2
=
1
⁡
A
v
2
,
∀
v
∈
R
n
,
A
∈
R
n
×
n
.Lemma 3.
With the argumentρ
(
d
,
N
) defined by (16a), the spectral norms of D and E satisfy (19)
D
2
,
E
2
≤
ρ
d
,
N
.Proof.
We prove the bound forD. The bound for the matrix E can be obtained similarly. Clearly, the matrix D can be partitioned as D
=
J
+
r
2
F, where J is a tridiagonal matrix (20)
J
=
p
2
p
r
p
r
p
2
p
r
⋱
⋱
⋱
p
r
p
2
p
r
p
r
p
2
N
-
1
×
N
-
1
,and F is a matrix which has only O
(
N
-
2
) nonzero entries and these are equal to 1. In fact, it is easy to verify F
2
≤
m
i
n
{
N
-
2,1
} for N
≥
2. From Lemma 3.8 given in [5], we know that the eigenvalues of J are given by λ
j
J
=
p
2
+
2
p
r
cos
⁡
π
j
/
N. The spectral norm of D then can be estimated by D
2
≤
J
2
+
r
2
F
2
=
p
2
+
2
p
r
cos
⁡
π
/
N
+
min
⁡
{
N
-
2,1
}
r
2
=
ρ
(
d
,
N
).Clearly, to proveξ
k
,
η
k
→
0 as k
→
+
∞, it suffices to prove ρ
(
d
,
N
)
<
1. However, as we will show a little later, this in general does not hold for all choices of d and N. Let(21)
d
=
ω
π
L
,
ω
∈
0,1
.Then, the arguments p and r defined by (16a) can be regarded as functions of ω; that is,(22)
r
=
r
ω
≔
sin
⁡
l
/
L
π
ω
sin
⁡
L
+
N
-
1
l
/
N
L
π
ω
,
p
=
p
ω
≔
sin
⁡
L
-
l
/
N
L
π
ω
sin
⁡
L
+
N
-
1
l
/
N
L
π
ω
.Clearly, with K
(
ω
,
N
) defined by (16a), it holds that(23)
ρ
d
,
N
=
K
ω
,
N
=
p
ω
+
r
ω
2
-
p
ω
r
ω
sin
2
⁡
π
2
N
,
∀
N
≥
3
.Moreover, Hypothesis 1 implies s
>
2
l, and therefore by using N
s
-
(
N
-
1
)
l
=
L we get (
N
+
1
)
l
<
L. Hence, the quantities ϕ and φ defined by (16a) satisfy(24)
ϕ
+
φ
=
L
+
N
-
1
l
N
L
<
L
+
N
-
1
/
N
+
1
L
N
L
π
≤
π
2
,
∀
N
≥
3
,
ϕ
,
φ
∈
0
,
π
2
,
ϕ
<
φ
.For the case d
≤
0, the functions p
(
ω
) and r
(
ω
) are changed to(25)
r
ω
=
sinh
⁡
l
/
L
π
ω
sinh
⁡
L
+
N
-
1
l
/
N
L
π
ω
,
p
ω
=
sinh
⁡
L
-
l
/
N
L
π
ω
sinh
⁡
L
+
N
-
1
l
/
N
L
π
ω
,
with
ω
=
L
-
d
π
.Hence, it is easy to get r
(
ω
)
+
p
(
ω
)
<
1
(⇒K
(
ω
,
N
)
<
1
), since the hyperbolic-sine function satisfies s
i
n
h
(
x
1
)
+
s
i
n
h
(
x
2
)
≤
s
i
n
h
(
x
1
+
x
2
), ∀
x
1,2
∈
R. On the contrary, for the sine function, it holds that s
i
n
(
x
1
)
+
s
i
n
(
x
2
)
>
s
i
n
(
x
1
+
x
2
), ∀
x
1,2
∈
0
,
π
/
2 and x
1
+
x
2
≤
π
/
2. This, together with (24), gives (26)
r
ω
+
p
ω
=
sin
⁡
l
/
L
π
ω
+
sin
⁡
L
-
l
/
N
L
π
ω
sin
⁡
L
+
N
-
1
l
/
N
L
π
ω
>
sin
⁡
l
/
L
π
ω
+
L
-
l
/
N
L
π
ω
sin
⁡
L
+
N
-
1
l
/
N
L
π
ω
=
1
.Therefore, for d
>
0 it is not obvious to see K
(
ω
,
N
)
<
1.Lemma 4.
Under Hypothesis1, for given N
≥
3 the function K
(
ω
,
N
) defined by (16a) is increasing for ω
∈
(
0,1
) and satisfies K
(
0
,
N
)
<
1 and K
(
1
,
N
)
>
1.Proof.
The proof is divided into two parts.
Part I (K
(
0
,
N
)
<
1 and K
(
1
,
N
)
>
1). It is easy to get l
i
m
ω
→
0
K
(
ω
,
N
)
=
ϕ
2
+
φ
2
+
2
σ
ϕ
φ
/
(
ϕ
+
φ
)
2
<
1, since σ
<
1. We next prove K
(
1
,
N
)
>
1. To this end, we define (27)
R
~
ϕ
,
φ
≔
sin
2
⁡
ϕ
+
sin
2
⁡
φ
+
2
σ
sin
⁡
ϕ
sin
⁡
φ
sin
2
⁡
ϕ
+
φ
,
R
^
ϕ
,
φ
≔
sin
⁡
ϕ
+
φ
sin
⁡
ϕ
cos
⁡
ϕ
+
σ
cos
⁡
ϕ
sin
⁡
φ
-
sin
2
⁡
ϕ
+
sin
2
⁡
φ
+
2
σ
sin
⁡
ϕ
sin
⁡
φ
cos
⁡
ϕ
+
φ
.Then, it holds that K
(
1
,
N
)
=
R
~
(
ϕ
,
φ
) and(28)
∂
R
~
ϕ
,
φ
∂
ϕ
=
2
R
^
ϕ
,
φ
sin
3
⁡
ϕ
+
φ
.Moreover, a routine calculation yields(29)
R
^
ϕ
,
φ
=
sin
⁡
ϕ
cos
⁡
φ
+
cos
⁡
ϕ
sin
⁡
φ
sin
⁡
ϕ
cos
⁡
ϕ
+
σ
cos
⁡
ϕ
sin
⁡
φ
-
cos
⁡
ϕ
cos
⁡
φ
-
sin
⁡
ϕ
sin
⁡
φ
sin
2
⁡
ϕ
+
sin
2
⁡
φ
+
2
σ
sin
⁡
ϕ
sin
⁡
φ
=
sin
⁡
φ
cos
⁡
ϕ
σ
cos
⁡
ϕ
sin
⁡
φ
-
cos
⁡
φ
sin
⁡
φ
+
sin
⁡
ϕ
cos
⁡
ϕ
-
σ
sin
⁡
ϕ
cos
⁡
φ
+
sin
⁡
ϕ
sin
⁡
φ
sin
2
⁡
ϕ
+
sin
2
⁡
φ
+
2
σ
sin
⁡
ϕ
sin
⁡
φ
=
sin
⁡
φ
cos
⁡
ϕ
σ
sin
⁡
φ
-
ϕ
+
sin
⁡
2
ϕ
-
sin
⁡
2
φ
2
+
sin
⁡
ϕ
sin
⁡
φ
sin
2
⁡
ϕ
+
sin
2
⁡
φ
+
2
σ
sin
⁡
ϕ
sin
⁡
φ
.Since ϕ
=
l
/
L
π and φ
=
L
-
l
/
N
L
π, we have(30)
σ
sin
⁡
φ
-
ϕ
+
sin
⁡
2
ϕ
-
sin
⁡
2
φ
2
=
V
l
,
V
l
≔
cos
⁡
π
N
sin
⁡
L
-
N
+
1
l
N
L
π
+
sin
⁡
2
l
/
L
π
-
sin
⁡
2
L
-
l
/
N
L
π
2
.It is easy to get ∂
V
(
l
)
/
∂
l
=
π
V
1
(
l
) and ∂
2
V
(
l
)
/
∂
l
2
=
π
2
V
2
(
l
), where (31)
V
1
l
≔
-
N
+
1
N
L
cos
⁡
π
N
cos
⁡
L
-
N
+
1
l
N
L
π
+
1
L
cos
⁡
2
l
L
π
+
1
N
L
cos
⁡
2
L
-
l
N
L
π
,
V
2
l
≔
-
N
+
1
N
L
2
cos
⁡
π
N
sin
⁡
L
-
N
+
1
l
N
L
π
-
2
L
2
sin
⁡
2
l
π
L
-
sin
⁡
2
L
-
l
π
/
N
L
N
2
.By using (
N
+
1
)
l
<
L, we get L
+
(
N
-
1
)
l
/
N
L
π
<
L
+
(
N
-
1
)
L
/
N
+
1
/
N
L
π = 2
π
/
N
+
1
≤
π
/
2
(
∀
N
≥
3
); this implies(32)
V
2
l
<
V
^
2
l
≔
-
cos
⁡
π
N
N
+
1
N
L
2
sin
⁡
L
-
N
+
1
l
N
L
π
-
2
L
2
sin
⁡
2
l
π
L
+
4
N
L
2
sin
⁡
L
-
l
+
N
l
N
L
π
.For any N
≥
3, we have c
o
s
π
/
N
N
+
1
/
N
L
2
≥
1
/
2
N
+
1
/
N
L
2
>
4
/
(
N
L
)
2; this, together with 2
/
L
2
>
4
/
(
N
L
)
2, gives(33)
V
^
2
l
≤
4
N
L
2
-
sin
⁡
L
-
N
+
1
l
N
L
π
-
sin
⁡
2
l
L
π
+
sin
⁡
L
-
l
+
N
l
N
L
π
<
0
,where in the last inequality we have used L
-
(
N
+
1
)
l
/
N
L
π
+
2
l
/
L
π
=
L
+
(
N
-
1
)
l
/
N
L
π
∈
(
0
,
π
/
2
] and s
i
n
(
x
1
)
+
s
i
n
(
x
2
)
>
s
i
n
(
x
1
+
x
2
) for any x
1
,
x
2
∈
0
,
π
/
2 and x
1
+
x
2
≤
π
/
2.
From (32) and (33), we have ∂
2
V
(
l
)
/
∂
l
2
<
0,∀
l
∈
0
,
L
/
N
+
1. Therefore, V
(
l
) does not have local minimum(s) for l
∈
0
,
L
/
N
+
1. Moreover, by noticing (34)
V
0
=
cos
⁡
π
N
sin
⁡
π
N
-
cos
⁡
π
N
sin
⁡
π
N
=
0
,
V
L
N
+
1
=
0
,we have V
(
l
)
>
0 for all l
∈
0
,
L
/
N
+
1. This, together with (28)–(30), gives ∂
R
~
(
ϕ
,
φ
)
/
∂
ϕ
>
0, ∀
ϕ
∈
(
0
,
φ
). Hence, K
(
1
,
N
)
=
R
~
(
ϕ
,
φ
)
>
R
~
(
0
,
φ
)
=
1.
Part II (K
(
ω
,
N
) is an increasing function for ω
∈
[
0,1
]). From the second equality in (23), we know that the function K
(
ω
,
N
) can be represented as (35)
K
ω
,
N
=
r
2
ω
+
2
r
ω
p
ω
σ
+
p
2
ω
,where r
(
ω
) and p
(
ω
) are defined by (22) and σ
=
c
o
s
(
π
/
N
). Let 0
≤
A
<
B
≤
π be two constants and H
(
ω
)
=
s
i
n
(
A
ω
)
/
s
i
n
(
B
ω
). Then, it is easy to prove H
′
(
ω
)
>
0
(
∀
ω
∈
(
0,1
)
). (We have sign
⁡
(
H
′
(
ω
)
)
=
sign
⁡
(
H
1
(
ω
)
) with H
1
ω
=
A
cos
⁡
A
ω
s
i
n
B
ω
-
B
cos
⁡
(
B
ω
)
s
i
n
(
A
ω
). Moreover, we have H
1
′
(
ω
)
=
(
B
2
-
A
2
)
s
i
n
(
A
ω
)
s
i
n
(
B
ω
)
>
0; this, together with B
>
A
≥
0 and H
1
(
0
)
=
0, gives H
1
(
ω
)
>
0. Hence, H
′
(
ω
)
>
0 for ω
∈
(
0,1
).) Therefore, it is easy to understand that r
′
ω
,
p
′
ω
>
0 for ω
∈
(
0,1
). Since r, p, and σ are positive, we finally get ∂
ω
K
>
0 for ω
∈
(
0,1
).Now, we are in a position to present one of the main results of this section.Theorem 5.
Under Hypothesis1, assume that the function f in (1) satisfies f
′
(
u
)
≤
d
(
∀
u
∈
R
) with 0
<
d
<
π
/
L
ω
∗
2, where for specified integer N
≥
2 the argument ω
∗
∈
(
0,1
] is the unique root of K
(
ω
,
N
)
=
1. Then, the N-subdomain SWR algorithm (2) with N
≥
2 is convergent. In particular, the error functions can be bounded in infinity norm in time and space, as(36)
max
1
≤
2
i
≤
N
⁡
e
2
i
2
k
+
1
·
,
·
∞
,
∞
≤
C
ρ
k
d
,
N
ξ
0
2
,
max
1
≤
2
i
+
1
≤
N
⁡
e
2
i
+
1
2
k
+
1
·
,
·
∞
,
∞
≤
C
ρ
k
d
,
N
η
0
2
,where(37)
C
=
max
i
=
1,2
,
…
,
N
⁡
max
x
∈
α
i
L
,
β
i
L
⁡
sin
⁡
x
-
α
i
L
d
sin
⁡
β
i
-
α
i
L
d
+
sin
⁡
β
i
L
-
x
d
sin
⁡
β
i
-
α
i
L
d
.Proof.
From (14), for all x
∈
[
α
i
L
,
β
i
L
] we have (38)
e
i
k
x
,
·
∞
≤
sin
⁡
x
-
α
i
L
d
sin
⁡
β
i
-
α
i
L
d
+
sin
⁡
β
i
L
-
x
d
sin
⁡
β
i
-
α
i
L
d
max
⁡
e
i
+
1
k
-
1
β
i
L
,
·
∞
,
e
i
-
1
k
-
1
α
i
L
,
·
∞
.With the constant C given above, this implies (39)
max
1
≤
2
i
≤
N
⁡
e
2
i
2
k
+
1
·
,
·
∞
,
∞
≤
C
ξ
2
k
∞
,
max
1
≤
2
i
+
1
≤
N
⁡
e
2
i
+
1
2
k
+
1
·
,
·
∞
,
∞
≤
C
η
2
k
∞
.Since the infinity norm is bounded by the spectral norm, we have (40)
max
1
≤
2
i
≤
N
⁡
e
2
i
2
k
+
1
·
,
·
∞
,
∞
≤
C
ξ
2
k
2
,
max
1
≤
2
i
+
1
≤
N
⁡
e
2
i
+
1
2
k
+
1
·
,
·
∞
,
∞
≤
C
η
2
k
2
.Then, by using ξ
2
k
2
≤
D
2
k
ξ
0
2 and η
2
k
2
≤
E
2
k
η
0
2 and Lemma 3, we get (36). Finally, by using Lemma 4 (i.e., ρ
(
d
,
N
)
<
1 for 0
<
d
<
π
/
L
ω
∗
2), convergence of the SWR algorithm in the multisubdomain case follows.Remark 6.
ForN
=
2, that is, the two-subdomain case, we have ϕ
+
2
φ
=
π; hence, K
(
ω
,
2
)
=
s
i
n
2
(
φ
ω
)
/
s
i
n
2
[
(
ϕ
+
φ
)
ω
]
=
s
i
n
2
(
φ
ω
)
/
s
i
n
2
[
(
π
-
φ
)
ω
]. Since φ
∈
(
0
,
π
/
2
), it is easy to know that K
(
ω
,
2
) is an increasing function of ω
∈
[
0,1
]; this, together with K
(
ω
,
2
)
ω
=
1
=
1, implies ω
∗
=
1. Therefore, Theorem 5 actually includes Theorem 4.1 given by Gander [1].


## 3.2.  Application to More General Nonlinear Problems

We now consider the following IBVP:(41)
∂
t
u
=
∂
x
θ
u
∂
x
u
+
f
u
,
x
,
t
∈
0
,
L
×
R
+
,
u
0
,
t
=
g
1
t
,
u
L
,
t
=
g
2
t
,
t
∈
R
+
,
u
x
,
0
=
u
0
x
,
x
∈
0
,
L
,where the functions θ and f satisfy(42)
f
′
u
≤
d
∀
u
∈
R
,
f
∈
C
1
R
,
θ
u
≥
θ
m
i
n
>
0
∀
u
∈
R
,
θ
∈
C
R
.We can also assume that θ and f depend on x and t, but this only makes a trivial difference. Here, we are interested in applying the domain decomposition strategy to (41) from time step to time step. Assume that (41) is discretized by the backward Euler method:(43)
u
n
-
Δ
t
n
∂
x
θ
u
n
∂
x
u
n
+
f
u
n
=
u
n
-
1
,where Δ
t
n denotes the step size and u
n
(
x
)
≈
u
(
t
n
,
x
). We can also consider some other time integrators, such as Trapezoidal, Runge-Kutta methods, but the analysis is similar. Now, with u
n
-
1
(
x
) known from the previous computation step, we focus on calculating u
n
(
x
) through the domain decomposition method [7, 8]:(44)
x
∈
Ω
i
:
U
i
k
x
-
Δ
t
n
∂
x
θ
U
i
k
x
∂
x
U
i
k
x
+
f
U
i
k
x
=
u
n
-
1
x
,
U
i
k
α
i
L
=
U
i
-
1
k
-
1
α
i
L
,
U
i
k
β
i
L
=
U
i
+
1
k
-
1
β
i
L
,where U
0
k
≡
g
1
(
t
n
) and U
N
+
1
k
≡
g
2
(
t
n
). Upon convergence, we get U
∞
(
x
)
=
u
n
(
x
).To analyze the convergence of the sequence{
U
j
k
}
k
=
0
∞, we need the following lemma.Lemma 7 (see [9]).
LetL
u
≔
a
u
′
′
+
b
u
′
+
c
u be a linear, elliptic operator with c
<
0 in a bounded domain Ω. Suppose that, in Ω, L
u
≥
0
(
≤
0
) with u
∈
C
2
(
Ω
)
∩
C
0
(
Ω
¯
). Then, it holds that s
u
p
x
Ω
u
≥
s
u
p
x
∈
∂
Ω
m
a
x
{
u
,
0
}
(
i
n
f
x
Ω
u
≤
i
n
f
x
∈
∂
Ω
m
i
n
{
u
,
0
}
).Define(45)
e
i
k
x
=
∫
U
i
x
U
i
k
x
θ
v
d
v
with
U
i
x
=
U
x
x
∈
Ω
i
.Then, we have(46)
∂
x
e
i
k
x
=
θ
U
i
k
x
∂
x
U
i
k
x
-
θ
U
i
x
∂
x
U
i
x
,
e
i
k
x
=
θ
U
¯
i
k
U
i
k
x
-
U
i
x
,where for the second equality we have used the mean value theorem for integrals with some U
¯
i
k lying between U
i
k and U
i. Subtracting U
i from (44) and then using (46), we get(47)
x
∈
Ω
i
:
∂
x
2
e
i
k
x
+
Δ
t
n
f
′
U
^
i
k
-
1
Δ
t
n
θ
U
¯
i
k
e
i
k
x
=
0
,
e
i
k
α
i
L
=
e
i
-
1
k
-
1
α
i
L
,
e
i
k
β
i
L
=
e
i
+
1
k
-
1
β
i
L
,where e
0
k
(
x
)
=
e
N
+
1
k
(
x
)
≡
0. Let(48)
d
^
=
Δ
t
n
d
-
1
Δ
t
n
θ
min
⁡
.Then, from (42) we have Δ
t
n
f
′
(
U
^
i
k
)
-
1
/
Δ
t
n
θ
(
U
¯
i
k
)
≤
d
^. Now, by using Lemma 7 and a similar procedure as we did in the proof of Lemma 2, it holds that(49)
e
i
k
x
≤
e
~
i
k
x
,
∀
x
∈
Ω
i
,provided d
^
<
(
π
/
L
)
2, where e
~
i
k
(
x
)
≥
0 is defined by(50)
e
~
i
k
x
=
sinh
⁡
x
-
α
i
L
-
d
^
sinh
⁡
β
i
-
α
i
L
-
d
^
e
i
+
1
k
-
1
β
i
L
+
sinh
⁡
β
i
L
-
x
-
d
^
sinh
⁡
β
i
-
α
i
L
-
d
^
e
i
-
1
k
-
1
α
i
L
.Here, for d
^
=
0 or d
^
>
0 the quantity s
i
n
h
A
-
d
^
/
s
i
n
h
B
-
d
^ should be understood as(51)
sinh
⁡
A
-
d
^
sinh
⁡
B
-
d
^
=
A
B
,
if
d
^
=
0
,
sinh
⁡
A
-
d
^
sinh
⁡
B
-
d
^
=
sin
⁡
A
d
^
sin
⁡
B
d
^
,
if
d
^
>
0
.Define(52)
r
^
=
sinh
⁡
l
-
d
^
sinh
⁡
L
+
N
-
1
l
/
N
-
d
^
,
p
^
=
sinh
⁡
L
-
l
/
N
-
d
^
sinh
⁡
L
+
N
-
1
l
/
N
-
d
^
,
ρ
^
d
^
,
N
=
p
^
2
+
2
p
^
r
^
cos
⁡
π
N
+
r
^
2
.Then, following the analysis in Section 3.1, Theorem 8 can be derived directly.Theorem 8.
Letθ and f satisfy (42). Let d
^
=
Δ
t
n
d
-
1
/
Δ
t
n
θ
m
i
n
<
(
π
/
L
ω
∗
)
2, where ω
∗
∈
(
0,1
] is the unique root of K
(
ω
,
N
)
=
1 and K is defined by (16a). Then, for N
≥
2 iterations (44) are convergent and the error functions {
e
i
k
(
x
)
}
i
=
1,2
,
…
,
N defined by (45) uniformly decay to zero with a rate ρ
^
(
d
^
,
N
)
<
1.For specifiedN, l, d, θ
m
i
n, and L, Theorem 8 can be used to select a safe step size Δ
t
n and therefore it is instructive for designing anadaptive-step-size computation.Remark 9 (monotonicity ofρ
^).
At the end of this section, we claim thatρ
^ is an increasing function of d
^ and N and is a decreasing function of l. We show the increasing monotonicity with respect to d
^ and the others can be proved similarly. Indeed, for d
^
∈
(
0
,
(
π
/
L
)
2
) it holds(53)
r
^
=
sin
⁡
l
d
^
sin
⁡
L
+
N
-
1
l
/
N
d
^
,
p
^
=
sin
⁡
L
-
l
/
N
d
^
sin
⁡
L
+
N
-
1
l
/
N
d
^
,and we have already proved in Lemma 4 (Part II) that both r
^ and p
^ are increasing functions of d
^ (and therefore they are increasing functions of d
^). It remains to consider d
^
≤
0. Let B
>
A
>
0 be two constants and H
(
z
)
=
s
i
n
h
(
A
z
)
/
s
i
n
h
(
B
z
). Then, it is easy to get sign
⁡
H
′
z
=
sign
⁡
(
H
1
(
z
)
), where (54)
H
1
z
=
A
cosh
⁡
A
z
sinh
⁡
B
z
-
B
cosh
⁡
B
z
sinh
⁡
A
z
.We have H
1
′
(
z
)
=
(
A
2
-
B
2
)
s
i
n
h
(
A
z
)
s
i
n
h
(
B
z
)
<
0
(
∀
z
>
0
) and this, together with H
1
(
0
)
=
0, implies H
′
(
z
)
>
0 for z
>
0. Hence, for d
^
≤
0 the arguments r
^ and p
^ are also increasing functions of d
^. Since r
^
,
p
^
≥
0, it is easy to understand that ρ
^ is an increasing function of d
^.


## 4.  Numerical Results

In this section, we present numerical results to verify the theoretical predictions analyzed at the continuous level. We consider the following linear reaction diffusion equation:(55)
∂
t
u
=
∂
x
2
u
+
d
u
+
t
2
s
i
n
t
x
,
x
,
t
∈
0,1
×
0,20
,
u
0
,
t
=
u
1
,
t
=
0
,
t
∈
0,20
,
u
x
,
0
=
0
,
x
∈
0,1
.The Laplace operator ∂
x
2 is discretized by the centered finite difference scheme with Δ
x
=
1
/
200 and the resulting system of ODEs is solved by the backward Euler method with step size Δ
t
=
1
/
100. The overlap size l is chosen as l
=
0.05. Then, according to Theorem 5, the allowed maximal choice of d, which theoretically guarantees convergence of the SWR algorithm, is d
m
a
x
=
4.7762. In Figure 2, for two choices of the problem parameter d: d
=
4.7762 and d
=
-
25, we compare the convergence rate of the SWR algorithm in the case of 4 subdomains. The left column corresponds to d
=
d
m
a
x
=
4.7762 and the right column corresponds to d
=
-
25. From top to bottom, we show the randomly chosen initial guess, the 5th iterate, the 10th iterate, and the reference solution. (The reference solution is defined by the so-calledmonodomain solution, which corresponds to the numerical solution computed in the global space-time domain, by using the same discretization.) We see that for d
=
-
25 the iterate after 5 iterations is very close to the reference solution, while for d
=
d
m
a
x
=
4.7762 the difference between the iterate and the reference solution is obviously visible after 10 iterations. A complete comparison is shown in Figure 3.Figure 2
Approximation of the iterates generated by the SWR algorithm to the reference solution for two problems parameters:d
=
d
m
a
x
=
4.7762 (left column) and d
=
-
25 (right column). From top to bottom: the randomly chosen initial guess, the 5th iterate, the 10th iterate, and the reference solution.
(a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)Figure 3
Comparison of the convergence rates of the 4-subdomain SWR algorithm for (55) with two problem parameters d: d
=
d
m
a
x
=
4.7762 (solid line) and d
=
-
25 (dash-dot line).To finish this section, we investigate how the convergence rate of the SWR algorithm depends onN, the number of subdomains. Let L
=
1 and the overlap size l
=
0.05. Then, for two choices of the problem parameter d we first show in Figure 4 the convergence factor ρ
(
d
,
N
) as a function of N. We see that a smaller problem parameter leads to smaller convergence factor. This confirms what we have observed in Figures 2 and 3. Moreover, for both d
=
d
m
a
x
=
4.7762 and d
=
-
25 the convergence factor increases as N increases; that is, the convergence factor deteriorates when the number of subdomains increases. Next, we show in Table 1 the measured iteration number for the SWR algorithm when the error between the iterate and reference solution is less than 1
0
-
5; that is,(56)
max
j
=
1,2
,
…
,
N
⁡
max
x
∈
Ω
j
,
t
∈
0,20
⁡
u
j
k
x
,
t
-
u
x
,
t
≤
1
0
-
5
.We see that the results in Table 1 confirm the theoretical prediction by Figure 4 very well.Table 1
To reach (56), the measured iteration number k for each d and N (× denotes divergence).
N
=
2
N
=
3
N
=
4
N
=
5
N
=
6
N
=
7
N
=
8
N
=
9
N
=
10
d
=
d
max
⁡
131
301
465
×
×
×
×
×
×
d
=
-
25
35
48
62
79
96
115
135
155
176Figure 4
Forl
=
0.05, L
=
1, and three choices of the problem parameter d, dependence of the convergence factor ρ
(
d
,
N
) of the Schwarz waveform relaxation algorithm (see (16a)) on N, the number of subdomains.


## 5. Conclusions

We have analyzed the convergence properties of the Schwarz waveform relaxation (SWR) algorithm for a class of representative nonlinear parabolic problems, in the case of many subdomains. Dependence of the convergence rate on the number of subdomains and problem parameters is investigated. By using this “dependence,” we can get sufficient condition guaranteeing convergence of the algorithm and estimate the convergence rate under specified problem/algorithm parameters. For example, for givenN (the number of subdomains) we can use Theorem 5 to get the allowed upper bound of f
′
(
u
), that is, d
m
a
x, which guarantees that the SWR algorithm is convergent if m
a
x
u
∈
R
f
′
(
u
)
≤
d
m
a
x. Numerical result shows that such a d
m
a
x predicted by Theorem 5 is sharp. We also presented a generalization of the analysis to more general nonlinear parabolic problems, where multisubdomain decomposition is used for each time step (see Theorem 8). Another contribution of this work is the special technique for proving Theorems 5 and 8, which, as we will show in our forthcoming paper, plays a central role for analyzing the convergence properties of the SWR algorithm with more efficient transmission conditions (e.g., the extensively studied Robin transmission conditions) in the nonlinear and multisubdomain situation.



---

*Source: 612862-2015-08-17.xml*