Geiser J. Decomposition Methods for Differential Equations: Theory and Applications

Подождите немного. Документ загружается.

106Decomposition Methods for Diﬀerential Equations Theory and Applications

REMARK 5.4 We can generalize our results for n decomposed do-

mains. We obtain the same results for the generalized semigroup A : X

→

REMARK 5.5 We require twice the number of iterations due to the

two partitions (i.e., i for time, j for space). Also, for higher-order accuracy

more work is needed, for example, 2(2m+1) iterations for O(τ

2m+1

) accuracy.

5.2 Schwarz Waveform-Relaxation Methods

5.2.1 Introduction

In the next chapter we discuss the methods for domain decomposition meth-

ods.

We motivate our studying on complex models with coupled processes (e.g.,

transport and reaction equations with nonlinear parameters). The ideas for

these models came from the background of the simulation of heat transport

in engineering apparatus (e.g., crystal-growth, cf. [95]), or the simulation of

chemical reaction and transport (e.g., in bio-remediation or waste dispos-

als, cf. [94]). In the past, many software tools have been developed for one-

dimensional and simple physical problems (e.g., one-dimensional transport

codes or convection-codes based on ODEs). The future interests will be the

coupling of standard software tools to more complex code, for solving multi-

dimensional and multiphysical problems.

The mathematical equations are given by

∂

Ru+ ∇·(vu − D∇u)=f(u) , in Ω × (0,T), (5.34)

u(x, 0) = u

, (Initial Condition), (5.35)

u(x, t)=u

, on ∂Ω × (0,T) , (Dirichlet-Boundary Condition), (5.36)

f(u)=u

, chemical reaction and p>0, (5.37)

f(u)=

1 − u

, bio remediation, (5.38)

f(u)=f (u

) , heat induction. (5.39)

The unknown u = u(x, t)isconsideredinΩ× (0,T) ⊂ R

× R,thespace

dimension is given by d. The parameter R ∈ R

is a constant and named

as retardation factor. The parameters u

∈ R

are constants and used

as initial- and boundary-parameter, respectively. The parameter f (u)isa

nonlinear function, for example, bio remediation or chemical reaction. D

is the thermal conductivity tensor or Scheidegger diﬀusion-dispersion tensor,

Spatial Decomposition Methods 107

and v is the velocity.

Our aim is to present a new method based on a mixed discretization method

with fractional splitting and domain decomposition methods for an eﬀective

solving of strong coupled parabolic diﬀerential equations.

In the next section we discuss the fractional splitting methods for solving

our equations.

Now we introduce the domain-decomposition methods as the next idea for

splitting methods to decompose complex domains and solve them eﬀectively

in an adaptive method.

5.3 Overlapping Schwarz Waveform Relaxation for the

Solution of Convection-Diﬀusion-Reaction Equation

The ﬁrst known method for solving a partial diﬀerential equation over over-

lapped domains is the Schwarz method due to [180] in 1869. The method has

regained its popularity after the development of the computational numerical

algorithms and the computer architecture, especially the parallel processing

computations.

Further techniques have been developed for the general cases when the

domains are overlapped and nonoverlapped. For each class of methods there

are some interesting features, and both share the same concepts on how to

deﬁne the interface boundary conditions over the overlapped or along the

nonoverlapped subdomains. The general solution methods over the whole

subdomains together with the interface boundary conditions estimations are

either iterative or noniterative methods.

For the nonoverlapping subdomains, the interfaces are predicted using ex-

plicit scheme and the problem is solved over each subdomain independently.

This type of method is of the noniterative type, but it has drawbacks regard-

ing the stability condition for the interface prediction by the explicit method

and the solution by the implicit scheme or any other unconditional stable

ﬁnite diﬀerence scheme [57].

For the overlapping subdomains, the determination of the interface bound-

ary condition is deﬁned using predictor corrector type of method. The predic-

tor will provide an estimation of the boundary condition while the correction

is performed from the updated solution over the subdomains. This class of

algorithms is of an iterative type with the advantage that the stability of the

solution by any unconditional diﬀerence approximation will not be aﬀected

by the predicted interface values.

In this work we will consider the overlapping type of domain decomposition

method for solving the studied models of constant coeﬃcients, decoupled and

coupled systems solved using the ﬁrst-order operator-splitting algorithm with

108Decomposition Methods for Diﬀerential Equations Theory and Applications

backward Euler diﬀerence scheme. The most recent method in this ﬁeld is

