[PDF] Exercices de mathématiques - Exo7

View - Download Exercices de mathématiques - Exo7

Previous PDF

Next PDF

Enoncés et corrections : Ana Matos.

Exo7

Méthodes itératives

Exercice 1

Soita2RetA=0

@1a a a1a a a11 A 1. Pour qu"elles v aleursde a Aest-elle définie positive? 2. Pour qu"elles v aleursde ala méthode de Gauss-Seidel est-elle convergente? 3.

Ecrire la matrice Jde l"itération de Jacobi.

4. Pour qu"elles v aleursde ala méthode de Jacobi converge-t-elle? 5. Ecrire la matrice L1de l"itération de Gauss-Seidel. Calculerr(L1). 6.

Pour quelles v aleursde ala méthode de Gauss-Seidel converge-t-elle plus vite que celle de Jacobi?

SoitAune matrice hermitienne inversible décomposée enA=MNoùMest inversible. SoitB=IM1A la matrice de l"itération: x n+1=Bxn+c:

Supposons queM+MAsoit définie positive.

1. Soit xun vecteur quelconque et on posey=Bx. Montrer l"identité: (x;Ax)(y;Ay) = ((xy);(M+MA)(xy)): 2.

Supposons que Aest définie positive. Soitx6=0 un vecteur propre deBassocié à la valeur proprel,

y=Bx=lx. Utiliser l"identité précédente pour montrer quejlj<1. Que peut-on conclure sur la convergence de la méthode? 3. Supposons maintenant que r(B)<1. montrer queAest définie positive. 4. Supposons Adécomposée par points ou par blocs sous la forme

A=DEFavecDdéfinie positive:

Montrer que la méthode de relaxation par points ou par blocs pour 0

Aest définie positive.

SoitA=IEEune matricecarrée d"ordreNoùEest unematrice strictement triangulaireinférieure (eij=0

pouri6j). Pour résoudre le systèmeAx=b, on propose la méthode itérative définie par (IE)x2k+1=Ex2k+b (IE)x2k+2=Ex2k+1+b 1

1.Déterminer Betcpour que l"on ait:

x

2k+2=Bx2k+c:

Vérifier queB=M1NetA=MNavecM= (IE)(IE),N=EE.

2.

Montrer que M+Nest une matrice définie positive. En déduire une condition nécessaire et suffisante

pour la convergence de la méthode.

SoientAetBdeux matrices réelles d"ordreNeta;bdeux vecteurs deRn. On considère les deux itérations

suivantes: xk+1=Byk+a y k+1=Axk+bk=0;1;(1) avecx0;y02Rndonnés. 1. Déterminer une condition nécessaire et suf fisantede con vergencedes deux suites de v ecteurs. 2. Soit zk= (xk;yk)T2R2n. Montrer que (1) peut s"écrire z k+1=Czk+c oùCest une matrice d"ordre 2n. ExpliciterCetc. 3.

Montrer que r2(C) =r(AB).

4. On considère maintenant les deux itérations sui vantes: xk+1=Byk+a y k+1=Axk+1+bk=0;1;(2) Donner une condition nécessaire et suffisante de convergence.

Montrer que (

2 ) est équivalent à z k+1=Dzk+d oùDest une matrice d"ordre 2N.

Montrer quer(D) =r(AB).

5.Taux de convergence

On appelle taux de convergence asymptotique de la matrice itérativeMle nombre

R(M) =ln(r(M))):

On poseek=xkxl"erreur de l"itéré d"ordrek.

(a)

Montrer que le nombre d"itérations kpour réduire l"erreur d"un facteure, i.e.,kekkke0k6evérifie

k>lneR(M): (b)

