Polytech Lyon, département MAM Année universitaire 2017-2018

Analyse numérique Philomène BOBICHON

Correction feuille d’exercices n°1

Rappels

kAk = max kAxk

kxk≤1

= max kAxk
kxk=y

kAxk
= max
x6=0 kxk
norme subordonnée ⇔ kAxk ≤ kAkkxk

Exercice 1.
1. Il existe {vi }i=1,...,n base orthonormale de vecteurs propres de A. {λi }i=1,...,n valeurs
propres réelles associées aux vecteurs propres.
n
X
n
∀x ∈ R , x= xi vi et kxk2 = (x, x)
i=1
De plus, kvi k = 1 (vi , vj ) = vij

Prenons kxk2 :

kxk2 = (x, x)
n n
!
X X
= xi v i , xj v j
i=1 i=1
n X
X n
= xi xj (vi , vj )
i=1 j=1
n
X
= x2i
i=1

n
X
Ax = A xi vi
i=1
n
X
= xi Avi
i=1

1
 n
X
= xi λi vi
i=1

n
X
2
kAxk = x2i λ2i
i=1

kAxk
kAk = max
x6=0 kxk
pPn
x2i λ2i
= max pPi=1 n 2
i=1 xi
n
pP
|λi | x2
≤ max pPn i=1 2 i
i=1 xi
= max |λi |

car n n n
X X 2
X
2
min |λi | x2i ≤ (xi λi ) ≤ max |λi | 2
x2i
i=1 i=1 i=1
kAxk
Posons i0 = max |λi |, et x = vi0 , d’où kxk
= λi0 = max |λi | et sachant que :

Avi = λi vi
⇔vi = λi A−1 vi
1
⇔ vi = A−1 vi
λi
on a :
 
−1
1
kA k = max  
λi
1
=
min |λi |
d’où, finalement,
max |λi |
κ(A) = kAkkA−1 k =
min |λi |

2. On a Ax = b et A(x + δx) = b + δb. Or

A(x + δx) = b + δb ⇒ b + Aδx = b + δb

⇔ Aδx = δb
⇔ δx = A−1 δb
⇔ kδxk ≤ kA−1 kkδbk
kAk 1
or kAkkxk ≥ kbk ⇒ kbk
≥ kxk
, on a donc finalement :

kδxk kδbk kδxk kδbk

≤ kAkkA−1 k ⇔ ≤ κ(A)
kxk kbk kxk kbk

2
3. On a

(A + δA)(x + δx) = b
⇔ Ax + Aδx + δA(x + δx) = b
⇔ Aδx + δA(x + δx) = 0
⇔ Aδx = −δA(x + δx)
⇔ δx = A−1 δA(x + δx)
⇒ kδxk ≤ kA−1 kkδAkkx + δxk
kδxk
⇔ ≤ kA−1 kkδAk
kx + δxk
kδxk kδAk
⇔ ≤ κ(A)
kx + δxk kAk

Exercice 2.
1.
 
2 − λ −1
det (A − λI2 ) =
−1 2 − λ
= (2 − λ)2 − 1
= (1 − λ)(3 − λ)

d’où sp(A) = {1, 3}. Soient u = (x, y) ∈ R∗ vecteur propre de A. Pour la valeur
propre λ = 1 :

(A − I2 )u = 0
    
1 −1 x 0
=
−1 1 y 0
!
√1
 
1 2
cela donne x = y, d’où u ∈ vect . En normalisant : √1
. Par la même
1 2
 
1 −1
logique, on trouve v2 = √2 .
1
x2 y2
2. On rappelle que la fonction formant une ellipse est a2
+ b2
= 1. Et une ellipse
2 2
centrée en (x0 , y0 ) suit la formule (x−x
a2
0)
+ (y−y
b2
0)
= 1.
On a :      
x 1 x x
J = ,A
y 2 y y
 
