Recueil d'Examens - Analyse Numérique

Montrer que

(b) On pose

Montrer que, pour h ≤ T , on a :

ξn = |αn| + |βn+1/2|.

|ξn+1| ≤ (1 + Λh)|ξn| + ϕn

o`u

Λ = max(L, 1 + LT ), ϕn = (1 + LT )|εn+1/2| + |ηn+1|.

(c) En d´eduire que

|ξn| ≤ |ξ0|exp(Λ(tn − t0)) +

exp(Λ(tn − t0)) − 1

Λh

max

0≤k≤n−1

ϕk.

(Indication: on pourra utiliser l’in´egalit´e 1 + k < exp(k))

(d) Choisir alors z1/2 de fa¸con qu’on ait

max

0≤n≤N −1

|ξn| = O(h2).

2

E.N.I.T.

14 juillet 2000

Examen – Session de rattrapage

Analyse Num´erique

Enseignants : H. BOUHAFA–H. CHAKER – H. EL FEKIH – H. RIAHI

Classe : 1`ere ann´ee GC - GE - GI - GM

Dur´ee : 1h30

Documents non autoris´es

Exercice 1

Soit f ∈ C 2([−1, 1]) et P le polynˆome d’interpolation d’Hermite de f au point −1 v´erifiant :

P (−1) = f (−1)

et

P 0(−1) = f 0(−1)

1– D´eterminer l’expression de P .

2– On consid`ere la formule de quadrature suivante :

(1)

Z 1

−1

f (t) dt = α0f (−1) + α1f 0(−1) + E(f )

2–a D´eterminer α0 et α1 pour que la formule (1) soit de degr´e au moins 1.

2–b Montrer qu’il existe η ∈ [−1, 1] tel que E(f ) = 4

3 f 00(η).

Indication : On rappelle que pour tout t ∈ [−1, 1], il existe ξt ∈ [−1, 1], d´ependant de t, tel que f (t) − P (t) =

2 (t + 1)2f 00(ξt).

1

Exercice 2

1– Soit B = (bij) une matrice a n lignes et n colonnes, a coefficients r´eels, v´erifiant :

bij ≥ 0

sup

1≤i≤n

n

X

(

j=1

; 1 ≤ i, j ≤ n

bij) < 1

Montrer que I − B est inversible et que (I − B)−1 est `a coefficients positifs ou nuls (I d´esigne la matrice

identit´e).

2– Soit A = (aij) une matrice a n lignes et n colonnes, a coefficients r´eels, v´erifiant :

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´ee 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´eelle, sym´etrique d´efinie positive `a nlignes et n colonnes, et un vecteur

b ∈ IRn.

On consid`ere, pour r > 0 donn´e, la suite d’´el´ements de IRn d´efinie par :

(cid:26) x(o) donn´e 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´eduire un algorithme de r´esolution du syst`eme lin´eaire Ax = b.

E.N.I.T.

Examen – Analyse Num´erique

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

Classe : 1`ere ann´ee GC – GE – GI – GM

2000/2001

Date : 2 Avril 2001

Dur´ee : 1h30

Documents non autoris´es

Exercice 1

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

(compt´ees avec leur ordre de multiplicit´e) v´erifiant :

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

On consid`ere la matrice B d´efinie par B = A − λnunut

propre de A associ´e `a λn, tel que kunk2 = 1.

n, o`u un est un vecteur

1. Montrer que Bun = 0.

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

associ´e λi, 1 ≤ i ≤ n − 1.

3. En d´eduire une m´ethode 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´erieure `a diagonale unit´e

UA ∈ Mn(R) triangulaire sup´erieure

B = LBUB,

LB ∈ Mm(R) triangulaire inf´erieure `a diagonale unit´e

UB ∈ Mm(R) triangulaire sup´erieure

Soit M ∈ Mn+m(R) d´efinie (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´ethode pour r´esoudre le systeme lin´eaire M x = b, ou

b ∈ Rn+m et donner le nombre d’op´erations ´el´ementaires.

Exercice 3

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

lin´eaire

(1)

Ax = b

dont on notera ¯x sa solution.

1. Montrer que la matrice AT A est sym´etrique d´efinie positive.

2. Pour r´esoudre le systeme (1), on considere la m´ethode du gradient `a pas

constant appliqu´ee au syst`eme AT Ax = AT b :

(2)

(cid:26) x(0) ∈ Rn

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

k ≥ 0

o`u r ∈ R∗

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

2.a Montrer que la m´ethode du gradient `a pas constant (2) est convergente, si

et seulement si 0 < r <

, o`u k·k2 d´esigne la norme matricielle subordonn´ee

