Recueil d'Examens - Analyse Numérique

j=1

; 1 ≤ i, j ≤ n

bij) < 1

Montrer que I − B est inversible et que (I − B)−1 est à coefficients positifs ou nuls (I désigne la matrice

identité).

2– Soit A = (aij) une matrice a n lignes et n colonnes, a coefficients réels, vérifiant :

aii > 0

aij ≤ 0

n

X

aij > 0

j=1

; 1 ≤ i ≤ n

; 1 ≤ i 6= j ≤ n

; 1 ≤ i ≤ n

et soit D la matrice diagonale formée par la diagonale de A :Dii = aii pour 1 ≤ i ≤ n, Dij = 0 pour

1 ≤ i 6= j ≤ n.

2–a Montrer que D est inversible. On pose alors C = D−1A.

2–b Calculer les coefficients de la matrice C en fonction de ceux de A.

2–c Montrer que A est inversible et que les coefficients de la matrice A−1 sont positifs ou nuls.

Exercice 3

On se donne une matrice A réelle, symétrique définie positive à nlignes et n colonnes, et un vecteur

b ∈ IRn.

On considère, pour r > 0 donné, la suite d’éléments de IRn définie par :

(cid:26) x(o) donné dans IRn

x(k+1) = x(k) − r(Ax(k) − b)

, k ≥ 0

1– Montrer que si la suite (x(k))k∈IN converge vers ¯x alors on a A¯x = b.

2– Montrer que pour r ∈]0,

