Е.Е. Тыртышников - Матричный анализ и линейная алгебра (1112313), страница 14
Текст из файла (страница 14)
. + 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 äîëæíà áûòü íåâûðîæäåííîé. Ìàòðèöà A, âêîòîðîé âñå ïîäìàòðèöû Ak íåâûðîæäåííûå, íàçûâàåòñÿ ñòðîãî ðåãóëÿðíîé.Òàêèì îáðàçîì, äëÿ ñóùåñòâîâàíèÿ LU -ðàçëîæåíèÿ íåâûðîæäåííîé ìàòðèöû Aíåîáõîäèìî, ÷òîáû îíà áûëà ñòðîãî ðåãóëÿðíîé.Ìîæíî äîêàçàòü, ÷òî ýòî óñëîâèå ÿâëÿåòñÿ òàêæå è äîñòàòî÷íûì.  ñàìîì äåëå,ïóñòü óæå ïîñòðîåíî LU -ðàçëîæåíèå äëÿ ïîäìàòðèöû Ak = Lk Uk .
Òîãäà Ak PL−10Uk Lk−1 Pkek − QA−1 P.=,W =A(#)ke−QA−1I0WQAkkÁëîê W íàçûâàåòñÿ äîïîëíåíèåì ïî Øóðó áëîêà Ak â ìàòðèöå A. Èç ðàâåíñòâà (#)è ñòðîãîé ðåãóëÿðíîñòè A ìîæíî âûâåñòè, ÷òî W ÿâëÿåòñÿ òàêæå ñòðîãî ðåãóëÿðíîéek Uek . Òîãäàìàòðèöåé. Ïðåäïîëîæèì, ÷òî äëÿ W óæå ïîñòðîåíî LU -ðàçëîæåíèå W = LïîëîæèìI 0Uk L−1Lk0k PL=U=.ek ,ek−QA−10 L0Uk Lk IÏîëó÷åííàÿ òàêèì îáðàçîì ìàòðèöà L âåðõíÿÿ òðåóãîëüíàÿ. Ðàâåíñòâî LU = A ïðîâåðÿåòñÿ ïðÿìûì âû÷èñëåíèåì.Çàäà÷à.ÏóñòüA íåâûðîæäåííàÿ ìàòðèöà ïîðÿäêànèA(I, J) åå íåâûðîæäåííàÿ ïîäìàòI = (i1 , . . . , ik ) è J = (j1 , .
. . , jk ),ðèöà íà ñòðîêàõ è ñòîëáöàõ, îïðåäåëåííûõ ñèñòåìàìè íîìåðîâñîîòâåòñòâåííî. Ïóñòük < n,àI0èJ0 äîïîëíèòåëüíûå ñèñòåìû íîìåðîâ. Äîêàçàòü, ÷òîdet A−1 (I 0 , J 0 ) = (−1)i1 +...+ik +j1 +...+jk det A(I, J)/ det A.Ëåêöèÿ 99.1Ìåòîä êîîðäèíàòÍàøèì èññëåäîâàíèÿì ëèíåéíîé çàâèñèìîñòè è ëèíåéíûõ îáîëî÷åê âåêòîðîâ (ìàòðèöñòîëáöîâ) ìîæíî äàòü íàãëÿäíóþ ãåîìåòðè÷åñêóþ èíòåðïðåòàöèþ. Êàê ñêîðî âûÿñíèòñÿ, îïðåäåëèòåëü òàêæå èìååò çàìå÷àòåëüíûé ãåîìåòðè÷åñêèé ñìûñë. Îñîáåííî âàæíîòî, ÷òî àëãåáðàèçàöèÿ ãåîìåòðè÷åñêèõ ïîíÿòèé äàåò ìîùíûé àëãåáðàè÷åñêèé èíñòðóìåíò äëÿ ðåøåíèÿ çàäà÷ ãåîìåòðèè.Ê îñíîâíûì îáúåêòàì ãåîìåòðèè îòíîñÿòñÿ òî÷êè, ïðÿìûå è ïëîñêîñòè â ãåîìåòðè÷åñêîì ïðîñòðàíñòâå. Åñëè A è B òî÷êè ïðÿìîé, òî ïóñòü [AB] îáîçíà÷àåò îòðåçîêïðÿìîé ìíîæåñòâî òî÷åê äàííîé ïðÿìîé, ðàñïîëîæåííûõ ìåæäó òî÷êàìè A è B ; |AB| äëèíà îòðåçêà [AB].Áóäåì îïèðàòüñÿ íà òî, ÷òî ìåæäó âåùåñòâåííûìè ÷èñëàìè è òî÷êàìè ïðÿìîé ñóùåñòâóåò âçàèìíî-îäíîçíà÷íîå ñîîòâåòñòâèå x ↔ P (x), êîòîðîå ïîëíîñòüþ îïðåäåëÿåòñÿçàäàíèåì äâóõ òî÷åê P (0), P (1) è îáëàäàåò ñëåäóþùèìè ñâîéñòâàìè:• åñëè x 6= 0 è òî÷êè P (x) è P (1) íàõîäÿòñÿ ïî îäíó ñòîðîíó îò òî÷êè P (0), òî x > 0;â ïðîòèâíîì ñëó÷àå x < 0;• |P (0)P (x)| = |x| |P (0)P (1)|.Ïðÿìóþ, äëÿ êîòîðîé óñòàíîâëåíî óêàçàííîå ñîîòâåòñòâèå, áóäåì íàçûâàòü ÷èñëîâîéîñüþ, à ÷èñëî x êîîðäèíàòîé òî÷êè P (x).Çàìåòèì, ÷òî ïðè âûáîðå ïðîèçâîëüíîãî âåùåñòâåííîãî ÷èñëà a ñîîòâåòñòâèå x ↔P (x + a) áóäåò òàêæå âçàèìíî-îäíîçíà÷íûì.
Ýòî ïîçâîëÿåò ïåðåíîñèòü òî÷êó P (0) âëþáóþ çàäàííóþ òî÷êó äàííîé ïðÿìîé.Ðàññìîòðèì ïðÿìûå l1 , l2 , l3 , ïðîõîäÿùèå ÷åðåç îáùóþ òî÷êó O è íå ëåæàùèå â îäíîéïëîñêîñòè. Ïóñòü êàæäàÿ èç ýòèõ ïðÿìûõ ÿâëÿåòñÿ ÷èñëîâîé îñüþ ñ ñîîòâåòñòâèÿìèx ↔ P1 (x),y ↔ P2 (y),z ↔ P3 (z),äàþùèìè îáùóþ òî÷êó P1 (0) = P2 (0) = P3 (0) = O. Ïóñòü (x, y, z) ñèñòåìà òðåõâåùåñòâåííûõ ÷èñåë, îïðåäåëÿþùèõ òî÷êè X = P1 (x), Y = P2 (y), Z = P3 (z) íà ïðÿìûõl1 , l2 , lz , ñîîòâåòñòâåííî.
Ðàññìîòðèì òðè ïëîñêîñòè:• π1 ïëîñêîñòü, ïðîõîäÿùàÿ ÷åðåç òî÷êó X ïàðàëëåëüíî ïðÿìûì l2 è l3 ;• π2 ïëîñêîñòü, ïðîõîäÿùàÿ ÷åðåç òî÷êó Y ïàðàëëåëüíî ïðÿìûì l1 è l3 ;• π3 ïëîñêîñòü, ïðîõîäÿùàÿ ÷åðåç òî÷êó Z ïàðàëëåëüíî ïðÿìûì l1 è l2 .5556Ëåêöèÿ 9Ëåãêî âèäåòü, ÷òî ïëîñêîñòè π1 , π2 , π3 ïåðåñåêàþòñÿ â îäíîé òî÷êå M = M (x, y, z).Òàêèì îáðàçîì óñòàíàâëèâàåòñÿ âçàèìíî-îäíîçíà÷íîå ñîîòâåòñòâèå(x, y, z) ↔ M (x, y, z).Òî÷êè X, Y, Z íàçûâàþòñÿ ïðîåêöèÿìè òî÷êè M íà ïðÿìûå l1 , l2 , l3 ïàðàëëåëüíî ïëîñêîñòÿì, ñîîòâåòñòâåííî, π1 , π2 , π3 .
×èñëà x, y, z íàçûâàþòñÿ êîîðäèíàòàìè òî÷êè M =M (x, y, z), à ñèñòåìà ÷èñëîâûõ îñåé l1 , l2 , l3 àôôèííîé ñèñòåìîé êîîðäèíàò. Òî÷êàO íàçûâàåòñÿ íà÷àëîì (èëè öåíòðîì) ñèñòåìû êîîðäèíàò.Ýïèòåò àôôèííàÿ ïî îòíîøåíèþ ê ñèñòåìå êîîðäèíàò îçíà÷àåò òîëüêî òî, ÷òî óãëûìåæäó îñÿìè ìîãóò íå áûòü ïðÿìûìè, à äëèíû îòðåçêîâ [OP1 (1)], [OP2 (1)], [OP3 (1)] íåîáÿçàòåëüíî ðàâíûå. Åñëè óãëû ìåæäó îñÿìè ïðÿìûå, à äëèíû óêàçàííûõ îòðåçêîâðàâíû 1, òî ñèñòåìà êîîðäèíàò íàçûâàåòñÿ äåêàðòîâîé.9.2Íàïðàâëåííûå îòðåçêèËþáóþ óïîðÿäî÷åííóþ ïàðó òî÷åê A, B áóäåì íàçûâàòü íàïðàâëåííûì îòðåçêîì ñ íà−→÷àëîì â òî÷êå A è êîíöîì â òî÷êå B .
Îáîçíà÷åíèå: AB .Åñëè èìååòñÿ ñèñòåìà êîîðäèíàò ñ íà÷àëîì â òî÷êå O, òî íàïðàâëåííûé îòðåçîê−→âèäà OA íàçûâàåòñÿ ðàäèóñ-âåêòîðîì òî÷êè A. Êîîðäèíàòû òî÷êè A íàçûâàþòñÿ òàêæå−→êîîðäèíàòàìè ðàäèóñ-âåêòîðà OA.Òî÷êà A 6= B ðàçáèâàåò ïðÿìóþ AB íà äâà ëó÷à: ëó÷ [AB), ñîñòîÿùèé èç òî÷åêäàííîé ïðÿìîé, ëåæàùèõ âìåñòå ñ B ïî îäíó ñòîðîíó îò A è äîïîëíèòåëüíûé ëó÷,ñîñòîÿùèé èç òî÷åê, ëåæàùèõ ïî äðóãóþ ñòîðîíó (òî÷êà A äëÿ äâóõ ëó÷åé ÿâëÿåòñÿ îáùåé). Äâà ëó÷à íà îäíîé ïðÿìîé íàçûâàþòñÿ îäèíàêîâî íàïðàâëåííûìè, åñëè èõïåðåñå÷åíèå ÿâëÿåòñÿ ëó÷îì (è ïðîòèâîïîëîæíî íàïðàâëåííûìè, åñëè èõ ïåðåñå÷åíèåÿâëÿåòñÿ îòðåçêîì).
Åñëè ïðÿìûå AB è CD íå ñîâïàäàþò, òî ëó÷è [AB) è [CD) íàçûâàþòñÿ îäèíàêîâî íàïðàâëåííûìè, åñëè ýòè ïðÿìûå ïàðàëëåëüíû è òî÷êè B è D ëåæàòïî îäíó ñòîðîíó îò ïðÿìîé AC .−→Ïðåäïîëîæèì, ÷òî A 6= B , ðàññìîòðèì îòðåçîê AB , è ïóñòü C ïðîèçâîëüíàÿòî÷êà. Ïðîâåäåì ÷åðåç C ïðÿìóþ, ïàðàëëåëüíóþ ïðÿìîé AB èëè ñîâïàäàþùóþ ñ íåéâ ñëó÷àå C ∈ AB . Íà ýòîé ïðÿìîé ìîæíî íàéòè ðîâíî äâå òî÷êè D1 è D2 òàêèå, ÷òî|CD1 | = |CD2 | = |AB|. Âûáåðåì èç íèõ òàêóþ òî÷êó D ∈ {D1 , D2 }, äëÿ êîòîðîé ëó÷è−→[AB) è [CD) îäèíàêîâî íàïðàâëåíû. Íàïðàâëåííûé îòðåçîê CD áóäåì ñ÷èòàòü ðàâíûì−→−→−→AB . (×àñòî ãîâîðÿò òàêæå, ÷òî CD ïîëó÷àåòñÿ èç AB ïàðàëëåëüíûì ïåðåíîñîì.)−→−→Äàííûì ïîñòðîåíèåì íå îõâà÷åí ñëó÷àé A = B .
Íàïðàâëåííûå îòðåçêè AA è CCáóäåì ñ÷èòàòü ðàâíûìè ïî îïðåäåëåíèþ è íàçûâàòü èõ íóëåâûìè.−→−→Îòìåòèì ôîðìàëüíóþ íåñèììåòðè÷íîñòü â äàííîì îïðåäåëåíèè: CD ðàâåí AB ,−→−→íî áóäåò ëè AB ðàâåí CD? Îòâåò, ê ñ÷àñòüþ, ïîëîæèòåëüíûé â ñèëó òîãî, ÷òî−→−→íàïðàâëåííûé îòðåçîê AB ïîëó÷àåòñÿ èç CD ñ ïîìîùüþ òî÷íî òàêîé æå êîíñòðóêöèè.Çàìåòèì, ÷òî âñå ñëó÷àè ïðè îïðåäåëåíèè ðàâåíñòâà íàïðàâëåííûõ îòðåçêîâ ìîæíî ñâåñòè ê îäíîìó ñëó÷àþ, åñëè ïðèíÿòü ôîðìàëüíî äðóãîå (è ïðèòîì ñèììåòðè÷−→−→íîå) îïðåäåëåíèå: íàçîâåì íàïðàâëåííûå îòðåçêè AB è CD ðàâíûìè, åñëè ñåðåäèíûîòðåçêîâ [AD] è [BC] ñîâïàäàþò. Ýêâèâàëåíòíîñòü íîâîãî îïðåäåëåíèÿ ïðåäûäóùåìóÅ.
Å. Òûðòûøíèêîâ57âûòåêàåò èç îáùåèçâåñòíûõ ñâîéñòâ ïàðàëëåëîãðàììà.Îáðàòèì âíèìàíèå íà òî, ÷òî ïðè ôèêñèðîâàííîé ñèñòåìå êîîðäèíàò ëþáîé íàïðàâëåííûé îòðåçîê ðàâåí íåêîòîðîìó è òîëüêî îäíîìó ðàäèóñ-âåêòîðó.9.3Îòíîøåíèå ýêâèâàëåíòíîñòèËþáîå íåïóñòîå ïîäìíîæåñòâî M ⊂ X × X îïðåäåëÿåò íà ìíîæåñòâå X áèíàðíîå îòíîøåíèå ìåæäó åãî ýëåìåíòàìè:Mx∼y⇔(x, y) ∈ M.X ìíîæåñòâî âñåõ ìàòðèö, M ìíîæåñòâî òàêèõ ïàð ìàòðèö (A, B),äëÿ êîòîðûõ ñóùåñòâóåò ïðîèçâåäåíèå AB . ßñíî, ÷òî èìåþòñÿ ïàðû ìàòðèö, íå âõîäÿMMùèå â M . Êðîìå òîãî, åñëè A ∼ B , òî îòñþäà íå ñëåäóåò, ÷òî B ∼ A.ÏÐÈÌÅÐ.Áèíàðíîå îòíîøåíèå M íà X íàçûâàåòñÿ îòíîøåíèåì ýêâèâàëåíòíîñòè, åñëè âûïîëíÿþòñÿ ñëåäóþùèå òðè ñâîéñòâà:M• x ∼ x äëÿ âñåõ ýëåìåíòîâ x ∈ XMM• åñëè x ∼ y , òî y ∼ xMM(ðåôëåêñèâíîñòü);(ñèììåòðè÷íîñòü);M• åñëè x ∼ y è y ∼ z , òî x ∼ z(òðàíçèòèâíîñòü).MÅñëè íà X çàäàíî îòíîøåíèå ýêâèâàëåíòíîñòè M è x ∼ y , òî x è y íàçûâàþòñÿ ýêâèâàëåíòíûìè ýëåìåíòàìè.
Ìíîæåñòâî âñåõ ýëåìåíòîâ èç X , ýêâèâàëåíòíûõ íåêîòîðîìóýëåìåíòó a ∈ X , íàçûâàåòñÿ êëàññîì ýêâèâàëåíòíîñòè, ïîðîæäåííûì ýëåìåíòîì a.Òåîðåìà. Íåïóñòîå ìíîæåñòâî X ñ îòíîøåíèåì ýêâèâàëåíòíîñòè ÿâëÿåòñÿ îáúåäèíåíèåì íåïåðåñåêàþùèõñÿ ïîäìíîæåñòâ, êàæäîå èç êîòîðûõ ñîñòîèò èç ýëåìåíòîâ,ýêâèâàëåíòíûõ ìåæäó ñîáîé è íå ýêâèâàëåíòíûõ íè îäíîìó èç ýëåìåíòîâ äðóãèõ ïîäìíîæåñòâ.Äîêàçàòåëüñòâî.
Ïóñòü X(a) îáîçíà÷àåò êëàññ ýêâèâàëåíòíîñòè, ïîðîæäåííûé ýëå-ìåíòîì a ∈ X . Âûáåðåì ïðîèçâîëüíûé ýëåìåíò x è ðàññìîòðèì åãî êëàññ ýêâèâàëåíòíîñòè X(a). Åñëè b, c ∈ X(a), òî êàæäûé èç íèõ ýêâèâàëåíòåí a, à çíà÷èò, â ñèëó òðàíçèòèâíîñòè, b è c ýêâèâàëåíòíû ìåæäó ñîáîé (b ∼ a, a ∼ c ⇒ b ∼ c). ßñíî òàêæå,÷òî X(b) = X(c) = X(a) (òî åñòü, êëàññ ýêâèâàëåíòíîñòè ïîðîæäàåòñÿ ëþáûì ñâîèìïðåäñòàâèòåëåì).Ïî îïðåäåëåíèþ, X(a) ñîäåðæèò àáñîëþòíî âñå ýëåìåíòû, ýêâèâàëåíòíûå a.
Ïîýòîìó åñëè b ∈/ X(a), òî b íå ÿâëÿåòñÿ ýêâèâàëåíòíûì a. Îòñþäà ñëåäóåò, ÷òî Têëàññûýêâèâàëåíòíîñòè X(a) è X(b) íå ïåðåñåêàþòñÿ: åñëè áû èìåëñÿ ýëåìåíò c ∈ X(a) X(b),òî ýòî áû îçíà÷àëî, ÷òî b ∈ X(a) ⇒ X(a) = X(b).Òàêèì îáðàçîì, äëÿ ïðîèçâîëüíûõ ýëåìåíòîâ a è b êëàññû ýêâèâàëåíòíîñòèX(a)Sè X(b) ëèáî íå ïåðåñåêàþòñÿ, ëèáî ñîâïàäàþò. Î÷åâèäíî, X =X(a). Äëÿ çàâåða∈Xøåíèÿ äîêàçàòåëüñòâà îñòàåòñÿ èñêëþ÷èòü èç ýòîãî îáúåäèíåíèÿ ñîâïàäàþùèå êëàññûýêâèâàëåíòíîñòè.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
