Матричный анализ. Поле комплексных чисел. Кольцо полиномов

Ìàòåðèàëû ê êóðñó Àëãåáðà Ä.Â. Ãðîìîâ 28 ÿíâàðÿ 2020 ã. Îãëàâëåíèå 1 Ñèñòåìû ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé. Îñíîâû ìàòðè÷íîãî àíàëèçà 4 1.1 Ïðèìåðû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Îïðåäåëåíèÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.3 Ìåòîä Ãàóññà ðåøåíèÿ ÑËÀÓ 1.4 Ìàòðèöû è îïåðàöèè íàä íèìè 1.5 1.6 . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 8 1.4.1 Îïåðàöèè íàä ìàòðèöàìè . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.4.2 Îñíîâíûå ñâîéñòâà îïåðàöèé íàä ìàòðèöàìè . . . . . . . . . . . . . . . 12 1.4.3 Ìàòðèöû ñïåöèàëüíîãî âèäà . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.4.4 Îáðàòíûå ìàòðèöû . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.5.1 LU/LUP-ðàçëîæåíèå Ïðåäñòàâëåíèå ÑËÀÓ â âåêòîðíî-ìàòðè÷íîì âèäå . . . . . . . . . . . . 19 1.5.2 Ìàòðèöû ýëåìåíòàðíûõ îïåðàöèé . . . . . . . . . . . . . . . . . . . . . 21 1.5.3 LU-ðàçëîæåíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.5.4 Ìàòðèöû ïåðåñòàíîâîê . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.5.5 LUP-ðàçëîæåíèå . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 LU(P)-ðàçëîæåíèå êâàäðàòíûõ ìàòðèö è åãî ïðèìåíåíèå 1.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6.1 Ñóùåñòâîâàíèå îáðàòíîé ìàòðèöû 1.6.2 Ðåøåíèå ÑËÀÓ 1.6.3 Ìåòîä Ãàóññà-Éîðäàíà 27 . . . . . . . . . . . . . . . . . . . . . 28 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Îïðåäåëèòåëü. Íàõîæäåíèå îáðàòíîé ìàòðèöû . . . . . . . . . . . . . . . . . . 30 1.7.1 Àêñèîìàòè÷åñêîå îïðåäåëåíèå îïðåäåëèòåëÿ. Ñâîéñòâà îïðåäåëèòåëÿ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 1.7.2 Ïåðåñòàíîâêè, èõ ñâîéñòâà . . . . . . . . . . . . . . . . . . . . . . . . . . 34 1.7.3 Ñèãíàòóðíàÿ ôîðìóëà Ëåéáíèöà 36 . . . . . . . . . . . . . . . . . . . . . . 2 Ïîëå êîìïëåêñíûõ ÷èñåë 38 3 Êîëüöî ïîëèíîìîâ 39 3.1 Êîëüöî 3.2 Ïîëèíîìû 3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 40 3.2.1 Äåëèìîñòü ïîëèíîìîâ 3.2.2 Íàèáîëüøèé îáùèé äåëèòåëü . . . . . . . . . . . . . . . . . . . . . . . . 43 3.2.3 Âçàèìíî ïðîñòûå ïîëèíîìû . . . . . . . . . . . . . . . . . . . . . . . . . 45 Öåëûå ðàöèîíàëüíûå (ïîëèíîìèàëüíûå) ôóíêöèè . . . . . . . . . . . . . . . . 46 3.3.1 47 Êîðíè ïîëèíîìà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 42 3.3.2 Îñíîâíàÿ òåîðåìà àëãåáðû . . . . . . . . . . . . . . . . . . . . . . . . . . Ëèòåðàòóðà 49 53 2 Ïðåäñòàâëåííûå íèæå ìàòåðèàëû íå ÿâëÿþòñÿ çàìåíîé ëåêöèÿì, à ñîäåðæàò ñâå- äåíèÿ/ çàäàíèÿ, ïðåäíàçíà÷åííûå äëÿ ëó÷øåãî óñâîåíèÿ ëåêöèîííîãî êóðñà! 3 Ãëàâà 1 Ñèñòåìû ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé. Îñíîâû ìàòðè÷íîãî àíàëèçà 1.1 Ïðèìåðû 1.2 Îïðåäåëåíèÿ Óñëîâèìñÿ, ÷òî ÷èñåë), R F áóäåò îáîçíà÷àòü îäíî èç òðåõ ìíîæåñòâ: (ìíîæåñòâî âåùåñòâåííûõ ÷èñåë), èëè C äàëüíåéøåì ìû áóäåì ïîëàãàòü äëÿ îïðåäåëåííîñòè, ÷òî Îïðåäåëåíèå 1.2.1. Q (ìíîæåñòâî ðàöèîíàëüíûõ (ìíîæåñòâî âñåõ êîìïëåêñíûõ ÷èñåë).  F = R. Óðàâíåíèå âèäà a1 x1 + a2 x2 + . . . an xn = b, ai ∈ F, i = 1, . . . , n, b∈F (1.1) ëèíåéíûì àëãåáðàè÷åñêèì óðàâíåíèåì íàä (ïîëåì1 ) F ñ n íåèçâåñòíûìè (ïåðåìåííûìè) (x1 , x2 , . . . xn ). ×èñëà ai íàçûâàþòñÿ êîýôôèöèåíòàìè, à b  ñâîáîäíûì ÷ëåíîì. Ðåøåíèåì óðàâíåíèÿ (1.1) íàçûâàåòñÿ ëþáîé íàáîð ÷èñåë (γ1 , γ2 , . . . , γn ) èç F , êîòîðûå, íàçûâàåòñÿ áóäó÷è ïîäñòàâëåííûìè â óðàâíåíèå (1.1), îáðàùàþò åãî â ðàâåíñòâî: a1 γ1 + a2 γ2 + . . . an γn = b. Íàáîð èç óðàâíåíèé m ëèíåéíûõ óðàâíåíèé âèäà (1.1) çàäàåò ñèñòåìó ëèíåéíûõ àëãåáðàè÷åñêèõ (ÑËÀÓ): a11 x1 + a12 x2 + · · · + a1n xn = b1 a21 x1 + a22 x2 + · · · + a2n xn = b2 .. . am1 x1 + am2 x2 + · · · + amn xn = bm , 1 Î ïîëÿõ ñì. ãëàâó 2 4 (1.2) ãäå aij ∈ F  êîýôôèöèåíòû, bi ∈ F  ñâîáîäíûå ÷ëåíû, à xj  íåèçâåñòíûå.  äàëüíåéøåì, çàïèñûâàÿ ñèñòåìû àëãåáðàè÷åñêèõ óðàâíåíèé, ìû áóäåì ïðèäåðæèâàòüñÿ ñîãëàøåíèÿ, ÷òî i ïåðâûé èíäåêñ èíäåêñ j ñîîòâåòñòâóåò íîìåðó óðàâíåíèÿ è ïðîáåãàåò çíà÷åíèÿ îò îáîçíà÷àåò íîìåð ïåðåìåííîé è ïðèíèìàåò çíà÷åíèÿ îò 1 äî 1 äî m, à âòîðîé n. Àíàëîãè÷íî ñëó÷àþ îäíîãî ëèíåéíîãî óðàâíåíèÿ ìîæíî îïðåäåëèòü ïîíÿòèå ðåøåíèÿ ÑËÀÓ. Îïðåäåëåíèå 1.2.2. Ðåøåíèåì ÑËÀÓ (1.2) íàçûâàåòñÿ íàáîð ÷èñåë (γ1 , γ2 , . . . , γn ) êîòîðûé îäíîâðåìåííî îáðàùàåò âñå óðàâíåíèÿ (1.2) â ðàâåíñòâà. èç F, Äàëåå ìû ââåäåì íåêîòîðûå îïðåäåëåíèÿ, êîòîðûå ïîçâîëÿþò êëàññèôèöèðîâàòü ñèñòåìû ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé. Îïðåäåëåíèå 1.2.3. ðàâíû íóëþ è Áóäåì ãîâîðèòü, ÷òî ÑËÀÓ (1.2) íåîäíîðîäíàÿ Îäíîðîäíàÿ ÑËÀÓ îäíîðîäíàÿ åñëè âñå ñâîáîäíûå ÷ëåíû â ïðîòèâíîì ñëó÷àå. âñåãäà èìååò òðèâèàëüíîå ðåøåíèå xi = 0, i = 1, . . . , n.  îáùåì ñëó÷àå ðåøåíèå ÑËÀÓ ìîæåò áûòü íå åäèíñòâåííî.  ýòîì ñëó÷àå ìû áóäåì ãîâîðèòü î ìíîæåñòâå ðåøåíèé Îïðåäåëåíèå 1.2.4. ìåðå îäíî ðåøåíèå è îïðåäåëåííîé 1.3 ÑËÀÓ. Ñèñòåìà (1.2) íàçûâàåòñÿ íåñîâìåñòíîé ñîâìåñòíîé åñëè îíà èìååò ïî êðàéíåé â ïðîòèâíîì ñëó÷àå. Ñîâìåñòíàÿ ÑËÀÓ íàçûâàåòñÿ åñëè îíà èìååò îäíî ðåøåíèå è íåîïðåäåëåííîé â ïðîòèâíîì ñëó÷àå. Ìåòîä Ãàóññà ðåøåíèÿ ÑËÀÓ Äëÿ íà÷àëà ìû îïðåäåëèì ïîíÿòèå ýêâèâàëåíòíîñòè äâóõ ÑËÀÓ. Îïðåäåëåíèå 1.3.1. Äâå ÑËÀÓ íàçûâàþòñÿ ýêâèâàëåíòíûìè, åñëè èõ ìíîæåñòâà ðåøå- íèé ñîâïàäàþò. Ðåøåíèå ÑËÀÓ ìåòîäîì Ãàóññà 2 çàêëþ÷àåòñÿ â ïðåîáðàçîâàíèè èñõîäíîé ñèñòåìû ëè- íåéíûõ óðàâíåíèé â ýêâèâàëåíòíóþ åé, êîòîðàÿ ìîæåò áûòü ðåøåíà ïðîùå, ÷åì èñõîäíàÿ. Ïðåîáðàçîâàíèå îäíîé ñèñòåìû â äðóãóþ îñíîâûâàåòñÿ íà èñïîëüçîâàíèè òðåõ íûõ îïåðàöèé, ýëåìåíòàð- êîòîðûå ïðèìåíÿþòñÿ ê óðàâíåíèÿì ñèñòåìû: 1. Óìíîæåíèå ëåâîé è ïðàâîé ÷àñòåé óðàâíåíèÿ íà íåíóëåâîå ÷èñëî α ∈ F. 2. Ïîêîìïîíåíòíîå ñëîæåíèå óðàâíåíèÿ ñ íåêîòîðûì äðóãèì óðàâíåíèåì ñèñòåìû. 3. Ïåðåñòàíîâêà äâóõ óðàâíåíèé. Î÷åâèäíî, ÷òî ñèñòåìà, ïîëó÷åííàÿ ïóòåì ïðèìåíåíèÿ ýëåìåíòàðíûõ ïðåîáðàçîâàíèé, áóäåò ýêâèâàëåíòíà èñõîäíîé, ò.ê. ñëîæåíèå äâóõ ðàâåíñòâ è óìíîæåíèå ëåâîé è ïðàâîé ÷àñòè ðàâåíñòâà íà íåíóëåâîå ÷èñëî îïÿòü ïðèâîäÿò ê ðàâåíñòâó. Îòìåòèì, ÷òî äëÿ ëþáîãî ýëåìåíòàðíîãî ïðåîáðàçîâàíèÿ ìîæíî îïðåäåëèòü îáðàòíîå ê íåìó. 2 Carl Friedrich Gauß (1777  1855). Èçâåñòåí êàê Princeps mathematicorum  êîðîëü ìàòåìàòèêîâ. Ãàóññ ñäåëàë ôóíäàìåíòàëüíûé âêëàä ïðàêòè÷åñêè âî âñå îáëàñòè ñîâðåìåííîé åìó ìàòåìàòèêè. Îäíàêî èçîáðåòàòåëåì ìåòîäà Ãàóññà ðåøåíèÿ ñèñòåì ëèíåéíûõ óðàâíåíèé îí íå ÿâëÿåòñÿ  ýòîò ìåòîä áûë îïèñàí êèòàéñêèìè ìàòåìàòèêàìè âî âòîðîì âåêå í.ý. 5 Äëÿ èëëþñòðàöèè ïðèìåíåíèÿ ìåòîäà Ãàóññà ðàññìîòðèì ÑËÀÓ ñëåäóþùåãî âèäà: [0] [0] [0] [0] [0] [0] [0] [0] a11 x1 + a12 x2 + · · · + a1n xn = b1 a21 x1 + a22 x2 + · · · + a2n xn = b2 .. . [0] [0] [0] am1 x1 + am2 x2 + · · · + a[0] mn xn = bm , ()[k] ãäå âåðõíèé èíäåêñ îáîçíà÷àåò íîìåð èòåðàöèè. Íóëåâàÿ èòåðàöèÿ ñîîòâåòñòâóåò èñ- õîäíîé ñèñòåìå. Îáðàòèòå âíèìàíèå, ÷òî èíäåêñ èòåðàöèè ñòàâèòñÿ òîëüêî íàä êîýôôèöèåíòàìè è ñâîáîäíûìè ÷ëåíàìè (ïî÷åìó?). Óñëîâèìñÿ îáîçíà÷àòü i-å óðàâíåíèå íà k -é èòåðàöèè êàê [k] Eqi . Òîãäà ìû ìîæåì ñèìâî- ëè÷åñêè çàïèñàòü ýëåìåíòàðíûå îïåðàöèè ñëåäóþùèì îáðàçîì: 1. Óìíîæåíèå ëåâîé è ïðàâîé ÷àñòåé óðàâíåíèÿ íà íåíóëåâîå ÷èñëî [k+1] Eqi 2. Ñëîæåíèå i-ãî óðàâíåíèÿ ñ q -òûì [k+1] i-ãî è q -ãî [k] = αEqi . (1.3) óðàâíåíèåì ñèñòåìû: Eqi 3. Ïåðåñòàíîâêà α ∈ F: [k] = Eqi + Eqq[k] . (1.4) óðàâíåíèé: [k+1] Eqi = Eqq[k] , (1.5) [k] Eqq[k+1] = Eqi .  äàëüíåéøåì ìû áóäåì îáúåäèíÿòü ïåðâóþ è âòîðóþ ýëåìåíòàðíûå îïåðàöèè è èñïîëüçîâàòü îïåðàöèþ âèäà [k+1] Eqi [k] = Eqi + δEqq[k] , (1.6) ëåâóþ è ïðàâóþ ÷àñòü q -ãî óðàâíåíèÿ íà δ è ïîëó÷åíïîêîìïîíåíòíî ñêëàäûâàåì ñ i-òûì óðàâíåíèåì. Ïîëó÷èâøèéñÿ ðåçóëüòàò êîòîðàÿ îçíà÷àåò, ÷òî ìû óìíîæàåì íîå óðàâíåíèå çàïèñûâàåòñÿ âìåñòî i-ãî óðàâíåíèÿ. Öåëüþ ïðèìåíåíèÿ ýëåìåíòàðíûõ îïåðàöèé ÿâëÿåòñÿ ïðèâåäåíèå ÑËÀÓ ê òðåóãîëüíîìó ñòóïåí÷àòîìó âèäó ïî ñòðîêàì. Ýòî çíà÷èò, ÷òî åñëè â ïðåîáðàçîâàííîé ñèñòåìå ïåðâûé íåíóëåâîé êîýôôèöèåíò â ñòðîêå i ñòîèò ïðè íåèçâåñòíîé ñ èíäåêñîì äóþùèõ ñòðîêàõ êîýôôèöèåíòû ïðè íåèçâåñòíûõ ñ èíäåêñàìè 1, . . . , j j, òî âî âñåõ ïîñëå- äîëæíû áûòü ðàâíû íóëþ. Àëãîðèòì 1 îïèñûâàåò ñõåìó ïðèìåíåíèÿ ìåòîäà Ãàóññà ñ èñïîëüçîâàíèåì ïñåâäîêîäà. Ðåçóëüòàòîì ðàáîòû ïðîãðàììû ÿâëÿåòñÿ íîâàÿ ñèñòåìà óðàâíåíèé. Êðîìå òîãî, ïðîãðàììà âîçâðàùàåò èíäåêñ ïîñëåäíåãî óðàâíåíèÿ âûïîëíÿåòñÿ iend = m èëè jend = n. iend è èíäåêñ ïîñëåäíåé íåèçâåñòíîé jend . Âñåãäà Ýòî îçíà÷àåò, â ÷àñòíîñòè, ÷òî ìåòîä Ãàóññà âñåãäà ñõîäèòñÿ. Ðàññìîòðèì ñëó÷àé m = n, ò. å. êîãäà ÷èñëî óðàâíåíèé ðàâíî ÷èñëó íåèçâåñòíûõ. Äëÿ òàêîé çàäà÷è åñòü äâà âàðèàíòà îêîí÷àíèÿ ðàáîòû àëãîðèòìà: Ðàññìîòðèì èõ ïîäðîáíåå, îïóñêàÿ èíäåêñ èòåðàöèè 6 k. iend = jend è iend < jend . Algorithm 1 Ìåòîä Ãàóññà ðåøåíèÿ ÑËÀÓ, ñîñòîÿùåé èç 1: i = 1, j = 1, k = 0 2: repeat 3: 4: 5: 6: .i m  óðàâíåíèå, óðàâíåíèé ñ j n íåèçâåñòíûìè  íåèçâåñòíàÿ, k  èòåðàöèÿ if a[k] γj = 0 äëÿ âñåõ γ = i, . . . , m then j =j+1 . else [k] if a[k] ij = 0 & alj 6= 0 [k] Eqi 7: 8: 9: 10: = [k] Eql , end if for γ = i + 1 : m do [k+1] äëÿ íåêîòîðîãî [k] Eql [k] = [k] a l > i then [k] Eqi . ïåðåñòàâëÿåì äâà óðàâíåíèÿ, íî . ñ÷åò÷èê èòåðàöèé íå óâåëè÷èâàåì [k] 11: Eqγ = Eqγ − γj [k] Eqi aij 12: 13: end for 14: i = i + 1, j = j + 1, k = k + 1 15: end if 16: until i > m | j > n 17: iend = min(i, n), jend = min(j, m) Ñëó÷àé iend = jend . ñäâèãàåìñÿ íà øàã âïðàâî . ñîêðàùàåì ÷ëåíû, ñîäåðæàùèå xj , âî âñåõ ïîñëåäóþùèõ óðàâíåíèÿõ . Ïðåîáðàçîâàííàÿ ñèñòåìà óðàâíåíèé èìååò âèä: a11 x1 + a12 x2 + · · · + a1n xn =b1 a22 x2 + · · · + a2n xn =b2 .. . (1.7) ann xn =bn , Ðåøåíèå ñèñòåìû (1.7) íàõîäèòñÿ ìåòîäîì îáðàòíîé ïîäñòàíîâêè. Äîáàâèòü îïèñàíèå ìåòîäà îáðàòíîé ïîäñòàíîâêè. Ñëó÷àé iend < jend . è (n − iend )  ýòîì ñëó÷àå ïðåîáðàçîâàííàÿ ñèñòåìà ñîñòîèò èç âûðàæåíèé, èìåþùèõ âèä ñâîáîäíûé ÷ëåí bγ 0 = bγ , γ = iend + 1, . . . , n. iend óðàâíåíèé Åñëè õîòÿ áû îäèí îòëè÷àåòñÿ îò íóëÿ, òî ñèñòåìà ÿâëÿåòñÿ íåñîâìåñòíîé.  ïðîòèâíîì ñëó÷àå ñèñòåìà ÿâëÿåòñÿ íåîïðåäåëåííîé. Ðàññìîòðèì ñèñòåìó ïåðâûõ iend óðàâíåíèé.  çàâèñèìîñòè îò ñòðóêòóðû ïîëó÷åííûõ óðàâíåíèé, íåêîòîðûå ðåøåíèÿ ýòîé ñèñòåìû ìîãóò áûòü âûðàæåíû îäíîçíà÷íî, à îñòàëüíûå ïîëó÷åíû â n − iend ïàðàìåòðè÷åñêîì âèäå, êàê ôóíêöèè ñâîáîäíûõ ïåðåìåííûõ. Ñì. çàäà÷ó 2 íèæå. Îáðàòèòå âíèìàíèå, ÷òî íåêîððåêòíîå èñïîëüçîâàíèå ýëåìåíòàðíûõ îïåðàöèé ìîæåò ïðèâåñòè ê íåâåðíûì ðåçóëüòàòàì, êàê äåìîíñòðèðóåò ñëåäóþùèé ïðèìåð. Ïðèìåð 1.3.1. Ðàññìîòðèì ñèñòåìó x1 + 2x2 = 4 −2x1 + x2 = 2. ż ðåøåíèåì ÿâëÿåòñÿ ïàðà (0, 2). Ïðåäïîëîæèì, ÷òî ìû âû÷ëè ïåðâîå óðàâíåíèå èç âòîðîãî è çàïèñàëè ïîëó÷åííûé ðåçóëüòàò â ïåðâîé ñòðîêå, à çàòåì çàïèñàëè âî âòîðóþ ñòðîêó 7 ðàçíèöó âòîðîãî è ïåðâîãî óðàâíåíèé.  èòîãå ïîëó÷èëàñü íîâàÿ ñèñòåìà 5x1 + x2 = 2 −5x1 − x2 = − 2. ż ðåøåíèåì áóäåò áåñêîíå÷íîå ìíîæåñòâî ïàð âèäà (α, 2 − 5α). Î÷åâèäíî, ÷òî-òî ïîøëî íå òàê.  äàííîì ñëó÷àå ïðè÷èíà ÿñíà: ìû äâà ðàçà ñîâåðøèëè îäíî è òî æå äåéñòâèå è â ðåçóëüòàòå ïîëó÷èëè ñèñòåìó èç äâóõ îäèíàêîâûõ óðàâíåíèé (ñ òî÷íîñòüþ äî çíàêà). Îäíàêî êàê áûòü, åñëè óðàâíåíèé ìíîãî? Ìîæíî ëè èçáåæàòü òàêîãî ðîäà îøèáîê? Îòâåò íà ýòîò âîïðîñ ìîæíî óçíàòü â ðàçäåëå 1.5. Çàäà÷è è âîïðîñû 1. Ïðîàíàëèçèðóéòå ðàáîòó àëãîðèòìà Ãàóññà äëÿ ÑËÀÓ, ó êîòîðûõ ÷èñëî óðàâíåíèé íå ðàâíî ÷èñëó íåèçâåñòíûõ. Êàêîé âèä ìîæåò èìåòü ïðåîáðàçîâàííàÿ ñèñòåìà äëÿ n < m? äëÿ n > m? 2. Ðàññìîòðèòå òðè ñèñòåìû óðàâíåíèé, ïðèâåäåííûå ê ñòóïåí÷àòî-òðåóãîëüíîìó âèäó (îïóñêàÿ èíäåêñ [k] äëÿ ïðîñòîòû): x1 + a12 x2 + a13 x3 + a14 x4 =b1 x1 + a12 x2 + a13 x3 + a14 x4 =b1 x1 + a12 x2 + a13 x3 + a14 x4 =b1 x2 + a23 x3 + a24 x4 =b2 x3 + a24 x4 =b2 x2 + a23 x3 + a24 x4 =b2 x3 + a34 x4 =b3 x4 =b3 x4 =b3 Çàïèøèòå àíàëèòè÷åñêîå ðåøåíèå äëÿ êàæäîé èç ýòèõ ñèñòåì. Óêàæèòå êàêèå ïåðåìåííûå îäíîçíà÷íî îïðåäåëÿþòñÿ, êàêèå ÿâëÿþòñÿ ñâîáîäíûìè è êàêèå çàâèñèìûìè? ßâëÿåòñÿ ëè âûáîð çàâèñèìûõ/íåçàâèñèìûõ ïåðåìåííûõ îäíîçíà÷íûì? 1.4 Ìàòðèöû è îïåðàöèè íàä íèìè Ñåé÷àñ ìû ïîçíàêîìèìñÿ ñ àëãåáðàè÷åñêèì îáúåêòîì, èìåíóåìûì ìàòðèöà, êîòîðûé ëåæèò â îñíîâå âñåé ëèíåéíîé àëãåáðû.  ïåðâîé ÷àñòè íàøåãî êóðñà ìû óâèäèì, ÷òî èñïîëüçîâàíèå ìàòðèö ïîçâîëÿåò ñóùåñòâåííî óïðîñòèòü è ñèñòåìàòèçèðîâàòü ïðîöåäóðó ðåøåíèÿ ëèíåéíûõ àëåáðàè÷åñêèõ óðàâíåíèé, à ïî ìåðå ïðîäâèæåíèÿ âñòðåòèìñÿ ñ ìíîæåñòâîì äðóãèõ ïðèìåíåíèé ýòèõ âàæíûõ ñòðóêòóð. ìàòðèöà  ýòî ïðÿìîóãîëüíûé ìàññèâ ÷èñåë, ïðèíàäëåæàùèõ íåêîòîðîìó ìíîæåF ∈ {Q, R, C}, íî íàì áóäóò âñòðå÷àòüñÿ è äðóãèå ñëó÷àè3 .  ýòîé ãëàâå ìû áóäåì ïîëàãàòü äëÿ îïðåäåëåííîñòè, ÷òî F = R. Íèæå ïðèâåäåíî íåñêîëüêî Èòàê, ñòâó F. Îáû÷íî ïîëàãàåòñÿ, ÷òî ïðèìåðîâ ìàòðèö  1 4 2 5  3 , 6 √   2 π , 0.27 1  0 −0.2  1 −1 , è ò. ä.  îáùåì ñëó÷àå ìû áóäåì ðàññìàòðèâàòü ìàòðèöû, ýëåìåíòû êîòîðûõ çàäàíû â ñèìâîëüíîì âèäå. Òàê, ìû áóäåì èñïîëüçîâàòü çàïèñü:  a11  a21  A= .  .. a12 a22 .. . ... ... .. .  a1n a2n   ..  . .  am1 am2 ... amn 3  êà÷åñòâå ìíîæåñòâà F ìîæíî ðàññìàòðèâàòü ëþáîå ïîëå. Åäèíñòâåííûé ñëó÷àé, êîòîðûé òðåáóåò îñîáîãî âíèìàíèÿ,  ýòî ïîëå õàðàêòåðèñòèêè 2. Äëÿ ìàòðèö, ýëåìåíòû êîòîðûõ ïðèíàäëåæàò òàêîìó ïîëþ, íåêîòîðûå ôîðìóëèðîâêè íå èìåþò ñìûñëà, à ðÿä ðåçóëüòàòîâ äîëæåí áûòü ïåðåôîðìóëèðîâàí. 8 äëÿ ìàòðèöû, ñîäåðæàùåé m ñòðîê è n ñòîëáöîâ, n, m ∈ N, aij ∈ F . Ìàòðèöû îáîçíà÷àþòñÿ ïðÿìûìè çàãëàâíûìè áóêâàìè ëàòèíñêîãî àëôàâèòà, à èõ ýëåìåíòû  ñîîòâåòñòâóþùèìè ñòðî÷íûìè áóêâàìè ñ äâîéíûìè èíäåêñàìè, ïåðâûé èç êîòîðûõ óêàçûâàåò íà íîìåð ñòðîêè, à âòîðîé  íà íîìåð ñòîëáöà. Ìû áóäåì ãîâîðèòü, ÷òî ìàòðèöà èìååò m ñòðîê è n ñòîëáöîâ. ðàâíû, åñëè îíè èìåþò îäèíàêîâóþ ðàçìåðíîñòü [m × n], åñëè îíà ñîäåðæèò Äâå ìàòðèöû ðàçìåðíîñòü è èõ ñîîòâåòñòâóþùèå ýëåìåíòû ðàâíû. Ðàññìîòðèì íåñêîëüêî ñïåöèàëüíûõ òèïîâ ìàòðèö: • Êâàäðàòíàÿ ìàòðèöà èìååò ðàçìåðíîñòü [n × n]. Èíà÷å ìàòðèöà íàçûâàåòñÿ ïðÿìîóãîëüíîé. ×àñòíûå ñëó÷àè ïðÿìîóãîëüíûõ ìàòðèö  ýòî ñòîëáåö è ñòðîêà. • Ñòîëáåö  ìàòðèöà ðàçìåðíîñòè [n × 1]. Ñòðîêà  ìàòðèöà ðàçìåðíîñòè [n × 1]. Ñòîëáöû è ñòðîêè ìû áóäåì îáîçíà÷àòü ïîëóæèðíûìè ñòðî÷íûìè áóêâàìè ëàòèíñêîãî àëôàâèòà. • Íàêîíåö, ìàòðèöà ðàçìåðíîñòè [1 × 1] îáû÷íî èäåíòèôèöèðóåòñÿ ñ ÷èñëîì. Îáðàòèòå âíèìàíèå, ÷òî îáðàòíîå íåâåðíî. Ïðè ðàáîòå ñ ìàòðèöàìè ÷èñëî íåëüçÿ ðàññìàòðèâàòü êàê ìàòðèöó åäèíè÷íîé ðàçìåðíîñòè, ò.ê. ýòî ìîæåò ïðèâåñòè ê ëîãè÷åñêèì ïðîòèâîðå÷èÿì. 1.4.1 Îïåðàöèè íàä ìàòðèöàìè 4 Äëÿ ìàòðèö îïðåäåëåíû îïåðàöèè ñëîæåíèÿ äâóõ ìàòðèö, óìíîæåíèÿ ìàòðèöû íà ñêàëÿð è óìíîæåíèÿ äâóõ ìàòðèö: 1. Ñëîæåíèå îïðåäåëåíî äëÿ ìàòðèö îäèíàêîâîé ðàçìåðíîñòè è âûïîëíÿåòñÿ ïîêîìïîíåíòíî:       a11 . . . a1n b11 . . . b1n a11 + b11 . . . a1n + b1n   ..  +  .. ..  =  .. .. .. .. .. A + B =  ... . . . . .   . .   . . am1 2. ... amn bm1 ... bmn am1 + bm1 ... amn + bmn Óìíîæåíèå íà ñêàëÿð γ ∈ F òàêæå îñóùåñòâëÿåòñÿ ïîêîìïîíåíòíî:     a11 . . . a1n γa11 . . . γa1n  ..  =  .. ..  . .. .. γA = γ  ... . . .   . .  am1 ... amn γam1 ... γamn óìíîæåíèå äâóõ ìàòðèö îïðåäåëåíî òîëüêî äëÿ ìàòðèö ñ ñîãëàñîâàííûìè ðàçìåðíîñòÿìè, à èìåííî, ÷èñëî ñòîëáöîâ ïåðâîé ìàòðèöû äîëæíî áûòü ðàâíî 3. Íàêîíåö, ÷èñëó ñòðîê âòîðîé. Ïóñòü A = [aij ]  ìàòðèöà ðàçìåðíîñòè [m × n], à B = [bij ]  ìàòðèöà ðàçìåðíîñòè [n × q]. Òîãäà èõ ïðîèçâåäåíèå C = AB  ýòî ìàòðèöà ðàçìåðíîñòè [m × q], ýëåìåíòû êîòîðîé îïðåäåëåíû êàê cij = n X aik bkj . (1.8) k=1 4  êîíòåêñòå ëèíåéíîé àëãåáðû è ìàòðè÷íîãî àíàëèçà ìû áóäåì ÷àñòî èñïîëüçîâàòü ñëîâî â âèäó ÷èñëî èç ìíîæåñòâà F . 9 ñêàëÿð, èìåÿ Ïîëåçíî çàïîìíèòü ïðîñòîå ìíåìîíè÷åñêîå ïðàâèëî: îïåðàöèÿ óìíîæåíèÿ îïðåäåëåíà [m × n] · [n × q]. [m × q]. äëÿ äâóõ ìàòðèö, åñëè èõ ñìåæíûå ðàçìåðíîñòè ðàâíû: ìåðíîñòè ñîêðàùàþòñÿ â ðåçóëüòèðóþùåé ìàòðèöå: Ýòè ðàâíûå ðàç- Ðàññìîòðèì íåêîòîðûå ÷àñòíûå ñëó÷àè è ïðèåìû, ïîçâîëÿþùèå óïðîñòèòü ïðîöåäóðó óìíîæåíèÿ ìàòðèö ñïåöèàëüíîãî âèäà. Ïóñòü a = [ai ]  ñòðîêà ðàçìåðíîñòè Òîãäà ïðîèçâåäåíèå ab  ab = a1 [1 × n], à b = [bi ]  ñòîëáåö ðàçìåðíîñòè [n × 1]. áóäåò îïðåäåëÿòüñÿ ïî ñëåäóþùåìó ïðàâèëó: a2 ...   b1 n  X   b2   an  .  = a1 b1 + a2 b2 + · · · + an bn = ai bi .  ..  i=1 bn Òåïåðü ìû ìîæåì äàòü áîëåå èíòóèòèâíóþ èíòåðïðåòàöèþ ïðîöåäóðå óìíîæåíèÿ äâóõ ìàò- â ïðîèçâåäåíèè C = AB: (ij)-é ýëåìåíò ìàòðèöû C ðàâåí ïðîèçâåäåíèþ i-é ñòðîêè ìàòðèöû A íà j -é ñòîëáåö ìàòðèöû B. ðèö: Îáðàòèòå âíèìàíèå, ÷òî óìíîæåíèå ñòîëáöà íà ñòðîêó òîæå îïðåäåëåíî, íî ïðèâîäèò ê b ðàçìåðíîñòè [n × 1] [1 × m] áóäåò ïîðîæäàòü ìàòðèöó ðàçìåðà [n × m]:     b1 b1 a1 b1 a2 . . . b1 am  b2         b2 a1 b2 a2 . . . b2 am   ..  a1 a2 . . . am =  .. .. ..  . .. .  . . . .  ñîâåðøåííî èíîìó ðåçóëüòàòó. Òàê, óìíîæåíèå ñòîëáöà ðàçìåðíîñòè bn bn a1 bn a2 ... íà ñòðîêó a bn am A  ìàòðèöà [m × n]. Òîãäà äîïóñòèìû ñëåäóþùèå îïåðàöèè: óìíîæåíèå A ñëåâà íà ñòðîêó ðàçìåðíîñòè [1 × m] è óìíîæåíèå A ñïðàâà íà ñòîëáåö ðàçìåðíîñòè [n × 1]. Ïîéäåì äàëüøå è ðàññìîòðèì óìíîæåíèå ñòðîêè è ñòîëáöà íà ìàòðèöó. Ïóñòü ðàçìåðíîñòè Ñôîðìóëèðóåì ïðàâèëà, ïîçâîëÿþùèå â ðÿäå ñëó÷àåâ óïðîñòèòü ñîîòâåòñòâóþùèå ïðîöåäóðû óìíîæåíèÿ. Äëÿ íà÷àëà óñëîâèìñÿ j -é ñòîëáåö êàê a×,j . 5 îáîçíà÷àòü i-þ ñòðîêó ìàòðèöû A êàê ai,× , à ai,× , a×,j Òåïåðü ìû ìîæåì çàïèñàòü ñîîòâåòñòâóþùèå ïðàâèëà: 1. Óìíîæåíèå ñòðîêè íà ìàòðèöó:    cA = c1 c2 ...   cm   a1,× a2,× .. . am,×        =       c1 a1,× + c2 a2,× + .. . + cm am,× ò. å. ðåçóëüòàò óìíîæåíèÿ ïðåäñòàâëÿåò ñîáîé ñóììó ñòðîê ìàòðèöû íà ñîîòâåòñòâóþùèå ýëåìåíòû ñòðîêè       ,     A, äîìíîæåííûõ c. 5  ñèñòåìå êîìïüþòåðíîé àëãåáðû MATLAB (MATrix LABoratory) äëÿ òåõ æå öåëåé ïðèíÿòû îáîçíà÷åíèÿ a(i,:) è a(:,j). Ìû áóäåì èñïîëüçîâàòü ñèìâîë × âìåñòî äâîåòî÷èÿ äëÿ óëó÷øåíèÿ ÷èòàåìîñòè ôîðìóë. 10 2. Óìíîæåíèå ìàòðèöû íà ñòîëáåö:     b1  b2   a×,n    ..  = b1 a×,1 . bn  Ab = a×,1 a×,2 ...  + b2 a×,2 ò. å. ðåçóëüòàò ïðåäñòàâëÿåò ñîáîé ñóììó ñòîëáöîâ ìàòðèöû ìåíòû ñòîëáöà + ... A, + bn a×,n  , äîìíîæåííûõ íà ýëå- b. 3. Íàêîíåö çàìåòèì, ÷òî óìíîæåíèå ìàòðèöû íà ìàòðèöó òîæå ìîæåò áûòü ïðåäñòàâëåíî ñ ïîìîùüþ ïðèâåäåííûõ âûøå ñõåì. Ïóñòü è [q × n]. A è Òîãäà ìû ìîæåì çàïèñàòü ïðîèçâåäåíèå   a1,× B a2,× B .. .   AB =   B  ìàòðèöû ðàçìåðíîñòåé [m × q] AB äâóìÿ ñïîñîáàìè:     Ab ×,1 =  Ab×,2 ... Ab×,n  , (1.9) am,× B ò. å. ìîæíî óìíîæàòü ìàòðèöó ðèöó B A ñëåâà ïîñòðî÷íî íà ìàòðèöó ñïðàâà ïîñòîëáöîâî íà ìàòðèöó B, ëèáî óìíîæàòü ìàò- A. Íåêîììóòàòèâíîñòü ìàòðè÷íîãî óìíîæåíèÿ. Îáðàòèòå âíèìàíèå: óìíîæåíèå ìàòðèö â îáùåì ñëó÷àå íåêîììóòàòèâíî, ò. å. ìû èìååì AB 6= BA. Äëÿ ïðèìåðà ðàññìîòðèì ìàòðèöû  1 A= 1 1  1 è  2 1 : 1  1 B = 2 1  3 AB = 3   1 3 , BA = 2 2 1 3 3 2  2 1 . 1  äàííîì ñëó÷àå íåêîììóòàòèâíîñòü ñëåäóåò óæå èç íåñîâïàäåíèÿ ðàçìåðíîñòåé. Îäíàêî ïîäîáíûé ïðèìåð ìîæåò áûòü ïðèâåäåí è äëÿ äâóõ êâàäðàòíûõ ìàòðèö:  1  1 1 1 2   3 = 2 2   2 1 6= 2 2   1 1 = 4 2  0 1 2 0  1 . 1 Íàêîíåö ðàññìîòðèì äâà ñïåöèàëüíûõ òèïà ìàòðèö, êîòîðûå ïðåäñòàâëÿþò ñîáîé ìàòðè÷íûå àíàëîãè íóëÿ è åäèíèöû â ìíîæåñòâå âåùåñòâåííûõ ÷èñåë. Îïðåäåëåíèå 1.4.1. íàçûâàåòñÿ Îïðåäåëåíèå 1.4.2. òîðîé ðàâíû ìàòðèöåé Ìàòðèöà ðàçìåðíîñòè íóëåâîé ìàòðèöåé 1, [m×n], ñîäåðæàùàÿ òîëüêî íóëåâûå ýëåìåíòû, 0[m×n] . è îáîçíà÷àåòñÿ Êâàäðàòíàÿ ìàòðèöà ðàçìåðíîñòè [n×n], äèàãîíàëüíûå ýëåìåíòû êîåäèíè÷íîé à âñå îñòàëüíûå, âíåäèàãîíàëüíûå ýëåìåíòû,  íóëè, íàçûâàåòñÿ è îáîçíà÷àåòñÿ 6 En (èëè In â àíãëîÿçû÷íîé ëèòåðàòóðå, ò. å. Identity matrix). Òàê, íàïðèìåð, 0[2×3]  =  ,  1 E3 = 0 1  0 . 1 Îáðàòèòå âíèìàíèå, ÷òî íóëåâàÿ ìàòðèöà ìîæåò èìåòü ëþáóþ ðàçìåðíîñòü, â òî âðåìÿ êàê åäèíè÷íàÿ ìàòðèöà ìîæåò áûòü òîëüêî êâàäðàòíîé. 6 Ñèìâîë E â äåéñòâèòåëüíîñòè ïðîèñõîäèò îò íåìåöêîãî 11 Einheitsmatrix. AB 6= BA 1.4.2 Îñíîâíûå ñâîéñòâà îïåðàöèé íàä ìàòðèöàìè  òàáëèöå 1.1 côîðìóëèðîâàíû îñíîâíûå ñâîéñòâà îïåðàöèé íàä ìàòðèöàìè. Ìû íå óêàçûâàåì ðàçìåðíîñòè ìàòðèö, ïîëàãàÿ, ÷òî âñå ìàòðèöû, âõîäÿùèå â âûðàæåíèÿ, èìåþò ñîãëàñîâàííûå ðàçìåðíîñòè. Çà èñêëþ÷åíèåì òðåáîâàíèÿ ñîãëàñîâàííîñòè, íèêàêèå îãðàíè÷åíèÿ íà ðàçìåðû ìàòðèö íå íàêëàäûâàþòñÿ. Òàáëèöà 1.1: Ñâîéñòâà ìàòðè÷íûõ îïåðàöèé Ìàòðè÷íîå ñëîæåíèå Óìíîæåíèå íà ñêàëÿð Êîììóòàòèâíîñòü A+B=B+A Àññîöèàòèâíîñòü (A + B) + C = A + (B + C) Íåéòðàëüíûé ýëåìåíò A+0=0+A=A Îáðàòíûé ýëåìåíò A + (−A) = 0 Àññîöèàòèâíîñòü (αβ)A = α(βA) Äèñòðèáóòèâíîñòü (α + β)A = αA + βA α(A + B) = αA + αB Ìàòðè÷íîå óìíîæåíèå Åäèíè÷íûé ñêàëÿð 1·A=A Íóëåâîé ñêàëÿð 0·A=0 Àññîöèàòèâíîñòü (AB)C = A(BC) Äèñòðèáóòèâíîñòü A(B + C) = AB + AC (A + B)C = AC + BC Ñîãëàñîâàííîñòü óìíîæå- α(AB) = (αA)B = A(αB) íèÿ íà ñêàëÿð è ìàòðè÷íîãî óìíîæåíèÿ Íåéòðàëüíûé ýëåìåíò EA = A, AE = A Íóëåâàÿ ìàòðèöà 0 · A = 0, A · 0 = 0 Ïîêàæåì âûïîëíåíèå ñâîéñòâà àññîöèàòèâíîñòè ìàòðè÷íîãî óìíîæåíèÿ. Âûâîä îñòàëüíûõ ñâîéñòâ îñòàâëÿåòñÿ ÷èòàòåëþ â êà÷åñòâå ñàìîñòîÿòåëüíîãî óïðàæíåíèÿ. Ïóñòü ìàòðèöû A, B è âñïîìîãàòåëüíûå ìàòðèöû C èìåþò ðàçìåðíîñòè [m × n], [n × q] è [q × r]. Îïðåäåëèì äâå D = AB è G = BC . Èõ ðàçìåðíîñòè ðàâíû [m × q] è [n × r], à ýëåìåíòû âûðàæàþòñÿ ñëåäóþùèì îáðàçîì: dij = gij = n X k=1 q X aik bkj , i = 1, . . . , m, j = 1, . . . , q, (1.10) bik ckj , i = 1, . . . , n, j = 1, . . . , r. k=1 Íåîáõîäèìî ïîêàçàòü. ÷òî äåíèÿ DC è AG (AB)C = DC = AG = A(BC). Äëÿ íà÷àëà çàìåòèì, ÷òî ïðîèçâå[m × r]. Çàïèøåì âûðàæåíèÿ äëÿ (i, j)-ãî èìåþò îäèíàêîâóþ ðàçìåðíîñòü 12 ýëåìåíòà ïåðâîãî è âòîðîãî ïðîèçâåäåíèÿ, [DC]ij = [AG]ij = q X l=1 n X i = 1, . . . , m, j = 1, . . . , r: q X n X dik ckj = ail glj = l=1 aik bkl clj k=1 =1 q n X X ail l=1 (1.11a) blk ckj . (1.11b) k=1 Ïîñëåäíèå ÷àñòè âûðàæåíèé ïîëó÷åíû ñ ó÷åòîì (1.10). Ðàññìîòðèì ñóììó â âûðàæåíèè (1.11b). Ïîñêîëüêó ail íå çàâèñèò îò èíäåêñà Ïîëó÷àåì n X l=1 ail q X k , ìû ìîæåì âíåñòè ail blk ckj = k=1 q n X X ïîä çíàê âòîðîé ñóììû. ail blk ckj . (1.12) l=1 k=1 Îáðàòèì âíèìàíèå, ÷òî â (1.11a) è (1.12) âíåøíåå ñóììèðîâàíèå îñóùåñòâëÿåòñÿ ïî ïåðâîìó ïîâòîðÿþùåìóñÿ èíäåêñó, à âíóòðåííåå ñóììèðîâàíèå  ïî âòîðîìó ïîâòîðÿþùåìóñÿ èíäåêñó. Ïîñëå ïåðåîáîçíà÷åíèÿ èíäåêñîâ ïîëó÷àåì òðåáóåìîå ðàâåíñòâî. Çàìå÷àíèå 1.4.1. E, íèÿ, ò. å. Çàìåòèì, ÷òî íåéòðàëüíûé ýëåìåíò îòíîñèòåëüíî ìàòðè÷íîãî óìíîæå- â îáùåì ñëó÷àå ìîæåò èìåòü ðàçëè÷íóþ ðàçìåðíîñòü ïðè óìíîæåíèè ñëåâà è ñïðàâà. Åñëè A  êâàäðàòíàÿ ìàòðèöà ðàçìåðíîñòè [n×n], òî âûïîëíÿåòñÿ AEn = En A = A. Íàðÿäó ñ îñíîâíûìè ìàòðè÷íûìè îïåðàöèÿìè áîëüøóþ ðîëü èãðàåò îïåðàöèÿ òðàíñïîíèðîâàíèÿ. Îïðåäåëåíèå 1.4.3. Òðàíñïîíèðîâàííàÿ ìàòðèöà A> ìåíû ñòðîê íà ñòîëáöû. Îáîçíà÷àÿ ÷åðåç ìîæíî çàïèñàòü [X]ij (i, j)-é ïîëó÷àåòñÿ èç èñõîäíîé ïóòåì çà- ýëåìåíò ìàòðè÷íîãî âûðàæåíèÿ X,  > A ij = aji . Òåîðåìà 1.4.1. Îïåðàöèÿ òðàíñïîíèðîâàíèÿ óäîâëåòâîðÿåò ñëåäóþùèì ñâîéñòâàì: 1. A>
> = A, 2. (A + B)> = A> + B> , 3. (γA)> = γA> , 4. (AB)> = B> A> . Äîêàçàòåëüñòâî. Ìû äîêàæåì òîëüêî ïîñëåäíèé ïóíêò. Èñïîëüçóÿ âûðàæåíèå (1.8) è îïðåäåëåíèå òðàíñïîíèðîâàíèÿ, èìååì Pn     Pn (AB)> ij = k=1 ajk bki .  òî æå âðåìÿ, B> A> ij = k=1 bki ajk . Èçìåíÿÿ ïîðÿäîê ñîìíîæèòåëåé, ïîëó÷àåì èñêîìîå òîæäåñòâî. 1.4.3 Ìàòðèöû ñïåöèàëüíîãî âèäà  äàëüíåéøåì ìû ÷àñòî áóäåì âñòðå÷àòüñÿ ñ ìàòðèöàìè, èìåþùèìè ñïåöèàëüíóþ ñòðóêòóðó. Òàêèå ìàòðèöû ìîãóò ïîÿâëÿòüñÿ åñòåñòâåííûì îáðàçîì ïðè ðåøåíèè ïðàêòè÷åñêèõ çàäà÷ èëè èñïîëüçîâàòüñÿ ïðè ðåøåíèè çàäà÷ îáùåãî âèäà (êîãäà èññëåäóåìàÿ ìàòðèöà ïðåîáðàçóåòñÿ ê íåêîòîðîé ñïåöèàëüíîé ôîðìå). 13 A> Äèàãîíàëüíûå ìàòðèöû. Ãëàâíîé äèàãîíàëüþ êâàäðàòíîé ìàòðèöû A áóäåì íàçûâàòü ýëåìåíòû ñ ïîâòîðÿþùèìèñÿ èíäåêñàìè, ò. å. ìàòðèöà  ýòî êâàäðàòíàÿ ìàòðèöà íóëþ, ò. å. aij = 0 äëÿ âñåõ i 6= j . A aii , i = 1, . . . , n. Ñîîòâåòñòâåííî, äèàãîíàëüíàÿ âíåäèàãîíàëüíûå ýëåìåíòû ðàâíû òàêàÿ, ÷òî âñå Îáû÷íî èñïîëüçóåòñÿ ñîêðàùåííàÿ çàïèñü  a1  .. A = diag(a1 , . . . , an ) =  . ... .. . ...  ..  . . an Îäíèì èç ïðåäñòàâèòåëåé äèàãîíàëüíûõ ìàòðèö ÿâëÿåòñÿ ò. í. ìàòðèöà âèäà αE. ñêàëÿðíàÿ ìàòðèöà, ò. å. Ëåãêî ïðîâåðèòü, ÷òî ñêàëÿðíàÿ ìàòðèöà êîììóòèðóåò ñî âñåìè ìàòðè- öàìè. Òðåóãîëüíûå ìàòðèöû. Âåðõíÿÿ (íèæíÿÿ) òðåóãîëüíàÿ ìàòðèöà ìàòðèöà aij = 0 A  ýòî êâàäðàòíàÿ òàêàÿ, ÷òî âñå ýëåìåíòû íèæå (âûøå) ãëàâíîé äèàãîíàëè ðàâíû íóëþ, ò. å. äëÿ âñåõ i > j (i < j ). Çàìåòèì, ÷òî åñëè A  íèæíÿÿ òðåóãîëüíàÿ ìàòðèöà, òî A>  âåðõíÿÿ òðåóãîëüíàÿ è íàîáîðîò.  îáùåì ñëó÷àå äèàãîíàëüíûå ýëåìåíòû òðåóãîëüíîé ìàòðèöû ìîãóò ðàâíÿòüñÿ íóëþ.  äàëüíåéøåì ìû óâèäèì, ÷òî äèàãîíàëüíûå ýëåìåíòû òðåóãîëüíîé ìàòðèöû èãðàþò áîëüøóþ ðîëü â ðàçëè÷íûõ çàäà÷àõ.  ÷àñòíîñòè, ìû áóäåì âñòðå÷àòüñÿ ñ óíèïîòåíòíûìè òðåóãîëüíûìè ìàòðèöàìè, ò. å. òðåóãîëüíûìè ìàòðèöàìè, âñå äèàãîíàëüíûå ýëåìåíòû êîòîðûõ ðàâíû 1. Ñôîðìóëèðóåì íåêîòîðûå ðåçóëüòàòû î òðåóãîëüíûõ ìàòðèöàõ, êîòîðûå ïîòðåáóþòñÿ íàì â äàëüíåéøåì. Òåîðåìà 1.4.2. Ïðîèçâåäåíèå äâóõ âåðõíèõ (íèæíèõ) òðåóãîëüíûõ ìàòðèö åñòü âåðõíÿÿ (íèæíÿÿ) òðåóãîëüíàÿ ìàòðèöà. Äîêàçàòåëüñòâî. C = AB Ïóñòü A è B  äâå âåðõíèå òðåóãîëüíûå ìàòðèöû ðàçìåðà  èõ ïðîèçâåäåíèå. Ñîãëàñíî (1.8), cij = cij n X [n × n], à çàïèñûâàåòñÿ êàê aik bkj . k=1 i > j äëÿ âñåõ k âûïîëíÿåòñÿ îäíî èç äâóõ íåðàâåíñòâ: i > k èëè k > i > j îäèí èç ñîìíîæèòåëåé â âûðàæåíèè äëÿ cij ðàâåí íóëþ ïî îïðåäåëåíèþ âåðõíåé òðåóãîëüíîé ìàòðèöû: aik = 0 ïðè i > k èëè bkj = 0 ïðè k > j . Òàêèì îáðàçîì, cij = 0 ïðè i > j è ñëåäîâàòåëüíî C  âåðõíÿÿ òðåóãîëüíàÿ ìàòðèöà. Ïóñòü òåïåðü A è B  äâå íèæíèå òðåóãîëüíûå ìàòðèöû. Äâàæäû òðàíñïîíèðóÿ èõ Çàìåòèì, ÷òî ïðè j. Ñëåäîâàòåëüíî, ïðè ïðîèçâåäåíèå ïîëó÷èì: AB = (AB)>
> = B > A>
> , ãäå âûðàæåíèå ñïðàâà â ñêîáêàõ ïðåäñòàâëÿåò ñîáîé ïðîèçâåäåíèå äâóõ âåðõíèõ òðåóãîëüíûõ ìàòðèö, ñëåäîâàòåëüíî òàêæå âåðõíþþ òðåóãîëüíóþ ìàòðèöó. Òðàíñïîíèðóÿ ýòó ìàòðèöó ïîëó÷àåì íèæíþþ òðåóãîëüíóþ ìàòðèöó. Òåîðåìà 1.4.3. Ïðîèçâåäåíèå äâóõ âåðõíèõ (íèæíèõ) óíèïîòåíòíûõ òðåóãîëüíûõ ìàòðèö åñòü âåðõíÿÿ (íèæíÿÿ) óíèïîòåíòíàÿ òðåóãîëüíàÿ ìàòðèöà. 14 Äîêàçàòåëüñòâî. Ðàññìîòðèì ñëó÷àé äâóõ âåðõíèõ òðåóãîëüíûõ ìàòðèö. Äëÿ íèæíèõ A è B  äâå óíèïîòåíòíûå [n×n], à C = AB  èõ ïðîèçâåäåíèå. Ïî òåîðåìå 1.4.2, Ñîãëàñíî (1.8), äèàãîíàëüíûå ýëåìåíòû cii , i = 1, . . . , n, òðåóãîëüíûõ ìàòðèö ðåçóëüòàò ïîëó÷àåòñÿ àíàëîãè÷íî. Ïóñòü âåðõíèå òðåóãîëüíûå ìàòðèöû ðàçìåðà C  âåðõíÿÿ òðåóãîëüíàÿ ìàòðèöà. èìåþò âèä n X cii = aik bki . k=1 k 6= i âûïîëíÿåòñÿ îäíî èç äâóõ íåðàâåíñòâ: i > k èëè k > i è, ñëåäîâàòåëüíî, k 6= i îäèí èç ñîìíîæèòåëåé â âûðàæåíèè äëÿ cii ðàâåí íóëþ. Òîãäà èìååì cii = aii bii = 1. Äëÿ âñåõ äëÿ êàæäîãî Ñèììåòðè÷åñêèå ìàòðèöû. A = A> è êîñî-ñèììåòðè÷åñêîé Êâàäðàòíàÿ ìàòðèöà A íàçûâàåòñÿ A = −A> . åñëè ñèììåòðè÷åñêîé åñëè Ìíîæåñòâà ñèììåòðè÷åñêèõ è êîñî-ñèììåòðè÷åñêèõ ìàòðèö çàìêíóòû îòíîñèòåëüíî îïåðàöèé ñëîæåíèÿ äâóõ ìàòðèö è óìíîæåíèÿ íà ñêàëÿð. Îäíàêî ñâîéñòâî ñèììåòðè÷íîñòè (êîñî-ñèììåòðè÷íîñòè) â îáùåì ñëó÷àå íå ñîõðàíÿåòñÿ ïðè óìíîæåíèè äâóõ ìàòðèö. Âûÿñíåíèå óñëîâèé, ïðè êîòîðûõ ïðîèçâåäåíèå äâóõ ñèììåòðè÷åñêèõ (êîñî-ñèììåòðè÷åñêèõ) ìàòðèö áóäåò ñèììåòðè÷åñêîé (êîñî-ñèììåòðè÷åñêîé) ìàòðèöåé, îñòàâëÿåòñÿ ÷èòàòåëþ â êà÷åñòâå óïðàæíåíèÿ. Ìîæíî ñôîðìóëèðîâàòü ñëåäóþùèé èíòåðåñíûé ðåçóëüòàò. Òåîðåìà 1.4.4. Ëþáàÿ êâàäðàòíàÿ ìàòðèöà A ìîæåò áûòü ïðåäñòàâëåíà â âèäå ñóììû ñèììåòðè÷åñêîé è êîñî-ñèììåòðè÷åñêîé ìàòðèö. Äîêàçàòåëüñòâî. 1 > + 12 A − A> . Ëåãêî ïðî2 A+A âåðèòü, ÷òî ïåðâîå ñëàãàåìîå ÿâëÿåòñÿ ñèììåòðè÷åñêîé, à âòîðîå  êîñî-ñèììåòðè÷åñêîé Çàïèøåì ìàòðèöó A â âèäå A=

ìàòðèöåé. Áëî÷íûå ìàòðèöû. Ãîâîðèòñÿ, ÷òî ìàòðèöà ïðåäñòàâëåíà â áëî÷íîé ôîðìå, åñëè îíà ìîæåò áûòü ðàçáèòà (óñëîâíûìè) âåðòèêàëüíûìè è ãîðèçîíòàëüíûìè ëèíèÿìè íà íåñêîëüêî ïðÿìîóãîëüíûõ ïîäìàòðèö:  A= A11 |A12 A21 |A22  (1.13) Áëî÷íîå ïðåäñòàâëåíèå ìàòðèöû ïîëåçíî òîãäà, êîãäà íåêîòîðûå áëîêè ìàòðèöû èìåþò ïðîñòóþ ñòðóêòóðó, íàïðèìåð, ñîâïàäàþò ñ íóëåâîé ìàòðèöåé. Ïî àíàëîãèè ñ ðàññìîòðåííûìè âûøå ïðèìåðàìè, ìîæíî îïðåäåëèòü íûå ìàòðèöû, à òàêæå âåðõíèå è íèæíèå áëî÷íî-òðåóãîëüíûå áëî÷íî-äèàãîíàëü- ìàòðèöû, êàê ìàòðèöû ñ êâàäðàòíûìè (!) ïîäìàòðèöàìè âäîëü ãëàâíîé äèàãîíàëè è ñîîòâåòñòâóþùèìè íóëåâûìè âíåäèàãîíàëüíûìè áëîêàìè. Óìíîæåíèå áëî÷íûõ ìàòðèö. Áëî÷íûå ìàòðèöû ìîæíî óìíîæàòü ïî òåì æå ïðàâè- ëàì, ÷òî è îáû÷íûå ïðè óñëîâèè, ÷òî ðàçáèåíèå íà áëîêè â îáåèõ ìàòðèöàõ Ïóñòü A è B ñóòü äâå áëî÷íûå ìàòðèöû ñ áëîêàìè Aij , Bij , i, j ∈ {1, 2}. ñîãëàñîâàíî. Òîãäà âûðàæåíèå äëÿ èõ ïðîèçâåäåíèÿ çàïèñûâàåòñÿ ñëåäóþùèì îáðàçîì (ïðè óñëîâèè, ÷òî âñå ïðîèçâåäåíèÿ ìàðèö, âõîäÿùèå â âûðàæåíèå îïðåäåëåíû):  AB = A11 |A12 A21 |A22  B11 |B12 B21 |B22   = A11 B11 + A12 B21 |A11 B12 + A12 B22 A21 B11 + A22 B21 |A21 B12 + A22 B22 15  . Ìîæíî çàìåòèòü, ÷òî ïðè óìíîæåíèè áëî÷íûõ ìàòðèö âíóòðåííèå èíäåêñû âñåãäà ðàâíû. Ýòî çíà÷èò, ÷òî ÷èñëî ñòîëáöîâ â ïåðâîì áëî÷íîì ñòîëáöå ìàòðèöû ÷èñëó ñòðîê â ïåðâîé áëî÷íîé ñòðîêå ìàòðèöû B A äîëæíî áûòü ðàâíî è ò. ä. Çàäà÷è è âîïðîñû 1. Êëàññèôèöèðóéòå ïðèâåäåííûå íèæå ìàòðèöû, ïðåäëîæèòå âîçìîæíûå ðàçáèåíèÿ íà áëîêè.  1 0  0 2 −1 3 1  −2 0  , 0  2  1 0  0 2 −1 3 3 −1  2 0 , 0 2  1 0  2 1 5 3 −1  0 , 0 2  1  0   2 −1 1 1  0  , −1 2  0  2 1 −3 −2 3  1 0 . 0 2. Ðàññìîòðèì äâå áëî÷íûå ìàòðèöû A è B.  1 A= 3 2| 0 4| 0 0 |−1  0 , 1  0 |−2  0| 1  B= 0| 1 0 |−2  −1 2   −1  2 Áóäóò ëè îïðåäåëåíû ïðîèçâåäåíèÿ AB è BA ñ ó÷åòîì ñòðóêòóðû áëî÷íîãî ðàçáèåíèÿ? Äëÿ äîïóñòèìûõ âûðàæåíèé çàïèøèòå ðåçóëüòàò óìíîæåíèÿ ìàòðèö â áëî÷íîì âèäå. 1.4.4 Îáðàòíûå ìàòðèöû Êàê ìû ìîãëè çàìåòèòü ðàíüøå, ïðè ôîðìóëèðîâêå ñâîéñòâ ìàòðè÷íûõ îïåðàöèé ìû èñêëþ÷èëè ñóùåñòâîâàíèå îáðàòíîãî ýëåìåíòà îòíîñèòåëüíî óìíîæåíèÿ. Ýòî çíà÷èò, ÷òî äëÿ ïðî- A â îáùåì ñëó÷àå íå ñóùåñòâóåò ìàòðèö ÃR è ÃL òàêèõ, ÷òî AÃR = E ÃL A = E. Åñëè áû òàêèå ìàòðèöû ìîãëè áûòü íàéäåíû, òî îíè íàçûâàëèñü áû ïðàâîé ëåâîé îáðàòíûìè ìàòðèöàìè ê A. Îòäåëüíîå ðàññìîòðåíèå ïðàâîé è ëåâîé îáðàòíûõ èçâîëüíîé ìàòðèöû èëè è ìàòðèö âûçâàíî òåì, ÷òî óìíîæåíèå íåêîììóòàòèâíî.  äàëüíåéøåì ìû áóäåì èññëåäîâàòü âîïðîñ ñóùåñòâîâàíèÿ îáðàòíûõ ìàòðèö òîëüêî äëÿ ñëó÷àÿ êâàäðàòíûõ ìàòðèö, ò.ê. îíè èìåþò íàèáîëüøåå ïðàêòè÷åñêîå è òåîðåòè÷åñêîå çíà÷åíèå. Îïðåäåëåíèå 1.4.4. èëè ÃL A = E, A, ìàòðèöû ÃR è ÃL òàêèå, ÷òî AÃR = E ëåâîé è ïðàâîé îáðàòíûìè ìàòðèöàìè. Åñëè òàêèå ìàòðèöû A íàçûâàåòñÿ îáðàòèìîé èëè íåâûðîæäåííîé (àíãë., non-singular). Äëÿ êâàäðàòíîé ìàòðèöû íàçûâàþòñÿ ñóùåñòâóþò, ìàòðèöà Óòâåðæäåíèå 1.4.5. Åñëè ëåâàÿ è ïðàâàÿ îáðàòíûå ìàòðèöû ñóùåñòâóþò, òî îíè ðàâíû, ÃR = ÃL . Äëÿ îáðàòíîé ìàòðèöû ïðèíÿòî èñïîëüçîâàòü îáîçíà÷åíèå A−1 . Äîêàçàòåëüñòâî. Äîìíîæèì îáå ÷àñòè âûðàæåíèÿ AÃR = E ñâîéñòâî àññîöèàòèâíîñòè óìíîæåíèå, ðàâíî êàê è òîò ôàêò, ÷òî ÃL ÃL A = E: ñëåâà íà è èñïîëüçóåì ÃL (AÃR ) = ÃL E ⇒ ÃR = ÃL . Ñëåäñòâèå 1.4.6. Åñëè êâàäðàòíàÿ ìàòðèöà A íåâûðîæäåíà, òî îíà êîììóòèðóåò ñî ñâîåé îáðàòíîé: AA−1 = A−1 A. Óòâåðæäåíèå 1.4.7. Åñëè îáðàòíàÿ ìàòðèöà ñóùåñòâóåò, òî îíà îïðåäåëåíà îäíîçíà÷íî. 16 Äîêàçàòåëüñòâî. äîìíîæàÿ AA −1 A−1 è Ã−1 . Òîãäà A = E, ïîëó÷àåì Ïóñòü ñóùåñòâóþò äâå ðàçëè÷íûå îáðàòíûå ìàòðèöû =E ñëåâà íà à −1 è ïðèíèìàÿ âî âíèìàíèå, ÷òî à −1 Ã−1 AA−1 = Ã−1 E ⇒ A−1 = Ã−1 . Òåïåðü ìû ìîæåì ñôîðìóëèðîâàòü íåñêîëüêî ïðàâèë, ïîêàçûâàþùèõ, êàê îïåðàöèÿ âçÿòèÿ îáðàòíîé ìàòðèöû ñîîòíîñèòñÿ ñ äðóãèìè ìàòðè÷íûìè îïåðàöèÿìè. Òåîðåìà 1.4.8. Åñëè A è B  íåâûðîæäåííûå êâàäðàòíûå ìàòðèöû, à γ  íåíóëåâîé ñêàëÿð, òî âåðíû ñëåäóþùèå òîæäåñòâà:
−1 1. A−1 = A, 2. (γA)−1 = γ1 A−1 , 3. (AB)−1 = B−1 A−1 ,
−1
> 4. A> = A−1 . Äîêàçàòåëüñòâî. Q = A−1 , E. Äëÿ òîãî, ÷òîáû äîêàçàòü, ÷òî ìàòðèöà äîñòàòî÷íî ïîêàçàòü, ÷òî ïðè óìíîæåíèè Q íà 1. A−1 A = E 2. 1 −1 (γA) γA 3. B−1 A−1 (AB) = B−1 (A−1 A)B = B−1 EB = B−1 B = E,
>
> A−1 A> = AA−1 = E> = E. 4. A Q ÿâëÿåòñÿ îáðàòíîé ê A, ò. å. ñïðàâà èëè ñëåâà ìû ïîëó÷àåì = γ1 γA−1 A = 1 · E = E, Çàìåòèì, ÷òî ïðè äîêàçàòåëüñòâå ïåðå÷èñëåííûõ óòâåðæäåíèé ìû èñïîëüçîâàëè ñâîéñòâà ìàòðè÷íûõ îïåðàöèé è îïåðàöèè òðàíñïîíèðîâàíèÿ. Òàêèì îáðàçîì, åùå íå óìåÿ âû÷èñëÿòü îáðàòíûå ìàòðèöû, ìû óæå ñìîãëè ñôîðìóëèðîâàòü ðÿä âàæíûõ çàêëþ÷åíèé î èõ ñâîéñòâàõ, îñíîâûâàÿñü òîëüêî íà îïðåäåëåíèè è ñâîéñòâàõ ìàòðè÷íûõ îïåðàöèé. Ýòîò ìåòîä àíàëèçà ñèìâîëè÷åñêèõ âûðàæåíèé ìîæåò áûòü ñ óñïåõîì ïðèìåíåí è â áîëåå ñëîæíûõ ñëó÷àÿõ, êàê ïîêàçûâàåò ñëåäóþùèé ðåçóëüòàò (ñì. òàêæå óïðàæíåíèå 11 â êîíöå ðàçäåëà). Óòâåðæäåíèå 1.4.9. Ïóñòü A  êâàäðàòíàÿ áëî÷íàÿ ìàòðèöà âèäà (1.13) òàêàÿ, ÷òî A11 è A22  íåâûðîæäåííûå êâàäðàòíûå ìàòðèöû ïðîèçâîëüíûõ ðàçìåðíîñòåé, à A21 = 0. Òîãäà îáðàòíàÿ ìàòðèöà A−1 èìååò âèä   −1 −1 −1 A | −A A A 12 11 22   11 A−1 =   −1 0 | A22 Äîêàçàòåëüñòâî. Ïðåäñòàâèì îáðàòíóþ ìàòðèöó ÷òîáû ïðîèçâåäåíèå AB B = A−1 â áëî÷íîì âèäå è ïîòðåáóåì, ðàâíÿëîñü åäèíè÷íîé ìàòðèöå (òàêæå çàïèñàííîé â áëî÷íîé ôîð- ìå): 17  A11 |A12 0 |A22  B11 |B12 B21 |B22   = A11 B11 + A12 B21 |A11 B12 + A12 B22 A22 B21 | A22 B22   = E|0 0|E  . Ïðèðàâíèâàÿ ìàòðèöû â ïîñëåäíåì ðàâåíñòâå ïîêîìïîíåíòíî ìû ïîëó÷àåì ñèñòåìó ìàòðè÷íûõ óðàâíåíèé:  A11 B11 + A12 B21 = E    A B + A B = 0 11 12 12 22  A B = 22 21    A22 B22 = E, −1 −1 7 B21 = 0 (äîìíîæèì ñëåâà íà A−1 22 ) , B22 = A22 è B11 = A11 . Íàêîíåö, ìû −1 −1 −1 ìîæåì âûðàçèòü B12 èç âòîðîãî óðàâíåíèÿ, äîìíîæèâ åãî ñëåâà íà A11 : B12 = −A11 A12 A22 . Ïîäñòàâëÿÿ íàéäåííûå áëîêè â B ïîëó÷àåì èñêîìîå âûðàæåíèå. îòêóäà ñëåäóåò, ÷òî Çàäà÷è è âîïðîñû 1. Ïóñòü A, B, C è D  ìàòðèöû ðàçìåðíîñòåé [2×2], [3×2], [2×3] è [3×3], ñîîòâåòñòâåííî. Çàïèøèòå ïî 3 äîïóñòèìûõ è íåäîïóñòèìûõ âûðàæåíèÿ ñ èñïîëüçîâàíèåì ýòèõ ìàòðèö. ßâëÿþòñÿ ëè äîïóñòèìûìè ñëåäóþùèå âûðàæåíèÿ: A2 , B2 , (A + D)B, A + BC , D + BC , BCD, BDC , DCB? 2. Äîêàçàòü, ÷òî åñëè Av = 0 äëÿ ëþáîãî âåêòîðà v, òî A = 0. 3. Âåðíî ëè, ÷òî ñóììà è ïðîèçâåäåíèå äâóõ äèàãîíàëüíûõ ìàòðèö ÿâëÿþòñÿ äèàãîíàëüíûìè ìàòðèöàìè? 4. Çàïèøèòå íåîáõîäèìûå óñëîâèÿ, ïðè êîòîðûõ ìàòðèöû A è B êîììóòèðóþò. Çàïèøèòå äîñòàòî÷íûå óñëîâèÿ, ïðè êîòîðûõ ìàòðèöû A è B êîììóòèðóþò. 5. Äîêàæèòå, ÷òî åñëè A = a0 0b , a 6= b, òî AB = BA âûïîëíÿåòñÿ òîëüêî äëÿ äèàãîíàëüíûõ ìàòðèö B. ×òî èçìåíèòñÿ, åñëè a = b?   6. Çàïèøèòå îáùèé âèä ìàòðèöû B, êîòîðàÿ êîììóòèðóåò ñ ìàòðèöåé A =   0 1 ìàòðèö, êîììóòèðóþùèõ ñ ìàòðèöåé A = 01 −1 0 , ñ ìàòðèöåé A = 1 0 . 1 2 01 . Íàéäèòå îáùèé âèä 7. Âåðíî ëè ÷òî A2 − B2 = (A + B)(A − B)? 8. Âåðíî ëè ÷òî åñëè AB = 0, òî A = 0 èëè B = 0? 9. Ïóñòü ìàòðèöà A ñîäåðæèò ñòðîêó, ñîñòîÿùóþ èç íóëåé. Îáúÿñíèòå, ïî÷åìó ïðîèçâåäåíèå AB òàêæå áóäåò ñîäåðæàòü íóëåâóþ ñòðîêó. Áóäåò ëè ýòî âåðíî òàêæå äëÿ BA? 10. Ïóñòü A  íåâûðîæäåííàÿ ñèììåòðè÷åñêàÿ (êîñî-ñèììåòðè÷åñêàÿ) ìàòðèöà. Äîêàæèòå, ÷òî îáðàòíàÿ ê íåé ìàòðèöà A−1 òàêæå áóäåò ñèììåòðè÷åñêîé (êîñî-ñèììåòðè÷åñêîé). 11∗ . Ïóñòü A  íåâûðîæäåííàÿ ìàòðèöà ðàçìåðà [n × n], à U è V  ïðÿìîóãîëüíûå ìàòðèöû ðàçìåðîâ [n × m] è [m × n]. Ïóñòü, êðîìå òîãî, [m × m]-ìàòðèöà Em + V A−1 U  íåâûðîæäåíà. Äîêàæèòå, ÷òî âåðíî ñëåäóþùåå âûðàæåíèå8 : (A + U V )−1 = A−1 − A−1 U Em + V A−1 U
−1 V A−1 . 12∗ . Íàéäèòå íåíóëåâóþ ìàòðèöó A òàêóþ, ÷òî A2 = 0. Êâàäðàòíàÿ [n × n]- ìàòðèöà A íàçûâàåòñÿ íèëüïîòåíòíîé åñëè ñóùåñòâóåò òàêîå ÷èñëî k ≤ n, ÷òî Ak = 0. 7 Ïðèåì ñ ñîêðàùåíèåì íåêîòîðîé íåâûðîæäåííîé ìàòðèöû ïóòåì å¼ äîìíîæåíèÿ ñëåâà èëè ñïðàâà íà îáðàòíóþ ê íåé ÿâëÿåòñÿ îäíèì èç îñíîâíûõ ïðè îñóùåñòâëåíèè ìàòðè÷íûõ ïðåîáðàçîâàíèé. Íåîáõîäèìî, îäíàêî, îáðàùàòü âíèìàíèå, ÷òî ýòà îïåðàöèÿ âîçìîæíà òîëüêî äëÿ íåâûðîæäåííûõ ìàòðèö. Êðîìå ýòîãî, î÷åíü âàæíî ñëåäèòü çà òåì, ÷òî óìíîæåíèå îñóùåñòâëÿåòñÿ ñ îäíîé è òîé æå ñòîðîíû äëÿ âñåõ ñëàãàåìûõ, âõîäÿùèõ â âûðàæåíèå. 8 Ýòî âûðàæåíèå íàçûâàåòñÿ ôîðìóëîé Øåðìàíà-Ìîðèñîíà-Âóäáåðè (ShermanMorrisonWoodbury formula). Îíà ïîçâîëÿåò ýôôåêòèâíî âû÷èñëèòü îáðàòíóþ ìàòðèöó â òåõ ñëó÷àÿõ, êîãäà A−1 èçâåñòíà, à ðàçìåðíîñòü m êîððåêòèðóþùèõ ìàòðèö U è V äîñòàòî÷íî ìàëà. 18 13∗ . Îáîçíà÷èì ÷åðåç a×,j j -é ñòîëáåö ìàòðèöû A, à ÷åðåç bi,× i-þ ñòðîêó ìàòðèöû B. Äîêàæèòå, ÷òî ïðîèçâåäåíèå äâóõ ìàòðèö A è B ñ ðàçìåðíîñòÿìè [m × n] è [n × k] ìîæåò áûòü çàïèñàíî êàê AB = n X a×,i bi,× . i=1 1.5 1.5.1 LU/LUP-ðàçëîæåíèå Ïðåäñòàâëåíèå ÑËÀÓ â âåêòîðíî-ìàòðè÷íîì âèäå Êàê óæå óïîìèíàëîñü âûøå, èñïîëüçîâàíèå âåêòîðíî-ìàòðè÷íîé çàïèñè ìîæåò ñóùåñòâåííî óïðîñòèòü ïðîöåäóðó ðåøåíèÿ ñèñòåì ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé. Åùå ðàç çàïèøåì ñèñòåìó óðàâíåíèé (1.2): a11 x1 + a12 x2 + · · · + a1n xn = b1 a21 x1 + a22 x2 + · · · + a2n xn = b2 .. . (1.2) am1 x1 + am2 x2 + · · · + amn xn = bm . aij â ôîðìå ìàòðèöû A = [aij ], i = 1, . . . , m, j = 1, . . . , n, à íåèçâåñòíûå è ñâîáîäíûå ÷ëåíû â âèäå ñòîëáöîâ9 x = [x1 , . . . , xn ]> è b = [b1 , . . . , bm ]> , òî ÑËÀÓ (1.2) ìîæåò áûòü êîìïàêòíî ïðåäñòàâëåíà â âèäå Åñëè çàïèñàòü êîýôôèöèåíòû óðàâíåíèé Ax = b. (1.14) Òåïåðü ìû ìîæåì ñôîðìóëèðîâàòü äîñòàòî÷íî î÷åâèäíûé, íî î÷åíü âàæíûé ôàêò, îáîáùàþùèé èäåþ ýëåìåíòàðíûõ îïåðàöèé â ìåòîäå Ãàóññà. Óòâåðæäåíèå 1.5.1. Ïóñòü ìàòðèöà A è âåêòîðû x è b èìåþò ðàçìåðíîñòè, êàê óêà- çàíî âûøå, à T åñòü íåêîòîðàÿ íåâûðîæäåííàÿ ìàòðèöà ðàçìåðíîñòè [m × m]. Òîãäà ìíîæåñòâà ðåøåíèé ñèñòåì Ax = b è TAx = Tb ñîâïàäàþò. Äîêàçàòåëüñòâî. Ïóñòü x ÿâëÿåòñÿ ðåøåíèåì Ax = b. Ïîäñòàâëÿÿ x â TAx = Tb 00 è ó÷èòûâàÿ, ÷òî Ax = b, ïîëó÷àåì òîæäåñòâî Tb ≡ Tb. Íàîáîðîò, ïóñòü x ÿâëÿåòñÿ 00 ðåøåíèåì TAx = Tb. Ïîäñòàâëÿÿ x â ïîñëåäíåå âûðàæåíèå è äîìíîæàÿ îáå ÷àñòè ñëåâà −1 00 íà T , ïîëó÷àåì Ax = b. Çàìåòèì, ÷òî âñå ýëåìåíòàðíûå ïðåîáðàçîâàíèÿ, êîòîðûå ìû ðàññìàòðèâàëè ðàíåå, ìî- ãóò áûòü ïðåäñòàâëåíû êàê ðåçóëüòàò óìíîæåíèÿ íà íåêîòîðóþ íåâûðîæäåííóþ ìàòðèöó T è, òåì ñàìûì, çàïèñàíû â âåêòîðíî-ìàòðè÷íîì âèäå. Îá ýòîì ìû áóäåì ãîâîðèòü â ïîä- ðàçäåëàõ 1.5.2 è 1.5.4. T, à = TA èìååò íåêîòîðûé ñïåöèàëü- Òåïåðü çàáåæèì íåìíîãî âïåðåä è ïðåäïîëîæèì, ÷òî ìû íàøëè òàêîå ïðåîáðàçîâàíèå ÷òî ìàòðèöà êîýôôèöèåíòîâ ïðåîáðàçîâàííîé ñèñòåìû íûé âèä (íàïðèìåð, ÿâëÿåòñÿ òðåóãîëüíîé ìàòðèöåé). Çàïèøåì ïðåîáðàçîâàííóþ ñèñòåìó óðàâíåíèé: Ãx = Tb. Äîìíîæàÿ ýòó ñèñòåìó ñëåâà íà T−1 , ïîëó÷èì T−1 Ãx = b. Òàêèì A çàïèñûâàåòñÿ â â âèäå ïðîèçâåäåíèÿ äâóõ ìàòðèö, ïðåäïîëîæèòåëüíî áîëåå ïðîñòîãî âèäà: A = T−1 Ã. Ýòîò ïîäõîä îáðàçîì ìû âåðíóëèñü ê èñõîäíîé ñèñòåìå, íî òåïåðü ìàòðèöà ëåæèò â îñíîâå LU-ðàçëîæåíèÿ, êîòîðîå ìû áóäåì ðàññìàòðèâàòü â ïîäðàçäåëå 1.5.3. 9 Îáðàòèòå âíèìàíèå: çàïèñü ñòîëáöà â âèäå òðàíñïîíèðîâàííîé ñòðîêè ÷àñòî èñïîëüçóåòñÿ òîãäà, êîãäà ìû íå õîòèì çàãðîìîæäàòü òåêñò âåðòèêàëüíûì èçîáðàæåíèåì ñòîëáöîâ. 19 Ëèíåéíûå ìàòðè÷íûå óðàâíåíèÿ∗ . Ïåðåä òåì, êàê ìû ïåðåéäåì ê ôîðìàëèçàöèè ìå- òîäà Ãàóññà, çàìåòèì, ÷òî óðàâíåíèÿ (1.14) ìîãóò áûòü îáîáùåíû íà ñëó÷àé, êîãäà íåèçâåñòíûå è ñâîáîäíûå ÷ëåíû ïðåäñòàâëåíû â âèäå ìàòðèö. Òîãäà ìû èìååì äåëî ñ ìàòðè÷íûìè óðàâåíèÿìè AX = B. Ïóñòü ìàòðèöû A, X è ëèíåéíûìè âèäà (1.15) B èìåþò ðàçìåðíîñòè, ñîîòâåòñòâåííî, [m×n], [n×q] è [m×q]. Òîãäà mq ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé ñ óðàâíåíèå (1.15) ìîæåò áûòü ñâåäåíî ê ñèñòåìå nq íåèçâåñòíûìè. Ïîïðîáóåì ïðåäñòàâèòü óðàâíåíèå (1.15) â âèäå (1.14). Âñïîìíèì, ÷òî ïðîèçâåäåíèå ìîæíî ðàññìàòðèâàòü ïî ñòîëáöàì (ñì. (1.9)): äëÿ êàæäîãî i = 1, . . . , q [AX]×,i = AX×,i = B×,i . AX Òàêèì îáðàçîì, ìû èìååì îáû÷íóþ ñèñòåìó óðàâíåíèé âèäà (1.14). Ñîáåðåì âñå q ñèñòåì â îäíó, ïîëüçóÿñü ïðàâèëàìè ìàòðè÷íûõ îïåðàöèé:  A   .. .     B×,1 X×,1   ..   ..   .  =  . . A (1.16) B×,q X×,q Òàêîãî ðîäà ïðåîáðàçîâàíèÿ ìîãóò áûòü êîìïàêòíî çàïèñàíû ñ ïîìîùüþ ñïåöèàëüíûõ âåêòîðíî-ìàòðè÷íûõ îïåðàöèé. • âåêòîðèçàöèè, îáîçíà÷àåòñÿ vec(·), çàêëþ÷àåòñÿ â ïðåîáðàçîâàíèè ìàòðèöû [k × l] â âåêòîð ðàçìåðà [kl × 1] ïóòåì âåðòèêàëüíîãî ñîñòàâëåíèÿ ñòîëáöîâ M:   M×,1   vec(M ) =  ...  . Îïåðàöèÿ M ðàçìåðà ìàòðèöû M×,l • Ïðîèçâåäåíèå Êðîíåêåðà10 äâóõ ìàòðèö A è B ðàçìåðíîñòåé [k×n] è [m×r] îáîçíà÷àåòñÿ êàê A⊗B è ïðåäñòàâëÿåò ñîáîé áëî÷íóþ ìàòðèöó ðàçìåðíîñòè [km×nr] ñëåäóþùåãî âèäà:  a11 B ... .. . a1,n B ak1 B . . . ak,n B  A⊗B=   . Ñ èñïîëüçîâàíèåì ââåäåííûõ îïåðàöèé ìû ìîæåì îêîí÷àòåëüíî âåêòîðèçîâàòü ìàòðè÷íîå óðàâíåíèå (1.15) è çàïèñàòü åãî â âèäå (1.14) êàê Ãx = b, ãäå x = vec(X), b = vec(B) à = Eq ⊗ A. 10 Leopold Kronecker (1823  1891). Èçâåñòåí âûðàæåíèåì ¾Áîã ñîçäàë öåëûå ÷èñëà, âñ¼ îñòàëüíîå  äåëî ðóê ÷åëîâåêà¿. Áûë ñòîðîííèêîì êîíñòðóêòèâíîé ìàòåìàòèêè, ò. å. ïðèçíàâàë òîëüêî òî, ÷òî ìîæíî âû÷èñëèòü.  ñèëó ýòîãî Êðîíåêåð íå ñìîã ïðèíÿòü òåîðèþ óïîðÿäî÷åííûõ áåñêîíå÷íûõ ìíîæåñòâ Ãåîðãà Êàíòîðà è àêòèâíî ïðîòèâîäåéñòâîâàë êàê êàðüåðíîìó ðîñòó Êàíòîðà, òàê è åãî ïîïûòêàì îïóáëèêîâàòü ñâîè ðåçóëüòàòû. Àêòèâíàÿ êðèòèêà ñî ñòîðîíû Êðîíåêåðà (êàê, âïðî÷åì, è äðóãèõ âûäàþùèõñÿ ìàòåìàòèêîâ, òàêèõ, êàê Àíðè Ïóàíêàðå è Ãåðìàí Âàéëü) âî ìíîãîì ñïîñîáñòâîâàëà òîìó, ÷òî Êàíòîð íå äîâåë äî êîíöà ñâîþ òåîðèþ òðàíñôèíèòíûõ ìíîæåñòâ è â êîíöå æèçíè îòîøåë îò ìàòåìàòè÷åñêèõ èññëåäîâàíèé. 20 Çàäà÷è è âîïðîñû 1. Äàíà ÑËÀÓ 2x1 + x2 = 4 (1.17) x1 − 3x2 = 2. (a) Çàïèøèòå ñèñòåìó (1.17) â âåêòîðíî-ìàòðè÷íîì âèäå. (b) Óìíîæüòå ïîëó÷åííîå óðàâíåíèå âèäà Ax = b íà T = . 1 2 01 (c) Çàïèøèòå ïîëó÷åííîå âûðàæåíèå â âèäå ñèñòåìû ëèíåéíûõ óðàâíåíèé. Áóäóò ëè ñîâïàäàòü ðåøåíèÿ íîâîé è èñõîäíîé ñèñòåì? h i 1 −2 (d) Òåïåðü ïðîäåëàéòå òî æå ñàìîå äëÿ ìàòðèöû T = −2 4 . Áóäóò ëè ñîâïàäàòü ðåøåíèÿ ïðåîáðàçîâàííîé ñèñòåìû è ñèñòåìû (1.17)? Åñëè íåò, òî ïî÷åìó? 2∗ . Ïóñòü A, B, C è X  [2 × 2] ìàòðèöû. Ðàññìîòðèòå ìàòðè÷íîå àëãåáðàè÷åñêîå óðàâíåíèå AX + XB = C , ãäå X  ìàòðèöà íåèçâåñòíûõ. Ýòî óðàâíåíèå íàçûâàåòñÿ óðàâíåíèåì Ñèëüâåñòðà11 . Çàïèøèòå ýòî óðàâíåíèå â âèäå ñèñòåìû ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé è â âåêòîðíî-ìàòðè÷íîì âèäå: Ãx = c, ãäå x = vec(X). Ïîïðîáóéòå îáîáùèòü ïîëó÷èâøèéñÿ ðåçóëüòàò íà ñëó÷àé ïðîèçâîëüíûõ (íî ñîãëàñîâàííûõ) ðàçìåðíîñòåé. 1.5.2 Ìàòðèöû ýëåìåíòàðíûõ îïåðàöèé  ðàçäåëå 1.3 ìû îïðåäåëèëè 3 ýëåìåíòàðíûå îïåðàöèè, ïðèìåíåíèå êîòîðûõ ê ÑËÀÓ (1.2) ïðèâîäèò ê ýêâèâàëåíòíîé ÑËÀÓ. Ýòî óìíîæåíèå íà íåíóëåâîå ÷èñëî (1.3), ñëîæåíèå ñòðîêè ñ äðóãîé ñòðîêîé, óìíîæåííîé íà ÷èñëî (1.6) è ïåðåñòàíîâêà äâóõ ñòðîê (1.5).  ýòîì ðàçäåëå ìû ðàñìîòðèì ïåðâûå äâå îïåðàöèè: [k+1] [k] Eqi = αEqi . [k+1] = Eqi + δEqq[k] , Eqi (1.3) [k] (1.6) îäíàêî òåïåðü ñôîðìóëèðóåì èõ ïðèìåíèòåëüíî ê âåêòîðíî-ìàòðè÷íîé çàïèñè (1.14). Ýòè îïåðàöèè ïðèìåíÿþòñÿ ê îòäåëüíûì óðàâíåíèÿì, ÷òî â ìàòðè÷íîé çàïèñè îçíà÷àåò, ÷òî îíè äåéñòâóþò íà ñòðîêè. Òàêèì îáðàçîì, ñîîòâåòñòâóþùèå ìàòðèöû äîëæíû äåéñòâîâàòü íà ñèñòåìó Ax = b ñëåâà (âñïîìíèì ïðàâèëî óìíîæåíèÿ äâóõ ìàòðèö (1.9)). Íà÷íåì ñ îïåðàöèè (1.3). Î÷åâèäíî, ÷òî â ðåçóëüòàòå ïðèìåíåíèÿ ýòîé îïåðàöèè âñå ñòðîêè çà èñêëþ÷åíèåì i-é äîëæíû îñòàòüñÿ íåèçìåííûìè, à ýëåìåíòû i-é ñòðîêè äîëæíû áûòü äîìíîæåíû íà α 6= 0. Ýòà îïåðàöèÿ îñóùåñòâëÿåòñÿ ìàòðèöåé âèäà T(i) α  1    =    .. . α .. .     ,    1 êîòîðàÿ îòëè÷àåòñÿ îò åäèíè÷íîé òîëüêî ýëåìåíòîì â ïîçèöèè (i, i), ðàâíûì α. Òåïåðü ðàñ- ñìîòðèì îïåðàöèþ (1.6). Òàê æå, êàê è â ïðåäûäóùåì ñëó÷àå, äåéñòâèå ýòîé îïåðàöèè 11 James Joseph Sylvester (1814  1897). Ââåë â îáîðîò òåðìèí ìàòðèöà, îò ëàò. matrix  ÷ðåâî, óòðîáà. Äëÿ ìàòåìàòèêà ñåðåäèíû XIX âåêà êâàäðàòíûé ìàññèâ ÷èñåë îáÿçàòåëüíî èìåë ÷èñëåííîå çíà÷åíèå  åãî îïðåäåëèòåëü (î îïðåäåëèòåëå ñì â ðàçäåëå 1.7) è íå ìîã áûòü èíòåðïðåòèðîâàí íèêàê èíà÷å. Åñëè ýòî áûë ïðÿìîóãîëüíûé ìàññèâ, òî îí ¾ïîðîæäàë¿ íàáîð ÷èñåë, êîòîðûå ÿâëÿëèñü îïðåäåëèòåëÿìè ïîäìàòðèö, âõîäÿùèõ â ýòîò ìàññèâ. Ñàì Ñèëüâåñòåð ïèñàë îá ýòîì òàê: ¾I have in previous papers dened a Matrix as a rectangular array of terms, out of which dierent systems of determinants may be engendered as from the womb of a common parent¿. 21 ðàñïðîñòðàíÿåòñÿ òîëüêî íà i-þ ñòðîêó, â òî âðåìÿ êàê îñòàëüíûå ñòðîêè îñòàþòñÿ íåèç- ìåííûìè. Ñîîòâåòñòâåííî, ìàòðèöà îïåðàöèè (1.6) èìååò âèä (äëÿ  (i,q) Tδ i > q ):  1 ..     = . . .     0   .     1 . 1 ... 1 δ .. . Ýòà ìàòðèöà èìååò åäèíè÷íóþ ãëàâíóþ äèàãîíàëü è åäèíñòâåííûé íåíóëåâîé âíåäèàãî- (i, q), i 6= q , ðàâíûé δ . (i) Çàìåòèì, ÷òî ìàòðèöà Tα  äèàãîíàëüíàÿ, à ìàòðèöà íàëüíûé ýëåìåíò â ïîçèöèè ýëåìåíòàìè íà ãëàâíîé äèàãîíàëè (ò. å. íèæíåé òðåóãîëüíîé åñëè q q.  íåâûðîæäåííûå.  êà÷åñòâå óïðàæíåíèÿ ÷èòàòåëþ ïðåäëàãàåòñÿ ïðîâåðèòü, ÷òî ñîîòâåòñòâóþùèå èì îáðàòíûå ìàòðèöû óäîâëåòâîðÿþò ñëåäóþùèì âûðàæåíèÿì: h 1.5.3 T(i) α i−1 (i) = T1 , α h (i,q) Tδ i−1 (i,q) = T(−δ) . LU-ðàçëîæåíèå Òåïåðü ìû ãîòîâû ôîðìàëüíî îïèñàòü ìåòîä Ãàóññà ðåøåíèÿ ñèñòåìû ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé, çàäàííîé â âåêòîðíî-ìàòðè÷íîì âèäå. Äëÿ íà÷àëà ìû ðàññìîòðèì îäèí ÷àñòíûé ñëó÷àé, à íèæå îáîáùèì åãî íà ñëó÷àé ïðîèçâîëüíûõ ÑËÀÓ. À èìåííî, A1. ìû áóäåì ðàññìàòðèâàòü ñëó÷àé, êîãäà ðåàëèçàöèÿ ìåòîäà Ãàóññà íå òðåáóåò ïåðåñòàíîâîê óðàâíåíèé. Çàìå÷àíèå 1.5.1. Ó íàñ íåò êðèòåðèåâ, ïîçâîëÿþùèõ àïðèîðíî îïðåäåëèòü, áóäåò ëè íà- øà ñèñòåìà óäîâëåòâîðÿòü ýòîìó óñëîâèþ, îäíàêî ìû ìîæåì âûÿñíèòü, âûïîëíÿåòñÿ ëè ýòî óñëîâèå, â ïðîöåññå ðåøåíèÿ. Åñëè â õîäå ðåøåíèÿ ñèñòåìû ïîÿâèòñÿ íåîáõîäèìîñòü â ïåðåñòàíîâêå ñòðîê, òî ìû ïåðåéä¼ì ê îáùåìó ñëó÷àþ, îïèñàííîìó â ïîäðàçäåëå 1.5.4 è äàëåå. Öåëü ìåòîäà Ãàóññà çàêëþ÷àåòñÿ â ïðèâåäåíèè ñèñòåìû óðàâíåíèé, à òåì ñàìûì è ìàòðèöû A ê òàê íàçûâàåìîìó ñòóïåí÷àòîìó âèäó ïî ñòðîêàì (àíãë., row echelon form, REF). Îïðåäåëåíèå 1.5.1. Ìàòðèöà A íàçûâàåòñÿ ìàòðèöåé ñòóïåí÷àòîãî âèäà ïî ñòðîêàì åñëè 1. âñå íåíóëåâûå ñòðîêè (èìåþùèå ïî êðàéíåé ìåðå îäèí íåíóëåâîé ýëåìåíò) ðàñïîëàãàþòñÿ íàä âñåìè ÷èñòî íóëåâûìè ñòðîêàìè; 2. âåäóùèé ýëåìåíò (ïåðâûé íåíóëåâîé ýëåìåíò ñòðîêè ïðè îòñ÷¼òå ñëåâà íàïðàâî) êàæäîé íåíóëåâîé ñòðîêè ðàñïîëàãàåòñÿ ñòðîãî ïðàâåå âåäóùåãî ýëåìåíòà â ñòðîêå, ðàñïîëîæåííîé âûøå äàííîé. 22 Çàìåòèì, ÷òî ìàòðèöà ñòóïåí÷àòîãî âèäà ïî ñòðîêàì íå îáÿçàòåëüíî äîëæíà áûòü êâàäðàòíîé. Íèæå ïðèâåäåíû íåñêîëüêî ïðèìåðîâ ìàòðèö, çàïèñàííûõ â âèäå REF:  1 0  0  0 −2 2 1 , 0 −3 0 0 A Ïðèâåäåíèå ìàòðèöû  1 0 −2 1  0 , 1  1 0  0 −1 3 0.1 1  0 . 1 1 ê âèäó REF çàêëþ÷àåòñÿ â å¼ óìíîæåíèè ñëåâà íà ìàòðèöû ýëåìåíòàðíûõ îïåðàöèé. Ìû áóäåì ðàññìàòðèâàòü òîëüêî îïåðàöèè (1.6). Îïåðàöèè (1.3) îáû÷íî èñïîëüçóþòñÿ äëÿ íîðìèðîâêè âåäóùèõ ýëåìåíòîâ â ñòðîêàõ ïðåîáðàçîâàííîé ìàòðèöû. Ìû íå áóäåì íàêëàäûâàòü íèêàêèõ îãðàíè÷åíèé íà âåäóùèå ýëåìåíòû, ÷òî ïîçâîëèò íàì îáîéòèñü òîëüêî îïåðàöèÿìè âòîðîãî òèïà. Ïóñòü Tj , j = 1, . . . , k ,  íàáîð ìàòðèö òèïà (i,q) Tδ , i > q, ñîîòâåòñòâóþùèé òðåáóåìîìó ÷èñëó ýëåìåíòàðíûõ îïåðàöèé. Çàïèøåì ðåçóëüòàò ïðèìåíåíèÿ ýòèõ îïåðàöèé â ìàòðè÷íîì âèäå: Tk . . . T1 A = AREF . Ïàìÿòóÿ, ÷òî ìàòðèöû T−1 k , ..., T−1 1 , Tj îáðàòèìû, ìû ìîæåì óìíîæèòü −1 A = T−1 1 . . . Tk AREF . (i,q) Íàêîíåö, âñïîìíèì, ÷òî ìàòðèöû, îáðàòíûå ê ìàòðèöàì ýëåìåíòàðíûõ îïåðàöèé òèïà Tδ ïîëó÷åííîå âûðàæåíèå ñëåâà íà òåì ñàìûì ïîëó÷àÿ ÿâëÿþòñÿ óíèïîòåíòíûìè íèæíèìè òðåóãîëüíûìè ìàòðèöàìè. Ñîãëàñíî Òåîðåìå 1.4.3, ïðîèçâåäåíèå óíèïîòåíòíûõ òðåóãîëüíûõ ìàòðèö ÿâëÿåòñÿ óíèïîòåíòíîé ìàòðèöåé. Òàê ìû äîêàçàëè ñëåäóþùèé ðåçóëüòàò: Òåîðåìà 1.5.2. Ïðè âûïîëíåíèè ïðåäïîëîæåíèÿ A1, ëþáàÿ ïðÿìîóãîëüíàÿ ìàòðèöà A ìîæåò áûòü ïðåäñòàâëåíà â âèäå A = LAREF , ãäå AREF  ìàòðèöà ñòóïåí÷àòîãî âèäà ïî ñòðîêàì, à L  óíèïîòåíòíàÿ íèæíÿÿ òðåóãîëüíàÿ ìàòðèöà. Èç îïðåäåëåíèÿ REF-ìàòðèöû ìîæíî ñäåëàòü âûâîä, ÷òî REF-ôîðìà êâàäðàòíîé ìàòðèöû ÿâëÿåòñÿ âåðõíåé òðåóãîëüíîé ìàòðèöåé. Òàê ìû ïîëó÷àåì ñëåäóþùåå âàæíîå ñëåäñòâèå. Ñëåäñòâèå 1.5.3. Ïðè âûïîëíåíèè ïðåäïîëîæåíèÿ A1, ëþáàÿ êâàäðàòíàÿ ìàòðèöà A ìîæåò áûòü ïðåäñòàâëåíà â âèäå A = LU, (1.18) ãäå L  íåâûðîæäåííàÿ óíèïîòåíòíàÿ íèæíÿÿ òðåóãîëüíàÿ ìàòðèöà, à U  âåðõíÿÿ òðåóãîëüíàÿ ìàòðèöà (â îáùåì ñëó÷àå íå óíèïîòåíòíàÿ). Ïðåäñòàâëåíèå êâàäðàòíîé ìàòðèöû â âèäå ïðîèçâåäåíèÿ íèæíåé è âåðõíåé òðåóãîëüíûõ ìàòðèö íàçûâàåòñÿ ÿçûêà è ñîîòâåòñòâóþò LU-ðàçëîæåíèåì (îáîçíà÷åíèÿ L è Lower and Upper triangular matrices). Ïðàêòè÷åñêèå àñïåêòû ïðèìåíåíèÿ LU-ðàçëîæåíèÿ. U ïðîèñõîäÿò èç àíãëèéñêîãî Ñõåìàòè÷íî, àëãîðèòì ïðèìå- íåíèÿ ìåòîäà Ãàóññà ìîæåò áûòü ïðåäñòàâëåí êàê ïîñëåäîâàòåëüíîñòü ïðîõîäîâ, ïðè÷åì êàæäûé ïðîõîä ìåòîäà Ãàóññà çàêëþ÷àåòñÿ â ñëåäóþùåì: 1. Âûáðàòü âåäóùèé ýëåìåíò. Ïóñòü ýòî áóäåò ýëåìåíò â ïîçèöèè 2. Îáíóëèòü ýëåìåíòû â ïîçèöèÿõ (i, r), i > q , ò. å. ïîä âåäóùèì ýëåìåíòîì. Ïðèìåíåíèå ýòîé ñõåìû ñâîäèòñÿ ê óìíîæåíèþ ìàòðèöû 1, . . . , n, à δi (q, r). A íà ìàòðèöû (i,q) Tδi , ãäå i=q+  íåêîòîðûå êîíñòàíòû. Ñôîðìóëèðóåì ñëåäóþùèé ïîëåçíûé ðåçóëüòàò. 23 Óòâåðæäåíèå 1.5.4. Äëÿ ëþáûõ i, j > q (i, j < q ) è ïðîèçâîëüíûõ δi , δj ∈ F âûïîëíÿåòñÿ (i,q) (j,q) Tδi Tδj Äîêàçàòåëüñòâî. Ïóñòü A (j,q) (i,q) = Tδj Tδi .  íåêîòîðàÿ íåâûðîæäåííàÿ ìàòðèöà ïîäõîäÿùåé ðàçìåðíî- ñòè. Èìååì (i,q) (j,q) (j,q) (i,q) Tδi Tδj A = Tδj Tδi A, òàê êàê ìàòðèöû (i,q) Tδi æàÿ (1.19) ñïðàâà íà Çàìå÷àíèå 1.5.2. è (j,q) Tδj A−1 (1.19) íåçàâèñèìî äðóã îò äðóãà äåéñòâóþò íà ñòðîêè i è j . Äîìíî- ïîëó÷àåì òðåáóåìûé ðåçóëüòàò. Îáðàòèòå âíèìàíèå íà äîêàçàòåëüñòâî óòâåðæäåíèÿ 1.5.4. Âìåñòî òîãî, ÷òîáû ïðîâåðÿòü êîììóòàòèâíîñòü óìíîæåíèÿ äâóõ ìàòðèö, ìû ïîêàçàëè, ÷òî ðåçóëüòàò èõ äåéñòâèÿ íà íåêîòîðóþ íåâûðîæäåííóþ ìàòðèöó íå çàâèñèò îò òîãî, â êàêîì ïîðÿäêå îíè ïðèìåíÿëèñü. Ýòî î÷åíü ïðîäóêòèâíûé ïîäõîä, êîòîðûé íàõîäèò ñâîå ïðèìåíåíèå äàëåêî çà ïðåäåëàìè òåîðèè ìàòðèö. Íàêîíåö çàìåòèì, ÷òî ïðîõîä ìåòîäà Ãàóññà ìîæåò áûòü öåëèêîì îïèñàí îäíîé ìàòðèöåé, êîòîðóþ ìû áóäåì îáîçíà÷àòü (·,q) Tδ  (·,q) Tδ Ïðèìåð 1.5.1 1.5.4 (LU-ðàçëîæåíèå) : 1     =     ..     .     . 1 δi .. . 1 .. . δn  (1.20) 1 . Äîáàâèòü! Ìàòðèöû ïåðåñòàíîâîê Äî ñèõ ïîð ìû ðàññìàòðèâàëè ðåàëèçàöèþ ìåòîäà Ãàóññà ñ èñïîëüçîâàíèåì òîëüêî äâóõ òèïîâ ýëåìåíòàðíûõ îïåðàöèé. Òðåòüÿ ýëåìåíòàðíàÿ îïåðàöèÿ çàêëþ÷àåòñÿ â ïåðåñòàíîâêå äâóõ ñòðîê è ðåàëèçóåòñÿ ñ ïîìîùüþ ò. í. ìàòðèö ïåðåñòàíîâîê. Îïðåäåëåíèå 1.5.2. Êâàäðàòíàÿ ìàòðèöà P ðàçìåðíîñòè [n × n] íàçûâàåòñÿ ìàòðèöåé ïåðåñòàíîâêè åñëè â êàæäîé åå ñòðîêå è ñòîëáöå íàõîäèòñÿ òîëüêî îäíà åäèíèöà, à îñòàëüíûå ýëåìåíòû ðàâíû íóëþ. [3 × 3] (êàê ñëåäóåò èç òîãî, 6: 3! = 6):        0 0 1 0 1 0 0 0 1 1 , 0 1 0 , 0 0 1 è 1 0 0 . 1 0 0 1 0 0 0 1 0 Ñóùåñòâóåò âñåãî 6 ìàòðèö ïåðåñòàíîâîê ðàçìåðíîñòè ÷òî ÷èñëî ïåðåñòàíîâîê òðåõ ýëåìåíòîâ ðàâíî  1 0 1   0 , 1 1 1   1 0 , 0 1 1 A [n × q], à P  ìàòðèöà ïåðåñòàíîâêè ðàçìåðíîñòè [n × n] ñ (1, j1 ), (2, j2 ), . . . , (n, jn ), ïðè÷åì âñå èíäåêñû ji ïîïàðíî ðàçëè÷íû: Ïîñìîòðèì, êàê ìàòðèöû ïåðåñòàíîâîê äåéñòâóþò ïðè óìíîæåíèè ñëåâà è ñïðàâà. Ïóñòü  íåêîòîðàÿ ìàòðèöó ðàçìåðíîñòè åäèíèöàìè íà ïîçèöèÿõ 24 jk 6= jm , ∀k 6= m. Ðàññìîòðèì ïðîèçâåäåíèå PA è âñïîìíèì ïðàâèëî óìíîæåíèÿ äâóõ ìàòðèö (1.9): n X [PA]1,× = p1,k ak,× = aj1 ,× . k=1 Ïîëó÷àåì, ÷òî ïåðâàÿ ñòðîêà ïðîèçâåäåíèÿ ñòðîêó ïðîèçâåäåíèÿ çàïèñûâàåòñÿ Ïðè óìíîæåíèè íà ìàòðèöó P j2 -ÿ PA ñîäåðæèò j1 -þ ñòðîêó ìàòðèöû A, âî âòîðóÿ A è òàê äàëåå. ñòðîêà ìàòðèöû ñïðàâà, ïåðåñòàíîâêè ïðèìåíÿþòñÿ ê ñòîëáöàì. Äåòàëüíîå èçó÷åíèå äåéñòâèÿ ìàòðèöû ïåðåñòàíîâîê ïðè óìíîæåíèè ñïðàâà îñòàâëÿåòñÿ ÷èòàòåëþ â êà÷åñòâå óïðàæíåíèÿ. P íà  0  a3 ,  0 1  êà÷åñòâå ïðèìåðà ðàññìîòðèì óìíîæåíèå ìàòðèöû  a1 a2 a3   0 a4  0 1 Óïðàæíåíèå 1.5.1. ñäâèãà. 1 1   0  = a4 1 a1 Ðàññìîòðåííàÿ âûøå ìàòðèöà P 1 íàçûâàåòñÿ 1     b2 b1 b2  b3  0   =  . 1 b3  b4  b1 b4 ìàòðèöåé öèêëè÷åñêîãî Îáúÿñíèòå ïî÷åìó. Äåéñòâóåò ëè îíà îäèíàêîâî íà ñòðîêè è ñòîëáöû? Çàïèøèòå [5 × 5]. Çàïèøèòå ìàòðèöó ïåðåñòàíîâêè ðàçìåð- ìàòðèöó öèêëè÷åñêîãî ñäâèãà ðàçìåðíîñòè íîñòè a2 ñòðîêó è íà ñòîëáåö: [6 × 6], êîòîðàÿ ìåíÿåò ìåñòàìè ñòîÿùèå ðÿäîì ÷åòíûå è íå÷åòíûå ñòðîêè/ñòîëáöû. Ìàòðèöû ïåðåñòàíîâîê îáëàäàþò ñëåäóþùèìè âàæíûìè ñâîéñòâàìè. Òåîðåìà 1.5.5. Ïðîèçâåäåíèå äâóõ ìàòðèö ïåðåñòàíîâîê åñòü ìàòðèöà ïåðåñòàíîâêè. Äîêàçàòåëüñòâî. â k -ì ýëåìåíòó. ýëåìåíòû k 1 äî n. Ïî îïðåäåëåíèþ, k -é ñòðîêå ìàòðèöû Π åñòü ðîâíî ïî îäíîìó åäèíè÷íîìó Ïóñòü ýòî áóäóò pik è πkj . Ñîîòâåòñòâåííî, èìååì [PΠ]ij = 1. Ðàññìîòðèì äðóãèå ïðîèçâåäåíèÿ PΠ, ðàñïîëîæåííûå â j -ì ñòîëáöå: Ïóñòü ñòîëáöå ìàòðèöû P  íåêîòîðîå ïðîèçâîëüíîå ÷èñëî îò è â [PΠ]lj = n X plk πkj , l 6= i. k=1 Ïî îïðåäåëåíèþ, äëÿ âñåõ l 6= i, plk = 0, ïîêàçûâàåì, ÷òî ðàíû íóëþ âñå ýëåìåíòû ñëåäîâàòåëüíî i-é [PΠ]lj = 0 ∀l 6= i. Àíàëîãè÷íî ñòðîêè ïðîèçâåäåíèÿ, îòëè÷íûå îò (i, j)-ãî ýëåìåíòà. Òåîðåìà 1.5.6. Äëÿ êàæäîé ìàòðèöû ïåðåñòàíîâêè P âåðíî P−1 = P> . Äîêàçàòåëüñòâî. Çàïèøåì ïðîèçâåäåíèå ìàòðèöû ïåðåñòàíîâêè è òðàíñïîíèðîâàííîé ìàòðèöû: n X  > PP i,j = pik pjk . k=1 Çàôèêñèðóåì k0 íîâîê, äëÿ âñåõ îñòàëüíûõ çíà÷åíèé æèòåëü.  ñòîëáöå j 6= i. pik0 = 1. Ïî îïðåäåëåíèþ ìàòðèöû ïåðåñòàpik = 0. Òåïåðü ðàññìîòðèì âòîðîé ñîìíîîäèí íåíóëåâîé ýëåìåíò, ñëåäîâàòåëüíî pjk0 = 0, òàêîå, ÷òî â âûðàæåíèè âûøå k0 k 6= k 0 ìîæåò áûòü òîëüêî èìååì Èòàê, ïîëó÷àåì, (  > PP i,j = ò. å., PP> = E ⇒ P> = P−1 . 25 1, i = j , 0, i = 6 j Î÷åâèäíûé ÷àñòíûé ñëó÷àé ïðåäûäóùåãî ðåçóëüòàòà çàêëþ÷àåòñÿ â òîì, ÷òî äëÿ ëþáûõ i è k , ìàòðèöà ïåðåñòàíîâêè i-é è k -é ñòðîê (ñòîëáöîâ) ÿâëÿåòñÿ îáðàòíîé ê Pik Pik = E. Äîêàçàòåëüñòâî ýòîãî ôàêòà îñòàâëÿåòñÿ â êà÷åñòâå óïðàæíåíèÿ. ñàìîé ñåáå: Äëÿ íàøèõ öåëåé, ýòîé èíôîðìàöèè î ìàòðèöàõ ïåðåñòàíîâîê íàì ïîêà äîñòàòî÷íî. Ìû âåðíåìñÿ ê ýòîé òåìå â ïîäðàçäåëå 1.7.2, ãäå äàäèì áîëåå ôîðìàëüíîå îïðåäåëåíèå ìíîæåñòâó ïåðåñòàíîâîê è åãî ñâîéñòâàì. 1.5.5 LUP-ðàçëîæåíèå  îáùåì ñëó÷àå, ðåàëèçàöèÿ ìåòîäà Ãàóññà òðåáóåò èñïîëüçîâàòü îïåðàöèè ïåðåñòàíîâîê. Òàêàÿ íåîáõîäèìîñòü âîçíèêàåò â òîì ñëó÷àå, êîãäà íà ïîçèöèè (q, r), ãäå ìû îæèäàåì óâè- äåòü âåäóùèé ýëåìåíò, ñòîèò íîëü. Ïðîñìàòðèâàÿ êîýôôèöèåíòû íèæå ïî ñòîëáöó ìû íàõîäèì ïåðâûé íåíóëåâîé ýëåìåíò â ïîçèöèè q -é è m-é (m, r), ãäå m>q è îñóùåñòâëÿåì ïåðåñòàíîâêó ñòðîê ïóòåì äîìíîæåíèÿ íà ìàòðèöó ïåðåñòàíîâêè Pqm . Òåïåðü â ïîçèöèè (q, r) ñòîèò íåíóëåâîé ýëåìåíò è ìû ìîæåì èñïîëüçîâàòü åãî äëÿ îáíóëåíèÿ âñåõ (íåíóëåâûõ) ýëåìåíòîâ, ñòîÿùèõ íèæå â ñòîëáöå r. Òàêèì îáðàçîì, ðåçóëüòàò ðàáîòû ìåòîäà Ãàóññà â îáùåì ñëó÷àå ìîæåò áûòü ïðåäñòàâëåí â âèäå óìíîæåíèÿ ìàòðèöû è ìàòðèö òèïà (·,q) Tδ A íà ÷åðåäóþùóþñÿ ïîñëåäîâàòåëüíîñòü ìàòðèö ïåðåñòàíîâîê : Tk Pk . . . P2 T1 P1 A = AREF , ãäå íåêîòîðûå ìàòðèöû ïåðåñòàíîâîê Pi (1.21) ìîãóò áûòü ðàâíû åäèíè÷íûì ìàòðèöàì åñëè íà ñîîòâåòñòâóþùåì øàãå ïåðåñòàíîâêà íå òðåáóåòñÿ. Çàìåòèì, ÷òî åñëè íà íåêîòîðîì ýòàïå ïðèìåíåíèÿ ìåòîäà Ãàóññà ìû èñïîëüçîâàëè îïåðàöèþ âèäà (·,q) Tδ , òî ñëåäóþùàÿ çà íåé îïåðàöèÿ ïåðåñòàíîâêè (åñëè â íåé âîçíèêàåò íåîá- õîäèìîñòü) áóäåò ïðèìåíÿòüñÿ ê ñòðîêàì l, m > q . Ñôîðìóëèðóåì ñëåäóþùèé ðåçóëüòàò. Ëåììà 1.5.7. Ïóñòü T(·,q)  ìàòðèöà âèäà δ (1.20), à Plm  ìàòðèöà ïåðåñòàíîâêè l-é è m-é ñòðîê, ïðè÷åì âûïîëíÿåòñÿ l > m > q . Òîãäà ìîæíî íàéòè òàêóþ íåâûðîæäåííóþ íèæíþþ òðåóãîëüíóþ ìàòðèöó T̃, ÷òî âûïîëíÿåòñÿ (·,q) Plm Tδ Äîêàçàòåëüñòâî. = T̃Plm . (1.22) (·,q) Plm = T̃. Ëåâàÿ ÷àñòü ýòîãî âûðàæå(·,q) íèÿ ñîîòâåòñòâóåò ïåðåñòàíîâêå l-é è m-é ñòðîê ìàòðèöû Tδ ñ ïîñëåäóþùåé ïåðåñòàíîâ(·,q) êîé l-ãî è m-ãî ñòîëáöîâ ïîëó÷èâøèâîñÿ âûðàæåíèÿ. Ïðåäñòàâèì ìàòðèöó Tδ â áëî÷íîì Ïåðåïèøåì (1.22) â âèäå Plm Tδ âèäå  (·,q) Tδ   =   Eq−1 | | 1 | δq+1 . 0 | .. | δn  1 0      .. . 1 è çàìåòèì, ÷òî ïåðåñòàíîâêè ïðèìåíÿþòñÿ òîëüêî ñ íèæíåìó ïðàâîìó áëîêó ðàçìåðíîñòè [q × q]. Ìîæíî ëåãêî ïðîâåðèòü, åäèíñòâåííûì ñëåäñòâèåì ïåðåñòàíîâêè äâóõ ñòðîê ñ èí- äåêñàìè l, m > q è äâóõ ñòîëáöîâ ñ òåìè æå èíäåêñàìè áóäåò çàìåíà ýëåìåíòîâ δl è δm . Ñòðóêòóðà ìàòðèöû ïðè ýòîì îñòàåòñÿ íåèçìåííîé, ñîîòâåòñòâåííî ñîõðàíÿþòñÿ ñâîéñòâà óíèïîòåíòíîñòè è íåâûðîæäåííîñòè. 26 Òåîðåìà 1.5.8. Äëÿ ëþáîé ïðÿìîóãîëüíîé ìàòðèöû ìîãóò áûòü íàéäåíû ìàòðèöà ïåðåñòàíîâîê P è íåâûðîæäåííàÿ íèæíÿÿ òðåóãîëüíàÿ ìàòðèöà L òàêèå, ÷òî èìååò ìåñòî âûðàæåíèå PA = LAREF , (1.23) ãäå AREF  ìàòðèöà ñòóïåí÷àòîãî âèäà ïî ñòðîêàì. Äîêàçàòåëüñòâî. Èñïîëüçóÿ ðåçóëüòàò ëåììû 1.5.7 ìû ìîæåì ïåðåïèñàòü (1.21) â âèäå T̃k . . . T̃2 T̃1 Pk . . . P2 P1 A = AREF , T̃i ãäå (1.24) ñóòü íåêîòîðûå íåâûðîæäåííûå óíèïîòåíòíûå íèæíèå òðåóãîëüíûå ìàòðèöû, â îá- Ti . Ïðåäñòàâèì ïðîèçâåäåíèå ìàòðèö ïåðåñòàíîâîê â âèäå Pk . . . P2 P1 = P, ãäå P  íåêîòîðàÿ ìàòðèöà ïåðåñòàíîâêè è äîìíîæèì âûðàæåíèå (1.24) ñëåâà íà L = −1 −1 T̃−1 1 T̃2 . . . T̃k . Ïîëó÷àåì òðåáóåìóþ ôîðìó (1.23), êîòîðàÿ íàçûâàåòñÿ LUP-ðàçëîæåíèåì ìàòðèöû A. ùåì ñëó÷àå íå ðàâíûå Àíàëîãè÷íî ñëó÷àþ LU-ðàçëîæåíèÿ, äàäèì ôîðìóëèðîâêó LUP-ðàçëîæåíèÿ äëÿ ñëó÷àÿ ïðîèçâîëüíîé êâàäðàòíîé ìàòðèöû. Ñëåäñòâèå 1.5.9. Ëþáàÿ êâàäðàòíàÿ ìàòðèöà A ìîæåò áûòü ïðåäñòàâëåíà â âèäå PA = LU, (1.25) ãäå P  ìàòðèöà ïåðåñòàíîâîê, L  íåâûðîæäåííàÿ óíèïîòåíòíàÿ íèæíÿÿ òðåóãîëüíàÿ ìàòðèöà, à U  âåðõíÿÿ òðåóãîëüíàÿ ìàòðèöà. Î÷åâèäíî, ÷òî LU-ðàçëîæåíèå (1.18) ÿâëÿåòñÿ ÷àñòíûì ñëó÷àåì LUP-ðàçëîæåíèÿ (1.25) äëÿ P = E. Ïðèìåð 1.5.2 1.6 (LUP-ðàçëîæåíèå) . Äîáàâèòü! LU(P)-ðàçëîæåíèå êâàäðàòíûõ ìàòðèö è åãî ïðèìåíåíèå A, äîìíîæåííàÿ íà ìàòðèöó ïåP (êîòîðàÿ ìîæåò áûòü ðàâíà E), ìîæåò áûòü ïðåäñòàâëåíà â âèäå ïðîèçâåäåíèÿ íåâûðîæäåííîé óíèòàðíîé íèæíåé òðåóãîëüíîé ìàòðèöû L è âåðõíåé òðåóãîëüíîé ìàòðèöû U. Ýòîò ðåçóëüòàò èìååò ìíîæåñòâî ïðèìåíåíèé, ðÿä èç êîòîðûõ ìû ðàçáåðåì íèæå. Îäíàêî Èòàê, âûøå ìû äîêàçàëè, ÷òî ëþáàÿ êâàäðàòíàÿ ìàòðèöà ðåñòàíîâîê ñïåðâà ìû êðàòêî îáñóäèì íåêîòîðûå âàæíûå âîïðîñû, êîòîðûå îñòàëèñü çà êàäðîì. 1. Íåñìîòðÿ íà ñâîþ ýôôåêòèâíîñòü, ìåòîä Ãàóññà è, ñîîòâåòñòâåííî, LUP-ðàçëîæåíèå ìîãóò ïðèâîäèòü ê íåâåðíûì ðåçóëüòàòàì èç-çà îøèáîê îêðóãëåíèÿ åñëè ìàòðèöà ïëîõî îáóñëîâëåíà (àíãë., badly conditioned). A Ìû ïîêà íå ãîòîâû äàòü ñòðîãîå îïðå- äåëåíèå îáóñëîâëåííîñòè ìàòðèöû, ò. ê. ýòî ïîòðåáóåò ìàòåìàòè÷åñêîãî àïïàðàòà, ñ êîòîðûì ìû åùå íå çíàêîìû. Ñêàæåì òîëüêî, ÷òî ìàòðèöà ñ áîëüøîé âåðîÿòíîñòüþ áóäåò ïëîõî îáóñëîâëåííîé, åñëè åå ýëåìåíòû áóäóò ðàçëè÷àòüñÿ íà íåñêîëüêî ïîðÿäêîâ.  òàêîé ñèòóàöèè èñïîëüçóþòñÿ ÷èñëåííî óñòîé÷èâûå ìîäèôèêàöèè îïèñàííûõ âûøå ñõåì. 27 2. Ñóùåñòâóåò ðÿä ìåòîäîâ, ïîçâîëÿþùèõ âû÷èñëèòü LUP ðàçëîæåíèå íåêîòîðûõ ñïåöèàëüíûõ âèäîâ ìàòðèö ñ ìåíüøèìè çàòðàòàìè (íàïðèìåð, ðàçëîæåíèå Õîëåöêîãî 12 ïîëîæèòåëüíî (ïîëó-)îïðåäåëåííûõ ñèììåòðè÷åñêèõ ìàòðèö). Ñóùåñòâóåò òàêæå ðÿä A íà ìàòðèöû âèäà, îòëè÷íîQR-ðàçëîæåíèå, ãäå Q  îðòîãîíàëüíàÿ ìàòðèöà, ò. å. > óñëîâèþ QQ = E, à R  âåðõíÿÿ òðåóãîëüíàÿ ìàòðèöà). ðàçëîæåíèé íåêîòîðîé (îáû÷íî êâàäðàòíîé) ìàòðèöû ãî îò òðåóãîëüíîãî (íàïðèìåð, ìàòðèöà, óäîâëåòâîðÿþùàÿ Òåïåðü ìû ïåðåéäåì ê òîìó, êàê ìîæíî èñïîëüçîâàòü LUP-ðàçëîæåíèå äëÿ ðåøåíèÿ ðÿäà ïðàêòè÷åñêè âàæíûõ çàäà÷. 1.6.1 Ñóùåñòâîâàíèå îáðàòíîé ìàòðèöû Âûøå ìû ïîêàçàëè, ÷òî âñå ìàòðèöû ýëåìåíòàðíûõ îïåðàöèé ÿâëÿþòñÿ íåâûðîæäåííûìè. Îêàçûâàåòñÿ, ýòîò ôàêò ìîæåò áûòü èñïîëüçîâàí äëÿ îïðåäåëåíèÿ íåâûðîæäåííîñòè ïðîèçâîëüíîé êâàäðàòíîé ìàòðèöû. Òåîðåìà 1.6.1. Êâàäðàòíàÿ ìàòðèöà A ÿâëÿåòñÿ íåâûðîæäåííîé, ò.å. îáðàòíàÿ ê íåé ìàòðèöà A−1 ñóùåñòâóåò è õîðîøî îïðåäåëåíà, òîãäà è òîëüêî òîãäà, êîãäà âñå äèàãîíàëüíûå ýëåìåíòû ìàòðèöû U â LUP-ðàçëîæåíèè (1.25) íå ðàâíû íóëþ. Ïåðåä òåì, êàê äîêàçàòü ýòó òåîðåìó, ìû óñòàíîâèì ðÿä âñïîìîãàòåëüíûõ ôàêòîâ. Ëåììà 1.6.2. Ïóñòü A  ïðîèçâîëüíàÿ ìàòðèöà ðàçìåðà [k×n], à U  âåðõíÿÿ òðåóãîëüíàÿ ìàòðèöà ðàçìåðíîñòè [n × n] ñ íåíóëåâûìè äèàãîíàëüíûìè ýëåìåíòàìè. Òîãäà èç AU = 0[k×n] ñëåäóåò A = 0. Äîêàçàòåëüñòâî. Âñïîìíèì, ÷òî ïðîèçâåäåíèå AU ìîæåò áûòü ïðåäñòàâëåíî êàê AU = [Au×,1 , Au×,2 , . . . , Au×,n ], k -é ñòîëáåö ìàòðèöû U. Ðàññìîòðèì ïåðâûé ñòîëáåö ðåçóëüòèðóþùé ìàòAu×,1 . Èç óñëîâèÿ AU = 0[k×n] ýòîò ñòîëáåö äîëæåí áûòü íóëåâûì. Ïîñêîëüêó ýëåìåíò u11 6= 0, à îñòàëüíûå ýëåìåíòû ñòîëáöà u×,1 íóëåâûå, ìû èìååì Au×,1 = u11 a×,1 è, ñîîòâåòñòâåííî, a×,1 = 0. Òåïåðü ðàññìîòðèì âòîðîé ñòîëáåö ìàòðèöû AU, ò. å. Au×,2 .  ñòîëáöå u×,2 ýëåìåíò u22 6= 0, à ýëåìåíòû uj2 = 0 äëÿ âñåõ j > 2 (íèêàêèõ ïðåäïîëîæåíèé î u12 ìû íå äåëàåì). Ñëåäîâàòåëüíî èìååì Au×,2 = u12 a×,1 + u22 a×,2 = u22 a×,2 (âñïîìèíàÿ, ÷òî a×,1 = 0). Ïîñêîëüêó u22 6= 0, ñòîëáåö Au×,2 = u22 a×,2 ðàâåí íóëþ òîëüêî ïðè a×,2 = 0. Äâèãàÿñü äàëüøå, ìû ïîëó÷àåì, ÷òî èç óñëîâèÿ AU = 0[k×n] ñëåäóåò, ÷òî âñå ñòîëáöû ìàòðèöû A ðàâíû íóëþ, ÷òî ýêâèâàëåíòíî A = 0. ãäå u×,k  ýòî ðèöû, ò. å. Òåïåðü ìû ãîòîâû ñôîðìóëèðîâàòü ðåçóëüòàò î íåâûðîæäåííîñòè (âåðõíåé) òðåóãîëüíîé ìàòðèöû. Òåîðåìà 1.6.3. Âåðõíÿÿ òðåóãîëüíàÿ ìàòðèöà ÿâëÿåòñÿ íåâûðîæäåííîé òîãäà è òîëüêî òîãäà, êîãäà âñå åå äèàãîíàëüíûå ýëåìåíòû íå ðàâíû íóëþ. Äîêàçàòåëüñòâî. Èòàê, íàì òðåáóåòñÿ äîêàçàòü âåðíîñòü ñëåäóþùåãî âûðàæåíèÿ: ∃U−1 ⇐⇒ uii 6= 0 ∀i = 1, . . . , n. 12 Andr
e-Louis Cholesky (1875  1918), ôðàíöóçñêèé âîåííûé ãåîäåçèñò è àðòèëëåðèñò. Ïîãèá âî âðåìÿ ïåðâîé ìèðîâîé âîéíû. Îïèñàíèå ìåòîäà, íàçâàííîãî åãî èìåíåì, áûëî îïóáëèêîâàíî òîëüêî ïîñëå åãî ñìåðòè. 28 [⇒] Ïîêàæåì, ÷òî åñëè ñóùåñòâóåò òàêîå ê U, B òàêóþ, ÷òî âûïîëíÿåòñÿ i ∈ {1, . . . , n}, ÷òî uii = 0, òî ìàòðèöû, îáðàòíîé íå ñóùåñòâóåò. Ìû áóäåì èñêàòü ëåâóþ îáðàòíóþ ìàòðèöó, ò. å. [n × n] ìàòðèöó BU = E. (∗) Ðàññìîòðèì ñëó÷àé i = 1. Òîãäà ìàòðèöà U èìååò ïåðâûé íóëåâîé ñòîëáåö. Êàêîâà B, ïðîèçâåäåíèå BU áóäåò òàêæå èìåòü ïåðâûé íóëåâîé ñòîëáåö. i h U11 |U12 , Äàëåå, ïóñòü i = l > 1. Òîãäà ìû ðàçîáüåì ìàòðèöó U íà ÷åòûðå áëîêà, U = U |U áû íè áûëà ìàòðèöà 21 ãäå U11 ìè  íà ãëàâíîé äèàãîíàëè, 0  .. . [l × l] k = n − l è U22  âåðõíÿÿ òðåóãîëüíàÿ ìàòðèöà ðàçìåðíîñòè ∗ uk+1,k+1 .. . ... ... .. . ... ∗ ∗ .. . U21 = 0kl , ãäå 22 ñ íåíóëåâûìè ýëåìåíòà [k × k] ìàòðèöà âèäà   . Ïðåäñòàâèì ìàòðèöó B â áëî÷íîì âèäå, B= h B11 |B12 B21 |B22 i , ãäå unn ðàçìåðíîñòè áëîêîâ Bij ñîâïàäàþò ñ ðàçìåðíîñòÿìè ñîîòâåòñòâóþùèõ áëîêîâ ïèøåì ïðîèçâåäåíèå äâóõ ìàòðèö è ïðèðàâíÿåì åãî ê åäèíè÷íîé ìàòðèöå:  BU = B11 U11 |B11 U12 + B12 U22 B21 U11 |B21 U12 + B22 U22   = E[l×l] | 0[l×k] 0[k×l] |E[k×k] Uij . Çà-  . B21 U11 = 0[k×l] . Èç ëåììû 1.6.2 ñëåB21 = 0[k×l] . Ïîäñòàâëÿÿ B21 â íèæíèé ïðàâûé áëîê ïîëó÷àåì óðàâíåíèå B22 U22 = E[k×k] . Îäíàêî ýòî óðàâíåíèå íå èìååò ðåøåíèÿ ïî òîé æå ïðè÷èíå, ÷òî è â ñëó÷àå i = 1 (ñì. (∗) âûøå). Äëÿ íèæíåãî ëåâîãî áëîêà äîëæíî âûïîëíÿòüñÿ äóåò, ÷òî [⇐] Ïîêàæåì, ÷òî åñëè âñå äèàãîíàëüíûå ýëåìåíòû Äîìíîæàÿ ìàòðèöó U uii 6= 0, òî ìàòðèöà U−1 ñóùåñòâóåò. D = diag(u11 , . . . , unn ) è ïðè(i,q) âèäà Tδ , i < q , ïîëó÷àåì åäè- ñëåâà íà äèàãîíàëüíóþ ìàòðèöó ìåíÿÿ ïîñëåäîâàòåëüíîñòü ýëåìåíòàðíûõ îïåðàöèé íè÷íóþ ìàòðèöó: Tk . . . T1 DU = E. Ñîîòâåòñòâåííî, îáðàòíàÿ ìàòðèöà èìååò âèä −1 U−1 = D−1 T−1 1 . . . Tk . Òåïåðü ìû ìîæåì äîêàçàòü òåîðåìó 1.6.1. Äîêàçàòåëüñòâî. Ïî îïðåäåëåíèþ, A = P −1 LU. Ñîîòâåòñòâåííî, A−1 = (LU)−1 P = U−1 L−1 P. Ìàòðèöû U P è L íåâûðîæäåíû, êàê áûëî óñòàíîâëåíî ðàíåå, à íåâûðîæäåííîñòü ìàòðèöû îïðåäåëÿåòñÿ òåîðåìîé 1.6.3. Ñôîðìóëèðóåì ñëåäóþùåå ïðàâèëî: Äëÿ ïðîâåðêè íåâûðîæäåííîñòè êâàäðàòíîé ìàòðèöû íåîáõîäèìî ïðèâåñòè åå ê òðåóãîëüíîìó âèäó ñ ïîìîùüþ ýëåìåíòàðíûõ ïðåîáðàçîâàíèé è ïðîâåðèòü äèàãîíàëüíûå ýëåìåíòû. Åñëè âñå äèàãîíàëüíûå ýëåìåíòû íå ðàâíû íóëþ, òî ìàòðèöà íåâûðîæäåíà, â ïðîòèâíîì ñëó÷àå  âûðîæäåíà. Òåïåðü ìû ìîæåì îïðåäåëèòü ñòåïåíü âûðîæäåííîñòè íåêîòîðîé êâàäðàòíîé ìàòðèöû. 29 Îïðåäåëåíèå 1.6.1. Ðàíãîì ìàòðèöû A, îáîçíà÷àåòñÿ rank(A), íàçûâàåòñÿ ÷èñëî íåíóëåâûõ ñòðîê ìàòðèöû U â LU(P)-ðàçëîæåíèè ìàòðèöû A. Èñïîëüçóÿ ïîíÿòèå ðàíãà ìû ìîæåì ïåðåôîðìóëèðîâàòü ðåçóëüòàò òåîðåìû 1.6.1: êâàäðàòíàÿ ìàòðèöà A ÿâëÿåòñÿ íåâûðîæäåííîé òîãäà è òîëüêî òîãäà, êîãäà ðàíã A ðàâåí åå ðàçìåðíîñòè, ò. å. rank(A) = n. Êàê ñëåäóåò èç îïðåäåëåíèÿ, ðàíã ìîæåò áûòü îïðåäåëåí äëÿ ëþáîé ìàòðèöû (â ñëó÷àå ïðÿìîóãîëüíîé ìàòðèöû A, ðàíã ðàâåí ÷èñëó íåíóëåâûõ ñòðîê ìàòðèöû AREF ). Âî âòîðîé ÷àñòè íàøåãî êóðñà ìû óâèäèì, ÷òî ïîíÿòèå ðàíãà ÿâëÿåòñÿ îñíîâîïîëàãàþùèì â òåîðèè âåêòîðíûõ ïðîñòðàíñòâ è åãî ïðèìåíåíèÿ âûõîäÿò äàëåêî çà ïðåäåëû âîïðîñà âûÿñíåíèÿ âûðîæäåííîñòè êâàäðàòíîé ìàòðèöû. 1.6.2 Ðåøåíèå ÑËÀÓ 1.6.3 Ìåòîä Ãàóññà-Éîðäàíà 1.7 Îïðåäåëèòåëü. Íàõîæäåíèå îáðàòíîé ìàòðèöû Îïðåäåëèòåëü (àíãë., determinant)  ýòî íåêîòîðàÿ ÷èñëîâàÿ õàðàêòåðèñòèêà, îïðåäåëåííàÿ äëÿ ëþáîé êâàäðàòíîé ìàòðèöû. Îïðåäåëèòåëè èãðàþò êëþ÷åâóþ ðîëü â ëèíåéíîé àëãåáðå è ìàòðè÷íîì àíàëèçå. Íèæå ìû ðàññìîòðèì äâà ïîäõîäà ê ââåäåíèþ îïðåäåëèòåëåé. Ïåðâûé ïîäõîä, àêñèîìàòè÷åñêèé, àññîöèèðóåòñÿ ñ èìåíåì Âåéåðøòðàññà, òîãäà êàê âòîðîé, êîíñòðóêòèâíûé ïîäõîä îñíîâàí íà âû÷èñëåíèè îïðåäåëèòåëÿ ñ ïîìîùüþ ò. í. ñèãíàòóðíîé ôîðìóëû Ëåáíèöà. 1.7.1 Àêñèîìàòè÷åñêîå îïðåäåëåíèå îïðåäåëèòåëÿ. Ñâîéñòâà îïðåäåëèòåëÿ Îïðåäåëåíèå 1.7.1. M  [n × n] ìàòðèöà ñ ýëåìåíòàìè èç ïîëÿ F . Îïðåäåëèòåëåì det : M → F óäîâëåòâîðÿþùåå ñëåäóþùèì ñâîéñòâàì: Ïóñòü íàçûâàåòñÿ îòîáðàæåíèå D1. Ïîëèëèíåéíîñòü. Ïóñòü äëÿ íåêîòîðîãî èíäåêñà i ∈ {1, . . . , n}, i-ÿ ñòðîêà ìàòðèöû M èìååò âèä mi,× = m0i,× + m00i,× . Òîãäà âûïîëíÿåòñÿ 13      .. .. .. . . .  0   0   00  00      det  mi,× + mi,×  = det mi,×  + det mi,×  . .. .. .. . . .  Ñîîòâåòñòâåííî, ïóñòü äëÿ i ∈ {1, . . . , n}, mi,× = λm0i,× , λ ∈ F .    .. ..  .0   0.   mi,×  . λm det  = λ det    i,×  .. .. . . (1.26) Òîãäà âûïîëíÿåòñÿ  13 Òî÷êè îçíà÷àþò, ÷òî îñòàëüíûå ýëåìåíòû ìàòðèöû îñòàþòñÿ íåèçìåííûìè. 30 (1.27) D2. Êîñîñèììåòðè÷íîñòü. Ïóñòü mi,× è mj,×  äâå ñòðîêè ìàòðèöû M. Ïåðåñòàíîâêà äâóõ ñòðîê ïðèâîäèò ê èçìåíåíèþ çíàêà îïðåäåëèòåëÿ:    .. ..  .   .  mj,×  mi,×         ..  det  .  = − det  ...  .     mi,×  mj,×      .. .. . .  D3. Íîðìèðîâàííîñòü. det En = 1. Èç àêñèîì D1-D3 ñëåäóåò ðÿä âàæíûõ ñâîéñòâ îïðåäåëèòåëÿ. Òåîðåìà 1.7.1. Îïðåäåëèòåëü det M óäîâëåòâîðÿåò ñëåäóþùèì ñâîéñòâàì: 1. Äëÿ ëþáîãî λ ∈ F âåðíî det(λM ) = λn det M . 2. Åñëè íåêîòîðàÿ ñòðîêà M ñîäåðæèò òîëüêî íóëåâûå ýëåìåíòû, det M = 0. 3. Åñëè ëþáûå äâå ñòðîêè M ðàâíû, òî det M = 0. 4. Ïóñòü i-ÿ ñòðîêà ìàòðèöû Q ðàâíà qi,× = mi,× +λmj,× , ãäå mi,× è mj,×  äâå ñòðîêè ìàòðèöû M , à îñòàëüíûå ñòðîêè ìàòðèö Q è M ñîâïàäàþò. Òîãäà det Q = det M . C Îïðåäåëèòåëü îñòàåòñÿ íåèçìåííûì ïðè èñïîëüçîâàíèè ýëåìåíòàðíîé îïåðàöèè âèäà (1.6). B 5. Åñëè ñòðîêè ìàòðèöû M ëèíåéíî-çàâèñèìû. ò.På. ñóùåñòâóåò òàêîé íàáîð ÷èñåë n (c1 , . . . , cn ), íå ðàâíûõ íóëþ îäíîâðåìåííî, ÷òî i=1 ci mi,× = 0, òî det M = 0. 6. Åñëè M  òðåóãîëüíàÿ ìàòðèöà, òî îïðåäåëèòåëü ðàâåí ïðîèçâåäåíèþ äèàãîíàëüíûõ ýëåìåíòîâ. 7. Ïóñòü ìàòðèöà M ðàçìåðíîñòè [n × n], n > 2, ìîæåò áûòü ïðåäñòàâëåíà â âèäå   M11 |M12 M= , M21 |M22 ãäå M11 è M22  êâàäðàòíûå ìàòðèöû, à M12 èëè M21 ñîäåðæèò òîëüêî íóëåâûå ýëåìåíòû (ò. å. , M  áëî÷íî-òðåóãîëüíàÿ ìàòðèöà). Òîãäà âåðíî det M = det M11 · det M22 . 8. Âûïîëíåíèå det M = 0 ýêâèâàëåíòíî âûïîëíåíèþ rank M < n. Äîêàçàòåëüñòâî. 1. Ñëåäóåò èç D1, (1.27). 2. Ñëåäóåò èç D1, (1.27), ïîëàãàÿ λ = 0. 3. Ñëåäóåò èç D2. 4. Ïóñòü i-ÿ qi,× = mi,× + λmj,× . Òîãäà èç D1 èìååì      .. .. .. .    .   .   = det mi,×  + λ det mj,×  . m + λm det Q = det  i,× j,×       .. .. .. . . . Q  ñòðîêà ìàòðèöû ðàâíà 31 mj,× , det Q = det M . Ïîñëåäíÿÿ ìàòðèöà ñîäåðæèò äâå îäèíàêîâûå ñòðîêè ëèòåëü ðàâåí íóëþ ïðî ñâîéñòâó 3. Èìååì M 5. Ïîëîæèì äëÿ îïðåäåëåííîñòè, ÷òî ñëåäîâàòåëüíî åå îïðåäå-  âåðõíÿÿ òðåóãîëüíàÿ ìàòðèöà. Ðàññìîòðèì äâà ñëó÷àÿ. (a) Ïóñòü ïî êðàéíåé ìåðå îäèí èç äèàãîíàëüíûõ ýëåìåíòîâ ðàâåí íóëþ. Âûáåðåì i òàê, ÷òîáû âûïîëíÿëîñü mkk 6= 0 äëÿ âñåõ k > i. Èñïîëüçóÿ ýëåìåíòàðíûå mij , j > i. Ïðèìåíÿÿ ñâîéñòâî ïîëó÷àåì det M = 0. èíäåêñ îïåðàöèè âèäà (1.6) ìû ìîæåì îáíóëèòü ýëåìåíòû 2. (b) Ïóñòü âñå äèàãîíàëüíûå ýëåìåíòû íå ðàâíû íóëþ. Òîãäà ìíîãîêðàòíî ïðèìåíÿÿ ýëåìåíòàðíóþ îïåðàöèþ (1.6) ìû ïðèâîäèì ìàòðèöó ê äèàãîíàëüíîìó âèäó. Ñîãëàñíî ñâîéñòâó 4, îïðåäåëèòåëü ïðåîáðàçîâàííîé ìàòðèöû ðàâåí îïðåäåëèòåëþ èñõîäíîé. Íàêîíåö, èñïîëüçóÿ  m11  det   .. D1, (1.27), è D3 ïîëó÷àåì   = m11 · · · · · mnn · det En = m11 · · · · · mnn . . mnn 6. Ëèíåéíî-çàâèñèìûå ñòðîêè 7. Ïîëîæèì, ÷òî ìàòðèöà M âåðõíÿÿ áëî÷íî-òðåóãîëüíàÿ, ò. å.  M= ãäå M11 M22 è M11 |M12 0 |M22  ,  êâàäðàòíûå ìàòðèöû. Èñïîëüçóÿ ýëåìåíòàðíûå îïåðàöèè òèïà (1.6) è ïåðåñòàíîâêè ñòðîê ìû ìîæåì ïðåîáðàçîâàòü ìàòðèöó âèäó. Ìàòðèöà M12 . M22 ïðè ýòîì íå èçìåíèòñÿ, à ìàòðèöà Îáîçíà÷èì ïîëó÷àâøóþñÿ ìàòðèöó Q1 . M11 ê âåðõíåìó òðåóãîëüíîìó M12 ïðåîáðàçóåòñÿ â ìàòðèöó Èìååì det M11 = (−1)k1 det Q1 , ãäå k1  ÷èñëî îïåðàöèé ïåðåñòàíîâîê. Àíàëîãè÷íî Q1 è M12 M11 , ïðèâåäåì ìàòðèöó M22 ê âåðõíåìó äèàãîíàëüíîìó âèäó. Ìàòðèöû ïðè ýòîì íå èçìåíÿòñÿ. Îáîçíà÷èì ïîëó÷èâøóþñÿ òðåóãîëüíóþ ìàòðèöó Èìååì det M22 = (−1)k2 det Q2 , ãäå k2  ÷èñëî îïåðàöèé ïåðåñòàíîâîê. Íàêîíåö, ìû ìîæåì çàïèñàòü  det M = det M11 |M12 0 |M22  = (−1)k1 +k2 det îòêóäà ñëåäóåò òðåáóåìûé ðåçóëüòàò. 8. det M = 0 ýêâèâàëåíòíî rank M < n. 32  Q1 |M12 0 | Q2  = (−1)k1 +k2 det Q1 det Q2 , Q2 . Çàìåòèì, ÷òî îïðåäåëèòåëü ïðîèçâîëüíîé ìàòðèöû ìîæåò áûòü âû÷èñëåí ïóòåì ïðèâåäåíèÿ ìàòðèöû ê âåðõíåé òðåóãîëüíîé ôîðìå ñ èñïîëüçîâàíèåì ïåðåñòàíîâîê ñòðîê è îïåðàöèé ( k ãäå ??). Îïðåäåëèòåëü áóäåò ðàâåí ïðîèçâåäåíèþ äèàãîíàëüíûõ ýëåìåíòîâ íà (−1)k ?  ÷èñëî ïåðåñòàíîâîê. Ïðèìåð 1.7.1. a12 a22 ]. Åñëè a11 = 0, ìû ïðèâîäèì ìàòðèöó A ê âåðíåìó òðåóãîëüíîìó âèäó ïóòåì ïåðåñòàíîâêè ñòðîê è ïîëó÷àåì det A = (−1)a21 a12 .  Ðàññìîòðèì ìàòðèöó A = [ aa11 21 ??) ñëåäóþùèì îáðàçîì: ñêëà- ïðîòèâíîì ñëó÷àå ìû èñïîëüçóåì ýëåìåíòàðíóþ îïåðàöèþ ( äûâàåì âòîðóþ ñòðîêó ñ ïåðâîé, äîìíîæåííîé íà 21 . − aa11 Ïðåîáðàçîâàííàÿ ìàòðèöà èìååò âèä  a11 A = Ñîîòâåòñòâåííî,  a12 . 21 a12 a22 − − aa11 det A = det A0 = a11 a22 − a12 a21 . Äëÿ a11 = 0 ïîëó÷àåì âûðàæåíèå, íàéäåí- íîå ðàíåå. Ïðèìåð 1.7.2. Íàéòè îïðåäåëèòåëü ìàòðèöû ðàçìåðà [n × n] ñ íóëÿìè íà ãëàâíîé äèàãî- íàëè è åäèíèöàìè âî âñåõ îñòàëüíûõ ïîçèöèÿõ.  1  det  .  .. 1 1 1 ... .. . ...    1 1 ... 1 n−1 1 0 1 1     ..  = ..  = (n − 1) · det  .. . .. .   . . . . . 1 1 ... 0 1 ...   1 1 ... 1 0 −1 0   (n−1) (n − 1) = (n − 1) · det  . ..  = (−1) ..  .. . .    n−1 1  1 1   ..  = det  ..  .  . 1 n−1 ... Ïðèìåð 1.7.3. −1  αE3 + x ... Íàéòè îïðåäåëèòåëü ìàòðèöû (Îáîáùèòü?) y z >  x y z  . Çàïèøåì âûðàæåíèå â ìàòðè÷íîì âèäå è íàéäåì îïðåäåëèòåëü, èñïîëüçóÿ ñâîéñòâà, óñòàíîâëåííûå âûøå:  2 x +α det  xy xz xy y2 + α yz  2 x +α = det  x2 x2    xz x + α/x y z yz  = xyz det  x y + α/y z = z2 + α x y z + α/z   2  x + y2 + z2 + α y2 z2 y2 z2 y2 + α z 2  = det x2 + y 2 + z 2 + α y 2 + α z2  = y2 z2 + α x2 + y 2 + z 2 + α y2 z2 + α   1 y2 z2 = (x2 + y 2 + z 2 + α) det 0 α 0  = α2 (x2 + y 2 + z 2 + α). 0 0 α Çàäàíèÿ 1. Âû÷èñëèòå îïðåäåëèòåëè ñëåäóþùèõ ìàòðèö ðàçìåðà [n × n]:  a a   .. . b ... . .. ... a b a  b a  ..  , . a  a1 + b  a1   ..  . a1 a2 a2 + b .. . a2 ... ... .. . ...  an an   ..  . .  an + b 2. Äîêàæèòå, ÷òî îïðåäåëèòåëü ïðîèçâîëüíîé ìàòðèöû ïåðåñòàíîâêè ìîæåò áûòü ðàâåí òîëüêî +1 èëè −1. Îò ÷åãî çàâèñèò çíàê îïðåäåëèòåëÿ? 33 1.7.2 Ïåðåñòàíîâêè, èõ ñâîéñòâà Îïðåäåëåíèå 1.7.2. N Ïóñòü ýëåìåíòîâ: N = {1, . . . , n}. N â ñåáÿ: π : N → N . Ìíî14 îáîçíà÷àåòñÿ Sn . - ìíîæåñòâî, ñîñòîÿùåå èç n Ïåðåñòàíîâêîé íàçûâàåòñÿ âçàèìíî-îäíîçíà÷íîå îòîáðàæåíèå æåñòâî âñåõ ïåðåñòàíîâîê íàáîðà èç n ýëåìåíòîâ Ñóùåñòâóåò íåñêîëüêî âàðèàíòîâ äëÿ çàïèñè ïåðåñòàíîâêè. Ìû áóäåì èñïîëüçîâàòü ôîðìó, â êîòîðîé èñõîäíîå ìíîæåñòâî è ðåçóëüòàò ïåðåñòàíîâêè çàïèñûâàþòñÿ äðóã ïîä äðóãîì:   1 2 ... n . π(1) π(2) . . . π(n)   1 2 3 π = çàêëþ÷àåòñÿ 2 3 1 π= Òàê, íàïðèìåð, ïåðåñòàíîâêà â òîì, ÷òî íà ìåñòî ïåðâîãî ýëåìåíòà ñòàâèòñÿ âòîðîé, íà ìåñòî âòîðîãî  òðåòèé è ò. ä. Äëÿ ïåðåñòàíîâîê îïðåäåëåíà îïåðàöèÿ êîìïîçèöèè, êîòîðàÿ çàêëþ÷àåòñÿ â ïîñëåäîâàòåëüíîì ïðèìåíåíèè äâóõ ïåðåñòàíîâîê, äâèãàÿñü ñïðàâà íàëåâî. Òàê, â êîìïîçèöèè ñíà÷àëà ïðèìåíÿåòñÿ ïåðåñòàíîâêà π, à çàòåì ïåðåñòàíîâêà σ◦π σ. Òàêèì îáðàçîì ìû ìîæåì ðàññìàòðèâàòü äåéñòâèå îïåðàöèè êîìïîçèöèè íà ìíîæåñòâå Sn . Ñôîðìóëèðóåì ñâîéñòâà ýòîé îïåðàöèè. Äëÿ ëþáûõ τ, σ, π ∈ Sn âûïîëíÿåòñÿ: 1. Àññîöèàòèâíîñòü: τ ◦ (σ ◦ π) = (τ ◦ σ) ◦ π . 2. Ñóùåñòâîâàíèå íåéòðàëüíîãî ýëåìåíòà: ∃ id ∈ Sn : id ◦ π = π ◦ id = π . 3. Ñóùåñòâîâàíèå îáðàòíîãî ýëåìåíòà: ∃π −1 ∈ Sn : π −1 ◦ π = π ◦ π −1 = id. Îáðàòèòå âíèìàíèå, ÷òî îïåðàöèÿ êîìïîçèöèè äâóõ ïåðåñòàíîâîê íåêîììóòàòèâíà, êàê èëëþñòðèðóåò ñëåäóþùèé ïðèìåð. Ïðèìåð 1.7.4. Ðàññìîòðèì ïåðåñòàíîâêè  π= Âû÷èñëèì êîìïîçèöèè π◦σ 1 2 2 3  3 1 σ ◦ π:  1 2 π◦σ = 3 2 è  1 σ= 1 2 3  3 . 2 è   3 1 , σ◦π = 1 2 2 1  3 . 3 Çàìåòèì, ÷òî îáðàòíàÿ ïåðåñòàíîâêà ìîæåò áûòü ïîëó÷åíà ïóòåì èçìåíåíèÿ ïîðÿäêà ñòðîê â çàïèñè ïåðåñòàíîâêè: π −1 = Âñåãî ñóùåñòâóåò n!  2 1 3 2   1 1 = 3 3 ïåðåñòàíîâîê ìíîæåñòâà èç 2 1 n  3 . 2 ýëåìåíòîâ, ò. å. |Sn | = n!. Íàïîìíèì, ÷òî ýòà âåëè÷èíà ìîæåò áûòü îöåíåíà ïî ôîðìóëå Ñòèðëèíãà: n! ≈ ãäå 2πn  n n e , e  èçâåñòíûå ìàòåìàòè÷åñêèå êîíñòàíòû. Äëÿ ïðèìåðà çàìåòèì, ÷òî 60! ≈ 1082 , ò. å. äëÿ ñðàâíèòåëüíî ñêðîìíûõ çíà÷åíèé n ôàêòîðèàë n! ìîæåò ïðåâûñèòü ÷èñëî àòîìîâ π óæå √ è â íàáëþäàåìîé ÷àñòè Âñåëåííîé. Âàæíàÿ õàðàêòåðèñòèêà ïåðåñòàíîâêè îñíîâûâàåòñÿ íà ïîíÿòèè èíâåðñèè. 14 Ñèììåòðè÷åñêàÿ ãðóïïà ïåðåñòàíîâîê n ýëåìåíòîâ 34 Îïðåäåëåíèå 1.7.3. π ∈ Sn åñòü íåêîòîðàÿ ïåðåñòàíîâêà. Ãîâîðÿò, ÷òî ïàðà ýëåìåíèíâåðñèþ åñëè π(i) > π(j) äëÿ i < j . Îáîçíà÷èì ÷åðåç inv(π) îáùåå ÷èñëî èíâåðñèé â ïåðåñòàíîâêå π . Ïåðåñòàíîâêà π íàçûâàåòñÿ ÷åòíîé åñëè îíà ñîäåðæèò ÷åòíîå ÷èñëî èíâåðñèé è íå÷åòíîé â ïðîòèâíîì ñëó÷àå. π(i) òîâ è π(j) Ïóñòü îáðàçóåò  äàëüíåéøåì, â áîëüøèíñòâå ñëó÷àåâ íàñ áóäåò èíòåðåñîâàòü íå ÷èñëî èíâåðñèé â ïåðåñòàíîâêå, à åå ÷åòíîñòü/íå÷åòíîñòü. Ïîýòîìó ìû ââåäåì ôóíêöèþ sign : Sn → {−1, 1}, êîòîðàÿ îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì: ( sign(π) = Èíà÷å ãîâîðÿ, π  íå÷åòíàÿ  ÷åòíàÿ. π è σ èç Ïðèìåðà 1.7.4. Ïåðå(π(1) = 2, π(3) = 1) è (π(2) = 3, π(3) = 1). Èòàê, inv(π) = 2, Ïåðåñòàíîâêà σ ñîäåðæèò òîëüêî îäíó èíâåðñèþ (σ(2) = 3, σ(3) = 2), Âû÷èñëèì ÷èñëî èíâåðñèé â ïåðåñòàíîâêàõ ñîäåðæèò èíâåðñèè ïåðåñòàíîâêà ÷åòíàÿ. inv(σ) = 1, π π sign(π) = (−1)inv(π) . Ïðèìåð 1.7.5. ñòàíîâêà −1, 1, ïåðåñòàíîâêà íå÷åòíàÿ. Äëÿ àíàëèçà ÷åòíîñòè ïåðåñòàíîâêè ìû áóäåì ðàñêëàäûâàòü åå íà ýëåìåíòàðíûå ïåðåñòàíîâêè, êîòîðûå íàçûâàþòñÿ òðàíñïîçèöèÿìè. Îïðåäåëåíèå 1.7.4. Ïåðåñòàíîâêà π ∈ Sn íàçûâàåòñÿ òðàíñïîçèöèåé åñëè îíà ìåíÿåò äâà i, j ∈ N , ýëåìåíòà, îñòàâëÿÿ îñòàëüíûå íåèçìåííûìè. Ôîðìàëüíî ãîâîðÿ, ñóùåñòâóþò òàêèå ÷òî π(i) = j , π(j) = i è π(k) = k äëÿ âñåõ k ∈ N \ {i, j}. Óòâåðæäåíèå 1.7.2. Ïðè òðàíñïîçèöèè äâóõ ñîñåäíèõ ýëåìåíòîâ ÷èñëî èíâåðñèé â ïåðåñòàíîâêå ìåíÿåòñÿ íà åäèíèöó. Äîêàçàòåëüñòâî. Ðàññìîòðèì ïåðåñòàíîâêó π0 =  1 π(1) 2 π(2) ... ...  i j ... n , π(j) π(i) . . . π(n) π . Îáîçíà÷èì ÷åðåç inv0 è inv00 ÷èñëî i è j , ÷åðåç inv1 è inv10  ÷èñëî èíâåðñèé â ïàðàõ, ñîäåðæàùèõ îäèí èç äâóõ ýëåìåíòîâ è, íàêîíåö, ÷åðåç inv2 è inv2  ÷èñëî èíâåðñèé â ïàðå i è j . Î÷åâèäíî, ÷òî inv0 = inv00 , ò.ê. ñîîòâåòñòâóþùèå ýëåìåíòû îñòàþòñÿ íåèçìåííûìè. Òàêæå âåðíî inv1 = inv1 , ò.ê. îòíîñèòåëüíîå ðàñïîëîæåíèå ýëåìåíòîâ i è j îòíîñèòåëüíî äðóãèõ ýëåìåíòîâ íå èçìåíÿåòñÿ. Äëÿ inv2 è inv2 èìååì inv2 = 1 åñëè inv2 = 0 è inv2 = 0 åñëè inv2 = 1. Îáùàÿ ñóììà èíâåðñèé â îäíîì è äðóãîì ñëó÷àå ðàâíà inv(π) = inv0 + inv1 + inv2 è inv(π ) = inv0 + inv1 + inv2 . Âû÷èòàÿ, ïîëó÷èì inv(π ) − inv(π) = ±1. ïîëó÷åííóþ èç íåêîòîðîé èñõîäíîé ïåðåñòàíîâêè èíâåðñèé â ïàðàõ, íå ñîäåðæàùèõ ýëåìåíòû Óòâåðæäåíèå 1.7.3. Ëþáàÿ òðàíñïîçèöèÿ ìîæåò áûòü ïðåäñòàâëåíà êàê êîìïîçèöèÿ íå÷åòíîãî ÷èñëà òðàíñïîçèöèé ñîñåäíèõ ýëåìåíòîâ. Äîêàçàòåëüñòâî. Ðàññìàòðèì ïåðåñòàíîâêó  π = ãäå 1 π(1) ... ... i ... j ... π(j) . . . π(i) . . .  n , π(n) i < j . Äëÿ òîãî, ÷òîáû ïðèâåñòè åå ê èñõîäíîé, íåîáõîäèìî ïðèâåñòè π(j) íà j -þ ïîçèçèþ. j − i ïåðåñòàíîâîê ñîñåäíèõ ýëåìåíòîâ. Òåïåðü ïåðåñòàíîâêà Äëÿ ýòîãî íåîáõîäèìî ñäåëàòü èìååò âèä π =  1 π(1) ... ... i π(i + 1) ... j − 1 j ... . . . π(i) π(j) . . . 35  n . π(n) Äëÿ òîãî, ÷òîáû âåðíóòü π(i) j − 1 − i ïåðåñòàíîâîê 2(j − i) − 1 ïåðåñòàíîâêó. íà ñâîå ìåñòî, íåîáõîäèìî ñäåëàòü îáðàòíîì íàïðàâëåíèè. Èòîãî, âñåãî íåîáõîäèìî ñäåëàòü â Ñëåäñòâèå 1.7.4. Ëþáàÿ òðàíñïîçèöèÿ èçìåíÿåò ÷åòíîñòü ïåðåñòàíîâêè íà ïðîòèâîïîëîæíóþ. Ïðèâåäåííûé âûøå ðåçóëüòàò ìîæåò áûòü ñôîðìóëèðîâàí ñëåäóþùèì îáðàçîì: ïóñòü τ ∈ Sn  òðàíñïîçèöèÿ. Òîãäà äëÿ ëþáîãî π ∈ Sn âåðíî sign(τ ◦ π) = − sign(π). Çàìåòèì, ÷òî êàæäàÿ ïåðåñòàíîâêà ìîæåò áûòü ïðåäñòàâëåíà, êàê ðåçóëüòàò ïðèìåíåíèÿ ïîñëåäîâàòåëüíîñòè òðàíñïîçèöèé ê åäèíè÷íîé ïåðåñòàíîâêå id, ò. å. ëþáàÿ ïåðåñòàíîâêà ìîæåò áûòü ïðåäñòàâëåíà (íååäèíñòâåííûì îáðàçîì) êàê êîìïîçèöèÿ íàáîðà òðàíñïîçèöèé: π = τ1 ◦τ2 ◦· · ·◦τk . Äîêàçàòåëüñòâî ýòîãî ôàêòà îñòàâëÿåòñÿ ÷èòàòåëþ â êà÷åñòâå óïðàæíåíèÿ. −1 −1 −1 Ñîîòâåòñòâåííî, îáðàòíàÿ ïåðåñòàíîâêà èìååò âèä π = τk ◦ τk−1 ◦ · · · ◦ τ1 . Óòâåðæäåíèå 1.7.5. ×åòíîñòü ïåðåñòàíîâêè π è îáðàòíîé ê íåé π −1 ðàâíû: sign(π) = sign(π −1 ). Äîêàçàòåëüñòâî. Ïåðåñòàíîâêà, îáðàòíàÿ ê òðàíñïîçèöèè, òàêæå ÿâëÿåòñÿ òðàíñïîçèöèåé. Äàëüíåéøåå î÷åâèäíî. Íàêîíåö, ìû ñôîðìóëèðóåì âàæíûé ðåçóëüòàò, õàðàêòåðèçóþùèé ìíîæåñòâî ïåðåñòàíîâîê Sn . Óòâåðæäåíèå 1.7.6. Äëÿ ëþáîãî n ∈ N, ìíîæåñòâî Sn ñîäåðæèò ðàâíîå ÷èñëî ÷åòíûõ è íå÷åòíûõ ïåðåñòàíîâîê. Äîêàçàòåëüñòâî. ïåðåñòàíîâîê, a 6= b. Ïðåäïîëîæèì, ÷òî ìíîæåñòâî âòîðîãî ýëåìåíòîâ. Ïîëó÷èì a ñîäåðæèò a ÷åòíûõ è b íå÷åòíûõ ðàçëè÷íûõ íå÷åòíûõ ïåðåñòàíîâîê. Ïîñêîëüêó îáùåå ÷èñ- ëî íå÷åòíûõ ïåðåñòàíîâîê ðàâíî b, èìååì íå÷åòíûìè ïåðåñòàíîâêàìè. Ïîëó÷èì 1.7.3 Sn Âî âñåõ ÷åòíûõ ïåðåñòàíîâêàõ îñóùåñòâèì òðàíñïîçèöèþ ïåðâîãî è b ≤ a. a ≤ b. Òåïåðü îñóùåñòâèì òó æå îïåðàöèþ ñ Ñðàâíåíèå äâóõ íåðàâåíñòâ âëå÷åò a = b. Ñèãíàòóðíàÿ ôîðìóëà Ëåéáíèöà Òåîðåìà 1.7.7. Îïðåäåëèòåëü ìàòðèöû A = [aij ] ðàçìåðíîñòè [n × n], çàäàííîé íàä ìíîæåñòâîì F  ýòî ýëåìåíò èç F , îïðåäåëåííûé ñëåäóþùèì îáðàçîì: X det A = (−1)inv(π) a1,π(1) · a2,π(2) · · · · · an,π(n) . (1.28) π∈Sn Äîêàçàòåëüñòâî. Äëÿ íà÷àëà ïîêàæåì, ÷òî ôîðìóëà (1.28) ñëåäóåò èç àêñèîì D1D3. [1 × n], ñîäåðæàùèé 1 â i-é ïîçèöèè è íóëè âî âñåõ îñòàëüíûõ. Çàïèøåì ñòðîêè ìàòðèöû A â âèäå ai,× = ai1 e1 +ai2 e2 +· · ·+ain en . Áóäåì Îáîçíà÷èì ÷åðåç ei âåêòîð-ñòðîêó ðàçìåðíîñòè 36 ñ÷èòàòü îïðåäåëèòåëü, îïóñêàÿñü îò ïåðâîé ñòðîêè âíèç è ïðèìåíÿÿ ñâîéñòâà (1.26)-(1.27):    ej1 ej1  ej2   a2,×  n n n     X    a3,×  X X det A = a1j1 a2j2 det  a3,×  = . . . a1j1 det  =  ..   ..  j1 =1  .   .  j1 =1 j2 =1 an,× an,×    ej1 n X n n  ej2  X X   = ··· a1j1 a2j2 . . . anjn det  .  .  ..  j1 =1 j2 =1 jn =1 ejn Ïîëó÷åííîå âûðàæåíèå ïðåäñòàâëÿåò ñîáîé ñóììó nn ïðîèçâåäåíèé èç n êîýôôèöèåíòîâ aij , âçÿòûõ ïî îäíîìó èç êàæäîé ñòðîêè. Çàìåòèì, ÷òî îïðåäåëèòåëü ìàòðèöû, ñîñòàâëåííîé èç ejk , ðàâåí íóëþ, åñëè ëþáûå äâà èíäåêñà ñîâïàäàþò. Òàêèì îáðàçîì, îïðåäåëèòåëü íå (j1 , j2 , . . . , jn ) çàäàåò íåêîòîðóþ ïåðåñòàíîâêó. Íàêîíåö, âñïîìíèì, ÷òî îïðåäåëèòåëü ìàòðèöû ïåðåñòàíîâêè ðàâåí +1 åñëè ïåðåñòàíîâêà ÷åòíàÿ è −1 â ïðîòèâíîì ñëó÷àå. ñòðîê ðàâåí íóëþ ëèøü â òîì ñëó÷àå, êîãäà íàáîð Ïîêàæåì, ÷òî âûðàæåíèå (1.28) óäîâëåòâîðÿåò àêñèîìàì D1D3. Àêñèîìà D1 ñëåäóåò èç òîãî, ÷òî ýëåìåíòû êàæäîé ñòðîêè âõîäÿò â âûðàæåíèå äëÿ îïðåäåëèòåëÿ ëèíåéíî, ïðè ÷åì êàæäûé ýëåìåíò ñòðîêè âõîäèò ðîâíî â àêñèîìû D2, ïðåäñòàâèì, ÷òî â ìàòðèöå (1.28) äëÿ ïðåîáðàçîâàííîé ìàòðèöû det A0 = X A0 A (n−1)! ñëàãàåìîå. ×òîáû ïðîâåðèòü âûïîëíåíèå ïåðåñòàâëåíû ñòðîêè i1 è i2 . Òîãäà âûðàæåíèå ïðèíèìàåò âèä (−1)inv(π) a1,π(1) · . . . · ai2 ,π(i1 ) · . . . · ai1 ,π(i2 ) · . . . · an,π(n) = π∈Sn = X (−1)inv(π) a1,π(1) · . . . · ai1 ,π(i2 ) · . . . · ai2 ,π(i1 ) · . . . · an,π(n) . π∈Sn Ìû âèäèì, ÷òî ïîëó÷åííîå âûðàæåíèå îòëè÷àåòñÿ îò èñõîäíîãî òåì, ÷òî ê êàæäîé ïåðåñòàíîâêå π ∈ Sn ïðèìåíåíà òðàíñïîçèöèÿ i1 -ãî è i2 -ãî ýëåìåíòîâ. Èç Ñëåäñòâèÿ 1.7.4 ñëåäóåò, ÷òî â ýòîì ñëó÷àå ÷åòíîñòü âñåõ ïåðåñòàíîâîê ìåíÿåòñÿ íà ïðîòèâîïîëîæíóþ, ÷òî ñîîòâåòñòâóåò èçìåíåíèþ çíàêà ïåðåä îïðåäåëèòåëåì. Íàêîíåö, àêñèîìà D3 ìîæåò áûòü ïðîâåðåíà íåïîñðåäñòâåííî ïóòåì âû÷èñëåíèÿ îïðåäåëèòåëÿ. Åäèíñòâåííàÿ ïåðåñòàíîâêà, ñîîòâåòñòâóþùàÿ îòëè÷íûì îò íóëÿ êîýôôèöèåíòàì, áóäåò ðàâíà 37 π = id. Ãëàâà 2 Ïîëå êîìïëåêñíûõ ÷èñåë Áóäåò äîáàâëåíî ïîçæå.  êà÷åñòâå îïîðíîãî òåêñòà ìîæíî èñïîëüçîâàòü Ëåêöèè ïî àëãåáðå Ä.Ê. Ôàääååâà, ãë. II. Äîáàâèòü: ñâîéñòâà êîìïëåêñíî ñîïð., â ÷àñòí. (ᾱ)n = (α)n 38 Ãëàâà 3 Êîëüöî ïîëèíîìîâ 3.1 Êîëüöî  ýòîì ðàçäåëå ìû ïîçíàêîìèìñÿ ñ íîâîé àëãåáðàè÷åñêîé ñòðóêòóðîé: êîëüöîì (àíãë., ring). Êîëüöî ðàñøèðÿåò ïîíÿòèå ïîëÿ â òîì ñìûñëå, ÷òî îïðåäåëåíèå êîëüöà íå òðåáóåò ñóùåñòâîâàíèÿ ýëåìåíòîâ, îáðàòíûõ îòíîñèòåëüíî óìíîæåíèÿ. Êàê ìû óâèäèì äàëüøå, ýòî îñëàáëåíèå ïîçâîëÿåò ñóùåñòâåííî ðàñøèðèòü êëàññ ðàññìàòðèâàåìûõ îáúåêòîâ. Îïðåäåëåíèå 3.1.1. æåñòâî R Êîëüöîì (èëè àññîöèàòèâíûì êîëüöîì ñ åäèíèöåé) íàçûâàåòñÿ ìíî- âìåñòå ñ äâóìÿ îïåðàöèÿìè: íàçûâàþòñÿ ñëîæåíèå è óìíîæåíèå + : R × R → R, × : R × R → R, êîòîðûå ïðèâû÷íî a, b, c ∈ R óäîâëåòâîðÿþò ñâîéñòâàì, ïðè- è äëÿ âñåõ âåäåííûì â òàáëèöå 3.1. Òàáëèöà 3.1: Ñâîéñòâà êîëüöà Ñëîæåíèå Óìíîæåíèå Êîììóòàòèâíîñòü a+b=b+a Àññîöèàòèâíîñòü a + (b + c) = (a + b) + c Íåéòðàëüíûé ýëåìåíò ∃0 ∈ R : 0 + a = a + 0 = a Îáðàòíûé ýëåìåíò ∃(−a) ∈ R : a + (−a) = 0 Àññîöèàòèâíîñòü a(bc) = (ab)c Äèñòðèáóòèâíîñòü a × (b + c) = a × b + a × c (a + b) × c = a × c + b × c Íåéòðàëüíûé ýëåìåíò Åñëè, äîïîëíèòåëüíî, äëÿ âñåõ êîììóòàòèâíûì. a, b ∈ R ∃1 ∈ R : 1 × a = a âûïîëíÿåòñÿ a × b = b × a, è a×1=a êîëüöî íàçûâàåòñÿ Ìíîãèå èç ñâîéñòâ êîëüöà ìîãóò áûòü ïîëó÷åíû àíàëîãè÷íî òîìó, êàê ìû ïîëó÷èëè èõ äëÿ ïîëÿ. Íèæå ìû ïðèâåäåì èõ áåç äîêàçàòåëüñòâà. Ïîòîì óáðàòü è ññûëàòüñÿ íà ïîëå. 1. Ñóùåñòâóåò òîëüêî îäèí ýëåìåíò, íåéòðàëüíûé îòíîñèòåëüíî ñëîæåíèÿ. 39 2. Äëÿ ëþáîãî ýëåìåíòà êîëüöà ñóùåñòâóåò òîëüêî îäèí ýëåìåíò, îáðàòíûé ê íåìó îòíîñèòåëüíî ñëîæåíèÿ. 3. Ñóùåñòâóåò òîëüêî îäèí ýëåìåíò, íåéòðàëüíûé îòíîñèòåëüíî óìíîæåíèÿ. 4. Ýëåìåíòû, íåéòðàëüíûå îòíîñèòåëüíî ñëîæåíèÿ è óìíîæåíèÿ, íå ìîãóò ñîâïàäàòü: 0 6= 1. 5. ∀a ∈ R : a × 0 = 0, òî åñòü 6. Ýëåìåíò, îáðàòíûé ê ðàòíûé ê 1 b b íà ýëåìåíò, îá- (−b) = (−1) × b. R òàêîå, ÷òî äëÿ ëþáûõ a, b ∈ R èç ab = 0 îáëàñòüþ öåëîñòíîñòè (àíãë., integral domain). Êîììóòàòèâíîå êîëüöî ñëåäóåò a=0 3.2 Ïîëèíîìû èëè  ïîãëîùàþùèé ýëåìåíò ïî óìíîæåíèþ. ïî ñëîæåíèþ, ïîëó÷àåòñÿ ïóòåì óìíîæåíèÿ ïî ñëîæåíèþ: Îïðåäåëåíèå 3.1.2. b = 0, íàçûâàåòñÿ Äëÿ òîãî, ÷òîáû ôîðìàëüíî îïðåäåëèòü ïîíÿòèå ïîëèíîìà íàì ïîòðåáóþòñÿ äâà èíãðåäèåíòà: ìíîæåñòâî êîýôôèöèåíòîâ è íåèçâåñòíîå x. F, 1 êîòîðîå â äàëüíåéøåì ìû áóäåì ïîëàãàòü ïîëåì , Íà íà÷àëüíîì ýòàïå ìû íå áóäåì ïîëàãàòü, ÷òî x ïðèíàäëåæèò êàêîìó- òî îïðåäåëåííîìó ìíîæåñòâó è, âîîáùå, íå áóäåì îïðåäåëÿòü åãî ñâîéñòâà. Åäèíñòâåííàÿ îïåðàöèÿ íàä íåèçâåñòíûì, êîòîðàÿ íàì ïîíàäîáèòñÿ, ýòî óìíîæåíèå, â òîì ÷èñëå íà ïðîèçâîëüíîå ÷èñëî a ∈ F. Èñïîëüçóÿ îïåðàöèþ óìíîæåíèÿ ìû ìîæåì çàïèñàòü èíäóêòèâíî ïðîäîëæèòü ýòî îïðåäåëåíèå íà ñëó÷àé n x , ãäå n ∈ N0 . x · x = x2 è Êàê îáû÷íî, ïîëàãàåì x0 = 1. Îïðåäåëåíèå 3.2.1. Ïîëèíîì (ìíîãî÷ëåí) n-é ñòåïåíè îò íåèçâåñòíîãî x  ýòî âûðàæåíèå a0 xn + a1 xn−1 + · · · + an−1 x + an , ãäå F n ∈ N0 , à ai ∈ F , i = 0, . . . , n, a0 6= 0. F [x]. (3.1) Ìíîæåñòâî âñåõ ïîëèíîìîâ îò íåèçâåñòíîãî x íàä îáîçíà÷àåòñÿ Äëÿ ñîêðàùåííîé çàïèñè ïîëèíîìîâ ìû áóäåì èñïîëüçîâàòü âûðàæåíèÿ ä. Äîïóñòèìû ñëåäóþùèå âûðàæåíèÿ: f (x) = x5 − 1, g(x) = x3 + x, p(x) = 1 p(x), f (x) è ò. èëè q(x) = 0, òî åñòü ïîëèíîì ìîæåò áûòü ðàâåí êîíñòàíòå (â òîì ÷èñëå íóëþ). êîýôôèöèåíòàìè. Ñëàãàåìîå a0 xn íàçûâàåòñÿ ñòàðøèì ÷ëåíîì, à êîýôôèöèåíò a0  ñòàðøèì êîýôôèöèåíòîì. Ñòåïåíü ïîëèíîìà  âûðàæåíèè (3.1), ìíîæèòåëè ai íàçûâàþòñÿ îïðåäåëÿåòñÿ êàê ìàêñèìàëüíûé ïîêàçàòåëü ñòåïåíè ïðè íåèçâåñòíîì ñ íåíóëåâûì êîýô- deg(·). Òàê, â ïðèâåäåííûõ âûøå ïðèìåðàõ èìååì: deg(f (x)) = 5, deg(p(x)) = 0. Äëÿ îáåñïå÷åíèÿ íåïðîòèâîðå÷èâîñòè òåîðèè ìû áóäåì ïîëàíóëåâîé ïîëèíîì èìååò ñòåïåíü ðàâíóþ ìèíóñ áåñêîíå÷íîñòè, ò. å., deg(0) = −∞. ôèöèåíòîì è îáîçíà÷àåòñÿ deg(g(x)) = 3 ãàòü, ÷òî è Îïðåäåëåíèå 3.2.2. 1. Äëÿ ïîëèíîìîâ îïðåäåëåíû ñëåäóþùèå îïåðàöèè: Ðàâåíñòâî. Äâà ïîëèíîìà íàçûâàþòñÿ ðàâíûìè åñëè îíè èìåþò îäèíàêîâóþ ñòåïåíü è èõ êîýôôèöèåíòû ñîâïàäàþò. 1  êà÷åñòâå F ìîæíî ðàññìàòðèâàòü ïðîèçâîëüíóþ îáëàñòü öåëîñòíîñòè, íàïðèìåð, ìíîæåñòâî öåëûõ ÷èñåë. Îäíàêî â ýòîì ñëó÷àå íàøè âîçìîæíîñòè ñóùåñòâåííî ñóçÿòñÿ. Ïîçæå: Äîáàâèòü ïðî äåëåíèå öåëî÷èñëåííûõ ïîëèíîìîâ... 40 2. Ñëîæåíèå. Ñóììîé äâóõ ïîëèíîìîâ f (x) = a0 xn + a1 xn−1 + · · · + an−1 x + an è g(x) = b0 xm + b1 xm−1 + · · · + bm−1 x + bm ñòåïåíåé n è m íàçûâàåòñÿ ïîëèíîì p(x) = f (x) + g(x) = c0 xk + c1 xk−1 + · · · + ck−1 x + ck , êîýôôèöèåíòû êîòîðîãî ïîëó÷àþòñÿ ñëîæåíèåì êîýôôèöèåíòîâ ïðè íåèçâåñòíûõ ñ îäèíàêîâûìè ñòåïåíÿìè è îòáðàñûâàíèåì ñòàðøèõ ÷ëåíîâ ñ íóëåâûìè êîýôôèöèåíòàìè. Ñëîæåíèå ñ íóëåâûì ïîëèíîìîì íå èçìåíÿåò ðåçóëüòàò: p(x) + 0 = p(x), ∀p(x) ∈ F [x]. 3. Óìíîæåíèå. Ïðîèçâåäåíèåì äâóõ ïîëèíîìîâ f (x) = a0 xn + · · · + an−1 x + an è g(x) = b0 xm + · · · + bm−1 x + bm ñòåïåíåé n è m íàçûâàåòñÿ ïîëèíîì ñòåïåíè l = n + m, q(x) = f (x)g(x) = d0 xl +d1 xl−1 +· · ·+dl−1 x+dl , êîýôôèöèåíòû êîòîðîãî îïðåäåëÿþòñÿ ïî ñëåäóþùåé ôîðìóëå: di = X aj bk . (3.2) j,k j+k=i Óìíîæåíèå íà íóëåâîé ïîëèíîì âîçâðàùàåò íóëåâîé ïîëèíîì: 0 · p(x) = p(x) · 0 = 0, ∀p(x) ∈ F [x]. Çàìåòèì, ÷òî ñòàðøèé êîýôôèöèåíò ïîëèíîìà q(x), d0 , ðàâåí ïðîèçâåäåíèþ a0 è b0 , êîòîðûå ïî îïðåäåëåíèþ íå ðàâíû íóëþ. Òàêèì îáðàçîì, ñòåïåíü ïðîèçâåäåíèÿ äâóõ ïîëèíîìîâ âñåãäà ðàâíà ñóììå ñòåïåíåé ñîîòâåòñòâóþùèõ ïîëèíîìîâ: deg(p(x)q(x)) = deg(p(x)) + deg(q(x)). (3.3)  òî æå âðåìÿ, äëÿ ñòåïåíè ñóììû äâóõ ïîëèíîìîâ ìîæíî çàäàòü òîëüêî âåðõíþþ ãðàíèöó: deg(p(x) + q(x)) ≤ max(deg(p(x)), deg(q(x))). Íåðàâåíñòâî (3.4) ïðåâðàùàåòñÿ â ðàâåíñòâî, åñëè (3.4) deg(p(x)) 6= deg(q(x)). Ïðîâåðêà ýòîãî ôàêòà îñòàâëÿåòñÿ ÷èòàòåëþ â êà÷åñòâå óïðàæíåíèÿ. Òåïåðü ñòàíîâèòñÿ ïîíÿòåí âûáîð ñîãëàøåíèÿ deg(0) = −∞ ïðè îïðåäåëåíèè ñòåïåíè ïîëèíîìà. Êàê ëåãêî çàìåòèòü, ëþáîé äðóãîé âûáîð ïðîòèâîðå÷èë áû âûðàæåíèþ (3.3). Óòâåðæäåíèå 3.2.1. Ñ ââåäåííûìè îïåðàöèÿìè ñëîæåíèÿ è óìíîæåíèÿ, ìíîæåñòâî ïîëèíîìîâ F [x] ïðèîáðåòàåò ñòðóêòóðó êîììóòàòèâíîãî êîëüöà. Äîêàçàòåëüñòâî. Àññîöèàòèâíîñòü è êîììóòàòèâíîñòü ñëîæåíèÿ ñëåäóåò èç àññîöèàòèâ- íîñòè è êîììóòàòèâíîñòè ñëîæåíèÿ äëÿ ìíîæåñòâà F . Ñóùåñòâîâàíèå íåéòðàëüíîãî ýëåìåí- òà ñëåäóåò èç îïðåäåëåíèÿ, à îáðàòíûé ýëåìåíò îòíîñèòåëüíî ñëîæåíèÿ ïîëó÷àåòñÿ ïóòåì óìîæåíèÿ ïîëèíîìà íà îáðàòíûé ê åäèíè÷íîìó ïîëèíîìó: −p(x) = (−1) · p(x). Ðàññìîòðèì áîëåå ïîäðîáíî ñâîéñòâà ïîëèíîìîâ îòíîñèòåëüíî óìíîæåíèÿ. Êîììóòàòèâíîñòü óìíîæåíèÿ ñëåäóåò èç òîãî, ÷òî â âûðàæåíèè (3.2) èíäåêñû j è k ìîãóò áûòü ïåðåñòàâëåíû áåç èçìåíåíèÿ ñìûñëà âûðàæåíèÿ. Äëÿ îïðåäåëåíèÿ àññîöèàòèâíîñòè çàïèïîëèíîìîâ f (x), g(x) i,α i+α=l dl d0l â ïðîèçâåäåíèÿõ f (x)(g(x)p(x)) è (f (x)g(x))p(x) p(x) ñ êîýôôèöèåíòàìè ai , bj è ck :     X X X X X     dl = ai  bj c k  = ai bj ck = ai bj  ck = d0l .  øåì âûðàæåíèÿ äëÿ êîýôôèöèåíòîâ è è j,k j+k=α i,j,k i+j+k=l α,k α+k=l i,j i+j=α Àíàëîãè÷íî äîêàçûâàåòñÿ äèñòðèáóòèâíîñòü óìíîæåíèÿ îòíîñèòåëüíî ñëîæåíèÿ. 41 3.2.1 Äåëèìîñòü ïîëèíîìîâ Íàðÿäó ñ ìíîæåñòâîì ïîëèíîìîâ, îäíèì èç òèïè÷íûõ ïðèìåðîâ êîììóòàòèâíîãî êîëüöà ÿâëÿåòñÿ ìíîæåñòâî öåëûõ ÷èñåë. Îêàçûâàåòñÿ, ÷òî ýòè ìíîæåñòâà èìåþò ìíîãî îáùåãî. Òàê, ìû ìîæåì îïðåäåëèòü äëÿ ïîëèíîìîâ îïåðàöèè äåëåíèÿ ñ îñòàòêîì è íàõîæäåíèÿ íàèáîëüøåãî îáùåãî ìíîæèòåëÿ. Òåîðåìà 3.2.2. Äëÿ ëþáûõ ïîëèíîìîâ f (x), g(x) ∈ F [x], g(x) 6= 0, åäèíñòâåííûì îáðàçîì îïðåäåëåíû ïîëèíîìû q(x) è r(x)2 òàêèå, ÷òî âûïîëíÿåòñÿ f (x) = g(x)q(x) + r(x) (3.5) è ñòåïåíü r(x) ñòðîãî ìåíüøå ñòåïåíè g(x) (÷òî âêëþ÷àåò â ñåáÿ ñëó÷àé r(x) = 0). Äîêàçàòåëüñòâî. Äîêàæåì ñíà÷àëà ñóùåñòâîâàíèå, à çàòåì åäèíñòâåííîñòü. deg(f (x)) < deg(g(x)) (÷òî âêëþ÷àåò â ñåáÿ r(x) = f (x).  îáùåì ñëó÷àå deg(f (x)) ≥ deg(g(x)), 1. Ñíà÷àëà ðàññìîòðèì ÷àñòíûé ñëó÷àé f (x) = 0). q(x) = 0 Òîãäà èìååì è äåëåíèå îñóùåñòâëÿåòñÿ ñîãëàñíî ñëåäóþùåìó àëãîðèòìó: ADD: Àëãîðèòì äåëåíèÿ ïîëèíîìîâ. 2. Ïóñòü íàðÿäó ñ ïîëèíîìàìè deg(r̃(x)) < deg(g(x)), q(x) è r(x) óäîâëåòâîðÿþùèå ìîãóò áûòü íàéäåíû ïîëèíîìû f (x) = g(x)q̃(x) + r̃(x). q̃(x) è r̃(x), Âû÷èòàÿ ïîñëåäíåå âûðàæåíèå èç (3.5) è ïåðåãðóïïèðîâûâàÿ ÷ëåíû ïîëó÷àåì g(x)[q(x) − q̃(x)] = r̃(x) − r(x). (3.6) Èñïîëüçóÿ ïðàâèëà îïðåäåëåíèÿ ñòåïåíåé ñóììû è ïðîèçâåäåíèÿ ïîëèíîìîâ ïîëó÷àåì deg (g(x)[q(x) − q̃(x)]) = deg(g(x)) + deg(q(x) − q̃(x)) = deg(r̃(x) − r(x)) < deg(g(x)), deg(q(x) − q̃(x)) < 0, ÷òî ñîîòâåòñòâóåò q(x) − q̃(x) = 0 èëè q(x) = q̃(x). q(x) − q̃(x) = 0 â (3.6) ïîëó÷àåì r̃(x) = r(x), ÷òî è òðåáîâàëîñü äîêàçàòü. îòêóäà ñëåäóåò Ïîäñòàâëÿÿ Òàê æå. êàê è â ñëó÷àå öåëûõ ÷èñåë, ìû áóäåì íàçûâàòü ïîëèíîì  îñòàòêîì íà g(x). Ïîëèíîì g(x) îò äåëåíèÿ Îïðåäåëåíèå 3.2.3. g(x) äåëèò f (x), f (x) íàçûâàåòñÿ åñëè ñóùåñòâóåò ïîëèíîì ñëó÷àå ìû áóäåì ïèñàòü q(x), äåëèòåëåì q(x) ÷àñòíûì, à r(x) f (x), èíà÷å ãîâîðÿ, f (x) = g(x)q(x).  ýòîì ïîëèíîìà óäîâëåòâîðÿþùèé f (x) : g(x). Íèæå ñôîðìóëèðîâàí ðÿä ñâîéñòâ äåëèìîñòè ïîëèíîìîâ, êîòîðûå áóäóò èñïîëüçîâàòüñÿ â äàëüíåéøåì. Òåîðåìà 3.2.3. íà p(x). 1. Åñëè f (x) äåëèòñÿ íà g(x), à g(x) äåëèòñÿ íà p(x), òî f (x) äåëèòñÿ 2. Åñëè f (x) è g(x) äåëÿòñÿ íà p(x), òî f (x) ± g(x) äåëèòñÿ íà p(x). 3. Åñëè f (x) äåëèòñÿ íà p(x), òî f (x)g(x) äåëèòñÿ íà p(x) äëÿ ëþáîãî g(x) ∈ F [x], g(x) 6= 0. 2 Áóêâû q è r îòñûëàþò ê àíãëèéñêèì ñëîâàì quotient, ÷àñòíîå è remainder, îñòàòîê. 42 f (x) : g(x) 4. Âñÿêèé ïîëèíîì f (x) äåëèòñÿ íà ëþáîé ïîëèíîì íóëåâîé ñòåïåíè: f (x) : γ , γ ∈ F . 5. Ïîëèíîìû f (x) è g(x) îäíîâðåìåííî äåëÿòñÿ äðóã íà äðóãà òîãäà è òîëüêî òîãäà, êîãäà f (x) = γg(x), γ ∈ F , γ 6= 0. Äîêàçàòåëüñòâî. ïîëíÿåòñÿ 1. Ïî îïðåäåëåíèþ, ñóùåñòâóþò f (x) = g(x)φ(x) è g(x) = p(x)ψ(x). φ(x), ψ(x) ∈ F [x] òàêèå, ÷òî âû- Ïîäñòàâëÿÿ ïîñëåäíåå âûðàæåíèå â ïðåäïîñëåäíåå è èñïîëüçóÿ ñâîéñòâî àññîöèàòèâíîñòè óìíîæåíèÿ ïîëó÷èì f (x) = (p(x)ψ(x))φ(x) = p(x) (ψ(x)φ(x)). 2. Àíàëîãè÷íî ïðåäûäóùåìó ñëó÷àþ, èç f (x) = p(x)φ(x) è g(x) = p(x)ψ(x) ñëåäóåò f (x)± g(x) = p(x)[φ(x) ± ψ(x)]. 3. Èç f (x) = p(x)φ(x) 4. Äîìíîæàÿ f (x) íà f (x) = (p(x)φ(x)) g(x) = p(x) (φ(x)g(x)).   an−1 an a0 n ïîëó÷èì f (x) = γ x + · · · + x + γ γ γ . ñëåäóåò γ è 1 γ g(x) = γ1 f (x), ò. å. f (x) è g(x) îäíîâðåìåííî äåëÿò äðóã äðóãà. Ñ äðóãîé ñòîðîíû, åñëè f (x) è g(x) îäíîâðåìåííî äåëÿò äðóã äðóãà, òî ñóùåñòâóþò òàêèå ïîëèíîìû φ(x) è ψ(x), ÷òî âûïîëíÿåòñÿ f (x) = g(x)φ(x) è g(x) = f (x)ψ(x). Èç àíàëèçà ðàçìåðíîñòåé ïîëó÷àåì 5. Åñëè f (x) = γg(x), òî âûïîëíÿåòñÿ deg(f (x)) = deg(g(x)) + deg(φ(x)), deg(g(x)) = deg(f (x)) + deg(ψ(x)). Ñêëàäûâàÿ óðàâíåíèÿ è ñîêðàùàÿ ïîäîáíûå ïðèõîäèì ê ðàâåíñòâó 0, ò. å. ïîëèíîìû φ(x) γ ∈ F \ {0}. 3.2.2 è ψ(x) deg(φ(x))+deg(ψ(x)) = f (x) = γg(x), èìåþò íóëåâóþ ñòåïåíü. Ñëåäîâàòåëüíî, Íàèáîëüøèé îáùèé äåëèòåëü Îïðåäåëåíèå 3.2.4. Ïîëèíîì p(x) íàçûâàåòñÿ îáùèì äåëèòåëåì ïîëèíîìîâ f (x) è g(x), f (x) è g(x). Ïîëèíîì p(x) íàçûâàåòñÿ íàèáîëüøèì îáùèì äåëèòåëåì ïîëèg(x), îáîçíà÷àåòñÿ p(x) = ÍÎÄ (f (x), g(x)), åñëè îí åñëè îí äåëèò íîìîâ f (x) è • ÿâëÿåòñÿ îáùèì äåëèòåëåì • äåëèòñÿ íà ëþáîé äðóãîé îáùèé äåëèòåëü f (x) è g(x) f (x) è g(x). Íàõîæäåíèå íàèáîëüøåãî îáùåãî äåëèòåëÿ èñïîëüçóåòñÿ äëÿ ðåøåíèÿ ðÿäà çàäà÷ àëãåáðû ïîëèíîìîâ, íàïðèìåð, äëÿ íàõîæäåíèå êðàòíûõ êîðíåé ïîëèíîìîâ, ïðè ôàêòîðèçàöèè ïîëèíîìîâ è ò. ä.  ñâÿçè ñ ýòèì âàæíî èìåòü ýôôåêòèâíûé àëãîðèòì äëÿ âû÷èñëåíèÿ íàèáîëüøåãî îáùåãî äåëèòåëÿ. Íèæå ìû ðàññìîòðèì àëãîðèòì Åâêëèäà, êîòîðûé  ñ íåêîòîðûìè ìîäèôèêàöèÿìè  èñïîëüçóåòñÿ âî âñåõ ñîâðåìåííûõ ñèñòåìàõ êîìïüþòåðíîé àëãåáðû. Ïóñòü äàíû äâà ïîëèíîìà f (x) è g(x) òàêèå, ÷òî deg(f (x)) ≥ deg(g(x)) (â ïðîòèâíîì ñëóÀëãîðèòì Åâêëèäà íàõîæäåíèÿ íàèáîëüøåãî îáùåãî äåëè- ÷àå ïåðåîáîçíà÷èì ïîëèíîìû). òåëÿ ïîëèíîìîâ îò äåëåíèÿ f (x) f (x) è g(x) çàêëþ÷àåòñÿ â ñëåäóþùåì: íà ïåðâîì øàãå âû÷èñëÿåòñÿ ÷àñòíîå íà g(x), r1 (x). Çàïèñûâàåòñÿ ïîñëåäîâàòåëüíîñòü (f (x), g(x), r1 (x)). Ñëåäó- þùèé ÷ëåí ïîñëåäîâàòåëüíîñòè ïîëó÷àåòñÿ êàê ÷àñòíîå îò äåëåíèÿ ïðåäïîñëåäíåãî ÷ëåíà íà ïîñëåäíèé, ò. å. ÷àñòíîå îò äåëåíèÿ g(x) íà r1 (x). Ïîëó÷èâøèéñÿ ïîëèíîì äîáàâëÿåò- ñÿ ê ïîñëåäîâàòåëüíîñòè è ïðîöåäóðà ïîâòîðÿåòñÿ ñíîâà. Àëãîðèòì Åâêëèäà çàâåðøàåòñÿ, 43 êîãäà ÷àñòíîå îò î÷åðåäíîãî äåëåíèÿ ðàâíî íóëþ (ò. å. ïîñëåäíèé ïîëèíîì äåëèò íàöåëî ïðåäïîñëåäíèé). Ïîñëåäíèé ïîëèíîì â ïîñëåäîâàòåëüíîñòè è ÿâëÿåòñÿ ÍÎÄ (f (x), g(x)). Çàïèøåì àëãîðèòì Åâêëèäà â âèäå ïîñëåäîâàòåëüíîñòè îïåðàöèé äåëåíèÿ ñ îñòàòêîì. f (x) = g(x) q1 (x) + r1 (x), (3.7a) g(x) = r1 (x) q2 (x) + r2 (x), (3.7b) r1 (x) = r2 (x) q3 (x) + r3 (x), (3.7c) ... rk−3 (x) = rk−2 (x) qk−1 (x) + rk−1 (x), (3.7d) rk−2 (x) = rk−1 (x) qk (x) + rk (x), (3.7e) rk−1 (x) = rk (x) qk+1 (x), (3.7f ) rk (x) = ÍÎÄ (f (x), g(x)). Òåîðåìà 3.2.4. Ëþáûå äâà ïîëèíîìà èìåþò íàèáîëüøèé îáùèé äåëèòåëü, êîòîðûé ìîæåò áûòü íàéäåí ñ ïîìîùüþ àëãîðèòìà Åâêëèäà Äîêàçàòåëüñòâî. Ïî îïðåäåëåíèþ äåëåíèÿ ñ îñòàòêîì, ñòåïåíü ÷àñòíîãî ñòðîãî ìåíüøå ñòåïåíè äåëèòåëÿ. Ïîýòîìó â ïîñëåäîâàòåëüíîñòè íîì, íà÷èíàÿ ñ (3.7). r1 (x), f (x), g(x), r1 (x), r2 (x), . . . , êàæäûé ïîëè- áóäåò èìåòü ñòåïåíü ñòðîãî ìåíüøå ïðåäûäóùåãî. Ýòî çíà÷èò, ÷òî àëãîðèòì Åâêëèäà ñõîäèòñÿ. rk (x) äåéñòâèòåëüíî ÿâëÿåòñÿ îáùèì äåëèòåëåì f (x) è g(x). Èç rk (x) äåëèò rk−1 (x). Äàëüøå, â (3.7e) îáà ñëàãàåìûõ â ïðàâîé ÷àñòè ðàâåíñòâà äåëèòñÿ íà rk (x), ñëåäîâàòåëüíî rk−2 (x) òàêæå äåëèòñÿ íà rk (x). Ïîäíèìàÿñü äàëüøå ìû âèäèì, ÷òî rk−3 (x) è äàëåå âïëîòü äî r1 (x) âñå äåëÿòñÿ íà rk (x). Íàêîíåö, èç (3.7a) è (3.7b) ñëåäóåò, ÷òî f (x) è g(x) äåëÿòñÿ íà rk (x). Òåïåðü ïðåäïîëîæèì, ÷òî íåêîòîðûé ïîëèíîì ψ(x) ÿâëÿåòñÿ îáùèì äåëèòåëåì f (x) è g(x). Èç (3.7a) ñëåäóåò, ÷òî r1 (x) òàêæå äåëèòñÿ íà ψ(x). Ñïóñêàÿñü âíèç è ñëåäóÿ òîé æå ëîãèêå, ìû ïîëó÷àåì, ÷òî âñå îñòàòêè âïëîòü äî rk (x) äåëÿòñÿ íà ψ(x). Òàêèì îáðàçîì, ïî îïðåäåëåíèþ rk (x) ÿâëÿåòñÿ íàèáîëüøèì îáùèì äåëèòåëåì. Ïîêàæåì, ÷òî â (3.7) (3.7f) ñëåäóåò, ÷òî Ïðèâåäåííîå äîêàçàòåëüñòâî ìîæåò áûòü èñïîëüçîâàíî äëÿ ïîëó÷åíèÿ îöåíêè íà ñòåïåíü íàèáîëüøåãî îáùåãî äåëèòåëÿ. Ñëåäñòâèå 3.2.5. Ñòåïåíü íàèáîëüøåãî îáùåãî äåëèòåëÿ p(x) = ÍÎÄ (f (x), g(x)) óäîâëå- òâîðÿåò íåðàâåíñòâó deg(p(x)) ≤ min(deg(f (x)), deg(g(x))), ïðè÷åì ðàâåíñòâî èìååò ìåñòî òîëüêî â òîì ñëó÷àå, êîãäà ïîëèíîì ìåíüøåé ñòåïåíè äåëèò íàöåëî ïîëèíîì áîëüøåé ñòåïåíè. Î÷åâèäíî, ÷òî íàèáîëüøèé îáùèé äåëèòåëü îïðåäåëÿåòñÿ ñ òî÷íîñòüþ äî óìíîæåíèÿ íà ïîëèíîì íóëåâîé ñòåïåíè (ò. å. íà íåíóëåâîå ÷èñëî). Ïîýòîìó âñåãäà ìîæíî âûáèðàòü íàèáîëüøèé îáùèé äåëèòåëü òàêèì îáðàçîì, ÷òî ñòàðøèé êîýôôèöèåíò ðàâåí 1. Ïðèìåð 3.2.1. Íàõîæäåíèå ÍÎÄ. Òåîðåìà 3.2.6. Åñëè p(x) = ÍÎÄ (f (x), g(x)), òî ñóùåñòâóþò ïîëèíîìû u(x) è v(x), äëÿ êîòîðûõ âûïîëíÿåòñÿ ðàâåíñòâî f (x)u(x) + g(x)v(x) = p(x). (3.8) Ïðè ýòîì ïîëèíîìû u(x) è v(x) óäîâëåòâîðÿþò óñëîâèÿì deg(u(x)) < deg(g(x)), deg(v(x)) < deg(f (x)). 44 (3.9) Äîêàçàòåëüñòâî. Äëÿ äîêàçàòåëüñòâà èñïîëüçóåì âûðàæåíèÿ (3.7).  âûðàæåíèè (3.7e), rk (x) = ÍÎÄ (rk−2 (x), rk−1 (x)). Âûáèðàÿ u(x) = 1 è v(x) = −qk (x) ïîëó÷àåì rk−2 (x)uk−1 (x) + rk−1 (x)vk−1 (x) = rk (x). rk−1 (x) èç (3.7d) rk−3 (x) è rk−2 (x): Ïîäñòàâëÿÿ â (3.10) âûðàæåíèå äëÿ ñàòü âûðàæåíèå òèïà (3.8) äëÿ (3.10) è ñîáèðàÿ ïîäîáíûå ìû ìîæåì çàïè- rk−3 (x)uk−2 (x) + rk−2 (x)vk−2 (x) = rk (x), ãäå (3.11) uk−2 (x) = vk−1 (x) è vk−2 (x) = uk−1 (x)−qk−1 (x)vk−1 (x). Ïðîäîëæàÿ ïîäíèìàòüñÿ íàâåðõ ïî óðàâåíèÿì (3.7), ìû íàêîíåö ïðèäåì ê âûðàæåíèþ f (x)u0 (x) + g(x)v0 (x) = rk (x), ÷òî ñîîòâåòñòâóåò (3.8). Äëÿ òîãî, ÷òîáû ïðîâåðèòü óñëîâèÿ (3.9), ïðåäïîëîæèì, ÷òî íàéäåíû íåêîòîðûå ïîëèíîìû ũ(x) è ṽ(x), óäîâëåòâîðÿþùèå óðàâíåíèþ (3.8). Ïóñòü ïðè ýòîì deg ũ(x) ≥ deg(g(x)). ũ(x) íà g(x), ũ(x) = g(x)q(x) + r(x), è ïîäñòàâèì ïîëó÷èâøååñÿ âûðàæåíèå â (3.8): Ïîäåëèì f (x)r(x) + g(x)[f (x)q(x) + ṽ(x)] = p(x).  ïîëó÷åííîì âûðàæåíèè øå ñòåïåíè f (x), deg(r(x)) < deg(g(x)). Còåïåíü ìíîæèòåëÿ ïðè g(x) ñòðîãî ìåíü- ò.ê. â ïðîòèâíîì ñëó÷àå ñòåïåíü âòîðîãî ñëàãàåìîãî, à âìåñòå ñ òåì è ñòåïåíü âñåãî âûðàæåíèÿ â ëåâîé ÷àñòè áûëà áû áîëüøå èëè ðàâíà deg(f (x)) + deg(g(x)), ÷òî ïðîòèâîðå÷èò ñëåäñòâèþ 3.2.5. 3.2.3 Âçàèìíî ïðîñòûå ïîëèíîìû Îïðåäåëåíèå 3.2.5. Ïîëèíîìû f (x) è g(x) íàçûâàþòñÿ âçàèìíî ïðîñòûìè (àíãë., coprime), åñëè îíè íå èìåþò îáùèõ äåëèòåëåé, çà èñêëþ÷åíèåì ïîëèíîìîâ íóëåâîé ñòåïåíè. Äëÿ âçàèìíî ïðîñòûõ ïîëèíîìîâ âåðíî ÍÎÄ (f (x), g(x)) = 1. Ñîîòâåòñòâåííî, ìîæíî ñôîðìóëèðîâàòü ñëåäóþùåå ñëåäñòâèå èç òåîðåìû 3.2.6. Óòâåðæäåíèå 3.2.7. Ìíîãî÷ëåíû f (x) è g(x) âçàèìíî ïðîñòû òîãäà è òîëüêî òîãäà, êîãäà ñóùåñòâóþò äâà ïîëèíîìà u(x) è v(x), óäîâëåòâîðÿþùèå f (x)u(x) + g(x)v(x) = 1. Òåîðåìà 3.2.8. Âçàèìíî ïðîñòûå ïîëèíîìû óäîâëåòâîðÿþò ñëåäóþùèì ñâîéñòâàì: 1. Åñëè ÍÎÄ (f (x), φ(x)) = 1 è ÍÎÄ (f (x), ψ(x)) = 1, òî âûïîëíÿåòñÿ ÍÎÄ (f (x), φ(x)ψ(x)) = 1. 2. Åñëè ïðîèçâåäåíèå f (x)g(x) äåëèòñÿ íà φ(x), íî ïðè ýòîì ÍÎÄ (f (x), φ(x)) = 1, òî g(x) äåëèòñÿ íà φ(x). 3. Åñëè f (x) äåëèòñÿ íà φ(x) è íà ψ(x), ïðè÷åì ÍÎÄ (φ(x), ψ(x)) = 1, òî f (x) äåëèòñÿ è íà ïðîèçâåäåíèå φ(x)ψ(x). 45 Äîêàçàòåëüñòâî. è 1. Åñëè ÍÎÄ (f (x), φ(x)) = 1, òî ìîæíî íàéòè òàêèå ïîëèíîìû u(x) v(x), ÷òî f (x)u(x) + φ(x)v(x) = 1. Äîìíîæàÿ îáå ÷àñòè âûðàæåíèÿ íà ψ(x), ïîëó÷èì f (x)[u(x)ψ(x)] + [φ(x)ψ(x)]v(x) = ψ(x). Åñëè áû ñóùåñòâîâàë îáùèé äåëèòåëü Îäíàêî ïî óñëîâèþ f (x) è ψ(x) f (x) è φ(x)ψ(x), òî îí òàêæå äåëèë áû è ψ(x). íå èìåþò íåòðèâèàëüíûõ îáùèõ äåëèòåëåé. 2. Àíàëîãè÷íî ïðåäûäóùåìó ñëó÷àþ, çàïèøåì f (x)u(x) + φ(x)v(x) = 1. Óìíîæàÿ íà g(x) ïîëó÷àåì [f (x)g(x)]u(x) + φ(x)[v(x)g(x)] = g(x). Îáà ñëàãàåìûõ â ïðàâîé ÷àñòè âûðàæåíèÿ äåëÿòñÿ íà äåëèòñÿ íà φ(x). Ñëåäîâàòåëüíî g(x) òàêæå φ(x). f (x) äåëèòñÿ íà φ(x), ìû ìîæåì çàïèñàòü f (x) = φ(x)q(x). Ïî óñëîâèþ, φ(x)q(x) äåëèòñÿ íà ψ(x), ïðè÷åì ÍÎÄ (φ(x), ψ(x)) = 1. Ñëåäîâàòåëüíî, ñîãëàñíî ïóíê0 òó 2 ýòîé òåîðåìû, q(x) äåëèòñÿ íà ψ(x), ò. å. q(x) = ψ(x)q (x). Ñîáèðàÿ âìåñòå âñå âûðàæåíèÿ, çàïèøåì f (x) = [φ(x)ψ(x)]q (x), îòêóäà ñëåäóåò òðåáóåìûé ðåçóëüòàò. 3. Ïîñêîëüêó 3.3 Öåëûå ðàöèîíàëüíûå (ïîëèíîìèàëüíûå) ôóíêöèè Äî ñèõ ïîð ìû ðàññìàòðèâàëè ïîëèíîìû êàê íåêîòîðûå àáñòðàêòíûå àëãåáðàè÷åñêèå îáúåêòû, äëÿ êîòîðûõ îïðåäåëåíû îïåðàöèè ñëîæåíèÿ, óìíîæåíèÿ, à òàêæå äåëåíèÿ è íàõîæäåíèÿ íàèáîëüøåãî îáùåãî äåëèòåëÿ.  ýòîé ãëàâå ìû áóäåì ðàññìàòðèâàòü ïîëèíîìû êàê ôóíêöèè, ñòàâÿùèå â ñîîòâåòñòâèå íåêîòîðîìó ÷èñëó ξ∈F âûðàæåíèå f (ξ) = a0 ξ n + · · · + an−1 ξ + an . (3.12) öåëûìè ðàöèîíàëüíûìè (ïîëèíîìèàëüíûìè) çíà÷åíèåì ôóíêöèè (ïîëèíîìà) f (x) ∈ F [x] â Ôóíêöèè, èìåþùèå âèä (3.12) íàçûâàþòñÿ ôóíêöèÿìè, à âåëè÷èíà òî÷êå f (ξ) íàçûâàåòñÿ x = ξ ∈ F. Íåñìîòðÿ íà òî, ÷òî çàäà÷à âû÷èñëåíèÿ çíà÷åíèé ôóíêöèé âûõîäèò çà ïðåäåëû àëãåáðû, ìû óâèäèì, ÷òî ðåøåíèå ìíîãèõ çàäà÷, îòíîñÿùèõñÿ ñêîðåå ê àíàëèçó èëè ÷èñëåííûì ìåòîäàì, íàïðèìåð òàêèõ êàê èíòåðïîëÿöèÿ, èíòåãðèðîâàíèå èëè íàõîæäåíèÿ êîðíåé ðàöèîíàëüíûõ ôóíêöèé ñóùåñòâåííî îïèðàåòñÿ íà èñïîëüçîâàíèå àëãåáðàè÷åñêèõ ìåòîäîâ. â òî÷êå ξ . n2 +3n îïåðàöèé 2 îïåðàöèé ñëîæåíèÿ. Ñîêðàòèòü ÷èñëî òðåáóåìûõ îïåðàöèé ìîæíî çà ñ÷åò Íà÷íåì ñ âû÷èñëåíèÿ çíà÷åíèÿ íåêîòîðîé ïîëèíîìèàëüíîé ôóíêöèè Äëÿ ïîëèíîìà ñòåïåíè óìíîæåíèÿ è n n f (x) â îáùåì ñëó÷àå íàì ïîòðåáîâàëîñü áû âûïîëíèòü 3 èñïîëüçîâàíèè ñõåìû Ãîðíåðà . Çàïèøåì ïîëèíîì f (x) â âèäå f (x) = ((((a0 x + a1 )x + a2 ) x + . . . ) x + an−1 ) x + an . 3 William George Horner (1786  1837). Íàðÿäó ñî ñâîèìè ìàòåìàòè÷åñêèìè èññëåäîâàíèÿìè èçâåñòåí èçîáðåòåíèåì çîîòðîïà  ïðîòîòèïà ñîâðåìåííîãî êèíî. Ïðè ýòîì èçîáðåòàòåëåì ñõåìû Ãîðíåðà îí íå ÿâëÿåòñÿ  âïåðâûå îíà áûëà ïðåäëîæåíà èòàëüÿíñêèì ìàòåìàòèêîì Ïàîëî Ðóôôèíè (Paolo Runi, 17651822), àâòîðîì ìíîãî÷èñëåííûõ ðàáîò â îáëàñòè ðåøåíèÿ àëãåáðàè÷åñêèõ óðàâíåíèé. 46 Áóäåì âû÷èñëÿòü çíà÷åíèå f (x) â òî÷êå ξ íà÷èíàÿ ñî âíóòðåííåé ñêîáêè è çàïèñûâàòü ïîëó÷èâøèåñÿ âûðàæåíèÿ: b0 = a0 b1 = b0 ξ + a1 b2 = b1 ξ + a2 (3.13) ... bn−1 = bn−2 ξ + an−1 bn = bn−1 ξ + an = f (ξ) Òàêèì îáðàçîì, ìû âû÷èñëèëè çíà÷åíèå ôóíêöèè èñïîëüçîâàâ âñåãî ëèøü æåíèÿ è n n îïåðàöèé óìíî- îïåðàöèé ñëîæåíèÿ. Îäíàêî ýòî åùå íå âñå. Îêàçûâàåòñÿ, ÷òî ïðîìåæóòî÷íûå êîýôôèöèåíòû bi , êîòîðûå ìû âû÷èñëèëè äëÿ òîãî, ÷òîáû ïîëó÷èòü bn = f (ξ), èìåþò ñàìî- ñòîÿòåëüíîå çíà÷åíèå, êàê ïîêàçûâàåò ñëåäóþùåå óòâåðæäåíèå, êîòîðîå ïðåäñòàâëÿåò ñîáîé âàðèàíò ò.í. ìàëîé òåîðåìû Áåçó4 . Óòâåðæäåíèå 3.3.1. ×àñòíîå îò äåëåíèÿ f (x) = a0 xn + · · · + an−1 x + an íà ëèíåéíûé äåëèòåëü (x − ξ) èìååò âèä q(x) = b0 xn−1 + · · · + bn−2 x + bn−1 , à îñòàòîê bn ðàâåí çíà÷åíèþ f (x) â òî÷êå x = ξ , ïðè÷åì êîýôôèöèåíòû bi , i = 0, . . . , n, íàõîäÿòñÿ ïî ôîðìóëå (3.13). Äîêàçàòåëüñòâî. Ïðèìåð 3.3.1. 3.3.1 XXX XXX Êîðíè ïîëèíîìà Îïðåäåëåíèå 3.3.1. Êîðíåì ïîëèíîìà f (x) ∈ F [x] (íóëåì ïîëèíîìèàëüíîé ôóíêöèè5 ) íàçûâàåòñÿ ÷èñëî ξ ∈ F, óäîâëåòâîðÿþùåå f (ξ) = 0. Ïðèìåíèì ðåçóëüòàò óòâåðæäåíèÿ 3.3.1 ê çàäà÷å íàõîæäåíèÿ êîðíåé ïîëèíîìà. Óòâåðæäåíèå 3.3.2. ×èñëî ξ òîãäà è òîëüêî òîãäà ÿâëÿåòñÿ êîðíåì ïîëèíîìà f (x), êîãäà f (x) äåëèòñÿ íà (x − ξ). Äîêàçàòåëüñòâî. XXX F . Íàïðèf (x) = x2 − 2 êàê ýëåìåíò Q[x], òî îêàæåòñÿ, ÷òî íå ñóùåñòâóåò òàêèõ ξ ∈ Q, ÷òî f (ξ) = 0.  òî æå âðåìÿ, ïîìåùàÿ òîò æå ïîëèíîì â áîëåå √ øèðîêîå ìíîæåñòâî R[x], ìû ëåãêî íàéäåì åãî êîðíè êàê ξ = ± 2 ∈ R. Îäíàêî, ñêàæåì, 2 óæå ïîëèíîì f (x) = x + 2 íå èìååò êîðíåé íè â Q, íè â R.  ýòîì ñëó÷àå íåîáõîäèìî ðàññìàòðèâàòü åùå áîëåå øèðîêîå ìíîæåñòâî C, êîòîðîå áóäåò ñîäåðæàòü èñêîìûå êîðíè √ ξ = ±ı 2 ∈ C. Ê ñ÷àñòüþ, íà ýòîì ìû ñìîæåì îñòàíîâèòüñÿ. Êàê ìû ñêîðî óâèäèì, âñå êîðíè ïðîèçâîëüíîãî ïîëèíîìà ñ êîýôôèöèåíòàìè èç Q, R èëè C ñîäåðæàòñÿ â ìíîæåñòâå êîìïëåêñíûõ ÷èñåë C. Çàìåòèì, ÷òî âîïðîñ ñóùåñòâîâàíèÿ êîðíåö ïîëèíîìà çàâèñèò îò ìíîæåñòâà ìåð, åñëè ìû ðàññìîòðèì ïîëèíîì 4 Etienne
B
ezout (1730  1783), èçâåñòåí ñâîèìè ðàáîòàìè â îáëàñòè ðåøåíèÿ ñèñòåì àëãåáðàè÷åñêèõ óðàâíåíèé. 5  ñâÿçè ñ òåì, ÷òî ìû ìîæåì ðàññìàòðèâàòü îäíè è òå æå îáúåêòû êàê ïîëèíîìû (àëãåáðà) è êàê ôóíêöèè (àíàëèç), âîçíèêàåò äâîéñòâåííîñòü â òåðìèíîëîãèè.  äàëüíåéøåì ìû áóäåì â îñíîâíîì ïðèäåðæèâàòüñÿ àëãåáðàè÷åñêîé òåðìèíîëîãèè, à â ñêîáêàõ ïðèâîäèòü ñîîòâåòñòâóþùèå ïîíÿòèÿ èç àíàëèçà. 47 Êðàòíûå êîðíè. Åñëè ξ ìû ãîâîðèì, ÷òî êîðåíü ξ f (x), òî ìû ìîæåì çàïèñàòü f (x) = (x − ξ)q(x). q(x) ñàìî áóäåò äåëèòüñÿ íà (x−ξ).  ýòîì ñëó÷àå ÿâëÿåòñÿ êîðíåì Îäíàêî ìîæåò ñëó÷èòüñÿ òàê, ÷òî ÷àñòíîå  êðàòíûé. Îïðåäåëåíèå 3.3.2. Êîðåíü ξ ïîëèíîìà f (x) èìååò êðàòíîñòü k , åñëè f (x) äåëèòñÿ íà (x−ξ)k , íî íå äåëèòñÿ íà (x−ξ)k+1 . Åñëè êðàòíîñòü êîðíÿ ðàâíà 1, îí íàçûâàåòñÿ ïðîñòûì. Çàäà÷à íàõîæäåíèÿ êðàòíûõ êîðíåé ïîëèíîìà ðåøàåòñÿ ñ èñïîëüçîâàíèåì ïðîèçâîäíûõ d dx : F [x] → F [x] ñëåäóþùèì îáðà+· · ·+an−1 x+an , åãî ïðîèçâîäíÿ îïðåäåëÿåòñÿ êàê ïîëèíîì îò ïîëèíîìîâ. Îïðåäåëèì îïåðàòîð äèôôåðåíöèðîâàíèÿ çîì. Äëÿ ïîëèíîìà ñòåïåíè (n − 1), p(x) = a0 x n èìåþùèé âèä d p(x) = a0 nxn−1 + a1 (n − 1)xn−2 + · · · + an−2 x + an−1 . dx Îïåðàöèþ äèôôåðåíöèðîâàíèÿ ìîæíî ïðèìåíÿòü íåîäíîêðàòíî.  ÷àñòíîñòè, ïðèìåíÿÿ ðàç îïåðàöèþ äèôôåðåíöèðîâàíèÿ ê ïîëèíîìó ñòåïåíè ñòåïåíè, ò. å. ÷èñëî: n, n ìû ïîëó÷èì ïîëèíîì íóëåâîé dn p(x) = n! a0 . dxn Ñîîòâåòñòâåííî, ïðîèçâîäíàÿ îò êîíñòàíòû ðàâíà íóëþ. Îïåðàöèÿ äèôôåðåíöèðîâàíèÿ óäîâëåòâîðÿåò cëåäóþùèì ñâîéñòâàì äëÿ âñåõ F [x] è p(x), g(x) ∈ α, β ∈ F : d d d (αp(x) + βg(x)) = α p(x) + β g(x) dx dx dx d d d (p(x)g(x)) = g(x) p(x) + p(x) g(x) dx dx dx ëèíåéíîñòü (3.14a) ïðàâèëî Ëåéáíèöà. (3.14b) Èñïîëüçóÿ (3.14b), ìû ìîæåì âûðàçèòü ïðîèçâîäíóþ îò ïîëèíîìà, âîçâåäåííîãî â öåëî÷èñëåííóþ ñòåïåíü: d k d p (x) = kpk−1 (x) p(x). dx dx Èñïîëüçóÿ ïîñëåäíèé ðåçóëüòàò ìû äîêàæåì ñëåäóþùóþ âàæíóþ òåîðåìó î ïîèñêå êðàòíûõ êîðíåé. Òåîðåìà 3.3.3. Åñëè ÷èñëî ξ ÿâëÿåòñÿ k-êðàòíûì êîðíåì ïîëèíîìà p(x), òî îíî áóäåò d (k − 1)-êðàòíûì êîðíåì ïðîèçâîäíîé dx p(x). Åñëè æå ÷èñëî ξ ÿâëÿåòñÿ ïðîñòûì êîðíåì, d ò. å. k = 1, òî îíî íå áóäåò êîðíåì ïðîèçâîäíîé dx p(x). Äîêàçàòåëüñòâî. Äèôôåðåíöèðóÿ Ïî óñëîâèþ, p(x) p(x) = (x − ξ)k φ(x), k ∈ N è ÍÎÄ (φ(x), (x − ξ)) = 1. ïîëó÷àåì   d d d p(x) = k(x − ξ)k−1 φ(x) + (x − ξ)k φ(x) = (x − ξ)k−1 kφ(x) + (x − ξ) φ(x) . dx dx dx (x − ξ), à âòîðîå íåò. Ïîýòîìó âñÿ (x − ξ). Ïîëó÷àåì, ÷òî ÷èñëî ξ ÿâëÿåòñÿ êîðíåì êðàòíîñòè (k − 1)  êâàäðàòíûõ ñêîáêàõ îäíî èç ñëàãàåìûõ äåëèòñÿ íà ñóììà òîæå íå äåëèòñÿ íà ïîëèíîìà d dx p(x), ÷òî è òðåáîâàëîñü äîêàçàòü. Ïðèâåäåííàÿ òåîðåìà èìååò îäíî âàæíîå ñëåäñòâèå, êîòîðîå èñïîëüçóåòñÿ ïðè íàõîæäåíèè êðàòíûõ êîðìåé ïîëèíîìîâ. 48 Ñëåäñòâèå 3.3.4. Åñëè ÷èñëà ξ1 , ξ2 , . . . , ξl  êîðíè ïîëèíîìà p(x) ñ êðàòíîñòÿìè k1 , k2 , . . . , kl , ïðè÷åì èíûõ êðàòíûõ êîðíåé ó ïîëèíîìà p(x) íåò, òî íàèáîëüøèé îáùèé äåëèòåëü ïîëèíîìà p(x) è åãî ïðîèçâîäíîé èìååò âèä   d ÍÎÄ p(x), p(x) = (x − ξ1 )k1 −1 (x − ξ2 )k2 −1 × · · · × (x − ξl )kl −1 . dx Òàêèì îáðàçîì, íàèáîëüøèé îáùèé äåëèòåëü ïîëèíîìà è åãî ïðîèçâîäíîé äåëèòñÿ òîëüêî íà ëèíåéíûå ìíîãî÷ëåíû, ñîîòâåòñòâóþùèå êðàòíûì êîðíÿì ïîëèíîìà, ïðè÷åì êðàòíîñòü ñîîòâåòñòâóþùèõ êîðíåé íà åäèíèöó ìåíüøå èõ êðàòíîñòè â èñõîäíîì ïîëèíîìå. 3.3.2 Îñíîâíàÿ òåîðåìà àëãåáðû Ìû óæå çàìåòèëè âûøå, ÷òî âîïðîñ ñóùåñòâîâàíèÿ èëè íå ñóùåñòâîâàíèÿ êîðíåé ïîëèíîìà çàâèñèò îò òîãî, â êàêîì ìíîæåñòâå ìû èõ èùåì. Òàê, ïîëèíîì ñ êîýôôèöèåíòàìè èç ïîëÿ Q ìîæåò íå èìåòü êîðíåé â Q, îäíàêî áóäåò èìåòü êîðíè â R èëè C. Àíàëîãè÷íî, ïîëèíîì R ìîæåò íå èìåòü êîðíåé â ìíîæåñòâå âåùåñòâåííûõ ÷èñåë. Ãîâîðÿ ìíîæåñòâà Q è R àëãåáðàè÷åñêè íåçàìêíóòû. ñ êîýôôèöèåíòàìè èç ôîðìàëüíî, Îïðåäåëåíèå 3.3.3. êàæäûé ýëåìåíò çàìêíóòûì L Ìíîæåñòâî L íàçûâàåòñÿ àëãåáðàè÷åñêèì çàìûêàíèåì ïîëÿ F åñëè F [x]. Ïîëå F íàçûâàåòñÿ àëãåáðàè÷åñêè ÿâëÿåòñÿ êîðíåì ïîëèíîìîâ èç åñëè îíî ñîâïàäàåò ñî ñâîèì àëãåáðàè÷åñêèì çàìûêàíèåì. àëãåáðàèC. ñàìèì C. Ýòîò Àëãåáðàè÷åñêèì çàìûêàíèåì ïîëÿ ðàöèîíàëüíûõ ÷èñåë ÿâëÿåòñÿ ìíîæåñòâî ÷åñêèõ ÷èñåë A ⊂ C, àëãåáðàè÷åñêîå çàìûêàíèå R  ýòî ìíîæåñòâî êîìïëåêñíûõ ÷èñåë Íàêîíåö, îêàçûâàåòñÿ, ÷òî àëãåáðàè÷åñêîå çàìûêàíèå ïîëÿ ðåóëüòàò ñîñòàâëÿåò îñíîâíóþ òåîðåìó àëãåáðû. C ñîâïàäàåò ñ Òåîðåìà 3.3.5. Âñÿêèé ïîëèíîì ñòåïåíè íå ìåíüøå 1 ñ êîýôôèöèåíòàìè èç C èìååò ïî ìåíüøåé ìåðå îäèí êîðåíü, â îáùåì ñëó÷àå ïðèíàäëåæàùèé C. Î÷åâèäíî, ÷òî ýòîò ðåçóëüòàò ðàâíûì îáðàçîì ìîæåò áûòü ïðèìåí¼í ê ïîëèíîìàì ñ êîýôôèöèåíòàìè èç ìíîæåñòâà ðàöèîíàëüíûõ è âåùåñòâåííûõ ÷èñåë, ò.ê. îíè ÿâëÿþòñÿ ïîäìíîæåñòâàìè C. Ìîæíî ðàñìàòðèâàòü òàêæå ïîëèíîìû ñ êîýôôèöèåíòàìè èç êîíå÷íûõ ïîëåé, îäíàêî â ýòîì ñëó÷àå çàäà÷à íàõîæäåíèÿ êîðíåé íå èìååò áîëüøîãî ïðèìåíåíèÿ. Îñíîâíàÿ òåîðåìà àëãåáðû îòíîñèòñÿ ê òåì ðåçóëüòàòàì, êîòîðûå íå ìîãóò áûòü äîêàçàíû èñêëþ÷èòåëüíî àëãåáðàè÷åñêèìè ìåòîäàìè, òðåáóþò èñïîëüçîâàíèÿ ðåçóëüòàòîâ èç àíàëèçà. Íèæå ìû ñõåìàòè÷íî ñôîðìóëèðóåì äâà äîêàçàòåëüñòâà îñíîâíîé òåîðåìû èñïîëüçóÿ ñëåäóþùèå ôàêòû èç àíàëèçà. Òåì, êòî èíòåðåñóåòñÿ èñòîðèåé è àëüòåðíàòèâíûìè âàðèàíòàìè äîêàçàòåëüñòâà îñíîâíîé òåîðåìû, ðåêîìåíäóåòñÿ ñòàòüÿ [6]. Óòâåðæäåíèå 3.3.6. Ðàöèîíàëüíàÿ ôóíêöèÿ p(z) ∈ C[z], ðàâíî êàê è åå àáñîëþòíîå çíà÷åíèå |p(z)|, ÿâëÿþòñÿ ðàâíîìåðíî íåïðåðûâíûìè íà C, ò. å. äëÿ ëþáîãî  > 0 ñóùåñòâóåò δ = δ() > 0 òàêîå, ÷òî äëÿ ëþáûõ äâóõ òî÷åê z1 , z2 ∈ C, óäîâëåòâîðÿþùèõ íåðàâåíñòâó |z1 − z2 | < δ , âûïîëíÿåòñÿ íåðàâåíñòâî |p(z1 ) − p(z2 )| <  (äëÿ àáñîëþòíîãî çíà÷åíèÿ âåðíî | |p(z1 )| − |p(z2 )| | ≤ |p(z1 ) − p(z2 )| Ñîñëàòüñÿ íà ãëàâó 2). Ýòîò ðåçóëüòàò îçíà÷àåò, ÷òî ïðè ìàëîì èçìåíåíèè àðãóìåíòà z ôóíêöèÿ p(z) òàêæå èçìåíÿåòñÿ íà íåáîëüøóþ âåëè÷èíó. Ôàêòè÷åñêè, äëÿ íàñ áóäåò âàæíî òî, ÷òî íåïðåðûâíàÿ ôóíêöèÿ íå ïðåòåðïåâàåò ñêà÷êîâ, ò. å. êîíå÷íûõ èçìåíåíèé ïðè áåñêîíå÷íî ìàëîì çíà÷åíèè àðãóìåíòà. Êðîìå òîãî, íåïðåðûâíîñòü ôóíêöèè ïîçâîëÿåò ïðèìåíÿòü òåîðåìó Âåéåðøòðàññà. 49 Òåîðåìà 3.3.7 (Âåéåðøòðàññ). Ôóíêöèÿ, íåïðåðûâíàÿ íà íåêîòîðîì çàìêíóòîì è îãðàíè÷åííîì ïîäìíîæåñòâå ïðîñòðàíñòâà Rk , îãðàíè÷åíà íà í¼ì è äîñòèãàåò ñâîèõ ìèíèìàëüíîãî è ìàêñèìàëüíîãî çíà÷åíèé. Çàìåòèì, ÷òî ìíîæåñòâî êîìïëåêñíûõ ÷èñåë C èçîìîðôíî ìíîæåñòâó R2 = R × R, ÷òî ïîçâîëÿåò ïðèìåíÿòü òåîðåìó Âåéåðøòðàññà ê ôóíêöèÿì êîìïëåêñíîãî àðãóìåíòà. Òåïåðü ìû ãîòîâû ñôîðìóëèðîâàòü äâå ñõåìû äîêàçàòåëüñòâà îñíîâíîé òåîðåìû. Ìû n≥1 áóäåì ðàññìàòðèâàòü ïîëèíîì ñòåïåíè ñ åäèíè÷íûì ñòàðøèì êîýôôèöèåíòîì âèäà p(z) = z n + a1 z n−1 + · · · + an−1 z + an . (3.15) Î÷åâèäíî, ÷òî ëþáîé ïîëèíîì ìîæåò áûòü ïðèâåäåí ê òàêîìó âèäó äåëåíèåì âñåõ êîýôôèöèåíòîâ íà a0 . Äîêàçàòåëüñòâî I. îêðóæíîñòü ðàäèóñà z äâèæåòñÿ âäîëü ïàðàìåòðèçîâàííîé êðèâîé γ , z = R(cos(φ) + ı sin(φ)), φ ∈ [0, 2π]. Ýòà êðèâàÿ ïðåäñòàâëÿåò cîáîé öåíòðîì â òî÷êå (0 + ı · 0), êîòîðàÿ âû÷åð÷èâàåòñÿ â íàïðàâëåíèè, Ïóñòü ïåðåìåííàÿ îïèñûâàåìîé óðàâíåíèåì R ñ ïðîòèâîïîëîæíîì äâèæåíèþ ÷àñîâîé ñòðåëêè. Òåïåðü èññëåäóåì âèä êðèâîé, îïèñûâàåìîé òî÷êîé γ äëÿ ðàçëè÷íûõ çíà÷åíèé R. p(z) ïðè äâèæåíèè Îáîçíà÷èì ýòó êðèâóþ êàê ΓR . z âäîëü êðèâîé Î÷åâèäíî, ÷òî ïðåäñòàâëÿòü ñîáîé çàìêíóòóþ êðèâóþ, ò.ê. íà÷àëüíàÿ è êîíå÷íàÿ òî÷êè γ ΓR áóäåò ñîâïàäàþò. n z R → ∞, ïîâåäåíèå (3.15) îïðåäåëÿåòñÿ ñòàðøèì ÷ëåíîì z n (âñïîìíèì, ÷òî lim|z|→∞ a1 zn−1 +···+a n−1 z+an ∞). Òàêèì îáðàçîì, ïðè äîñòàòî÷íî áîëüøèõ çíà÷åíèÿõ R îäèí îáîðîò òî÷êè z âîêðóã íà÷àëà êîîðäèíàò ñîîòâåòñòâóåò n îáîðîòàì òî÷êè p(z) (ñì. ðèñ. 3.1): Ïðè p(z) ≈ Rn (cos(nφ) + ı sin(nφ)), ΓR Çàìåòèì, ÷òî êðèâàÿ íå ïåðåñåêàåò íà÷àëà êîîðäèíàò, ò.ê. ïðè áîëüøèõ |p(z)| ≈ Rn . Ïðè èçìåíåíèè R êðèâàÿ íîñòè, ÷òî åñëè êðèâàÿ φ ∈ [0, 2π]. ΓR ΓR áóäåò R âûïîëíÿåòñÿ íåïðåðûâíî äåôîðìèðîâàòüñÿ. Ýòî çíà÷èò, â ÷àñò- áóäåò ñòÿãèâàòüñÿ, òî ïðè ýòîì îíà áóäåò çàìåòàòü âñå òî÷êè, ëåæàùèå âíóòðè îáëàñòè, î÷åð÷èâàåìîé êðèâîé. Ðàññìîòðèì òåïåðü, ÷òî ïðîèçîéäåò åñëè ðàäèóñ R óñòðåìèòñÿ ê íóëþ.  ýòîì ñëó÷àå âñå an áóäóò ñòðåìèòüñÿ ê íóëþ è êðèâàÿ ÷ëåíû ïîëèíîìà, çà èñêëþ÷åíèåì ñâîáîäíîãî ÷ëåíà ΓR an (êîòîðàÿ â îáùåì ñëó÷àå ìîæåò áûòü êîìR ìû âñåãäà ìîæåì äîñòè÷ü òîãî, ÷òî êðèâàÿ ΓR íå áóäåò îõâàòûâàòü áóäåò êîíöåíòðèðîâàòüñÿ âîêðóã òî÷êè ïëåêñíîé). Óìåíüøàÿ íà÷àëî êîîðäèíàò (ñì. ðèñ. 3.2). Î÷åâèäíî, ÷òî ïî ìåðå òîãî êàê î÷åíü ìàëûì, ïðè íåêîòîðîì âåòñòâóþùåå çíà÷åíèå z R R êðèâàÿ áóäåò óìåíüøàòüñÿ îò î÷åíü áîëüøèõ çíà÷åíèé ê ΓR äîëæíà ïðîéòè ÷åðåç íà÷àëî êîîðäèíàò. Ñîîò- áóäåò ÿâëÿòüñÿ êîðíåì ïîëèíîìà Äîêàçàòåëüñòâî II. p(z). Ïóñòü, êàê è ðàíüøå, ïîëèíîì p(z) èìååò âèä (3.15). Ðàññìîòðèì R: DR = {z ∈ C : |z| ≤ R, R > 0}. Ïî òåîðåìå Âåéåðøòðàññà, ñóùåñòâóåò òî÷êà ξ ∈ DR òàêàÿ, ÷òî ìîäóëü p(z) äîñòèãàåò â ýòîé òî÷êå ìèíèìóìà. Åñëè òî÷êà ξ ïðèíàäëåæèò ãðàíèöå DR , òî ìû áóäåì óâåëè÷èâàòü R äî òåõ ïîð, ïîêà ξ íå îêàæåòñÿ âíóòðè îáëàñòè. Áîëåå òîãî, ïîñêîëüêó ïðè óâåëè÷åíèè ìîäóëÿ z çíà÷åíèå |p(z)| ðàñòåò, ìû ìîæåì íàéòè òàêîå R, ÷òî áóäåò âûïîëíÿòüñÿ minz∈DR |p(z)| = minz∈C |p(z)|, ò. å. òî÷êà ξ áóäåò òî÷êîé ãëîáàëüíîãî ìèíèìóìà. Ïðåäïîëîæèì, ÷òî p(ξ) 6= 0, ò. å. ξ íå ÿâëÿåòñÿ êîðíåì p(z). Îïðåäåëèì íîâóþ ôóíêöèþ g(z) = p(z+ξ) p(ξ) . Ôóíêöèÿ |g(z)| èìååò ìèíèìóì â òî÷êå 0, ò. å., |g(0)| = 1 è |g(z)| ≥ 1 äëÿ êðóã ðàäèóñà 50 (a) R = 100 Ðèñ. 3.1: Ãðàôèê ôóíêöèè çíà÷åíèé (b) R = 10000 p(z) = z 5 +300z 4 −2z 3 +1 ïðè äâèæåíèè z âäîëü γ äëÿ ðàçëè÷íûõ R. z ∈ C. Çàïèøåì g(z) = 1 + ck z k + ck+1 z k+1 + · · · + cn z n , ãäå ci ∈ C, i = k, . . . , n. k Âûáèðàÿ α òàêèì, ÷òî α = −1/ck è ïðîâîäÿ â g(z) çàìåíó ïåðåìåííîé z = αζ ìû ïîëó÷àåì îêîí÷àòåëüíîå âûðàæåíèå äëÿ ôóíêöèè g : âñåõ g(ζ) = 1 − ζ k + dk+1 ζ k+1 + · · · + dn ζ n . Ïåðåïèøåì g(ζ) â âèäå g(ζ) = 1 − ζ k + b(ζ). Êîãäà ζ ñòðåìèòñÿ ê 0, èìååì |ζ k | = ∞. |ζ|→0 |b(ζ)| lim  ÷àñòíîñòè, ýòî çíà÷èò, ÷òî ìîæíî íàéòè òàêîå ïîëîæèòåëüíîå âåùåñòâåííîå ÷èñëî xk > |b(x)|. Äëÿ ζ=x x, ÷òî ìîæíî çàïèñàòü ñëåäóþùèå íåðàâåíñòâà (ññûëêà íà íåðàâåíñòâà äëÿ êîìïëåêñíûõ ÷èñåë): |g(x)| = |1 − xk + b(x)| ≤ |1 − xk | + |b(x)| = 1 − xk + |b(x)| < 1, ÷òî ïðîòèâîðå÷èò óñëîâèþ åñòü êîðåíü g(z) ≥ 1, ∀z ∈ C. Çàêëþ÷àåì, ÷òî âûïîëíÿåòñÿ p(z). 51 p(ξ) = 0, ò. å. ξ Ðèñ. 3.2: Êðèâàÿ ΓR 52 ïðè R = 0.1 Ëèòåðàòóðà [1] Å. À. Êàëèíèíà, À. Þ. Óòåøåâ [2] Ôàääååâ [3] Êóðîø Äîïîëíèòåëüíàÿ ëèòåðàòóðà [6] Â. Ì. Òèõîìèðîâ, Â. Â. Óñïåíñêèé, Äåñÿòü äîêàçàòåëüñòâ îñíîâíîé òåîðåìû àëãåáðû, Ìàòåì. ïðîñâ., ñåð. 3, âûï. 1, ÌÖÍÌÎ, Ì., 1997, 5070. 53