Е.Е. Тыртышников - Матричный анализ и линейная алгебра (1113045), страница 70
Текст из файла (страница 70)
Áîëåå òîãî, ïðèáëèæåíèå ðàíãà r ìîæíî ïîëó÷èòü, èñïîëüçóÿ ëèøü íåêîòîðûå r ñòðîê è r ñòîëáöîâ ìàòðèöû A ýòî âûòåêàåò èçñëåäóþùåé òåîðåìû.Òåîðåìà.Ïóñòü äëÿ ìàòðèöû A ïîðÿäêà n ñóùåñòâóåò ìàòðèöà B ðàíãà r òàêàÿ,÷òî ||B − A||2 ≤ ε. Òîãäà, åñëè A èìååò áëî÷íîå ðàçáèåíèå âèäàA11 A12A =,A21 A222ãäå A11 íåâûðîæäåííàÿ ïîäìàòðèöà ïîðÿäêà r ñ ìàêñèìàëüíûì ïî ìîäóëþ îïðåäåëèòåëåì ñðåäè âñåõ ïîäìàòðèö ïîðÿäêà r, òî A11 −1A11 A11 A12 A− ≤ (r + 1)ε, 1 ≤ i, j ≤ n.A21ijÍà ïðîòÿæåíèè ïîñëåäíèõ 10-20 ëåò ìåòîäû áûñòðîãî ïðèáëèæåííîãî óìíîæåíèÿäëÿ ìàòðèö, ïðèíàäëåæàùèõ âåñüìà îáùèì êëàññàì ìàòðèö, ðàçâèâàëèñü îñîáåííî èíòåíñèâíî.
Îíè ñòàíîâÿòñÿ îñíîâîé î÷åíü ýôôåêòèâíûõ âû÷èñëèòåëüíûõ òåõíîëîãèé: åñëè â 1960-õ ãîäàõ ðåøåíèå ñèñòåì ñ ïëîòíîé ìàòðèöåé êîýôôèöèåíòîâ ïîðÿäêà íåñêîëüêèõ ñîòåí ñ÷èòàëîñü óæå òðóäíîé çàäà÷åé, òî òåïåðü ïîëó÷åíû ìåòîäû, ïîçâîëÿþùèåóñïåøíî ðàáîòàòü ñ ïëîòíûìè ìàòðèöàìè ïîðÿäêà íåñêîëüêèõ ìèëëèîíîâ. Ïðè ýòîìêëþ÷åâîé èäååé ÿâëÿåòñÿ èñïîëüçîâàíèå ìíîãîóðîâíåâûõ áëî÷íûõ ðàçáèåíèé èñõîäíîéìàòðèöû ñ àïïðîêñèìàöèåé áëîêîâ ìàòðèöàìè ìàëîãî ðàíãà.
Äàííûé êðóã âîïðîñîâèìååò îãðîìíîå ïðèêëàäíîå çíà÷åíèå è íàõîäèòñÿ â ñòàäèè àêòèâíîãî èçó÷åíèÿ, â òîì÷èñëå è êàê ÷àñòü òåîðèè è àëãîðèòìîâ ñæàòèÿ è ñòðóêòóðèçàöèè äàííûõ íà îñíîâåìåòîäîâ íåëèíåéíîé àïïðîêñèìàöèè.2 Ýòà òåîðåìà ïîëó÷åíà â ðàáîòå: S. A. Goreinov, E. E. Tyrtyshnikov, The maximal-volume concept inapproximation by low-rank matrices,Contemporary Mathematics,Volume 280, 4751 (2001).Äîïîëíåíèå ê ëåêöèè 3560.1Îáùèé âèä óíèòàðíî èíâàðèàíòíûõ íîðìÏðè ðàáîòå ñ ìàòðèöàìè ìû àêòèâíî èñïîëüçóåì äâå óíèòàðíî èíâàðèàíòíûõ íîðìû:ñïåêòðàëüíóþ íîðìó ||A||2 è íîðìó Ôðîáåíèóñà ||A||F . Äðóãèå íîðìû òîãî æå òèïà ñîãðîìíîé ïîëüçîé ïðèìåíÿþòñÿ, íàïðèìåð, â àñèìïòîòè÷åñêîì ìàòðè÷íîì àíàëèçå (ïðèèçó÷åíèè ïîñëåäîâàòåëüíîñòåé ìàòðèö, ïîðÿäîê êîòîðûõ ñòðåìèòñÿ ê áåñêîíå÷íîñòè).Ïîëíîå îïèñàíèå óíèòàðíî èíâàðèàíòíûõ íîðì áûëî äàíî Äæîíîì ôîí Íåéìàíîìâ 1937 ãîäó.
1Ïóñòü A = V ΣU ∗ ñèíãóëÿðíîå ðàçëîæåíèå ìàòðèöû A. Òîãäà äëÿ ëþáîé óíèòàðíî èíâàðèàíòíîé íîðìû èìååì ðàâåíñòâî ||A|| = ||Σ||. Ïîýòîìó ||A|| åñòü ôóíêöèÿ îòñèíãóëÿðíûõ ÷èñåë ìàòðèöû A:||A|| = Φ(σ1 , . . . , σk ),k = min(m, n).ßñíî, ÷òî Φ(σ1 , . . . , σk ) ìîæíî ðàññìàòðèâàòü êàê ôóíêöèþ îò âåêòîðà σ =[σ1 , . . . , σk ]> ∈ Rn .Êîíå÷íî, ñèíãóëÿðíûå ÷èñëà íåîòðèöàòåëüíû, íî äàâàéòå ïðåäïîëîæèì, ÷òî Φ(σ)îïðåäåëåíà ïðè âñåõ σ ∈ Rk . Ðàññìîòðèì ñëåäóþùèé ñïèñîê òðåáîâàíèé ê ôóíêöèè Φ:(1) Φ(σ) ÿâëÿåòñÿ âåêòîðíîé íîðìîé íà Rk ;(2) Φ(σ) çàâèñèò òîëüêî îò ìîäóëåé êîîðäèíàò âåêòîðà σ ∈ Rk ;(3) Φ(P σ) = Φ(σ) äëÿ ëþáîé ìàòðèöû ïåðåñòàíîâêè ïîðÿäêà k ;(4) åñëè σ = [1, 0, . .
. , 0]> , òî Φ(σ) = 1.Ôóíêöèÿ Φ(σ) ñ òàêèìè ñâîéñòâàìè íàçûâàåòñÿ ñèììåòðè÷íîé êàëèáðîâî÷íîé ôóíêöèåé íà Rk .Åñëè Φ(σ) îïðåäåëÿåòñÿ óíèòàðíî èíâàðèàíòíîé íîðìîé êàê ||Σ||, òî ýòè ñâîéñòâà, î÷åâèäíî, äîëæíû âûïîëíÿòüñÿ. Íåòðèâèàëüíàÿ ÷àñòü òåîðåìû Äæîíà ôîí Íåéìàíà â òîì, ÷òî ëþáàÿ ñèììåòðè÷íàÿ êàëèáðîâî÷íàÿ ôóíêöèÿ îïðåäåëÿåò óíèòàðíîèíâàðèàíòíóþ íîðìó. Åäèíñòâåííóþ (íî îùóòèìóþ) òðóäíîñòü äîñòàâëÿåò ïîëó÷åíèåíåðàâåíñòâà òðåóãîëüíèêà.1 Ëþáîïûòíûé èñòîðè÷åñêèé ôàêò: äàííûé ðåçóëüòàò áûë îïóáëèêîâàí àâòîðîì â Ó÷åíûõ çàïèñêàõÒîìñêîãî óíèâåðñèòåòà.335336Ëåêöèÿ 60Äîïîëíåíèå ê ëåêöèè 3661.1Ãèïåðïîâåðõíîñòè âòîðîãî ïîðÿäêàÐàññìîòðèì â Rn ìíîæåñòâî òî÷åê S ñ êîîðäèíàòàìè x1 , .
. . , xn , óäîâëåòâîðÿþùèìèóðàâíåíèþn XnnXXaij xi xj − 2bk xk + c = 0,i=1 j=1k=1èëè, â ìàòðè÷íîé ôîðìå,f (x) ≡ (Ax, x) − 2(b, x) + c = 0,A = [aij ], b1b = ... ,bn(x, y) ≡ y > x.Âñå êîýôôèöèåíòû ïðåäïîëàãàþòñÿ âåùåñòâåííûìè è, êðîìå òîãî, aij = aji⇒>A = A . Åñëè A 6= 0, òî ìíîæåñòâî ðåøåíèé äàííîãî óðàâíåíèÿ íàçûâàåòñÿ ãèïåðïîâåðõíîñòüþ âòîðîãî ïîðÿäêà.Êàê è ëþáàÿ âåùåñòâåííàÿ ñèììåòðè÷íàÿ ìàòðèöà, A êîíãðóýíòíà è äàæå îðòîãîíàëüíî ïîäîáíà äèàãîíàëüíîé ìàòðèöå Λ = P > AP , ãäå P îðòîãîíàëüíàÿ ìàòðèöà.Çàìåíà ïåðåìåííûõ x = P y ïðèâîäèò óðàâíåíèå f (x) = 0 ê âèäó(Λy, y) − 2(d, y) + c = 0⇔λ1 y12 + .
. . + λr yr2 − 2d1 y1 − . . . − 2dn yn + c = 0,ãäå d = P > b, r ðàíã ìàòðèöû Λ, à λ1 , . . . , λr åå îòëè÷íûå îò íóëÿ ýëåìåíòû(íåíóëåâûå ñîáñòâåííûå çíà÷åíèÿ ìàòðèöû A). Ïîñëåäíåå óðàâíåíèå ñ ïîìîùüþ ñäâèãîâzi = yi − di /λi , 1 ≤ i ≤ r, zi = yi , r + 1 ≤ i ≤ n, ïðèâîäèòñÿ ê âèäóλ1 z12 + . .
. + λr zr2 − 2dr+1 zr+1 − . . . − 2dn zn + h = 0,h = c − d21 /λ21 − . . . − d2r /λ2r .Åñëè dr+1 = . . . = dn = 0, òî äàííîå óðàâíåíèå èìååò óæå äîñòàòî÷íî ïðîñòîé âèäλ1 z12 + . . . + λr zr2 + h = 0.(1) ïðîòèâíîì ñëó÷àå êàêîå-òî èç ÷èñåë dr+1 , . . . , dn îòëè÷íî îò íóëÿ. Ïóñòü dr+1 6= 0.Òîãäà ñóùåñòâóåò îðòîãîíàëüíàÿ ìàòðèöà Q áëî÷íîãî âèäàQ=hIr0337i0eQ,338Ëåêöèÿ 61e îðòîãîíàëüíàÿ ìàòðèöà ïîðÿäêà n − r è ïðè ýòîìãäå Q dr+11e> dr+2 = µ 0 .Q ... ...dn0e> ìîæíî ïîëó÷èòü êàê ïðîèçâåäåíèå ìàòðèö âðàùåíèÿ.
Åñëè z = Qu èÌàòðèöó Qˆ y) = (Q> d,ˆ u) = µ ur+1dˆ = [0, ..., 0, dr+1 , ..., dn ]> , òî (d,⇒ çàìåíà z = Qu äàåòóðàâíåíèå âèäàλ1 u21 + . . . + λr u2r − 2µ ur+1 + h = 0.ßñíî, ÷òî µ 6= 0 (ïî÷åìó?). Ïîýòîìó ìîæíî âûïîëíèòü ñäâèã wr+1 = ur+1 − h/(2µ),wi = ui , i 6= r + 1, è ïîëó÷èòü óðàâíåíèåλ1 w12 + .
. . + λr wr2 − 2µ wr+1 = 0.(2)Óðàâíåíèÿ (1) è (2) íàçûâàþòñÿ ïðèâåäåííûìè óðàâíåíèÿìè ãèïåðïîâåðõíîñòè S . Èçíàøåãî îáñóæäåíèÿ ÿñíî, ÷òî îíè ïîëó÷àþòñÿ ñ ïîìîùüþ ïåðåõîäà ê äðóãîìó îðòîíîìèðîâàííîìó áàçèñó è ñäâèãà íà÷àëà êîîðäèíàò. Îòêàçàâøèñü îò îðòîíîðìèðîâàííîñòè,ìîæíî ïîëó÷èòü óðàâíåíèÿ òàêîãî æå âèäà, â êîòîðûõ λi = ±1. Âûáîð ñîîòâåòñòâóþùåéñèñòåìû êîîðäèíàò ñâÿçàí ñ ïðèâåäåíèåì êâàäðàòè÷íîé ôîðìû (Ax, x) ê êàíîíè÷åñêîìó âèäó; â ñèëó çàêîíà èíåðöèè ÷èñëî ïîëîæèòåëüíûõ è îòðèöàòåëüíûõ êîýôôèöèåíòîâíå çàâèñèò îò ñïîñîáà ïðèâåäåíèÿ.61.2Ãåîìåòðè÷åñêèå ñâîéñòâà ãèïåðïîâåðõíîñòåéS è ìíîæåñòâîì ðåAx = b.
Ôèêñèðóåì òî÷êó x0 ∈ Rn è ðàññìîòðèì ïðÿìóþ x0 +tv, t ∈ R, ñ íàïðàâëÿþùèìv 6= 0. Åå òî÷êè ïåðåñå÷åíèÿ ñ ãèïåðïîâåðõíîñòüþ S îïðåäåëÿþòñÿ êâàäðàòíûì óðàâíåíèåìÈìååòñÿ èíòåðåñíàÿ ñâÿçü ìåæäó ãåîìåòðè÷åñêèìè ñâîéñòâàìè ãèïåðïîâåðõíîñòèøåíèé ñèñòåìûâåêòîðîì(A(x0 + tv), x0 + tv) − 2(b, x0 + tv) + c = 0 ⇔(Av, v) t2 − 2(b − Ax0 , v) t + f (x0 ) = 0.(∗)v èìååò àñèìïòîòè÷åñêîå íàïðàâëåíèå îòíîñèòåëüíî S , åñëè (Av, v) = 0, è íåàñèìïòîòè÷åñêîå íàïðàâëåíèå, åñëè (Av, v) 6= 0.Ïóñòü v èìååò íåàñèìïòîòè÷åñêîå íàïðàâëåíèå è x0 ∈ S .  ýòîì ñëó÷àå f (x0 ) = 0⇒ óðàâíåíèå(∗) èìååò äâà (âîçìîæíî, ñîâïàäàþùèõ) ðåøåíèÿ: ïðè t = 0 è t = 2(b − Ax0 , v)/(Av, v).
Òî÷êàÃîâîðÿò, ÷òî âåêòîðz = x0 + ((b − Ax0 , v)/(Av, v)) v(∗∗)v è ñîåäèíÿþùåãî äâå òî÷êè èç S . Òàêîé îòðåçîêv . Óìíîæèâ (∗∗) ñêàëÿðíî íà Av è çàìåòèâ, ÷òîÿâëÿåòñÿ, î÷åâèäíî, ñåðåäèíîé îòðåçêà, ïàðàëëåëüíîãîõîðäîé äëÿ S ñ(Av, z) = (Az, v), íàõîäèìíàçûâàåòñÿíàïðàâëÿþùèì âåêòîðîì(Az, v) = (b, v).(#)âñå òî÷êè z , ÿâëÿþùèåñÿ ñåðåäèíàìè âñåâîçìîæíûõ õîðä äëÿ S ñ ôèêñèðîâàííûì íåàñèìïòîòè÷åñêèì íàïðàâëåíèåì v , ïðèíàäëåæàò ãèïåðïëîñêîñòè (#). Äàííàÿ ãèïåðïëîñêîñòü íàçûâàåòñÿäèàìåòðàëüíîé ãèïåðïëîñêîñòüþ, ñîïðÿæåííîé âåêòîðó v îòíîñèòåëüíî ãèïåðïîâåðõíîñòè S .Âûâîä:Òî÷êàzíàçûâàåòñÿöåíòðîì ñèììåòðèèäëÿS,åñëèz+p ∈ Sâ òîì è òîëüêî òîì ñëó÷àå, êîãäàz − p ∈ S.Óòâåðæäåíèå.
Ñîâìåñòíîñòü ñèñòåìû Ax = b ñ ïðîèçâîëüíîé âåùåñòâåííîé ñèììåòðè÷íîé ìàò-ðèöåé A ðàâíîñèëüíà ñóùåñòâîâàíèþ öåíòðà ñèììåòðèè ó ãèïåðïîâåðõíîñòè f (x) = 0. Ìíîæåñòâîâñåõ öåíòðîâ ñèììåòðèè ñîâïàäàåò ñ ìíîæåñòâîì âñåõ ðåøåíèé ñèñòåìû Ax = b.Äîêàçàòåëüñòâî.zAz = b ⇒ (Av, z) = (b, v) äëÿ ëþáîãî íåàñèìïòîòè÷åñêîãî âåêòîðà v ⇒âñåõ äèàìåòðàëüíûõ ãèïåðïëîñêîñòåé ⇒ z ÿâëÿåòñÿ ñåðåäèíîé ëþáîéöåíòðîì ñèììåòðèè) äëÿ S .Ïóñòüïðèíàäëåæèò ïåðåñå÷åíèþõîðäû (à çíà÷èò, èÅ. Å. ÒûðòûøíèêîâÒåïåðü ïðåäïîëîæèì, ÷òî339z öåíòð ñèììåòðèè äëÿS⇒(A(z + p), z + p) − 2(b, z + p) = (A(z − p), z − p) − 2(b, z − p)⇒ (Az − b, p) = 0.n ëèíåéíî íåçàâèñèx0 , x1 = x0 + v1 , .
. . , xn = x0 + vn ∈ S áóäóòx0 ∈ S òàêîâà, ÷òî b − Ax0 6= 0. Èç (∗) ÿñíî,ïðèíàäëåæàòü S . Ëåãêî âèäåòü, ÷òî âåêòîðûËåãêî ïîêàçàòü (íàïðèìåð, ñ ïîìîùüþ ïðèâåäåííûõ óðàâíåíèé), ÷òî ñóùåñòâóþòìûõ íåàñèìïòîòè÷åñêèõ âåêòîðîâv1 , . . . , vn .Òîãäà òî÷êèàôôèííî íåçàâèñèìûìè (ñì. ðàçäåë 13.6). Ïóñòü òî÷êà÷òîviìîæíî âûáðàòü òàêèì îáðàçîì, ÷òî âñåxiáóäóòxi −z , 0 ≤ i ≤ n, áóäóò àôôèííî íåçàâèñèìûìè. Ïîýòîìó èç íèõ ìîæíî âûáðàòü ïîäñèñòåìó èçn ëèíåéíî íåçàâèñèìûõ âåêòîðîâ (ñì. çàäà÷ó èç ðàçäåëà 13.6). Ñëåäîâàòåëüíî, ñóùåñòâóþò n ëèíåéíîíåçàâèñèìûõ âåêòîðîâ p òàêèõ, ÷òî z + p ∈ S⇒ Az = b. 2(òî÷êè)340Ëåêöèÿ 61Äîïîëíåíèå ê ëåêöèè 3762.1Ýðìèòîâî âîçìóùåíèå çàäàííîãî ðàíãàÒåîðåìà.
Ïóñòü A ýðìèòîâà ìàòðèöà ïîðÿäêà n è B = A + vv ∗ åå ýðìèòîâîâîçìóùåíèå ðàíãà 1. Òîãäàλ1 (B) ≥ λ1 (A) ≥ λ2 (B) ≥ . . . ≥ λn−1 (A) ≥ λn (B) ≥ λn (A),λk (A) + ||v||2 ≥ λk (B), 1 ≤ k ≤ n.Äîêàçàòåëüñòâî. Èñïîëüçóÿ òåîðåìó ÊóðàíòàÔèøåðà, íàõîäèìλk (A)=maxdim L=kmaxdim L=kx∗ Ax≤x∈L, x6=0 x∗ xminmaxdim L=kx∗ Ax + |v ∗ x|2=x∈L, x6=0x∗ xminx∗ Bx= λk (B) ≤ λk (A) + ||v||2 .x∈L, x6=0 x∗ xminÄàëåå, ïóñòü V óíèòàðíàÿ ìàòðèöà ñ ïîñëåäíèì ñòîëáöîì, ðàâíûì v/||v||2 . Òîãäàλk (V ∗ AV ) = λk (A), λk (B) = λk (V ∗ BV ) è, êàê ëåãêî âèäåòü,"0#V ∗ BV = V ∗ AV +...0γ̄[0...0γ] ,γ = ||v||2 .Îáîçíà÷èì ÷åðåç C îáùóþ äëÿ V ∗ AV è V ∗ BV ïîäìàòðèöó ïîðÿäêà n−1 íà ïåðåñå÷åíèèïåðâûõ n − 1 ñòðîê è ñòîëáöîâ.Ïóñòü M ïîäïðîñòðàíñòâî ñòîëáöîâ èç Cn ñ ïîñëåäíåé êîîðäèíàòîé, ðàâíîé íóëþ.Ïî òîé æå òåîðåìå ÊóðàíòàÔèøåðà, ïðè 2 ≤ k ≤ nλk (B)=mindim L=n−k+1x∗ (V ∗ BV )x≤x∈L, x6=0x∗ xmaxmindim L = (n − 1) − (k − 1) + 1L ⊂ Cn−1mindim L=n−k+1, L⊂Mx∗ (V ∗ AV )x=x∈L, x6=0x∗ xmaxy ∗ Cy= λk−1 (C) ≤ λk−1 (V ∗ AV ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
