Е.Е. Тыртышников - Матричный анализ и линейная алгебра (1112313), страница 5
Текст из файла (страница 5)
. . + a1n xn ,...+ . . . + amn xn ,5x1=b11 z1xn= bn1 z1+ . . . + b1k zk ,...+ . . . + bnk zk .6Ëåêöèÿ 1ßñíî, ÷òî y1 , . . . , ym âûðàæàþòñÿ ÷åðåç z1 , . . . , zk àíàëîãè÷íûì îáðàçîì. Ìàòðèöó èçïîñòîÿííûõ êîýôôèöèåíòîâ ýòîé çàâèñèìîñòè îáîçíà÷èì ÷åðåç C . Òîãäàx = Bz è y = Cz.y = Ax,×òîáû ïîëó÷èòü êîýôôèöèåíòû ìàòðèöû C , íóæíî ïîäñòàâèòü âûðàæåíèÿ äëÿx1 , . . . , xn ÷åðåç z1 , . . .
, zk â ôîðìóëû, âûðàæàþùèå y1 , . . . , ym ÷åðåç x1 , . . . , xn , èñîáðàòü êîýôôèöèåíòû ïðè âåëè÷èíàõ z1 , . . . , zk . Ïîëó÷èòñÿ âîò ÷òî:nXC = [cij ], ãäå cij =ail blj .(∗)l=1Îïðåäåëåíèå. Ìàòðèöà C âèäà (∗) íàçûâàåòñÿ ïðîèçâåäåíèåì ìàòðèö A è B è îáîçíà÷àåòñÿ C = AB .Ñëåäñòâèå. y = A(Bz) = (AB)z .×àñòî ãîâîðÿò, ÷òî ìàòðèöû óìíîæàþòñÿ ïî ïðàâèëó ñòðîêà íà ñòîëáåö. ×èñëîñòîëáöîâ â ïåðâîì ñîìíîæèòåëå îáÿçàíî, êîíå÷íî, ñîâïàäàòü ñ ÷èñëîì ñòðîê âî âòîðîì.Åñëè ìû ïèøåì C = AB , òî àâòîìàòè÷åñêè èìååì â âèäó, ÷òî ìàòðèöû A è B íå ñîâñåìóæ ïðîèçâîëüíûå.1.3Àññîöèàòèâíîñòü óìíîæåíèÿ ìàòðèöÒåîðåìà. (AB)C = A(BC).Äîêàçàòåëüñòâî.
Ïóñòü A m × n, B n × k , C k × l. Òîãäà{(AB)C}ij =kX{AB}ip cpj =p=1p=1=nXaiqq=11.4kX!aiq bqpcpjq=1!bqp cpj= {A(BC)}ij .p=1Íåêîììóòàòèâíîñòü óìíîæåíèÿ ìàòðèö îáùåì ñëó÷àå AB 6= BA äàæå äëÿ0 10 00 01 01.5knXXêâàäðàòíûõ ìàòðèö. Íàïðèìåð, 0 01 0=,1 00 0 0 10 0=.0 00 1Ñëîæåíèå ìàòðèö è óìíîæåíèå íà ÷èñëîÌàòðèöà C = [cij ] íàçûâàåòñÿ ñóììîé ìàòðèö A = [aij ] è B = [bij ], åñëècij = aij + bijäëÿ âñåõ i, j.Ìàòðèöû A, B è C = A + B îäèíàêîâûõ ðàçìåðîâ.
Äëÿ îïåðàöèè ñëîæåíèÿ ìàòðèöâûïîëíÿþòñÿ ñðàçó äâà ïðèÿòíûõ ñâîéñòâà:A + (B + C) = (A + B) + C(àññîöèàòèâíîñòü),Å. Å. Òûðòûøíèêîâ7A + B = B + A (êîììóòàòèâíîñòü).Ïîëåçíî ââåñòè òàêæå îïåðàöèþ óìíîæåíèÿ ìàòðèöû íà ÷èñëî. Åñëè α ÷èñëî, òîìàòðèöà C = αA îïðåäåëÿåòñÿ êàê ìàòðèöà òåõ æå ðàçìåðîâ ñ ýëåìåíòàìè cij = αaij .1.6Óìíîæåíèå áëî÷íûõ ìàòðèöÏðåäïîëîæèì, ÷òî ìàòðèöûA11A = ...Ap1A è B ñîñòàâëåíû èç áëîêîâ. . . A1qB11... ...
,B = .... . . ApqBq1Aij è Bij :. . . B1r... ... ,. . . Bqrãäå Aij mi × nj , Bij ni × kj . Òîãäà ïðîèçâåäåíèå C = AB ñóùåñòâóåò è åãî ìîæíîâû÷èñëÿòü, èñïîëüçóÿ îïåðàöèè óìíîæåíèÿ è ñëîæåíèÿ ìàòðèö-áëîêîâ:qC11 . . . C1rXC = . . . . . . . . . , ãäå Cij =Ail Blj mi × kj .l=1Cp1 .
. . CprÄîêàæèòå!Ìîæíî ñêàçàòü, ÷òî áëî÷íûå ìàòðèöû óìíîæàþòñÿ ïî ïðàâèëó áëî÷íàÿ ñòðîêà íàáëî÷íûé ñòîëáåö. Ìû î÷åíü ñêîðî óâèäèì, êàêóþ ïîëüçó ìîæåò äàòü áëî÷íîå óìíîæåíèå.1.7Âû÷èñëèòåëüíûé àñïåêò óìíîæåíèÿ ìàòðèöÏóñòü çàäàíû n×n-ìàòðèöû A è B è òðåáóåòñÿ âû÷èñëèòü èõ ïðîèçâåäåíèå C = AB . Âîòêëàññè÷åñêèé àëãîðèòì (ïðîãðàììà íà íåêîì ïîäîáèè àëãîðèòìè÷åñêîãî ÿçûêà Ôîðòðàí):DO i = 1, nDO j = 1, nDO k = 1, ncij = cij + aik bkjEND DOEND DOEND DO.Êîíå÷íî, ïðåäâàðèòåëüíî ñëåäóåò çàíóëèòü ýëåìåíòû cij .ÄÎÏÎËÍÈÒÅËÜÍÀß ×ÀÑÒÜ1.8Õîðîøà ëè ïðîãðàììà?Îòâåòèòü íà ýòîò âîïðîñ íå î÷åíü ïðîñòî. Ïðåæäå âñåãî, íóæåí êàêîé-òî êðèòåðèé ïóñòü ýòî áóäåò âðåìÿ èñïîëíåíèÿ ïðîãðàììû. Íî âðåìÿ çàâèñèò íå òîëüêî îò òèïàêîìïüþòåðà.
 ñòðîãîì ñìûñëå, îíî ïðèâÿçàíî ê îòäåëüíî âçÿòîìó êîìïüþòåðó è çàâèñèò îò åãî ñîñòîÿíèÿ íà äàííûé ìîìåíò, îò îïåðàöèîííîé ñèñòåìû è, êîíå÷íî, îòîñîáåííîñòåé òðàíñëÿòîðà.8Ëåêöèÿ 1×òîáû ÷òî-òî çäåñü ïîíÿòü, íóæíî îòáðîñèòü î÷åíü ìíîãî äåòàëåé è îñòàâèòü íå÷òîãëàâíîå. Åñëè âñå îïåðàöèè âûïîëíÿþòñÿ ïîñëåäîâàòåëüíî, òî âðåìÿ ðàáîòû ìîæíîñ÷èòàòü ïðîïîðöèîíàëüíûì ÷èñëó îïåðàöèé. Ìû ïîéäåì äàëüøå è áóäåì ïîäñ÷èòûâàòü ëèøü àðèôìåòè÷åñêèå îïåðàöèè. Îáùåå èõ ÷èñëî áóäåì íàçûâàòü àðèôìåòè÷åñêîéñëîæíîñòüþ àëãîðèòìà.Ëåãêî íàéòè, ÷òî àðèôìåòè÷åñêàÿ ñëîæíîñòü êëàññè÷åñêîãî àëãîðèòìà óìíîæåíèÿìàòðèö ðàâíà 2n3 (n3 óìíîæåíèé è n3 ñëîæåíèé). Íî õîðîøî ëè ýòî? Óâåðåíû ëè ìû âòîì, ÷òî ýòî íàèëó÷øèé àëãîðèòì?Ñàìî ïîíÿòèå íàèëó÷øèé ïðåäïîëàãàåò íàëè÷èå íåêîãî ìíîæåñòâà âîçìîæíûõàëãîðèòìîâ.