[ la suite (x(k))k∈IN est convergente. (λn = max1≤i≤n λi, λi ∈ Sp(A).

2

λn

3– En déduire un algorithme de résolution du système linéaire Ax = b.

E.N.I.T.

Examen – Analyse Numérique

Enseignants : H. CHAKER – H. EL FEKIH – M. JAOUA

Classe : 1ère année GC – GE – GI – GM

2000/2001

Date : 2 Avril 2001

Durée : 1h30

Documents non autorisés

Exercice 1

Soit A ∈ Mn(R) une matrice symétrique et λ1, . . . , λn ses valeurs propres

(comptées avec leur ordre de multiplicité) vérifiant :

|λ1| ≤ · · · ≤ |λn−2| < |λn−1| < |λn|

On considère la matrice B définie par B = A − λnunut

propre de A associé à λn, tel que kunk2 = 1.

n, où un est un vecteur

1. Montrer que Bun = 0.

2. Montrer que Bui = λiui, 1 ≤ i ≤ n − 1, où ui est un vecteur propre de A

associé λi, 1 ≤ i ≤ n − 1.

3. En déduire une méthode qui permet de calculer λn−1.

Exercice 2

Soit A ∈ Mn(R) et B ∈ Mm(R) deux matrices inversibles admettant chacune

une factorisation ”LU ” :

A = LAUA,

LA ∈ Mn(R) triangulaire inférieure à diagonale unité

UA ∈ Mn(R) triangulaire supérieure

B = LBUB,

LB ∈ Mm(R) triangulaire inférieure à diagonale unité

UB ∈ Mm(R) triangulaire supérieure

Soit M ∈ Mn+m(R) définie (par blocs) comme suit :

M =

(cid:19)

(cid:18) A O

O B

1. Montrer que M est inversible.

2. Montrer que M admet une factorisation LU unique.

3. Proposer alors une méthode pour résoudre le systeme linéaire M x = b, ou

b ∈ Rn+m et donner le nombre d’opérations élémentaires.

Exercice 3

Soit A ∈ Mn(R) une matrice inversible et b ∈ Rn. On considere le systeme

linéaire

(1)

Ax = b

dont on notera ¯x sa solution.

1. Montrer que la matrice AT A est symétrique définie positive.

2. Pour résoudre le systeme (1), on considere la méthode du gradient à pas

constant appliquée au système AT Ax = AT b :

(2)

(cid:26) x(0) ∈ Rn

x(k+1) = x(k) − rg(k),

k ≥ 0

où r ∈ R∗

+ et g(k) = AT Ax(k) − AT b.

2.a Montrer que la méthode du gradient à pas constant (2) est convergente, si

et seulement si 0 < r <

, où k·k2 désigne la norme matricielle subordonnée

2

kAk2

2

à la norme vectorielle k · k2. Quelle est dans ce cas la limite de la suite (x(k))k≥0

définie par (2) ?

2.b Soit ε > 0, montrer que

kg(k)k2

kAT bk2

≤ ε =⇒

kx(k) − ¯xk2

k¯xk2

≤ ε[cond2(A)]2

où cond2(A) = kAk2 kA−1k2 et ¯x désigne la solution de (1).

2.c Ecrire l’algorithme de la méthode du gradient à pas constant appliquée au

système AT Ax = AT b.

2

E.N.I.T.

Examen – Analyse Numérique

Enseignant(s) : H. EL FEKIH

Classe : 1ère année INFO & TELEC

2000/2001

Date : 13 Janvier 2001

Durée : 1h30

Documents non autorisés

Exercice 1

Soit x1, x2, . . . , xn, n points distincts de [a, b] ⊂ R, et V la matrice :

· · · xn−1

· · · xn−1

...

· · ·

...

. . .

· · · xn−1

x2

1 x1

1

x2

1 x2

2

...

...

. . .

...

...

...

1 xn x2

n















V =



n

2

1

















1– Montrer, en utilisant l’interpolation de Lagrange, que V est inversible.

2– Soit L1, · · · , Ln les polynômes de Lagrange aux points x1, . . . , xn. On pose, pour j = 1, . . . , n,

Lj(x) =

uijxi−1. Montrer que V −1 = U , où U = (uij)1≤i,j≤n.

n

X

i=1

Exercice 2

On considère l’équation différentielle :

(E)

(cid:26) y0 = f (x, y), x ∈ [a, b]

y(a) = Y0

ou f est une fonction de [a, b] × R −→ R Lipschitzienne par rapport a y et de classe C 3. On notera Y la solution

exacte de (E). Pour approcher l’équation différentielle (E), on propose le schéma numérique suivant :

(S)







y0 = Y0,

h =

b − a

N

yn+1 = yn + αhf (xn, yn) + βh2f (1)(xn + λh, yn + λhf (xn, yn)), n ≥ 0

où α, β et λ sont des réels ≥ 0, et xn, n = 0, · · · , N , (N + 1) points équidistants de [a, b]. On rappelle que f (k)

est donnée par :

f (k)(x, y) =

∂f (k−1)(x, y)

∂x

+ f (x, y)

∂f (k−1)(x, y)

∂y

,

k ≥ 1, avec f (0) = f

1– Montrer que si la fonction f (1) est lipschitzienne par rapport a la deuxieme variable, alors le schéma (S) est

stable.

2– A quelle condition le schéma (S) est-il consistant ?

3– Déterminer α, β et λ pour que le schéma (S) soit d’ordre (au moins) 3.

4– En déduire, que pour ce choix de α, β et λ , le schéma (S) est convergent. Donner alors une estimation de

l’erreur max

|yn − Y (xn)| en fonction de h.

n

Exercice 3

On se donne deux points distincts τ1 et τ2 dans l’intervalle [-1,1], et deux nombres réels non nuls ω1 et ω2. Soit

la formule de quadrature suivante :

Z 1

−1

f (t)dt = ω1f (τ1) + ω2f (τ2) + E(f )

où E(f ) est le terme d’erreur.

1– Quelle condition doivent vérifier ω1 et ω2 pour que cette formule soit exacte pour les fonctions constantes ?

2– Montrer qu’une condition nécessaire et suffisante pour que la formule soit exacte pour les polynômes impairs

de degré inférieur ou égal 3 est que τ1 = −τ2 et ω1 = ω2 .

3– En déduire les valeurs de τ1, τ2, ω1 et ω2 pour que la formule soit exacte pour tous les polynômes de degré

inférieur ou égal 3. A quelle famille appartient la formule obtenue ?

E.N.I.T.

11 juillet 2001

Examen – Session de rattrapage

Analyse Numérique

Enseignant(s) : H. EL FEKIH

Classe : 1ère année INFO & TELEC

Durée : 1h30

Documents non autorisés

Exercice

Soit a et b deux réels et f : [a, b] → R une fonction de classe C 3.

On souhaite approcher D2f ≡ f 00( a+b

2 ) par une expression du type :

∆2f ≡ λ0f (a) + λ1f (

a + b

2

) + λ2f (b)

de telle sorte que E(f ) ≡ D2f − ∆2f vérifie :

(1)

∀P ∈ P2,

E(P ) ≡ D2P − ∆2P = 0

2 , b] = 1

On supposera dans toute la suite que les réels λ0, λ1 et λ2 sont tels que la propriété (1)

soit vérifiée.

1– Montrer que f [a, a+b

de f aux points a, a+b

2 , b.

2– Soit Pf le polynôme d’interpolation de Lagrande de f aux points a, a+b

f (x) − Pf (x).

2–a Montrer qu’il existe c ∈ [a, b] tel que r00(c) = 0.

2–b Montrer que E(f ) = r00( a+b

2 , b] désigne la différence divisée d’ordre 2

2 ∆2f , où f [a, a+b

2 , b et r(x) =

2 ).

2–c En déduire que

|E(f )| ≤

b − a

2

sup

x∈[a,b]

|f 000(x)|

3– Calculer les réels λ0, λ1, λ2 en fonction de a et b pour que la propriété (1) soit vérifiée.

Problème

On considere la formule de quadrature de Gauss-Legendre a k + 1 points, k ≥ 0,

donnée par :

(1)

Z 1

−1

f (x) dx =

k

X

i=0

λif (xi) + E(f )

où nous avons désigné par :

• E(f ) le terme d’erreur (on ne s’intéresse pas ici à l’étude de E(f ));

• xi, 0 ≤ i ≤ k, les nœuds d’intégration vérifiant : −1 < x0 < x1 < · · · < xk < 1;

• λi, 0 ≤ i ≤ k, les poids d’intégration.

On rappelle que x0, . . . , xk sont les k + 1 racines du (k + 2)-ième polynôme orthogonal de

Legendre Qk+1 ∈ Pk+1 (qui est unitaire) associé à la fonction poids w ≡ 1 sur l’intervalle

[−1, 1].

Le but de ce problème est de calculer les (k + 1) nœuds x0, . . . , xk ainsi que les k + 1

poids λ0, . . . , λk de la formule de quadrature de Gauss-Legendre donnée par (1).

Le probleme est divisé en trois parties. La premiere est une étape préliminaire, la

deuxieme concerne le calcul des nœuds xi et la derniere porte sur le calcul des poids λi.

Partie I : Soient r0 < r1 < · · · < rm, (m + 1) réels, m > 0, et P ∈ Pm+1 le polynôme

défini par P (x) = (x − r0) (x − r1) · · · (x − rm).

On considere la méthode de Newton appliquée a la résolution de l’équation P (x) = 0.

On rappelle que cette méthode génère la suite définie par :

t0 donné,

t‘+1 = t‘ −

P (t‘)

P 0(t‘)

,

‘ ≥ 0

On suppose que t0 > rm.

I.1– Montrer que ∀ ‘, t‘ > rm et que la suite (t‘)‘≥0 est décroissante.

I.2– En déduire que la suite (t‘)‘≥0 est convergente et que lim

‘→+∞

t‘ = rm.

Partie II : On considere le (k + 2)-ieme polynôme orthogonal (de Legendre) Qk+1

associé à la fonction poids w ≡ 1 sur l’intervalle [−1, 1], et ses (k + 1) racines notées

x0 < x1 < . . . < xk.

II.1– Montrer que la méthode de Newton appliquée à Qk+1, avec une initialisation t0 > xk,

génère une suite (t‘)‘≥0 qui converge vers xk.

II.2– On suppose que les racines xk, xk−1, . . . , xj (1 < j ≤ k) de Qk+1 ont été déjà

calculées et on se propose de calculer xj−1.

On considère le polynôme Rj ∈ Pj défini par : Rj(x) = Qk+1(x)/ Qk

Montrer que la méthode de Newton appliquée au polynôme Rj, avec une initialisation

i=j(x − xi)

t0 = xj, génère une suite (t‘)‘≥0 qui converge vers xj−1.

II.3– En déduire un algorithme qui permet de calculer les (k + 1) racines x0, x1, . . . , xk

de Qk+1.

Partie III : On s’intéresse dans cette partie au calcul des poids λi intervenant dans

la formule de Gauss-Legendre donnée par (1). Rappelons que cette formule est de

degré 2k + 1.

Montrer que les poids λi, i = 0, . . . , k, sont donnés par

λi =

1

k+1(xi)

Q0

Z 1

−1

Qk+1(x)

x − xi

dx

(cid:3)

2

E.N.I.T.

Examen – Analyse Numérique

Enseignant(s) : H. EL FEKIH

Classe : 1ère année GE & TELEC

2001/2002

Date : 12 Mars 2002

Durée : 1h30

Documents non autorisés

Exercice 1

Soit u ∈ Rn \ {0} tel que kuk2 < 1, où k · k2 désigne la norme euclidienne de Rn.

1– Soit A ∈ Mn(R) la matrice donnée par A = uut. Calculer |||A|||2, où ||| · |||2 désigne la norme

matricielle subordonnée à la norme vectorielle k · k2.

2– Soit B la matrice donnée par B = I + A, où I désigne la matrice identité. Montrer que B est

inversible.

Exercice 2

Soient A ∈ Mn(R) et B ∈ Mm(R) deux matrices inversibles admettant chacune la factorisation

”LU ” :

A = LAUA,

B = LBUB,

LA ∈ Mn(R)

UA ∈ Mn(R)

LB ∈ Mm(R)

UB ∈ Mm(R)

triangulaire inférieure à diagonale unité

triangulaire supérieure

triangulaire inférieure à diagonale unité

triangulaire supérieure

Soit M ∈ Mn+m(R) définie (par blocs) comme suit :

M =

(cid:19)

(cid:18) A O

O B

1– Montrer que M est inversible.

2– Montrer que la matrice M admet une factorisation “LU ” unique.

3– Proposer une méthode pour résoudre le systeme linéaire M x = b, ou b ∈ Rn+m, et donner le

nombre d’opérations élémentaires.

Exercice 3

Soient A ∈ Mn(R) une matrice inversible et b ∈ Rn. On considere le systeme linéaire

(1)

Ax = b

dont on notera ¯x sa solution.

1– Vérifier que le systeme (1) est équivalent au systeme :

(2)

AT Ax = AT b

2– Montrer que la matrice AT A est symétrique définie positive.

3– Pour résoudre le systeme (1), on considere la méthode du gradient à pas constant appliquée au

système (2) :

(3)

(cid:26) x(0) ∈ Rn

x(k+1) = x(k) − r∇J(x(k)),

k ≥ 0

où r ∈ R∗

+ et J(·) est la fonctionnelle définie sur Rn par :

(·, ·) désigne le produit scalaire euclidien dans Rn.

J(x) =

1

2

(AT Ax, x) − (AT b, x)

3–a Montrer que la méthode du gradient à pas constant (3) est convergente, si et seulement si

0 < r <

, ou k · k2 désigne la norme matricielle subordonnée a la norme vectorielle k · k2.

2

kAk2

2

Quelle est dans ce cas la limite de la suite (x(k))k≥0 définie par (3) ?

3–b On note g(k) = ∇J(x(k)). Soit ε > 0, montrer que

kg(k)k2

kAT bk2

≤ ε =⇒

kx(k) − ¯xk2

k¯xk2

≤ ε[cond2(A)]2

où cond2(A) = kAk2 kA−1k2 et ¯x désigne la solution de (2)(ou de (1)).

3–c Ecrire l’algorithme de la méthode du gradient a pas constant appliquée au systeme (2).

2

E.N.I.T.

juillet 2002

Examen – Session de rattrapage

Analyse Numérique

Enseignante : Henda El Fekih

Classe : 1ère année GE 1-2 & TELEC 1-2

Durée : 1h30

Documents non autorisés

Exercice 1

On considere le systeme linéaire Ax = c où A une matrice carrée inversible d’ordre n . On note λi ses valeurs

propres ordonnées comme suit : 0 < λ1 < λ2 < .... < λn−1 < λn. Soit B une autre matrice carrée inversible

d’ordre n.

1. Montrer que le systeme linéaire Ax = c est équivalent au systeme : x = (I − B−1A)x + d,

où I est la matrice idendité et d un vecteur que l’on exprimera en fonction de c.

2. On suppose que B = αI (α > 0) et on considère la méthode itérative : x(k+1) = (I −B−1A)x(k)+d, (k ≥ 0).

On note par la suite F = I − B−1A et ρ(F ) le rayon spectral de la matrice F .

2.1 Exprimer ρ(F ) en fonction de α, λ1 et λn (on discutera l’expression de ρ(F ) avec α).

2.2 En déduire une condition sur α assurant que la méthode itérative est convergente.

2.3. Pour quelle valeur αo de α la vitesse de convergence est-elle la plus élevée ? Que vaut dans ce cas ρ(F )?

Exercice 2

On considere le systeme linéaire Ax = b où A =





1

β 1

γ

0

0 α

0

1





b =





1

3

2



, où α, β, γ ∈ R sont donnés.

1- Ecrire les méthodes itératives de Jacobi et Gauss-Seidel pour résoudre le système linéaire Ax = b (donner

explicitement les expressions des composantes de x(k+1)).

2- Calculer dans les deux cas le vecteur x(1) obtenu apres la premiere itération, à partir du vecteur initial

x(0) = (1, 1, 1)t.

3- Trouver sous quelles conditions sur α, β, γ les méthodes de Jacobi et Gauss-Seidel sont convergentes.

4- Dire laquelle des deux méthodes converge la plus vite.

Exercice 3

On considère la matrice carrée d’ordre 4 suivante :



A =







2

4

2

4

2

4









1

1

1

2

où les termes manquants sont des zéros.

1- calculer la factorisation LU de la matrice A et comparer la structure (c’est-à-dire la position des éléments

non nuls) des matrices L et U obtenues avec celle de A.

2- Si on considère maintenant une matrice d’ordre n avec la structure suivante :

A1 =















α1

α2

. . .

γ1

γ2

· · ·

β1

β2

...

αn−1 βn−1

αn

γn−1















où tous les coefficients αi, βi et γi sont des réels donnés, quelle est la structure des matrices L et U ?

3- En revanche, que se passe-t-il si on prend une matrice de la forme suivante :

A2 =















α1 β2 β3

γ2 α2

γ3

...

γn

α3















?

· · · βn

. . .

αn

Help! On rappelle qu’a l’étape p de la factorisation LU , la p-eme ligne de U et la p-ème colonne de L sont

déterminées comme suit :

upj = apj −

p−1

X

k=1

‘pkukj, p ≤ j

‘ip =

aip −

!

‘ikukp

/upp, p < i.

p−1

X

k=1

E.N.I.T.

Examen – Analyse Numérique

Enseignant(s) : H. El Fekih

Classe : 1ère année GM

2002/2003

Date : 11 Juin 2003

Durée : 1h30

Documents non autorisés

Exercice 1

On suppose que l’équation

(1)

f (x) = g(x)

admet une unique solution simple α sur [a, b],où f et g sont monotones et dérivables.

1– Démontrer que si |

g0(α)

f 0(α)

| < 1, alors la méthode itérative

x0 donné,

f (xn+1) = g(xn), n ≥ 0

est convergente.

2– On suppose que |

g0(α)

f 0(α)

| > 1. Proposer une méthode itérative convergente pour calculer α.

Exercice 2

Soit A ∈ Mn(R) une matrice symétrique dont on connait une valeur propre λ et un vecteur

propre associé u de norme kuk2 = 1, où k · k2 désigne la norme euclidienne de Rn.

Soit B ∈ Mn(R) la matrice définie par B = A − λuut.

1– Montrer que 0 est une valeur propre de B de vecteur propre associé u.

2– Soit β une autre valeur propre de A (β 6= λ) de vecteur propre associé v.

Montrer que β est une valeur propre de B de vecteur propre associé v.

3– Soient λ1, λ2, . . . , λn les valeurs propres de A, comptées avec leur ordre de multiplicité,

vérifiant :

|λ1| ≤ |λ2| ≤ · · · ≤ |λn|

En utilisant la méthode de la puissance, donner une méthode qui permet de calculer λn et

λn−1 et préciser les hypothèses sous lesquelles la méthode proposée converge.

Exercice 3

Soit n ∈ N, n ≥ 2. Soit A ∈ Mn(R), A = (aij)1≤i,j≤n. On suppose que A est inversible et

admet la factorisation A = LU , ou L ∈ Mn(R) est triangulaire inférieure a éléments diagonaux

égaux a 1, et ou U ∈ Mn(R) est triangulaire supérieure.

Pour k ∈ {1, 2, . . . , n}, on note Ak la matrice de Mk(R) obtenue à partir de A en ne gardant

que les k premieres lignes et les k premieres colonnes, soit Ak = (aij)1≤i,j≤k.

1– Montrer que pour tout k ∈ {1, 2, . . . , n}, la matrice Ak admet la factorisation Ak = LkUk,

ou Lk ∈ Mk(R) est triangulaire inférieure a éléments diagonaux égaux a 1, et ou Uk ∈ Mk(R)

est triangulaire supérieure.

2– On pose, pour k ∈ {2, 3, . . . , n} :









Ak =









,

Ak−1

vk

wt

k

akk

où vk ∈ Rk−1 et wk ∈ Rk−1.

En supposant connue la factorisation Ak−1 = Lk−1Uk−1 et en écrivant :









Ak =

















Lk−1 0

mt

k

1

Uk−1

qk

0

ukk









,

où mk ∈ Rk−1, qk ∈ Rk−1 et ukk ∈ R,

montrer comment on peut déterminer la factorisation Ak = LkUk.

3– Déduire de ce qui précède une méthode pour la détermination de la factorisation LU de la

matrice A.

2

E.N.I.T.

2 juillet 2003

Examen { Session de rattrapage

Analyse Num(cid:19)erique

Enseignants : H. El Fekih { M. Jaoua { M. Moakher { A. Sakat

Classe : 1(cid:18)ere ann(cid:19)ee GC { GE { GI { GM { INFO { TELEC

Dur(cid:19)ee : 1h30

Documents non autoris(cid:19)es

Exercice 1

1{ Soit H 2 Mn(R) une matrice sym(cid:19)etrique d(cid:19)e(cid:12)nie positive (ou seulement sym(cid:19)etrique positive).

1-a Montrer que pour tout r(cid:19)eel r > 0 la matrice rI + H est inversible.

1-b Montrer que pour tout r(cid:19)eel r > 0 la matrice (rI (cid:0) H)(rI + H)(cid:0)1 est sym(cid:19)etrique.

1-c Soit (cid:21) une valeur propre de H et u un vecteur propre qui lui est associ(cid:19)e. Montrer que

est une valeur propre de (rI (cid:0) H)(rI + H)(cid:0)1 associ(cid:19)ee au vecteur propre u.

r (cid:0) (cid:21)

r + (cid:21)

1-d En d(cid:19)eduire que k(rI (cid:0) H)(rI + H)(cid:0)1k2 < 1 pour H sym(cid:19)etrique d(cid:19)e(cid:12)nie positive, et que

k(rI (cid:0) H)(rI + H)(cid:0)1k2 (cid:20) 1 pour H sym(cid:19)etrique positive. (k (cid:1) k2 d(cid:19)esigne la norme matricielle subordonn(cid:19)ee

indice 2).

2{ Soit H1 une matrice sym(cid:19)etrique d(cid:19)e(cid:12)nie positive et H2 une matrice sym(cid:19)etrique positive. On

suppose que les deux matrices H1 et H2 commutent. Pour u0 et b donn(cid:19)es dans Rn, on d(cid:19)e(cid:12)nit la

suite (uk) par :

(rI + H1)uk+ 1

(rI + H2)uk+1 = (rI (cid:0) H1)uk+ 1

= (rI (cid:0) H2)uk + b

2

+ b

2

2-a Ecrire uk+1 en fonction de uk sous la forme uk+1 = Buk + c, o(cid:18)u la matrice B et le vecteur c

sont (cid:18)a d(cid:19)eterminer.

2-b Montrer que la suite (uk) converge vers un vecteur u et que u est solution d’un syst(cid:18)eme

lin(cid:19)eaire (cid:18)a d(cid:19)eterminer.

Exercice 2

1{ Soit B = (bij)1(cid:20)i;j(cid:20)n une matrice (cid:18)a coe(cid:14)cients r(cid:19)eels, v(cid:19)eri(cid:12)ant :

bij (cid:21) 0

, 1 (cid:20) i; j (cid:20) n

n

kBk1 (cid:17) max

1(cid:20)i(cid:20)n

(

X

j=1

bij) < 1

Montrer que I (cid:0) B est inversible et que (I (cid:0) B)(cid:0)1 est (cid:18)a coe(cid:14)cients positifs ou nuls (I d(cid:19)esigne la

matrice identit(cid:19)e).

2{ Soit A = (aij)1(cid:20)i;j(cid:20)n une matrice (cid:18)a coe(cid:14)cients r(cid:19)eels, v(cid:19)eri(cid:12)ant :

aii > 0

aij (cid:20) 0

n

, 1 (cid:20) i (cid:20) n

, 1 (cid:20) i 6= j (cid:20) n

aij > 0

, 1 (cid:20) i (cid:20) n

X

j=1

et soit D la matrice diagonale form(cid:19)ee par la diagonale de A :dii = aii pour 1 (cid:20) i (cid:20) n, dij = 0 pour

1 (cid:20) i 6= j (cid:20) n.

2{a Montrer que D est inversible. On pose alors C = D (cid:0)1A.

2{b Calculer les coe(cid:14)cients de la matrice C en fonction de ceux de A.

2{c Montrer que A est inversible et que les coe(cid:14)cients de la matrice A(cid:0)1 sont positifs ou nuls.

(cid:3)

E.N.I.T.

Examen – Analyse Numérique

Enseignants : H. El Fekih – K. Gribaa

Classe : 1ère année GC & GI

2003/2004

Date : 23 Janvier 2004

Durée : 1h30

Documents non autorisés

Exercice

Soit f : D = [a, b] × R → R une fonction continue sur D et Lipschitizienne par rapport à la

deuxieme variable. On considere l’équation différentielle

(E)

(cid:26) y0 = f (x, y),

y(a) = Y0

x ∈ [a, b]

dont la solution exacte est notée Y . Soit x0 = a, x1, . . . , xN = b, N + 1 points équidistants

appartenant à [a, b], et soit h = xn+1 − xn, n = 0, . . . , N − 1.

1– En utilisant la formule d’intégration numérique du point milieu, montrer que :

Y (xn+1) − Y (xn) = hf

(cid:16)

xn+ 1

2

, Y (xn+ 1

2

(cid:17)

)

+ E1(f )

= 1

2

2 (xn+1 + xn).

où xn+ 1

[E1(f ) est le terme d’erreur (on ne demande pas l’expression de E1(f )).]

2– En utilisant la formule d’intégration numérique du rectangle à gauche, montrer que

Y (xn+ 1

2

) = Y (xn) +

h

2

f (xn, Y (xn)) + E2(f )

[E2(f ) est le terme d’erreur (on ne demande pas l’expression de E2(f )).]

3– En déduire un schéma numérique à un pas :

(S)

yn+1 = yn + hΦ(xn, yn, h)

pour la détermination d’une approximation yn de Y (xn).

4– Montrer que le schéma (S) est stable, consistant et est d’ordre 2.

Problème

Soit A ∈ Mn(IR) une matrice symétrique définie positive. On considère les fonctions définies

par

ρ : IRn −→ IR

v 7→ vtAv = (Av, v)

f : IRn −→ IRn

v 7→ Av − ρ(v)v

où vt désigne le transposé de v et (.,.) le produit scalaire Euclidien sur IRn.

1– Montrer que v ∈ IRn est vecteur propre de A avec kvk2 = 1 si et seulement si v 6= 0 et

f (v) = 0.

2– En déduire que u ∈ IRn est solution du problème de minimisation suivant

T rouver

∀v ∈ S

u ∈ S ≡ {x ∈ IRn/ kxk2 = 1}

kf (u)k2 ≤ kf (v)k2

si et seulement si u ∈ IRn est vecteur propre de A et kuk2 = 1.

3– Soient v, w ∈ IRn.On considère les fonctions

g : IR −→ IR

t 7→ ρ(v + tw)

h : IR −→ IRn

t 7→ f (v + tw)

3-a Montrer que

g0(t) = 2(wtAv + twtAw)

h0(t) = Aw − g(t)w − g0(t)(v + tw)

3-b Montrer en utilisant un développement limité de la fonction h au voisignage de zéro, que

kh(t)k2

2 = (h(0), h(0)) + 2t(h0(0), h(0)) + O(t2)

3-c Soit v ∈ IRn tel que kvk2 = 1. On suppose que det(A − ρ(v)I) 6= 0. On pose w = −v + αz,

ou α ∈ IR et z ∈ IRn est la solution du systeme linéaire (A − ρ(v)I)z = v. Montrer que

(h0(0), h(0)) = − kAv − ρ(v)vk2

2

et en déduire que (h0(0), h(0)) < 0.

4– Soit z et v ∈ IRn avec kvk2 = 1 et t ∈ [0, 1]. Montrer qu’il existe α ∈ IR tel que pour

t ∈ [0, 1] on ait

k(1 − t)v + tαzk2

2 = 1

5– Soit v ∈ IRn, on suppose que det(A−ρ(v)I) = 0. Montrer qu’il existe w ∈ IRn avec kwk2 = 1

vérifiant

(A − ρ(v)I)w = 0

6– On considère l’algorithme

Soient t ”assez petit” et v0 tel que kv0k2 = 1

Pour k=1,2 ... faire

• Si det(A − ρ(vk−1)I) = 0, alors il existe wk ∈ IRn tel que kwkk2 = 1 et

(A − ρ(vk−1)I)wk = 0

λk = ρ(vk−1)

vk = wk

STOP

• Si det(A − ρ(vk−1)I) 6= 0 alors

Résoudre (A − ρ(vk−1)I)zk = vk−1

Déterminer αk ∈ IR tel que k(1 − t)vk−1 + tαkzkk2

wk = −vk−1 + αkzk

vk = vk−1 + twk

λk = ρ(vk)

2 = 1

6-a Montrer en utilisant 3-, que dans le cas où det(A − ρ(vk−1)I) 6= 0, on a pour t ”assez petit”

kf (vk)k2 < kf (vk−1)k2

6-b Que représente l’élement (λk, vk) dans le cas où det(A − ρ(vk−1)I) = 0 ?

6-c On suppose que l’algorithme ci-dessus converge. Quelle est alors la limite de la suite (λk, vk).

(cid:3)

2

E.N.I.T.

Examen – Session de rattrapage

Analyse Numérique

Enseignants : H. El Fekih – K. Gribaa – M. Mnif – M. Moakher

Classe : 1ère année GC – GE – GI – GM – INFO – TELEC

Documents non autorisés

28 juin 2004

Durée : 1h30

Exercice

Soit M une matrice de M2n(R) définie par blocs comme suit :

M =

(cid:18) A11 A12

A21 A22

(cid:19)

où Aij, 1 ≤ i, j ≤ 2, sont quatre matrices dans...