Лекции (1163663), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Òîãäà ó íèõ ñîâïàäàþò ñîáñòâåííûåçíà÷åíèÿ.Ïîñòðîåíèå ñèíãóëÿðíîãî ðàçëîæåíèÿ. (Óèëêèíñîí è äð. "Ñïðàâî÷íèê àëãîðèòìîâïî ëèíåéíîé àëãåáðå", Ì., 1976.)Ñïîñîá 1. Ïðè ïîìîùè QR àëãîðèòìà ìîæíî íàéòè ñîáñòâåííûå çíà÷åíèÿ ìàòðèöûAAT , à çàòåì è ñèíãóëÿðíûå ÷èñëà.Ïðèìåð.pµ¶1 121+β12 + β2σ=T1A =  β 0 ,AA =,211+βσ2 = |β|0 βÝòîò ïðèìåð ÷åì-òî èíòåðåñåí â ñëó÷àå β 2 < ε ¿ 1.10Èäåÿ ðåàëüíîãî àëãîðèòìà.Åñëè ìîæíî ïðè ïîìîùè îðòîãîíàëüíûõ ìàòðèö âðàùåíèé P (j) , Q(j) ïðèâåñòè èñõîäíóþìàòðèöó A ê âèäóq1 e2 . .

. 0.. ......=. en qn 0 ...0J 0 = P (n) ...P (1) AQ(1) ...Q(n−2)(ñðàâí. ñ êàíîíè÷åñêîé ïðàâîé ôîðìîé Æîðäàíà), òî ñïðàâåäëèâîÓòâåðæäåíèå. Ñèíãóëÿðíûå ÷èñëà ìàòðèö J 0 è A ñîâïàäàþò. (Ðàçóìååòñÿ áåçäîêàçàòåëüñòâà)Äàëåå â ëåêöèè ñ ïîìîùüþ èëëþñòðàöèé áûë îïèñàí èòåðàöèîííûé ìåòîä ïîñòðîåíèÿìàòðèöû J 0 , îñíîâàííûé íà èçáàâëåíèè îò "ïîääèàãîíàëüíûõ" ýëåìåíòîâ ïðè ïîìîùèýëåìåíòàðíûõ âðàùåíèé-ïðîãîíîâ. Âî ìíîãîì ýòîò ìåòîä àíàëîãè÷åí ñòàíäàðòíîìóQR àëãîðèòìó ðåøåíèÿ ïîëíîé ïðîáëåìû ñîáñòâåííûõ çíà÷åíèé.

Òàê æå è â ýòîììåòîäå "ïîääèàãîíàëüíûå" ýëåìåíòû îáíóëÿþòñÿ, è èç ýëåìåíòîâ, îñòàâøèõñÿ íà"äèàãîíàëè" , ìîæíî èçâëå÷ü èíôîðìàöèþ î ñèíãóëÿðíûõ ÷èñëàõ ìàòðèöû.Äàëåå áóäåò ðàññìàòðèâàòüñÿ çàäà÷à ëèíåéíîé àëãåáðû ñ ïðÿìîóãîëüíîé ìàòðèöåé.Òðåáóåòñÿ íàéòè "ðåøåíèå", òî-åñòü ðåøåíèå â êàêîì-òî (äàëåå îïðåäåëÿåòñÿ âêàêîì) ñìûñëåAx = bãäåA (m × n) , m ≥ n , rankA = r ≤ n , b ∈ Rm .Ïðèìåíèì ê ñèñòåìå óðàâíåíèé ñèíãóëÿðíîå ðàçëîæåíèåTU| ΣV{z } x = bAïîëó÷èì òðè çàäà÷èz = V T x,d = U T b,j≤r σj zj = dj ,0 · zj = dj , r < j ≤ nΣz = d ⇔0 = dj ,j>nÂèäíî, ÷òî åñëè ïðè j > r dj 6= 0 - ðåøåíèÿ ( â îáû÷íîì ñìûñëå ) íåò.Ñôîðìóëèðóåì çàäà÷ó ïî-äðóãîìó.

