Е.Е. Тыртышников - Матричный анализ и линейная алгебра (1113045), страница 4
Текст из файла (страница 4)
Îáùåèçâåñòíî, îäíàêî, ÷òî çíà÷åíèå è ñèëà ëèíåéíîé àëãåáðûîáóñëîâëåíû ïðåæäå âñåãî åå ìíîãî÷èñëåííûìè ïðèëîæåíèÿìè.ß ñîãëàñåí ñ òåì, ÷òî ëèíåéíîé àëãåáðå íå ñëåäóåò ó÷èòü ñëèøêîì àáñòðàêòíî. Òåìáîëåå, ÷òî åñòü âîçìîæíîñòü ïîçíàêîìèòüñÿ ñ îñíîâíûìè ïîíÿòèÿìè, ðàáîòàÿ ñ ïðîñòûìè äëÿ ïîíèìàíèÿ îáúåêòàìè ìàòðèöàìè, à íå ñ àáñòðàêòíûìè ýëåìåíòàìè ëèíåéíûõïðîñòðàíñòâ.  òî æå âðåìÿ, ìíå êàæåòñÿ, ÷òî îïðåäåëåííàÿ äîçà àáñòðàêòíûõ ïîíÿòèéóìåñòíà è äàæå ïîëåçíà íà ñàìîé ðàííåé ñòàäèè îáó÷åíèÿ.
 ñàìîì äåëå, âðÿä ëè ìîæíîñ÷èòàòü ÷ðåçìåðíûìè óñèëèÿ íà îñâîåíèå âñåãî ëèøü îïðåäåëåíèÿ ãðóïïû è ïðîñòåéøèõ åå ñâîéñòâ. Îäíàêî, åñëè ýòî ñäåëàòü íà ðàííåì ýòàïå îáó÷åíèÿ, òî â äàëüíåéøåìíàõîäèòñÿ ìíîãî ïîâîäîâ äëÿ âîçâðàùåíèÿ ê ýòîìó ïîíÿòèþ â ñâÿçè ñ ïðèìåðàìè ãðóïï,êîòîðûå åñòåñòâåííûì îáðàçîì âîçíèêàþò â ðàçíûõ ìåñòàõ êóðñà.Ìíå êàæåòñÿ, ÷òî óïðîùåíèå ôîðìû èçëîæåíèÿ âñå æå ìîæåò ñî÷åòàòüñÿ ñ áîëååíàïîëíåííûì ñîäåðæàíèåì. Ïî êðàéíåé ìåðå, ÿ ñòðåìèëñÿ ê ýòîìó.
