Fichier PDF

Partage, hébergement, conversion et archivage facile de documents au format PDF

Partager un fichier Mes fichiers Convertir un fichier Boite à outils Recherche Aide Contact



tipe ens .pdf



Nom original: tipe_ens.pdf

Ce document au format PDF 1.5 a été généré par TeX / MiKTeX pdfTeX-1.40.12, et a été envoyé sur fichier-pdf.fr le 27/07/2014 à 18:44, depuis l'adresse IP 176.182.x.x. La présente page de téléchargement du fichier a été vue 364 fois.
Taille du document: 243 Ko (9 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


Fonctions harmoniques discr`etes et ´equation de
Laplace
KGD
July 27, 2014

On s’int´eresse dans le cadre de ce TIPE `a la notion de fonction harmonique sur un graphe et `
a son application `a la r´esolution num´erique de
l’´equation de Laplace.

1

Probl`
eme de Dirichlet sur un graphe `
a bord

Dans toute cette section, G = (S, A) d´esigne un graphe fini connexe et f
une application de G dans R.

1.1


efinitions

On num´erote arbitrairement les sommets de G: S = {s1 , . . . , sn }.

efinition 1. On appelle
laplacien de f l’application ∆f : S → R d´efinie
X
par ∀x ∈ G, ∆f (x) =
(f (x) − f (y)).
y voisin de x

Proposition-d´
efinition 1. L’application laplacien ∆ : F(S, R) → F(S, R)
est un endomorphisme de F(S, R). On appelle matrice laplacienne du graphe
la matrice de l’endomorphisme laplacien
dans la base (ei )1≤i≤n o`
u on d´efinit

1 si i = j
ei sur S par ∀j ∈ [[1, n]], ei (sj ) =
.
0
sinon

efinition 2. Soit x un sommet de G. On dit que f est harmonique au
point x si ∆f (x) = 0.

1.2

Formulation du probl`
eme

On consid`ere un ensemble ∂S de sommets de G qu’on appellera bord de G
˚ = S \ ∂S.
et on notera S

efinition 3. On dira que f est harmonique sur G si f est harmonique en
˚
tout point de S.
1

Soit g : ∂S 7→ R. On va montrer qu’il existe une unique fonction f :
S → R harmonique sur G v´erifiant f|∂S = g.
On montre dans un premier temps le lemme suivant qui va assurer l’unicit´e:
Lemme 1 (Principe du maximum discret). Soit f : S → R harmonique sur
G. Les extrema de f sont atteints sur le bord. Plus pr´ecis´ement, si f atteint
˚ alors, il existe y ∈ ∂S tel que f (x) = f (y).
un extremum en x ∈ S,
On en d´eduit l’unicit´e de l’´eventuelle solution du probl`eme. En effet,
si deux fonctions f1 et f2 harmoniques sur G v´erifient f1|∂S = f2|∂S , alors
f1 − f2 est harmonique sur G et v´erifie (f1 − f2 )|∂S = 0. Les extrema de
f1 − f2 sont donc nuls donc f1 = f2 .
On remarque que le principe de la d´emonstration du lemme permet d’obtenir
la proposition suivante, un peu plus forte:
Proposition 1 (Principe du maximum fort). Supposons le graphe constitu´e
des sommets int´erieurs et des arˆetes reliant les sommets int´erieurs connexe.
Alors si f : S → R harmonique sur G atteint un extremum en un point
int´erieur, elle est constante.
La condition est optimale comme le montre l’exemple suivant:
s5

En prenant ∂S = {s3 , s4 } et
en consid´erant l’application f d´efinie
8
7
par f (s1 ) = , f (s2 ) = , f (s3 ) =
3
3
3, f (s4 ) = 2, f (s5 ) = f (s6 ) = 3, f est
harmonique sur le graphe et atteint
˚ mais n’est
son maximum en s6 ∈ S
pas constante.

s3
s1

s6

s4
s2
On montre ensuite l’existence d’une telle fonction en deux ´etapes. On
r´eduit le probl`eme `
a un probl`eme ´equivalent:
Lemme 2. Soit f : S → R v´erifiant f|∂S = g. Si f minimise la forme
quadratique
X
X
E : f 7→
(f (x) − f (y))2
x∈S y voisin de x

parmi les fonctions d´efinies sur S co¨ıncidant avec g sur ∂S, alors elle est
harmonique sur G.
On montre ensuite l’existence du minimum de la forme quadratique par
des consid´erations d’alg`ebre bilin´eaire et de topologie, ce qui nous permet
finalement d’´enoncer le th´eor`eme suivant.
2

Th´
eor`
eme 1 (Prolongement harmonique). Soit g : ∂S → R. Il existe une
unique fonction f : S → R harmonique sur G v´erifiant f|∂S = g.

2
2.1

Application `
a la r´
esolution de l’´
equation de Laplace
Introduction et quelques notations

On va tenter de confirmer que l’analogie formelle entre les ´enonc´es pr´ec´edents
et les ´enonc´es concernant les fonctions harmoniques sur un domaine du plan
n’est pas accidentelle et que la connaissance de fonctions harmoniques sur
des graphes bien choisis permet effectivement d’obtenir des informations sur
les fonctions harmoniques sur un domaine du plan.
On s’est ici int´eress´e au cas du carr´e K = [0, 1]2 . On consid`ere f : K → R
˚ et v´erifiant ∀x ∈ K,
˚ ∆f = 0.
continue de classe C 2 sur K

2
1
n−1

Pour tout n de N , on note Kn = 0, , . . . ,
,1
en convenant
n
n




i j
k l
que
,
est voisin de
,
dans Kn si et seulement si |i − k| +
n n
n n


n−1
1
,1 ∪
|j − l| = 1. On pose ´egalement ∂Kn = {0, 1} × 0, , . . . ,
n
n


n−1
1
, 1 × {0, 1}. On peut alors noter fn l’unique fonction har0, , . . . ,
n
n
monique sur Kn v´erifiant fn|Kn = f|Kn .
On va montrer que ||f − fn ||∞,Kn −→ 0.
n→+∞

2.2

Tentative d’exp´
erimentation num´
erique

On a tent´e de constater num´eriquement la convergence de fn vers f en
´etudiant l’´evolution de la diff´erence ||f − fn ||∞,Kn en fonction de n.
Pour cela, on a tent´e de calculer les fn pour de plus en plus grandes
valeurs de n. On a alors mis en ´evidence le fait que le calcul des fn revient `
a l’inversion d’un syst`eme de taille (n − 1)2 × (n − 1)2 . Puisque
l’inversion de matrice est de complexit´e O(N 3 ) o`
u N est la taille de la
matrice, l’algorithme na¨ıf de calcul de fn adopt´e est de complexit´e O(n6 ).
Les limitations mat´erielles se sont rapidement faites sentir (le calcul peine
pour n = 20 et deux heures n’ont pas suffi au calcul pour n = 50).
On a n´eanmoins ´et´e en mesure de constater, ne serait-ce que graphiquement, que les fonctions harmoniques sur Kn fournissent effectivement une
approximation des fonctions harmoniques sur K. Toutefois, les valeurs
num´eriques ne le mettent pas toujours en ´evidence (ceci peut ˆetre attribu´e
au faible nombre de mesures).

3

2.3


emonstration de la convergence

Pour d´emontrer effectivement la convergence des fonctions fn , on remarque
i
dans un premier temps qu’en notant xi = yi = pour tout i ∈ [[0, n]], on a
n
par la formule de Taylor-Lagrange, si 1 ≤ i, j ≤ n − 1,
ci,j
f (xi+1 , yj ) + f (xi , yj+1 ) + f (xi−1 , yj ) + f (xi , yj−1 ))
= f (xi , yj ) + 4
4
n
4

4

o`
u les ci,j sont des combinaisons lin´eaires de valeurs de ∂∂xf4 et ∂∂yf4 sur K et
sont major´es ind´ependamment de n, disons par c. Puisque f et fn co¨ıncident
au bord, on a donc en soustrayant l’´egalit´e traduisant le fait que fn est
harmonique en (xi , yj ):
X
ci,j
(f − fn )(x, y) = − 4
4(f − fn )(xi , yj ) −
n
(x,y) voisin int´
erieur de (xi ,yj )






C1
−ci,1
1




Ce qui s’´ecrit An (F − Fn ) = 4 C o`
u C =  ...  avec Ci =  ...  et
n
Cn−1
−ci,n−1




4 −1 0
0
T
−In−1
0
0




..


−1 4 −1 . . .
−In−1
.
T
−In−1








..
..
..
..
..
..
,
,
T
=
An =  0


. 0
.
.
.
.
.
0 

0





..
..


. −1 4 −1
.
−In−1
T
−In−1 
0
0 −1 4
0
0
−In−1
T








F1
f (xi , y1 )
Fn,1
fn (xi , y1 )




 . 


..
..
F =  ...  et Fi = 
, Fn =  ..  , Fn,i = 
.
.
.
Fn−1
f (xi , yn−1 )
Fn,n−1
fn (xi , yn−1 )
An ∈ M(n−1)2 (R), T ∈ Mn−1 (R).
Ainsi, on a F − Fn = n14 A−1
n C. On montre alors la convergence en obtenant
une majoration de la norme de A−1
. On calcule dans unpremier temps les
n 
0 1
0
0

.
.. 
1 0

1


 .. .. ..

valeurs propres de la matrice Bn = 0
 ∈ Mn (R):
.
.
.
0


 ..


. 1
0 1
0
0
1 0



Lemme 3. Les valeurs propres de Bn sont les 2 cos
, pour k allant
n+1
de 1 `
a n.
Une id´ee de d´emonstration consiste `a obtenir une formule de r´ecurrence
sur les χBn et d’exprimer les polynˆomes caract´eristiques en fonction de
4

polynˆ
omes de Tchebychev de seconde esp`ece.
On en d´eduit puisque T = 4In−1 − Bn−1 que


SpecR (T ) = {4 − 2 cos
, 0 ≤ k ≤ n − 2}
n
En remarquant que An = T ⊗ In−1 − In−1 ⊗ Bn−1 et que T ⊗ In−1 et
In−1 ⊗ Bn−1 sont codiagonalisables (cf. annexe) de valeurs propres les
valeurs propres de T pour la premi`ere et les valeurs propres de Bn−1 pour
la deuxi`eme, chacune de multiplicit´e n − 1, on en tire le lemme:
Lemme 4. Les valeurs propres de A−1
ees par
n sont positives et major´

1
2

8 sin

π
2n

On a alors pour tout (xi , yj ) int´erieur
(f − fn )(xi , yj ) ≤ ||F − Fn ||2 ≤
Or, on a ||C||2 ≤ (n−1)c et |||A−1
n ||| ≤
Ainsi, on a finalement le th´eor`eme:

1
8 sin2

1
|||A−1
n ||| ||C||2
n4
π
2n

2
et donc |||A−1
n ||| = O(n ).

Th´
eor`
eme 2. L’´ecart maximal v´erifie ||f − fn ||∞,Kn

3


1
=O
n

Conclusion

On observe ainsi comment on peut obtenir, par des moyens ´el´ementaires, des
informations sur un probl`eme complexe de calcul diff´erentiel en le ramenant
`a un probl`eme d’alg`ebre lin´eaire. Le proc´ed´e nous fournit une forme de
transfert: On part d’une fonction harmonique sur une partie du plan (dont
on ne connait que les valeurs au bord), ce qui nous permet de construire un
ensemble de fonctions harmoniques sur des graphes de plus en plus grands
”approchant” cette partie. On peut alors obtenir les valeurs de la fonction
de d´epart sur l’int´erieur du domaine par passage `a la limite.
Le r´esultat n’a en r´ealit´e que peu d’int´erˆet pratique puisque le calcul effectif
des fonctions harmoniques sur un graphe contenant un nombre important
de sommets est tr`es long et que la vitesse de convergence n’est pas des
meilleures. Il a toutefois le m´erite d’illustrer une forme de transfert en
math´ematiques.

5

.

Annexes

emonstrations de la premi`
ere section
D´emonstration du Lemme 1 (et de la proposition 1). Soit f harmonique sur
˚ tel que f (x) soit le maximum
G = (S, A) connexe de bord ∂S et soit x ∈ S
de f sur S. Notons, pour tout x ∈ S, V (x) = {y ∈ S, {x, y} ∈ A} son
voisinage imm´ediat.
X
(f (x) − f (y)) = 0 donc
On a alors ∀y ∈ V (x), f (x) − f (y) ≥ 0 or
y∈V (x)

∀y ∈ V (x), f (x) = f (y). Soit alors y ∈ ∂S tel qu’il existe k ∈ N et
˚ et
(a0 , a1 , . . . , ak ) ∈ S k+1 tels que a0 = x, ak = y, ∀i ∈ [[1, k − 1]], ai ∈ S
∀i ∈ [[1, k]], ai ∈ V (ai−1 ). On a, par r´ecurrence que ∀i ∈ [[1, k]], f (ai ) = f (x)
donc f (x) = f (y) donc le maximum de f est bien atteint sur le bord. Par
une d´emonstration analogue (ou en consid´erant −f ), on montre de mˆeme
que le minimum de f est atteint sur ∂S.
Si en outre, le graphe constitu´e des sommets int´erieurs et des arˆetes les reliant est connexe, on peut relier x `a tout autre sommet y par un chemin
˚ On en d´eduit
(a0 , . . . , ak ) o`
u tous les ai pour 0 ≤ i ≤ k − 1 sont dans S.
alors par ce qui pr´ec`ede que f est constante.
D´emonstration du Lemme 2 et du Th´eor`eme 1. On note F = F(S, R). F
est un R-espace vectoriel
de dimension card S (en effet la famille (δx )x∈S
1 si x = t
est une base de F ). Soit E : F → R
avec ∀t ∈ S, δx (t) =
0
sinon
X X
d´efinie par ∀f ∈ F, E(f ) =
(f (x) − f (y))2 .
x∈S y∈V (x)

E est une forme quadratique sur F issue de la forme bilin´eaire sym´etrique
positive h·, ·i d´efinie sur F 2 par
X X
∀(f, g) ∈ F 2 hf, gi =
(u(x) − u(y))(v(x) − v(y))
x∈S y∈V (x)

Soit K l’espace des fonctions constantes sur S et H un suppl´ementaire de
K dans F .
On a, pour tout f de H, hf, f i = 0 ⇔ ∀x ∈ S, ∀y ∈ V (x), f (x) = f (y) ⇔ f ∈
K ∩H = {0}. h·, ·i|H×H est donc un produit scalaire donc on a E = H ⊕H ⊥ ,
or H ⊥ est de dimension 1 et on a d’´evidence K ⊂ H ⊥ donc K = H ⊥ . On
peut donc d´efinir une projection orthogonale pH sur H et, pour tout f de
F , on a E(f ) = E(pH (f )).
Soit Fg = {f ∈ F, f|∂S = g}. Fg est un sous-espace affine de F donc sa
projection orthogonale sur H est un sous-espace affine de H, donc un ferm´e
de H. Puisque H est de dimension finie, il existe f ∈ pH < Fg > telle que
E(f ) =
inf
E(u) = inf E(u)
|{z}
u∈pH <Fg > |{z}
u∈Fg

||f −0||2

||u−0||2

6

f est la projection sur H d’une fonction u ∈ Fg qui minimise donc la fonction
E. Or, en identifiant F `
a R|S| , E peut ˆetre vu comme une application C 1
(car polynomiale) en les |S| valeurs de son argument.
Plus pr´ecis´ement, posons n = |S| et num´erotons les sommets du graphe,
de sorte que S = {s1 , s2 , . . . , sn }. On peut supposer la num´erotation telle
qu’il existe k ∈ [[1, n − 1]] tel que ∂S = {ak+1 , . . . , an }. On note, pour tout
i ∈ [[1, n]], Vi = {j ∈ [[1, n]], {ai , aj } ∈ A}. On d´efinit alors l’application
E : Rn → R d´efinie par
n

∀(x1 , . . . xn ) ∈ R , E(x1 , . . . , xn ) =

n X
X

(xi − xj )2

i=1 j∈Vi

E est une application polynomiale en ses n variables et est donc C 1 et on a
∀f ∈ F, E(f ) = E(f (a1 ), . . . , f (an )). E et E ont donc les mˆemes extrema. En
particulier, puisque u est un minimum de E|Fg , (u(a1 ), . . . , u(ak )) est un minimum de l’application partielle Epart : (x1 , . . . , xk ) 7→ E(x1 , . . . , xk , g(ak+1 ), . . . , g(an ))
et annule toutes ses d´eriv´ees partielles. Or, on a
∀i ∈ [[1, k]], ∀(x1 , . . . , xk ) ∈ Rk ,

∂Epart
∂E
(x1 , . . . , xk ) =
(x1 , . . . , xk , g(ak+1 ), . . . , g(an ))
∂xi
∂xi

On a donc:
∀i ∈ [[1, k]],

∂E
∂E
(u(a1 ), . . . , u(ak ), g(ak+1 ), . . . , g(an )) =
(u(a1 ), . . . , u(an )) = 0
∂xi
∂xi

Or:
∀i ∈ [[1, k]], ∀(x1 , . . . , xn ) ∈ Rn ,

X
∂E
(x1 , . . . , xn ) = 4
(xi − xj )
∂xi
j∈Vi

D’o`
u:
∀i ∈ [[1, k]], 4

X

(u(ai ) − u(aj )) = 0

j∈Vi

Ce qui se r´ecrit, au vu de la d´efinition des Vi et de la num´erotation des
sommets:
X
˚
∀x ∈ S
(u(x) − u(y)) = 0
y∈V (x)

u est donc harmonique sur G et u|∂S = g. D’autre part, si v est harmonique
et v´erifie v|∂S = g, u − v sera harmonique et on aura (u − v)|∂S = 0. Or,
d’apr`es le lemme, u − v atteint son maximum et son minimum sur ∂S donc
u − v est la fonction nulle sur S et on a donc u = v.

7


emonstrations de la seconde section
Soit n ≥ 3. On
notera pour tout n ∈ N, Pn =
0
0

..

.
1


..
..
.
.
0 . En d´eveloppant par rapport `a

1 −X
1
0
1
−X

−X
1
0
· · · 0



..
1

.
−X 1



.
.
.
..
..
. . 0 =
la derni`ere colonne, on obtient Pn = −XPn−1 − 0




..

.
1 −X 1

0
···
0
1

D´emonstration du
lemme 3.
−X
1


1
−X


..
χBn On a Pn = 0
.


..

.

0

−XPn−1 − Pn−2 . Puisque P1 = −X et P2 = X 2 − 1, on a par r´ecurrence
sin((n + 1)θ)
. Pn a donc n racines,
∀n ∈ N∗ , ∀θ ∈ R \ πZ, Pn (−2 cos θ) =
sin θ



les −2 cos
avec 1 ≤ k ≤ n, qui sont deux `a deux distinctes.
n+1
Pr´eliminaire `
a la d´emonstration du lemme 4

efinition 4. Soient A = (aij )1≤i,j≤n et B ∈ Mn (R). On appelle produit tensoriel de A et B et on note A ⊗ B la matrice de l’endomorphisme de
t
Mn (R) ΨA,B : M
 7→ AM B dans la base (E1,1
, . . . , En,1 , E1,2 , . . . , En,2 , . . . , En,n ).
a1,1 B a1,2 B · · · a1,n B
 a2,1 B a2,2 B · · · a2,n B 


On a A ⊗ B =  .
..
.. 
 ..
.
···
. 
an,1 B an,2 B · · ·

an,n B

Proposition 2.
1. Soient A, A0 , B, B 0 ∈ R. On a AA0 ⊗ BB 0 = (A ⊗
0
0
B)(A ⊗ B ).
2. Soient A, B ∈ Mn (R). A ⊗ B et B ⊗ A sont semblables.
Proof.

1. On a ΨAA0 ,BB 0 = ΨA,B ◦ ΨA0 ,B 0

2. Si T d´esigne l’endomorphisme transposition M 7→t M , on a ΨA,B =
T ◦ ΨB,A ◦ T . Puisque T est involutif, le passage aux matrices donne
une ´egalit´e de similitude entre A ⊗ B et B ⊗ A.

8

D´emonstration du Lemme 4. On a




0
−In−1
(0)
T
(0)


0
−In−1

 −In−1

T

 

.
.
.
.
.
.
An = 




.
.
.
..


 
.

−In−1
0
−In−1 
(0)
T
(0)
−In−1
0
Donc An = T ⊗ In−1 − In−1 ⊗ Bn−1 . Puisque T est diagonalisable, T ⊗
In−1 
l’est. Par ailleurs, In−1 ⊗Bn−1 est semblable `a Bn−1 ⊗ In−1 , c’est `a
Bn−1
(0)


Bn−1


dire 
 qui est diagonalisable puisque Bn−1 l’est
..


.
(0)
Bn−1
d’apr`es le Lemme 3. Par ailleurs, les deux matrices commutent puisque
d’apr`es le 1) de la proposition ci-dessus, on a (T ⊗ In−1 )(In−1 ⊗ Bn−1 ) =
(In−1 ⊗ Bn−1 )(T ⊗ In−1 ) = T ⊗ Bn−1 . Elles sont donc codiagonalisables.

Les



− 2 cos
valeurs propres de An sont donc de la forme 4 − 2 cos
n
n
avec 1 ≤ k, l ≤
Elles sont donc toutes strictement positives et minor´ees
πn−1.

par 4 − 4 cos
.
n
1

Ainsi, les valeurs propres de A−1
ees par
n sont major´
2 π
8 sin 2n

References
[1] Cognet M. Alg`ebre bilin´eaire. Br´eal, 2002.
[2] G´erard Meurant. A review on the inverses of symmetric tridiagonal
and block tridiagonal matrices. SIAM Journal on Matrix Analysis and
Applications, 13(3):707–728, juillet 1992.
[3] Ciarlet P. Introduction `
a l’analyse num´erique matricielle et optimisation.
Dunod, 1998.

9


Documents similaires


Fichier PDF tipe ens
Fichier PDF tipe ens 1
Fichier PDF theorie des graphes
Fichier PDF fq2
Fichier PDF chapitre 2 problemes de graphes
Fichier PDF graphe


Sur le même sujet..