Е.Е. Тыртышников - Матричный анализ и линейная алгебра (1113045), страница 71
Текст из файла (страница 71)
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.
Òàêèì îáðàçîì,Ïðîèçâîëüíûé âåêòîðíèæå||x − xk ||A = ||A−1 rk ||A ≤ ||A−1 Φk (A)r0 ||A .Ïóñòüλ1 ≥ . . . ≥ λn > 0 ñîáñòâåííûå çíà÷åíèÿ ìàòðèöûAq1 , . . . , q nèáàçèñ èç ñîáñòâåííûõ âåêòîðîâ:λ1AQ = QΛ,Q = [q1 , . . . , qn ],Λ=....λn345 îðòîíîðìèðîâàííûé346Ëåêöèÿ 63rk =nX||A−1 rk ||2A =⇒ζi qii=1r0 =nXnX|Φk (λi )|2 |ξi |21≤λλini=1ξi qi ⇒ ||A−1 Φk (A)r0 ||2A =||rk ||22,λ1≥maxλmin ≤λ≤λmax|Φk (λ)|2 ||r0 ||22 . 2Îöåíêà ñ ïîìîùüþ ìíîãî÷ëåíîâ ×åáûøåâàÒàêèì îáðàçîì, îöåíêè äëÿ íîðìûk -éíåâÿçêè ìîæíî ïîëó÷àòü ñ ïîìîùüþ ìíîãî÷ëåíîâ. Ïðè ýòîìíàñ èíòåðåñóåò âåëè÷èíà, óæå èçâåñòíàÿ íàì êàêîòðåçêåC -íîðìàâ ïðîñòðàíñòâå íåïðåðûâíûõ ôóíêöèé íà[λmin , λmax ]:||Φk ||C =Êàê âûáðàòü ìíîãî÷ëåí[λmin , λmax ]?Φk (λ)|Φk (λ)|.Φk (0) = 1 è íàèìåíüøåé C -íîðìîéìíîãî÷ëåíû ×åáûøåâà.îòðåçêà [−1, 1] îïðåäåëÿþòñÿ ñëåäóþùèì îáðàçîì:ñ óñëîâèåì íîðìèðîâêèíà îòðåçêåTn+1 (t) = 2tTn (t) − Tn−1 (t), n = 1 2, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