Ëèíåéíàÿ àëãåáðàè åå ïðèëîæåíèÿ íàñòîëüêî ôóíäàìåíòàëüíû è âàæíû, ÷òî íåò íèêàêèõ îñíîâàíèé äëÿðåàëüíîãî ñîêðàùåíèÿ îáúåìà îáÿçàòåëüíûõ áàçîâûõ çíàíèé â äàííîé îáëàñòè. íàøåì êóðñå ïðåäìåò ëèíåéíîé àëãåáðû ïîíèìàåòñÿ â ðàñøèðåííîì ñìûñëå, äîâîëüíî ÷àñòî ìû îêàçûâàåìñÿ íà òåððèòîðèè ñìåæíûõ äèñöèïëèí ìàòåìàòè÷åñêîãî àíàëèçà, âû÷èñëèòåëüíûõ ìåòîäîâ è, êîíå÷íî, îáùåé àëãåáðû. Ãðàíèöû ÿâëÿþòñÿóñëîâíîñòüþ, êàê è â æèçíè. Îñîáåííî ÷àñòî îíè ïåðåñåêàþòñÿ ïðè ðàçðàáîòêå ñîâðåìåííûõ èíôîðìàöèîííûõ è âû÷èñëèòåëüíûõ òåõíîëîãèé.Íàïðèìåð, îäíà èç ãëàâíûõ îáÿçàòåëüíûõ òåì ïåðâîãî ñåìåñòðà òåîðèÿ è ìåòîäû èññëåäîâàíèÿ è ðåøåíèÿ ñèñòåì ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé.
Ìàòåðèàëâïîëíå ýëåìåíòàðíûé è, âîçìîæíî, îñòàâëÿþùèé âïå÷àòëåíèå àáñîëþòíîé çàâåðøåííîñòè. Îäíàêî, ïðàêòè÷åñêàÿ íåîáõîäèìîñòü ðåøåíèÿ ñèñòåì ñ ìèëëèîíàìè óðàâíåíèéè íåèçâåñòíûõ è ïîÿâëåíèå âû÷èñëèòåëüíîé òåõíèêè ñ ïàðàëëåëüíûì âûïîëíåíèåì îïåðàöèé äàëè èìïóëüñ ê èçó÷åíèþ íîâûõ, ïàðàëëåëüíûõ ñâîéñòâ àëãîðèòìîâ.  äàííîìñëó÷àå óñïåõè ïðÿìî ñâÿçàíû ñ ðîñòîì ìîùè êîìïüþòåðîâ.  òî æå âðåìÿ - è ìíå îñîáåííî ïðèÿòíî ñêàçàòü îá ýòîì - âûõîä íà ðàäèêàëüíî íîâûé óðîâåíü âîçìîæíîñòåéáûë ñäåëàí áëàãîäàðÿ íîâîìó ìàòåìàòè÷åñêîìó çíàíèþ, à íå ðîñòó ïðîèçâîäèòåëüíîñòè êîìïüþòåðîâ. Áîëåå òîãî, äëÿ äàííîé âïîëíå êëàññè÷åñêîé çàäà÷è ëèíåéíîé àëãåáðûïîòðåáîâàëîñü ðàçâèòèå ôóíäàìåíòàëüíûõ âîïðîñîâ èç îáëàñòè ìàòåìàòè÷åñêîãî àíàëèçà è òåîðèè ïðèáëèæåíèé.Îòäåëüíûå ìåñòà â êíèãå ñîäåðæàò ìàòåðèàë, êîòîðûé âîîáùå íåëüçÿ íàéòè â êàêèõëèáî ó÷åáíèêàõ è äàæå ìîíîãðàôèÿõ.
 ÷àñòíîñòè, ýòî îòíîñèòñÿ ê òåîðåìå îá îáîáùå-Å. Å. Òûðòûøíèêîâ3íèÿõ ìåòîäîâ ñîïðÿæåííûõ ãðàäèåíòîâ.  åùå áîëüøåé ñòåïåíè êî âñåìó ìàòåðèàëóçàêëþ÷èòåëüíîé ëåêöèè, ïîñâÿùåííîé ìíîãîìåðíûì ìàññèâàì, òåíçîðíûì ðàíãàì è ïîëèëèíåéíûì îáîáùåíèÿì ñèíãóëÿðíîãî ðàçëîæåíèÿ ìàòðèöû.Ê äîïîëíèòåëüíîìó ìàòåðèàëó, âåðîÿòíî, ñëåäóåò îòíåñòè è âêëþ÷åííûå â òåêñòëåêöèé çàäà÷è. Ýòî èìåííî çàäà÷è, à íå óïðàæíåíèÿ. Áîëåå òîãî, îáû÷íî ýòî íå ñàìûå ëåãêèå çàäà÷è, íî ïðè ýòîì ïîäñêàçêîé ê èõ ðåøåíèþ ÿâëÿåòñÿ ñàìî ðàñïîëîæåíèåçàäà÷è. Êîíå÷íî, äëÿ àêòèâíîãî îñâîåíèÿ ëèíåéíîé àëãåáðû íóæíû è óïðàæíåíèÿ, èçàäà÷è ðàçíîãî óðîâíÿ ñëîæíîñòè.
