referat, referate , referat romana, referat istorie, referat geografie, referat fizica, referat engleza, referat chimie, referat franceza, referat biologie
 
Informatica Educatie Fizica Mecanica Spaniola
Arte Plastice Romana Religie Psihologie
Medicina Matematica Marketing Istorie
Astronomie Germana Geografie Franceza
Fizica Filozofie Engleza Economie
Drept Diverse Chimie Biologie
 

Puterea unei matrici de ordin 2

Categoria: Referat Matematica

Descriere:

Ceea ce e important pentru noi este că produsul acesta are proprietatea asociativităţii mixte următoare :...

Varianta Printabila 


1 MATRICI PǍTRATE DE ORDIN 2

I.    RIDICAREA LA PUTERE A UNEI MATRICI PǍTRATE DE ORDIN 2

٭ În  ceea ce urmează vom folosi următoarele notaţii :

     , S=a+d  ,   D=ad-bc  ,      ;  a,b,c,d C (am notat cu C mulţimea numerelor complexe).

Presupunem cunoscută identitatea:

A2=SA-DI        (R I.1)

Oricum, se poate verifica foarte uşor. În acest capitol vom da o generalizare a relatiei (R I.1) pentru puteri naturale ale lui A .

        ٭ Înmulţind relaţia (R I.1) cu An-1 obţinem An+1=SAn-DAn-1.
De aici rezultă că putem să considerăm identitatea
      (R I.2)       dacă definim produsul mixt

  unde x,y,z,w C iar M,N sunt matrici pătrate de ordin2.

Ceea ce e important pentru noi este că produsul acesta are proprietatea asociativităţii mixte următoare :
  unde x,y,z,w,x’,y’,z’,w’ C iar M şi N sunt matrici pătrate de ordin 2 cu elemente numere complexe.Aceasta se poate verifica direct prin calcul.

    ٭ Dacă notăm   din relaţia (R I.2) , prin iterare repetată  şi folosind asociativitatea mixtă , rezultă :

 
Deci avem relatia          n≥1        ;     (R I.3)
 care de altfel se poate verifica prin inducţie.

Ceea ce este remarcabil aici este că H are un element egal cu zero ; aceasta ne dă posibilitatea să calculăm Hn şi în cele din urmă An+1.

٭ Calculul lui Hn şi al lui An+1:
Notăm   ; atunci din relaţia    Hn+1=H Hn    rezultă :

  . De aici rezultă :
xn+1=Sxn-Dzn                                                               xn+1=Sxn - Dxn-1
yn+1=Syn-Dwn                                                      yn+1=Syn - Dyn-1            (R I.4)
zn+1=xn                                                                              zn+1=xn
wn+1=yn                                                                             wn+1=yn

Fie p şi q rădăcinile ecuaţiei   ; presupunem că p≠q .
Atunci  şirurile  xn=a1pn+b1qn     şi     yn= a2pn+b2qn       sunt soluţii pentru relaţiile (R I.4) , ceea ce se poate verifica direct prin calcul.
            Numerele a1,b1 şi a2,b2 rezultă din condiţiile iniţiale    şi   
   .    H0=I  deoarece presupunem    det H=D≠0 .
 Rezultă:   x0=1 , y0=0       şi      x1=S , y1= -D  . Aceasta permite să scriem relaţiile :

a1+b1=x0=1                         a2+b2=y0=0
a1p+b1q=x1=S                     a2p+b2q=y1= -D

De aici rezultă printr-un calcul simplu că:
   . De aici deducem :

                                                        
                           Folosind relaţia (R I.3) putem calcula An+1 ; din ea rezultă:
                                                
                    
                    An+1=xnA+ynI=       n≥1       (R I.5)
                     unde p,q sunt rădăcinile distincte ale ecuaţiei   .

II GENERALIZAREA RELAŢIEI :  An+1=    
       
        În determinarea relatiei (R I.5) am folosit faptul că p≠q şi că D≠0. În continuare vom găsi o formulă pentru An care este mai generală pentru că nu depinde de aceste condiţii .

    Notăm Xn=  ; p+q=S şi pq=D  deoarece p,q verifică ecuaţia   .
            Şirul Xn  verifică relaţia de recurenţă Xn+1=SXn – DXn-1 : Într-adevăr SXn – DXn-1= = =Xn+1.De aceea dăm o nouă definiţie pentru Xn

