Ответы на экзаменационные вопросы (1163657), страница 9
Текст из файла (страница 9)
 ýòîì ñëó÷àå ðåøåíèå íîðìàëüíîé ñèñòåìû äàåò ðåøåíèå çàäà÷èíàèìåíüøèõ êâàäðàòîâ, ïðè÷åì åäèíñòâåííîå.Äîêàçàòåëüñòâî.rankAT A = n, ò.å. AT A - íåâûðîæäåííàÿ, ïîëîæèòåëüíî îïðåäåëåííàÿ ñèììåòðè÷íàÿìàòðèöà. Ïóñòü x - åäèíñòâåííîå ðåøåíèå íîðìàëüíîé ñèñòåìû, r = b − Ax óäîâëåòâîðÿåòAT r = 0 ⇐ AT b − AT Ax = 0Äëÿ çàäà÷è íàèìåíüøèõ êâàäðàòîâ èìååìkr̃k2 = min kb − Ax̃k2 = kb − Ax̃k22x̃(âñå âîò èìåííî òàê è áûëî íàïèñàíî...)kr̃k2 ≤ krk2 = kb − Axk2 = kb − Ax + Ax̃ − Ax̃k = kb − Ax̃ + A(x̃ − x)k = kr̃ + A(x̃ − x)kkrk22 = (r, r) = rT r = (r̃ + A(x̃ − x))T (r̃ + A(x̃ − x)) = (r̃ + (x̃ − x)T AT )(r̃ + A(x̃ − x)) ≤kr̃k2 + r̃T A(x̃ − x) + (x̃ − x)T AT r̃ +(x̃ − x)T AT A(x̃ − x) = kr̃k2 + kA(x̃ − x)k2 .}{z} |{z|=0=0Åñëè A(x̃ − x) = 0, òî óðà! krk2 = kr̃k2 , íî ò.ê.
rankA = 0, òî x̃ − x = 0.(òðåáóåòñÿ êîíêðåòíàÿ ðåäàêöèÿ åâòîãî äîêàçàòñòñâà)Îïðåäåëåíèå. Ïóñòü A (m × n). A+ (n × m) íàçûâàåòñÿ ïñåâäîîáðàòíîé ê A, åñëèAA+ A = AÓïðàæíåíèå 1. Ïóñòü A(n × n),rankA < n. Ñóùåñòâóåò ëè A+ ?Åñëè m > n, rankA = n, òî äëÿ çàäà÷è Ax = b íîðìàëüíàÿ ñèñòåìà AT Ax = AT b èìååòåäèíñòâåííîå ðåøåíèå. Åñòåñòâåííî âîçíèêàåò âîïðîñ (ìàëåíüêèé òàêîé)x = (AT A)−1 AT b}{z|?=A+59Îòâåò ìîæåò áûòü íàéäåí äëÿ êîíêðåòíîãî ñëó÷àÿ èç ðåøåíèÿ çàäà÷è, êîòîðàÿ çàâåäîìîèìååò ðåøåíèå?A (AT A)−1 AT A = A}{z|?=EÓïðàæíåíèå 2.1. Åäèíñòâåííà ëè A+2.
rankA < n.?(rankA = n,Ñóùåñòâóåò ëè A+m > n)?Åñëè òðåáóåòñÿ íàéòè ðåøåíèå çàäà÷èmin kAx − bk−?xêîãäà ýòîò ìèíèìóì ðàâåí íóëþ è èìååòñÿ ñèíãóëÿðíîå ðàçëîæåíèå ìàòðèöû A, òî ðåøåíèåâñïîìîãàòåëüíîé çàäà÷è ìîæåò áûòü âûïèñàíî â ÿâíîì âèäåTbkkrk2 = kAx − bk2 = kAV V T x − bk2 − k(U T AV )(V T x) − U T bk2 = kΣ (V T x) − U| {z } |{z} 2=d=zkΣ z − dk22 =mrankAXX(σj zj − dj )2 =(σj zj − dj )2 +j=1j=1nX(σj zj − dj )2 +mXd2j = 0nrankA+1rankA = n : zj = dj /σj , j = 1...nrankA < n : zj = dj /σj , j = 1...rankAzj − ëþáîå j = rankA + 1...nA (m × n) , m > n - ìàòðèöà ïîëíîãî ðàíãà rank(A) = n.Ïðîäîëæàåì ðàññìàòðèâàòü çàäà÷óAx = b, b ∈ Rmíà ñàìîì äåëå èùåìmin kAx − bk22xÐåøåíèå çàäà÷è íàèìåíüøèõ êâàäðàòîâ äàåò ðåøåíèå ñèñòåìûTTA| {zA} x = A bn×nÐàññìîòðèì âëèÿíèå îøèáêè â ïðàâîé ÷àñòè íà ðåøåíèå çàäà÷èAx̃ = b̃,(b̃ − âîçìóùåííûé âåêòîð)Îáîçíà÷èì R(A) ëèíåéíîå ïðîñòðàíñòâî (ðàçìåðíîñòè n), íàòÿíóòîå íà âûáðàííûå êàêèìëèáî ñïîñîáîì ëèíåéíî-íåçàâèñèìûå ñòðîêè ìàòðèöû A.
Äàëüíåéøèå ðåçóëüòàòû çàâèñÿò îòñïîñîáà âûáîðà ýòîãî ïðîñòðàíñòâàb1 = projR(A) b,b̃1 = projR(A) b̃60Òåîðåìà. Ïóñòü b1 6= 0, ò.å. b íå îðòîãîíàëåí R(A). Òîãäà:kb1 − b̃1 k2kx − x̃k2≤ kAk2 · kA+ k2 ·kb1 k2kxk2b6åñëè b1 = 0 ⇒:e2q 1eR(A)⇒ x = 0 ⇒ íåëüçÿ îöåíèâàòücond2 (A) := kAk2 · kA+ k2 - ÷èñëî îáóñëîâëåííîñòèÇàìå÷àíèå:Äîêàçàòåëüñòâî. b = b1 + b2 , b2 ⊥ R(A)A+ b = A+ b1 + A+ b2 = A+ b1 + (AT A)−1 · AT b2 = A+ b1 ,}{z|=0kx − x̃k2 = kA+ b − A+ b̃k2 = kA+ b1 − A+ b̃1 k2 ≤ kA+ k2 · kb1 − b̃1 kÄàëåå Ax = b1±±x = A+ b⇒AA+ b = b1kb1 k2 ≤ kAk2 · kxk2⇒⇒kbk2 ≤ kAk2 · kA+ bk2kxk2 ≥kb1 k2kAk2Èç ïîëó÷åííûõ íåðàâåíñòâ ïîëó÷èì (1)/(2) ⇒ ÷.ò.ä.Ðàññìîòðèì âîïðîñ, ãäå ïðîÿâëÿåòñÿ cond2 (A).Ðåøàòü çàäà÷ó min kAx − bk ìîæíî äâóìÿ ñïîñîáàìèx1. ñ ïîìîùüþ ñèíãóëÿðíîãî ðàçëîæåíèÿ2.
ñ ïîìîùüþ ðåøåíèÿ íîðìàëüíîé ñèñòåìûAT Ax = AT b.1. ⇒ îøèáêà â ïðàâîé ÷àñòè áóäåò óìíîæàòüñÿ íà cond2 (A)2. ⇒ îøèáêà â ïðàâîé ÷àñòè áóäåò óìíîæàòüñÿ íà cond2 (AT A)Òåîðåìà. A (m × n) m ≥ n, rank(A) = n.cond2 (AT A) = (cond2 (A))2 .Çàìå÷àíèå.kBk2 =Äîêàçàòåëüñòâî.qmax λi (B T B)ikAk22 = max λi (AT A)i qkAT Ak2 = max λi ((AT A)T AT A) = max λi (AT A)ii61(1)±±(2)! Äîêàçàòü ïîñëåäíåå ðàâåíñòâî ñàìîñòîÿòåëüíî.Åñòü òàêàÿÒåîðåìà. A, λ1 , . .
. , λN , Pn (A) = an An + an−1 An−1 + . . .⇒ ñ.÷. : Pn (λ1 ), . . . , Pn (λN )⇒ kAk22 = kAT Ak2Îñòàëîñü ïîëó÷èòü àíàëîã äëÿ ïñåâäîîáðàòíîé ìàòðèöû. Èìååì öåïî÷êó ðàâåíñòâA+ (A+ )T = (AT A)−1 AT · ((AT A)−1 AT )T = (AT A)−1 (AT A) · (AT A)−1 = (AT A)−1⇒ kA+ k22 = k(A+ )T A+ k2 = kA+ (A+ )T k2 = k(AT A)−1 k2! äîêàçàòü ñàìîñòîÿòåëüíî kAT k2 = kAk2 .(cond2 (A))2 = kAk22 · kAT k22 = kAT Ak2 · k(AT A)−1 k2 = cond2 (AT A).÷.ò.ä.23Ìåòîä íàèìåíüøèõ êâàäðàòîâ.Íîðìàëüíûå ñèñòåìû. Ïñåâäîîáðàòíûå ìàòðèöû.Îöåíêà îòíîñèòåëüíîé îøèáêèðåøåíèÿ íîðìàëüíûõ ñèñòåì.ñì. âîïðîñ 2224Ïðèìåíåíèå ñèíãóëÿðíîãî ðàçëîæåíèÿ äëÿðåøåíèÿëèíåéíîéçàäà÷èíàèìåíüøèõêâàäðàòîâ.Âûðàâíèâàíèå äàííûõ ìåòîäîìíàèìåíüøèõ êâàäðàòîâ.ñì.
âîïðîñ 2225Ìåòîä ïðîñòîé èòåðàöèè ðåøåíèÿñèñòåì ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé.Íåîáõîäèìûå è äîñòàòî÷íûå óñëîâèÿ ñõîäèìîñòè.Ñèñòåìó Ax = b ïðåîáðàçóåì ê âèäó x = Bx + c, îáû÷íî áåðóò x = x − D(Ax − b), det(D) 6= 0.62Ìåòîä ïðîñòîé èòåðàöèèx0 − âûáèðàåì ñàìèxk+1 = Bxk + c, k = 0, 1, . . .Åñëè ìàòðèöà B íå ñèììåòðè÷íàÿ, òî ýòîò ìåòîä - àòàâèçì. Íå ïîíÿòíî, ïî÷åìó åãî äîñèõ ïîð íå èñêëþ÷èëè èç ïðîãðàììû ÷èñëåííûõ ìåòîäîâ.Äîñòàòî÷íîå óñëîâèå ñõîäèìîñòè - kBk < 1. Äîêàçûâàåòñÿ â îäíó ñòðîêó. Íåîáõîäèìîåè äîñòàòî÷íîå óñëîâèå - âñå ñîáñòâåííûå ÷èñëà ìàòðèöû ïåðåõîäà B ïî ìîäóëþ ìåíüøååäèíèöû. Íåîáõîäèìîñòü äîêàçûâàåòñÿ ëåãêî îò ïðîòèâíîãî, äîñòàòî÷íîñòü äîêàçàòüäîâîëüíî òðóäíî â ñëó÷àå íåñèììåòðè÷íîé ìàòðèöû.Ñõîäèìîñòü ìåòîäà ìîæåò ïîìåíÿòüñÿ íà ðàñõîäèìîñòü ïðè ïåðåñòàíîâêå ñòðîê ìàòðèöû.Äëÿ ñèììåòðè÷íîé ïîëîæèòåëüíî îïðåäåëåííîé ìàòðèöû A ìåòîä ïðîñòîé èòåðàöèèçàïèñûâàþò â âèäåxk+1 − xk+ Axk = b.τ2.  ýòîì ñëó÷àå B = I −Åñëè λ(A) ∈ [m, M ], m > 0, òî ìåòîä ñõîäèòñÿ ïðè 0 < τ <M2.τ A, kBk2 = max |λ(B)| = max |1 − τ t|, îòêóäà ïîëó÷àåòñÿ óñëîâèå −1 < 1 − τ M ⇒ τ <Mt∈[m,M ]Èç Ëåêöèè 11:Òåîðåìà.
Ïóñòü ∃ ! x : x = Bx + c. Òîãäൠn+1¶x= Bxn + c⇔|λ(B)| < 1.ñõîäèòñÿ ∀ x0Äîêàçàòåëüñòâî. °⇒ Îò ïðîòèâíîãî. Ïóñòü |λk | ≥ 1. Bēk = λk ēk , x0 = x + ēkz 0 = x0 − x = ēk , z 1 = Bz 0 = Bēk = λk ēk , ...., z n = λnk ēk .⇐ ñì. êíèãó.°26Îïòèìèçàöèÿ ñêîðîñòè ñõîäèìîñòèïðîñòîéèòåðàöèè äëÿ ñèììåòðè÷íûõïîëîæèòåëüíî îïðåäåëåííûõ ìàòðèö.ìåòîäàÈç Ëåêöèè 11:Äàëåå ñ÷èòàåì, ÷òî ìû ðåøàåì ñèñòåìó ñ ñèììåòðè÷íîé ïîëîæèòåëüíî îïðåäåëåííîéìàòðèöåéAx = b A = AT > 0 (Ax, x) > 0 ∀ x 6= 0.Ïóñòü ∃ m, M : 0 < m ≤ λ(A) ≤ M < ∞. Ñåé÷àñ ìû ïîêàæåì, ÷òî ïðè òàêîì óñëîâèè ìîæíîïîñòîèòü ñõîäÿùèéñÿ èòåðàöèîííûé ïðîöåññ.Íóæíî (äëÿ ñõ-òè), ÷òîáû|λ(E − αA)|p <1kxk2 = p(x, x)kAk2 = λmax (AT A)x = x − α(Ax − b)xn+1 = xn − α(Axn − b)B = E − αAc = αb63|λ(B)| ≤ q < 1kBk2 =sTλmax (B| {zB}) = |λmax (B)| ≤ q < 1.B2Ïðèìå÷àíèå.
Pn (A) = an An + an−1 An−1 + ... + a0 E, {λj } - ñîáñòâåííûå çíà÷åíèÿ A{Pn (λj )} - ñîáñòâåííûå çíà÷åíèÿ Pn (A).Ïóñòü B = E − αA,⇒λ - ñîáñòâåííîå çíà÷åíèå A, òîãäà 1 − αλ - ñîáñòâåííîå çíà÷åíèå B.α16|1 − αλ|1J@J@J@J @J @αJ @¡ 2J @¡0| J @¡m-λMÎïòèìàëüíîå çíà÷åíèå α, îáåñïå÷èâàþùåå íàèáîëüøóþ ñêîðîñòü ñõîäèìîñòè, áóäåòðåøåíèåì çàäà÷è min max |1 − αλ| = q < 1. Ïîñêîëüêó òî÷íûå çíà÷åíèÿ ñîáñòâåííûõαλ1 ,...,λN÷èñåë íåèçâåñòíû, à èçâåñòíû òîëüêî ãðàíèöû ñïåêòðà ìàòðèöû A, âûáèðàåì α èç óñëîâèÿmin max |1 − αλ| = q < 1.α λ∈[m,M ]¶µm+M, 0 . ÄëÿÃðàôèê, ñîîòâåòñòâóþùèé îïòèìàëüíîìó α, ïðîõîäèò ÷åðåç òî÷êó2òàêîãî ᶵM −m n 0M −mnkz k2 .<1kz k2 ≤q0 =M +mM +mÅñëè m è M äîñòèãàþòñÿ, òî ÷èñëî îáóñëîâëåííîñòè cond2 (A) =Ó ýòîé ìàòðèöû2−1N2 0· · ·0÷èñëî îáóñëîâëåííîñòè ∼ N 2−12......00....−1 . .......0M.m0· · ·−1 2 −1. .
. −1 2⇒ â äàííîì ñëó÷àå òàêîé ìåòîä íå î÷åíü õîðîøèé.Òî, ÷òî ó íàñ áûëî ïåðåä ýòèì - ìåòîä ïðîñòîé èòåðàöèè.6427Îïòèìàëüíûé n-øàãîâûé èòåðàöèîííûé ïðîöåññäëÿ ñèñòåìñ ñèììåòðè÷íûìè ïîëîæèòåëüíî îïðåäåëåííûìèìàòðèöàìè.Ðàññìàòðèâàåòñÿ öèêëè÷åñêèé (äëèíà öèêëà N ) ìåòîä èòåðàöèè ñ ïåðåìåííûìè øàãàìèxk+1 − xk+ Axk = bτk+1ñ ñèììåòðè÷íîé ïîëîæèòåëüíî îïðåäåëåííîé ìàòðèöåé A : λ(A) ∈ [m, M ].
Èòåðàöèîííèåïàðàìåòðû èçìåíÿþòñÿ ñëåäóþùèì îáðàçîì τ1 , τ2 , ..., τN , τ1 , τ2 , ..., τN , τ1 , τ2 , ..., τN , ...Óòâåðæäåíèå. Ïðè óñëîâèè A = AT , λ(A) ∈ [m, M ], 0 < m îïòèìàëüíûå çíà÷åíèÿïàðàìåòðîâ ðàâíû îáðàòíûì âåëè÷èíàì êîðíåé ìíîãî÷ëåíà ×åáûøåâà ñòåïåíè N íàπ(2j − 1)M +m M −m. Ïðè ýòîì èìååò ìåñòî ñëåäóþùàÿcos+îòðåçêå [m, M ] : τj−1 =2N22îöåíêà ñêîðîñòè ñõîäèìîñòè çà N øàãîâ:kx − xN k2 ≤2q Nkx − x0 k2 ,1 + q 2N√√M− mãäå q = √√ .M+ mÄîêàçàòåëüñòâî. Äëÿ îøèáêè ïîëó÷èì óðàâíåíèåeN = BN e0 ,BN =NY(I − τj A).j=1 ñèëó ñèììåòðèè ìàòðèöû A ñîáñòâåííûå çíà÷åíèÿ ìàòðèöû BN ïåðåõîäà ñ íóëåâîãî íàN -íûé ñëîé åñòü ïîëèíîì îò ñîáñòâåííûõ çíà÷åíèé Aλ(BN ) =NY(1 − τj λ(A)).j=1Ñòàâèì îïòèìèçàöèîííóþ çàäà÷óqN = min kBN k2 = min max |τjτjλ∈[m,M ]NY(1 − τj λ(A))| .j=1Ýòà çàäà÷à ÿâëÿåòñÿ çàäà÷åé ïîèñêà ìíîãî÷ëåíà, íàèìåíåå óêëîíÿþùåãîñÿ îò íóëÿ íàîòðåçêå [m, M ] ñ ôèêñèðîâàííûì ìëàäøèì êîýôôèöèåíòîì.
Êàêîé áû êîýôôèöèåíò íèôèêñèðîâàòü, êîðíè áóäóò ñîâïàäàòü ñ êîðíÿìè ìíîãî÷ëåíà ×åáûøåâà íà ýòîì îòðåçêå.Íàéäåì òåïåðü âåëè÷èíó qN (çà îäíî êîå-÷òî âñïîìíèì ïðî ìíîãî÷ëåíû ×åáûøåâà):• TN (x) = cos(n arccos x) - ìíîãî÷ëåí ×åáûøåâà íà îòðåçêå [−1, 1];651TN (x) - ïðèâåäåííûé ìíîãî÷ëåí ×åáûøåâà íà îòðåçêå [−1, 1] ñî ñòàðøèì1êîýôôèöèåíòîì 1; åãî íîðìà N −1 â C[−1, 1];2¶µ2x − (b + a)[a,b]- ïðèâåäåííûé ìíîãî÷ëåí ×åáûøåâà íà• T̄N (x) = (b − a)N 21−2N TNb−ab−aîòðåçêå [a, b]; åãî íîðìà 2N −1 ;2• T̄N (x) =[m,M ]•T̄N2n−1(x)[m,M ]T̄N(0)- íàø ìíîãî÷ëåí, åãî ìëàäøèé êîýôôèöèåíò ðàâåí åäèíèöå.[m,M ]Ìîæíî áðàòü îòíîøåíèå íåïðèâåäåííûõTN(x)[m,M ]TN(0). Íîðìà òàêîãî ìíîãî÷ëåíàïîñêîëüêó íîðìà ÷èñëèòåëÿ åäèíèöà - ýòî "êîñèíóñ îò àðêêîñèíóñà".¶µM +m[m,M ].TN(0) = TN −M −m1[m,M ]TN(0),Áåðåì ôîðìóëó äëÿ ìíîãî÷ëåíà ×åáûøåâà â âèäå√√(x − 1 − x2 )N + (x + 1 − x2 )N,TN (x) =2+mïîäñòàâëÿåì x = − MM −m , ïîëó÷àåì, åñëè âûêëàäêó äîòÿíóòü äî êîíöà, òî ÷òîñôîðìóëèðîâàíî â óòâåðæäåíèè.Ïðè ðåàëèçàöèè ðàñ÷åòîâ òðåáóåòñÿ ïåðåìåøèâàòü ïàðàìåòðû τj .
Ñïîñîá ïåðåìåøèâàíèÿ:ïóñòü N = 2l .l = 1 → {1, 2}, l = 2 → {1, 4, 2, 3}, l = 3 → {1, 8, 4, 5, 2, 7, 3, 6}.Çäåñü ðàçäâèãàþòñÿ ýëåìåíòû äëÿ ïðåäûäóùåãî çíà÷åíèÿ l è íà ñâîáîäíûå ìåñòàçàïèñûâàþòñÿ âåëè÷èíû 2l + 1−"ïðåäûäóùèé ýëåìåíò".Èçëîæåíèå ýòîãî æå âîïðîñà ïî Ëåêöèè 11:xn+1 = xn − αn+1 (Axn − b)z n+1 = (E − αn+1 A)z nnQz 0 = Pn (A)z 0(E − αj A)zn =}{z|j=1ñèììåòð. ìàòðèöànQkPn (A)k2 ≤ max |(1 − αj λ)|minα∈[m,M ] j=1nQmax |(1 − αj λ)| ≤ q1 < 1.α1 ,...,αn λ∈[m,M ] j=166Pn (λ) : Pn (0) = 1 êëàññå ìíîãî÷ëåíîâ ñòåïåíè n : P (0) = 1 ïîñòðîèòü ìíîãî÷ëåí, íàèìåíåå îòêëîíÿþùèéñÿîò 0 íà îòðåçêå [m, M ]. Äëÿ ýòîãî âîçüìåì ìíîãî÷ëåí ×åáûøåâà íà [m, M ] è ïîäåëèì íàçíà÷åíèå â íóëå. cos(n√arccos x)|x| ≤ 1√2 − 1)n + (x − x2 − 1)nTn (x) =x(x+|x| ≥ 12T̄n (x) = 21−n Tn (x) = xn +µ...[−1,¶1]2λ − M − m1¶ TnµPn (λ) =M +mM −mTnm−Mπ(2j − 1)M +m M −mπ(2j − 1)cos+λj =xj = cos2n222n2λ − M − mM +m M −m1xx=+λ=αj =M −m22λjM +m1¶¯x0 =|Pn (λ)| ≤ ¯¯ µ¯m−M¯Tn M + m ¯¯M −m ¯sµ¶pM +m 2M+m2−1=±x0 ± x0 − 1 =m−Mm−M√√ 2(M ∓ m)M + m 2 Mm==−±=M −mM√− mm−M√− M− m= −q1√ √√M − √m⇒=1M+ m −√√ =−q1M− m(−1)n 2(q + q1−1 ) ⇒⇒ Tn (x0 ) =2n 12q1< 2q n ⇒ kz n k2 ≤ kPn (A)k2 kz 0 k2 ≤⇒ |Pn (λ)| ≤1 + q1n √ 1 √M− m≤ 2q1n kz 0 k2 , ãäå q1 = √√ < q0 .M+ mÓëó÷øèòü ðåçóëüòàò òÿæåëî.Åñëè n áîëüøîå, òî ìîæåì ïîëó÷èòü ïåðåïîëíåíèå (ò.å.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