Comparer le taux de con vergencedes algorithmes (

1 ) et ( 2

On considère le systèmeAx=bavec

A=0 B

BBB@3 1 0 0 0

1 2 1 0 0

0 2 3 1 0

0 0 1 4 3

0 0 0 1 11

C

CCCA(3)

2

1.Décomposer Asous la formeLUet en déduire que (3) admet une solution uniquex.

2.

Ecrire l"itération de Gauss-Seidel pour ce systèm e,c"est-à-dire, le système linéaire donnant Xn+1=

(xn+1;yn+1;zn+1;tn+1;un+1)en fonction deXn= (xn;yn;zn;tn;un). 3. Pour tout n2Non poseen=Xnx. Montrer qu"il existea2[0;1[tel que:

8n2Nken+1k¥6akenk¥:

En déduire la convergence de la suite.

4.

Déterminer la matrice de Gauss-Seidel L1associée àA. CalculerkL1k¥. En déduire la convergence de

(Xn)versx. 5. Soit A2Rnnvérifiant la propriété suivante: jaijj>åj6=ijaijji=2;;n ja11j>åj6=1ja1jj et sur chaque ligne deAil existe il existe un terme non nulaijpouri>2 etj2.y=Bx=lx)xy= (1l)x. En utilisant l"égalité précédente (x;Ax)(y;Ay) = (x;Ax)(lx;A(lx)) = (1jlj2)(x;Ax) (xy;(M+MA)(xy)) = ((1l)x;(M+MA)((1l)x)) =j1lj2(x;(M+MA)x) et donc (1jlj2)(x;Ax) =j1lj2(x;(M+MA)x) lne peut pas être=1 car sinony=Bx=x,xM1Ax=x,M1Ax=0,x=0. Doncl6=1, M+MAdéfinie positive,j1lj2>0,Adéfinie positive impliquent que 1jlj2>0, jlj<1. Doncr(B)<1 et la méthode itérative converge. 3. Démonstration par a bsurde.Supposons que ce n"est pas vrai: 9x06=0a0= (x0;Ax0)60. Alors la suitexn=Bxn1=Bnx0tend vers 0 et liman=lim(xn;Axn) =0 On utilise maintenant la relation de la question 1 avecx=xn1ety=Bxn1=xnet on obtient a n1an= (xn1xn;(M+MA)(xn1xn)>0 sixn1xn6=0 (ce qui est vrai car sinonxn1=xn=Bxn1etBa une valeur propre=1) Donc(an1an)est une suite strictement décroissante convergeant vers 0 aveca0<0. Ceci est impossible et doncAest définie positive 4. Soit A=DEFla décomposition usuelle deA. CommeAest hermitienne,D=DetF=E. Pour la méthode de relaxation on aM=D=wEet donc M +MA=D=wF+D=wED+E+F=2ww D quiesthermitienne. Pour0on conclut que la méthode converge ssiAest définie positive.Correction del"exer cice3 N1.On a x2k+1= (IE)1Ex2k+(IE)1bet donc

x

2k+2= (IE)1E(IE)1Ex2k+(IE)1E(IE)1b+(IE)1b

MaisE(IE)1= (IE)1Eet alors

x

2k+2= (IE)1(IE)1EEx2k+(IE)1(IE)1(E+IE)b=M1Nx2k+M1b

avec

M= (IE)(IE);N=EE;MN=IEE=A

4

2.M+N=IEE+2EEet donc

v (M+N)v=kvk22vEvvEv+2vEEv=kEvk22+(kvk22+kEvk222Re(v;Ev))Onal"inégalité

2kvkkEvk62j(v;Ev)j62jRe(v;Ev)j

et donc (kvk2kEvk2)26kvk22+kEvk222Re(v;Ev)) v (M+N)v>kEvk22+(kvkkEvk2)2implique que v (M+N)b=0, kEvk2=0 etkvk2=kEvk2, kvk2=0

DoncM+Nest définie positive et en appliquant un résultat d"un exercice précédent on conclut que la

méthode converge ssiAest définie positive.Correction del"exer cice4 N1.C"est f acileà v oirque si (xk)converge versxet(yk)converge versy, alorsxetysont solution des

