Е.Е. Тыртышников - Матричный анализ и линейная алгебра (1112313), страница 71
Текст из файла (страница 71)
Ñëåäîâàòåëüíî, ñóùåñòâóþò 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 ).
2y∈L, y6=0 y ∗ ymaxÑëåäñòâèå. Ïóñòü A è B ýðìèòîâû ìàòðèöû ïîðÿäêà n è ïðè ýòîìB = V − U,V =kXvi vi∗ ,i=1341U=lXi=1ui u∗i .342Ëåêöèÿ 62Òîãäàλi+l (A) ≤ λi (A + B) ≤ λi−k (A),ãäå ëåâîå íåðàâåíñòâî ñïðàâåäëèâî ïðè i + l ≤ n, à ïðàâîå ïðè 1 ≤ i − k .Äîêàçàòåëüñòâî. Ïîñëåäîâàòåëüíîå ïðèìåíåíèå òåîðåìû äàåòλi (A) ≤ λi (A + V ) ≤ λi−k (A),λi (A + B) ≤ λi (A + V ) ≤ λi−l (A + B).Ñëåäîâàòåëüíî,2λi+l (A) ≤ λi (A + B) ≤ λi−k (A).×àñòî áûâàåò èçâåñòíî, ÷òî âñå ñîáñòâåííûå çíà÷åíèÿ ýðìèòîâîé ìàòðèöû A ïðèíàäëåæàò íåêîòîðîìó îòðåçêó [a, b]. Ïîëó÷åííûé ðåçóëüòàò îçíà÷àåò, ÷òî ïðè âñåõ ýðìèòîâûõ âîçìóùåíèÿõ F ðàíãà r ìàòðèöà A + F áóäåò, ïî-ïðåæíåìó, èìåòü âñå ñîáñòâåííûåçíà÷åíèÿ íà îòðåçêå [a, b], êðîìå, áûòü ìîæåò, r àóòñàéäåðîâ.62.2Ñîáñòâåííûå çíà÷åíèÿ è ñèíãóëÿðíûå ÷èñëàÅñòü ìíîãî èíòåðåñíûõ ñîîîòíîøåíèé, ñâÿçûâàþùèõ ñîáñòâåííûå çíà÷åíèÿ ìàòðèöû èåå ñèíãóëÿðíûå ÷èñëà.
Íåêîòîðûå èç íèõ ïîëó÷àþòñÿ î÷åíü ïðîñòî.Ïóñòü A ∈ Cn×n èìååò ñèíãóëÿðíûå ÷èñëà σ1 ≥ . . . ≥ σn , à åå ñîáñòâåííûå çíà÷åíèÿóïîðÿäî÷åíû ïî íåóáûâàíèþ ìîäóëÿ: |λ1 | ≥ . . . ≥ |λn |.Óòâåðæäåíèå. σn ≤ |λn |, |λ1 | ≤ σ1 .Äîêàçàòåëüñòâî. Ïóñòü Ax = λi x, x 6= 0. ⇒ |λi |||x||2 = ||Ax||2 ≤ ||A||2 ||x||2 = σ1 ||x||2⇒ |λi | ≤ σ1 . Äàëåå, åñëè ìàòðèöà A âûðîæäåííàÿ, òî λn = 0 è σn = 0. Åñëè æå Aíåâûðîæäåííàÿ, òî A−1 èìååò ñîáñòâåííûå çíà÷åíèÿ λ−1è ||A−1 ||2 = 1/σn .
2iÄàííûé ïðîñòîé ôàêò èìååò ìíîãî îáîáùåíèé. Íàïðèìåð, òàêîå.Òåîðåìà. Äëÿ âñåõ 1 ≤ k ≤ n ñïðàâåäëèâû íåðàâåíñòâàkX2|λi |kX≤i=1σi2 .i=1Äîêàçàòåëüñòâî.  ñèëó òåîðåìû Øóðà, ñ ïîìîùüþ óíèòàðíîé ìàòðèöû Q ìîæíîïðèâåñòè A ê âåðõíåé òðåóãîëüíîé ìàòðèöåλ1Q∗ AQ = R =hB0CDi,B=b12λ2........b1kb2k..λkÑîáñòâåííûå çíà÷åíèÿ äëÿ A∗ A ðàâíû σ12 ≥ . . . ≥ σn2 è ñîâïàäàþò ñ ñîáñòâåííûìèçíà÷åíèÿìè äëÿh ∗ihih ∗i0B CB BB∗CR∗ R = B=∗∗∗∗∗CD0 DC B C C+D D .Èñïîëüçóÿ ñîîòíîøåíèÿ ðàçäåëåíèÿ äëÿ ýðìèòîâûõ ìàòðèö B ∗ B è R∗ R, íàõîäèìkXi=12∗|λi | ≤ tr (B B) =kXi=1∗λi (B B) ≤kXi=1∗λi (R R) =kXi=1σi2 .Å. Å.
ÒûðòûøíèêîâÇàäà÷à.343Äîêàçàòü, ÷òî ìàòðèöàAÿâëÿåòñÿ íîðìàëüíîé òîãäà è òîëüêî òîãäà, êîãäà ñóììà êâàä-ðàòîâ åå ñèíãóëÿðíûõ ÷èñåë ðàâíà ñóììå êâàäðàòîâ ìîäóëåé ñîáñòâåííûõ çíà÷åíèé.Íåðàâåíñòâà Âåéëÿ. Ñèíãóëÿðíûå ÷èñëà è ñîáñòâåííûå çíà÷åíèÿ, çàíóìåðîâàííûåïî íåóáûâàíèþ ìîäóëåé, óäîâëåòâîðÿþò íåðàâåíñòâàìkYkY|λi | ≤i=11 ≤ k ≤ n.σi ,i=1Äîêàçàòåëüñòâî.  îáîçíà÷åíèÿõ ïðåäûäóùåãî äîêàçàòåëüñòâà,kY2∗2|λi | = | det B| = det(B B) =i=162.3kYkY∗λi (B B) ≤i=1∗λi (R R) =i=1kYσi2 . 2i=1Ìàæîðèçàöèÿ è íåðàâåíñòâàÍà áàçå íåðàâåíñòâ Âåéëÿ ìîæíî ïîëó÷èòü öåëóþ ñåðèþ ïîëåçíûõ íåðàâåíñòâ. Äëÿ ýòîãî èõ íàäîAïåðåïèñàòü â âèäå (äàâàéòå ñ÷èòàòü, ÷òî ìàòðèöàíåâûðîæäåííàÿ)ln |λ1 | + . . .
+ ln |λk | ≤ ln σ1 + . . . + ln σk ,1 ≤ k ≤ n,è çàìåòèòü äîïîëíèòåëüíî, ÷òîln |λ1 | + . . . + ln |λn | = ln σ1 + . . . + ln σn . äàííîé ôîðìå íåðàâåíñòâà Âåéëÿ îêàçûâàþòñÿ ÷àñòíûì ñëó÷àåì íåêîòîðîãî îáùåãî òèïà íåðàâåíñòâ.Ãîâîðÿò, ÷òî âåêòîðx = [x1 , . . . , xn ]> ∈ Rn ìàæîðèðóåòñÿ(1)x1 ≥ . . .
≥ xn ,(2)x1 + . . . + xk ≤ y1 + . . . + yk ,(3)x1 + . . . + xn = y1 + . . . + yn .Îáîçíà÷åíèå:âåêòîðîìy = [y1 , . . . , yn ]> ∈ Rn ,åñëèy 1 ≥ . . . ≥ yn ;x ≺ y.1 ≤ k ≤ n − 1;Ìàæîðèçàöèÿ âñåãäà ñâÿçàíà ñ ðàâåíñòâîìx = Sy ,ãäåS ìàòðèöà ïîðÿäêànñíåîòðèöàòåëüíûìè ýëåìåíòàìè, ñóììû êîòîðûõ äëÿ êàæäîé ñòðîêè è äëÿ êàæäîãî ñòîëáöà îäèíàêîâûè ðàâíû 1. Ìàòðèöà ñ òàêèìè ñâîéñòâàìè íàçûâàåòñÿÇàäà÷à.äâîÿêîñòîõàñòè÷åñêîé.Äîêàæèòå, ÷òî ìíîæåñòâî âñåõ äâîÿêîñòîõàñòè÷åñêèõ ìàòðèö ïîðÿäêàn ÿâëÿåòñÿ âûïóê-ëûì è ïðè ýòîì ìàòðèöû ïåðåñòàíîâîê è òîëüêî îíè ÿâëÿþòñÿ åãî óãëîâûìè òî÷êàìè.Òåîðåìà.
Ïóñòü x1 ≥ . . . ≥ xn , y1 ≥ . . . ≥ yn . Äëÿ òîãî ÷òîáû âåêòîð x = [x1 , . . . , xn ]> ìàæîðè-ðîâàëñÿ âåêòîðîì y = [y1 , . . . , yn ]> , íåîáõîäèìî è äîñòàòî÷íî ñóùåñòâîâàíèå äâîÿêîñòîõàñòè÷åñêîéìàòðèöû S òàêîé, ÷òî x = Sy .Äîêàçàòåëüñòâî.[sij ],Äîñòàòî÷íîñòü: ïóñòüx = Syäëÿ íåêîòîðîé äâîÿêîñòîõàñòè÷åñêîé ìàòðèöûòîãäàkXi=1xi =k XnXi=1 j=1sij yj ≤kXk−1Xi=1kXsij yj + 1 −k−1Xj=1yj +j=1Äîêàæåì íåîáõîäèìîñòü.
Ïóñòüsij yk = kyk −j=1k−1Xj=1x ≺ y.1−kX!sij(yk − yj ) ≤i=1kXk−1XkXj=1i=1yj .j=1Î÷åâèäíî,nx1 ≥ x1 + . . . + xn = y1 + . . . + yn ≥ nyn⇒x1 ≥ yn .!sij(yk − yj ) =S =344Ëåêöèÿ 62 ñëó÷àå n = 2 èìååì y2 ≤ x1 ≤ y1⇒ x1sy1 + ty2 , s, t ≥ 0, s + t = 1. Òàêèì îáðàçîì,ÿâëÿåòñÿ âûïóêëîé êîìáèíàöèåé ÷èñåëy1èy2 :x1 =s tS=.t sx = Sy,yn ≤ x1 ≤ y1 . Îáîçíà÷èì ÷åðåç k íàèìåíüøèé íîìåð òàêîé, ÷òî yk ≤ x1 ≤ yk−1 ≤ y1 .x1 = sy1 +tyk , s, t ≥ 0, s+t = 1.
Ïóñòü ìàòðèöà F ∈ Rn×n çàäàåò ïðåîáðàçîâàíèå u 7→ v = F u, îáùåì ñëó÷àåÏîýòîìóîïðåäåëÿåìîå ñëåäóþùèì ïðàâèëîì:v1 = su1 + tuk ,vk = tu1 + suk ,i 6= 1, k.vi = ui ,Ëåãêî âèäåòü, ÷òî ìàòðèöà F äâîÿêîñòîõàñòè÷åñêàÿ. Äàëåå, ïîëîæèì z = F y , ðàññìîòðèìx0 = [x2 , . . . , xn ]> , z 0 = [z2 , . . . , zn ]> è äîêàæåì, ÷òî x0 ≺ z 0 .
Ñîãëàñíî âûáîðó íîìåðà k ,âåêòîðûxn ≤ . . . ≤ x1 ≤ yk−1 ≤ . . . ≤ y1 .ÏîýòîìólPxi ≤i=2lPyiäëÿ âñåõ1 ≤ l ≤ k − 1.Ïðèk≤l≤níàõîäèìi=2lXzi=(ty1 + syk ) +k−1Xi=2yi +i=2=lXlXyii=k+1yi − (sy1 + tyk ) ≥i=1lXxi − x1 =lXxi .i=2i=1Ðàññóæäàÿ ïî èíäóêöèè, ïðåäïîëîæèì, ÷òî ñóùåñòâóåò äâîÿêîñòîõàñòè÷åñêàÿ ìàòðèöàòàêàÿ, ÷òî00 0x =T zS = TFn−11 00 T0áóäåò, î÷åâèäíî, äâîÿêîñòîõàñòè÷åñêîé. Ó÷èòûâàÿ, ÷òîãäåïîðÿäêà. Òîãäà ìàòðèöàT =Sy ,T0x1 = z1 ,ïîëó÷àåìx = T z.Òàêèì îáðàçîì,x=åñòü ïðîèçâåäåíèå äâóõ äâîÿêîñòîõàñòè÷åñêèõ ìàòðèö è ïîýòîìó, êàê ëåãêî ïðîâåðèòü,2òîæå ÿâëÿåòñÿ äâîÿêîñòîõàñòè÷åñêîé ìàòðèöåé.Ñëåäñòâèå. Ïóñòü [x1 , . .
. , xn ]> ≺ [y1 , . . . , yn ]> . Òîãäà äëÿ ëþáîé âûïóêëîé ìîíîòîííî âîçðàñòàþùåéôóíêöèè φ(t) ñïðàâåäëèâû íåðàâåíñòâàφ(x1 ) + . . . + φ(xk ) ≤ φ(y1 ) + . . . + φ(yk ),Äîêàçàòåëüñòâî.Ñîãëàñíî òåîðåìå,x = Sy1 ≤ k ≤ n.äëÿ íåêîòîðîé äâîÿêîñòîõàñòè÷åñêîé ìàòðèöûS = [sij ].Âñëåäñòâèå ýòîãî,kXφ(xi ) ≤i=1k XnXsij φ(yj ) ≤i=1 j=1kXj=1φ(yj ) +k−1Xj=1k−1XkXj=1i=11−kX!sijφ(yj ) +1−(φ(yk ) − φ(yj )) ≤i=1!!sijkXφ(yk )≤φ(yj ). 2j=1A íåâûðîæäåííàÿ ìàòðèöà ñ ñèíãóëÿðíûìè ÷èñëàìè σ1 ≥ . .
. ≥ σn è ñîáñòâåííûìèλ1 , . . . , λn , óïîðÿäî÷åííûìè ïî íåóáûâàíèþ ìîäóëÿ. Ïîëîæèì xi = ln |λi | è yi = ln σi .tíåðàâåíñòâ Âåéëÿ âûòåêàåò, ÷òî x ≺ y . Âîçüìåì, íàïðèìåð, ôóíêöèþ φ(t) = e .  ñèëó òîãî,Òåïåðü ïóñòüçíà÷åíèÿìèÒîãäà èç!i=1!sijkX÷òî îíà ÿâëÿåòñÿ âûïóêëîé è ìîíîòîííî âîçðàñòàþùåé, ïîëó÷àåì íåðàâåíñòâà|λ1 | + . . .
+ |λk | ≤ σ1 + . . . + σk ,1 ≤ k ≤ n.Äîïîëíåíèå ê ëåêöèè 3863.1×èñëî èòåðàöèé ìåòîäå ñîïðÿæåííûõ ãðàäèåíòîâ xk ∈ x0 + Lk , íî xk ∈/ x0 + Lk−1 . Çíà÷èò, xk − x0 ÿâëÿk−1åòñÿ ëèíåéíîé êîìáèíàöèåé âåêòîðîâ r0 , Ar0 , . . . , A r0 ñ íåíyëåâûì êîýôôèöèåíòîìïðè Ak−1 r0 ⇒ xk = x0 + ψk−1 (A)r0 , ãäå φk−1 (λ) ìíîãî÷ëåí ñòåïåíè k − 1. Èòàê,rk = r0 − Aψk−1 (A)r0 ⇒rk = φk (A)r0 ,deg φk (λ) = k,φk (0) = 1.Óòâåðæäåíèå. Åñëè A ýðìèòîâà ïîëîæèòåëüíî îïðåäåëåííàÿ ìàòðèöà, èìåþùàÿm ïîïàðíî ðàçëè÷íûõ ñîáñòâåííûõ çíà÷åíèé, òî ÷èñëî èòåðàöèé â ìåòîäå ñîïðÿæåííûõ ãðàäèåíòîâ ïðè ëþáîì íà÷àëüíîì âåêòîðå íå áîëüøå m.Äîêàçàòåëüñòâî. Äîñòàòî÷íî ó÷åñòü, ÷òî ñòåïåíü ìèíèìàëüíîãî ìíîãî÷ëåíà äëÿ ýðìèòîâîé ìàòðèöû A íå áîëüøå m.63.22Êàê óáûâàþò íîðìû íåâÿçîên øàãîâ äëÿ ïîëó÷åíèÿ òî÷íîãî ðåøåk -é íåâÿçêè ìîæåò îêàçàòüñÿ äîñòàòî÷íî ìàëîé ïðè k n.
Ïîëó÷åíèå îöåíîêÒåîðåòè÷åñêè ìåòîä ñîïðÿæåííûõ ãðàäèåíòîâ òðåáóåò íå áîëååíèÿ. Ïðàêòè÷åñêè íîðìàîñíîâàíî íà ñëåäóþùåì ðåçóëüòàòå.Ëåììà îá îöåíêå íîðì íåâÿçîê. Ïóñòü λmin è λmax ìèíèìàëüíîå è ìàêñèìàëüíîå ñîáñòâåííûåçíà÷åíèÿ ýðìèòîâîé ïîëîæèòåëüíî îïðåäåëåííîé ìàòðèöû A. Òîãäà k -ÿ íåâÿçêà â ìåòîäå ñîïðÿæåííûõ ãðàäèåíòîâ ïðè ëþáîì íà÷àëüíîì âåêòîðå óäîâëåòâîðÿåò íåðàâåíñòâórλmaxmax|Φk (λ)| ||r0 ||2 ,||rk ||2 ≤λmin λmin ≤λ≤λmaxãäå Φk (λ) ëþáîé ìíîãî÷ëåí ñòåïåíè íå âûøå k , ïîä÷èíåííûé óñëîâèþ Φk (0) = 1.Äîêàçàòåëüñòâî. ìåòîäå ñîïðÿæåííûõ ãðàäèåíòîâ||x − xk ||A = min ||x − (x0 + y)||A .y∈Lky ∈ Lk èìååò âèä y = Ψk−1 (A)r0 , ãäå Ψk−1 (λ) ìíîãî÷ëåí ñòåïåíè k − 1 èëè⇒ A(x − (x0 + y)) = r0 − Ay = Φk (A)r0 , ãäå Φk (λ) ìíîãî÷ëåí ñòåïåíè íå âûøå k ñî ñâîáîäíûì÷ëåíîì Φk (0) = 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