2

kAk2

2

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

d´efinie par (2) ?

2.b Soit ε > 0, montrer que

kg(k)k2

kAT bk2

≤ ε =⇒

kx(k) − ¯xk2

k¯xk2

≤ ε[cond2(A)]2

o`u cond2(A) = kAk2 kA−1k2 et ¯x d´esigne la solution de (1).

2.c Ecrire l’algorithme de la m´ethode du gradient `a pas constant appliqu´ee au

syst`eme AT Ax = AT b.

2

E.N.I.T.

Examen – Analyse Num´erique

Enseignant(s) : H. EL FEKIH

Classe : 1`ere ann´ee INFO & TELEC

2000/2001

Date : 13 Janvier 2001

Dur´ee : 1h30

Documents non autoris´es

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ˆomes de Lagrange aux points x1, . . . , xn. On pose, pour j = 1, . . . , n,

Lj(x) =

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

n

X

i=1

Exercice 2

On consid`ere l’´equation diff´erentielle :

(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’´equation diff´erentielle (E), on propose le sch´ema num´erique 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`u α, β et λ sont des r´eels ≥ 0, et xn, n = 0, · · · , N , (N + 1) points ´equidistants de [a, b]. On rappelle que f (k)

est donn´ee 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´ema (S) est

stable.

2– A quelle condition le sch´ema (S) est-il consistant ?

3– D´eterminer α, β et λ pour que le sch´ema (S) soit d’ordre (au moins) 3.

