Luận văn Ma trận và hệ truy hồi

Nội dung tài liệu: Luận văn Ma trận và hệ truy hồi

1. ĐẠI HÅC QUẩC GIA HÀ NậI TRƯỜNG ĐẠI HÅC KHOA HÅC TỰ NHIấN ———————o0o——————– NGặ THỊ HƯỜNG MA TRẬN VÀ HỆ TRUY HầI LUẬN VĂN THẠC SĨ TOÁN HÅC Chuyản ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP MÂ số: 60 46 01 13 Người hướng dăn khoa học PGS.TS ĐÀM VĂN NHỈ HÀ NậI - 2014
2. Mục lục Lời núi đầu ................................2 Lời cÊm ơn ................................4 1 Mởt số kián thực vã ma trên 5 1.1 KhĂi niằm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5 1.2 CĂc ph²p toĂn ma trên . . . . . . . . . . . . . . . . . . . . . . .6 1.2.1 Ph²p cởng hai ma trên . . . . . . . . . . . . . . . . . . .6 1.2.2 Ph²p nhƠn cĂc phƯn tỷ trường K với ma trên . . . . .6 1.2.3 Ph²p nhƠn hai ma trên . . . . . . . . . . . . . . . . . .6 1.3 Vành ma trên . . . . . . . . . . . . . . . . . . . . . . . . . . . .7 1.4 Ma trên nghịch đÊo . . . . . . . . . . . . . . . . . . . . . . . . .9 1.5 Phương trẳnh đặc trưng cừa ma trên . . . . . . . . . . . . . . . 10 1.5.1 GiĂ trị riảng và vectơ riảng cừa ph²p bián đổi tuyán tẵnh 10 1.5.2 Đa thực đặc trưng . . . . . . . . . . . . . . . . . . . . . 11 1.6 Ch²o húa ma trên . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.7 GiĂ trị riảng cừa hàm ma trên . . . . . . . . . . . . . . . . . . . 16 2 Ma trên và hằ truy hồi 20 2.1 X²t dÂy số qua ph²p nhƠn ma trên . . . . . . . . . . . . . . . . 20 2.2 Ứng dụng định lẵ Cayley - Hamilton vào dÂy số . . . . . . . . . 27 2.3 X²t dÂy số qua ch²o húa ma trên . . . . . . . . . . . . . . . . . 31 3 XƠy dựng bài toĂn mới cho dÂy số 46 3.1 Đặt vĐn đề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.2 XƠy dựng bài toĂn mới vã dÂy số . . . . . . . . . . . . . . . . . 47 4 Mởt số phương phĂp khĂc giÊi hằ truy hồi 53 4.1 Hằ truy hồi qua cĐp số nhƠn . . . . . . . . . . . . . . . . . . . . 53 4.1.1 Phương phĂp cĐp số nhƠn để x²t dÂy số . . . . . . . . . 53 4.1.2 Chuyºn dÂy truy hồi phực tÔp vã dÂy đơn giÊn . . . . . 62 4.2 X²t dÂy số qua đồng cĐu . . . . . . . . . . . . . . . . . . . . . . 69 Kát luên .................................. 74 Tài liằu tham khÊo ........................... 75 1
3. Ma trên và hằ truy hồi LÍI NÂI ĐẦU CĂc vĐn đề liản quan đến dÂy số là mởt bở phên quan trọng cừa giÊi tẵch và đại số, đặc biằt là mởt phƯn quan trọng khụng thº thiáu trong toĂn học phờ thụng. Nhiãu dÔng toĂn cừa hẳnh học, lượng giĂc và nhiãu mụn học khĂc cũng đũi hỏi giÊi quyát cĂc vĐn đề vã dÂy số...CĂc học sinh và sinh viản cũng thường xuyản phÊi đối mặt với nhiãu bài toĂn khú liản quan đến dÂy số. CĂc bài toĂn liản quan đến dÂy số rĐt phong phỳ và đa dÔng, thường gặp trong cĂc kẳ thi học sinh giỏi toĂn cĐp quốc gia, khu vực, quốc tá và cĂc kẳ Olympic. Trong khuụn khờ luên vôn này, tĂc giÊ ch¿ đề cêp đán mởt phƯn nhỏ cừa lý thuyát dÂy số là cĂc dÂy và hằ cĂc dÂy dÔng truy hồi tuyán tẵnh. Mởt hằ truy hồi dự tuyán tẵnh, nhưng để giÊi được nú bơng cĂc bước bián đổi sơ cĐp là rĐt phực tÔp, thêm chẵ đưa bài toĂn vã viằc giÊi mởt phương trẳnh bêc cao khụng đơn giÊn. Bơng viằc biºu diạn mởt hằ truy hồi tuyán tẵnh dưới dÔng phương trẳnh ma trên, ta đó làm đơn giÊn húa đỏng kº bài toĂn, đưa đến viằc tẵnh toĂn trản cĂc ma trên. Luên vôn này tĂc giÊ cũng nhơm đỏp ựng nhu cƯu tự bồi dưỡng, học cĂch lý luên, cĂch mở rởng tự nhiản cừa mởt vĐn đề tứ đơn giÊn đến phực tÔp, để tứ đú hiºu và ựng dụng được mởt vĐn đề sƠu sưc, mÔch lÔc và cú trẳnh tự hơn. Bố cục cừa luên vôn gồm bốn chương: - Chương 1: Mởt số kián thực vã ma trên. Nởi dung cừa chương này là nhưc lÔi mởt số kián thực vã ma trên: KhĂi niằm, cĂc ph²p toĂn ma trên, vành ma trên, ma trên nghịch đảo, giĂ trị riảng và vectơ riảng cừa ma trên; hàm ma trên và giĂ trị riảng cừa hàm ma trên. - Chương 2: Ma trên và hằ truy hồi. Trong chương này, luên vôn đề cêp đến viằc biºu diạn mởt hằ truy hồi tuyán tẵnh dưới dÔng ma trên, và sỷ dụng cĂc ph²p bián đổi ma trên để giÊi toĂn. Luên vôn cũng đề cêp thảm đến cĂc hằ thực truy hồi phi tuyán ma khụng thº dựng ma trên để giÊi. - Chương 3: XƠy dựng bài toĂn mới cho dÂy số. Chương này, luên vôn đề cêp đến viằc xƠy dựng bài toĂn mới vã dÂy số tứ cĂc bài toĂn đó 2
4. Ma trên và hằ truy hồi biát nhờ cĂc kián thực cừa hàm ma trên. - Chương 4: Mởt số phương phĂp khĂc giÊi hằ truy hồi. PhƯn này, luên vôn đề cêp đến hai phương phĂp: giÊi hằ truy hồi qua cĐp số nhƠn và x²t dÂy số qua đồng cĐu. 3
5. Ma trên và hằ truy hồi LÍI CẢM ƠN TĂc giÊ xin bày tỏ sự kẵnh trọng và lỏng biát ơn sƠu sưc đến PGS.TS Đàm Vôn Nh¿. ThƯy đó giành nhiãu thời gian hướng dăn cũng như giÊi đỏp cĂc thưc mưc giỳp đỡ tĂc giÊ hoàn thành luên vôn này. TĂc giÊ cũng xin gỷi lời cÊm ơn chƠn thành đến cĂc thƯy, cụ giĂo trong khoa ToĂn - Cơ - Tin học, cựng cĂc bÔn học viản đó nhên x²t và đúng gúp ý kián cho bÊn luên vôn. TĂc giÊ xin cÊm ơn gia đỡnh, bÔn b± đó luụn quan tƠm, đụng viản và cờ vũ tÔo diãu kiằn thuên lủi cho tĂc giÊ hoàn thành luên vôn. Hà Nởi, thĂng 5 nôm 2014 4
6. Chương 1 Mởt số kián thực vã ma trên 1.1 KhĂi niằm GiÊ sỷ X là mởt têp, m và n là cĂc số nguyản dương. Ma trên A cỡ m ì n với cĂc phƯn tỷ thuởc têp X là mởt họ m ì n phƯn tỷ aij 2 X; trong đú i = 1; 2; :::; m gọi là ch¿ số hàng; j = 1; 2; :::; n gọi là ch¿ số cởt. Ma trên A thường được ký hiằu 0 a11 a12 : : : a1n 1 a21 a22 : : : a2n A = B . . . C @ . . ::: . A am1 am2 : : : amn hay được viát gọn dưới dÔng A = (aij)mìn. Ma trên cỡ 1 ì n gọi là ma trên hàng, ma trên cỡ m ì 1 gọi là ma trên cởt. Ma trên cỡ n ì n gọi là ma trên vuụng cĐp n hay ma trên cĐp n. Trong ma trên vuụng A = (aij)nìn dÂy cĂc phƯn tỷ a11; a22; :::; ann gọi là đường ch²o chẵnh cừa ma trên A. Ma trên đơn vị là ma trên vuụng cú cĂc phƯn tỷ trản đường ch²o chẵnh bơng 1, cỏn cĂc phƯn tỷ ngoài đường ch²o chẵnh đều bơng 0. Ma trên đơn vị thường được ký hiằu là E. 0 1 0 ::: 0 1 0 1 ::: 0 E = B C @::::::::::::A 0 0 ::: 1 0 0 Ma trên chuyºn vị cừa ma trên A = (aij)mìn là ma trên A = (aij)mìn trong 0 đú aij = aij với mọi i = 1,2,..,m và j=1,2,...,n. 5
7. Ma trên và hằ truy hồi Ma trên chuyºn vị At nhên đưủc tứ ma trên A bơng cĂch chuyºn cởt thành hàng và chuyºn hàng thành cởt. t Ma trên vuụng A = (aij)nìn gọi là ma trên đối xựng náu A = A, tực là aij = aji với mọi i = 1,2,..,m và j=1,2,...,n. 1.2 CĂc ph²p toĂn ma trên Cho K là mởt trường, Ký hiằu têp Mmìn[K] là têp cĂc ma trên cỡ m ì n với cĂc phƯn tỷ thuởc trường K. Trong têp Mmìn[K] ta định nghĩa cĂc ph²p toĂn sau 1.2.1 Ph²p cởng hai ma trên GiÊ sỷ hai ma trên A = (aij)mìn;B = (bij)mìn, ta định nghĩa A + B = (aij + bij)mìn 1.2.2 Ph²p nhƠn cĂc phƯn tỷ trường K với ma trên GiÊ sỷ λ 2 K; A = (aij)mìn, ta định nghĩa λA = (λaij)mìn 1.2.3 Ph²p nhƠn hai ma trên Cho hai ma trên A = (aij)mìn;B = (bij)nìl, ta định nghĩa tẵch hai ma trên A và B là ma trên C = AB = (cij)mìl Pn trong đú cij = k=1 aikbkj. Như vêy tich hai ma trên AB tồn tÔi khi và ch¿ khi số cởt cừa ma trên A bơng số hàng cừa ma trên B. Đối với cĂc ma trên cú cỡ thẵch hủp, ta dạ dàng chựng minh được cĂc tẵnh chĐt sau • A + B = B + A. • λ(A + B) = λA + λB. • A + O = A (O là ma trên khụng). 6
8. Ma trên và hằ truy hồi • OA=O, AO = O. • A(B+C) = AB + AC, (B+C)A = BA + CA. • (AB)C = A(BC). • (At)t = A, kẵ hiằu At là ma trên chuyºn vị cừa A. • (A + B)t = At + Bt. • (AB)t = BtAt. • AE = EA = A; ArE = EAr = Ar. • ArAs = AsAr = Ar+s. • Ar(αAs + βAp) = αAr+s + βAr+p với α; β 2 K Ký hiằu Mn[K] là têp cĂc ma trên vuụng cĐp n với cĂc phƯn tỷ thuởc trường K. Tứ cĂc tẵnh chĐt trản ta thĐy Mn[K] với ph²p cởng và ph²p nhƠn ma trên là mởt vành cú đơn vị E, được gọi là vành cĂc ma trên vuụng cĐp n trản trường K. Với n ≥ 2 thẳ vành Mn[K] khụng giao hoĂn. 1.3 Vành ma trên X²t vành đa thực mởt bián K[x] trản trường K. GiÊ sỷ đa thực f(x) thuởc s s−1 vành K[x] cú dÔng f(x) = asx + as−1x + ::: + a1x + a0, và cho A là ma trên vuụng cĐp n. Ta định nghĩa s s−1 f(A) = asA + as−1A + ::: + a1A + a0E trong đú E là ma trên đơn vị cựng cĐp với ma trên vuụng A. Tứ cĂc ph²p toĂn vã ma trên ở trản ta suy ra đưủc cĂc kát quÊ sau Định lý 1.3.1. Với hai đa thực f và g thuởc vành đa thực K[x] và ma trên vuụng A ta luụn cú 1. Náu f = g thẳ f(A) = g(A). 2. (f+g)(A) = f(A)+g(A). 3. (fg)(A) = f(A)g(A) = g(A)f(A) = (gf)(A). 4. (αf)(A) = αf(A) với α bĐt kẳ thuởc trường K. 7
9. Ma trên và hằ truy hồi Ký hiằu K[A] = f(A)jf 2 K[x];A 2 Mn[K]. Tứ định lẵ (1.3.1) ta suy ra kát quÊ sau Định lý 1.3.2. Têp cĂc ma trên K[A] tương ựng với hàm f 2 K[x] cựng với ph²p cởng, nhƠn cĂc ma trên và nhƠn ma trên với mởt sụ lêp thành mởt vành giao hoĂn cú đơn vị E. Mằnh đề 1.3.1. Tương ựng φ : K[x] ! K[A]; f(x) 7! f(A) là mởt toàn cĐu với Ker(φ) 6= 0 Chựng minh. Theo định lẵ (1.3.1), ta cú φ(f + g) = (f + g)(A) = f(A) + g(A) = φ(f) + φ(g) φ(fg) = (fg)(A) = f(A)g(A) = φ(f)φ(g): Do đú φ là mởt đồng cĐu. s s−1 Và với ma trên vuụng A 2 Mn[K] bĐt kẳ thẳ ma trên f(A) = asA + as−1A + s s−1 :::+a1A+a0E s³ cú tương ựng đa thực f(x) = asx +as−1x +:::+a1x+a0 2 K[x] để φ(f) = f(A). Do vêy φ là mởt toàn cĐu. Vẳ têp tĐt cÊ cĂc ma trên vuụng cĐp n Mn[K] trản trường K là mởt khụng gian vectơ n2 chiãu nản tĐt cÊ cĂc têp cú nhiãu hơn n2 cĂc ma trên vuụng cĐp n đều phụ thuởc tuyán tẵnh. Như vêy mụt hằ gồm s + 1 cĂc ma trên As;As−1; :::; A; E với s ≥ n2 + 1 là mởt hằ phụ thuởc tuyán tẵnh. Tực là tồn tÔi cĂc số as; as−1; :::; s1; s0 khụng đồng thời bơng 0 để s s−1 asA + as−1A + ::: + a1A + a0E = 0: s s−1 Vêy tồn tÔi đa thực khĂc khụng f(x) = asx + as−1x + ::: + a1x + a0 với s ≥ n2 + 1 mà f(A) = 0. Tứ đú suy ra Ker(φ) 6= 0. Hằ quÊ 1.3.1. Ta cú K[A] ∼= K[x]=(F ) Chựng minh. Vẳ φ : K[x] ! K[A]; f(x) 7! f(A) là mởt toàn cĐu với Ker(φ) = (F ) 6= 0 nản ta cú K[A] ∼= K[x]=Ker(φ) = K[x]=(F ) Vẳ K[x] là vành cĂc iđờan chẵnh nản cú duy nhĐt mởt đa thực bêc thĐp d d−1 nhĐt m(x) = x + a1x + ::: + ad 2 K[x] để Ker(φ) = (m(x)). m(x) gọi là đa thực tối thiºu cừa ma trên A. 8
10. Ma trên và hằ truy hồi 1.4 Ma trên nghịch đảo Định nghĩa 1.4.1. Ma trên vuụng B cĐp n được gọi là ma trên nghịch đảo cừa ma trên vuụng A cĐp n náu AB = BA = E. Ma trên nghịch đảo B thường được ký hiằu là A−1. Khi đú A gọi là ma trên khÊ nghịch. GiÊ sỷ ma trên vuụng A = (aij)nìn, gọi Mij là định thực con cĐp n - 1 cừa i+j ma trên A sau khi đó bỏ đi hàng i và cởt j. khi đú Aij = (−1) :Mij được gọi là phƯn bự đại số cừa phƯn tỷ aij cừa ma trên A. X²t ma trên 0 1 A11 A21 ::: An1 A A ::: A A∗ = B 12 22 n2C @ ::: ::: ::: ::: A A1n A2n ::: Ann Ma trên A∗ gọi là ma trên phụ hủp cừa ma trên A. Dạ thĐy n X cij = Akiakj = δjAj: k=1 Do đú A∗A = AA∗ = jAjE: Vêy náu ma trên A khÊ nghịch thẳ ma trên nghịch đảo A−1 được tẵnh theo cụng thực 1 A−1 = A∗: jAj Bờ đề 1.4.1. Ma trên vuụng A cú nghịch đảo A−1 khi và ch¿ khi jAj 6= 0 Chựng minh. GiÊ sỷ A cú ma trên nghịch đảo A−1 thẳ AA−1 = E. Khi đú 1 = jEj = jAA−1j = jAjjA−1j Vêy jAj= 6 0 1 Ngược lÔi náu jAj 6= 0 thẳ A khÊ nghịch và A−1 = A∗. jAj Ch¯ng hÔn, ta x²t ma trên thực 1 2 0! A = 0 3 1 0 1 2 9