x0
Soit tel que J soit minimum.
y0
   
x x0
= + Xv1 + Y v2
y y0

3
Comme le minimum est atteint quand Ax = b, alors
   
x0 1
=
y0 1

Finalement :
      
x 1 1 1
J = + v1 x + v2 y, A + xv1 + yv2
y 2 1 1
   
1
− b, + xv1 + yv2 = constante
1
1 D√  √  E
= 2 + x v1 + yv2 , 2 + x v1 + 3v2 y
2 D√ √  E
− 2v1 , 2 + x v1 + yv2
1 D√  √  E 1
= 2 + x v1 , 2 + x v1 + hyv2 + 3yv2 i
2 D√ √  E 2
− 2v1 , 2 + x v1
1 √
  2 1 √ √ 
= 2 + x + 3y 2 − 2 2 + x = constante
2 2

1
√
√ √
2 + x2 + 2 2x − 2 2 + x + 32 y 2 = constante


⇔ 2
1 2 µ2
⇔ 2
x + 32 y 2 = constante − 1 + 2 := 2
x2
⇔ µ2
+ µ32 = 1

Equation d’une ellipse d’axes v1 , v2 et de grand rayon µ porté par v1 et de petit

rayon √µ3 porté par v2 .
J est donc une ellipse. A ∈ Rn , ∃ {vi }i=1,ldots,n une base de vp de A. Soit le change-
ment de vp    
x1 x˙1
 ..   ..  X
 . = . + i = 1n xi vi
xn x˙n
   
x1 n x˙1
λi x2i
J  ...  = constante ⇒ pour constante ≥ J  ... 
X
=1
   
µ 2
xn i=1 x˙n

3. S’inspirer du cours
4. (a) On rappelle que l’agorithme du gradient à pas fixe est le suivant :
Données : x0
pour k = 0, . . . , n faire
rk = b − Axk ;
xk+1 = xk + αopt rk ;
fin

4
  
2 1 0 1
On peut prendre αopt = λ1 +λ2
= 2
, et on part de x = . Pour k = 0, on a :
0

r0 = b − Ax0
    
1 2 −1 1
= −
1 −1 2 0
 
−1
=
2
x1 = x0 + αopt r0
   
1 1 −1
= +
0 2 2
 
1/2
=
1
   
1 2 1
1. r1 = 1 et x = 3
−
 1 2  8 4
2. r2 = 41 et x3 = 9
2
1

(b) Algorithme du gradient à pas variable :

Données : x0
pour k = 0, . . . , n faire
rk = b − Axk ;
(rk ,rk )
αk = rk ,Ark ;
( )
k+1
x = x + αk r k ;
k

fin

Avec le même x0 , on calcule :

  9
0 −1 0 5 1
1. r = , α = 14 , et x = 14
5
2 7
Exercice 3.
On a l’algorithe du gradient conjugué pour A ∈ Rn×n symétrique définie positive
(sdp). On pose rk 6= 0 et 0 ≤ k ≤ n − 2. On procède par récurrence en démontrant
toutes les propriétés en une seule fois.

Pour k = 1 1.

Ad1 , d0 = A(r1 + β 0 d0 ), d0




= Ar1 , d0 + Aβ 0 d0 , d0




= Ar1 , d0 + β 0 Ad0 , d0




 hAd0 , r1 i
0 0 
= Ar1 , d0 − 0

Ad , d
hd , Ad0 i

5
 = Ar1 , d0 − Ad0 , r1




= Ar1 , d0 − d0 − Ar1 = 0




2.
d0 , r1 = d0 , r0 − α0 Ad0




= d0 , r0 − α0 d0 , Ad0




hr0 , d0 i
0
= d0 , r 0 − 0 d , Ad0 = 0

 
hd , Ad i 0

3. hd1 , r0 i = hd1 , r0 i pour k = 1 et l = 0. Prenons l = 1, on a