Definiţia 1: Xn+1=def=SXn – DXn-1  cu valorile iniţiale X1=1 şi X2=S  şi   n≥2   ;    (R II.1)

Observaţia1 : termenii X1, X2 , X3 , ... , Xn , ...sunt definiţi independent de relaţiile p≠q şi D≠0
Observaţia2 :putem defini cu aceeaşi relaţie de recurenţă termenii X0 , X -1 , X -2 , … dacă impunem condiţia suplimentară D≠0 . Într-adevăr :

n=1 implică X1+1=SX1 – DX0 adică S= S∙1 – D∙X0 de unde rezultă X0=0 deoarece D≠0 .
n=0 implică X0+1=SX0 – DX0-1adică 1=S∙0 - D∙X -1  de unde rezultă  deoarece D≠0.
n= -1implică X -1+1=SX -1 – DX -1-1  adică    deoarece D≠0.

   În general   .

Definiţia 2 :Fie      , S=a+d  ,   D=ad-bc  ,      ;  a,b,c,d C ; definim şirul de matrici :          An+1=def=Xn+1A- XnD I    n≥1 ;     (R II.2)    

    Dacă D≠0  atunci   An+1=def=Xn+1A- XnD I    Z       (R’II.2)   este un şir de matrici definit pentru orice întreg n (vezi obs.2 din def1).
                     Aici şirul Xn este cel din  Definiţia 1.

Vom demonstra ca An+1=An+1  în 2 etape : n≥1 si n≤0

Teorema 1 : An+1=An+1  pentru orice n≥1.
Demonstraţia o facem prin inducţie :
n=1 ; trebuie arătat că A2=A2 ;dar A2= A1+1=def2= X1+1A- X1D I=def1=SA-1∙D I =(R I.1)=A2

Presupunem că Ak+1=Ak+1 , unde k≥1  e fixat ; atunci  :
        
         Ak+2=Ak+1 A =Ak+1 A=def2= (Xk+1 A – Xk D I ) A = Xk+1 A2 – Xk D I A=(R I.1)=           
                              =Xk+1 (S A – D I) – Xk D A = (S Xk+1 – D Xk) A – Xk+1 D I =def1=
                   =Xk+2 A – Xk+1 D I=def2= Ak+2.
 Rezultă :Ak+2=Ak+2  şi demonstraţia este completă. Deci:
                  An+1=An+1=Xn+1A- XnD I , n≥1.       (R II.3)
Vom extinde teorema1 şi pentru exponenţi întregi negativi:

Teorema 2 : Dacă D≠0 atunci An+1=An+1  pentru orice întreg n.

Demonstraţia o facem prin inducţie descendentă pentru toate valorile întregi  n≤0 deoarece pentru n≥1 este deja făcută. Conform obs.2 din def1, Xn este definit şi pentru orice număr n≤0 deoarece D≠0. Reţinem valorile deja determinate:
 

Dacă n=0 atunci A1= A0+1=def2=X0+1A- X0D I=1∙A- 0∙D I=A=A1. Deci A1=A1.
Dacă n= -1 atunci A0=A -1+1=def2=X -1+1A- X -1D I= =I=A0 . Deci A0=A0
   Fie n= -2.
Deoarece det A=D≠0 există A-1.Atunci din relaţia A2=SA-DI  prin înmulţirea ei cu A-1 obţinem A=S I – DA-1 de unde rezultă că
                                       
Dar A -1=A -2+1=def2= X -2+1A- X -2D I=X -1A- X -2D I=
                          ; rezultă:

                                   (R II.4)
Presupunem Ak+1=Ak+1  unde k≤-2 este fixat.

Atunci Ak=A-1Ak+1=A-1Ak+1=(R II.4),def2=    
   
              Deci din Ak+1=Ak+1  rezultă Ak=Ak . Inducţia descendentă este probată şi teorema 2 este demonstrată.Deci :
             
 An+1=An+1=Xn+1A- XnD I oricare ar fi n Z , dar cu condiţia D≠0.  (R II.5)

TREBUIE REŢINUTǍ CONCLUZIA:
            Dacă      , S=a+d  ,   D=ad-bc , atunci rezultă că :