the overlapping Schwarz waveform relaxation scheme due to [77] and [107].

Overlapping Schwarz waveform relaxation is the name for a combination of

two standard algorithms, Schwarz alternating method and waveform-relaxation

algorithm to solve evolution problems in parallel. The method is deﬁned by

partitioning the spatial domain into overlapping subdomains, as in the classi-

cal Schwarz method. However, on subdomains, time-dependent problems are

solved in the iteration and thus the algorithm is also of waveform-relaxation

type. Furthermore, the problem is solved using the operator splitting of ﬁrst-

order over each subdomain. The overlapping Schwarz waveform relaxation is

introduced in [107] and independently in [77] for the solver method of evolu-

tion problems in a parallel environment with slow communication links. The

idea is to solve over several time-steps before communicating information to

the neighboring subdomains and updating the calculated interface boundary

conditions for the overlapped domains.

These algorithms contrast with the classical approach in domain decompo-

sition for evolution problems, where time is ﬁrst discretized uniformly using

an implicit discretization and then at each time-step a problem in space only

is solved using domain decomposition, see for example [35], [36], and [157].

Furthermore, in this work the operator-splitting method will be considered

by using Crank-Nicolson (CN) or an implicit Euler method for the time dis-

cretization. The main advantage in considering the overlapping Schwarz wave

form relaxation method is the ﬂexibility that we could solve over each subdo-

main with a diﬀerent time-step and diﬀerent spatial steps in the whole time

interval. In this section we will consider the Schwarz waveform relaxation

to solve scalar, and systems of convection-diﬀusion-reaction equation. For

the systems of convection-diﬀusion-reaction equation, we study the decoupled

case, i.d. m scalar equations and the coupled case, i.d. m equations coupled

by the reaction terms.

5.3.1 Overlapping Schwarz Waveform Relaxation for the Scalar

Convection-Diﬀusion-Reaction Equation

We consider the convection-diﬀusion-reaction equation, given by

= Du

− vu

− λu , (5.40)

deﬁned on the domain Ω = [0,L]forT =[t

], with the following initial

and boundary conditions:

u(0,t)=f

(t),u(L, t)=f

(t),u(x, t

)=u

To solve the model problem using the overlapping Schwarz waveform re-

laxation method, we subdivide the domain Ω in two overlapping subdomains

=[0,L

]andΩ

=[L

,L], where L

and Ω

=[L

]isthe

overlapping region for Ω

and Ω

Spatial Decomposition Methods 109

To start the waveform relaxation algorithm, we ﬁrst consider the solution

of the model problem (5.40) over Ω

and Ω

as follows:

= Dv

− vv

− λv over Ω

