Matrici patrate de ordin 2 Categoria: Referat Marketing
Descriere: Î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 ... |
|
||
|
|
|||
|
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 Prof. VELCSOV GHEORGHE IOAN |
|||
| Referat oferit de www.ReferateOk.ro | |||
Varianta Printabila 
Free Download Referat PDF
Free Download Referat Word |
Home : Despre Noi : Contact : Parteneri |  |