1)    An+1=Xn+1A - XnD I  pentru orice n≥1 , unde şirul Xn este definit de relaţia           
      Xn+1=SXn – DXn-1    cu valorile iniţiale X1=1 şi X2=S .
2)    Dacă D≠0 relaţia An+1=Xn+1A- XnD I  este valabilă pentru orice număr întreg n .
      Facem  precizarea că şirul Xn este definit acum pentru orice număr întreg n cu   
      aceeaşi relaţie  Xn+1=SXn – DXn-1   şi valorile iniţiale X1=1 şi X2=S.



III   STUDIUL ŞIRULUI Xn ŞI CÂTEVA APLICAŢII


٭Să vedem ce se întâmplă cu şirul Xn+1=SXn – DXn-1 dacă ecuaţia   are rădăcinile p şi q egale :
Teorema 1 : Dacă rădăcinile ecuaţiei   sunt egale (q=p≠0) atunci soluţia recurenţei Xn+1=SXn – DXn-1  este şirul Xn=nqn-1 , n≥1.

Demonstraţie:   Avem relaţiile S=2q şi D=q2 . Atunci rezultă că:
                         SXn – DXn-1=2q∙ nqn-1- q2∙(n-1)qn-2=(n+1)qn=Xn+1 .
                         În plus avem îndeplinite condiţiile iniţiale X1=1q1-1=1 şi  X2=2q2-1=2q=S .

Consecinţă : An+1=Xn+1A- XnD I=(n+1)qnA- nqn-1q2 I=qn[(n+1)A- nqI ] . Relaţia este valabilă şi pentru n≤0 deoarece D=q2≠0.

Exemplu:   , S=2 , D=1 ; ecuaţia  are soluţiile p=q=1 . Rezultă că
An+1= 1n[(n+1)∙A- n∙1∙I ]=  ; deoarece D=1≠0 putem considera valoarea   n= -2 ; atunci  obţinem :   .
٭Acum considerăm un exemplu în care S=0 . Fie   . Avem S=0 şi D=5.
Din Xn+1=SXn – DXn-1 rezultă :
Xn+1=0∙Xn – 5∙Xn -1 adică Xn+1= -5Xn -1 ; deoarece X1=1 şi X2=S=0 rezultă
X2k=0  şi X2k+1=(-5)k ; atunci  avem următoarele relaţii ce rezultă din (R II.5) :

A2k+1=X2k+1A- X2k5 I=(-5)kA    şi   A2k=X2kA- X2k -1∙ 5∙ I=(-5)kI  ,

ceea ce se poate scrie condensat astfel:
 

Relaţia este valabilă şi pentru n≤1 deoarece D≠0.
Generalizarea cazului S=0 este imediată şi o lăsăm pe seama cititorului.
٭Considerăm şi un exemplu în care D=0 . Fie   . Avem S=8 şi D=0.
Din Xn+1=SXn – DXn-1 rezultă Xn+1=8∙Xn – 0∙Xn-1 . Rezultă Xn+1=8n iar An+1=Xn+1A- XnD I implică      An+1=8n ∙A- 8n-1∙0∙ I=8n∙A.
Generalizarea cazului D=0 este imediată şi o lăsăm pe seama cititorului.
    
٭Dacă S=D=0 atunci din identitatea A2=SA-DI rezultă A2=0. Atunci dacă n≥3 rezultă
              An=A2∙An-2=0∙An-2=0
1 Din Xn+1=SXn – DXn-1 rezultă o formulă combinatorială pentru Xn+1 dacă observăm şi generalizăm următoarele relaţii :
X1=1
X2=S
X3=SX2- DX1=S2- D
X4=SX3- DX2=S3- 2SD
X5=SX4- DX3=S4- 3S2D+D2
X6=SX5- DX4=S5- 4S3D+3SD2
X7=SX6- DX5=S6- 5S4D+6S2D2- D3
X8=SX7- DX6=S7- 6S5D+10S3D2- 4SD3

Dacă citim triunghiul lui Pascal pe diagonală de jos în sus şi de la stânga la dreapta în sensul indicat de puncte vedem chiar coeficienţii dezvoltării lui Xn+1 :

 
De aceea putem presupune că termenul Sn-2iDi din dezvoltarea lui Xn+1
are coeficientul  . Intuiţia nu ne înşeală pentru că se poate demonstra :