Ïóñòü ~a1 ...~an - ñòîëáöû A:x1~a1 + ... + xn~an = ~b11Ïîïûòàåìñÿ ïîäîáðàòü xi òàê, ÷òîáûkb − Axk → minpPÂåêòîð íåâÿçêè r = b − Ax, krk2 =ri2 - ò.å. ïîëó÷èëè çàäà÷ó ìèíèìèçàöèèíåâÿçêè.  ëåêöèÿõ ýòî íàçâàíîÇàäà÷à íàèìåíüøèõ êâàäðàòîâmin kb − Axk22 = krk22 î÷åâèäíàÿ îïå÷àòêàxÌîæåò îêàçàòüñÿ, ÷òî íîðìàëüíàÿ ñèñòåìà ñ êâàäðàòíîé ìàòðèöåéAT Ax = AT b, rankA = níåâûðîæäåíà,Óòâåðæäåíèå.  ýòîì ñëó÷àå ðåøåíèå íîðìàëüíîé ñèñòåìû äàåò ðåøåíèå çàäà÷èíàèìåíüøèõ êâàäðàòîâ, ïðè÷åì åäèíñòâåííîå.Äîêàçàòåëüñòâî.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+12Îòâåò ìîæåò áûòü íàéäåí äëÿ êîíêðåòíîãî ñëó÷àÿ èç ðåøåíèÿ çàäà÷è, êîòîðàÿ çàâåäîìîèìååò ðåøåíèå?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, òîðåøåíèå âñïîìîãàòåëüíîé çàäà÷è ìîæåò áûòü âûïèñàíî â ÿâíîì âèäåkrk2 = kAx − bk2 = kAV V T x − bk2 − k(U T AV )(V T x) − U T bk2 = kΣ (V T x) − |{z}U T b k2| {z }=d=zkΣ z −dk22=mX2(σj zj − dj ) =j=1rankAXnX2(σj zj − dj ) +j=12(σj zj − dj ) +mXnrankA+1rankA = n : zj = dj /σj , j = 1...nrankA < n : zj = dj /σj , j = 1...rankAzj − ëþáîå j = rankA + 1...n4 Ëåêöèÿ 4.A (m × n) , m > n - ìàòðèöà ïîëíîãî ðàíãà rank(A) = n.Ïðîäîëæàåì ðàññìàòðèâàòü çàäà÷óAx = b, b ∈ Rmíà ñàìîì äåëå èùåìmin kAx − bk22xÐåøåíèå çàäà÷è íàèìåíüøèõ êâàäðàòîâ äàåò ðåøåíèå ñèñòåìûTTA| {zA} x = A bn×nÐàññìîòðèì âëèÿíèå îøèáêè â ïðàâîé ÷àñòè íà ðåøåíèå çàäà÷èAx̃ = b̃,(b̃ − âîçìóùåííûé âåêòîð)13d2j = 0Îáîçíà÷èì R(A) ëèíåéíîå ïðîñòðàíñòâî (ðàçìåðíîñòè n), íàòÿíóòîå íà âûáðàííûåêàêèì-ëèáî ñïîñîáîì ëèíåéíî-íåçàâèñèìûå ñòðîêè ìàòðèöû A.

Äàëüíåéøèå ðåçóëüòàòûçàâèñÿò îò ñïîñîáà âûáîðà ýòîãî ïðîñòðàíñòâàb1 = projR(A) b,b̃1 = projR(A) b̃Òåîðåìà. Ïóñòü b1 6= 0, ò.å. b íå îðòîãîíàëåí R(A). Òîãäà:kb1 − b̃1 k2kx − x̃k2≤ kAk2 · kA+ k2 ·kxk2kb1 k2båñëè b1 = 0 ⇒6: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(1)Äàëåå Ax = b1±±x = A+ bAA+ b = b1⇒kbk2 ≤ kAk2 · kA+ bk2kb1 k2 ≤ kAk2 · kxk2⇒kxk2 ≥⇒kb1 k2kAk2Èç ïîëó÷åííûõ íåðàâåíñòâ ïîëó÷èì (1)/(2) ⇒ ÷.ò.ä.Ðàññìîòðèì âîïðîñ, ãäå ïðîÿâëÿåòñÿ cond2 (A).Ðåøàòü çàäà÷ó min kAx − bk ìîæíî äâóìÿ ñïîñîáàìèx1.

ñ ïîìîùüþ ñèíãóëÿðíîãî ðàçëîæåíèÿ2. ñ ïîìîùüþ ðåøåíèÿ íîðìàëüíîé ñèñòåìûAT Ax = AT b.1. ⇒ îøèáêà â ïðàâîé ÷àñòè áóäåò óìíîæàòüñÿ íà cond2 (A)2. ⇒ îøèáêà â ïðàâîé ÷àñòè áóäåò óìíîæàòüñÿ íà cond2 (AT A)14±±(2)Òåîðåìà. 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)iqTkA Ak2 = max λi ((AT A)T AT A) = max λi (AT A)ii! Äîêàçàòü ïîñëåäíåå ðàâåíñòâî ñàìîñòîÿòåëüíî.Åñòü òàêàÿÒåîðåìà.

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).÷.ò.ä.Ïðèáëèæåíèå ôóíêöèé.Ïîñòàíîâêà çàäà÷è:f (x) çàäàíà íà îòðåçêå [a, b]; èçâåñòíû f (xi ), i = 1, n, xi ∈ [a, b].Õîòèì ïîëó÷èòü çíà÷åíèÿ â äðóãèõ òî÷êàõ.Ìîäåëü:ϕ1 (x), ..., ϕn (x)nPf (x) ≈Cj ϕj (x)j=1(õîòèì íàéòè íàèëó÷øèå Cj )Ñàìîå ïðîñòîå: ϕj = xj−1 , j = 1, n ⇒ f (x) ≈nPCj xj−1j=1Ïîäñòàâëÿÿ x = x1 , x2 , ..., xn ïîëó÷èì ñèñòåìó äëÿ êîýôôèöèåíòîâ CjnPj=1Cj xj−1= f (xj ), i = 1, ni15Ýòà ñèñòåìà èìååò ðåøåíèå è åäèíñòâåííîå.