systèmes(IBA)x=Bb+aet(IAB)y=Aa+b. On a: xk+1=B(Axk1+b)+a=BAxk1+Bb+a y k+1=A(Byk1+a)+b=AByk1+Aa+b et donc(xk)converge ssir(BA)<1 et(yk)converge ssir(AB)<1.

2.zk+1=Czk+cavecC=0B

A0 ;c=a b 3. Soit lvaleur propre non nulle deCetz= (x;y)Tvecteur propre associé

Cz=lz,By=lx

Ax=ly)ABy=lAx=l2y)

l

2est valeur propre deAB.

Soit maintenantavaleur propre deAB, 9u6=0 :ABu=au. On poseb2=aetx=Bu,y=bu C x y =bBu ABu =bBu b 2u =bx y et doncr2(C) =r(AB)

4.D=0B

0AB ;d=a Aa+b . La démonstration der(D) =r(AB)se fait comme dans la question précédente. 5. (a) ek=Mke0)kekkke0k6kMkk6e. Il suffit donc d"avoirkMkk1=k6e1=k)log(kMkk1=k)61k loge c"est- à direk>logelog(kMkk1=k)Mais commer(M)6kMkk1=kon obtient finalement k>loge=R(M) (b) nous a vonsr2(C) =r(AB))r(C) =pr(AB)etr(D) =r(AB). Doncr(D)

R(C). Donc on atteint la même réduction d"erreur avec un plus petit nombre d"itérations de la

méthode 2)Correction del"exer cice5 N5 1. 2.

Itération de Gauss-Seidel : (DE)Xn+1=FXn+bavec

DE=0 B BBB@3 1 2 0 2 3

0 0 1 4

0 0 0 1 11

C

CCCA;F=0

B

BBB@0 1

0 1 0 1 0 3 01 C CCCA

3.en=XnX; ;Xn+1= (DE)1FXn+(DE)1b;X= (DE)1FX+(DE)1b)en+1=

(DE)1Fen On obtient alors(DE)en+1= (DE)1Fenet si on écrit composante à composante on obtient

3e1n+1=e2n) je1n+1j613

kenk¥ e

1n+1+2e2n+1=e3n) je2n+1j616

kenk¥+12 kenk¥=23 kenk¥

2e2n+1+3e3n+1=e4n) je3n+1j623

23
kenk¥+13 kenk¥=79 kenk¥ e n+132+4e4n+1=3e5n) je4n+1j614 79
kenk¥+34 kenk¥=3416 kenk¥ e

4n+1+e5n+1=0) je5n+1j61718

kenk¥ et donc kenk¥61718 kenk¥ 4. (DE)1=0 B

BBB@13

0 0 0 0

16 12 0 0 0 19 13 13 0 0 136
112
112
14 0 136
112
112
14 11 C CCCA; L

1= (DE)1F=0

B BBB@0 13 0 0 0 016 12 0 0 0 19 12 13 0 0136
112
112
34
0136
112
112
34
1 C CCCA et donckL1k¥=max(13 ;46 ;1718 ;3236 ;3236 ) =1718

On en déduit donc la convergence de(Xn)versX.6

quotesdbs_dbs11.pdfusesText_17

[PDF] exercices corrigés microéconomie 1ère année

[PDF] exercices corrigés microéconomie équilibre général

[PDF] exercices corrigés mitose

[PDF] exercices corrigés mouvement des satellites

[PDF] exercices corrigés mouvement seconde

[PDF] exercices corrigés ondes seconde

[PDF] exercices corrigés ondes terminale s

[PDF] exercices corrigés optimisation non linéaire

[PDF] exercices corrigés optique géométrique pdf

[PDF] exercices corrigés optique ondulatoire mp

[PDF] exercices corrigés orthogonalité dans l'espace

[PDF] exercices corrigés outlook 2010

[PDF] exercices corrigés pendule elastique

[PDF] exercices corrigés pert pdf

[PDF] exercices corrigés ph des solutions aqueuses