Е.Е. Тыртышников - Матричный анализ и линейная алгебра (1113045), страница 12
Текст из файла (страница 12)
. , (Pk . . . P2 P1 A)x = Pk . . . P2 P1 b.Ìàòðèöà êîýôôèöèåíòîâ ïîñëåäíåé ñèñòåìû èìååò íàñòîëüêî ïðîñòîé âèä, ÷òî ðåøåíèåñîîòâåòñòâóþùåé ñèñòåìû îñóùåñòâëÿåòñÿ óæå î÷åâèäíûì îáðàçîì.Öåëü êàæäîãî øàãà ïîëó÷åíèå äîïîëíèòåëüíûõ íóëåé, èëè, êàê ÷àñòî ãîâîðÿò,èñêëþ÷åíèå ýëåìåíòîâ â ìàòðèöå ïðåîáðàçîâàííîé ñèñòåìû. ×òîáû ïîÿñíèòü, êàê ýòîäåëàåòñÿ, ðàññìîòðèì ìàòðèöó A ðàçìåðîâ 4 × 6, çàâåäîìî íóëåâûå ýëåìåíòû áóäåìîáîçíà÷àòü íîëèêîì, ïðîèçâîëüíûå ýëåìåíòû êðåñòèêîì, à çàâåäîìî íåíóëåâûåýëåìåíòû êðåñòèêîì â ðàìî÷êå. Åñëè a11 6= 0, òî èç êàæäîé ñòðîêè ñ íîìåðîì i > 1ìîæíî âû÷åñòü ïåðâóþ ñ êîýôôèöèåíòîì, äàþùèì íóëü â ïîçèöèè (i, 1):×2×××××××××××××××××××××××7→49×2000××××××××××××××××××.××50Ëåêöèÿ 8 äàëüíåéøåì ïåðâûå ñòðîêà è ñòîëáåö îñòàþòñÿ áåç èçìåíåíèé.
Åñëè âî âòîðîì ñòîëáöåèìååòñÿ íå íóëü, äåëàåì ñîîòâåòñòâóþùóþ ñòðîêó âòîðîé è ñ åå ïîìîùüþ èñêëþ÷àåìâñå îñòàëüíûå ýëåìåíòû âòîðîãî ñòîëáöà:×2000××2××××××××××××××××××7→×2000××200××××××××××××××.××Ïåðâûå äâà ñòîëáöà è ïåðâûå äâå ñòðîêè ìåíÿòüñÿ áîëüøå íå áóäóò. Ìîæåò ñëó÷èòüñÿòàê, ÷òî ó íàñ ïîëó÷èëèñü âíåïëàíîâûå íóëåâûå ñòîëáöû. Íàïðèìåð, åñëè îñòàâøèåñÿêðåñòèêè â òðåòüåì è ÷åòâåðòîì ñòîëáöàõ îêàçàëèñü íóëÿìè, òî ñëåäóåò ïðîâîäèòüèñêëþ÷åíèå ñ ïîìîùüþ íåíóëåâîãî ýëåìåíòà â ïÿòîì ñòîëáöå (åñëè òàêîâîé åñòü):×2000××200××00××00×××2×××××7→×2000××200××00××00×××20××.××Êàæûé øàã, î÷åâèäíî, ñâîäèòñÿ ê óìíîæåíèþ ìàòðèöû ñëåâà íà íåêîòîðóþ ìàòðèöó Pl .
Ïðè ýòîì êàæäàÿ èç ìàòðèö Pl , 1 ≤ l ≤ k , ìîæåò áûòü ïðåäñòàâëåíà êàêïðîèçâåäåíèå äâóõ ìàòðèö:P l = Z l Πl ,ãäå Zl îòëè÷àåòñÿ îò I (åäèíè÷íîé ìàòðèöû) òîëüêî â ïîçèöèÿõ íèæå ãëàâíîé äèàãîíàëèêàêîãî-òî îäíîãî (ïóñòü j -ãî) ñòîëáöà:Zl = 1...,1(Zl )j+1 j...(Zl )nj...1à Πl ïîëó÷àåòñÿ èç I ïåðåñòàíîâêîé ñòîëáöîâ (èëè ñòðîê). Ìàòðèöû Πl è Zl óêàçàííîãîñïåöèàëüíîãî âèäà áóäåì äëÿ êðàòêîñòè íàçûâàòü ýëåìåíòàðíûìè ìàòðèöàìè; ìàòðèöà Πl íàçûâàåòñÿ ìàòðèöåé ïåðåñòàíîâêè, à Zl ìàòðèöåé ìîäèôèêàöèè ñòðîê. Èõðîëü â ïðîöåññå èñêëþ÷åíèÿ îáúÿñíÿåòñÿ ñëåäóþùèìè ôàêòàìè:• ìàòðèöà Πl A îòëè÷àåòñÿ îò A ïåðåñòàíîâêîé ñòðîê;• åñëè Zl îòëè÷àåòñÿ îò åäèíè÷íîé ìàòðèöû j -ì ñòîëáöîì, òî ìàòðèöà Zl A èìååòïåðâûå j ñòðîê òå æå, ÷òî è â ìàòðèöå A, à i-ÿ ñòðîêà ïðè i > j åñòü ñóììà i-éñòðîêè è âçÿòîé ñ íåêîòîðûì êîýôôèöèåíòîì j -é ñòðîêè ìàòðèöû A.Óòâåðæäåíèå 1.
Ëþáàÿ ìàòðèöà ïåðåñòàíîâêè Π îáðàòèìà è ïðè ýòîìΠ−1 = Π> .Å. Å. Òûðòûøíèêîâ51Óòâåðæäåíèå 2. Ëþáàÿ ìàòðèöà ìîäèôèêàöèè ñòðîê Z = Zl îáðàòèìà è ïðè ýòîìîáðàòíàÿ ìàòðèöà ïîëó÷àåòñÿ èç Z èçìåíåíèåì çíàêîâ ïîääèàãîíàëüíûõ ýëåìåíòîâ:1Z −1=...1−(Zl )j+1 j.....−(Zl )nj,.1Äîêàçàòåëüñòâî ñâîäèòñÿ ê íåïîñðåäñòâåííîé ïðîâåðêå ðàâåíñòâ ΠΠ−1 = I , ZZ −1 = I .8.3Ñòóïåí÷àòûå ìàòðèöûÁóäåì ãîâîðèòü, ÷òî ìàòðèöà S = [sij ] ðàçìåðîâ m × n ÿâëÿåòñÿ âåðõíåé ñòóïåí÷àòîéñ ÷èñëîì ñòóïåíåé k , åñëè ñóùåñòâóþò íîìåðà 1 ≤ j1 < .
. . < jk ≤ m, äëÿ êîòîðûõ:• åñëè 1 ≤ i ≤ k , òî sij 6= 0 ïðè j = ji è sij = 0 ïðè âñåõ 1 ≤ j ≤ ji − 1;• åñëè k + 1 ≤ i ≤ m, òî sij = 0 ïðè âñåõ 1 ≤ j ≤ n.Ìàòðèöà S íàçûâàåòñÿ íèæíåé ñòóïåí÷àòîé ñ ÷èñëîì ñòóïåíåé k , åñëè S > ÿâëÿåòñÿâåðõíåé ñòóïåí÷àòîé ñ ÷èñëîì ñòóïåíåé k .Óòâåðæäåíèå. Ðàíã ñòóïåí÷àòîé ìàòðèöû ñ ÷èñëîì ñòóïåíåé k ðàâåí k .Äîêàçàòåëüñòâî. Ðàññìîòðèì âåðõíþþ ñòóïåí÷àòóþ ìàòðèöó S è äîêàæåì, ÷òî ååñòðî÷íûé ðàíã (ðàçìåðíîñòü ëèíåéíîé îáîëî÷êè ñòðîê) ðàâåí ÷èñëó ñòóïåíåé k .
ßñíî,÷òî S èìååò ðîâíî k íåíóëåâûõ ñòðîê. Äîêàæåì, ÷òî ýòè ñòðîêè ëèíåéíî íåçàâèñèìû.Ïðèðàâíÿåì íóëþ èõ ëèíåéíóþ êîìáèíàöèþ ñ êîýôôèöèåíòàìè α1 , . . . , αk :[α1 , . . . , αk ]S = [0, . . . , 0].Îòñþäàα1 s1i1 = 0⇒α1 = 0.Äàëåå,0 · s1 i2 + α2 s2 i2 = 0⇒α2 = 0.Ïðîäîëæàÿ ïîäîáíûì îáðàçîì, íàõîäèì α1 = . . . = αk = 0.  ñëó÷àå íèæíåé ñòóïåí÷àòîé ìàòðèöû S åå ñòîëáöîâûé ðàíã, î÷åâèäíî, ñîâïàäàåò ñî ñòðî÷íûì ðàíãîì âåðõíåéñòóïåí÷àòîé ìàòðèöû S > . 28.4Ïðèâåäåíèå ê ñòóïåí÷àòîé ôîðìåÒåîðåìà 1. Äëÿ ëþáîé m×n-ìàòðèöû A ðàíãà r ñóùåñòâóåò îáðàòèìàÿ ìàòðèöà P ,ïðåäñòàâèìàÿ â âèäå ïðîèçâåäåíèÿ êîíå÷íîãî ÷èñëà ýëåìåíòàðíûõ ìàòðèö è òàêàÿ,÷òî ìàòðèöà S = P A ÿâëÿåòñÿ âåðõíåé ñòóïåí÷àòîé ñ ÷èñëîì ñòóïåíåé r.Äîêàçàòåëüñòâî.
Îáîçíà÷èì ÷åðåç j1 íîìåð ïåðâîãî ñòîëáöà ìàòðèöû A, â êîòîðîìåñòü õîòÿ áû îäèí íåíóëåâîé ýëåìåíò. (Åñëè òàêîâîé ñòîëáåö îòñóòñòâóåò, òî A = 0 è òåîðåìà óæå äîêàçàíà.) Ñ ïîìîùüþ óìíîæåíèÿ ñëåâà íà íåêîòîðóþ ìàòðèöó ïåðåñòàíîâêè52Ëåêöèÿ 8Π1 íåíóëåâîé ýëåìåíò ìîæíî ïåðåìåñòèòü â ïîçèöèþ (1, j1 ). Äàëåå ñ ïîìîùüþ óìíîæåíèÿ ñëåâà íà íåêîòîðóþ ìàòðèöó ìîäèôèêàöèè ñòðîê Z1 ìîæíî ïîëó÷èòü ìàòðèöóñ íóëÿìè â ïîääèàãîíàëüíûõ ïîçèöèÿõ j1 -ãî ñòîëáöà è ñîõðàíåíèåì íóëåé â ïðåäûäóùèõ ñòîëáöàõ. Î÷åâèäíî, ïðåîáðàçîâàííàÿ ìàòðèöà èìååò áëî÷íûé âèä (÷åðåç 0p×q ìûîáîçíà÷àåì íóëåâîé áëîê ðàçìåðîâ p × q )01×(i1 −1)u>Z 1 Π1 A =,u ∈ R(n−i1 +1)×1 .0(m−1)×(i1 −1) BÑäåëàåì èíäóêòèâíîå ïðåäïîëîæåíèå î ñóùåñòâîâàíèè ìàòðèöû Q, ÿâëÿþùåéñÿ ïðîèçâåäåíèåì ýëåìåíòàðíûõ ìàòðèö ïîðÿäêà m − 1 è òàêîé, ÷òî QB èìååò âåðõíþþ ñòóïåí÷àòóþ ôîðìó. Ðàññìîòðèì ìàòðèöó1 0P =Z 1 Π1 .0 QËåãêî âèäåòü, ÷òî P åñòü ïðîèçâåäåíèå ýëåìåíòàðíûõ ìàòðèö è ïðè ýòîì S = P A èìååòâåðõíþþ ñòóïåí÷àòóþ ôîðìó.
Ïóñòü ÷èñëî ñòóïåíåé ðàâíî k . Çíà÷èò, ñòðî÷íûé ðàíãìàòðèöû S ðàâåí k ⇒ k = rank S = rank A = r. 2Òåîðåìà 2. Äëÿ ëþáîé m×n-ìàòðèöû A ðàíãà r ñóùåñòâóåò îáðàòèìàÿ ìàòðèöà Q,ïðåäñòàâèìàÿ â âèäå ïðîèçâåäåíèÿ êîíå÷íîãî ÷èñëà ýëåìåíòàðíûõ ìàòðèö è òàêàÿ,÷òî ìàòðèöà AQ> ÿâëÿåòñÿ íèæíåé ñòóïåí÷àòîé ñ ÷èñëîì ñòóïåíåé r.Äîêàçàòåëüñòâî. Äîñòàòî÷íî ïðèìåíèòü òåîðåìó 1 ê ìàòðèöå A> è çàìåòèòü, ÷òîåñëè ìàòðèöà QA> âåðõíÿÿ ñòóïåí÷àòàÿ, òî ìàòðèöà (QA> ) = AQ> áóäåò íèæíåéñòóïåí÷àòîé.8.5Ïðèâåäåíèå ê äèàãîíàëüíîé ôîðìåÒåîðåìà.
Äëÿ ëþáîé m × n-ìàòðèöû A ðàíãà r ñóùåñòâóþò îáðàòèìûå ìàòðèöû Pè Q, ïðåäñòàâèìûå â âèäå ïðîèçâåäåíèÿ êîíå÷íîãî ÷èñëà ýëåìåíòàðíûõ ìàòðèö è òàêèå, ÷òî ìàòðèöà B = P AQ> èìååò íåíóëåâûå ýëåìåíòû b11 , . . . , brr , à âñå îñòàëüíûååå ýëåìåíòû ðàâíû íóëþ.Äîêàçàòåëüñòâî. Ñíà÷àëà ïðèâåäåì A ê âåðõíåé ñòóïåí÷àòîé ôîðìå S = P A, àçàòåì çàìåòèì, ÷òî íèæíÿÿ ñòóïåí÷àòàÿ ôîðìà SQ> , ïîëó÷àåìàÿ ñîãëàñíî ïîñòðîåíèÿìòåîðåìû 2, áóäåò èìåòü òðåáóåìóþ äèàãîíàëüíóþ ôîðìó.
28.6Ýêâèâàëåíòíûå ìàòðèöûÌàòðèöû A è B íàçûâàþòñÿ ýêâèâàëåíòíûìè, åñëè ñóùåñòâóþò îáðàòèìûå ìàòðèöûP è Q òàêèå, ÷òî B = P AQ.Òåîðåìà. Ìàòðèöû A è B ýêâèâàëåíòíû òîãäà è òîëüêî òîãäà, êîãäà îíè èìåþòîäèíàêîâûå ðàçìåðû è îäèíàêîâûå ðàíãè.Äîêàçàòåëüñòâî.  ñèëó òåîðåìû î ïðèâåäåíèè ê äèàãîíàëüíîé ôîðìå, êàæäàÿ èçìàòðèö A è B ýêâèâàëåíòíà ïðÿìîóãîëüíîé äèàãîíàëüíîé ìàòðèöå îáîçíà÷èì èõ ÷åðåç DA è DB . Ïðè ýòîì î÷åâèäíî, ÷òî DA è DB ýêâèâàëåíòíû òîãäà è òîëüêî òîãäà, êîãäàîíè èìåþò îäèíàêîâîå ÷èñëî íåíóëåâûõ äèàãîíàëüíûõ ýëåìåíòîâ. Ïîñëåäíåå îçíà÷àåò,÷òî rank DA = rank DB .
Îñòàåòñÿ ó÷åñòü, ÷òî rank A = rank DA è rank B = rank DB . 2Å. Å. Òûðòûøíèêîâ8.753Ìåòîä Ãàóññà è LU -ðàçëîæåíèåÐàññìîòðåííûé âûøå ìåòîä èñêëþ÷åíèÿ íåèçâåñòíûõ îáû÷íî íàçûâàþò ìåòîäîì Ãàóññà. Ïóñòü îí ïðèìåíÿåòñÿ ê ñèñòåìå Ax = b ñ íåâûðîæäåííîé ìàòðèöåé A.  äàííîìñëó÷àå âåðõíÿÿ ñòóïåí÷àòàÿ ìàòðèöà, ê êîòîðîé ïðèâîäèòñÿ ìàòðèöà A, îêàçûâàåòñÿâåðõíåé òðåóãîëüíîé ìàòðèöåé.Ìåòîä èñêëþ÷åíèÿ íåèçâåñòíûõ ìîæíî òðàêòîâàòü êàê ìåòîä èñêëþ÷åíèÿ ýëåìåíòîâìàòðèöû ñ öåëüþ ïðèâåäåíèÿ åå ê áîëåå ïðîñòîìó âèäó. Åñëè ìîæíî îáîéòèñü áåç ïåðåñòàíîâêè óðàâíåíèé (ñòðîê ìàòðèöû), òî ìåòîä Ãàóññà äëÿ ìàòðèöû ïîðÿäêà n ñîñòîèòâ ïîñëåäîâàòåëüíîì èñêëþ÷åíèè ýëåìåíòîâ â ñòîëáöàõ îò 1-ãî äî n − 1-ãî è ïðèâîäèò êðàâíîñèëüíîé ñèñòåìå(Zn−1 .
. . Z2 Z1 A)x = Zn−1 . . . Z2 Z1 b,(∗)ãäå Z1 , . . . , Zn−1 ìàòðèöû ìîäèôèêàöèè ñòðîê, ïðè÷åì Zi îòëè÷àåòñÿ îò I â òî÷íîñòèi-ì ñòîëáöîì. Êàæäàÿ èç ìàòðèö Z1 , . . . , Zn−1 ÿâëÿåòñÿ íèæíåé òðåóãîëüíîé, ïîýòîìóèõ ïðîèçâåäåíèåb = Zn−1 . . .
Z1Lÿâëÿåòñÿ òàêæå íèæíåé òðåóãîëüíîé ìàòðèöåé. Ìàòðèöà êîýôôèöèåíòîâ ñèñòåìû (∗)bAU = Zn−1 . . . Z1 A = Lb −1 ÿâëÿåòñÿ òàêæå íèæíåé òðåóãîëüíîé.ÿâëÿåòñÿ âåðõíåé òðåóãîëüíîé. Ìàòðèöà L = LÑëåäîâàòåëüíî, ìåòîä Ãàóññà ïîðîæäàåò ðàçëîæåíèå ìàòðèöû A â ïðîèçâåäåíèå íèæíåéè âåðõíåé òðåóãîëüíîé ìàòðèöA = LU.Ïðè ýòîì L èìååò íà ãëàâíîé äèàãîíàëè åäèíèöû, à U ÿâëÿåòñÿ íåâûðîæäåííîé ìàòðèöåé (â ñèëó íåâûðîæäåííîñòè A).
Òàêîå ðàçëîæåíèå íàçûâàåòñÿ LU -ðàçëîæåíèåì.Ïîäñ÷èòàåì ÷èñëî àðèôìåòè÷åñêèõ îïåðàöèé ïðè ïðèâåäåíèè A ê âåðõíåé òðåóãîëüíîé ìàòðèöå U . Íà i-ì øàãå òðåáóåòñÿ ïîëó÷èòü n − i íóëåé íèæå äèàãîíàëè â i-ìñòîëáöå. Ïðè ïîëó÷åíèè íóëÿ íà ïåðåñå÷åíèè i-ãî ñòîëáöà è l-é ñòðîêè ïðè l > i èç l-éñòðîêè âû÷èòàåòñÿ i-ÿ ñòðîêà, ïðåäâàðèòåëüíî óìíîæåííàÿ íà êîýôôèöèåíò, âûáîð êîòîðîãî è îáåñïå÷èâàåò ïîëó÷åíèå äàííîãî íóëÿ. Ïîñêîëüêó â ðàññìàòðèâàåìûõ ñòðîêàõìîæåò áûòü òîëüêî n − i íåíóëåâûõ ýëåìåíòîâ, ÷èñëî óìíîæåíèé (è âû÷èòàíèé) ïðèïîëó÷åíèè îäíîãî íóëÿ â i-ì ñòîëáöå ðàâíî (n − i)2 .
Âñåãî ïîòðåáóåòñÿ(n − 1)2 + (n − 2)2 + . . . + 12 =1 3n + O(n2 )3óìíîæåíèé è ñòîëüêî æå âû÷èòàíèé; ÷åðåç O(n2 ) îáîçíà÷åí ìíîãî÷ëåí îò n ñòåïåíè 2.×òîáû íàéòè ðåøåíèå ñèñòåìû Ax = b, òðåáóåòñÿ âûïîëíèòü åùå äâà äåéñòâèÿ:• âû÷èñëèòü âåêòîð Zn−1 . . . Z1 b;• íàéòè ðåøåíèå ñèñòåìû ñ âåðõíåé òðåóãîëüíîé ìàòðèöåé U .Êàæäîå èç ýòèõ äåéñòâèé òðåáóåò ëèøü O(n2 ) àðèôìåòè÷åñêèõ îïåðàöèé íà ïîðÿäîêìåíüøå, ÷åì ïðèâåäåíèå ê âåðõíåìó òðåóãîëüíîìó âèäó.Çàäà÷à.Íåâûðîæäåííàÿ ìàòðèöà è îáðàòíàÿ ê íåé ðàçáèòû íà áëîêè îäèíàêîâûõ ðàçìåðîâ:A11A=A21A12,A22A−1B11=B21B12.B2254Ëåêöèÿ 8Äîêàçàòü, ÷òî áëîêA11íåâûðîæäåí òîãäà è òîëüêî òîãäà, êîãäà íåâûðîæäåí áëîêB22 .ÄÎÏÎËÍÈÒÅËÜÍÀß ×ÀÑÒÜ8.8LU -ðàçëîæåíèå è ñòðîãî ðåãóëÿðíûå ìàòðèöûÄîïóñòèì, ÷òî íåâûðîæäåííàÿ ìàòðèöà A èìååò LU -ðàçëîæåíèå: A = LU .
Îáîçíà÷èì÷åðåç Ak , Lk , Uk ïîäìàòðèöû ïîðÿäêà k , ðàñïîëîæåííûå â ëåâîì âåðõíåì óãëó ìàòðèöA, L, U , ñîîòâåòñòâåííî, è ðàññìîòðèì ðàâåíñòâî áëî÷íûõ ìàòðèöAk PLk 0Uk WA≡=ekekek .Q AV L0 UÎòñþäà âûòåêàåò, ÷òîAk = Lk Uk ,k = 1, . . . , n.Î÷åâèäíî, ÷òî ìàòðèöû Lk è UK íåâûðîæäåííûå (êàê òðåóãîëüíûå ìàòðèöû ñ íåíóëåâîé äèàãîíàëüþ). Ïîýòîìó ïîäìàòðèöà Ak äîëæíà áûòü íåâûðîæäåííîé.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
