Е.Е. Тыртышников - Матричный анализ и линейная алгебра (1112313), страница 70
Текст из файла (страница 70)
Åñëè èì ïðåíåáðå÷ü, òî ïîëó÷àåòñÿ íåêîòîðàÿ àïïðîêñèìàöèÿ ñ ðàçäåu è v . Åñëè f êàê ôóíêöèÿ îò v ïðèíàäëåæèò êëàññó áåñêîíå÷íî äèôôåðåíöèsðóåìûõ ôóíêöèé, äëÿ êîòîðûõ ïðîèçâîäíàÿ ëþáîãî ïîðÿäêà s îãðàíè÷åíà ïî ìîäóëþ âåëè÷èíîé M ,ãäå M ïîëîæèòåëüíàÿ êîíñòàíòà, îäèíàêîâàÿ äëÿ âñåõ u ∈ D , òîrMr b − a|Er (u, v)| ≤.r!2ãäåëåííûìè ïåðåìåííûìèÌîæíî ïîêàçàòü, ÷òî ïðàâàÿ ÷àñòü ñòðåìèòñÿ ê íóëþ ïðèp, q > 1îíà íå ïðåâîñõîäèòp/q rïðè âñåõr.Íåðàâåíñòâîp/q r ≤ εr → ∞.Áîëåå òîãî, äëÿ íåêîòîðûõ êîíñòàíò334Ëåêöèÿ 59áóäåò âûïîëíåíî, åñëèlog p + log ε−1≤ r.log q äàííîì ñëó÷àå ÷èñëî îïåðàöèé â íàøåì ïðèáëèæåííîì àëãîðèòìå óìíîæåíèÿ ìàòðèöûxïîëó÷àåò âèäO(n log ε−1Aíà âåêòîð).Ìåòîäû ìàòåìàòè÷åñêîãî àíàëèçà íóæíû äëÿ òîãî, ÷òîáû äîêàçàòü ñóùåñòâîâàíèå ïðèáëèæåíèÿ ìàòðèöû A ìàòðèöåé Ar , ðàíã êîòîðîé ìàë ïî ñðàâíåíèþ ñ n.
Åñëèýòîò ôàêò óæå óñòàíîâëåí, òî èíòåðåñóþùåå íàñ ïðèáëèæåíèå ìîæíî íàéòè ñ ïîìîùüþñîáñòâåííûõ ìåòîäîâ òåîðèè ìàòðèö. Áîëåå òîãî, ïðèáëèæåíèå ðàíãà 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).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