,t∈ [T

v(0,t)=f

(t) ,t∈ [T

v(L

,t)=w(L

,t) ,t∈ [T

v(x, t

)=u

x ∈ Ω

(5.41)

= Dw

− vw

− λw over Ω

,t∈ [T

w(L

,t)=v(L

,t) ,t∈ [T

w(L, t)=f

(t) ,t∈ [T

w(x, t

)=u

x ∈ Ω

(5.42)

where v(x, t)=u(x, t)|

and w(x, t)=u(x, t)|

Then the Schwarz waveform relaxation is given by

k+1

= Dv

k+1

− vv

k+1

− λv

k+1

over Ω

,t∈ [T

k+1

(0,t)=f

(t) ,t∈ [T

k+1

,t)=w

,t) ,t∈ [T

k+1

(x, t

)=u

x ∈ Ω

(5.43)

k+1

= Dw

k+1

− vw

k+1

− λw

k+1

over Ω

,t∈ [T

k+1

,t)=v

,t) ,t∈ [T

k+1

(L, t)=f

(t) ,t∈ [T

k+1

(x, t

)=u

x ∈ Ω

(5.44)

We are interested in estimating the decay of the error of the solution over

the overlapping subdomains by the overlapping Schwarz waveform relaxation

method.

Let us assume e(x, t)=u(x, t) −v(x, t), and d(x, t)=u(x, t)−w(x, t)isthe

error of (5.43) and (5.44) over Ω

and Ω

, respectively. The corresponding

diﬀerential equations satisfying e(x, t)andd(x, t)aregivenby

k+1

= De

k+1

− ve

k+1

− λe

k+1

over Ω

,t∈ [T

k+1

(0,t)=0,t∈ [T

k+1

,t)=d

,t) ,t∈ [T

k+1

(x, t

)=0 x ∈ Ω

(5.45)

k+1

= Dd

k+1

− vd

k+1

− λd

k+1

over Ω

,t∈ [T

k+1

,t)=e

,t) ,t∈ [T

k+1

(L, t)=0,t∈ [T

k+1

(x, t

)=0,x∈ Ω

(5.46)

We deﬁne for bounded functions h(x, t):Ω× [0,T] → R the norm

||h(., .)||

∞

:= sup

x∈Ω,t∈[t

]

|h(x, t)|.

110Decomposition Methods for Diﬀerential Equations Theory and Applications

The convergence and error bound of e

k+1

and d

k+1

are presented in Theorem

5.2.

THEOREM 5.2

Let e

k+1

and d

k+1

be the error from the solution of the subproblems (5.41)

and (5.42) by Schwarz waveform relaxation over Ω

and Ω

, respectively, then

||e

k+2

,t)||

∞

≤ γ||e

,t)||

∞

and

||d

k+2

,t)||

∞

≤ γ||d

,t)||

∞

where

γ =

sinh(βL

)

sinh(βL

)

sinh(β(L

− L))

sinh(β(L

− L))

PROOF

For the error e

k+1

and d

k+1

, consider the following diﬀerential equations

deﬁned by ˆe

k+1

and

k+1

given by

ˆe

k+1

= Dˆe

k+1

− vˆe

k+1

− λˆe

k+1

over Ω

,t∈ [T

ˆe

k+1

(0,t)=0,t∈ [T

ˆe

k+1

,t)=||d

,t)||

∞

,t∈ [T

ˆe

k+1

(x, t

)=e

(x−L

)α

sinh(βx)

sinh(βL

)

||d

,t)||

∞

,x∈ Ω

(5.47)

and

k+1

= D

k+1

− v

k+1

− λ

k+1

over Ω

,t∈ [T

k+1

,t)=||e

,t)||

∞

,t∈ [T

k+1

(L, t)=0,t∈ [T

k+1

(x, t

)=e

(x−L

)α

sinh β(x−L)

sinh β(L

−L)

||e

,t)||

∞

,x∈ Ω

(5.48)

where α =

and β =

√

+4Dλ

The solution to (5.47) and (5.48) is the steady state solution given by

ˆe

k+1

(x)=e

(x−L

)α

sinh(βx)

sinh(βL

)

||d

,t)||

∞

and

k+1

(x)=e

(x−L

)α

sinh β(x − L)

sinh β(L

− L)

||e

,t)||

∞

respectively.

Spatial Decomposition Methods 111

Hence, deﬁne E(x, t)=ˆe

k+1

− e

k+1

, and therefore,

− DE

+ vE

+ λE ≥ 0 , over Ω

,t∈ [T

E(0,t)=0,t∈ [T

E(L

,t) ≥ 0 ,t∈ [T

E(x, t

) ≥ 0 ,x∈ Ω

(5.49)

and it satisﬁes the positivity lemma by Pao (or the maximum principle theo-

rem), see [164]; therefore,

E(x, t) ≥ 0

that is,

k+1

|≤ˆe

k+1

for all (x, t), and similarly we conclude that

k+1

|≤

k+1

for all (x, t).

Then

k+1

(x, t)|≤e

(x−L

)α

sinh(βx)

sinh(βL

)

||d

,t)||

∞

, (5.50)

and

k+1

(x, t)|≤e

(x−L

)α

sinh β(x − L

)

sinh β(L

− L)

||e

,t)||

∞

. (5.51)

Evaluate d

(x, t)atL

,t)|≤

sinh β(L

− L)

sinh β(L

− L)

||e

k−1

,t)||

∞

, (5.52)

and substitute in (5.50) implies that

k+1

(x, t)|≤e

(x−L

)α

sinh(βx)

sinh(βL

)

−L

)α

sinh β(L

− L)

sinh β(L

− L)

||e

k−1

,t)||

∞

therefore

k+1

,t)|≤e

−L

)α

sinh(βL

)

sinh(βL

)

−L

)α

sinh β(L

− L)

sinh β(L

− L)

||e

k−1

,t)||

∞

that is,

k+2

,t)|≤

sinh(βL

)

sinh(βL

)

sinh β(L

− L)

sinh β(L

− L)

||e

,t)||

∞

112Decomposition Methods for Diﬀerential Equations Theory and Applications

