Е.Е. Тыртышников - Матричный анализ и линейная алгебра (1112313), страница 48
Текст из файла (страница 48)
. . , Ak . Ïóñòü P ëþáàÿîáðàòèìàÿ ìàòðèöà, ïåðâûé ñòîëáåö êîòîðîé ðàâåí x. Òîãäà êàæäàÿ èç ìàòðèöP A1 P −1 , . . . , P Ak P −1 èìååò áëî÷íûé âèäλi vi>−1P Ai P =, Bi ∈ C(n−1)×(n−1) .0 BiÍåïîñðåäñòâåííî ïðîâåðÿåòñÿ, ÷òî ìàòðèöû B1 , . . . , Bk êîììóòèðóþò. Åñëè îíè îäíîâðåìåííî ïðèâîäÿòñÿ ê âåðõíåìó òðåóãîëüíîìó âèäó ñ ïîìîùüþ îáðàòèìîé ìàòðèöû ZÅ. Å. Òûðòûøíèêîâ227ïîðÿäêà n − 1 (êàæäàÿ èç ìàòðèö Z −1 Bi Z ÿâëÿåòñÿ âåðõíåé òðåóãîëüíîé), òî ìàòðèöà1 0Q=P0 Zîäíîâðåìåííî ïðèâîäèò ê òðåóãîëüíîìó âèäó êàæäóþ èç ìàòðèö A1 , .
. . , Ak . Òî æåâåðíî è äëÿ ïðîèçâîëüíîé ëèíåéíîé êîìáèíàöèè ìàòðèö A1 , . . . , Ak . 2Çàäà÷à.ìàòðèöûkèPn − k,èÌàòðèöûQAèòàêèå, ÷òîBIP AQ = k0ñîîòâåòñòâåííî, è, êðîìåÇàäà÷à.n êîììóòèðóþò.÷òî ñóùåñòâóþò íåâûðîæäåííûå Äîêàæèòå,0X 0è P BQ =, ãäå áëîêè Ik , X è N, Y èìåþò ïîðÿäîêN0 Yòîãî, ìàòðèöà Ik åäèíè÷íàÿ, à N íèëüïîòåíòíàÿ.ïîðÿäêàA, B ∈ Cn×n det(λA − B) 6= 0.Äîêàæèòå,Ik 0X0÷òî ñóùåñòâóþò íåâûðîæäåííûå ìàòðèöû P è Q òàêèå, ÷òî P AQ =è P BQ =,0 N0 In−kãäå áëîêè Ik , X è N, In−k èìåþò ïîðÿäîê k è n − k , ñîîòâåòñòâåííî, è, êðîìå òîãî, ìàòðèöû Ik è In−kåäèíè÷íûå, à N íèëüïîòåíòíàÿ.Äëÿ ìàòðèöñóùåñòâóåò ÷èñëîλòàêîå, ÷òîÄÎÏÎËÍÈÒÅËÜÍÀß ×ÀÑÒÜ34.5Áûñòðîå ïðåîáðàçîâàíèå ÔóðüåÓìíîæåíèå ìàòðèöû Ôóðüå Fn íà âåêòîð-ñòîëáåö x ∈ Cn íàçûâàåòñÿ ïðÿìûì ïðåîáðàçîâàíèåì Ôóðüå âåêòîðà x.Êëàññè÷åñêîå ïðàâèëî óìíîæåíèÿ ìàòðèöû íà âåêòîð äàåò àëãîðèòì ñ ÷èñëîì îïåðàöèé ïîðÿäêà n2 .
Îäíàêî, ñïåöèàëüíûé âèä ìàòðèöû Fn ïîçâîëÿåò óìíîæàòü åå íàâåêòîð ñ çàòðàòîé ëèøü O(n log2 n) àðèôìåòè÷åñêèõ îïåðàöèé!Àëãîðèòìû ñ òàêèì ñâîéñòâîì (áûñòðîå ïðåîáðàçîâàíèå Ôóðüå) íà÷àëè âíåäðÿòüñÿâ ïðàêòèêó âû÷èñëåíèé â 60-õ ãîäàõ 20-ãî âåêà è ïðîèçâåëè áóêâàëüíî ïåðåâîðîò â ðÿäåðàçäåëîâ ïðèêëàäíîé ìàòåìàòèêè. 2 Òàê èëè èíà÷å, áûñòðîå ïðåîáðàçîâàíèå Ôóðüåñòàëî îñíîâíîé êîìïîíåíòîé ìíîãèõ áûñòðûõ àëãîðèòìîâ â çàäà÷àõ ëèíåéíîé àëãåáðû.Ïðåäïîëîæèì, ÷òî n = 2L è m = n/2. Áóäåì íóìåðîâàòü ñòðîêè è ñòîëáöû ìàòðèöûFn ÷èñëàìè îò 0 äî n − 1. Îò Fn ïåðåéäåì ê ìàòðèöå Fen , â êîòîðîé ñíà÷àëà èäóò ïîäðÿäâñå ñòðîêè Fn ñ ÷åòíûìè íîìåðàìè, à çàòåì âñå ñòðîêè ñ íå÷åòíûìè íîìåðàìè (ÿñíî,÷òî Fen = Pn Fn , ãäå Pn ñîîòâåòñòâóþùàÿ ìàòðèöà ïåðåñòàíîâêè).
Ðàññìîòðèì Fen êàêáëî÷íóþ 2 × 2-ìàòðèöó:"Fen =[ε2 k l ]m×m[ε2 k (m+l) ]m×m[ε(2k+1) l ]m×m[ε(2k+1)(m+l) ]m×m#,0 ≤ k, l ≤ m − 1.Çàìåòèì, ÷òî[ε2 k l ]m×m = [ε2 k (m+l) ]m×m = Fm ,[ε(2k+1) l ]m×m = Fm Dm ,[ε(2k+1)(m+l) ]m×m = −Fm Dm ,2 Íà÷àëî ïåðåâîðîòà îòñ÷èòûâàåòñÿ ñ 1965 ãîäà ñî çíàìåíèòîé ðàáîòû àìåðèêàíöåâ Êóëè èÒüþêè. Âïîñëåäñòâèè áûëî âûÿñíåíî, ÷òî áûñòðûå àëãîðèòìû áûëè îïèñàíû Ðóíãå åùå â íà÷àëå 20-ãîâåêà; áîëåå òîãî, Ã.
Ñòðýíã óòâåðæäàåò, ÷òî îáíàðóæèë èõ ïðîòîòèïû åùå ó Ãàóññà.228Ëåêöèÿ 34ãäåDm 1ε1= ....εm−1Ñëåäîâàòåëüíî,Fn = PnFm 00 FmIm 00 DmIm ImIm −Im,m = n/2.Òàêèì îáðàçîì, çàäà÷à óìíîæåíèÿ ìàòðèöû Fn íà âåêòîð ñâîäèòñÿ ê äâóì àíàëîãè÷íûì çàäà÷àì äëÿ ìàòðèöû Fn/2 . ×òîáû îñóùåñòâèòü ðåäóêöèþ, òðåáóåòñÿ âûïîëíèòü nñëîæåíèé-âû÷èòàíèé è n/2 óìíîæåíèé (íà ýëåìåíòû äèàãîíàëüíîé ìàòðèöû Dn ). Îáîçíà÷èì ÷åðåç S± (n) è S∗ (n) îáùåå ÷èñëî ñëîæåíèé-âû÷èòàíèé è óìíîæåíèé.
×òîáû èõîöåíèòü, íóæíî ïðîñóììèðîâàòü çàòðàòû íà ðåäóêöèþ çàäà÷ äëÿ âñåõ L = log2 n øàãîâðåêóðñèè:S± (n) = n + 2(n/2) + 22 (n/22 ) + . . . + 2L−1 (n/2L−1 ) = nL = n log2 n,S∗ (n) =1n log2 n.2Ëåêöèÿ 3535.1Ñèíãóëÿðíûå ÷èñëà è ñèíãóëÿðíûå âåêòîðûÏóñòü A ∈ Cm×n . Òîãäà A∗ A ∈ Cn×n ýðìèòîâà íåîòðèöàòåëüíî îïðåäåëåííàÿ ìàòðèöà:(A∗ A)∗ = A∗ (A∗ )∗ = A∗ A;xA∗ Ax = (Ax, Ax) = |Ax|2 ≥ 0 ∀ x ∈ Cn .Ïîýòîìó âñå åå ñîáñòâåííûå çíà÷åíèÿ íåîòðèöàòåëüíû.Íåîòðèöàòåëüíûå êâàäðàòíûå êîðíè èç ñîáñòâåííûõ çíà÷åíèé ìàòðèöû A∗ A íàçûâàþòñÿ ñèíãóëÿðíûìè ÷èñëàìè ìàòðèöû A. Ñèíãóëÿðíûå ÷èñëà σi = σi (A) ïðèíÿòîíóìåðîâàòü ïî íåâîçðàñòàíèþ:σ1 ≥ σ2 ≥ .
. . ≥ σr > σr+1 = . . . = σn = 0.Áóäåì ñ÷èòàòü, ÷òî A èìååò r íåíóëåâûõ ñèíãóëÿðíûõ ÷èñåë.Ïóñòü u1 , . . . , un îðòîíîðìèðîâàííûé áàçèñ ñîáñòâåííûõ âåêòîðîâ ìàòðèöû A∗ Aòàêîé, ÷òî 21 ≤ i ≤ r,σi ui ,∗A Aui =0,r + 1 ≤ i ≤ n.Ïîëîæèì vi = Aui /σi , 1 ≤ i ≤ r. Òîãäà (vi , vj ) = 0 ïðè i 6= j è (vi , vi ) = 1. Äîïîëíèìñèñòåìó v1 , .
. . , vr âåêòîðàìè vr+1 , . . . , vm äî îðòîíîðìèðîâàííîãî áàçèñà â Cm . Çàìåòèìòàêæå, ÷òî ïðè j ≥ r + 1A∗ Auj = 0 ⇒ u∗j A∗ Auj = 0 ⇒ (Auj )∗ (Auj ) = 0 ⇒ |Auj | = 0 ⇒ Auj = 0. èòîãå ïîëó÷àåìσ1...A[u1 , . . . , un ] = [v1 , . . . , vm ] σr ⇒ AU = V Σ,ãäå U = [u1 , . . .
, un ] è V = [v1 , . . . , vm ] óíèòàðíûå ìàòðèöû, à Σ äèàãîíàëüíàÿïðÿìîóãîëüíàÿ ìàòðèöà òåõ æå ðàçìåðîâ, ÷òî è ìàòðèöà A.Ñòîëáöû ìàòðèö U è V îáðàçóþò ñèíãóëÿðíûå áàçèñû ìàòðèöû A. Ñòîëáöû U íàçûâàþòñÿ ïðàâûìè ñèíãóëÿðíûìè âåêòîðàìè, à ñòîëáöû V ëåâûìè ñèíãóëÿðíûìèâåêòîðàìè ìàòðèöû A. Ñâÿçü ìåæäó ñèíãóëÿðíûìè âåêòîðàìè è íåíóëåâûìè ñèíãóëÿðíûìè ÷èñëàìè óñòàíàâëèâàåòñÿ ñîîòíîøåíèÿìèAui = σi vi ,A∗ vi = σi ui ,2291 ≤ i ≤ r.230Ëåêöèÿ 35Êðîìå òîãî,A∗ vi = 0, r + 1 ≤ i ≤ m.Aui = 0, r + 1 ≤ i ≤ n,Èòàê, ìû äîêàçàëè, ÷òî äëÿ ëþáîé ìàòðèöû A ∈ Cm×n èìååò ìåñòî ðàâåíñòâîAU = V Σ(∗)äëÿ íåêîòîðûõ óíèòàðíûõ ìàòðèö U ∈ Cn×n , V ∈ Cm×m è äèàãîíàëüíîé ïðÿìîóãîëüíîé ìàòðèöû ðàçìåðîâ m × n ñ ÷èñëàìè σi ≥ 0 ïðè i = j .
Çàïèñàâ (∗) â âèäåA = V ΣU ∗ ,(∗∗)ïîëó÷àåì ïðåäñòàâëåíèå ìàòðèöû, íàçûâàåìîå åå ñèíãóëÿðíûì ðàçëîæåíèåì. 1Åñëè êàêèì-òî ñïîñîáîì ïîëó÷åíî ðàçëîæåíèå (∗∗) ñ óíèòàðíûìè ìàòðèöàìè U èV , òî A∗ A = U (Σ∗ Σ)U ∗ . Ïîýòîìó åñëè Σ äèàãîíàëüíàÿ ïðÿìîóãîëüíàÿ ìàòðèöà ñíåîòðèöàòåëüíûìè ýëåìåíòàìè, òî åå íåíóëåâûå ýëåìåíòû îïðåäåëåíû îäíîçíà÷íî.Çàäà÷à.35.2Íàéäèòå ñèíãóëÿðíîå ðàçëîæåíèå2 × n-ìàòðèöû1 1 ... 1A=.1 1 ... 1Ïîëÿðíîå ðàçëîæåíèåÅñëè m = n, òî ìîæíî çàïèñàòü (∗∗) â âèäåA = (V ΣV ∗ )(V U ∗ ) = HQ,ãäå H = V ΣV ∗ íåîòðèöàòåëüíî îïðåäåëåííàÿ (ïîýòîìó òàêæå ýðìèòîâà) ìàòðèöà, àQ = V U ∗ óíèòàðíàÿ ìàòðèöà (êàê ïðîèçâåäåíèå óíèòàðíûõ ìàòðèö).
Ïðåäñòàâëåíèåìàòðèöû A â âèäå A = HQ ñ íåîòðèöàòåëüíî îïðåäåëåííîé H è óíèòàðíîé Q íàçûâàåòñÿåå ïîëÿðíûì ðàçëîæåíèåì.Ïîëÿðíîå ðàçëîæåíèå ìàòðèöû ìîæíî ñ÷èòàòü àíàëîãîì òðèãîíîìåòðè÷åñêîé ôîðìû êîìïëåêñíîãî ÷èñëà.35.3Âûâîäû èç ñèíãóëÿðíîãî ðàçëîæåíèÿ(1) ×èñëî íåíóëåâûõ ñèíãóëÿðíûõ ÷èñåë r ðàâíî ðàíãó ìàòðèöû A.(2) Ñèíãóëÿðíîå ðàçëîæåíèå ñîïðÿæåííîé ìàòðèöû èìååò âèäA∗ = U Σ > V ∗ .(3) imA = L(v1 , .
. . , vr ),kerA = L(ur+1 , . . . , un ).(4) imA∗ = L(u1 , . . . , ur ),kerA∗ = L(vr+1 , . . . , vm ). êà÷åñòâå ñëåäñòâèÿ ìîæíî ïîëó÷èòü ïðåäñòàâëåíèÿ ïðîñòðàíñòâ â âèäå îðòîãîíàëüíûõ ñóììCn = kerA ⊕ imA∗ , Cm = kerA∗ ⊕ imA.1 Îíî áûëî ïîëó÷åíî ñîâåðøåííî äðóãèì ñïîñîáîì â Ëåêöèè 27.Å. Å. Òûðòûøíèêîâ(5) A =rPσk vk u∗k ,k=1231A∗ =rPσk uk vk∗ .k=1(6) Åñëè m = n = r (ìàòðèöà A íåâûðîæäåííàÿ), òîA=nXσk vk u∗k ,A−1 =k=1nX1uk vk∗ .σkk=1(7) Ïóñòü σ1 ≥ . . . ≥ σn ñèíãóëÿðíûå ÷èñëà íåâûðîæäåííîé ìàòðèöû A.
Òîãäàσn−1 ≥ . . . ≥ σ1−1 ñèíãóëÿðíûå ÷èñëà ìàòðèöû A−1 .p(8) ||A||2 = σ1 , ||A||F = σ12 + . . . + σr2 .Ñïåêòðàëüíàÿ è ôðîáåíèóñîâà íîðìû ÿâëÿþòñÿ óíèòàðíî èíâàðèàíòíûìè. Ïîýòîìó||A||2 = ||Σ||2 è ||A||F = ||Σ||F . Î÷åâèäíî, ||Σx||2 ≤ σ1 ||x||2 ; ðàâåíñòâî äîñòèãàåòñÿ, åñëèx èìååò 1 â ïåðâîé ïîçèöèè èp0 â îñòàëüíûõ.ßñíî òàêæå, ÷òî ||Σ||F = σ12 + . . .
+ σr2 . 2Çàäà÷à.ìàòðèöûÄàíà êâàäðàòíàÿ ìàòðèöà ñ íîðìîéB, C, DÇàäà÷à.òàêèå, ÷òî ìàòðèöàÏóñòüAACBDÄîêàæèòå, ÷òî ñóùåñòâóþò êâàäðàòíûåÿâëÿåòñÿ óíèòàðíîé. êâàäðàòíàÿ ìàòðèöà è÷òî äëÿ ïðîèçâîëüíîé ýðìèòîâîé ìàòðèöû||A||2 ≤ 1.HHA = (A + A∗ )/2 åå ýðìèòîâà ÷àñòü. Äîêàæèòå,òîãî æå ïîðÿäêà èìååò ìåñòî íåðàâåíñòâî||A − HA ||2 ≤||A − H||2 .Çàäà÷à.Äîêàæèòå, ÷òî åñëèH ýðìèòîâà, àU óíèòàðíàÿ ìàòðèöà òîãî æå ïîðÿäêà, òî||H − I||2 ≤ ||H − U ||2 ≤ ||H + I||2 .35.4Ñèíãóëÿðíîå ðàçëîæåíèå è ðåøåíèå ñèñòåìÓòâåðæäåíèå.
Ðåøåíèå ñèñòåìû Ax = b ñ íåâûðîæäåííîé ìàòðèöåé A èìååò âèäx=nPk=1βku ,σk kãäå βk = vk∗ b = (vk , b) êîýôôèöèåíòû ðàçëîæåíèÿ âåêòîðà ïðàâîé ÷àñòèb ïî ñèíãóëÿðíûì âåêòîðàì v1 , . . . , vm .Äîêàçàòåëüñòâî. Âûðàæåíèå äëÿ x ñðàçó æå ïîëó÷àåòñÿ èç (6). Åñëè b = β1 v1 + . . . +βn vn , òî (b, vk ) = βk (vk , vk ) = βk (âñëåäñòâèå îðòîíîðìèðîâàííîñòè ñèñòåìû âåêòîðîâv1 , . .
. , vn ). 2Äàííîå óòâåðæäåíèå ïðîÿñíÿåò ðîëü íàïðàâëåíèÿ âîçìóùåíèé ïðè ðåøåíèè ñèñòåì.Åñëè êîýôôèöèåíò βk çàìåíÿåòñÿ íà βk + ε, òî êîýôôèöèåíò ïðè uk â ðàçëîæåíèè xïî áàçèñó u1 , . . . , un âîçìóùàåòñÿ íà âåëè÷èíó ε/σk . ×åì ìåíüøå σk , òåì ñèëüíåå ìîæåò èçìåíèòüñÿ ðåøåíèå. Ïðè ìàëîì σn îñîáåííî îïàñíû âîçìóùåíèÿ âåêòîðà ïðàâîé÷àñòè b â íàïðàâëåíèè âåêòîðà vn .35.5Ìåòîä íàèìåíüøèõ êâàäðàòîâÅñëè ñèñòåìà Ax = b íåñîâìåñòíà, òî ðàâåíñòâî Ax = b íå âûïîëíÿåòñÿ íè äëÿ îäíîãîâåêòîðà x.  ýòîì ñëó÷àå, òåì íå ìåíåå, ïûòàþòñÿ èíòåðåñîâàòüñÿ òàêèìè x, ïðè êîòîðûõâåêòîð b − Ax (åãî íàçûâàþò íåâÿçêîé äëÿ x) èìååò ìèíèìàëüíî âîçìîæíóþ äëèíó.232Ëåêöèÿ 35Âåêòîð x íàçûâàåòñÿ ïñåâäîðåøåíèåì ñèñòåìû Ax = b, åñëè||b − Ax||2 = min ||b − Az||2 .z äàííîì ìåòîäå îïðåäåëåíèÿ îáîáùåííîãî ðåøåíèÿ â âåùåñòâåííîì ñëó÷àå ðå÷üäåéñòâèòåëüíî èäåò î íàèìåíüøåì çíà÷åíèè ñóììû êâàäðàòîâ (îòñþäà íàçâàíèå ìåòîäà)mX2(bi − ai1 x1 − .
. . − ain xn )2 .||b − Ax||2 =i=1Óòâåðæäåíèå. Ïóñòü A ìàòðèöà ðàçìåðîâ m × n è ðàíãà r. Ìíîæåñòâî ïñåâäîðåøåíèé ñèñòåìû Ax = b åñòü ëèíåéíîå ìíîãîîáðàçèå, ðàçìåðíîñòü êîòîðîãî ðàâíàn − r.Äîêàçàòåëüñòâî. Ïóñòü h ïåðïåíäèêóëÿð, îïóùåííûé èç âåêòîðà b íà ïîäïðîñò-ðàíñòâî imA, à y ∈ imA ñîîòâåòñòâóþùàÿ îðòîãîíàëüíàÿ ïðîåêöèÿ. Òîãäà ñèñòåìàAz = y ñîâìåñòíà, è åñëè z åå ïðîèçâîëüíîå ðåøåíèå, òî |h| = |b − Az| < |b − Ax| äëÿâñåõ x òàêèõ, ÷òî Ax 6= y .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