Îïðåäåëèòåëü ñèñòåìû¯¯¯ 1¯x1 x21 . . . xn−11¯¯ Yn−1 ¯2¯ 1xx...x222¯=det ¯¯(xk − xn ) 6= 0· ¯¯¯ · · · · · · · ·2· · · · · ·n−1k>n¯ 1xn xn . . . x n ¯ïðè óñëîâèè, ÷òî âñå òî÷êè ðàçëè÷íû.Ñ âû÷èñëèòåëüíîé òî÷êè çðåíèÿ ýòîãî íå äîñòàòî÷íî:1Ïðèìåð: f (x) =225x + 1[ | | || | ] óçëû ðàâíîìåðíî ðàñïðåäåëåíû ïî îòðåçêó........-11×èñëî îáóñëîâëåííîñòè ìàòðèöû íàñòîëüêî áîëüøîå ïðè n → ∞, ÷òîf (x) −nXCj xj−1 → ∞ (n → ∞)j=1Èíòåðïîëÿöèîííûé ìíîãî÷ëåí Ëàãðàíæà.x âíóòðè [a, b]Ln (x), degLn (x) = n − 1Ââåäåì Φi (xj ), degΦi (x) ≤ n − 1,Ln (x) =nXΦi (xj ) = δij òîãäàf (xi )Φi (x),degLn ≤ n − 1i=1x := xj⇒Ln (xj ) = f (xj ).Îñòàëîñü ïîñòðîèòü Φi (x):Φi (x) = const ·Q(const, ò.ê.

deg ≤ n − 1)(x − xj ),j6=ix := xi⇒1 = const ·Q (x − xj )j6=i xi − xj⇒Φi (x) =⇒Ln (x) =nPi=1f (xi )Q(xi − xj )j6=iQ (x − xj )j6=i (xi − xj )Ïóñòü èìååòñÿ Pn (x) = an xn + an−1 xn−1 + ... + a0 , {a0 , ..., an } - èçâåñòíû. Íóæíîíàéòè Pn â êàêîé-ëèáî òî÷êå• 1 ïóòü: âû÷èñëèòü ïîñëåäîâàòåëüíî a0 , a1 x, ..., an xn - ÷èñëî îïåðàöèé ∼ O(n2 )16• 2 ïóòü: âû÷èñëèòü x, x·x, ..., xn ïîòîì óìíîæèòü íà a1 , a2 , ..., an - ÷èñëî îïåðàöèèéO(n) (â ãëàâíîì ÷ëåíå 3n + O(1)) (òðåáóåò äîïîëíèòåëüíîé ïàìÿòè)• 3 ïóòü: ñõåìà Ãîðíåðà((((an x + an−1 )x + an−2 )x + an−3 )x + an−4 )...(íå òðåáóåò äîïîëíèòåëüíîé ïàìÿòè, ÷èñëî îïåðàöèé ìåíüøå (ïîðÿäêà 2n))Ðàçäåëåííàÿ ðàçíîñòü (ð.ð.)Îïðåäåëåíèå.• ð.ð.

