Méthodes de décomposition de domaine de type Schwarzfboyer/_media/enseignements/m2... · Par ailleurs, on voit que l’algorithme est complètement déterminé par la seule valeur

Méthodes de décomposition de domainede type Schwarz

Franck Boyer - Florence Hubert

Master 2ième année - Mathématiques et Applications

Aix-Marseille université

12 février 2014

ii

F. BOYER, F. HUBERT - VERSION DU 12 FÉVRIER 2014

TABLE DES MATIÈRES iii

TABLE DES MATIÈRES

I Introduction aux méthodes de Schwarz 11 Méthodes avec recouvrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.1 Principe général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Exemples en 1D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 La preuve de convergence originale de Schwarz . . . . . . . . . . . . . . . . . . . . . 41.4 La preuve variationnelle de P.L. Lions . . . . . . . . . . . . . . . . . . . . . . . . . . 51.5 Formalisme algébrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Méthode sans recouvrement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.1 Principe général . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172.2 Exemples en 1D et 2D. Notion de méthode optimale . . . . . . . . . . . . . . . . . . 182.3 La preuve de convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19


iv TABLE DES MATIÈRES


1

Chapitre I

INTRODUCTION AUX MÉTHODES DESCHWARZ

Basiquement les méthodes de décomposition de domaine de type Schwarz consiste à remplacer la résolutiond’une EDP posée sur un domaine Ω potentiellement gros et compliqué par une succession de résolutions de lamême EDP sur des sous-domaines de Ω, notés Ωi, supposément plus simples, plus petits, etc ...

Evidemment, ceci ne peut se faire tout à fait aisément et il s’agit de procéder à des résolutions itératives surles sous-domaines, choisies de telle sorte que la solution exacte du problème complet soit obtenue à conver-gence.

Historiquement ces méthodes ont été introduites pour démontrer d’un point de vue théorique l’existence desolutions au problème de Dirichlet sur des domaines plus complexes que ceux pour lesquels un calcul expliciteest possible (disque, carré, ...).

Aujourd’hui, ces méthodes sont plutôt utilisées à des fins numériques (ou bien sur le problème continuavant discrétisation, ou bien directement sur le problème discrétisé, voire même directement sur la matrice duproblème) afin d’accélérer la résolution numérique des problèmes, ou même de permettre un calcul parallèledes solutions.

Dans cette courte présentation, on va se baser sur le problème modèle suivant−∆u = f, dans Ω

u = g, sur ∂Ω.(I.1)

1 Méthodes avec recouvrement

On commence par étudier le cas où les sous-domaines de Ω se recouvrent, par exemple de l’une des deuxfaçons indiquées dans la figure I.1.

On note γ12 (resp. γ21) la partie du bord de ∂Ω1 (resp. ∂Ω2) qui est contenue dans Ω2 (resp. Ω1).


2 Chapitre I. Introduction aux méthodes de Schwarz

Ω1 Ω2

(a) Les interfaces sont disjointes

Ω1 Ω2

(b) Les interfaces se croisent

FIGURE I.1: Décomposition du carré unité en deux sous-domaines qui se recouvrent

1.1 Principe généralEtant donnée une parition de Ω de la forme donnée dans la figure I.1, l’algorithme de Schwarz le plus

élémentaire consiste à construire des suites (u1n)n ⊂ H1(Ω1) et (u2

n)n ⊂ H1(Ω2) de la façon suivante

• Choisir des initialisations u10 et u2

0.

• Pour tout n ≥ 0, effectuer de façon successive :

– Calcul de u1n+1 ∈ H1(Ω1) solution du problème suivant

−∆u1n+1 = f, dans Ω1

u1n+1 = g, sur ∂Ω ∩ ∂Ω1,

u1n+1 = u2

n, sur γ12.

(I.2)

– Calcul de u2n+1 ∈ H1(Ω1) solution du problème suivant

−∆u2n+1 = f, dans Ω2

u2n+1 = g, sur ∂Ω ∩ ∂Ω2,

u2n+1 = u1

n+1, sur γ21.

(I.3)

• S’arrêter à convergence (si celle-ci se produit !), i.e. quand u1n et u2

n sont suffisamment proches surΩ1 ∩ Ω2 par exemple.

Remarquons que l’étude de la convergence peut toujours se ramener au cas f = 0 et g = 0 en soustrayantla (restriction de la) solution limite recherchée u de toutes les valeurs de u1

n et u2n. Le problème revient donc

à savoir si, en partant de données initiales non nulles u10 et u2

0, l’algorithme précédent (avec f = 0 et g = 0)fournit bien deux suites qui convergent vers 0.

Dans toute la suite nous allons donc supposer f = 0 et g = 0.Par ailleurs, on voit que l’algorithme est complètement déterminé par la seule valeur de la donnée initiale

u20 sur l’interface γ12 et qu’au bout d’une itération complète, on obtient une valeur de la trace de u2

1 sur γ12.L’algorithme peut donc être compris comme une itération de la fonction qui à une trace sur γ12 associe unenouvelle trace sur γ12 obtenue en résolvant successivement deux problèmes elliptiques.

1.2 Exemples en 1DOn va commencer par essayer de comprendre la situation en dimension 1 d’espace.

1.2.1 Le problème de Laplace