Èõ ìîæíî íàéòè â ðàçëè÷íûõ ðàçäåëàõ ñóùåñòâóþùèõ çàäà÷íèêîâ (íàïðèìåð, [11, 17, 20, 25]). òå âðåìåíà, êîãäà ôàêóëüòåò ÂÌèÊ òîëüêî ïîÿâèëñÿ, ìàòåìàòèêè-âû÷èñëèòåëè÷àñòî ñåòîâàëè íà òî, ÷òî â îáÿçàòåëüíûõ êóðñàõ ìåõ-ìàòà íè÷åãî íå ãîâîðèëîñü îâîçíèêøèõ ïåðåä íèìè ïðîáëåìàõ.  íàñòîÿùåå âðåìÿ ìîæíî óæå ãîâîðèòü î òîì, ÷òîìàòåìàòèêàì-âû÷èñëèòåëÿì ÷àñòî íå õâàòàåò çíàíèé èç òðàäèöèîííûõ èìåííî äëÿ ìåõìàòà ðàçäåëîâ ìàòåìàòèêè. Ìîæíî ïðèâåñòè ïðèìåðû ðåêîðäíî ýôôåêòèâíûõ âû÷èñëèòåëüíûõ òåõíîëîãèé, âîçíèêøèõ íà îñíîâå èäåé è àïïàðàòà êàçàëîñü áû äàëåêèõ îòïðèëîæåíèé îáëàñòåé íàïðèìåð, àëãåáðàè÷åñêîé òîïîëîãèè. Ïîñëåäíèå çàÿâëåíèÿ âäàííîé êíèãå îñòàíóòñÿ âñå æå ëèøü äåêëàðàöèÿìè, ê ñîæàëåíèþ àâòîðà è ÷èòàòåëåé.Íî âåäü ýòî ëèøü íà÷àëî ïóòè! ëþáîì äåëå î÷åíü âàæåí íà÷àëüíûé èìïóëüñ.
Äëÿ äàííîé êíèãè åãî ãåíåðàòîðîìáûë Â. À. Èëüèí, ïðèãëàñèâøèé ìåíÿ ïðî÷èòàòü ëåêöèè íà ÂÌèÊ. Èíñòèòóòå âû÷èñëèòåëüíîé ìàòåìàòèêè Ðîññèéñêîé àêàäåìèè íàóê, ãäå ÿ èìåþ÷åñòü ðàáîòàòü, ýòî ïðåäëîæåíèå áûëî ãîðÿ÷î ïîääåðæàíî Â. Â. Âîåâîäèíûì, Â. Ï.Äûìíèêîâûì è Ã. È. Ìàð÷óêîì, ïîïðîñèâøèì ìåíÿ â òî æå ñàìîå âðåìÿ ïîìî÷ü âîðãàíèçàöèè íà ÂÌèÊ íîâîé êàôåäðû êàôåäðû âû÷èñëèòåëüíûõ òåõíîëîãèé è ìîäåëèðîâàíèÿ, êîòîðîé îí ñòàë çàâåäîâàòü.Ìíå îñòàâàëîñü òîëüêî ñîãëàñèòüñÿ è ïîïûòàòüñÿ ñäåëàòü òî, î ÷åì ÿ, ñêîðåå âñåãî, óæå äóìàë ïîïðîáîâàòü ðàññêàçàòü ñòóäåíòàì î ëèíåéíîé àëãåáðå òî, ÷òî ÿ ñàìáû õîòåë óñëûøàòü, êîãäà áûë ñòóäåíòîì. Ïî êðàéíåé ìåðå, ñàìîìó ìíå ýòî âñå ïîêàíðàâèòñÿ. Ïîýòîìó âñåì íàçâàííûì ëèöàì âûðàæàþ èñêðåííþþ áëàãîäàðíîñòü.
Õî÷óïîáëàãîäàðèòü òàêæå Ñ. À. Ãîðåéíîâà, Í. Ë. Çàìàðàøêèíà, Õ. Ä. Èêðàìîâà, Ã. Ä. Êèì,Â. Ñ. Ïàíôåðîâà, Â. Í. ×óãóíîâà è âñåõ òåõ, êòî óæå ñäåëàë èëè åùå ñäåëàåò çàìå÷àíèÿïî òåêñòó ëåêöèé.4.ÏÐÅÄÈÑËÎÂÈÅËåêöèÿ 11.1Ëèíåéíûå îòîáðàæåíèÿ è ìàòðèöû ìàòåìàòèêå è äðóãèõ íàóêàõ ïîñòîÿííî èçó÷àåòñÿ çàâèñèìîñòü îäíèõ âåëè÷èí îòäðóãèõ. Îáû÷íî çàâèñèìîñòü îïèñûâàåòñÿ ðàçëè÷íîãî òèïà ôóíêöèÿìè (îòîáðàæåíèÿìè, îïåðàòîðàìè).
Ïðîñòåéøèé ñëó÷àé ëèíåéíûå îòîáðàæåíèÿ. Ñòðîãèå îïðåäåëåíèÿìû äàäèì ïîçæå. À ïîêà ïðåäïîëîæèì, ÷òî ïåðåìåííûå y1 , . . . , ym âûðàæàþòñÿ ÷åðåçx1 , . . . , xn ñëåäóþùèì îáðàçîì: y1 = a11 x1 + . . . + a1n xn ,...(∗)ym = am1 x1 + . . . + amn xn ,ãäå êîýôôèöèåíòû ñ÷èòàþòñÿ çàäàííûìè ïîñòîÿííûìè âåëè÷èíàìè. Ñîáåðåì âñå ïîñòîÿííûå êîýôôèöèåíòû â ïðÿìîóãîëüíóþ òàáëèöó è îáîçíà÷èì åå áóêâîé A; ñîñòàâèìòàêæå òàáëèöû-ñòîëáöû èç âåëè÷èí x1 , .
. . , xn è y1 , . . . , ym :a11 . . . a1nx1y1A = ... ... ... ,x = ... ,y = ... .am1 . . . amnxnymÒàêèå òàáëèöû è íàçûâàþòñÿ ìàòðèöàìè. Ìû èìååì öåëûõ òðè ìàòðèöû: ðàçìåðîâm × n, n × 1 è m × 1. Ñîîòíîøåíèÿ (∗), îïèñûâàþùèå çàâèñèìîñòü y îò x, çàïèøåìñèìâîëè÷åñêè òàêèì îáðàçîì:y = Ax.(∗∗)Âîçíèêàåò âïå÷àòëåíèå, ÷òî ìàòðèöà A óìíîæàåòñÿ íà ìàòðèöó-ñòîëáåö x, â ðåçóëüòàòå÷åãî ïîÿâëÿåòñÿ ìàòðèöà-ñòîëáåö y .
Òàê îíî è áóäåò, åñëè ìû ñêàæåì, ÷òî ñîîòíîøåíèÿ(∗) ñóòü îïðåäåëåíèå îïåðàöèè (∗∗) óìíîæåíèÿ A íà x.Åñëè m = n, òî ìàòðèöà íàçûâàåòñÿ êâàäðàòíîé. Êâàäðàòíàÿ ìàòðèöà ðàçìåðîân × n íàçûâàåòñÿ òàêæå ìàòðèöåé ïîðÿäêà n.1.2Óìíîæåíèå ìàòðèöÏóñòü y1 , . . . , ym âûðàæàþòñÿ ÷åðåç x1 , . . .
, xn è ïðè ýòîì x1 , . . . , xn âûðàæàþòñÿ ÷åðåçz1 , . . . , zk ñëåäóþùèì îáðàçîì:((y1=a11 x1ym= am1 x1+ . . . + 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 ñëîæåíèé). Íî õîðîøî ëè ýòî? Óâåðåíû ëè ìû âòîì, ÷òî ýòî íàèëó÷øèé àëãîðèòì?Ñàìî ïîíÿòèå íàèëó÷øèé ïðåäïîëàãàåò íàëè÷èå íåêîãî ìíîæåñòâà âîçìîæíûõàëãîðèòìîâ. Áóäåì ïîëàãàòü, ÷òî àëãîðèòì ýòî ïîñëåäîâàòåëüíîñòü ýëåìåíòàðíûõîïåðàöèé èç êîíå÷íîãî ôèêñèðîâàííîãî íàáîðà ýëåìåíòàðíûõ îïåðàöèé.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