Similarly for d

k+1

(x, t) we conclude that

k+2

,t)|≤

sinh(βL

)

sinh(βL

)

sinh β(L

− L)

sinh β(L

− L)

||d

,t)||

∞

Theorem 5.2 shows that the convergence of of the overlapping Schwarz

method depends on γ =

sinh(βL

)

sinh(βL

)

sinh β(L

−L)

sinh β(L

−L)

. Due to the characteristic of the

sinh function, we will have sharp decay of the error for any L

, and also

for a large amount of overlapping.

5.3.2 Overlapping Schwarz Waveform Relaxation for Decou-

pled System of Convection-Diﬀusion-Reaction Equa-

tion

In the following part of this section, we are going to present, overlap-

ping Schwarz waveform-relaxation method deﬁned for a system of convection-

diﬀusion-reaction equation, such that for a system deﬁned by u

(x, t)for

i =1,...,I it is given by

i,t

= D

i,xx

− v

i,x

− λ

over Ω,t∈ [T

,t)=f

1,i

(t),t∈ [T

(L, t)=f

2,i

(L, t),t∈ [T

(x, t

)=u

,x∈ Ω.

(5.53)

The considered system (5.53) is already deﬁned over the spatial domain Ω =

{0 <x<L} and the overlapping Schwarz over relaxation method is con-

structed over the overlapping subdomains Ω

= {0 <x<L

} and Ω

<x<L} L

with an overlapping size (L2 − L1). In this work

we are going to consider two types of systems of convection-diﬀusion-reaction

equation, the decoupled and coupled systems.

To construct the waveform-relaxation algorithm for (5.53), we will consider

the case where I = 2, and we ﬁrst consider the solution of (5.53) over Ω

and

as follows:

i,t

= D

i,xx

− v

i,x

− λ

over Ω

,t∈ [T

,t)=f

1,i

(t),t∈ [T

(L, t)=f

2,i

(L, t),t∈ [T

(x, t

)=u

,x∈ Ω

(5.54)

i,t

= D

i,xx

− v

i,x

− λ

over Ω

,t∈ [T

,t)=f

1,i

(t),t∈ [T

(L, t)=f

2,i

(L, t),t∈ [T

(x, t

)=u

,x∈ Ω

(5.55)

Spatial Decomposition Methods 113

where v

(x, t)=u

(x, t)|Ω

and w

(x, t)=u

(x, t)|Ω

Then the overlapping Schwarz waveform-relaxation method for the decoupled

system over the two overlapped subdomains, Ω

and Ω

,isgivenby

k+1

1,t

= D

k+1

1,xx

− v

k+1

1,x

− λ

k+1

over Ω

,t∈ [T

k+1

,t)=f

1,1

(t),t∈ [T

k+1

,t)=w

,t),t∈ [T

k+1

(x, t

)=u

,x∈ Ω

(5.56)

k+1

1,t

= D

k+1

1,xx

− v

k+1

1,x

− λ

k+1

over Ω

,t∈ [T

k+1

,t)=v

,t),t∈ [T

k+1

(L, t)=f

1,2

(t),t∈ [T

k+1

(x, t

)=u

,x∈ Ω

(5.57)

for the system deﬁned by u

for i =1, and for the system deﬁned by u

,i=2,

it is given by

k+1

2,t

= D

k+1

2,xx

− v

k+1

2,x

− λ

k+1

over Ω

,t∈ [T

k+1

,t)=f

2,1

(t),t∈ [T

k+1

,t)=w

,t),t∈ [T

k+1

(x, t

)=u

,x∈ Ω

(5.58)

k+1

2,t

= D

k+1

2,xx

− v

k+1

2,x

− λ

k+1

over Ω

,t∈ [T

k+1

,t)=v

,t),t∈ [T

k+1

(L, t)=f

2,2

(t),t∈ [T

k+1

(x, t

)=u

x ∈ [T

(5.59)

where k represents the iteration index.

Deﬁne e

k+1

= u − v

k+1

and d

k+1

= u − w

k+1

to be the errors from the

solution given by (5.56)–(5.57) and (5.58)–(5.59) over Ω

and Ω

, respectively,

and for i =1, 2.

The corresponding diﬀerential equations satisfying e

k+1

and d

k+1

over Ω

and Ω

for i =1, 2, respectively, are given by

k+1

1,t

= D

k+1

1,xx

− v

k+1

1,x

− λ

k+1

over Ω

,t∈ [T

k+1

,t)=f

1,1

(t),t∈ [T

k+1

,t)=d

,t),t∈ [T

k+1

(x, t

)=u

,x∈ Ω

(5.60)

k+1

1,t

= D

k+1

1,xx

− v

k+1

1,x

− λ

k+1

over Ω

,t∈ [T

k+1

,t)=e

,t),t∈ [T

k+1

(L, t)=f

1,2

(t),t∈ [T

k+1

(x, t

)=u

x ∈ [T

(5.61)

114Decomposition Methods for Diﬀerential Equations Theory and Applications

for i =1,andfori =2,

k+1

2,t

= D

k+1

2,xx

− v

k+1

2,x

− λ

k+1

over Ω

,t∈ [T

k+1

,t)=f

2,1

(t),t∈ [T

k+1

,t)=d

,t),t∈ [T

k+1

(x, t

)=u

,x∈ Ω

(5.62)

k+1

2,t

= D

k+1

2,xx

− v

k+1

2,x

− λ

k+1

over Ω

,t∈ [T

k+1

,t)=e

,t),t∈ [T

k+1

(L, t)=f

2,2

(t),t∈ [T

k+1

(x, t

)=u

x ∈ [T

(5.63)

The convergence and the error bound for the solution of (5.56)–(5.57) and

(5.58)–(5.59) are given in Theorem 5.3.

THEOREM 5.3

Let e

k+1

and d

k+1

(i =1, 2) be the error of the subproblems deﬁned by

the diﬀerential equations (5.60)–(5.61) and (5.62)–(5.63) over Ω

and Ω

respectively, then

||e

k+2

,t)||

∞

≤ γ

||e

,t)||

∞

, (5.64)

and

||d

k+2

,t)||

∞

≤ γ

||d

,t)||

∞

, (5.65)

where

sinh(β

)

sinh(β

)

sinh(β

− L))

sinh(β

− L))

, (5.66)

for i =1, 2.

PROOF

The proof will follow by utilization the proof given by Theorem 5.2.

Let e

and d

be the error of the approximated solutions u

over Ω

and Ω

for i =1, 2, respectively.

Following the proof presented for Theorem 5.2 for each of the error dif-

ferential equations (5.60)–(5.61) and (5.62)–(5.63), then we will conclude the

following relation:

||e

k+2

,t)||

∞

≤ γ

||e

,t)||

∞

, (5.67)

and

||d

k+2

,t)||

∞

≤ γ

||d

,t)||

∞

, (5.68)

Spatial Decomposition Methods 115

where

sinh(β

)

sinh(β

)

sinh(β

− L))

sinh(β

− L))