4– En d´eduire, que pour ce choix de α, β et λ , le sch´ema (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´eels non nuls ω1 et ω2. Soit

la formule de quadrature suivante :

Z 1

−1

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

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

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

2– Montrer qu’une condition n´ecessaire et suffisante pour que la formule soit exacte pour les polynˆomes impairs

de degr´e inf´erieur ou ´egal 3 est que τ1 = −τ2 et ω1 = ω2 .

3– En d´eduire les valeurs de τ1, τ2, ω1 et ω2 pour que la formule soit exacte pour tous les polynˆomes de degr´e

inf´erieur ou ´egal 3. A quelle famille appartient la formule obtenue ?

E.N.I.T.

11 juillet 2001

Examen – Session de rattrapage

Analyse Num´erique

Enseignant(s) : H. EL FEKIH

Classe : 1`ere ann´ee INFO & TELEC

Dur´ee : 1h30

Documents non autoris´es

Exercice

Soit a et b deux r´eels 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´erifie :

(1)

∀P ∈ P2,

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

2 , b] = 1

On supposera dans toute la suite que les r´eels λ0, λ1 et λ2 sont tels que la propri´et´e (1)

soit v´erifi´ee.

1– Montrer que f [a, a+b

de f aux points a, a+b

2 , b.

2– Soit Pf le polynˆome 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´esigne la diff´erence divis´ee d’ordre 2

2 ∆2f , o`u f [a, a+b

2 , b et r(x) =

2 ).

2–c En d´eduire que

|E(f )| ≤

b − a

2

sup

x∈[a,b]

|f 000(x)|

3– Calculer les r´eels λ0, λ1, λ2 en fonction de a et b pour que la propri´et´e (1) soit v´erifi´ee.

Probl`eme

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

donn´ee par :

(1)

Z 1

−1

f (x) dx =

k

X

i=0

λif (xi) + E(f )

o`u nous avons d´esign´e par :

• E(f ) le terme d’erreur (on ne s’int´eresse pas ici `a l’´etude de E(f ));

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

• λi, 0 ≤ i ≤ k, les poids d’int´egration.

On rappelle que x0, . . . , xk sont les k + 1 racines du (k + 2)-i`eme polynˆome orthogonal de

Legendre Qk+1 ∈ Pk+1 (qui est unitaire) associ´e `a la fonction poids w ≡ 1 sur l’intervalle

[−1, 1].

Le but de ce probl`eme 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´ee par (1).

Le probleme est divis´e en trois parties. La premiere est une ´etape pr´eliminaire, 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´eels, m > 0, et P ∈ Pm+1 le polynˆome

d´efini par P (x) = (x − r0) (x − r1) · · · (x − rm).

On considere la m´ethode de Newton appliqu´ee a la r´esolution de l’´equation P (x) = 0.

On rappelle que cette m´ethode g´en`ere la suite d´efinie par :

t0 donn´e,

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´ecroissante.

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

‘→+∞

t‘ = rm.

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

associ´e `a la fonction poids w ≡ 1 sur l’intervalle [−1, 1], et ses (k + 1) racines not´ees

x0 < x1 < . . . < xk.

II.1– Montrer que la m´ethode de Newton appliqu´ee `a Qk+1, avec une initialisation t0 > xk,

g´en`ere 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 ´et´e d´ej`a

calcul´ees et on se propose de calculer xj−1.

On consid`ere le polynˆome Rj ∈ Pj d´efini par : Rj(x) = Qk+1(x)/ Qk

Montrer que la m´ethode de Newton appliqu´ee au polynˆome Rj, avec une initialisation

i=j(x − xi)

t0 = xj, g´en`ere une suite (t‘)‘≥0 qui converge vers xj−1.

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

de Qk+1.

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

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

degr´e 2k + 1.

Montrer que les poids λi, i = 0, . . . , k, sont donn´es 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´erique

Enseignant(s) : H. EL FEKIH

Classe : 1`ere ann´ee GE & TELEC

2001/2002

Date : 12 Mars 2002

Dur´ee : 1h30

Documents non autoris´es

Exercice 1

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

1– Soit A ∈ Mn(R) la matrice donn´ee par A = uut. Calculer |||A|||2, o`u ||| · |||2 d´esigne la norme

matricielle subordonn´ee `a la norme vectorielle k · k2.

2– Soit B la matrice donn´ee par B = I + A, o`u I d´esigne la matrice identit´e. 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´erieure `a diagonale unit´e

triangulaire sup´erieure

triangulaire inf´erieure `a diagonale unit´e

triangulaire sup´erieure

Soit M ∈ Mn+m(R) d´efinie (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´ethode pour r´esoudre le systeme lin´eaire M x = b, ou b ∈ Rn+m, et donner le

nombre d’op´erations ´el´ementaires.

Exercice 3

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

(1)

Ax = b

dont on notera ¯x sa solution.

1– V´erifier que le systeme (1) est ´equivalent au systeme :

(2)

AT Ax = AT b

2– Montrer que la matrice AT A est sym´etrique d´efinie positive.

3– Pour r´esoudre le systeme (1), on considere la m´ethode du gradient `a pas constant appliqu´ee au

syst`eme (2) :

(3)

(cid:26) x(0) ∈ Rn

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

k ≥ 0

o`u r ∈ R∗

+ et J(·) est la fonctionnelle d´efinie sur Rn par :

(·, ·) d´esigne le produit scalaire euclidien dans Rn.

J(x) =

1

2

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

3–a Montrer que la m´ethode du gradient `a pas constant (3) est convergente, si et seulement si

0 < r <

, ou k · k2 d´esigne la norme matricielle subordonn´ee a la norme vectorielle k · k2.

2

kAk2

2

Quelle est dans ce cas la limite de la suite (x(k))k≥0 d´efinie 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`u cond2(A) = kAk2 kA−1k2 et ¯x d´esigne la solution de (2)(ou de (1)).

3–c Ecrire l’algorithme de la m´ethode du gradient a pas constant appliqu´ee au systeme (2).

2

E.N.I.T.

juillet 2002

Examen – Session de rattrapage

Analyse Num´erique

Enseignante : Henda El Fekih

Classe : 1`ere ann´ee GE 1-2 & TELEC 1-2

Dur´ee : 1h30

Documents non autoris´es

Exercice 1

On considere le systeme lin´eaire Ax = c o`u A une matrice carr´ee inversible d’ordre n . On note λi ses valeurs

propres ordonn´ees comme suit : 0 < λ1 < λ2 < .... < λn−1 < λn. Soit B une autre matrice carr´ee inversible

d’ordre n.

1. Montrer que le systeme lin´eaire Ax = c est ´equivalent au systeme : x = (I − B−1A)x + d,

o`u I est la matrice idendit´e et d un vecteur que l’on exprimera en fonction de c.

2. On suppose que B = αI (α > 0) et on consid`ere la m´ethode it´erative : 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´eduire une condition sur α assurant que la m´ethode it´erative est convergente.

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

Exercice 2

On considere le systeme lin´eaire Ax = b o`u A =





1

β 1

γ

0

0 α

0

1





b =





1

3

2



, o`u α, β, γ ∈ R sont donn´es.

1- Ecrire les m´ethodes it´eratives de Jacobi et Gauss-Seidel pour r´esoudre le syst`eme lin´eaire 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´eration, `a partir du vecteur initial

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

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

4- Dire laquelle des deux m´ethodes converge la plus vite.

Exercice 3

On consid`ere la matrice carr´ee d’ordre 4 suivante :



A =







2

4

2

4

2

4









1

1

1

2

o`u les termes manquants sont des z´eros.

1- calculer la factorisation LU de la matrice A et comparer la structure (c’est-`a-dire la position des ´el´ements

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

2- Si on consid`ere 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`u tous les coefficients αi, βi et γi sont des r´eels donn´es, 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’´etape p de la factorisation LU , la p-eme ligne de U et la p-`eme colonne de L sont

d´etermin´ees 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´erique

Enseignant(s) : H. El Fekih

Classe : 1`ere ann´ee GM

2002/2003

Date : 11 Juin 2003

Dur´ee : 1h30

Documents non autoris´es

Exercice 1

On suppose que l’´equation

(1)

f (x) = g(x)

admet une unique solution simple α sur [a, b],o`u f et g sont monotones et d´erivables.

1– D´emontrer que si |

g0(α)

f 0(α)

| < 1, alors la m´ethode it´erative

x0 donn´e,

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

est convergente.

2– On suppose que |

g0(α)

f 0(α)

| > 1. Proposer une m´ethode it´erative convergente pour calculer α.

Exercice 2

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

propre associ´e u de norme kuk2 = 1, o`u k · k2 d´esigne la norme euclidienne de Rn.

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

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

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

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

3– Soient λ1, λ2, . . . , λn les valeurs propres de A, compt´ees avec leur ordre de multiplicit´e,

v´erifiant :

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

En utilisant la m´ethode de la puissance, donner une m´ethode qui permet de calculer λn et

λn−1 et pr´eciser les hypoth`eses sous lesquelles la m´ethode propos´ee 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´erieure a ´el´ements diagonaux

´egaux a 1, et ou U ∈ Mn(R) est triangulaire sup´erieure.

Pour k ∈ {1, 2, . . . , n}, on note Ak la matrice de Mk(R) obtenue `a 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´erieure a ´el´ements diagonaux ´egaux a 1, et ou Uk ∈ Mk(R)

est triangulaire sup´erieure.

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









Ak =









,

Ak−1

vk

wt

k

akk

o`u vk ∈ Rk−1 et wk ∈ Rk−1.

En supposant connue la factorisation Ak−1 = Lk−1Uk−1 et en ´ecrivant :









Ak =

















Lk−1 0

mt

k

1

Uk−1

qk

0

ukk









,

o`u mk ∈ Rk−1, qk ∈ Rk−1 et ukk ∈ R,

montrer comment on peut d´eterminer la factorisation Ak = LkUk.

3– D´eduire de ce qui pr´ec`ede une m´ethode pour la d´etermination 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´erique

Enseignants : H. El Fekih – K. Gribaa

Classe : 1`ere ann´ee GC & GI

2003/2004

Date : 23 Janvier 2004

Dur´ee : 1h30

Documents non autoris´es

Exercice

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

deuxieme variable. On considere l’´equation diff´erentielle

(E)

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

y(a) = Y0

x ∈ [a, b]

dont la solution exacte est not´ee Y . Soit x0 = a, x1, . . . , xN = b, N + 1 points ´equidistants

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

1– En utilisant la formule d’int´egration num´erique 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`u 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´egration num´erique du rectangle `a 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´eduire un sch´ema num´erique `a un pas :

(S)

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

pour la d´etermination d’une approximation yn de Y (xn).

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

Probl`eme

Soit A ∈ Mn(IR) une matrice sym´etrique d´efinie positive. On consid`ere les fonctions d´efinies

par

ρ : IRn −→ IR

v 7→ vtAv = (Av, v)

f : IRn −→ IRn

v 7→ Av − ρ(v)v

o`u vt d´esigne le transpos´e 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´eduire que u ∈ IRn est solution du probl`eme 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`ere 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´eveloppement limit´e de la fonction h au voisignage de z´ero, 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´eaire (A − ρ(v)I)z = v. Montrer que

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

2

et en d´eduire 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´erifiant

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

6– On consid`ere 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´esoudre (A − ρ(vk−1)I)zk = vk−1

D´eterminer α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`u det(A − ρ(vk−1)I) 6= 0, on a pour t ”assez petit”

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

6-b Que repr´esente l’´element (λk, vk) dans le cas o`u 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´erique

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

Classe : 1`ere ann´ee GC – GE – GI – GM – INFO – TELEC

Documents non autoris´es

28 juin 2004

Dur´ee : 1h30

Exercice

Soit M une matrice de M2n(R) d´efinie par blocs comme suit :

M =

(cid:18) A11 A12

A21 A22

(cid:19)

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