program ep95-288.pas; { Epreuve informatique de l'Ecole Polytechnique 95.288 -------------------------------------------------------------- 1) On considère la famille de matrices Ml Ml[1,1]=h Ml[1,2]=1 Ml[2,1]=h²-1 Ml[2,2]=h où h est un paramètre réel. Ecrire un programme qui calcule Ml^n , n-ième puissance de Ml pour toute valeur n 2) Soit u=(x,y) un vecteur à deux composantes réelles. On définit par récurrence la suite de vecteurs un à partir d'un vecteur initial u0 non nul selon la règle suivante : u[n+1]=Ml.u[n] A l'aide d'un programme Pascal, tracer dans un repère cartésien la suite de points d'affixe (xn,yn) composantes du vecteur un lorsque n croît. Qu'observe-t-on lorsque M appartient à la famille de matrices Ml ? Interpréter. Aurait-on pu prévoir le résultat sans l'aide d'un ordinateur ? 3) Quelles sont les valeurs de h pour lesquelles la suite un est bornée ? périodique ? Illustrer avec des exemples. 4) Soit F l'ensemble des matrices Ml telles que la suite un soit bornée. A tout couple de matrices Ml et Mm appartenant à F, on associe la matrice produit M = Ml.Mm. Tracer comme précédemment les images des suites de vecteurs définies par la récurrences : u[n+1]=M.u[n]. A quoi reconnaît-on qu'une matrice a priori quelconque de la forme M=[ a b ] [ c d ] est décomposable en un produit M = Ml.Mm du type précédent ? Ecrire un programme qui effectue cette décomposition, et l'appliquer à M=[ -7/12 5/6 ] [ -25/36 -13/18 ] 5) En multipliant entre elles de toutes les manières possibles un nombre quelconque de matrices appartenant à F, on obtient un surensemble Y. Montrer expérimentalement que pour toute matrice M de Y, la suite de vecteurs y[+1=M.u[n] est bornée et ne converge pas si u[0]=/=0 La réciproque est-elle vraie ? En déduire une méthode de décomposition de toute matrice M de Y en un produit de matrices appartenant chacune à F. Exemple de décomposition : [ 0 -1 ] = Ml.Mm.Mn avec l=0.5 m=-0.5 et n=0 [ 1 0 ] Programmer cette méthode pour l'appliquer aux exemples suivants : 1° M = [ -1/2 1 ] [ -3/4 -1/2 ] 2° M = [ -1 1 ] [ -2 1 ] +------------------------------------------------------------+ ¦ Imprimer tous les résultats ¦ ¦ en indiquant chaque fois à quoi ils correspondent ¦ +------------------------------------------------------------+ -=-=-=- } uses modubase, crt; const maxn=100; type Myreal=Double; Myint=Longint; Vecteur=array[1..2] of MyReal; matrice=array[1..2,1..2] of MyReal; var ch:char; n:integer; Lambda,mu:MyReal; un:array[0..maxn] of Vecteur; procedure New_Mat(VAR m:matrice;a,b,c,d:MyReal); begin m[1,1]:=a; m[1,2]:=b m[2,1]:=c; m[2,2]:=d; end; procedure AddMatrice(a,b:matrice;VAR c:matrice); var i,j:integer; begin for i:=1 to n do for j:=1 to n do c[i,j]:=a[i,j]+b[i,j]; end; procedure Mul_Mat(a,b:matrice;VAR c:matrice); var i,j,k:integer; x:MyReal; begin for i:=1 to 2 do for j:=1 to 2 do begin x:=0; for k:=1 to 2 do x:=x+a[i,k]*b[k,j]; c[i,j]:=x; end; end; procedure Aff_Mat(m:matrice); var i,j:integer; begin for i:=1 to 2 do begin for j:=1 to 2 do write(' m[',i,',',j,']=',m[i,j]:12:8); WriteLN; end; end; procedure Mat_vec(m:matrice;u:vecteur;VAR v:vecteur); begin v[1]:=m[1,1]*u[1]+m[1,2]*u[2]; v[2]:=m[2,1]*u[1]+m[2,2]*u[2]; end; procedure Gen_mat(VAR a:matrice;lambda:MyReal); begin a[1,1]:=lambda; a[1,2]:=1; a[2,1]:=sqr(lambda)-1; a[2,2]:=lambda; end; function determinant(m:matrice):MyReal; begin determinant:=m[1,1]*m[2,2]-m[1,2]*m[2,1]; end; procedure Decompose(m:matrice); var a,b,c,d,det:MyReal; aa,bb,cc,Delta:MyReal; { equation du second degré en Nu } lambda,mu,nu:Myreal; m1,m2,m3,m0:matrice; procedure Solution3; begin if b*Nu=a then begin WriteLN('Cas particulier (0, -1, 1 0)'); WriteLN('Toutes les solutions Lambda=0 Mu=-Nu'); WriteLN('ou Mu=-Lambda Nu=0 conviennent.'); end else begin Lambda:=(d*Nu-c+1)/(b*nu-a); Mu:=(a*Nu-b*(Nu*Nu-1)+1)/(b*nu-a); WriteLN('Lambda=',Lambda:12:8,' Mu=',Mu:12:8, ' Nu=',Nu:12:8); WriteLN('Verification:'); Gen_mat(m1,Lambda); Gen_mat(m2,Mu); Gen_mat(m3,Nu); Mul_mat(m1,m2,m0); Mul_mat(m0,m3,m0); Aff_mat(m0); end; end; begin a:=m[1,1]; b:=m[1,2]; c:=m[2,1]; d:=m[2,2]; Efface; WriteLN('Matrice à décomposer:'); Aff_mat(m); det:=a*d-b*c; if abs(det-1)>0.0001 then WriteLN('Déterminant=',det,'<>1 ==> décomposition impossible') else if abs(b*b-a-d-2)<0.001 then begin if b=0 then begin if c=0 then WriteLN('Il y a une infinité de décompositions M(Lambda).M(-Lambda)') else WriteLN('Aucune décomposition'); end else begin Lambda:=(d+1)/b; Mu :=(a+1)/b; WriteLN('Il y a une décomposition en deux matrices :'); WriteLN('Lambda=',Lambda:12:8,' Mu=',Mu:12:8); WriteLN('Verification:'); Gen_mat(m1,Lambda); Gen_mat(m2,Mu); Mul_mat(m1,m2,m0); Aff_mat(m0); end; end else begin WriteLN('décomposition en trois éléments'); aa:=b*(1+b); bb:=-(a+d+2*a*b); cc:=a*a-b+c-2; if aa=0 then begin if bb=0 then begin writeLN('Cas dégénéré'); WriteLN('décomposition en une matrice unique Lambda=',a); Gen_mat(m,a); Aff_mat(m); end else begin Nu:=-cc/bb; Solution3; end; end else begin Delta:=bb*bb-4*aa*cc; if Delta<0 then WriteLN('Impossible DELTA=',Delta,' <0') else begin Nu:=(-bb+sqrt(Delta))/(2*aa); Solution3; Nu:=(-bb-sqrt(Delta))/(2*aa); Solution3; end; end; end; Pause; end; procedure Question_1; var m:matrice; u,v:vecteur; begin Randomize; lambda:=random; if random<0.5 then lambda:=-lambda; Gen_mat(m,lambda); Aff_mat(m); Pause; ModeGraphique; IsoFenetre(-3,3,-2); X_axe(0,0,1); Y_axe(0,0,1); lambda:=1; Repeat lambda:=lambda/2; Gen_mat(m,lambda); Deplace(0,1);Ecris('lambda=');EcrisReel(Lambda); u[1]:=1; u[2]:=0; deplace(u[1],u[2]); repeat Mat_Vec(m,u,v); u:=v; Point(u[1],u[2]); Delay(100); until KeyPressed; ch:=ReadKey; until false; end; procedure Question_2; var m1,m2,m:matrice; u,v:Vecteur; C : Integer ; begin lambda:=random; mu:=random; Gen_mat(m1,lambda); Gen_mat(m2,mu); Mul_mat(m1,m2,m) Aff_mat(m); PAuse; ModeGraphique; Couleur (Brillant) ; IsoFenetre(-3,3,-2); X_axe(0,0,1) Y_axe(0,0,1); Couleur(1+random(10)); u[1]:=1; u[2]:=0; deplace(u[1],u[2]); C := 0 ; repeat Inc (C) ; If (C = 16) Then C := 1 ; Couleur (C) ; Mat_Vec(m,u,v); u:=v; Delay (10) ; Trace(u[1],u[2]); until KeyPressed; ch:=ReadKey; end; procedure Question_3; var m1,m2,m:matrice; u,v:Vecteur; i:integer; begin ModeGraphique; repeat Gen_mat(m,random); for i:=1 to random(12) do begin Gen_mat(m1,random); Mul_mat(m1,m,m); end; efface; IsoFenetre(-3,3,-2); X_axe(0,0,1); Y_axe(0,0,1); u[1]:=1; u[2]:=0; deplace(u[1],u[2]); repeat Mat_Vec(m,u,v); u:=v; Trace(u[1],u[2]); Delay(100); until KeyPressed; ch:=ReadKey; until false; end; procedure Question_4; var m1,m2,m:matrice; u,v:Vecteur; i:integer; begin ModeGraphique; repeat m[1,1]:=0; m[1,2]:=-1; m[2,1]:=1; m[2,2]:=0; IsoFenetre(-3,3,-2); X_axe(0,0,1); Y_axe(0,0,1); u[1]:=random; u[2]:=random; deplace(u[1],u[2]); repeat Mat_Vec(m,u,v); u:=v; Trace(u[1],u[2]); Delay(100); until KeyPressed; ch:=ReadKey; until false; end; procedure Question_5; var m:matrice; begin repeat Efface; WriteLN(' ====== Decomposition de M(a,b,c,d) ============'); WriteLN(' '); WriteLN(' '); WriteLN(' (1) -7/12 5/6 -25/36 -13/18'); WriteLN(' (2) -1 0 0 -1 '); WriteLN(' (3) 0 -1 1 0 '); WriteLN(' (4) -1/2 1 -3/4 -1/2 '); WriteLN(' (5) -1 1 -2 1 '); WriteLN(' (6) -1/3 -1 8/9 -1/3 '); WriteLN(' (7) -89/96 -3/8 145/288 -7/8 '); WriteLN(' (8) Matrice de votre choix '); WriteLN(' '); Write(' Tapez votre Choix : '); Repeat Read(ch); case ch of '1': New_Mat(m,-7/12,5/6,-25/36,-13/18); '2': New_Mat(m,-1,0,0,-1); '3': New_Mat(m,0,-1,1,0); '4': New_Mat(m,-1/2,1,-3/4,-1/2); '5': New_Mat(m,-1,1,-2,1); '6': New_Mat(m,-1/3,-1,8/9,-1/3); '7': New_Mat(m,-89/96,-3/8,145/288,-7/8); '8': begin Write('Entrez m[1,1]=');ReadLN(m[1,1]); Write('Entrez m[1,2]=');ReadLN(m[1,2]); Write('Entrez m[2,1]=');ReadLN(m[2,1]); Write('Entrez m[2,2]=');ReadLN(m[2,2]); end; end; { esac} Until ch in ['1'..'8']; Decompose(m); until ch='0'; end; procedure Presentation; begin; Efface; WriteLN(' ====== Famille de matrices ============'); WriteLN(' '); WriteLN(' '); WriteLN(' (1) Suite de vecteurs '); WriteLN(' (2) Deux matrices '); WriteLN(' (3) >2 matrices '); WriteLN(' (4) M(0,-1,1,0) '); WriteLN(' (5) Decomposition M '); WriteLN(' '); Write(' Tapez votre Choix : '); end; begin Randomize; InitGraphique; repeat ModeTexte; Presentation; Read(Ch); case ch of '1': Question_1; '2': Question_2; '3': Question_3; '4': Question_4; '5': Question_5; '0' : Halt end; until false; end.