1 1
1 0
d , r = d , r − α0 Ad0


= d1 , r0 − α0 d1 , Ad0



| {z }
=0

1 0
= d ,r

4. Pour k = 1 :
d1 , r1 = r1 + β 0 d0 , r1




= r 1 , r 1 + β 0 d0 , r 1




= r1 , r1 + β 0 d0 , r1



| {z }
=0

1 1
= r ,r

5.

1 1
1 1
Ad , d = Ad , r + β 0 d0


= Ad1 , r1 + β 0 Ad1 , d0




= Ad1 , r1



6.
r0 , r1 = r0 , r0 − α0 Ad0




= r0 , r0 − α0 r0 , Ad0




hr0 , d0 i
0
= r0 , r0 − 0 0

 
r , Ad =0
hr , Ad0 i

Hérédité 1. Supposons que (Adk , dl ) = 0 pour 0 ≤ k ≤ n − 2 et 0 ≤ l ≤ k.

(Adk+1 , dl ) = (A(rk+1 + β k dk ), dl )
= (Ark+1 , dl ) + (Aβ k dk , dl )
= (Ark+1 , dl ) + β k (Adk , dl )

Deux cas :

6
 1. l = k :

(Adk+1 , dl ) = (Ark+1 , dk ) + β k (Adk , dk )

(Adk , rk+1 )
= (Ark+1 , dk ) − k k
(Adk , dk )
(d , Ad )
=0

2. l < k :

(Adk+1 , dl ) = (Ark+1 , dl )
= (rk+1 , Adl )
= (rk − αk Adk , Adl )
= (rk , Adl ) − αk (Adk , Adl )
1
= k (rl − rl+1 , rk+1 )
α  
1  l k+1
= k
(r , r ) − (rl+1 , rk+1 )
α | {z } | {z }
=0 =0
=0

2. On a

(dl , rk+1 ) = (dl , rk − αk Adk )

= (dl , rk ) − αk (dl , Adk )

1. Si l < k, on a (dl , rk ) = 0 et (dl , Adk ) = 0 par hypothèse de récurrence et par

1..
2. Si l = k,

(dk , rk+1 ) = (dk , rk − αk Adk )

= (dk , rk ) − αk (dk , Adk )
(rk , dk ) k
= (dk , rk ) − k k
(d , Adk )
(d , Ad )
=0
Remarque. (rk , dk ) = (r0 , dk ) par hypothèse 3.
3.

(dk+1 , rl ) = (rk+1 + β k dk , rl )
= (rk+1 , rl ) + β k (dk , rl )

Or, par 6., (rk+1 , rl ) = 0 = (rk+1 , r0 ).

(dk+1 , rk+1 ) = (dk+1 , rk − αk Adk )

= (dk+1 , rk ) − αk (dk+1 , Adk )

7
4. On suppose que (dk , rk ) = (rk , rk ).

(dk+1 , rk+1 ) = (rk+1 , β k dk , rk+1 )

= (rk+1 , rk+1 ) + β k (dk , rk+1 )
= (rk+1 , rk+1 )

5. On suppose que (Adk , rk ) = (Adk , dk ).

(Adk+1 , rk+1 ) = (Adk+1 , dk+1 − β k dk )

= (Adk+1 , dk+1 ) − β k (Adk+1 , dk )

6. On suppose que (rl , rk ) = 0 pour 0 ≤ l < k.

(rl , rk+1 ) = (rl , rk − αk Adk )

= (rl , rk ) − αk (rl , Adk )

1. Si l = k, alors

(rl , rk+1 ) = (rk , rk ) − αk (rk , Adk )

(r0 , dk ) k
= (rk , rk ) − (r , Adk )
(dk , Adk )
5. (r0 , dk )
= (rk , rk ) − k k
(Adk , dk )
(d , Ad )
= (r , r ) − (r0 , dk )
k k