Áóäåì ïîëàãàòü, ÷òî àëãîðèòì ýòî ïîñëåäîâàòåëüíîñòü ýëåìåíòàðíûõîïåðàöèé èç êîíå÷íîãî ôèêñèðîâàííîãî íàáîðà ýëåìåíòàðíûõ îïåðàöèé. Äëÿ îïðåäåëåííîñòè, ïóñòü ýòî áóäóò ÷åòûðå àðèôìåòè÷åñêèõ äåéñòâèÿ.Èòàê, ìàòåìàòè÷åñêàÿ çàäà÷à ïîñòàâëåíà. Åùå â íåäàâíåì ïðîøëîì ìíîãèì êàçàëîñü, ÷òî êëàññè÷åñêèé àëãîðèòì ñàìûé ëó÷øèé. Òåïåðü óæå ÿñíî, ÷òî ýòî íå òàê.1.9Ìåòîä ÂèíîãðàäàÏîïðîáóéòå-êà ïåðåìíîæèòü ìàòðèöû êàê-ëèáî èíà÷å íå ïî êëàññè÷åñêîìó àëãîðèòìó.
Âåðîÿòíî, âïåðâûå ýòî ñäåëàë Âèíîãðàä (â íà÷àëå 60-õ). Îí äîãàäàëñÿ èñïîëüçîâàòüñëåäóþùåå òîæäåñòâî:2mXk=1aik bkj =mX(ai 2k−1 + b2k j )(b2k−1 j + ai 2k ) −k=1mXai 2k−1 ai 2k −k=1mXb2k j b2k−1 j .k=1Ïóñòü n = 2m. ßñíî, ÷òî âòîðóþ è òðåòüþ ñóììû äëÿ âñåõ 1 ≤ i, j ≤ n ìîæíî íàéòè,çàòðàòèâ 2nm = n2 óìíîæåíèé è 2nm = n2 ñëîæåíèé.
Äëÿ ïåðâîé ñóììû ïîòðåáóåòñÿn2 m = 12 n3 óìíîæåíèé è 3n2 m = 32 n3 ñëîæåíèé. èòîãå ïî-ïðåæíåìó, 2n3 îïåðàöèé (áåç ó÷åòà ïîðÿäêà n2 n3 îïåðàöèé), íî òåïåðü 12 n3 óìíîæåíèé è 32 n3 ñëîæåíèé! Ïîñêîëüêó óìíîæåíèå îïåðàöèÿ áîëåå ñëîæíàÿ,÷åì ñëîæåíèå, ìåòîä Âèíîãðàäà ìîæåò ïðåäñòàâëÿòü ïðàêòè÷åñêèé èíòåðåñ.1.10Ìåòîä Øòðàññåíà 1965 ãîäó Øòðàññåí íàøåë ñïîñîá óìíîæåíèÿ 2 × 2-ìàòðèö ñ ïîìîùüþ âñåãî ëèøü7-ìè óìíîæåíèé (â êëàññè÷åñêîì ìåòîäå 8 óìíîæåíèé). Òî, ÷òî ïðèäóìàë Øòðàññåí,ïîëó÷àåòñÿ ïîñðåäñòâîì âû÷èñëåíèÿ òåíçîðíîãî ðàíãà ìíîãîìåðíûõ ìàòðèö. Îá ýòîììû ïîãîâîðèì â çàêëþ÷èòåëüíîé ëåêöèè êóðñà. À ïîêà äàâàéòå ïîñìîòðèì íà èçîáðåòåíèå Øòðàññåíà áåç êîììåíòàðèåâ: 1α1 = (a11 + a22 )(b11 + b22 ),α2 = (a21 + a22 )b11 ,α3 = a11 (b12 − b22 ),α4 = a22 (b21 − b11 ),α5 = (a11 + a12 )b22 ,α6 = (a21 − a11 )(b11 + b12 ),c11 = α1 + α4 − α5 + α7 ,c12 = α3 + α5 ,c21 = α2 + α4 ,c22 = α1 + α3 − α2 + α6 .α7 = (a12 − a22 )(b21 + b22 ),1 Ñì.
çàäà÷ó 5.4.21 èç Çàäà÷íèêà ïî ëèíåéíîé àëãåáðå Õ.Ä.Èêðàìîâà.Å. Å. Òûðòûøíèêîâ9Òîëüêî î÷åíü ëåíèâûé ÷åëîâåê íå ñìîæåò ïðîâåðèòü, ÷òî äâå ìàòðèöû ïîðÿäêà 2 óìíîæàþòñÿ ïðàâèëüíî.1.11Ðåêóðñèÿ äëÿ n × n-ìàòðèöÎò ìåòîäà óìíîæåíèÿ 2×2-ìàòðèö ñ 7-þ óìíîæåíèÿìè äîâîëüíî ëåãêî ïåðåéòè ê ìåòîäóóìíîæåíèÿ n × n-ìàòðèö, òðåáóþùåìó íå áîëåå 7 nlog2 7 îïåðàöèé. Ïîñêîëüêó7nlog2 7→ 0 ïðè n → ∞,n3ìåòîä Øòðàññåíà àñèìïòîòè÷åñêè ëó÷øå êëàññè÷åñêîãî ìåòîäà.Ïðåäïîëîæèì, ÷òî n = 2L è áóäåì ðàññìàòðèâàòü A è B êàê áëî÷íûå 2 × 2-ìàòðèöû:n nA11 A12B11 B12A=, B=,Aij , Bij × .A21 A22B21 B22 ,22Çàìå÷àòåëüíî, ÷òî â øòðàññåíîâñêîì ìåòîäå óìíîæåíèÿ 2 × 2-ìàòðèö êîììóòàòèâíîñòüíå èñïîëüçóåòñÿ.
Ïîýòîìó ìåòîä ãîäèòñÿ è äëÿ óìíîæåíèÿ áëî÷íûõ 2 × 2-ìàòðèö!Èòàê, çàäà÷à ðàçìåðà n ñâîäèòñÿ ê 7-ìè àíàëîãè÷íûì çàäà÷àì ðàçìåðà n2 . Äëÿ ôîðìèðîâàíèÿ ýòèõ 7-ìè çàäà÷ è äëÿ ïîëó÷åíèÿ îêîí÷àòåëüíîãî ðåçóëüòàòà ïîñëå ðåøåíèÿýòèõ 7-ìè çàäà÷ òðåáóåòñÿ 18 ðàç ñëîæèòü áëîêè ïîðÿäêà n2 ."Ðàñêðóòèâ"óêàçàííóþ ðåêóðñèþ äî êîíöà, ïîëó÷èì7log2 n = nlog2 7óìíîæåíèé íà ïîñëåäíåì ýòàïå. Îáùåå ÷èñëî ñëîæåíèé íà âñåõ ýòàïàõ ñîñòàâèò18LXk=1k−17 n 22k18 2=n47 L−47−141≤ 6 · 7L = 6 nlog2 7(íóæíî ó÷åñòü, ÷òî 4L = n2 è 7L = nlog2 7 ).Ïðè ïðàêòè÷åñêîì ïðèìåíåíèè ðåêóðñèþ íå îáÿçàòåëüíî ðàñêðó÷èâàòü äî êîíöà.Ýòî âðåäíî: 7 nlog2 7 > 2n3 äàæå ïðè n = 512. Íî ïðè n = 1 024 íåðàâåíñòâî ìåíÿåòñÿ âïîëüçó Øòðàññåíà.Ê íàñòîÿùåìó âðåìåíè ïðèäóìàíû è áîëåå áûñòðûå (àñèìïòîòè÷åñêè) ìåòîäû, ÷åììåòîä Øòðàññåíà. Óæå ñóùåñòâóþò ìåòîäû ñ ÷èñëîì îïåðàöèé O (nα ), ãäå α < 2.42.Íèêòî íå çíàåò, êàêîâ ìèíèìàëüíûé ïîêàçàòåëü â òàêèõ îöåíêàõ.
ßñíî ëèøü, ÷òî α ≥ 2.10Ëåêöèÿ 1Ëåêöèÿ 22.1Ìíîæåñòâà è ýëåìåíòûÏîíÿòèå ìíîæåñòâà ââîäèòñÿ äëÿ îáîçíà÷åíèÿ ñîâîêóïíîñòè ýëåìåíòîâ, îáúåäèíåííûõ êàêèì-òî îáùèì ïðèçíàêîì. Ñ÷èòàåòñÿ, ÷òî îíî îòíîñèòñÿ ê ïåðâè÷íûì ïîíÿòèÿì,êîòîðûì íå äàåòñÿ ôîðìàëüíîãî îïðåäåëåíèÿ.Çàïèñü a ∈ M îçíà÷àåò, ÷òî ýëåìåíò a ïðèíàäëåæèò ìíîæåñòâó M . Çàïèñü X ⊂ Yîçíà÷àåò, ÷òî êàæäûé ýëåìåíò ìíîæåñòâà X ïðèíàäëåæèò ìíîæåñòâó Y . Ïðè ýòîì Xíàçûâàåòñÿ ïîäìíîæåñòâîì äëÿ Y .
Îñîáî âûäåëÿåòñÿ ìíîæåñòâî, â êîòîðîì íåò íèîäíîãî ýëåìåíòà. Îíî íàçûâàåòñÿ ïóñòûì è îáîçíà÷àåòñÿ ñèìâîëîì ∅. Ïî îïðåäåëåíèþ,∅ ⊂ M ∀ M.Ïðè îïèñàíèè ìíîæåñòâ èíîãäà âîçíèêàþò ëîãè÷åñêèå ïðîòèâîðå÷èÿ. Íàïðèìåð,ðàññìîòðèì ìíîæåñòâî M , ñîñòîÿùåå èç îäíîãî ÷èñëà, êîòîðîå îïðåäåëÿåòñÿ êàê íàèìåíüøåå öåëîå ÷èñëî, êîòîðîå íåëüçÿ îïðåäåëèòü ïðè ïîìîùè ôðàçû, èìåþùåé ìåíåå ñòà ðóññêèõ ñëîâ. Òàêîå ÷èñëî äîëæíî ñóùåñòâîâàòü, ïîñêîëüêó ÷èñëî äîïóñòèìûõôðàç, èìåþùèõ ìåíåå ñòà ñëîâ, êîíå÷íî.  òî æå âðåìÿ îíî îïðåäåëÿåòñÿ ïðèâåäåííîéâûøå ôðàçîé, à â íåé ìåíåå ñòà ñëîâ! 1 íàøåì êóðñå, ê ñ÷àñòüþ, ïðîòèâîðå÷èé òàêîãî ðîäà ïðè çàäàíèè ìíîæåñòâ âîçíèêàòü íå áóäåò. Íî äàæå ïðè ïîëíîé ÿñíîñòè ñ îïðåäåëåíèåì ìíîæåñòâà (íàïðèìåð,ìíîæåñòâî êîðíåé óðàâíåíèÿ) íå âñåãäà ëåãêî óñòàíîâèòü, ñêîëüêî â íåì ýëåìåíòîâ èáóäåò ëè îíî âîîáùå íåïóñòûì.Äîâîëüíî ÷àñòî ìíîæåñòâà áóäóò çàäàâàòüñÿ ïåðå÷èñëåíèåì ñâîèõ ýëåìåíòîâ.
Íàïðèìåð, M = {1, 2, 3} ìíîæåñòâî, ñîñòîÿùåå èç òðåõ ÷èñåë 1, 2, 3.Êðîìå òîãî, íîâûå ìíîæåñòâà ìîæíî êîíñòðóèðîâàòü ñ ïîìîùüþ óæå èìåþùèõñÿìíîæåñòâ X è Y ñëåäóþùèì îáðàçîì:• A = X ∪ Y ≡ {a : a ∈ X èëè a ∈ Y }(îáúåäèíåíèå ìíîæåñòâ);• B = X ∩ Y ≡ {b : b ∈ X è b ∈ Y }(ïåðåñå÷åíèå ìíîæåñòâ);(ðàçíîñòü ìíîæåñòâ);• C = X\Y ≡ {c : c ∈ X, c ∈/ Y}• D = X × Y ≡ {d = (a, b) : a ∈ X, b ∈ Y }2.2(äåêàðòîâî ïðîèçâåäåíèå ìíîæåñòâ).Îòîáðàæåíèÿ, ôóíêöèè, îïåðàòîðûÂñå òðè ñëîâà èç çàãîëîâêà îçíà÷àþò îäíî è òî æå ðå÷ü èäåò î ïðàâèëå, ïî êîòîðîìóêàæäîìó ýëåìåíòó x ìíîæåñòâà X ñòàâèòñÿ â ñîîòâåòñòâèå îäíîçíà÷íî îïðåäåëåííûé1 Ïðèìåð èç ó÷åáíèêà Â. Â.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