Teorema 2 :
 Şirul Xn+1 din capitolul II Definiţia 1 în cazul n≥0 admite reprezentarea următoare :
 
                     Notăm relaţia de mai sus cu (R III.1).

Demonstraţie:
Se verifică faptul că şirul    satisface relaţia de recurenţă
Xn+1=SXn – DXn-1 şi că are aceeaşi termeni iniţiali X1=1 şi X2=S .  Verificarea recurenţei se face analizând cazurile când n este par şi când n este impar deoarece trebuie explicitată limita de sumare   =partea întreagă a numarului   .








    
٭Aplicaţia 1 .
Să se determine o matrice pătrată de ordin 2 , A , astfel încât şirul de matrici An+1 să fie periodic de perioadă n=3 .
Rezolvare : Fie   . Avem S= -1 şi D=1. Ecuaţia   are soluţiile
  şi   ; atunci folosind formula lui Moivre rezultă că

   este un şir periodic de perioadă n=3; rezultă din (R II.5) că
şi An+1=Xn+1A- Xn∙1∙ I este şir periodic de perioadă 3 ; avem că A3=X3A- X2I=0A- (-1)I=I ;
de aceea   A3k=I ; A3k+1=A ; A3k+2=A2.

De asemenea relaţia (R III.1) din teorema 2 implică
  ; de aici rezultă prin înmulţire cu (-1)n identitatea remarcabilă :

     , n≥0

٭Aplicaţia 2.    
Să se determine o matrice pătrată de ordin 2 , A , astfel încât şirul de matrici An+1 să fie periodic de perioadă n=10 .
Rezolvare: Fie  ;avem  şi D=1
iar ecuaţia   are soluţiile   şi  .
Rezultă folosind din nou formula lui Moivre că   ; aceasta ne arată că şirul Xn+1 este periodic de perioadă n=10 ; rezultă din (R II.5) că şi
An+1=Xn+1A- Xn∙1∙ I este şir periodic de perioadă n=10.Se verifică uşor că X10=0 şi X9= -1 ; atunci A10= X10A- X9∙1∙ I= 0∙A- (-1)∙1∙ I =I . De aceea  A10k+j=Aj unde 0≤j≤9 .
     



Relaţia (R III.1) din teorema 2 conduce la identitatea:
                      ,  n≥0         (R III.2)
    ٭Aplicaţia 3 .
Aici vom demonstra câteva proprietăţi ale şirului lui Fibonaci.
Şirul numerelor lui Fibonaci este definit de recurenţa Fn+1=Fn+Fn-1
şi de valorile iniţiale F1=F2=1 ; avem în tabelul de mai jos primii 18 termeni :
F1    F2    F3    F4    F5    F6    F7    F8    F9    F10    F11    F12    F13    F14    F15    F16    F17    F18
1    1    2    3    5    8    13    21    34    55    89    144    233    377    610    987    1597    2584

٭Considerăm matricea   ; vrem să calculăm An+1 cu relaţia An+1=Xn+1A- XnD I .
Avem S=1 , D= -1 ; relaţia Xn+1=SXn – DXn-1 devine Xn+1=Xn +Xn-1 , valorile iniţiale fiind
X1=1 şi X2=S=1 ; de aici rezultă că Xn+1=Fn+1 .
Atunci relaţia  (R II.5) devine :
An+1=Fn+1A- Fn(-1)I= ;(am utilizat relaţiaFn+2=Fn+1+Fn)  Ultima relaţie se mai poate scrie :
  ;

٭Deoarece det (An)=(det A)n obţinem relaţia :
 

٭Din An+m=An∙Am obţinem :
  ; de aici se pot deduce patru identităţi a căror scriere o lăsăm pe seama cititorului.

٭Relaţia (R III.1) devine :
  ; de aici deducem identitatea remarcabilă :

              n≥0           (R III.3)

٭Rădăcinile ecuaţiei   sunt   de unde rezultă că recurenţa Fn+1=Fn+Fn-1  cu condiţiile iniţiale F1=F2=1 este verificată de şirul
  ; de aici rezultă că

  ;


De aceea în relaţia (R III.2)     este interesant să vedem

ce obţinem dacă facem  înlocuirea          .

 Prin înlocuire obţinem şirul         .

Am calculat cu ajutorul unui calculator de buzunar primele 18 valori ale acestui şir :