3.
= (rk , rk ) − (dk , rk )
4.
= (rk , rk ) − (rk , rk )
=0

2. Si l < k :

(rl , rk+1 ) = (rl , rk ) −αk (rl , Adk )

| {z }
=0
= −α (rl , Adk )
k

= −αk (dl − β l−1 dl−1 , Adk )

= −αk (dl , Adk ) + αk β l−1 (dl−1 , Adk )
=0
 

7. Kk (A, r0 ) = Vect r0 , Ar0 , . . . , Ak r0 . On a dim Vect r0 , . . . , rk = k + 1 car
rl 6= 0 pour tout 0 ≤ l ≤ k et (ri , rj ) = 0 pour tout 0 ≤ i 6= j ≤ k.
Montrons par récurrence que

Kk (A, r0 ) = Vect r0 , . . . , rk


= Vect d0 , . . . , dk


8
Remarque.

K0 (A, r0 ) ⊂ K1 (A, r0 ) ⊂ . . . ⊂ Kj (A, r0 )

Vect r0 ⊂ Vect d0 , d1 ⊂ . . . ⊂ Vect d0 , . . . , dk
  

AKl (A, r0 ) = y = Ax, x ∈ Kl (A, r0 ) ⊂ Kl+1 (A, r0 )



Initialisation. Pour k = 0, c’est évident.

Hérédité. Supposons que

Kl (A, r0 ) = Vect r0 , . . . , rl


= Vect d0 , . . . , dl


Montrons cette égalité au rang l + 1. On a

dim Vect r0 , . . . , rk+1 = l + 2



Dl+1 = Vect d0 , . . . , dl+1



Rl+1 = Vect r0 , . . . , rl+1



Or, on sait que dim(Rl+1 ) = l + 2. On veut montrer que

1. Rl+1 ⊂ Dl+1
2. Rl+1 ⊂ Kl+1 (A, r0 )

1. r0 , . . . , rl ∈ Rl = Dl ⊂ Dl+1 . Il suffit de montrer que rl+1 ⊂ Dl+1

rl+1 = |{z}
dl+1 − β l dl ∈ Dl+1
|{z}
∈Dl+1 ∈Dl ⊂Dl+1

2. r0 , . . . , rl ∈ Rl = Kl (A, r0 ) ⊂ Kl+1 (A, r0 ). Il suffit de montrer que rl+1 ∈

Kl+1 (A, r0 ).

rl+1 = rl −αl Adl ∈ Kl+1 (A, r0 )

|{z}
∈Kl (A,r0 )

8. Montrons que xk+1 ∈ x0 + Kk (A, r0 ). On sait que

k
X
k+1 0
x =x + αi di
i=1

Donc

xk+1 ∈ x0 + Vect {d0 , . . . , dk }

= x0 + Kk (A, r0 )

9
 Pk
Soit y = x0 + i=0 γi di .
k k
!
1 X X
J(y) = x0 + γi di , A(x0 + γi di ) − (b, y)
2 i=0 i=0
k
!
1 1 X
= (x0 , Ax0 ) + x0 , γi di
2 2 i=0
1  X X 
+ γi di , γj dj
2 ! !
k k
1 X i X
i
+ γi d , Ax0 − (b, x0 ) − b, γi d
2 i=0 i=0
k k k X
k
1X X 1 X
= J(x0 ) + γi (x0 , Adi ) − γi (b, di ) + γi γj (di , Adj )
2 i=0 i=0
2 i=0 j=0
k k
1X X
= J(x0 ) + (γi )2 (di , Adi ) + γi (Ax0 − b, di )
2 i=0 i=0
k k
1X X
= J(x0 ) + (γi )2 (di , Adi ) − γi (r0 , di )
2
| i=0 {z i=0
}
:=f (γi )

f 0 (γi ) = 0 ⇒ γi (di , Adi ) − (r0 , di ) = 0

⇒ γi = αi

10