íóëåâîãî ïîðÿäêà â ò. xf (x)• ð.ð. ïåðâîãî ïîðÿäêà:f (xi ; xj ) =f (xj ) − f (xi )xj − xi• ð.ð. âòîðîãî ïîðÿäêà:f (xi ; xj ; xk ) =f (xj ; xk ) − f (xi ; xj )xk − xi(òî÷êè íå îáÿçàíû áûòü ðàçëè÷íûìè: åñëè ñîâïàäóò - ìîæíîäîîïðåäåëèòü ïðîèçâîäíîé (â ñëó÷àå 1-ãî ïîðÿäêà), åñëè îíà ñóùåñòâóåò)• ð.ð. k - ãî ïîðÿäêà:f (x1 ; ...; xk+1 ) =Ëåììà.f (x1 ; ...; xk ) =kPj=1Ãf (xj )Qf (x2 ; ...; xk+1 ) − f (x1 ; ...; xk )xk+1 − x1!−1(xi − xj )i6=j, (xi − ðàçëè÷íû).Äîêàçàòåëüñòâî : ïî èíäóêöèè: k = 1 - î÷åâèäíî.17Ïóñòü ñïðàâåäëèâî äëÿ k ≤ m. Ðàññìîòðèì k = m ⇒f (x2 ; ...; xm+1 ) − f (x1 ; ...; xm )f (x1 ; ...; xm+1 ) ==x− x1à m+1!−1Ã!−1 m+1mPQPQ1=f (xj )(xi − xj )−f (xj )(xi − xj )xm+1 − x1 j=2j=1i6=j,2≤i≤m+1i6=j,1≤i≤mïðèj = 1, j = m = 1 ⇒ êîýôôèöèåíò ïðè f (xj ) :j=1 ⇒111· − Q= Qxm+1 − x1(x1 − xi )(x1 − xi )m≥i≥11j =m+1 ⇒·xm+1 − x1Qi6=11(xm+1 − xi )2≤i≤m=QQ1−(xj − xi )2≤i≤m,i6=j(xm+1 − xi )i6=m+1ïðè 1 < j < m + 1 ⇒ êîýôôèöèåíò ïðè f (xj ) :1·xm+1 − x11Q11= Q(xj − xi )(xj − xi )1≤i≤m,i6=ji6=j÷.ò.ä.5 Ëåêöèÿ 5.f (x) - îïðåäåëåíà è èìååò íåîáõîäèìîå ïî õîäó èçëîæåíèÿ ÷èñëî ïðîèçâîäíûõ.x1 , x2 , ..., xn - íàáîð ðàçëè÷íûõ òî÷åê;f (x1 ), ..., f (xn ) - çàäàíû;∃ ìíîãî÷ëåí ñòåïåíè n − 1, ïðîõîäÿùèé ÷åðåç ýòè òî÷êè Ln (x)nQ x − xiPf (xi )f (x) − Ln (x) = f (x) −=x−xiji=1j6=iµn¶nX f (x)Qf (xi )Q−=(x − xi )  Qn(x−x)(x−x)ijii=1(x − xi ) i=1j=i| i=1{z}f (x; x1 ; .

. . ; xn )−ðàçäåëåííàÿ ðàçíîñòüïîëó÷èëè ïðåäñòàâëåíèåf (x) − Ln (x) = f (x; x1 ; . . . ; xn )ωn (x);ωn (x) =nY(x − xi )(1)Ln (x) = L1 (x) + (L2 (x) − L1 (x)) + . . . + (Ln (x) − Ln−1 (x))(2)dfi=1Çàïèøåì î÷åâèäíîå òîæäåñòâî18(L1 (x) = const, L2 − ëèíåéíûé è ò.ä.)Ïóñòü Lm (x)- èíòåðïîëÿöèîííûé ìíîãî÷ëåí, ïîñòðîåííûé ïî x1 ...xm , (m < n).ÐàññìîòðèìLm (x) − Lm−1 (x)- ýòî ìíîãî÷ëåí ñòåïåíè m − 1,x1 , ..., xm−1 - ÿâëÿþòñÿ íóëÿìè ýòîãî ìíîãî÷ëåíà, èõ âñåãî m−1, è âñå îíè ðàçëè÷íû⇒ Lm (x) − Lm−1 (x) = Am−1m−1Y(x − xk ) = Am−1 ωm−1 (x); Am−1 = const.k=1 òî÷êå xm f (xm ) = Lm (xm ) è ïîñëåäíåå ðàâåíñòâî ïåðåïèøåì â âèäåf (x) − Lm−1 (x) = Am−1 ωm−1 (x).6=0 (1) ïîëîæèì n = m − 1, x = xm ⇒f (xm ) − Lm−1 (xm ) = f (xm ; x1 ; .

. . ; xm−1 )ωm−1 (x),èç äâóõ ïîñëåäíèõ ðàâåíñòâ⇒ Am−1 = f (xm ; x1 ; . . . ; xm−1 )òîãäàLm (x) − Lm−1 (x) = f (x1 ; . . . ; xm )ωm−1 (x).Ïîäñòàâèì â (2), ïîëó÷èì âåëè÷èíó, íå çàâèñÿùóþ îò çíà÷åíèÿ f â òî÷êå xLn (x) = f (x1 ) + f (x1 ; x2 )(x − x1 ) + . . .+f (x1 ; . . . ; xn )(x − x1 ) . . . (x − xn−1 )- èíòåðïîëÿöèîííàÿ ôîðìóëà Íüþòîíà.ª äëÿ âû÷èñëåíèÿ f (x1 ; . . . ; xm ) íóæíû ðåêêóð.

Характеристики

Список файлов лекций