Е.Е. Тыртышников - Матричный анализ и линейная алгебра (1113045), страница 58
Текст из файла (страница 58)
×àñòî ýòî ñâÿçàíî ñ íàëè÷èåì áîëüøîãî ÷èñëà íóëåé â ìàòðèöå. Èíîãäà íóëåé279280Ëåêöèÿ 44îêàçûâàåòñÿ íàñòîëüêî ìíîãî, ÷òî êàæäûé ÷ëåí îïðåäåëèòåëÿ ñîäåðæèò íóëåâîé ñîìíîæèòåëü è ïîýòîìó ðàâåí íóëþ. Î÷åâèäíî, òàê îáñòîèò äåëî, åñëè ìàòðèöà èìååò íóëåâîé ñòîëáåö èëè íóëåâóþ ñòðîêó.Ñëåäóþùåå óòâåðæäåíèå ïðåäñòàâëÿåò ñîáîé íåòðèâèàëüíîå îáîáùåíèå ýòîãî íàáëþäåíèÿ.Òåîðåìà Õîëëà.
Äëÿ òîãî ÷òîáû âñå ÷ëåíû îïðåäåëèòåëÿ ìàòðèöû ïîðÿäêà n áûëè ðàâíû íóëþ,íåîáõîäèìî è äîñòàòî÷íî ñóùåñòâîâàíèå íóëåâîé ïîäìàòðèöû ðàçìåðîâ p × q ñ óñëîâèåì p + q > n.Äîêàçàòåëüñòâî äîñòàòî÷íîñòè ÿâëÿåòñÿ ïðîñòûì óïðàæíåíèåì. À âîò äîêàçàòåëüñòâî íåîáõîäèìîñòè òðåáóåò óæå èçðÿäíîé èçîáðåòàòåëüíîñòè.Äîêàçàòåëüñòâî íåîáõîäèìîñòè.n. Ïðè n = 1 óòâåðæäåíèå î÷åâèäíî.k ≤ n, è ðàññìîòðèì ìàòðèöó A, â êîòîðîéÏðîâåäåì èíäóêöèþ ïîÏðåäïîëîæèì, ÷òî îíî äîêàçàíî äëÿ ëþáûõ ìàòðèö ïîðÿäêàêàæäûé ÷ëåí îïðåäåëèòåëÿ ñîäåðæèò íóëåâîé ýëåìåíò ìàòðèöû. Åñëè âñå åå ýëåìåíòû ðàâíû íóëþ, òîóòâåðæäåíèå óæå äîêàçàíî. Ïóñòü èìååòñÿ õîòÿ áû îäèí íåíóëåâîé ýëåìåíò.
Ïóñòüa11A=ïðè÷åì ëþáîé ÷ëåí îïðåäåëèòåëÿ ìàòðèöûïðåäïîëîæåíèþ, âk + l > n,BBa1n 6= 0.Òîãäà... a1 n−1a1na2n ,... annBîáÿçàí ñîäåðæàòü íóëåâîé ìíîæèòåëü. Ïî èíäóêòèâíîìóèìååòñÿ íóëåâàÿ ïîäìàòðèöà0k×lðàçìåðîâk×lñ óñëîâèåìk + l > n − 1.Åñëèòî ýòà ïîäìàòðèöà ÿâëÿåòñÿ èñêîìîé.Îñòàåòñÿ ðàññìîòðåòü ñëó÷àék + l = n.Íå îãðàíè÷èâàÿ îáùíîñòè, ïðåäïîëîæèì, ÷òîA110k×lA=ÏîäìàòðèöûA11èA22êâàäðàòíûå ïîðÿäêàlèk,èìååò âèäA12.A22ñîîòâåòñòâåííî.  ñèëó èñõîäíîãî ïðåäïîëîäåíèÿA11 íåíóëåâîé, òî âñå ÷ëåíû îïðåäåëèòåëÿ A22A22 èìååòñÿ íóëåâàÿ r × s-ïîäìàòðèöà ñ óñëîâèåìr +s > k . Íå îãðàíè÷èâàÿ îáùíîñòè, ïðåäïîëîäèì, ÷òî îíà íàõîäèñÿ íà ïîñëåäíèõ r ñòðîêàõ è ñòîëáöàõñ íîìåðàìè îò l + 1 äî l + s.
Ðàññìîòðèì ïîäìàòðèöó Z íà ïåðåñå÷åíèè ïîñëåäíèõ p = r ñòðîê è q = l + sè ñòîëáöîâ. Ëåãêî âèäåòü, ÷òî Z = 0, ïðè ýòîì p + q = l + r + s > l + k = n.Åñëè âñå ÷ëåíû îïðåäåëèòåëÿ A11 ðàâíû íóëþ, òî èíäóêòèâíîå ïðåäïîëîæåíèå ìîæíî ïðèìåíèòüíåïîñðåäñòâåííî ê A11 . Èñêîìàÿ íóëåâàÿ ïîäìàòðèöà â A ñòðîèòñÿ àíàëîãè÷íûì îáðàçîì.2î ìàòðèöåA,Aåñëè õîòÿ áû îäèí ÷ëåí îïðåäåëèòåëÿðàâíû íóëþ. Ïî èíäóêòèâíîìó ïðåäïîëîæåíèþ, âÇàìåòèì, ÷òî òåîðåìà Õîëëà ïîÿâèëàñü â 1935 ãîäó â ñâÿçè ñ èçó÷åíèåì ñïåöèàëüíûõ êîìáèíàòîðíûõ çàäà÷ (à èìåííî, çàäà÷è î ïàðîñî÷åòàíèÿõ).Äîïîëíåíèå ê ëåêöèè 645.1Ìàòðèöû ñ äèàãîíàëüíûì ïðåîáëàäàíèåìÎòìåòèì ïîëåçíîå äîñòàòî÷íîå óñëîâèå îáðàòèìîñòè ìàòðèöû.
Ïóñòü äëÿ ýëåìåíòîâìàòðèöû A = [aij ] ïîðÿäêà n âûïîëíÿþòñÿ ñîîòíîøåíèÿX|aii | >|aij |,i = 1, 2 . . . , n.1≤j≤nj6=i òàêèõ ñëó÷àÿõ A íàçûâàåòñÿ ìàòðèöåé ñ äèàãîíàëüíûì ïðåîáëàäàíèåì ïî ñòðîêàì.Åñëè èìåþò ìåñòî ñîîòíîøåíèÿX|ajj | >|aij |,j = 1, 2 . . . , n,1≤i≤ni6=jòî A íàçûâàåòñÿ ìàòðèöåé ñ äèàãîíàëüíûì ïðåîáëàäàíèåì ïî ñòîëáöàì.Òåîðåìà. Ëþáàÿ ìàòðèöà ñ äèàãîíàëüíûì ïðåîáëàäàíèåì ïî ñòðîêàì èëè ïî ñòîëáöàì ÿâëÿåòñÿ îáðàòèìîé.Äîêàçàòåëüñòâî.
Ïóñòü A ìàòðèöà ñ äèàãîíàëüíûì ïðåîáëàäàíèåì ïî ñòðîêàì. Äîêàæåì, ÷òî åå ñòîëáöû ëèíåéíî íåçàâèñèìû. Äëÿ ýòîãî ïðèðàâíÿåì íóëþ èõ ëèíåéíóþêîìáèíàöèþ ñ êîýôôèöèåíòàìè x1 , . . . , xn :x1A . . . = 0.xnÂûáåðåì ñòðîêó ñ íîìåðîì i òàêèì, ÷òî |xi | ≥ |xj | äëÿ âñåõ j . ÒîãäàXX|aij | |xi |.aij xj ≥ |aii | −0 = aii xi +1≤j≤n1≤j≤nj6=ij6=iÏîñêîëüêó âåëè÷èíà â ñêîáêàõ ïîëîæèòåëüíàÿ, ïîëó÷àåì xi = 0 ⇒ xj = 0 ∀ j . Îáðàòèìîñòü ìàòðèöû ñ äèàãîíàëüíûì ïðåîáëàäàíèåì ïî ñòîëáöàì äîêàçûâàåòñÿ ñ ïîìîùüþïåðåõîäà ê òðàíñïîíèðîâàííîé ìàòðèöå. 245.2Îïðåäåëèòåëü è âîçìóùåíèÿÌîæíî äîêàçàòü, ÷òî åñëè îïðåäåëèòåëü ìàòðèöû îòëè÷åí îò íóëÿ, òî ïðè âñåõ äîñòàòî÷íî ìàëûõ èçìåíåíèÿõ (â ìàòåìàòèêå ÷àñòî ãîâîðÿò âîçìóùåíèÿõ) ýëåìåíòîâ281282Ëåêöèÿ 45ìàòðèöû îïðåäåëèòåëü íå ñòàíåò íóëåì.Çàäà÷à.Äîêàæèòå, ÷òîïî ìîäóëþ ìåíüøådet(I + F ) 6= 0,åñëè êàæäûé ýëåìåíò ìàòðèöû-âîçìóùåíèÿFïîðÿäêàn1/n.Îäíàêî, ïî âåëè÷èíå îïðåäåëèòåëÿ òðóäíî ñóäèòü, íàñêîëüêî ìàëû äîëæíû áûòüñîîòâåòñòâóþùèå âîçìóùåíèÿ.
Íàïðèìåð, ðàññìîòðèì äâóõäèàãîíàëüíûå ìàòðèöû ïîðÿäêà n ñ âîçìóùåíèåì ε òîëüêî îäíîãî ýëåìåíòà â ëåâîì íèæíåì óãëó:1A(ε) = 2102..0ε....121.Ïðè ε = 0 èìååì det A(0) = 1.  îáùåì ñëó÷àå, ïðèìåíÿÿ òåîðåìó Ëàïëàñà äëÿ ðàçëîæåíèÿ îïðåäåëèòåëÿ ïî ïåðâîìó ñòîëáöó, íàõîäèìdet A(ε) = 1 + ε · (−1)n+1 2n−1 .Ïðè ε = (−1)n /2n−1 ïîëó÷àåì det A(ε) = 0. Ïóñòü, íàïðèìåð, n = 100. Êàê âèäèì,íåâûðîæäåííàÿ ìàòðèöà ñ îïðåäåëèòåëåì 1 ïðåâðàùàåòñÿ â âûðîæäåííóþ ïðè âåñüìàìàëîì âîçìóùåíèè!Äîïîëíåíèå ê ëåêöèè 846.1Âûáîð âåäóùåãî ýëåìåíòàÍåíóëåâûå ýëåìåíòû â ñòðîêàõ, ñ ïîìîùüþ êîòîðûõ ïðîâîäèòñÿ èñêëþ÷åíèå ýëåìåíòîâ,ïðèíÿòî íàçûâàòü âåäóùèìè ýëåìåíòàìè. Ñ òåîðåòè÷åñêîé òî÷êè çðåíèÿ âàæíî òîëüêîòî, ÷òî âåäóùèé ýëåìåíò íå ðàâåí íóëþ.Ñ òî÷êè çðåíèÿ ïðàêòè÷åñêèõ âû÷èñëåíèé ýòîãî ìàëî.
Äåëî â òîì, ÷òî êîìïüþòåðîïåðèðóåò ñ êîíå÷íûì íàáîðîì âåùåñòâåííûõ ÷èñåë òàê íàçûâàåìûõ ìàøèííûõ ÷èñåë. Ïðè èñïîëüçîâàíèè p-è÷íîé ñèñòåìû ñ÷èñëåíèÿ ëþáîå âåùåñòâåííîå ÷èñëî ìîæíîçàïèñàòü â âèäåx = pα · β, 0 ≤ β < 1,(∗)ãäå α öåëîå ÷èñëî íàçûâàåìîå ïîðÿäêîì ÷èñëà x, à β âåùåñòâåííîå ÷èñëî, íàçûâàåìîå ìàíòèññîé ÷èñëà x (êîíå÷íî, ïîðÿäîê è ìàíòèññà äëÿ x çàâèñÿò îò p).
1 Íàêîìïüþòåðå äëÿ ïðåäñòàâëåíèÿ ïîðÿäêà è ìàíòèññû îòâîäèòñÿ ëèøü êîíå÷íîå ÷èñëîðàçðÿäîâ. Ïîýòîìó ïðè âûïîëíåíèè îïåðàöèé ñ ìàøèííûìè ÷èñëàìè ïðèõîäèòñÿ äåëàòü îêðóãëåíèå çàìåíó òî÷íîãî ðåçóëüòàòà êàêèì-òî áëèçêèì ìàøèííûì ÷èñëîì.Ïðåäïîëîæèì, íàïðèìåð, ÷òî ìàíòèññà èìååò t = 5 ðàçðÿäîâ.
Òîãäà ïðè ñëîæåíèè ÷èñåë a = 102 ·0.11111 è b = 10−4 ·0.11111 ñíà÷àëà âûðàâíèâàþòñÿ ïîðÿäêè ýòî îçíà÷àåòèçìåíåíèå ìàíòèññû ÷èñëà ñ ìåíüøèì ïîðÿäêîì è ïîòåðþ çíàêîâ, îêàçàâøèõñÿ çà ïðåäåëàìè îòâåäåííûõ äëÿ ïðåäñòàâëåíèÿ ìàíòèññ ðàçðÿäîâ:10−4 · 0.11111 = 102 · 0.00000011111 7→ 102 · 0.00000.Äàëåå ìîäèôèöèðîâàííûå ìàíòèññû ñêëàäûâàòñÿ, ïîñëå ÷åãî ðåçóëüòàò ïðèâîäèòñÿ êâèäó (∗).  äàííîì ñëó÷àå102 · 0.11111 + 102 · 0.00000 = 102 · 0.11111.Êàê âèäèì, ñóììà ïîëîæèòåëüíûõ ÷èñåë a è b îêàçàëàñü ðàâíîé a!Ïóñòü íà ýòîì æå êîìïüþòåðå ðåøàåòñÿ ñèñòåìà −5 101 x2=.11 y1Ëåãêî âèäåòü, ÷òî òî÷íîå ðåøåíèå èìååò âèäx=1 Îáû÷íîp = 2,−1,1 − 10−5y=íî åñòü è êîìïüòåð, äëÿ êîòîðîãîÌîñêîâñêîì óíèâåðñèòåòå â 1960x ãîäàõ.2832 − 10−5.1 − 10−5p = 3(1) ýòî ÝÂÌ Ñåòóíü, ðàçðàáîòàííàÿ â284Ëåêöèÿ 46 òî æå âðåìÿ, ïðè èñêëþ÷åíèè ýëåìåíòà â ïîçèöèè (2, 1) ïîëó÷àåì −5 −510 10−5 1101101=7→,−105 11101 − 1050−105òàê êàê1 − 105 = 101 · 0.10000 − 106 · 0.10000 = 106 · 0.000001 − 106 · 0.100007→ 106 · 0.00000 − 106 · 0.10000 = −105 .Àíàëîãè÷íî, ïðè ñîîòâåòñòâóþùåì ïðåîáðàçîâàíèè ïðàâîé ÷àñòè íàõîäèì 10 227→.−105 1 1−2 · 105 èòîãå âû÷èñëåííîå ðåøåíèå x̃, ỹ áóäåò òî÷íûì ðåøåíèåì ñèñòåìû −5 101x̃2=.0−105 ỹ−2 · 105Òàêèì îáðàçîì,x̃ = 0,ỹ = 2.(2)Ñðàâíèâàÿ (1) è (2), ïðèõîäèì ê î÷åâèäíîìó âûâîäó: ïîëó÷åííûé îòâåò äàëåê îò èñòèííîãî.Ïðè÷èíà ÷óäîâèùíî áîëüøîé ïîãðåøíîñòè â îòíîñèòåëüíî ìàëîé âåëè÷èíå âåäóùåãî ýëåìåíòà, ïðèâîäÿùåé ê ðîñòó ýëåìåíòîâ â ïðåîáðàçîâàííîé ìàòðèöå.
×òîáûñíèçèòü íåïðèÿòíûé ýôôåêò, âûçâàííûé ðîñòîì ýëåìåíòîâ, îáû÷íî ðåêîìåíäóåòñÿ âêàæäîì ñòîëáöå âûáèðàòü â êà÷åñòâå âåäóùåãî ýëåìåíò, ìàêñèìàëüíûé ïî ìîäóëþ.Çàäà÷à.A = [aij ]Äàíà ìàòðèöàïîðÿäêànñ äèàãîíàëüíûì ïðåîáëàäàíèåì (ñì. ðàçäåë 6.9) ïîñòðîêàì (ïî ñòîëáöàì), è ïóñòü ïîñëå èñêëþ÷åíèÿ ýëåìåíòîâ â ïåðâîì ñòîëáöå ñ ïîìîùüþ ïåðâîéñòðîêè ñ âåäóùèì ýëåìåíòîìa11 6= 0ïîëó÷àåòñÿ ìàòðèöàa11 0 ...0Äîêàæèòå, ÷òî ìàòðèöàBïîðÿäêàa12... a1nB.n−1 òàêæå èìååò äèàãîíàëüíîå ïðåîáëàäàíèå ïî ñòðîêàì (ïî ñòîëáB íå áîëüøå ìàêñèìàëüíîãîöàì). Äîêàæèòå òàêæå, ÷òî ìàêñèìàëüíûé ïî ìîäóëþ ýëåìåíò ìàòðèöûïî ìîäóëþ ýëåìåíòà ìàòðèöû46.2A.Âû÷èñëåíèå îáðàòíîé ìàòðèöûÎáðàòíóþ ìàòðèöó ìîæíî âû÷èñëèòü, èñïîëüçóÿ êîíñòðóêöèè òîãî æå ìåòîäà Ãàóññà.
Åñëè ïîëó÷åíîðàçëîæåíèåA = LU ,òî, ïîñêîëüêóA−1 = U −1 L−1 ,äîñòàòî÷íî íàó÷èòüñÿ âû÷èñëÿòü îáðàòíûå êâåðõíåé è íèæíåé òðåóãîëüíûì ìàòðèöàì. Îáùåå ÷èñëî àðèôìåòè÷åñêèõ îïåðàöèé áóäåòO(n3 ).Îäíàêî, â 1965 ãîäó ïîÿâèëàñü ðàáîòà Øòðàññåíà ñ çàãîëîâêîì Ìåòîä Ãàóññà íå îïòèìàëåí, âêîòîðîé âïåðâûå áûëî ïîêàçàíî, ÷òî ñóùåñòâóþò è áîëåå áûñòðûå àëãîðèòìû. Ïóñòü èìååòñÿ àëãîðèòì≤ c nγ (íàïðèìåð, â äîïîëíèòåëüíîé ÷àñòè Ëåêöèè1 îáñóæäàåòñÿ àëãîðèòì Øòðàññåíà, äëÿ êîòîðîãî γ = log2 7 < 3). Òîãäà â ñëó÷àå ñòðîãî ðåãóëÿðíîé−1γìàòðèöû A ìîæíî ïîñòðîèòü àëãîðèòì âû÷èñëåíèÿ Añ ÷èñëîì îïåðàöèé O(n ).pÄëÿ ïðîñòîòû ïðåäïîëîæèì, ÷òî n = 2 .
Ðàçîáüåì A íà áëîêè ïîðÿäêà n/2 è ðàññìîòðèì ñëåäóþùååóìíîæåíèÿ äâóõn × n-ìàòðèöc ÷èñëîì îïåðàöèéðàâåíñòâî:I−A21 A−1110IA11A21A12A22=A110A12W,W = A22 − A21 A−111 A12 .Å. Å. ÒûðòûøíèêîâÈç íåâûðîæäåííîñòèâèäíî) èWAè285A11âûòåêàåò íåâûðîæäåííîñòü áëîêàW . Áîëåå òîãî, áëîêè A11 (÷òîA. Íåòðóäíî ïðîâåðèòü, ÷òîî÷å-(äîêàæèòå!) íàñëåäóþò ñòðîãóþ ðåãóëÿðíîñòü ìàòðèöûA110Òàêèì îáðàçîì,−1AÏîëó÷åííûå èç(∗)A12WA−1110=−1=A−1110−1−A−111 A12 W−1Wâûðàæåíèÿ äëÿ áëîêîâ ìàòðèöûÄëÿ íàøåé öåëè ôîðìóëà(∗)−1−A−111 A12 W−1W0II−A21 A−111A−1.èíîãäà íàçûâàþò.(∗)ôîðìóëàìè Ôðîáåíèóñà.nn/2. Äëÿ ðåàëèçàöèè óêàçàííîéïîðÿäêà n/2. Îáùèå çàòðàòû íà âñåõèíòåðåñíà òåì, ÷òî ïîêàçûâàåò, êàê îáðàùåíèå ìàòðèöû ïîðÿäêàñâîäèòñÿ ê äâóì àíàëîãè÷íûì çàäà÷àì äëÿ ìàòðèöA11èWïîðÿäêàðåäóêöèè òðåáóåòñÿ âûïîëíèòü íåñêîëüêî óìíîæåíèé ìàòðèöøàãàõ ðåäóêöèè ïðîïîðöèîíàëüíû n γ2+2 n γ22+ 22 n γ23+ ...≤nγ1nγ=.2γ 1 − 1/2γ2γ − 1Âñëåä çà îòêðûòèåì Øòðàññåíà ïîÿâèëàñü ðàáîòà äðóãèõ àâòîðîâ ïîä íàçâàíèåì Ìåòîä Øòðàññåíàíå îïòèìàëåí.
Íî ëèäåðñòâî íîâîãî àëãîðèòìà áûëî íå î÷åíü äîëãèì. Ñîðåâíîâàíèå ïî ïîñòðîåíèþâñå áîëåå áûñòðûõ àëãîðèòìîâ îáðàùåíèÿ ìàòðèö è ðåøåíèÿ ñèñòåì ïðîäîëæàåòñÿ äî ñèõ ïîð, à âîïðîñîá îïòèìàëüíîì àëãîðèòìå ñ òî÷êè çðåíèÿ ÷èñëà îïåðàöèé îñòàåòñÿ îòêðûòûì.Åùå ìåíåå ÿñíûì ÿâëÿåòñÿ âîïðîñ îá àëãîðèòìå ñ ìèíèìàëüíûì ÷èñëîì ïàðàëëåëüíûõ øàãîâ (õîòÿáû â ìîäåëè áåñêîíå÷íîãî ïàðàëëåëèçìà).
Äîâîëüíî äàâíî áûë ïðèäóìàí àëãîðèòì, â êîòîðîì ÷èñëîïàðàëëåëüíûõ øàãîâ â ñëó÷àå ìàòðèöû îáùåãî âèäà åñòüO(log22 n). Íèêòî íå çíàåò, ìîæíî ëè ïîñòðîèòüáîëåå áûñòðûé ïàðàëëåëüíûé àëãîðèòì. Ëþáîïûòíî, ÷òî ïðåäúÿâëåííûé àëãîðèòì íå èìååò íè÷åãîîáùåãî íè ñ ìåòîäîì Ãàóññà, íè ñ ìåòîäîì Øòðàññåíà. Êðîìå òîãî, äàæå äëÿ òðåóãîëüíîé ìàòðèöû íåèçâåñòíî àëãîðèòìà ñ ìåíüøèì ÷èñëîì ïàðàëëåëüíûõ øàãîâ (ïî ïîðÿäêó çàâèñèìîñòè îòÇàäà÷à.çàO(nlog2 7 )Äîêàæèòå, ÷òî îïðåäåëèòåëü ñòðîãî ðåãóëÿðíîé ìàòðèöû ïîðÿäêààðèôìåòè÷åñêèõ îïåðàöèé.nn).ìîæíî âû÷èñëèòü286Ëåêöèÿ 46Äîïîëíåíèå ê ëåêöèè 1347.1Àôôèííàÿ íåçàâèñèìîñòüÒî÷êè v0 , v1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