, (5.69)

and



+4D

for i =1, 2.

5.3.3 Overlapping Schwarz Waveform Relaxation for Cou-

pled System of Convection-Diﬀusion-Reaction Equa-

tion

In the following part we are going to present the convergence and the error

bound of the overlapping Schwarz waveform relaxation for the solution of the

coupled system of convection-diﬀusion-reaction deﬁned by two functions u

and u

. The coupling criterion in this case of study is imposed within the

source term of the second solution component. The considered system with

the solution u

and u

is given by

1,t

= D

1,xx

− v

1,x

− λ

over Ω = {0 <x<L},t∈ [T

,t)=f

1,1

(t),t∈ [T

(L, t)=f

1,2

(t),t∈ [T

(x, t

)=u

(5.70)

for u

,andforu

is given by

2,t

= D

2,xx

− v

2,x

− λ

+ λ

over Ω,t∈ [T

]

,t)=f

2,1

(t),t∈ [T

(L, t)=f

2,2

(t),t∈ [T

k+1

(x, t

)=u

(5.71)

In (5.71) the coupling appeared in the source term and is deﬁned by the

parameter λ

with the ﬁrst component u

. The strength or the bound of the

coupling and the contribution are related to the value of the scalar deﬁned

by λ

. The coupled case (5.71) is reduced to the decoupled case (5.53), by

assuming λ

=0.

The overlapping Schwarz waveform relaxation for (5.70) over Ω

and Ω

given by

k+1

1,t

= D

k+1

1,xx

− v

k+1

1,x

− λ

k+1

over Ω

,t∈ [T

k+1

,t)=f

1,1

(t),t∈ [T

k+1

,t)=w

,t),t∈ [T

k+1

(x, t

)=u

,x∈ Ω

(5.72)