Е.Е. Тыртышников - Матричный анализ и линейная алгебра (1112313), страница 66
Текст из файла (страница 66)
Íàïîìíèì, ÷òî â íàøåì êóðñå ëèíåéíûì ìíîãîáðàçèåì íàçûâàåòñÿ ìíîæåñòâî âèäàx + L = {x + h : h ∈ L}, ãäå x çàäàííûé âåêòîð ñäâèãà, à L çàäàííîåíàïðàâëÿþùåå ïîäïðîñòðàíñòâî.313314Ëåêöèÿ 54Ïîëîæèìxk+1 = (y − z0 )/γ.Òîãäà ||xk+1 || = 1 è, êðîìå òîãî,min ||xk+1 − z|| = min ||(y − z0 )/γ − z/γ|| =z∈Lkz∈Lk1min ||y − z|| = 1.γ z∈LkÏîñêîëüêó xi ∈ Lk ïðè 1 ≤ i ≤ k , íàõîäèì ||xk+1 − xi || ≥ inf ||xk+1 − z|| = 1.z∈LkÒàêèì îáðàçîì, ê ñèñòåìå âåêòîðîâ x1 , . .
. , xk ìîæíî äîáàâèòü âåêòîð xk+1 ñ ñîõðàíåíèåì ñîîòíîøåíèé âèäà (∗∗). Ëþáàÿ ïîäïîñëåäîâàòåëüíîñòü ïîñëåäîâàòåëüíîñòèâåêòîðîâ xk òàêèõ, ÷òî ||xi − xj || ≥ 1 ïðè i 6= j , îáëàäàåò òåì æå ñâîéñòâîì è ïîýòîìóíå ìîæåò áûòü ôóíäàìåíòàëüíîé. 254.3Ãåîìåòðè÷åñêèå ñâîéñòâà åäèíè÷íûõ øàðîâÏóñòü äàíà ïðîèçâîëüíàÿ íîðìà|| · ||íàCn ,à çàìêíóòûé åäèíè÷íûé øàðZ = {x ∈ Cn : ||x|| ≤ 1}ðàññìàòðèâàåòñÿ êàê íåêîòîðîå ìíîæåñòâî â ïðîñòðàíñòâåCnñ2-íîðìîé.Ëåãêî ïîêàçàòü, ÷òî èìåþòìåñòî òàêèå ñâîéñòâà:(1) Zÿâëÿåòñÿ çàìêíóòûì è îãðàíè÷åííûì.(2) Zñîäåðæèò íóëåâîé âåêòîð â êà÷åñòâå âíóòðåííåé òî÷êè.(3)Åñëè(4)Åñëèx ∈ Z,òîtx ∈ Zäëÿ âñåõ|t| ≤ 1.x, y ∈ Z , òî tx + (1 − t)y ∈ Zâûïóêëûìè).äëÿ âñåõ0≤t≤1(ìíîæåñòâà ñ òàêèì ñâîéñòâîì íàçûâàþòñÿÒåîðåìà.
Äëÿ òîãî ÷òîáû ìíîæåñòâî Z ⊂ Cn áûëî çàìêíóòûì åäèíè÷íûì øàðîì äëÿ êàêîé-íèáóäüíîðìû íà Cn , íåîáõîäèìî è äîñòàòî÷íî âûïîëíåíèå ñâîéñòâ (1)(4).Äîêàçàòåëüñòâî.Ðàññìîòðèì ìíîæåñòâî2òè íîðìó òàêèì îáðàçîì:Z , îáëàäàþùåå óêàçàííûìè ñâîéñòâàìè, è ïîïûòàåìñÿ ââåñ-f (x) = inf{t > 0 : x/t ∈ Z},x ∈ Cn .(#)Ïðåæäå âñåãî, çàìåòèì, ÷òî f (x) ïðèíèìàåò êîíå÷íûå çíà÷åíèÿ äëÿ âñåõ x. Ñîãëàñíî óñëîâèþ (2),Z ñîäåðæèòñÿ îêðåñòíîñòü íóëÿ âèäà O = {||x||2 < ε}, ãäå ε > 0.
Ïîýòîìó äëÿ ëþáîãî x 6= 0 èìååìx/t ∈ O ⊂ Z ïðè t > ||x||2 /ε ⇒ f (x) ≤ ||x||2 /ε. ßñíî òàêæå, ÷òî f (0) = 0 è f (x) > 0 ïðè x 6= 0 (ïåðâîåâñâîéñòâî íîðìû).Âòîðîå ñâîéñòâî (ïîëîæèòåëüíàÿ îäíîðîäíîñòü) äîêàçûâàåòñÿ òàê. ÏóñòüÏðåäïîëîæèì, ÷òîα 6= 0.Ïîñêîëüêó(α/|α|)(x/tk ) ∈ ZÑëåäîâàòåëüíî,x/tk ∈ Z ,òî, â ñèëó ñâîéñòâà⇒ (αx)/(|αk | tk ) ∈ Z(3),tk → f (x)èx/tk ∈ Z .⇒ f (αx) ≤ |α| tk → |α| f (x).f (αx) ≤ |α| f (x). Ïðîòèâîïîëîæíîå íåðàâåíñòâî äîêàçûâàåòñÿ àíàëîãè÷íî ñ âûáîðîìtk → f (αx), (αx)/tk ∈ Z .ïîñëåäîâàòåëüíîñòèÄîêàæåì íåðàâåíñòâî òðåóãîëüíèêà. Ïóñòüαk → f (x), x/αk ∈ Z,Ñîãëàñíî âûïóêëîñòèZ,βk → f (y), y/βk ∈ Z.íàõîäèìαkβk(x/αk ) +(y/βk ) = (x + y)/(αk + βk ) ∈ Z.αk + βkαk + βk2 Ôóíêöèÿ òàêîãî âèäà íàçûâàåòñÿôóíêöèîíàëîì Ìèíêîâñêîãî.Å.
Å. ÒûðòûøíèêîâÎòñþäà315f (x + y) ≤ αk + βk → f (x) + f (y). 2Çàìåòèì, ÷òî Ìèíêîâñêèé îïðåäåëÿë íîðìû èìåííî ñ ïîìîùüþ ôóíêöèè âèäàîáëàäàþùèõ ñâîéñòâàìè(1)(4).(#)è ìíîæåñòâ,Àêñèîìàòè÷åñêèé ïîäõîä ê îïðåäåëåíèþ íîðìû áûë ïðåäëîæåííåñêîëüêî ïîçæå (â 1922 ãîäó) íåçàâèñèìî Áàíàõîì è Âèíåðîì.Äîêàçàííàÿ íàìè òåîðåìà ëåãêî îáîáùàåòñÿ íà ñëó÷àé áåñêîíå÷íîìåðíûõ ïðîñòðàíñòâ. Âñå îñòàåòñÿáåç èçìåíåíèé, åñëè âìåñòî2-íîðìûâûáðàòü è çàôèêñèðîâàòü ëþáóþ íîðìó, îòíîñèòåëüíî êîòîðîéáóäóò çàòåì îïðåäåëÿòüñÿ ïîíÿòèÿ ñõîäèìîñòè, îêðåñòíîñòè, çàìêíóòîñòè è îãðàíè÷åííîñòè.54.4Òîïîëîãè÷åñêèå ïðîñòðàíñòâà äåéñòâèòåëüíîñòè ïðè èçó÷åíèè ñõîäèìîñòè ïîíÿòèå ðàññòîÿíèÿ íóæíî ëèøü äëÿ òîãî, ÷òîáû îïðåäåëÿòü, êàêèå òî÷êè ñ÷èòàþòñÿ áëèçêèìè.
 ìåòðè÷åñêîì ïðîñòðàíñòâåMìîæíî îáúÿâèòü, ÷òî áëèç-êèå òî÷êè ýòî òî÷êè, âõîäÿùèå â îäíî è òî æå îòêðûòîå ìíîæåñòâî. Îáû÷íî ëþáîå îòêðûòîåìíîæåñòâî, ñîäåðæàùåå çàäàííóþ òî÷êó, íàçûâàåòñÿ òàêæå åå÷åêxk ∈ Mñõîäèòñÿ ê òî÷êåx ∈ M,îêðåñòíîñòüþ.Ïîñëåäîâàòåëüíîñòü òî-åñëè â ëþáîé åå îêðåñòíîñòè ñîäåðæàòñÿ âñå òî÷êèxk ,íà÷èíàÿ ñíåêîòîðîé. Ýòî ïðåäëîæåíèå íå îïèðàåòñÿ ÿâíûì îáðàçîì íà ïîíÿòèå ðàññòîÿíèÿ è ÷àñòî ïðèíèìàåòñÿâ êà÷åñòâå îïðåäåëåíèÿ ñõîäÿùåéñÿ ïîñëåäîâàòåëüíîñòè.Îáîçíà÷èì ÷åðåçTTñèñòåìó âñåõ îòêðûòûõ ìíîæåñòâ òî÷åê èçM . Íåñëîæíî ïðîâåðèòü, ÷òî ñèñòåìàîáëàäàåò ñëåäóþùèìè ñâîéñòâàìè:(1)TñîäåðæèòMè ïóñòîå ìíîæåñòâî∅;(2) îáúåäèíåíèå ëþáîãî (êîíå÷íîãî èëè áåñêîíå÷íîãî) ÷èñëà ìíîæåñòâ èç(3) ïåðåñå÷åíèå ëþáîãî êîíå÷íîãî ÷èñëà ìíîæåñòâ èçÏóñòü òåïåðüMTïðèíàäëåæèòT.TïðèíàäëåæèòT;3T ïðîèçâîëüíàÿ ñèñòåìà åãî ïîäìíî(1) − (3).
Òîãäà T íàçûâàåòñÿ òîïîëîãèåé íà M , ñàìè ìíîæåñòâà,îòêðûòûìè, à ìíîæåñòâî M , ñíàáæåííîå òîïîëîãèåé, íàçûâàåòñÿ òîïî- ïðîèçâîëüíîå íåïóñòîå ìíîæåñòâî, àæåñòâ, îáëàäàþùàÿ ñâîéñòâàìèâõîäÿùèå â T , îáúÿâëÿþòñÿëîãè÷åñêèì ïðîñòðàíñòâîì. òîïîëîãè÷åñêîì ïðîñòðàíñòâå ñõîäèìîñòü îïðåäåëÿåòñÿ îòìå÷åííûì âûøå îáðàçîì. Ïîíÿòèå ïðåäåëüíîé òî÷êè, çàìûêàíèÿ è çàìêíóòîãî ìíîæåñòâà îïèðàþòñÿ èñêëþ÷èòåëüíî íà ïîíÿòèå ñõîäÿùåéñÿïîñëåäîâàòåëüíîñòè è ââîäÿòñÿ òàê æå, êàê â ìåòðè÷åñêîì ïðîñòðàíñòâå.54.5Êîìïàêòíûå ìíîæåñòâà â òîïîëîãè÷åñêîì ïðîñòðàíñòâåÎòêðûòûì ïîêðûòèåììíîæåñòâàS ⊂Mâ òîïîëîãè÷åñêîì ïðîñòðàíñòâåâîêóïíîñòü îòêðûòûõ ìíîæåñòâ, îáúåäèíåíèå êîòîðûõ ñîäåðæèòS.Míàçûâàåòñÿ ëþáàÿ ñî-Ïîêðûòèå, ñîñòîÿùåå èç ÷àñòèïîäïîêðûòèåì, à åñëè îíî ñîñòîèò èõ êîíå÷íîãî ÷èñëà îòêðûòûõ ìíîêîíå÷íûì ïîäïîêðûòèåì.Ìíîæåñòâî S íàçûâàåòñÿ êîìïàêòíûì â òîïîëîãè÷åñêîì ïðîñòðàíñòâå M , åñëè èç ëþáîãî åãîäàííûõ ìíîæåñòâ, íàçûâàåòñÿæåñòâ, òî îòêðûòîãî ïîêðûòèÿ ìîæíî âûäåëèòü êîíå÷íîå ïîäïîêðûòèå.Óòâåðæäåíèå.
Ëþáîå êîìïàêòíîå â òîïîëîãè÷åñêîì ïðîñòðàíñòâå ìíîæåñòâî çàìêíóòî è òàêîâî, ÷òî èç ëþáîé ïðèíàäëåæàùåé åìó ïîñëåäîâàòåëüíîñòè òî÷åê ìîæíî âûäåëèòü ñõîäÿùóþñÿïîäïîñëåäîâàòåëüíîñòü.Äîêàçàòåëüñòâî.Åñëè ìíîæåñòâî{xk }èìååò ïðåäåëüíóþ òî÷êó, ïðèíàäëåæàùóþ çàäàííîìó êîì-S , òî âñå äîêàçàíî. Åñëè ýòî íå òàê, òî äëÿ êàæäîé òî÷êè x ∈ S ñóùåñòâóåòkîòêðûòîå ìíîæåñòâî Ox , ñîäåðæàùåå ëèøü êîíå÷íîå ÷èñëî òî÷åê ïîñëåäîâàòåëüíîñòè x . Î÷åâèäíî,ìíîæåñòâà Ox îáðàçóþò îòêðûòîå ïîêðûòèå ìíîæåñòâà S ⇒ ñóùåñòâóåò êîíå÷íîå ïîäïîêðûòèå ⇒kkâ ìíîæåñòâå S èìååòñÿ ëèøü êîíå÷íîå ÷èñëî òî÷åê ìíîæåñòâà {x } ⇒ ïîñëåäîâàòåëüíîñòü x èìååòáåñêîíå÷íîå ÷èñëî îäèíàêîâûõ òî÷åê.2ïàêòíîìó ìíîæåñòâóÒåîðåìà. Äëÿ òîãî ÷òîáû ìíîæåñòâî â ìåòðè÷åñêîì ïðîñòðàíñòâå áûëî êîìïàêòíûì â ñîîòâåòñòâóþùåì òîïîëîãè÷åñêîì ïðîñòðàíñòâå, íåîáõîäèìî è äîñòàòî÷íî, ÷òîáû îíî áûëî çàìêíóòûì è3 Ïåðåñå÷åíèå áåñêîíå÷íîãî ÷èñëà îòêðûòûõ ìíîæåñòâ ìîæåò è íå áûòü îòêðûòûì (íàïðèìåð, ïåðåñå÷åíèå âñåõ îòêðûòûõ ìíîæåñòâ, ñîäåðæàùèõ äàííóþ òî÷êó).316Ëåêöèÿ 54òàêèì, ÷òî â ëþáîé ïðèíàäëåæàùåé åìó ïîñëåäîâàòåëüíîñòè âûäåëÿåòñÿ ñõîäÿùàÿñÿ ïîäïîñëåäîâàòåëüíîñòü.Äîêàçàòåëüñòâî äîñòàòî÷íîñòè.Ïóñòü ðå÷ü èäåò î ìíîæåñòâåS.Ïðåæäå âñåãî, çàìåòèì, ÷òî äëÿε.
4 Åñëè ýòîíå òàê äëÿ êàêîãî-òî ε, òî ñóùåñòâóåò òî÷êà a1 ∈ S òàêàÿ, ÷òî S íå ïîêðûâàåòñÿ øàðîì M (a1 , ε) ⇒ρ(a1 , a2 ) ≥ ε äëÿ íåêîòîðîé òî÷êè a2 ∈ S è ïðè ýòîì S íå ïîêðûâàåòñÿ ñèñòåìîé äâóõ øàðîâ M (a1 , ε)è M (a2 , ε), è òàê äàëåå.  èòîãå ïîëó÷àåòñÿ ïîñëåäîâàòåëüíîñòü òî÷åê ak ∈ S òàêèõ, ÷òî ρ(ai , aj ) ≥ εïðè i 6= j⇒ èç ïîñëåäîâàòåëüíîñòè ak íåëüçÿ âûäåëèòü ñõîäÿùóþñÿ ïîäïîñëåäîâàòåëüíîñòü.Ðàññìîòðèì êîíå÷íûå ïîêðûòèÿ øàðàìè ïîñëåäîâàòåëüíî äëÿ ε = 1, 1/2, 1/3, .
. . è îáîçíà÷èì÷åðåç B ìíîæåñòâî âñåõ ýòèõ øàðîâ. Ïóñòü èìååòñÿ ïðîèçâîëüíîå îòêðûòîå ïîêðûòèå ìíîæåñòâà S .Ëþáàÿ òî÷êà ëþáîãî îòêðûòîãî ìíîæåñòâà ïðèíàäëåæèò íåêîòîðîìó øàðó èç B . Ïîýòîìó ñóùåñòâóåòîòêðûòîå ïîêðûòèå S íåêîòîðîé ïîñëåäîâàòåëüíîñòüþ øàðîâ èç B . Ñëåäîâàòåëüíî, èç çàäàííîãî îòêðûòîãî ïîêðûòèÿ ìíîæåñòâà S ìîæíî âûáðàòü ñ÷åòíîå ïîäïîêðûòèå äðóãèìè ñëîâàìè, S ïîêðûâàåòñÿíåêîòîðîé ïîñëåäîâàòåëüíîñòüþ îòêðûòûõ ìíîæåñòâ Ok .Åñëè èç ñèñòåìû ìíîæåñòâ Ok íåëüçÿ âûáðàòü êàêîå-ëèáî êîíå÷íîå ïîäïîêðûòèå ìíîæåñòâà S , òî!SOi íåïóñòîå. Ïðè ýòîì Z1 ⊃ Z2 ⊃ Z3 ⊃ .
. . . Ïóñòüêàæäîå èç çàìêíóòûõ ìíîæåñòâ Zk = S\ëþáîãîε>0îíî ïîêðûâàåòñÿ êîíå÷íîé ñèñòåìîé îòêðûòûõ øàðîâ ðàäèóñà íå áîëüøå1≤i≤kxk ∈ Zk ⊂ S .Âûäåëèì èç ïîñëåäîâàòåëüíîñòèïðåäåë ÷åðåçx.xk ñõîäÿùóþñÿ ïîäïîñëåäîâàòåëüíîñòü è îáîçíà÷èì ååS , x ∈ S . Äëÿ êàêîãî-òî íîìåðà i èìååì x ∈ Oi .
Íî Oi íå èìååòîáùèõ òî÷åê ñ ñ ëþáûì èç ìíîæåñòâ Zk , íà÷èíàÿ ñ íåêîòîðîãî íîìåðà. Ïîýòîìó ïîñëåäîâàòåëüíîñòüxk íå ìîæåò ñõîäèòüñÿ ê x. Ïîëó÷åííîå ïðîòèâîðå÷èå îçíà÷àåò, ÷òî èç ïîêðûòèÿ S ìíîæåñòâàìè Okìîæíî âûäåëèòü êîíå÷íîå ïîäïîêðûòèå.2 ñèëó çàìêíóòîñòè4 Òàêîå ïîêðûòèå íàçûâàåòñÿε-ñåòüþ.Äîïîëíåíèå ê ëåêöèè 2555.1Ïîòåðÿ îðòîãîíàëüíîñòè ïðè âû÷èñëåíèÿõÏîïðîáóéòå ðåàëèçîâàòü ïðîöåññ îðòîãîíàëèçàöèè ÃðàìàØìèäòà íà êîìïüþòåðå. Ïîçàâåðøåíèè âû÷èñëåíèé çàêîííî æåëàíèå ïðîâåðèòü, íàñêîëüêî îðòîãîíàëüíûìè áóäóò âû÷èñëåííûå âåêòîðû qe1 , .
. . , qen ∈ Cn . ñèëó îøèáîê îêðóãëåíèÿ îíè, êîíå÷íî, îòëè÷àþòñÿ îò òî÷íûõ îðòîíîðìèðîâàííûõâåêòîðîâ q1 , . . . , qn . Îäíàêî, ïðîâåðêà ìîæåò Âàñ è óäèâèòü: â áîëüøîì ÷èñëå ñëó÷àåâñêàëÿðíûå ïðîèçâåäåíèÿ âû÷èñëåííûõ âåêòîðîâ (eqi , qej ) ïðè i 6= j ñîâñåì íå ïîõîæè íà1íóëè.Ïðè÷èíó ïîíÿòü íåòðóäíî. Äîïóñòèì, ÷òî âñå õîðîøî íà ïåðâûõ k øàãàõ:(eqi , qei ) ≈ 1,(eqi , qej ) ≈ 0, i 6= j,1 ≤ i, j ≤ k.Äàëåå, ïóñòü âû÷èñëåííûé ïåðïåíäèêóëÿð ehk+1 òàêîâ, ÷òî(ehk+1 , qei ) = ε,ε ≈ 0.(∗)Ïîñëå íîðìèðîâêè, òåì íå ìåíåå,(eqk+1 , qei ) = (ehk+1 , qei )/|ehk+1 | = ε/|ehk+1 |.Îòñþäà âèäíî, ÷òî îðòîãîíàëüíîñòü óòðà÷èâàåòñÿ ïðè äîñòàòî÷íî ìàëîé äëèíå ïðèáëèæåííîãî ïåðïåíäèêóëÿðà ehk+1 . Ïîñëåäíåå îçíà÷àåò, ÷òî âåêòîð ak+1 áëèçîê ê ëèíåéíîé êîìáèíàöèè âåêòîðîâ a1 , .
. . , ak .×òî æå äåëàòü? Õîðîøèé ðåöåïò çàäåðæàòüñÿ íà k + 1-ì øàãå è ïîâòîðèòü pðàç âû÷èñëåíèÿ k + 1-ãî øàãà ñ çàìåíîé ak+1 íà ehk+1 . Ýòî òàê íàçûâàåìàÿ ïðîöåäóðàp-êðàòíîé ðåîðòîãîíàëèçàöèè. ðåçóëüòàòå âåëè÷èíà ε â ñîîòíîøåíèÿõ òèïà (∗) óìåíüøàåòñÿ è ìîæåò áûòü ñäåëàíàek = [eñêîëü óãîäíî ìàëîé. Äåéñòâèòåëüíî, ïóñòü Qk = [q1 , . . . , qk ], Qq1 , . . . , qek ]. Òîãäàhk+1 = ak+1 −kXi=1"(hk+1 , q1 )(hk+1 , q2 )...(hk+1 , qk )1 Íàïðèìåð, ïðèn × n-ìàòðèöûqi (qi∗ ak+1 )= ak+1 −kX(qi qi∗ )ak+1 = (I − Qk Q∗k )ak+1 ⇒i=1#= Q∗k hk+1 = Q∗k (I − Qk Q∗k )ak+1 = (Ik − Q∗k Qk ) Q∗k ak+1 .n ≥ 10 ïîïðîáóéòå ïðèìåíèòü ïðîöåññ îðòîãîíàëèçàöèè ê ñòîëáöàì íåâûðîæäåííîéaij = 1/(i + j).ñ ýëåìåíòàìè317318Ëåêöèÿ 55Çäåñü I åäèíè÷íàÿ ìàòðèöà ïîðÿäêà n, à Ik åäèíè÷íàÿ ìàòðèöà ïîðÿäêà k .
Åñëèïîãðåøíîñòè èìåëè ìåñòî òîëüêî ïðè âû÷èñëåíèè ïåðâûõ k âåêòîðîâ, à íà k + 1-ì øàãåèõ íå áûëî, òî äëÿ âû÷èñëåííûõ âåêòîðîâ ïîëó÷àåìe∗ ee∗ e e∗Qk hk+1 = (Ik − Qk Q) Qk ak+1 .Ïóñòü ðåîðòîãîíàëèçàöèÿ ïîâòîðÿåòñÿ p ðàç áåç íîðìèðîâêè ïåðïåíäèêóëÿðà è âðåçóëüòàòå ïîëó÷àåòñÿ âåêòîð h(p) . Òîãäàe∗k h(p) = (Ik − Qe∗k Q)e pQe∗k ak+1 .Qe∗ QeËåãêî ïðîâåðèòü, ÷òî â ñëó÷àå äîñòàòî÷íî ìàëûõ ýëåìåíòîâ ìàòðèöû Ik − Qk k (òîåñòü, â ñëó÷àå ïðèåìëåìîé îðòîãîíàëüíîñòè ïåðâûõ k âåêòîðîâ)e pe∗ Q(Ik − Qk k ) → 0 ïðè p → ∞.e∗ h(p) → 0 ïðè p → ∞.Ïîýòîìó QkÇàìå÷àòåëüíî òî, ÷òî ìåòîä ðåîðòîãîíàëèçàöèè ïîçâîëÿåò äîáèòüñÿ õîðîøåé îðòîãîíàëüíîñòè âåêòîðà qek+1 ê âåêòîðàì qe1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
