Е.Е. Тыртышников - Матричный анализ и линейная алгебра (1112313), страница 56
Текст из файла (страница 56)
Åäèíñòâåííîñòü ñ òî÷íîñòüþ äî ýêâèâàëåíòíîñòè èìååò ìåñòî è ïðè áîëååñëàáûõ ïðåäïîëîæåíèÿõ, ÷åì â äîêàçàííîé íàìè òåîðåìå åäèíñòâåííîñòè.  1970-õ ãîäàõÊðóñêàë äîêàçàë ñëåäóþùóþ òåîðåìó: ïóñòü ðàíãè ìàòðèö A, B , C ðàâíû rA , rB , rCè ïóñòü ëþáûå rA ñòîëáöîâ èç A, ëþáûå rB ñòîëáöîâ èç B è ëþáûå rC ñòîëáöîâ èçC ÿâëÿþòñÿ ëèíåéíî íåçàâèñèìûìè; åñëè rA + rB + rC ≥ 2r + 2, ãäå r îáùåå ÷èñëîñòîëáöîâ äëÿ A, B è C , òî òðèëèíåéíîå ðàçëîæåíèå (A, B, C) îïðåäåëåíî îäíîçíà÷íîñ òî÷íîñòüþ äî ýêâèâàëåíòíîñòè.
Âîçìîæíî êàêîå-òî îñëàáëåíèå è ýòèõ óñëîâèé.40.8Òåíçîðíûé ðàíã è óìíîæåíèå ìàòðèöÒðèëèíåéíûå ðàçëîæåíèÿ èìåþò ãëóáîêóþ ñâÿçü ñ òåîðèåé ñëîæíîñòè âû÷èñëåíèé. Êêîìïåòåíöèè äàííîé òåîðèè îòíîñèòñÿ, íàïðèìåð, âîïðîñ, èíòåðåñóþùèé êàæäîãî, êòîèìååò äåëî ñ ìàòðèöàìè: êàêîâà èñòèííàÿ ñëîæíîñòü óìíîæåíèÿ äâóõ n × n-ìàòðèö?Ýïèòåò ïîä÷åðêèâàåò, ÷òî íàñ èíòåðåñóåò ñëîæíîñòü (÷èñëî îïåðàöèé) ñàìîãî áûñòðîãîàëãîðèòìà.Îòâåò íà ýòîò âîïðîñ äî ñèõ ïîð íå ïîëó÷åí. Äëÿ áîëüøèíñòâà ëèö, êîãäà-òî çíàêîìèâøèõñÿ ñ ëèíåéíîé àëãåáðîé, â ïàìÿòè îñòàåòñÿ ïðàâèëî ñòðîêà íà ñòîëáåö, äàþùååO(n3 ) îïåðàöèé.
Îäíàêî, ìû ìîæåì óòâåðæäàòü, ÷òî èñòèííîå ÷èñëî îïåðàöèé íåïðåâûøàåò O(nlog2 7 ). Èìåííî ñòîëüêî îïåðàöèé äàåò àëãîðèòì Øòðàññåíà, êîòîðûé ìûîáñóæäàëè â ñàìîé ïåðâîé ëåêöèè íàøåãî êóðñà.Îòêóäà æå áåðåòñÿ îðèãèíàëüíûé ñïîñîá óìíîæåíèÿ 2×2-ìàòðèö, íà êîòîðîì òàì âñåîñíîâàíî? Òåïåðü, â çàêëþ÷èòåëüíîé ëåêöèè, ìû èìååì âîçìîæíîñòü ðàñêðûòü òàéíóàëãîðèòìà Øòðàññåíà.Èòàê, ïóñòüu1 u3 v 1 v 3w1 w3=.u2 u4 v 2 v 4w2 w4Ðàâåíñòâà, âûðàæàþùèå wk ÷åðåç ui è vj , ìîæíî, î÷åâèäíî, çàïèñàòü â òàêîé ôîðìå:w1 = u1 v1 + u3 v2 ,4 X4Xw2 = u2 v1 + u4 v2 ,⇔ wk =xijk ui vj , k = 1, 2, 3, 4.w3 = u1 v3 + u3 v4 ,i=1 j=1w4 = u2 v3 + u4 v4 .Âîçíèêøèé çäåñü òðåõìåðíûé ìàññèâ X = [xijk ] èìååò ðàçìåðû 4 × 4 × 4, åãî ýëåìåíòûÅ.
Å. Òûðòûøíèêîâ269xijk ðàâíû 0 ëèáî 1. Âîò ñå÷åíèÿ X ïî îñè k :" 1 0 0 0#" 0 0 0 0#Xk=1 =000010000000100, Xk=2 =001000000"0, Xk=3 =000000010000010"0#, Xk=4 =000000010000001#. äàííîì ñëó÷àå ÿñíî, ÷òî òåíçîðíûé ðàíã ìàññèâà X íå áîëüøå 8 (äîêàæèòå!).Ïóñòü îí ðàâåí r. Òîãäà èìååòñÿ òðèëèíåéíîå ðàçëîæåíèå!!rr44XXXXxijk =ais bjs cks ⇒ wk =cksais uibjs vj , k = 1, 2, 3, 4.s=1s=1i=1j=1Êàê âèäèì, òðèëèíåéíîå ðàçëîæåíèå ðàíãà r ïîðîæäàåò ñïåöèàëüíûé àëãîðèòì âû÷èñëåíèÿ âåëè÷èí wk , â êîòîðîì âñåãî r àêòèâíûõ óìíîæåíèé òàê íàçûâàþòñÿ óìíîæåíèÿ, â êîòîðûõ îáà ìíîæèòåëÿ ñóùåñòâåííî çàâèñÿò îò âõîäíûõ ïåðåìåííûõ uiè vj (÷èñëà ais , bjs , cks íå çàâèñÿò îò ui , vj ; èõ íàçûâàþò êîíñòàíòàìè àëãîðèòìà óìíîæåíèå íà êîíñòàíòó íå ñ÷èòàåòñÿ àêòèâíûì óìíîæåíèåì).×òîáû ïîëó÷èòü îòêðûòèå Øòðàññåíà, äîñòàòî÷íî ðåøèòü çàäà÷ó î âû÷èñëåíèè òåíçîðíîãî ðàíãà äàííîãî êîíêðåòíîãî ìàññèâà X . Ìîæíî îãðàíè÷èòüñÿ è áîëåå ñêðîìíîéçàäà÷åé: íàéòè êàêîå-íèáóäü òðèëèíåéíîå ðàçëîæåíèå ðàíãà 7 (ðàçëîæåíèå ðàíãà 8 ñâÿçàíî ñ ïðàâèëîì ñòðîêà íà ñòîëáåö).
Íåñìîòðÿ íà îòñóòñòâèå êîíå÷íûõ àëãîðèòìîâòî÷íîãî âû÷èñëåíèÿ òåíçîðíîãî ðàíãà, ðàçðàáîòêà àëãîðèòìîâ òðèëèíåéíîé àïïðîêñèìàöèè çàäàííîãî ðàíãà ÿâëÿåòñÿ ïîñèëüíîé çàäà÷åé.Ýôôåêòèâíûå ìåòîäû äëÿ äàííîé çàäà÷è ÿâëÿþòñÿ îäíîé èç êðóïíûõ èññëåäîâàòåëüñêèõ ïðîáëåì. Îäíàêî, â îòäåëüíûõ ñëó÷àÿõ ìîæíî äîáèòüñÿ íóæíîãî ðåçóëüòàòàè ñ ïîìîùüþ êàêèõ-ëèáî ýâðèñòè÷åñêèõ è, âîçìîæíî, ìåäëåííûõ âû÷èñëåíèé: ÷òîáûïîñòðîèòü áûñòðûé àëãîðèòì óìíîæåíèÿ ìàòðèö, ìû âïîëíå ãîòîâû ïîòðàòèòü î÷åíüìíîãî âðåìåíè íà ïîèñê òåíçîðíîãî ðàíãà ìàññèâà X . Âîò êàê âûãëÿäèò òðèëèíåéíîåðàçëîæåíèå X = (A, B, C) ðàíãà 7 â íàøåì ñëó÷àå: 1" 1 1 0 −1 0 1 0 #" 1 0 1 0 1 −1 0 #A=001101000001010100"C=100101−1011−1, B=00111100−10100010001000−100001−1100001010101,#.Äàííîå ðàçëîæåíèå íàéäåíî ñ ïîìîùüþ êîìïüþòåðà. Òàêèì îáðàçîì, êîìïüþòåðìîæåò èñïîëüçîâàòüñÿ íå òîëüêî êàê èíñòðóìåíò ðåøåíèÿ âû÷èñëèòåëüíûõ çàäà÷, íîòàêæå è êàê èíñòðóìåíò ïîëó÷åíèÿ àëãîðèòìîâ äëÿ ðåøåíèÿ ýòèõ çàäà÷.1 Óñëîâèÿ äîêàçàííîé íàìè òåîðåìû åäèíñòâåííîñòè â äàííîì ñëó÷àå íå âûïîëíåíû.
Ïîýòîìó ìîæíîíàéòè è äðóãîå, íåýêâèâàëåíòíîå äàííîìó, ðàçëîæåíèå.270Ëåêöèÿ 40Äîïîëíåíèå ê ëåêöèè 141.1Ïàðàëëåëüíàÿ ôîðìà àëãîðèòìàÀðèôìåòè÷åñêàÿ ñëîæíîñòü àëãîðèòìà âåùü, êîíå÷íî, âàæíàÿ â ëþáîì ñëó÷àå. Íîñ ðàçâèòèåì êîìïüþòåðîâ âðåìÿ ñòàíîâèòñÿ âñå ìåíåå ïðîïîðöèîíàëüíûì îáùåìó÷èñëó îïåðàöèé. Äåëî â òîì, ÷òî ìíîãèå îïåðàöèè âûïîëíÿþòñÿ ïàðàëëåëüíî (îäíîâðåìåííî).×òîáû ïîíÿòü õîòü ÷òî-òî, íóæíî è òåïåðü îòáðîñèòü î÷åíü ìíîãî äåòàëåé.
Ðàññìîòðèì ìîäåëü áåñêîíå÷íîãî ïàðàëëåëèçìà: èìååòñÿ áåñêîíå÷íî ìíîãî ïðîöåññîðîâ ñíåîãðàíè÷åííîé ïàìÿòüþ, êàæäûé ìîæåò â ëþáóþ åäèíèöó âðåìåíè âûïîëíèòü îäíóàðèôìåòè÷åñêóþ îïåðàöèþ è ìãíîâåííî îáìåíèâàåòñÿ èíôîðìàöèåé ñ ëþáûì äðóãèìïðîöåññîðîì.×òîáû ðåàëèçîâàòü àëãîðèòì íà òàêîì èäåàëèçèðîâàííîì êîìïüþòåðå, äîñòàòî÷íîçàïèñàòü åãî â âèäå ïîñëåäîâàòåëüíîñòè ÿðóñîâ íàáîðîâ èíôîðìàöèîííî íåñâÿçàííûõîïåðàöèé (èõ ìîæíî âûïîëíÿòü ïàðàëëåëüíî). Òàêîå ïðåäñòàâëåíèå àëãîðèòìà íàçûâàåòñÿ åãî ïàðàëëåëüíîé ôîðìîé, ÷èñëî ÿðóñîâ íàçûâàåòñÿ âûñîòîé, à ìàêñèìàëüíîå ÷èñëîîïåðàöèé â îäíîì ÿðóñå øèðèíîé ïàðàëëåëüíîé ôîðìû.Äëÿ ëþáîãî àëãîðèòìà ñóùåñòâóåò, î÷åâèäíî, ïàðàëëåëüíàÿ ôîðìà ñ ìèíèìàëüíûì÷èñëîì ÿðóñîâ.
Ýòî ìèíèìàëüíîå ÷èñëî ÿðóñîâ íàçûâàåòñÿ âûñîòîé àëãîðèòìà.  ìîäåëè áåñêîíå÷íîãî ïàðàëëåëèçìà ìèíèìàëüíîå âðåìÿ ðåàëèçàöèè àëãîðèòìà ïðîïîðöèîíàëüíî åãî âûñîòå.41.2Ñõåìà ñäâàèâàíèÿ è ïàðàëëåëüíîå óìíîæåíèå ìàòðèöÂûñîòà êëàññè÷åñêîãî àëãîðèòìà óìíîæåíèÿ ìàòðèö èìååò âèä O (n). Äîêàæèòå!Ëåãêî ïîëó÷èòü è àëãîðèòì âûñîòû O (log2 n). Äëÿ ýòîãî äîñòàòî÷íî ïîñòðîèòü àëãîðèòì ñëîæåíèÿ n ÷èñåë, èìåþùèé âûñîòó O (log2 n). Òàêîé àëãîðèòì íàçûâàåòñÿ ñõåìîéñäâàèâàíèÿ: íóæíî ðàçáèòü ÷èñëà íà ïàðû, íàéòè ñóììû äëÿ êàæäîé ïàðû, çàòåì ðàçáèòü ðåçóëüòàòû íà ïàðû, íàéòè ñóììû, è òàê äàëåå.41.3Ìàòðèöû è ðåêóððåíòíûå âû÷èñëåíèÿÐàññìîòðèì ïîñëåäîâàòåëüíîñòü âåëè÷èí x−1 , x0 , x1 , . .
. , â êîòîðîé x−1 , x0 çàäàíû, àîñòàëüíûå âåëè÷èíû âû÷èñëÿþòñÿ ðåêóððåíòíî:xk = ak xk−1 + bk xk−2 ,k = 1, 2, . . . , n.(∗)Êîýôôèöèåíòû ak , bk ñ÷èòàþòñÿ çàäàííûìè. ×òîáû âû÷èñëèòü xn , â ñèëó (∗) òðåáóåòñÿ âûïîëíèòü O(n) àðèôìåòè÷åñêèõ îïåðàöèé. ×èñëî ïàðàëëåëüíûõ øàãîâ òàêæå271272Ëåêöèÿ 41O(n). Âîçíèêàåò âïå÷àòëåíèå, ÷òî àëãîðèòìïîëó÷èòü íåëüçÿ.Íî ýòî âïå÷àòëåíèå îáìàí÷èâî. Çàïèøåì xkak=1xk−1ñ ìåíüøåé âûñîòîé ïàðàëëåëüíîé ôîðìûñîîòíîøåíèÿ (∗) â ìàòðè÷íîé ôîðìå:bkxk−1,0xk−2èëè,zk =xkxk−1,zk = Ak zk−1 ,xk−1zk−1 =,xk−2Ak =ak b k1 0.Îòñþäàzn = Az0 ,A = An (An−1 (· · · (A3 (A2 A1 )) · · · ).×òîáû îïðåäåëèòü ïðîèçâåäåíèå ìàòðèö An An−1 · · · A1 , íóæíî ñâåñòè åãî ê âû÷èñëåíèþ ïðîèçâåäåíèé äâóõ ìàòðèö.
Ýòî äåëàåòñÿ ðàññòàíîâêîé ñêîáîê. Èñïîëüçóÿ àññîöèàòèâíîñòü îïåðàöèè óìíîæåíèÿ ìàòðèö, ìîæíî äîêàçàòü, ÷òî ðåçóëüòàò íå áóäåòçàâèñèòü îò ïîðÿäêà ðàññòàíîâêè ñêîáîê; ïîýòîìó ìîæíî ïèñàòü áåç ñêîáîê:A = An An−1 · · · A1 .×òîáû íàéòè zn (à çíà÷èò, è xn ), ñíà÷àëà âû÷èñëèì ìàòðèöó A.
Äëÿ ýòîãî ìîæíîèñïîëüçîâàòü òó æå ñõåìó ñäâàèâàíèÿ: íàõîäèì ïðîèçâåäåíèÿAn An−1 , An−2 An−3 , . . . , A2 A1 ,çàòåì ïîïàðíûå ïðîèçâåäåíèÿ ïîëó÷åííûõ ðåçóëüòàòîâ, è òàê äàëåå. Ïîòðåáóåòñÿ âñåãîëèøü O(log2 n) ïàðàëëåëüíûõ øàãîâ!41.4Ìîäåëè è ðåàëüíîñòü ìîäåëè áåñêîíå÷íîãî ïàðàëëåëèçìà ìû îòáðàñûâàåì, óâû, ñëèøêîì ìíîãî äåòàëåé,êîòîðûå ñëåäóåò ó÷èòûâàòü. ß äóìàþ, ìîæíî ïî÷óâñòâîâàòü ïðîáëåìû ïàðàëëåëüíûõâû÷èñëåíèé, ðàçìûøëÿÿ íàä ñëåäóþùåé çàäà÷åé-øóòêîé: Îäèí çåìëåêîï âûêàïûâàåòÿìó ãëóáèíîé 1 ìåòð çà 1 ÷àñ.
Çà êàêîå âðåìÿ ýòó ÿìó âûêîïàþò 100 çåìëåêîïîâ? ×òîáû âûïîëíÿòü êàêóþ-òî ðàáîòó ïàðàëëåëüíî, íåîáõîäèìî òàêóþ ðàáîòó èìåòü. ñóùåñòâóþùèõ àëãîðèòìàõ ðàáîòû äëÿ ïàðàëëåëüíîãî (îäíîâðåìåííîãî) èñïîëíåíèÿìîæåò áûòü íåäîñòàòî÷íî. Îïåðèðóÿ íàä îáùèìè äàííûìè, ïðîöåññîðû ìîãóò ìåøàòüäðóã äðóãó. Êàê ó÷åñòü âñå ýòî â áîëåå àäåêâàòíûõ è âñå æå ïîääàþùèõñÿ àíàëèçóìîäåëÿõ ýòî òðóäíûé âîïðîñ.Äîïîëíåíèå ê ëåêöèè 242.1Êîíå÷íûå ãðóïïûÃðóïïà íàçûâàåòñÿ êîíå÷íîé, åñëè â íåé èìååòñÿ êîíå÷íîå ÷èñëî ýëåìåíòîâ.  ýòîìñëó÷àå ÷èñëî ýëåìåíòîâ íàçûâàåòñÿ ïîðÿäêîì ãðóïïû.Òåîðåìà Ëàãðàíæà.
 ëþáîé êîíå÷íîé ãðóïïå ïîðÿäîê ëþáîé ïîäãðóïïû ÿâëÿåòñÿäåëèòåëåì ïîðÿäêà ãðóïïû.Äîêàçàòåëüñòâî. Ïóñòü H = {a1 , . . . , am } ïîäãðóïïà ãðóïïû G. Âîçüìåì ýëåìåíòa ∈ G\H è ðàññìîòðèì ìíîæåñòâîaH = {aa1 , . . . , aam }.Îíî ñîäåðæèò m ðàçëè÷íûõ ýëåìåíòîâ: åñëè aai = aaj , òî ai = aj . Êðîìå òîãî, aH ∩H = ∅: åñëè ai = aaj , òî a ∈ H .Åñëè H ∪ aH = G, òî âñå äîêàçàíî. Åñëè íåò, òî ñóùåñòâóåò b ∈ G\(H ∪ aH). ÌíîæåñòâîbH = {ba1 , . . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
