Е.Е. Тыртышников - Матричный анализ и линейная алгебра (1113045), страница 48
Текст из файла (страница 48)
Ðàññìîòðèì 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 . Çíà÷èò, ìíîæåñòâî ïñåâäîðåøåíèé ñîâïàäàåò ñ ìíîæåñòâîìðåøåíèé ñîâìåñòíîé ñèñòåìû Az = y . 2Ñðåäè âñåõ ïñåâäîðåøåíèé âûäåëÿåòñÿ ïñåâäîðåøåíèå x̂ ìèíèìàëüíîé äëèíû îíîíàçûâàåòñÿ íîðìàëüíûì ïñåâäîðåøåíèåì. Ãåîìåòðè÷åñêè ÿñíî, ÷òî x̂ åñòü ïåðïåíäèêóëÿð, îïóùåííûé íà kerA èç ëþáîãî ÷àñòíîãî ðåøåíèÿ z ñîâìåñòíîé ñèñòåìû Az = y(âåêòîð y îðòîãîíàëüíàÿ ïðîåêöèÿ âåêòîðà b íà imA). Òàêèì îáðàçîì, íîðìàëüíîåïñåâäîðåøåíèå ñóùåñòâóåò è åäèíñòâåííî.Ñèíãóëÿðíîå ðàçëîæåíèå ïîçâîëÿåò äàòü ÿâíûé âèä íîðìàëüíîãî ïñåâäîðåøåíèÿ:x̂ =rXv∗bkk=1σkuk .(∗)Äëÿ äîêàçàòåëüñòâà äîñòàòî÷íî ïðîâåðèòü, ÷òî b − Ax̂ ⊥ imA è x̂ ⊥ kerA.Ïðîñòîòà ôîðìóëû íå äîëæíà ñîçäàâàòü âïå÷àòëåíèå îá îòñóòñòâèè ïðîáëåì ïðè âû÷èñëåíèèÃëàâíàÿ ïðîáëåìà, ñîáñòâåííî, â òîì, ÷òî â ñëó÷àår < min(m, n)ðàíãrx̂.ìîæíî ïîâûñèòü ñêîëü óãîäíîìàëûì âîçìóùåíèåì ýëåìåíòîâ ìàòðèöû, à ýòî îçíà÷àåò, ÷òî íîðìàëüíîå ïñåâäîðåøåíèå, íåñìîòðÿ íàôàêò ñóùåñòâîâàíèÿ è åäèíñòâåííîñòè, íå ÿâëÿåòñÿ íåïðåðûâíîé ôóíêöèåé îò ýëåìåíòîâ ìàòðèöûÍàïðèìåð, ïóñòüm=n=1è ðàññìàòðèâàåòñÿ ñèñòåìàx̂ = 0, à íîðìàëüíîå ïñåâäîðåøåíèåx̂(ε) íå ñòðåìèòñÿ ê x̂ ïðè ε → 0.
Ñàìà0 · x = 1.A.Åå íîðìàëüíîå ïñåâäîðåøåíèå åñòü,ε·x = 1åñòüx̂(ε) = 1/ε.î÷åâèäíî,âîçìóùåííîé ñèñòåìûâèäèì,çàäà÷à î âû÷èñëåíèè ñòîëü íåóñòîé÷èâîãî îáúåêòà íåÊàêêàæåòñÿ î÷åíü óæ îñìûñëåííîé. òî æå âðåìÿ, çàäà÷è òàêîãî ðîäà ïîñòîÿííî âîçíèêàþò â ïðèëîæåíèÿõ, è îò íàñ òðåáóþòñÿ êàêèåòî ìåòîäû èõ ðåøåíèÿ. Ïðè ïîñòðîåíèè òàêèõ ìåòîäîâ ñëåäóåò èìåòü â âèäó, ÷òî ýòî äîëæíû áûòü,ìåòîäû èçìåíåíèÿ ñàìîé ïîñòàíîâêè çàäà÷è.ìåòîäàìè ðåãóëÿðèçàöèè.
2ïðåæäå âñåãî,âàåìûìèÇàäà÷à.Ïîäîáíûå âîïðîñû ñâÿçàíû ñ òàê íàçû-Íàéòè íîðìàëüíîå ïñåâäîðåøåíèå íåñîâìåñòíîé ñèñòåìûx1 + x2 + .. + xn = 1,x1 + x2 + ... + xn = 0.2 Îáùóþ òåîðèþ ìåòîäîâ ðåãóëÿðèçàöèè ñîçäàë îñíîâàòåëü ôàêóëüòåòà ÂÌèÊ àêàäåìèê ÀíäðåéÍèêîëàåâè÷ Òèõîíîâ.Å. Å. Òûðòûøíèêîâ35.6233Ïñåâäîîáðàòíàÿ ìàòðèöàÔîðìóëó (∗) äëÿ íîðìàëüíîãî ïñåâäîðåøåíèÿ ìîæíî çàïèñàòü òàêæå â âèäå1/σ1.. ∗.x̂ = M b, M = U V .1/σrÌàòðèöà M íàçûâàåòñÿ ïñåâäîîáðàòíîé (ïî ÌóðóÏåíðîóçó) äëÿ ìàòðèöû A.  ñèëó åäèíñòâåííîñòè íîðìàëüíîãî ïñåâäîðåøåíèÿ ïñåâäîîáðàòíàÿ ìàòðèöà îïðåäåëÿåòñÿîäíîçíà÷íî ïî ìàòðèöå A. Îáîçíà÷åíèå: M = A+ .Çàäà÷à.ÏóñòüA ïðîèçâîëüíàÿ ïðÿìîóãîëüíàÿ ìàòðèöà èA+ åå ïñåâäîîáðàòíàÿ ìàòðèöà.Äîêàæèòå, ÷òî âûïîëíÿþòñÿ ñîîòíîøåíèÿ(AA+ )∗ = AA+ , (A+ A)∗ = A+ A, AA+ A = A, A+ AA+ = A+ .Äîêàæèòå òàêæå, ÷òî35.7A+ åäèíñòâåííàÿ ìàòðèöà, óäîâëåòâîðÿþùàÿ ýòîé ñèñòåìå óðàâíåíèé.Íàèëó÷øèå àïïðîêñèìàöèè ñ ïîíèæåíèåì ðàíãà êàæäîé ìàòðèöå σk vk u∗k ýëåìåíò â ïîçèöèè (i, j) ìîæåò ðàññìàòðèâàòüñÿ êàê ôóíêöèÿîò i è j ñ ðàçäåëåííûìè äèñêðåòíûìè ïåðåìåííûìè i è j : f (i, j) = f1 (i)f2 (j).
ÒàêèìrPîáðàçîì, çàïèñü A â âèäå A =σi vi u∗i îïèñûâàåò íåêîòîðûé ñïåöèàëüíûé ñïîñîá ðàçi=1äåëåíèÿ ïåðåìåííûõ â êàæäîì ÷ëåíå ñóììû èëè, â ìàòðè÷íîé òåðìèíîëîãèè, ñêåëåòíîåðàçëîæåíèå ìàòðèöû A ïðè÷åì ñ âàæíûì äîïîëíèòåëüíûì ñâîéñòâîì îðòîíîðìèðîâàííîñòè ñèñòåì u1 , . . . , ur è v1 , . . . , vr .Îñîáàÿ öåííîñòü è øèðîòà ïðèìåíåíèé ñèíãóëÿðíîãî ðàçëîæåíèÿ âûçâàíû, ïðåæäåâñåãî, òåì, ÷òî îíî äàåò ïðîñòîé è íàäåæíûé ìåõàíèçì èñêëþ÷åíèÿ èç ìàòðèöû íàèìåíåå çíà÷èìîé èíôîðìàöèè ïóòåì åå àïïðîêñèìàöèè ñóììîé ìåíüøåãî ÷èñëà ñëàãàåìûõ ñ ðàçäåëåííûìè ïåðåìåííûìè i è j .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
