Cours-ChapitreI

Cours-ChapitreI

Documents
5 pages
Lire
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

ållåså¥lUNIVERSITE DE BOURGOGNE L3-MATHEMATIQUESAnalyse Nume´rique Ele´mentaire,NORMES MATRICIELLES ET CONDITIONNEMENT1. Rappel sur les normes et les normes matricielles:(a) Notations:n-K est le corpsR ouC.K est l’espace vectoriel surK des colonnes a` n e´le´ments dansK.n-K est muni du produit scalaire usuel note´ (ou` ¯ est la conjugaison complexe):   x y1 1n    t . n . n¯ . .< X|Y >= x y¯ = XY, X = ∈K , Y = ∈K .   i i . .i=1 x yn n-L’espace vectoriel des matrices a` coefficients dansK, a` nlignes et p colonnes est note´M (K). Il est de dimensionn,pnp surK. Quand n= p, on le noteM (K): on a un produit interne qui en fait une alge`bre.n- Soit M∈M (C). On appelle spectre de M , note´ (M), l’ensemble de ses valeurs propres dansC.n(b) Normes: De´finitions+i. Une norme sur une espace vectoriel E surK est une application de E dansR , note´e||.|| , telle que:-||v||= 0⇔ v= 0,-||v + v ||≤||v ||+||v ||, ∀v ,v ∈ E,1 2 1 2 1 2-|| v||=| |||v||∀v∈ E, ∀ ∈C.ii. Une norme sur l’espaceM (K) est appele´e matricielle si et seulement si elle ve´rifie:n||AB||≤||A||||B||, ∀A,B∈M (K).n(c) Equivalence des Normes′ ′i. De´finition: Soient deux normes note´es||.|| et||.|| sur un espace vectoriel E surK.||.|| et||.|| sont e´quivalentessi et seulement s’ il existe deux re´els positifs a et b tels que:′a||v||≤||v||≤ b||v||, ∀v∈ E.ii. Cas de la dimension finie:Dans un espace de dimension finie , toutes les normes sont e´quivalentes.iii. Remarques:En dimension ...

Sujets

Informations

Publié par
Nombre de visites sur la page 38
Langue Français
Signaler un problème

å
l
l
å
s
å
¥
l
UNIVERSITE DE BOURGOGNE L3-MATHEMATIQUES
Analyse Nume´rique Ele´mentaire,
NORMES MATRICIELLES ET CONDITIONNEMENT
1. Rappel sur les normes et les normes matricielles:
(a) Notations:
n-K est le corpsR ouC.K est l’espace vectoriel surK des colonnes a` n e´le´ments dansK.
n-K est muni du produit scalaire usuel note´ (ou` ¯ est la conjugaison complexe):
   
x y1 1
n    t . n . n¯ . .< X|Y >= x y¯ = XY, X = ∈K , Y = ∈K .   i i . .
i=1 x yn n
-L’espace vectoriel des matrices a` coefficients dansK, a` nlignes et p colonnes est note´M (K). Il est de dimensionn,p
np surK. Quand n= p, on le noteM (K): on a un produit interne qui en fait une alge`bre.n
- Soit M∈M (C). On appelle spectre de M , note´ (M), l’ensemble de ses valeurs propres dansC.n
(b) Normes: De´finitions
+i. Une norme sur une espace vectoriel E surK est une application de E dansR , note´e||.|| , telle que:
-||v||= 0⇔ v= 0,
-||v + v ||≤||v ||+||v ||, ∀v ,v ∈ E,1 2 1 2 1 2
-|| v||=| |||v||∀v∈ E, ∀ ∈C.
ii. Une norme sur l’espaceM (K) est appele´e matricielle si et seulement si elle ve´rifie:n
||AB||≤||A||||B||, ∀A,B∈M (K).n
(c) Equivalence des Normes
′ ′i. De´finition: Soient deux normes note´es||.|| et||.|| sur un espace vectoriel E surK.||.|| et||.|| sont e´quivalentes
si et seulement s’ il existe deux re´els positifs a et b tels que:

a||v||≤||v||≤ b||v||, ∀v∈ E.
ii. Cas de la dimension finie:
Dans un espace de dimension finie , toutes les normes sont e´quivalentes.
iii. Remarques:
En dimension finie, la convergence ou non d’une suite ne de´pend pas de la norme choisie: on prendra une
norme,meˆme inhabituelle , qui permet de conclure facilement. Par contre, un calcul d’erreur de´pendra de la
norme choisie.
(d) Exemples:
ni. Exemples surK :
On a les 3 normes usuelles suivantes:
 
nx1 ||X|| = |x|1 ii=1p . n n 2.∀X = ∈K , ||X|| = |x|  2 i. i=1
||X|| = sup{|x|, i= 1..n}+ ixn
ii. Normes surM (K).n
1l
r
l
r
l
r
l
r
r
l
r
l
s
l
l
l
6
l
6
l
r
r
r
l
r
r
r
r
l
r
l
r
l
r
¥
r
6
6
l
r
r
r
A. Normes subordonne´es:
nSoit une norme quelconque||.|| surK ; On appelle norme subordonne´e a` ||.|| surM (K) la norme note´en
|||.||| de´finie par:
||MX||∀M∈M (K),|||M|||= sup { }.n X=0 ||X||
B. Proprie´te´s e´le´mentaires d’une norme subordonne´e surM (K):n
n-||MX||≤|||M|||||X||,∀X∈K ;
n-|||M|||= inf{ /||MX||≤ ||X||,∀X∈K };
-|||MN|||≤|||M||||||N|||∀M,N∈M (K): toute norme subordonne´e est matricielle.n
n-|||I |||= 1 ou` I est la matrice identite´ dansK .n n
C. Norme de Frobe´nius:
De´finition:∀M∈M (K) on pose:n q
t ¯||M|| = Trace (M)M.F

C’est une norme matricielle qui n’est pas subordonne´e car||I || = n= 1 si n= 1.n F
(e) Proprie´te´s e´le´mentaires des normes subordonne´es|||.||| ,|||.||| ,|||.||| surM (K).1 2 n
i. Rayon spectral d’une matrice , valeurs singulie`res.
Soit M une matrice (n,n) a` coefficients dansK. M posse`de dansC n valeurs propres compte´es avec leur or-
dre de multiplicite´, note´es( , ,..., ) avec:1 2 n
0≤| |≤| |...,≤| |.1 2 n
• Rayon spectral : Definition et proprietes:´ ´ ´
– De´finition:
On appelle spectre de M, (M) l’ ensemble de ses valeurs propres dansC.
On appelle rayon spectral de M, (M) le plus grand module des valeurs propres de M, soit| |.n
– (⋆)Proprie´te´s du rayon spectral:
- Si M est hermitienne, semi-de´finie positive (⇔< MX|X >≥ 0), alors (M) est la plus grande des
valeurs propres.
t t¯ ¯- Pour toute matrice M deM (K) alors ( MM) est la plus grande valeur propre de MMn
t t¯ ¯et ( MM)= (M M).
Preuve:
-Si M est hermitienne alors toute valeur propre est re´elle. De plus , soit X un vecteur propre de M relatifi
2a` la valeur propre , alors< MX|X >= ||X|| ≥ 0 donc ≥ 0,∀i de 1 a` n. On a donc:i i i i i i
0≤ ≤ ...≤ .1 2 n
d’ou` : (M)= .n
t t¯ ¯- Dans le cas M quelconque MM est hermitienne semi-de´finie positive car< MMX|X >=< MX|MX >
t t t¯ ¯ ¯≥ 0 d’ou` ( MM) est la plus grande valeur propre de MM. En e´changeant les roˆles de M et M on obtient
t ¯le meˆme re´sultat pour M M.
t t t t¯ ¯ ¯ ¯Prouvons que : ( MM)= (M M). ( MM) est la plus grande valeur propre de MM et soit X un0
vecteur propre (non nul) relatif a` cette valeur propre. Alors:
t t t t¯ ¯ ¯ ¯MMX = ( MM)X ⇒(M M)MX = ( MM)MX .0 0 0 0
2 cas:
t t t¯ ¯ ¯-si MX = 0 alors MX est un vecteur propre de(M M) pour la valeur propre ( MM) et donc: ( MM)≤0 0
t ¯(M M).
t t t t¯ ¯ ¯ ¯-si MX = 0 alors MMX = ( MM)X ⇒ ( MM)= 0 et on a bien 0≤ (M M).0 0 0
Dans tous les cas, on a:
t t¯ ¯( MM)≤ (M M)
t ¯et comme on peut e´changer les roˆles de M et M on en de´duit l’ine´galite´ dans l’autre sens d’ou` l’e´galite´.

m
å
¥
¥
¥
a
¥
m
r
a
r
r
å
¥
r
r
¥
m
e
a
r
a
e
e
e
• De´finition des valeurs singulie`res d’une matrice M
t ¯MM est hermitienne semi-de´finie positive et donc ses valeurs propres compte´es avec leur ordre de mul-
tiplicite´ sont re´elles positives et ordonne´es comme suit:
0≤ ≤ ...≤ .1 2 n

Posons : = ∀i∈{1,2,..,n}. Alors l’ensemble{ ,.., } est appele´ l’ensemble des valeurs sin-i i 1 n
gulie`res de M
ii. (⋆) Proposition:
Soit A=(a ) une matrice deM (K).i, j i, j=1..n n
n• |||A||| = sup |a |.1 i, jj=1..n i=1p
t¯• |||A||| = ( AA).2
n• |||A||| = sup |a |.+ i, ji=1..n j=1
Preuve:
Seul sera prouve´ en cours le point 2.Les deux autres points seront faits en TD.
(f) (⋆)The´ore`me I.1 d’Approximation du rayon spectral par une norme matricielle.
Theoreme I.1:´ `
Soit A une matrice deM (K), alors:n
-Pour toute norme matricielle||.|| on a: (A)≤||A||.
-∀ > 0, il existe une norme matricielle||.|| telle que||A|| ≤ (A)+ .A, A,
Preuve: voir Cours.
2. Suite de matrices: Quelques the´ore`mes utilise´s dans les me´thodes ite´ratives
Une suite de matrices (A ) deM (K) tend vers B∈M (K) si et seulement si il existe une norme||.|| pour laque-k k∈N n n
lle||A − B|| tend vers 0 quand k−>+ .k
Conse´quences:
Si A =(a ) tend vers B=(b ) alors a tend vers b quand k−>+ .k k,(i, j) i, j=1..n i, j i, j=1..n k,(i, j) i, j
k(a) (⋆)Convergence de la suite(A ) ,A∈M (C).nk∈N
The´ore`me I.2:
Soit A une matrice deM (C), alors il y a e´quivalence entre les propositions suivanres:n
k- lim (A )= 0;k−>+
k n- lim (A )v= 0 ∀v∈C ;k−>+
- (A)< 1;
- il existe une norme matricielle surM (C) telle que||A||< 1.n
Preuve: voir cours.
(b) (⋆)Inversion de matrice
The´ore`me I.3:
Soit B une matrice deM (C)n
−1 k-Si (B)< 1, alors I− B est inversible et(I− B) = B et alors pour toute norme matricielle||.|| .k≥0
−1 1telle que||B||< 1 alors||(I− B) ||≤ .
1−||B||
-Si I− B est singulie`re, alors pour toute borme matricielle||.||, on a||B||≥ 1.
Preuve: voir cours.
(c) The´ore`me I.4:
1k
kSoit A une matrice deM (C) alors,||A || −> (A),k−>+ .n

d
d
d
d
d
¥
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
d
` ´3. Conditionnement d’un systeme lineaire:
(a) Pre´sentation et exemple: voir Cours
• Proble`me initial: Re´soudre le syste`me AX = b ou` A et b sont des donne´es.
• Proble`me re´el: Re´soudre le syste`me(A+ A)(X+ X)= b+ b ou` A et b sont les erreurs sur les donne´es
(par exemple erreurs d’arrondi lors de la saisie des donne´es.)
• Objectif: Quelle est la re´percussion sur la solution du syste`me, des erreurs sur les donne´es (suppose´es connues)
inde´pendamment de la me´thode nume´rique de re´solution.
• Un exemple:
Soit A la matrice de Hilbert :  1 1 11
2 3 4
1 1 1 1  2 3 4 5A= 1 1 1 1 
3 4 5 6
1 1 1 1
4 5 6 7
t 25 77 57 319et b=( , , , ).12 60 60 420 −1 tLa solution exacte du syste`me est donne´e par X = A b= (1,1,1,1). Si nous approximons le second membre
t tpar b+ b= (2.1,1.3,1,0.8) la solution X+ X est (5,6,−48,114,−70), tre`s loin de la solution de de´part X.
Nous constatons qu’une ”petite” pertubation sur b ( par exemple ,ici,|| b|| = 0,05) conduit a` une grande mod-
ification de la solution ( ici| X|| = 113), ce qui peut entrainer des instabilite´s lors de la re´solution nume´rique
du syste`me.
Maintenant, passons aux de´finitions et proprie´te´s mathe´matiques de ce qu’on va appeler ”conditionnement d’une
matrice” et qui va permettre de formuler ce qui vient d’eˆtre illustre´ sur l’exemple et surtout, de l’e´viter .
(b) Remarques sur l’erreur relative
(c) De´finition du Conditionnement
nSoit(K ,||.||) etM (K) est muni de la norme subordonne´e|||.|||.n
• De´finition:
−1Le conditionnement d’une matrice A deM (K) est K(A)=|||A||||||A |||.n
• (⋆)The´ore`me I.5: Conditionnement d’un syste`me line´aire
The´ore`me :
Soit le syste`me AX = b avec A matrice deM (K), inversible. Soit A∈M (K)n n
n 1et b∈K tels que||| A|||≤ .−1|||A |||
- Alors(A+ A) est inversible.
- Soient X et X+ X les solutions uniques respectives de AX = b et(A+ A)(X+ X)= b+ b. Alors:
|| X|| K(A) ||| A||| || b||≤ ( + ).−1||X|| 1−|||A |||||| A||| |||A||| ||b||
Preuve: voir cours.
• Conse´quences:
-Si b= 0, le the´ore`me donne:
|| X|| ||| A|||≤ K(A)( ).||X|| |||A|||
De plus , la majoration est optimale.
Le facteur d’amplitude entre l’erreur sur les donne´es et l’erreur sur le re´sultat qui en de´coule, est K(A).
´- De´finition: Le syste`me line´aire AX = b est bien conditionne pour la norme subordonne´e|||.||| si le condi-
´tionnement associe´ K(A) est proche de 1 et mal conditionne si K(A) est grand.
-Exemple: Pour la matrice de Hilbert(4,4) A ci-dessus, on a:
K (A)= 28375 K (A)= 15514.1 2
Les valeurs du conditionnement sont tre`s e´leve´es , inde´pendamment de la norme, ce que semblait indiquer
l’exemple nume´rique ci-dessus .
4m
l
a
l
m
d
a
s
l
d
m
l
m
d
m
l
l
l
• Proprie´te´s de K(A)
i. K(A)≥ 1,
−1K(A)= K(A ),
K( A)= K(A)∀ ∈K.
ii. Soit K (A) le conditionnement d’une matrice associe´e a` la norme spectrale. Soient 0≤ ≤ ≤..≤2 1 2 n
les n valeurs singulie`res de A. Alors:
nK (A)= .2
1
| |t n¯Si A= A, alors K (A)= ou` | |≤..≤| | sont les valeurs absolues des valeurs propres de A.2 1 n| |1−1 t¯Si A = A, alors K (A)= 1.2
−1iii. K (A)= K (UA)= K (AU)= K (UAU )∀U unitaire.2 2 2 2
Preuve: voir cours
`4. Conditionnement d’un probleme aux valeurs propres:
(a) Un exemple:voir Cours.
(b) Un the´ore`me:
Soit A une matrice(n,n) diagonalisable dansC. Alors, il existe P matrice inversible telle que
−1P AP=diag( ,., ). Soit une norme matricielle ||.|| telle que pour toute matrice diagonale D=diag(d ,..d ),1 n 1 n
||D||=sup {|d|}i=1..n i
Alors pour toute matrice A on a;
n[
(A+ A)⊂ D,i
i=1
avec D ={z∈C/|z− |≤ K(P)|| A||}.i i
(c) Conse´quences: Le proble`me aux valeurs propres le mieux conditionne´ correspondra aux matrices hermitiennes ou
syme´triques dans le cas re´el, car la matrice de passage P peut eˆtre alors choisie, unitaire ou orthogonale et K (P)= 1!2
5