On prend donc Ω =]0, 1[, Ω1 =]0, γ12[ et Ω2 =]γ21, 1[. Si on note α la valeur de u2(γ12) au début del’algorithme, on peut calculer aisément

u1(x) =αx

γ12, ∀x ∈ Ω1,


1. Méthodes avec recouvrement 3

ce qui donne la valeur de la trace transmise à Ω2 : u1(γ21) = αγ21γ12

et permet la résolution du problème dansΩ2

u2(x) =αγ21

γ12

1− x1− γ21

, ∀x ∈ Ω2.

On obtient, à la fin de l’itération

u2(γ12) = αγ21

γ12

1− γ12

1− γ21.

Ainsi, l’ensemble de l’algorithme revient à multiplier α par le nombre

k =γ21

γ12

1− γ12

1− γ21= 1− γ12 − γ21

γ12(1− γ21).

On observe que 0 < k < 1 dès lors que les deux sous-domaines se recouvrent (i.e. γ21 < γ12) et donc quela méthode itérative va converger de façon géométrique de raison k. Observons aussi que la raison tend vers 1quand la taille du recouvrement γ12 − γ21 tend vers 0.

Les conclusions de cette étude sont que la convergence a bien lieu mais qu’elle se dégrade de façon impor-tante quand la taille du recouvrement tend vers 0.

De plus, il est clair que si le recouvrement est nul, la méthode est stationnaire et ne peut en aucun casconverger.

1.2.2 Un problème un peu plus général. En route vers le 2D.

Pour des raisons qui apparaîtrons clairement un peu plus loin il est instructif de procéder aux mêmes calculsmais pour l’opérateur différentiel −u′′ + ω2u au lieu de −u′′.

Tous calculs faits, on trouve également une convergence géométrique de la méthode de raison

k(ω) =sinh(ω(1− γ12)) sinh(ωγ21)

sinh(ω(1− γ21)) sinh(ωγ12).

Ce nombre est bien toujours compris entre 0 et 1 ce qui prouve la convergence. Quand ω → 0, on retrouve lecas précédent mais si on étudie la fonction ω 7→ k(ω), alors on observe que c’est une fonction décroissante deω et qui converge vers 0 exponentiellement vite quand ω → +∞.

Ainsi, pour un choix de sous-domaines fixé, la méthode converge d’autant plus vite que la fréquence ω estgrande.

Ceci a des conséquences sur la compréhension de la méthode en dimension 2. Considérons la situation dela figure suivante où Ω est le carré unité et Ω1 =]0, γ12[×]0, 1[ et Ω2 =]γ21, 1[×]0, 1[.

Ω1 Ω2

γ12γ21

Dans cette géométrie particulière, on peut effectuer une transformée de Fourier dans la variable y de u1 etu2, ce qui revient à regarder les équations vérifiées par les quantités

v1k : x 7→∫ 1

0

u1(x, y) sin(kπy) dy, et v2k : x 7→∫ 1

0

u2(x, y) sin(kπy) dy.

On obtient−v′′1k + k2π2v1k = 0, dans ]0, γ12[,

−v′′2k + k2π2v2k = 0, dans ]γ21, 1[.



On se trouve donc dans la situation décrite ci-dessus avec une fréquence ω = kπ qui dépend donc de k.En utilisant les résultats précédents, on observe que le taux de convergence de la méthode à k fixé est

d’autant meilleur que k est grand, ce qui signifie d’une part que la méthode est bien convergente en 2D (écrireen Fourier la convergence) et que d’autre part les hautes fréquences en y convergent beaucoup plus vite que lesbasses fréquences. C’est une propriété fondamentale de ce type de méthodes.

Ainsi, on peut coupler la méthode à un solveur basse fréquence en y.

1.3 La preuve de convergence originale de SchwarzH. Schwarz a démontré la convergence de cette méthode dans un cadre assez général en utilisant le principe

du maximum dont nous rappelons une conséquence ici.

Théorème I.1

Si w1 est solution de ∆w1 = 0 dans Ω1 avec w1 = 1 sur γ12 et w1 = 0 sur ∂Ω1 \ γ12, alors w1

est continue sur Ω1 sauf possiblement sur ∂Ω ∩ γ12 et de plus elle ne peut atteindre son maximumà l’intérieur de Ω1.

On peut dès lors étudier la convergence de la méthode de Schwarz dans le cas de la Figure I.1a.Soit v : γ12 → R la trace sur γ12 de la donnée initiale de la composante u2.Par définition de u1 et de w1, nous avons

−‖v‖∞w1 ≤ u1 ≤ ‖v‖∞w1, sur ∂Ω1,

et les trois fonctions intervenant dans cette inégalité sont harmoniques dans Ω1. Le principe du maximumimplique que nous avons

−‖v‖∞w1 ≤ u1 ≤ ‖v‖∞w1, dans tout Ω1,

et en particulier sur l’interface γ21 ⊂ Ω1 nous avons

supγ21

|u1| ≤(

supγ21

w1

)‖v‖∞.

Par le théorème précédent, la fonction w1 est continue sur le compact γ21, elle y atteint donc son maximum,celui ne pouvant pas être atteint sur le bord (car w1 est nulle en ces points). Le maximum de w1 sur γ21 estdonc atteint à l’intérieur de Ω1 et il est donc nécessairement strictement plus petit que 1 sur les interfaces, sinonle principe du maximum impliquerait que w1 = 1 partout.

In fine, on a obtenusupγ21

|u1| ≤ k1 supγ12

|v|,

avec k1 ∈]0, 1[.De la même manière pour la seconde étape d’une itération de la méthode, on trouve

supγ12

|u2| ≤ k2 supγ21

|u1|,

avec k2 ∈]0, 1[.Tout compte fait, au bout d’une itération de la méthode on a

supγ12

|u2| ≤ k1k2 supγ12

|v|,

ce qui montre le caractère contractant de la méthode et donc sa convergence géométrique vers 0.Si les deux interfaces γ12 et γ21 se touchent de façon non tangentielle (voir la figure I.1b), alors l’argument

précédent doit être affiné car les fonctions w1 et w2 ne sont plus continues aux points d’intersection.On peut quand même démontrer que ces fonctions ont un maximum strictement plus petit que 1 mais il

faut l’étudier de façon plus précise. La démonstration générale est un peu technique nous allons juste montrercomment l’argument fonctionne dans le cas du demi-espace.



Plus précisément on peut calculer explicitement la fonction w1 définie sur R2+ et telle que w1(x, 0) = 1 si

x < 0 et w1(x, 0) = 0 si x > 0. En effet, la formule explicite est donnée par

w1(x, y) =1

π

∫ +∞

x

y

t2 + y2dt = − 1

πf(x/y),

où f est la primitive s’annulant en +∞ de 1/(1 + t2) (c’est-à-dire f(t) = arctan(t)− π/2).On observe que si (x, y)→ (0, 0) de façon non tangentielle à la frontière, c’est-à-dire avec x/y → α pour

un certain α ∈ R, alors nous obtenons

w1(x, y) −−−−−−−→(x,y)→(0,0)

−1

πf(α),

qui est bien une valeur strictement comprise entre 0 et 1.Le reste de la preuve s’en suit directement.

1.4 La preuve variationnelle de P.L. LionsCommençons par quelques remarques.

• Si vi ∈ H10 (Ωi), son prolongement par 0 à tout Ω que l’on note encore vi vérifie ui ∈ H1

0 (Ω). Onidentifie donc H1

0 (Ωi) à un sous-espace fermé de H10 (Ω).

• Par construction des deux étapes (I.2) et (I.3), on peut conventionnellement prolonger u1n+1 et u2

n+1 àtout Ω par les formules suivantes

u1n+1 =

u1n+1 dans Ω1,

u2n dans Ω \ Ω1,

et

u2n+1 =

u2n+1 dans Ω2,

u1n+1 dans Ω \ Ω2.

Par définition, ces prolongements sont bien dans H1(Ω).

• On introduit la forme bilinéaire

a(u, v) =

∫Ω

∇u · ∇v dx, ∀u, v ∈ H10 (Ω),

intervenant dans la formulation variationnelle du problème étudié.

Si maintenant u2n ∈ H1

0 (Ω) est connu, alors le problème (I.2) admet la formulation variationnelle sui-vante

Trouver u1n+1 ∈ H1

0 (Ω) tel que u1n+1 − u2

n ∈ H10 (Ω1) et a(u1

n+1, v) = 0, ∀v ∈ H10 (Ω1). (I.4)

De même, si u1n+1 ∈ H1

0 (Ω) est connu, le problème (I.3) s’écrit

Trouver u2n+1 ∈ H1

0 (Ω) tel que u2n+1 − u1

n+1 ∈ H10 (Ω2) et a(u2

n+1, v) = 0, ∀v ∈ H10 (Ω2). (I.5)

Si on définit Pi, i = 1, 2 la projection orthogonale dans l’espace de HilbertH10 (Ω) sur le sous-espace fermé

H10 (Ωi) et Qi = I − Pi la projection orthogonale sur l’orthogonal de cet espace, on voit que les deux étapes

de l’algorithme s’écrivent désormais

u1n+1 = u2

n − P1(u2n) = Q1(u2

n),

u2n+1 = u1

n+1 − P2(u1n+1) = Q2(u1

n+1).

Ainsi, une itération complète de l’algorithme revient à appliquer deux projections successives sur deuxsous-espaces fermés de H1

0 (Ω). Tout l’enjeu est donc de déterminer si Q2Q1 est une application contractanteou pas.



Théorème I.2

Soient V1 et V2 deux sous-espaces fermés de H10 (Ω) et Pi (resp. Qi) les projections orthogonales

dansH10 sur Vi (resp. sur V ⊥i ). On suppose que V1 +V2 est dense dansH1

0 (Ω) (ce qui est équivalentà V ⊥1 ∩ V ⊥2 = 0).Soit u0

2 ∈ H10 (Ω) quelconque une initialisation de l’algorithme. On pose, pour tout n,

un+12 = Q2Q1u

n2 .

Alors la suite (un2 )n tend vers 0 dans H10 (Ω) (autrement dit l’algorithme de Scwharz converge).

Si de plus on a V1 + V2 = H10 (Ω), alors la convergence est géométrique : il existe 0 < k < 1 tel

que‖un2‖H1

0≤ kn‖u0

2‖H10, ∀n ≥ 0.

Preuve :On écrit tout d’abord,la somme orthogonale

u2n = P1(u2

n) +Q1(u2n) = (u2

n − u1n+1) + u1

n+1,

ce qui donne en passant à la norme

‖u2n‖2H1

0= ‖u2

n − u1n+1‖2H1

0+ ‖u1

n+1‖2H10.

De la même façon, on a

‖u1n+1‖2H1

0= ‖u1

n+1 − u2n+1‖2H1

0 (Ω) + ‖u2n+1‖2H1

0.

En particulier la suite des normes (‖u2n‖)n est décroissante donc convergente et de plus

‖u2n − u1

n+1‖H10−−−−→n→∞

0. (I.6)

On peut extraire de (u2n)n une sous-suite faiblement convergente donc on note u la limite. Comme u2

n ∈ V ⊥2pour tout n et que V ⊥2 est un fermé faible de H1

0 (Ω), on a immédiatement que u ∈ V ⊥2 . Mais on a égalementque u1

n+1 = Q1un2 converge faiblement vers Q1u et d’après (I.6) la différence u1

n+1 − u2n tend vers 0. Ceci

montre que Q1u = u et donc en particulier que u ∈ V ⊥1 .On a donc montré que u ∈ V ⊥1 ∩ V ⊥2 et donc par hypothèse u = 0.Ainsi, la suite (u2

n)n a une unique valeur d’adhérence faible qui est 0, ce qui montre la convergence faiblede toute la suite vers 0. Il reste à montrer la convergence forte.

Pour cela, on observe que

‖u2n‖2H1

0= ‖(Q2Q1)nu2

0‖2H10

= 〈(Q1P2)n(Q2Q1)nu20, u

20〉H1

0

= 〈Q1(Q2Q1)2n−1u20, u

20〉H1

0= 〈u0

2n−1, Q1u20〉H1

0

et la convergence faible obtenue plus haut permet de conclure au fait que ‖u2n‖H1

0→ 0.

Supposons maintenant que V1 + V2 = H10 (Ω). On va montrer que sous cette hypothèse la norme de tout

élément de H10 (Ω) peut être contrôlée par les normes des deux projections P1v et P2v.

En effet, l’hypothèse implique que l’application

Φ : (v1, v2) ∈ V1 × V2 7→ v1 + v2 ∈ H10 (Ω),

est surjective (et bien entendu linéaire et continue). Le théorème de l’application ouverte implique alors que Φest ouverte ce qui signifie que l’image de tout ouvert de V1 × V2 est ouverte dans H1

0 (Ω) ou encore

∃C > 0, BH10(0, C) ⊂ Φ(BV1(0, 1)×BV2(0, 1)),

ce qui peut également s’écrire

∀v ∈ H10 (Ω), ∃(v1, v2) ∈ V1 × V2 tels que v = v1 + v2, et ‖v1‖2 + ‖v2‖2 ≤

1

C‖v‖2. (I.7)



Pour tout v ∈ H10 (Ω), on prend le couple (v1, v2) donné ci-dessus et on écrit

‖v‖2H10

= 〈v, v1〉H10

+ 〈v, v2〉H10

= 〈P1v, v1〉H10

+ 〈P2v, v2〉H10

≤ ‖P1v‖H10‖v1‖H1

0+ ‖P2v‖H1

0‖v2‖H1

0

≤ C ′‖v‖H10

(‖P1v‖H1

0+ ‖P2v‖H1

0

).

On a donc bien montré qu’il existe une constante C ′ > 0 telle que

‖v‖H10≤ C ′(‖P1v‖H1

0+ ‖P2v‖H1

0), ∀v ∈ H1

0 (Ω). (I.8)

On applique maintenant l’inégalité (I.8) à Q1v ce qui donne

‖Q1v‖H10≤ C ′‖P2Q1v‖H1

0, ∀v ∈ H1

0 (Ω).

En élevant au carré et en utilisant la décomposition orthogonale Q1v = P2Q1v +Q2Q1v, on obtient

‖Q1v‖2H10

= ‖P2Q1v‖2H10

+ ‖Q2Q1v‖2H10≥ 1

(C ′)2‖Q1v‖2H1

0+ ‖Q2Q1v‖2H1

0,

et donc

‖Q2Q1v‖2H10≤(

1− 1

(C ′)2

)‖Q1v‖2H1

0.

Ceci implique

‖Q2Q1v‖2H10≤(

1− 1

(C ′)2

)‖v‖2H1

0,

et donc le caractère contractant de l’application Q2Q1.Le résultat précédent est relativement abstrait. Pour le traiter dans le cadre donné plus haut on doit vérifier

que les espaces V1 = H10 (Ω1) et V2 = H1

0 (Ω2) vérifient bien l’une ou l’autre des hypothèses proposées.

Proposition I.3

Quelque soit la décompositon Ω = Ω1 ∪ Ω2, l’espace H10 (Ω1) +H2

0 (Ω2) est dense dans H10 (Ω).

Preuve :Soit ϕ ∈ D(Ω) une fonction test, dont on noteK le support (compact dans Ω). On commence par remarquer

qu’il existe ε > 0 tel queK ⊂ Kε

1 ∪Kε2 ,

oùKεi = x ∈ Ωi, d(x, ∂Ωi) ≥ ε.

En effet, si ça n’était pas le cas on pourrait construire une suite de points de K telle que

d(xn, ∂Ωi) ≤ 1/n, ∀i = 1, 2,

ce qui, après extraction de sous-suite convergente, impliquerait qu’il existe un élément de K (et donc de Ω) quiappartient à ∂Ω1 ∩ ∂Ω2, ce qui n’est pas possible car Ω = Ω1 ∪ Ω2 et donc ∂Ω1 ∩ ∂Ω2 ⊂ ∂Ω.

Comme Kεi est un compact contenu dans l’ouvert Ωi, on peut trouver une fonction ψi ∈ D(Ωi) telle que

ϕ1 = 1 sur Kεi .

On vérifie que l’on peut maintenant écrire

ϕ =ψ1

ψ1 + ψ2ϕ+

ψ2

ψ1 + ψ2ϕ.

Comme ψ1 + ψ2 ≥ 1 dans K (qui est le support de ϕ), cette écriture donne une décomposition de ϕ en lasomme d’une fonction de D(Ω1) et d’une fonction de D(O2).



Ainsi, nous avons montré queD(Ω) ⊂ D(Ω1) +D(Ω2),

ce qui implique que D(Ω) ⊂ H10 (Ω1) +H1

0 (Ω2) et donc que ce dernier espace est bien dans H10 (Ω).

Proposition I.4On suppose que γ12 et γ21 ne s’intersectent pas ou bien qu’ils s’intersectent de façon non tangen-tielle au bord de Ω. Alors nous avons l’égalité H1

0 (Ω) = H10 (Ω1) +H1

0 (Ω2).

Preuve :Tout le problème revient à construire deux fonctions ψi ayant de bonnes propriétés de régularité (qu’on va

préciser ci-dessous) et telles queψ1 + ψ2 = 1, dans Ω,

ψ1 = 0, en dehors de Ω1,

ψ2 = 0, en dehors de Ω2.

• Premier cas : les interfaces γ12 et γ21 ne s’intersectent pas (le recouvrement est donc suffisammentimportant). Il est alors facile de construire de tels ψi qui soient réguliers (disons Lipschitziens sur toutΩ).

Dans ce cas, toute fonction u ∈ H10 (Ω) s’écrit sous la forme

u = uψ1 + uψ2,

et on vérifie sans peine que uψi ∈ H10 (Ωi) ce qui donne le résultat.

• Second cas : les interfaces γ12 et γ21 s’intersectent au bord de Ω. Il est clair alors que l’on ne peuttrouver des ψi réguliers vérifiant les propriétés ci-dessus car les deux dernières conditions impliquentque ψ1 + ψ2 = 0 au point d’intersection des interfaces, ce qui contredit la première propriété.

Sous l’hypothèse que les interfaces ne sont pas tangentes, on peut toutefois construire de tels ψi avec larégularité localement Lipschitzienne dans Ω et une estimation du gradient de la forme

|∇ψi(x)| ≤ C

d(x, ∂Ω), ∀x ∈ Ω.

Cette dernière estimation étant surtout utile près du point d’intersection, on va étudier ce qui se passe dansle cas simple où Ω est un demi-espace et les interfaces sont des droites se coupant en (0, 0) d’équationx = αy et x = βy, y > 0 et α < β.

On définit alors

ψ1(x, y) = max

(min

(2

α− β

(x

y− α+ β

2

), 1

), 0

),

et une définition similaire pour ψ2.

On voit bien que ψ est localement Lipschitzienne dans Ω et que la norme de son gradient et non nulleuniquement dans le secteur angulaire séparé par les deux interfaces. Dans ce secteur angulaire, le gradientde ψ1 vaut

∇ψ1(x, y) =1

α− β

( 1y

− xy2

).

Comme dans ce secteur angulaire on a |x/y| ≤ max(|α|, |β|), on déduit que

|∇ψ1(x, y)| ≤ Cα,β1

y,

ce qui est bien l’estimation recherchée vu que y est la distance du point (x, y) au bord du domaine.

Muni de ces deux fonctions, on peut alors toujours écrire

u = uψ1 + uψ2,



mais il faut s’assurer que uψ1 ∈ H10 (Ω1). Par construction cette fonction est dans H1

loc(Ω) et nulle endehors de Ω1. Il reste à voir qu’elle est dans H1 jusqu’au bord de Ω. Ceci provient du calcul suivant

∇(uψ1) = ψ1∇u+ u∇ψ1,

qui donne

|∇(uψ1)(x)|2 ≤ C|∇u(x)|2 + C|u(x)|2

d(x, ∂Ω)2,

et on peut utiliser l’inégalité de Hardy qui nous dit que pour tout fonction u ∈ H10 (Ω), la fonction

u/d(., ∂Ω) est dans L2(Ω) et vérifie ∥∥∥ud

∥∥∥2

L2≤ C‖u‖2H1 .

Ceci conclut la preuve du fait que uψ1 est dans H10 (Ω) et donne le résultat attendu.

La preuve de convergence proposée donne une estimation de vitesse de convergence qui dépend de lameilleure constante qui apparaît dans (I.7). Il est donc potentiellement instructif d’estimer cette constante.Dans le cas 1D, on peut faire le calcul explicite et vérifier que la constante explose de façon inverse à la taillede l’overlap.

Soit donc Ω =]0, 1[, Ω1 =]0, γ12[ et Ω2 =]γ21, 1[. On se donne v ∈ H10 (Ω) et on veut décomposer v en

v1 + v2 avec vi ∈ H10 (Ωi). Cela implique immédiatement que

v1 = v, sur Ω1 \ Ω2 =]0, γ21[,

v2 = v, sur Ω2 \ Ω1 =]γ12, 1[.

De plus, dans la zone de recouvrement ∆ =]γ21, γ12[, si on note w la fonction affine qui vaut 0 en γ12 etqui coincide avec v en γ21, nous pouvons écrire v1 et v2 sous la forme

v1 = w + ϕ, v2 = v − w − ϕ, avec ϕ ∈ H10 (∆).

Il s’agit maintenant de minimiser la fonctionelle strictement convexe

F : ϕ ∈ H10 (∆) 7→

∫∆

|v′1|2 + |v′2|2 dx =

∫∆

|w′ + ϕ′|2 + |v′ − w′ − ϕ′|2 dx.

Un tel minimiseur ϕ existe et est unique et satisfait l’équation d’Euler-Lagrange

d

dx(w′ + ϕ′) +

d

dx(ϕ′ + w′ − v′) = 0, dans ∆,

et comme w est affine, il reste2ϕ′′ = v′′, dans ∆,

ce qui prouve que 2ϕ− v doit être affine. Les conditions aux limites sur ϕ fournissent la solution

ϕ =1

2

(v − x− γ12

γ21 − γ12v(γ21) +

x− γ21

γ21 − γ12v(γ12)

),

et la valeur du minimum

F (ϕ) =

∫∆

∣∣∣∣v′/2 +1

2

v(γ12) + v(γ21)

γ21 − γ12

∣∣∣∣2 +

∣∣∣∣v′/2− 1

2

v(γ12) + v(γ21)

γ21 − γ12

∣∣∣∣2 dx=

∫∆

1

2|v′|2 +

1

2

∣∣∣∣v(γ12) + v(γ21)

γ21 − γ12

∣∣∣∣2 dx=

1

2

∫∆

|v′|2 dx+|v(γ12) + v(γ21)|2

|γ12 − γ21|.



On cherche donc maintenant la meilleure constante C > 0 telle que

|v(γ12) + v(γ21)|2

|γ21 − γ12|≤ C

∫Ω

|v′|2 dx. (I.9)

Les valeurs de v aux bornes de ∆ étant fixés, la fonction v qui minimise le second membre est la fonction affinepar morceaux v, nulle en 0 et 1 et coincidant avec v en γ12 et γ21.

Tous calculs faits, on trouve∫ 1

0

|v′|2 dx =|v(γ21)|2

γ21+|v(γ12)|2

γ12+|v(γ12)− v(γ21)|2

|γ12 − γ21|.

On voit ainsi qu’en prenant des v telles que v(γ12) = v(γ21), la constante C dans (I.9) vérifie

C ≈ 1

|γ12 − γ21|,

ce qui montre bien l’explosion de cette constante quand la taille du recouvrement tend vers 0.

1.5 Formalisme algébriqueLe preuve de convergence variationnelle donnée plus haut peut en fait être vue comme un cas particulier

d’un algorithme plus général que nous allons décrire ici.Ce formalisme contient beaucoup de méthodes différentes (Schwarz, multigrilles, etc ...).Soit H un espace de Hilbert (éventuellement de dimension finie). On considère un problème linéaire du

typea(u, v) = L(v), ∀v ∈ H,

où a et L vérifient les hypothèses du théorème de Lax-Milgram (avec a symétrique pour simplifier ici). Onintroduit l’opérateur A et le vecteur b représentant a et L dans le produit scalaire de H :

a(u, v) = 〈Au, v〉, 〈b, v〉 = L(v), ∀u, v ∈ H.

Au vu des hypothèses, la matrice A est symétrique définie positive. Le problème à résoudre s’écrit alors

Trouver u ∈ H tel que Au = b. (I.10)

On suppose donnée une décomposition de l’espace H en sous-espaces fermés H1, ...,HJ (non nécessairementen somme directe). On note Ik : Hk → H l’injection canonique et I ′k son adjoint, c’est-à-dire la projection surHk définie par

〈Ikvk, v〉 = 〈vk, I ′kv〉, ∀vk ∈ Hk,∀v ∈ H.

La restriction de l’opérateur initial sur le sous-espace Hk est définie par

Ak = I ′kAIk,

et comme A est SDP, on vérifie aisément que Ak est SDP dans Hk.L’idée des méthodes présentées consiste à utiliser la résolution (éventuellement approchée) sur les sous-

espaces Hk pour construire des méthodes itératives de résolution de (I.10).Pour ce faire, on note Rk : Hk → Hk un opérateur résolution dans Hk qui a vocation à être une approxi-

mation de A−1k , et qui d’ailleurs peut être égal à A−1

k comme on l’a vu précédemment. On suppose que Rk estSDP dans Hk et que RkAk est diagonalisable (cet opérateur est Ak-SDP).

On va de plus typiquement supposer que ρ(I − RkAk) < 1 (ceci ayant au moins un sens en dimensionfinie) de sorte que, à k fixé, la méthode itérative

un+1k = unk −Rk(Aku

nk − I ′kf), ∀n ≥ 0,

converge vers la solution de Akuk = I ′kf .L’algorithme est alors le suivant : si on suppose une approximation un ∈ H de la solution de (I.10) connue,

alors on effectue successivement :



• Poser un0 = un.

• Pour k = 1, ..., J :

– Calculer la projection du résidu sur Hk

rk = I ′k(f −Aunk−1).

– Calculer le correcteur, c’est-à-dire résoudre la contribution du résidu sur Hk

ck = Rkrk.

– Mettre à jour la solution approchée

unk = unk−1 + Ikck.

• Définir la solution approchée en fin d’itération

un+1 = un+1J .

Comme f = Au, on peut récrire complètement l’algorithme en fonction de l’erreur en = un − u.

• Pour k = 1, ..., J :

– Calculer la projection du résidu sur Hk

rk = −I ′kAenk−1.

– Calculer le correcteur, c’est-à-dire résoudre la contribution du résidu sur Hk

ck = Rkrk.

– Mettre à jour l’erreurenk = enk−1 + Ikck.

• Définir l’erreur finaleen+1 = en+1

J .

Ceci s’écrit encoreenk =

(I − IkRkI ′kA

)enk−1, ∀k.

Si on pose Tk = IkRkI′kA, l’évolution de l’erreur au cours des itérations s’écritdonc

en+1 = (I − TJ) · · · (I − T1)en, ∀n ≥ 0.

Ainsi l’étude de la convergence de la méthode se ramène à l’étude de la norme et du spectre d’opérateursde la forme

E = (I − TJ) · · · (I − T1),

appelés opérateurs de propagation de l’erreur. On comprend mieux sous cette forme pourquoi la méthodes’appelle ici méthode multiplicative.

Remarque I.5Ce formalisme inclut par exemple les méthodes de Gauss-Seidel par blocs.



Nous aurons besoin d’introduire les opérateurs intermédiaires

Ej = (I − Tj) · · · (I − T1), ∀1 ≤ j ≤ J,

avec E0 = I par convention.On vérifie aisément par réccurence que

Ej−1 − Ej = TjEj−1, I − Ej =

j∑i=1

TiEi−1. (I.11)

Lemme I.6

Pour tout k, le projecteurA-orthogonal (i.e. pour le produit scalaire défini parA) surHk s’exprimesous la forme

Pk = Ik(I ′kAIk)−1I ′kA = Ik(Ak)−1I ′kA.

Preuve :On vérifie aisément que P 2

k = Pk et que PkIk = Ik, ce qui prouve que l’image de Pk est égale à Hk.De plus, on vérifie aussi que Pk est A-orthogonal et donc que Pk est bien le projecteur A-orthogonal sur

Hk.Ainsi, si on considère un solveur exact sur les sous-espaces Rk = A−1

k , les opérateurs Tk définis plus hautne sont autres que les projecteurs Pk, et on retrouve essentiellement le cadre de la preuve de Lions ci-dessus.

Dans le cas général, on va supposer qu’il existe 0 < ω0 ≤ ω1 < 2 tels que

ω0〈Avk, vk〉 ≤ 〈ARkAkvk, vk〉 ≤ ω1〈Avk, vk〉, ∀vk ∈ Hk. (I.12)

Cette hypothèse implique que

ρ(I −RkAk) ≤ max(|1− ω0|, |1− ω1|) < 1.

Lemme I.7Les opérateurs Tk sont A-autoadjoints et A-positifs et vérifient

ρ(Tk) ≤ ‖Tk‖A ≤ ω1 < 2.

Preuve :Comme Rk et Ak sont SDP, on montre aisément les propriétés de symétrie et positivité de Tk.De plus, la deuxième inégalité de (I.12) montre que les valeurs propres de RkAk (qui sont réelles car cet

opérateur est A-symétrique) sont positives et bornées par ω1. Il en est donc de même de l’opérateur symétriqueéquivalent R1/2

k AkR1/2k . On a donc

〈R1/2k AkR

1/2k vk, vk〉 ≤ ω1〈vk, vk〉,

et ainsi, en posant wk = R1/2k vk, on trouve

〈Akwk, wk〉 ≤ ω1〈R−1k wk, wk〉, ∀wk ∈ Hk.

On peut maintenant calculer

〈ATkv, Tkv〉 = 〈AIkRkI ′kAv, IkRkI ′kAv〉= 〈I ′kAIkRkI ′kAv,RkI ′kAv〉= 〈AkRkI ′kAv,RkI ′kAv〉≤ ω1〈R−1

k RkI′kAv,RkI

′kAv〉

= ω1〈I ′kAv,RkI ′kAv〉= ω1〈AIkRkI ′kAv, v〉= ω1〈ATkv, v〉.

(I.13)



Par l’inégalité de Cauchy-Schwarz on trouve

〈ATkv, Tkv〉 ≤ ω21〈Av, v〉,

ce qui montre bien que la A-norme de Tk est plus petite que ω1.Démontrons maintenant la convergence de la méthode sous l’hypothèse que les espaces Hk sont suffisam-

ment gros dans H .

Théorème I.8

Supposons que la somme∑Jk=1Hk est dense dans H , alors la méthode itérative précédente est

convergente (quelque soit le choix des opérateurs de résolution localeRk satifsaisant les hypothèses(I.12)).

Preuve :On a vu que l’erreur évolue selon les formules suivantes (avec en0 = en et enJ = en+1)

enk = (I − Tk)enk−1, ∀k = 1, ..., J,

ou encore de façon globaleen+1 = (I − TJ) · · · (I − T1)en.

On remarque que pour tout k et n nous avons

‖enk−1‖2A − ‖(I − Tk)enk−1‖2A = ‖(I − Tk)enk−1 + Tkenk−1‖2A − ‖(I − Tk)enk−1‖2A

= ‖Tkenk−1‖2A + 2〈(I − Tk)enk−1, Tkenk−1〉A

= 2〈Tkenk−1, enk−1〉A − ‖Tkenk−1‖2A.

Si on utilise (I.13), et la définition de l’erreur au cran suivant enk = (I − Tk)enk−1, on arrive à l’inégalité

‖enk−1‖2A − ‖enk‖2A ≥ (2− ω1)〈Tkenk−1, enk−1〉A. (I.14)

Comme ω1 < 2, le terme de droite est positif et on en déduit que la norme de l’erreur décroît à chaque étapedu calcul (sur chaque sous-domaine) et donc, plus globalement on a la décroissance de (‖en‖A)n.

On en déduit en particulier que cette suite de nombres positifs est convergente et donc bornée. Si on revientà (I.14), on a de plus la convergence des séries

+∞∑n=0

〈Tkenk−1, enk−1〉A, pour tout k = 1, ..., J. (I.15)

D’après (I.13) et la formule enk − enk−1 = Tkenk1

, on déduit que les séries

+∞∑n=0

‖enk − enk−1‖2, convergent pour tout k = 1, ..., J.

En particulier, la série suivante converge

+∞∑n=0

‖en+1 − en‖2A,

et donc en particulier‖en+1 − en‖A −−−−→

n→∞0. (I.16)

Comme (en)n est A-bornée (donc bornée), on peut en extraire une sous-suite faiblement convergente

eϕ(n) −−−−→n→∞

e.



Par continuité de tous les opérateurs mis en jeu, on déduit

eϕ(n)k −−−−→

n→∞(I − Tk) · · · (I − T1)e, pour tout k = 1, ..., J.

On note ek cette limite.Grâce à la convergence des séries (I.15) on a

limn→+∞

〈Tkenk−1, enk−1〉A = 0,

et donc 〈Tkek−1, ek−1〉A = 0.En effet, nous avons

0 ≤ 〈Tk(enk−1 − ek−1), enk−1 − ek−1〉A= 〈Tkenk−1, e

nk−1〉A − 2〈Tkenk−1, ek−1〉A + 〈Tkek−1, ek−1〉A

−−−−→n→∞

−〈Tkek−1, ek−1〉A.

D’après (I.13), on déduit que Tkek−1 = 0 pour tout k.La limite faible e vérifie donc

T1e = 0, T2(I − T1)e = 0, ..., Tk(I − Tk−1) · · · (I − T1)e = 0,

ce qui impliqueTke = 0, ∀k = 1, ..., J.

Revenons à la définition de Tk = I ′kRkIkA et prenons le produit scalaire de Tke = 0 par Ae

0 = 〈IkRkI ′kAe,Ae〉 = 〈RkI ′kAe, I ′kAe〉,

et donc I ′kAe = 0 pour tout k, ou encore

Ae ⊥ Hk, ∀k ∈ 1, ..., J.

Ainsi, Ae est orthogonal à la somme des espaces Hk et par l’hypothèse de densité, cela implique Ae = 0 etdonc e = 0.

Ainsi la seule valeur d’adhérence faible possible pour la suite (en)n est 0, ce qui montre la convergencefaible de toute la suite.

Il reste à montrer la convergence forte. Pour cela on utilise le lemme suivant

Lemme I.9Soit S : H → H un opérateur A-contractant au sens suivant

‖Sx‖A ≤ ‖x‖A, ∀x ∈ H.

On a alors

|〈x, y〉A − 〈Sx, Sy〉A| ≤1

2‖x‖2A +

1

2‖y‖2A −

1

2‖Sx‖2A −

1

2‖Sy‖2A, ∀x, y ∈ H.

Preuve (du lemme):

• On commence par écrire

〈x, y〉A =1

2‖x‖2A +

1

2‖y‖2A −

1

2‖x− y‖2A,

〈Sx, Sy〉A =1

2‖Sx‖2A +

1

2‖Sy‖2A −

1

2‖S(x− y)‖2A.

Comme ‖S(x− y)‖A ≤ ‖x− y‖A, et par soustraction, on obtient

〈x, y〉A − 〈Sx, Sy〉A ≥ −1

2‖x‖2A −

1

2‖y‖2A +

1

2‖Sx‖2A +

1

2‖Sy‖2A.



• Ensuite on écrit

〈x, y〉A = −1

2‖x‖2A −

1

2‖y‖2A +

1

2‖x+ y‖2A,

〈Sx, Sy〉A = −1

2‖Sx‖2A −

1

2‖Sy‖2A +

1

2‖S(x+ y)‖2A.

Comme ‖S(x+ y)‖A ≤ ‖x+ y‖A, et par soustraction, on obtient

〈Sx, Sy〉A − 〈x, y〉A ≤1

2‖x‖2A +

1

2‖y‖2A −

1

2‖Sx‖2A −

1

2‖Sy‖2A.

• La combinaison des deux inégalités précédentes donne le résutat attendu.

On applique ce résultat plusieurs fois par récurrence à E pour obtenir, pour tout n,m, p

∣∣〈en, en+m〉A − 〈en+p, en+m+p〉A∣∣ ≤ 1

2‖en‖2A +

1

2‖en+m‖2A −

1

2‖en+p‖2A −

1

2‖en+m+p‖2A.

On a déjà vu que la suite (‖en‖A) est convergente, on note l sa limite. Il s’agit de montrer que l = 0. L’inégalitéprécédente montre que pour tout m ≥ 0, la suite(

〈en, en+m〉A)n, est de Cauchy dans R, uniformément par rapport à m.

Ceci montre que ces suites convergent, vers une limite notée lm, et ce de manière uniforme par rapport à m.Donc nous avons

lm −−−−→m→∞

l.

Par ailleurs, en utilisant la borne sur (en)n et (I.16), nous avons pour tout m

|〈en, en+m〉A − 〈en, en+m+1〉A| ≤ ‖en‖A‖en+m − en+m+1‖A −−−−→n→∞

0.

Ceci montre que lm = lm+1 pour tout m.Mais en utilisant la convergence faible de en vers 0, on peut aussi écrire

〈en, en+m〉A −−−−→m→∞

0,

et le théorème de double passage à la limite nous permet de conclure que l = 0, ce qui donne bien la conver-gence forte des approximations.

On peut maintenant conclure cette section en montrant une estimation d’erreur pour la méthode dans le casoù la somme des espaces Hk est égale à H .

Théorème I.10

On suppose que H =∑Jk=1Hk. Alors il existe une constante C0 > 0 telle que

Pour tout v ∈ H , il existe v1 ∈ H1, ..., vJ ∈ HJ tels que v =

J∑k=1

vk etJ∑k=1

‖vk‖2A ≤ C0‖v‖2A.

Par ailleurs, ceci implique que la méthode de Schwarz converge de façon géométrique : il existe uneconstante k < 1 telle que

‖en‖A ≤ ‖e0‖Akn.

Preuve :L’existence de la constante C0, comme on l’a déjà vu, est une conséquence du théorème de l’application

ouverte et donc du fait que les espaces Hk sont fermés et que leur somme est l’espace entier.



• On va tout d’abord montrer une estimation sur les opérateurs R−1k . On écrit v =

∑Jk=1 vk comme dans

l’hypothèse et on a

J∑k=1

〈R−1k vk, vk〉 =

J∑k=1

〈AkA−1k R−1

k vk, vk〉

≤J∑k=1

〈Akvk, vk〉〈AkA−1

k R−1k vk, vk〉

〈Akvk, vk〉

≤ 1

ω0

J∑k=1

〈Akvk, vk〉

=1

ω0

J∑k=1

〈AIkvk, Ikvk〉

=1

ω0

J∑k=1

‖Ikvk‖2A

≤ C0

ω0‖v‖2A.

On a utilisé ici l’hypothèse spectrale (I.12).

• On peut maintenant démontrer une inégalité du type Lemme de Lions qui consiste à estimer la normed’un élément de H en fonction des normes de Tkv.

Soit v =∑Jk=1 Ikvk ∈ H , nous avons

‖v‖2A =

J∑k=1

〈v, Ikvk〉A =

J∑k=1

〈I ′kAv, vk〉 =

J∑k=1

〈RkI ′kAv,R−1k vk〉.

On applique alors l’inégalité de Cauchy-Schwarz au produit scalaire 〈Rk., .〉 pour obtenir

‖v‖2A ≤

(J∑k=1

〈RkR−1k vk, R

−1k vk〉

) 12(

J∑k=1

〈RkI ′kAv, I ′kAv〉

) 12

.

En appliquant l’estimation sur les R−1k obtenue précédemment, il vient

‖v‖2A ≤(C0

ω0

) 12

‖v‖A

(J∑k=1

〈IkRkI ′kAv, v〉A

) 12

.

Par définition de Tk = IkRkI′kA, on obtient

‖v‖2A ≤C0

ω0

(J∑k=1

〈Tkv, v〉A

). (I.17)

• Pour 1 ≤ k ≤ J , on écrit (en utilisant (I.11))

〈Tkv, v〉A = 〈Tkv,Ek−1v〉A +

k−1∑i=1

〈Tkv, TiEi−1v〉A.

Ensuite, on utilise l’inégalité de Cauchy-Schwarz pour le semi-produit scalaire 〈Tk., .〉A, et (I.13) pourobtenir

〈Tkv, v〉A ≤ 〈Tkv, v〉12

A〈TkEk−1v,Ek−1v〉12

A +

k−1∑i=1

〈Tkv, Tkv〉12

A〈TiEi−1v, TiEi−1v〉12

A

≤ 〈Tkv, v〉12

A

(〈TkEk−1v,Ek−1v〉

12

A + ω

k−1∑i=1

〈TiEi−1v,Ei−1v〉12

A

).


2. Méthode sans recouvrement 17

Si on simplifie et qu’on élève au carré, il vient

〈Tkv, v〉A ≤ 2

(〈TkEk−1v,Ek−1v〉A + ω2(k − 1)

k−1∑i=1

〈TiEi−1v,Ei−1v〉A

).

En sommant sur k et en réorganisant les termes, il vient

J∑k=1

〈Tkv, v〉A ≤[2 + ω2J(J − 1)

] J∑k=1

〈TkEk−1v,Ek−1v〉A. (I.18)

• L’inégalité (I.14), peut se récrire sous la forme plus générale suivante

‖v‖2A − ‖Ev‖2A = ‖v‖2A − ‖EJv‖2A ≥ (2− ω1)

J∑k=1

〈TkEk−1v,Ek−1v〉A.

Avec (I.18), on obtient

‖v‖2A − ‖Ev‖2A ≥2− ω1

2 + ω2J(J − 1)

(J∑k=1

〈Tkv, v〉A

),

et maintenant on utilise (I.17) pour obtenir

‖v‖2A − ‖Ev‖2A ≥2− ω1

2 + ω2J(J − 1)

ω0

C0‖v‖2A.

Si on note C1 = 2−ω1

2+ω2J(J−1)ω0

C0, on a donc montré

‖Ev‖2A ≤ (1− C1)‖v‖2A, ∀v ∈ H,

ce qui montre bien le caractère contractant de l’opérateur d’erreur avec la constante de contraction

k = 1− C1 < 1.

2 Méthode sans recouvrement

2.1 Principe généralIl s’agit maintenant de proposer des méthodes de décomposition de domaines qui fonctionnent dans le cas

où les sous-domaines ne se recouvrent pas. On se convainc aisément qu’une méthode à base de conditions auxlimites de Dirichlet (ou de Neumann) n’a aucune chance de fonctionner. C’est pourquoi P.L.Lions a proposéune version de ces méthodes basées sur des conditions de transmission de type Fourier. Plus exactement, étantconnues les approximations uin sur tous les sous-domaines, on calcule les nouvelles approximations uin+1 encalculant la solution de

−∆uin+1 = f, dans Ωi

uin+1 = g, sur ∂Ω ∩ ∂Ωi,

∂uin+1

∂νij+ λuin+1 =

∂ujn∂νij︸︷︷︸

= − ∂ujn

∂νji

+λujn, sur γij . (I.19)

Dans ces équations λ est un paramètre strictement positif fixé. On discutera de sa valeur un peu plus tard.En plus de ne pas nécessiter de recouvrement entre les sous-domaines, cette méthode est donc entièrement

parallélisable puisque la résolution sur les sous-domaines se fait de façon simultanée.



2.2 Exemples en 1D et 2D. Notion de méthode optimale2.2.1 Le cas 1D

On pose Ω =]0, 1[ et Ω1 =]0, γ[,Ω2 =]γ, 1[ (ici il n’y a qu’une interface ...). Comme précédemment, onpeut soustraire la solution exacte des solutions approchées et donc se ramener au cas f = 0, g = 0.

On peut voir la méthode proposée comme une itération permettant de résoudre les équations (ui)′′ = 0dans Ωi avec les conditions de transmission

(u1)′(γ) + λu1(γ) = (u2)′(γ) + λu2(γ),

−(u2)′(γ) + λu2(γ) = −(u2)′(γ) + λu2(γ).

Ces équations montrent bien que u1 = u2 en γ et que (u1)′ = (u2)′ en γ, et donc que la réunion de u1 et u2

forme une solution de l’équation homogène sur tout Ω qui ne peut être que 0.Ainsi, on peut considérer la méthode comme une itération sur les données de Fourier g1

n et g2n.

Ces données étant connues, on peut calculer u1 par les équations

(u1n+1)′′ = 0, u1

n+1(0) = 0, (u1n+1)′(γ) + λu1

n+1(γ) = g2n,

ce qui donne

u1n+1(x) =

g2n

1 + λγx,

et permet de calculer le flux g1n+1 qui sera passé au second domaine à l’itération suivante

g1n+1 = −(u1

n+1)′(γ) + λu1n+1(γ) =

λγ − 1

λγ + 1g2n.

De la même façon on trouve

g2n+1 =

λ(1− γ)− 1

λ(1− γ) + 1g1n.

Ainsi, l’itération s’écrit globalement sous la forme(g1n+1

g2n+1

)=

(0 λγ−1

λγ+1λ(1−γ)−1λ(1−γ)+1 0

)(g1n

g2n

).

La convergence de la méthode est assurée si on montre que le rayon spectral de la matrice d’itération estplus petit que 1, ce qui est bien le cas ici.

On voit même que pour les choix particuliers suivants du paramètre

λ =1

γ, ou λ =

1

1− γ,

la matrice d’itération est nilpotente et donc que la méthode converge en 2 itérations.

2.2.2 Le cas 2D

Si on étudie tout d’abord l’équation 1D suivante −u′′ + ω2u = 0, l’analyse précédente montre que lamatrice d’itérations de la méthode s’écrit

Aω,λ =

(0 λ sinh(ω(1−γ))−ω cosh(ω(1−γ))

λ sinh(ω(1−γ))+ω cosh(ω(1−γ))λ sinh(ωγ)−ω cosh(ωγ)λ sinh(ωγ)+ω cosh(ωγ) 0

).

Comme on l’a vu cette équation modélise une situation 2D dans laquelle on a préalablement effectué unetransformation de Fourier en y.

Pour un paramètre λ fixé, le taux de convergence de la méthode est piloté par le plus grand rayon spectralde Aω,λ pour toutes les valeurs de ω présentes dans le système.

Si on imagine qu’on a discrétisé le système dans la variable y selon un maillage de pas h, la plus grandefréquence dans le système est de l’ordre ∼ 1/h.



On peut alors chercher le paramètre optimal en résolvant le problème suivant

infλ>0

(sup

ω∈[0,1/h]

ρ(Aω,λ)

).

On peut montrer que ce paramètre optimal est alors de l’ordre de C/√h.

2.3 La preuve de convergenceThéorème I.11

Les suites (uin)n obtenues par la méthode de Schwarz sans recouvrement vérifient

uin −−−−n→∞

u|Ωi, dans H1(Ωi) pour tout i.

Preuve :Remarquons tout d’abord que, quitte à soustraire la solution u du problème limite, il suffit de montrer le

résultat pour u = 0, f = 0 et g = 0. C’est-à-dire de montrer la convergence faible vers 0 des approximationsdans le cas f = 0 et g = 0.

En guise de préliminaire, écrivons l’équation vérifiée par uin+1 − uin−1 sur le domaine Ωi. Celle-ci s’écrit−∆(uin+1 − uin−1) = 0, dans Ωi,

uin+1 − uin−1 = 0, sur ∂Ω ∩ ∂Ωi,

∂(uin+1 − uin−1)

∂νij+ λ(uin+1 − uin−1 − 2ujn) = 0, sur γij .

(I.20)

• On commence par multiplier l’équation (I.20) par uin+1 − uin−1 et intégrer par parties∫Ωi

|∇(uin+1 − uin−1)|2 dx+ λ∑j 6=i

∫γij

|uin+1 − ujn|2 dx = λ∑j 6=i

∫γij

|uin−1 − ujn|2 dx.

On somme sur i et sur n pour obtenir∑n≥0

∑i

∫Ωi

|∇(uin+1 − uin−1)|2 dx < +∞, (I.21)

et la borne

supn≥0

∑i 6=j

∫γij

|uin+1 − ujn|2 dx

< +∞. (I.22)

• Sur tous les domaines Ωi qui touchent le bord de Ω, de sorte que uin+1 − uin−1 est nul sur une partiedu bord de Ωi et on peut utiliser l’inégalité de Poincaré dans Ωi pour majorer les normes L2(Ωi) par lanorme du gradient.

Pour les domaines qui ne touchent pas le bord, on utilise les conditions de transmission et le lemmesuivant

Lemme I.12

Pour tout domaine O et γ0 ⊂ ∂O d’intérieur non vide dans ∂O, il existe une constante C > 0 telleque pour tout u ∈ H1(O) telle que ∆u ∈ L2(O) on a

‖u‖H1(O) ≤ C

(‖∇u‖L2(O) + ‖∆u‖L2(O) +

∥∥∥∥∂u∂ν + λu

∥∥∥∥H−1/2(γ0)

).



Ceci permet de proche en proche d’obtenir des estimations des normes L2(Ωi) sur tous les domaines.

On déduit ainsi de (I.21) l’inégalité∑n≥0

∑i

∫Ωi

|uin+1 − uin−1|2 dx < +∞, (I.23)

puis par le théorème de traces ∑n≥0

∑i 6=j

∫γij

|uin+1 − uin−1|2 dx < +∞. (I.24)

• Maintenant on multiplie (I.20) par uin+1 et on intègre par parties∫Ωi

∇(uin+1 − uin−1) · ∇uin+1 dx+ λ∑j 6=i

∫γij

(uin+1 + uin−1 − 2ujn)uin+1 dx.

On utilise les formules algébriques suivantes

∇(uin+1 − uin−1) · ∇uin+1 =1

2|∇uin+1|2 −

1

2|∇uin−1|2 +

1

2|∇(uin+1 − uin−1)|2,

(uin+1 + uin−1 − 2ujn)uin+1 =1

2|uin+1|2 +

1

2|uin−1|2 − |ujn|2 + |uin+1 − ujn|2 −

1

2|uin+1 − uin−1|2.

Ce qui donne

1

2

∫Ωi

|∇uin+1|2 dx+λ

2

∑j 6=i

∫γij

|uin+1|2 dx+λ

2

∑j 6=i

∫γij

|uin−1|2 dx

+1

2

∫Ωi

|∇(uin+1 − uin−1)|2 dx+ λ∑j 6=i

∫γij

|uin+1 − ujn|2

=1

2

∫Ωi

|∇uin−1|2 dx+ λ∑j 6=i

∫γij

|ujn|2 dx

+λ

2

∑j 6=i

∫γij

|uin+1 − uin−1|2 dx.

On somme maintenant sur i et on introduit

An =∑i

∫Ωi

|∇uin|2 dx,

Bn = λ∑i

∑j 6=i

∫γij

|uin|2 dx,

Cn = λ∑i

∑j 6=i

∫γij

|uin+1 − ujn|2 dx,

Dn =λ

2

∑i

∑j 6=i

∫γij

|uin+1 − uin−1|2 dx.

Il vient1

2An+1 +

1

2(Bn+1 +Bn−1) + Cn ≤

1

2An−1 +Bn +Dn,

ou encore1

2An+1 +

1

2(Bn+1 −Bn) + Cn ≤

1

2An−1 +

1

2(Bn −Bn−1) +Dn.



Si on somme cette inégalité entre n = 1 et N , on trouve

1

2(AN+1 +AN ) +

1

2(BN+1 −BN ) +

N∑n=1

Cn ≤1

2(A0 +A1) +

1

2(B1 −B0) +

N∑n=1

Dn. (I.25)

On calcule

BN+1 −BN = λ∑i6=j

∫γij

|uiN+1|2 − |ujN |

2 dx

= λ∑i6=j

∫γij

(uiN+1 − ujN )(uiN+1 + ujN ) dx,

d’où

|BN+1 −BN | ≤ λ√CN

∑i6=j

∫γij

|uiN+1|2 + |uiN |2 1

2

.

Mais par l’inégalité de Poincaré (pour les sous-domaines touchant le bord) et une utilisation répétée dulemme I.12 pour les autres, on a l’estimation des traces∑

i

∑j 6=i

∫γij

|uin|2 dx ≤ C∑i

∑j 6=i

‖uin‖2H1(Ωi)

≤M

(∑i

‖∇uin‖2L2(Ωi)

).

(I.26)

Ceci montre qu’il existe une constante M ne dépendant que des données vérifiant

|BN+1 −BN | ≤M√CN (1 +

√AN +AN+1).

Grâce à l’inégalité (I.22) qui montre que la suite (Cn)n est bornée, on conclut finalement que

|BN+1 −BN | ≤ M(1 +√AN +AN+1).

Par l’inégalité de Young, on obtient

1

2|BN+1 −BN | ≤

M + M2

2+

1

4(AN +AN+1),

et donc (I.25) donne

1

4(AN+1 +AN ) +

N∑n=1

Cn ≤M + M2

2+

1

2(A0 +A1) +

1

2(B1 −B0) +

N∑n=1

Dn. (I.27)

Enfin, d’après (I.24), la série de terme général Dn est convergente et donc, in fine, on a montré

supN≥1

AN < +∞,

∑n≥1

Cn < +∞.

Avec (I.26), on a donc finalement montré en particulier que

(uin)n est bornée dans H1(Ωi) pour tout i,

et‖uin+1 − ujn‖L2(γij) −−−−→

n→∞0. (I.28)



• Des considérations précédentes, on déduit que les suites

(u1n)n, . . . , (u

Jn)n, et (u1

n+1)n, . . . , (uJn+1)n,

sont toutes bornées dans les Sobolev respectifs et on peut donc extraire une même sous-suite et trouverdes ui, ui ∈ H1(Ωi) tels que

uiϕ(n) −−−−n→∞ui, dans H1(Ωi)

uiϕ(n)+1 −−−−n→∞ui, dans H1(Ωi).

De plus, d’après (I.23), nous avons également

uiϕ(n)+2 −−−−n→∞ui, dans H1(Ωi).

Il est clair que les ui et ui satisfont l’équation −∆ui = −∆ui = 0 dans chaque Ωi ainsi que lesconditions de Dirichlet sur ∂Ωi ∩ ∂Ω. De plus, d’après (I.28), on a les égalités

ui = uj , sur γij , ∀i 6= j. (I.29)

En passant à la limite (faible) dans la condition de Fourier sur chaque interface, on trouve également

∂ui

∂νij=

∂uj

∂νij, sur γij , ∀i 6= j. (I.30)

Par passage à la limite dans les équations, ui et ui sont solutions, dans chaque sous-domaine, des pro-blèmes

−∆ui = 0,∂ui

∂νij=

∂uj

∂νij,

−∆ui = 0,∂ui

∂νij=

∂uj

∂νij.

On soustrait ces deux équations, on multiplie par ui − ui et on intègre par parties, on trouve

0 =

∫Ωi

|∇(ui − ui)|2 dx−∑j 6=i

∫γij

(∂ui

∂νij− ∂ui

∂νij

)(ui − ui) dx, ∀i ∈ 1, ..., J.

En sommant sur i et en regroupant les termes de chaque interface

0 =∑i

∫Ωi

|∇(ui−ui)|2 dx−∑i<j

∫γij

[(∂ui

∂νij− ∂ui

∂νij

)(ui − ui) +

(∂uj

∂νji− ∂uj

∂νji

)(uj − uj)

]dx.

On utilise alors les conditions de transmissions obtenues à la limite (I.29) et (I.30) (et on remarque que lesnormales νij et νji sont opposées) pour conclure que chacun des termes d’interface dans cette sommeest nul.

On conclut de tout cela que ui = ui pour tout i. A la lumière des ces égalités, on constate que lesconditions de transmission (I.29) (I.30) deviennent

ui = uj , et∂ui

∂νij=

∂uj

∂νijsur γij ,∀i 6= j.

Ainsi, la fonction v définie sur Ω en recollant les fonctions ui est bien dans H10 (Ω) (raccord continu aux

interfaces) et vérifie l’équation −∆v = 0 dans Ω (raccord des flux). Ceci prouve donc que v = 0.

Par unicité de cette valeur d’adhérence faible, on a bien établi les convergences

uin −−−−n→∞

0, dans H1(Ωi) pour tout i.


BIBLIOGRAPHIE 23

BIBLIOGRAPHIE

[Gan08] Martin J. Gander, Schwarz methods over the course of time, Electron. Trans. Numer. Anal. 31 (2008),228–255, http://www.unige.ch/~gander/Preprints/SchwarzHistorical.pdf.MR 2569603 (2011a :65440)

[Gan09] , Schwarz methods over the course of time, http://www.unige.ch/~gander/Preprints/SchwarzTalk.pdf, 2009.

[Hol94] Michael Holst, Algebraic schwarz methods, http://ccom.ucsd.edu/~mholst/pubs/dist/Hols94c.pdf, 1994.

[Lio88] P.-L. Lions, On the Schwarz alternating method. I, First International Symposium on Do-main Decomposition Methods for Partial Differential Equations (Paris, 1987), SIAM, Phi-ladelphia, PA, 1988, http://www.ddm.org/DD01/On_the_Schwarz_Alternating_Method._I.pdf, pp. 1–42. MR 972510 (90a :65248)

[Lio89] , On the Schwarz alternating method. II. Stochastic interpretation and order pro-perties, Domain decomposition methods (Los Angeles, CA, 1988), SIAM, Philadelphia,PA, 1989, http://www.ddm.org/DD02/On_the_Schwarz_Alternating_Method_2_Stochastic_Interpretation_and_Order_properties.pdf, pp. 47–70. MR 992003(90e :65140)

[Lio90] , On the Schwarz alternating method. III. A variant for nonoverlapping subdomains, ThirdInternational Symposium on Domain Decomposition Methods for Partial Differential Equations(Houston, TX, 1989), SIAM, Philadelphia, PA, 1990, http://www.ddm.org/DD03/On_the_Schwarz_Alternating_Method_III_A_Variant_for_Nonoverlapping_Subdomains_(Lions).pdf, pp. 202–223. MR 1064345 (91g :65226)

[TW05] Andrea Toselli and Olof Widlund, Domain decomposition methods—algorithms and theory, Sprin-ger Series in Computational Mathematics, vol. 34, Springer-Verlag, Berlin, 2005. MR 2104179(2005g :65006)


Documents

Méthodes de décomposition de domaine de type Schwarzfboyer/_media/enseignements/m2... · Par ailleurs, on voit que l’algorithme est complètement déterminé par la seule valeur