Y1    Y2    Y3    Y4    Y5    Y6    Y7    Y8    Y9    Y10    Y11    Y12    Y13    Y14    Y15    Y16    Y17    Y18
0    1    1    0    0    0    -1    -1    0    0    0    1    1    0    0    0    -1    -1

În calcule am folosit valoarea F0=0.
Analizând aceste valori intuim că şirul Yn+1 este mărginit , ia doar valorile -1 , 0 , 1 şi este chiar periodic ( perioada este probabil n=10 ) .
Nu am demonstrat deocamdată nici una din aceste afirmaţii.
Propunem aceste probleme cititorului . (Sugerăm să folosim relaţia (R III.3) ; astfel reducem  totul la o problemă de combinări ) .
 
Aplicaţia 4 .
Vom prezenta în continuare fără detalii un sistem criptografic .
٭Chestiuni preliminare :
Considerăm aici că matricea A are elemente din corpul Zp , unde p este un număr prim mare.
Menţinem def 1 şi def 2 din cap. II ; în aceste condiţii au loc teoremele 1 şi 2 din cap. II adică
An+1=Xn+1A- XnD I    (R III.4)
٭Ideea de bază a cripto-sistemului :
-introducem textul pe care vrem să-l criptăm în elementele lui A sub formă binară
 (de exemplu fiecare caracter al textului poate fi reprezentat pe un octet iar câteva caractere alăturate formează un număr pe care îl atribuim elementului « a » al matricii A , etc. ) .
-criptarea matricii A constă în calcularea unei puteri An+1 ; An+1 reprezintă textul deja criptat sau criptotextul.
-cheia de decriptare este formată din perechea de numere (Xn+1, XnD)
    Cel care obţine în mod fraudulos criptotextul An+1, trebuie să-l ghicească pe A
(ştiindu-l doar pe An+1) , ca să ajungă la textul iniţial . Aceasta este extrem de improbabil fiindcă nu deţine cheia (Xn+1, XnD).
    Pentru cel care deţine cheia este foarte simplu să-l obţină pe A din (R III.4) :

A=(Xn+1)-1(An+1+XnD I)

٭Dacă avem de criptat un volum mare de date procedăm astfel :
    Presupunem că avem mai multe « sertare » fiecare cu cheia lui ; ca să nu purtăm după noi toate cheile încuiem în « sertarul 2 » cheia de la « sertarul 1 » , apoi încuiem în « sertarul 3 » cheia de la « sertarul 2 » şi aşa mai departe ; noi nu trebuie să păstrăm decât cheia de la ultimul « sertar ».
Sertarele conţin evident şi informatia pe care vrem să o protejăm.
    
Sertarele sunt un şir de matrici de forma :
                                   
Textul se introduce în elementele ai şi di iar cheia pentru decriptare a matricii precedente se introduce în elementele bi şi ci ; după aceste operaţiuni se criptează matricea A(i) iar cheia ei de decriptare se va introduce în matricea următoare A(i+1).
    ٭Trebuie evitate cazurile S=0 , D=0 , S2=4D deoarece atunci decriptarea poate deveni uşoară chiar fără cunoaşterea cheii ; de aceea vom folosi un caracter special w de un octet care nu are nici o semnificaţie în text dar prin introducerea căruia se modifică valoarea numerică a elementelor ai şi di până când obţinem îndeplinirea celor trei condiţii S≠0 , D≠0 , S2≠4D.
    ٭Toate calculele se fac modulo p ; de aceea numărul de caractere care formează elementele ai şi di este limitat de mărimea numărului prim p.
    ٭Putem oricând să adăugăm la text o continuare : caracterele noi vor fi introduse în matrici noi ;avantajul evident este că lungimea cheii ultimei matrici adăugate nu depinde deloc de lungimea textului pe care l-am criptat .
    ٭Numărul prim p trebuie să fie suficient de mare încât să descurajeze tentativa de a încerca toate cheile posibile.


Nota : Am utilizat o idee din cartea lui Isaac J. Shoenberg   « Privelisti matematice » ,
 Editura Tehnica -1989
Referat oferit de www.ReferateOk.ro
Home : Despre Noi : Contact : Parteneri  
Horoscop
Copyright(c) 2008 - 2012 Referate Ok
referate, referat, referate romana, referate istorie, referate franceza, referat romana, referate engleza, fizica