Ответы на экзаменационные вопросы (1163657), страница 8

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

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

íå òàêîãî âèäà {a11 , 0, ..., 0}T , òîãäà áåðåì âåêòîð y = a/kak2 , ãäå a - ïåðâûé ñòîëáåöìàòðèöû A, ñîñòàâëÿåì ìàòðèöó Õàóñõîëäåðà, êàê íàïèñàíî âûøå, è ïîëó÷àåì(I − 2wwT )a = kak2 (I − 2wwT )y = {kak, 0, ..., 0}T .Äàëåå ïåðåõîäèì ê ïîäìàòðèöå ìåíüøåé ðàçìåðíîñòè. Îáíóëÿåì õâîñò âòîðîãî ñòîëáöà (óæåâ ïðîñòðàíñòâå ðàçìåðíîñòè N − 1) è ò.ä., ïîêà íå ïîëó÷èì âåðõíåòðåóãîëüíóþ ìàòðèöó.Ïðè ðåøåíèè ñèñòåì ËÀÓ QR-àëãîðèòì ïðèìåíÿåòñÿ äëÿ ïðèâåäåíèÿ ìàòðèöûA ê òðåóãîëüíîìó âèäó. Äëÿ ðåøåíèÿ çàäà÷è íàõîæäåíèÿ ñîáñòâåííûõ çíà÷åíèÿ51ìàòðèöû A òàêæå èñïîëüçóåòñÿ QR àëãîðèòì, êîòîðûé ñîñòîèò èç ïîäãîòîâèòåëüíîãîýòàïà è èòåðàöèîííîãî ïðîöåññà.

Íà ïîäãîòîâèòåëüíîì ýòàïå ìàòðèöà Aïðèâîäèòñÿ ê ïî÷òè òðåóãîëüíîìó âèäóA0 = QT0 AQ0 ,A0 = ??0??????.. ....···0 ... 0... ?... ? ... ? ··· ? ? ?Ýòî òàê íàçûâàåìàÿ âåðõíÿÿ ôîðìà Õåññåíáåðãà. Âïðî÷åì QR àëãîðèòì ìîæíî ïðèìåíÿòüè áåç ýòîãî ýòàïà, ò.å. ïîëîæèòü ïðîñòî A0 = A. Çàäà÷à î íàõîæäåíèè ñ.ç.

â ïðîãðàììóýêçàìåíà íå âõîäèò.20Ðåøåíèå ñèñòåì ëèíåéíûõ àëãåáðàè÷åñêèõóðàâíåíèéè îáðàùåíèå ìàòðèö íà îñíîâå LU-,QRðàçëîæåíèÿ.Ìåòîä ïðîãîíêè .Ñòðàííûé âîïðîñ. Ïåðâàÿ ÷àñòü ñîäåðæèòñÿ â 18 è 19 âîïðîñàõ. Ïðîãîíêà âñòðå÷àåòñÿ â 40âîïðîñå. Äëÿ óäîáñòâà ïðèâåäåì ìåòîä ïðîãîíêè.Ìåòîä ïðîãîíêè ýòî â ÷èñòîì âèäå ìåòîä Ãàóññà. Ôîðìóëû âûâîäÿòñÿ çà 5 ìèíóò.

Èùåìðåøåíèå â âèäå (îáðàòíûé õîä ìåòîäà ïðîãîíêè)yi = αi+1 yi+1 + βi+1 , i = N − 1, N − 2, ..., 0.Èç ïåðâîãî óðàâíåíèÿ ñðàçó îïðåäåëÿþòñÿ (ñòàðòîâàÿ òî÷êà ïðÿìîãî õîäà)y0 = α1 y1 + β1 ⇒ α1 = b0 /c0 , β1 = f0 /c0 .Ôîðìóëó îáðàòíîãî õîäà ïîäñòàâëÿåì â óðàâíåíèÿ, ïîëó÷àåì ôîðìóëû äëÿ ïðîãîíî÷íûõêîýôôèöèåíòîâ (ïðÿìîé õîä ìåòîäà ïðîãîíêè)αi+1 =fi + ai βibi, i = 1, 2, ..., N − 1., βi+1 =ci − ai αici − ai αiÐàññìàòðèâàÿ ôîðìóëó îáðàòíîãî õîäà ñ ïîñëåäíèì óðàâíåíèåì ñèñòåìû íàõîäèì yN(ñòàðòîâàÿ òî÷êà äëÿ îáðàòíîãî õîäà):½fN + αN βNyN −1 = αN yN + βN ,⇒ yN =−aN yN −1 + cN yN = fN ,cN − aN αNÒàêîé âàðèàíò ìåòîäà ïðîãîíêè íàçûâàåòñÿ ïðàâîé ïðîãîíêîé.

Ñóùåñòâóåò ìåòîä ëåâîéïðîãîíêè, ìåòîä âñòðå÷íûõ ïðîãîíîê è äðóãèå âàðèàíòû.52Êîððåêòíîñòü ìåòîäà ïðîãîíêè ñâîäèòñÿ ê òîìó, ÷òîáû ãäå-íèáóäü â çíàìåíàòåëü íîëüíå ïîïàë, à òàêæå ÷òîáû ïðè ðåàëèçàöèè îáðàòíîãî õîäà íå íàáðàòü âû÷èñëèòåëüíóþïîãðåøíîñòü.Óòâåðæäåíèå. Ïóñòü êîýôôèöèåíòû ñèñòåìû óðàâíåíèé äåéñòâèòåëüíû èóäîâëåòâîðÿþò óñëîâèÿì: c0 , cN , ai , bi ïðè i = 1, 2, ..., N − 1 îòëè÷íû îò íóëÿ è|ci | ≥ |ai | + |bi |, i = 1, 2, ..., N − 1,|c0 | ≥ |b0 |, |cN | ≥ |aN |,ïðè÷åì õîòÿ áû îäíî èç íåðàâåíñòâ ÿâëÿåòñÿ ñòðîãèì.

Òîãäà äëÿ ôîðìóë ìåòîäà ïðîãîíêèñïðàâåäëèâû íåðàâåíñòâà:ci − ai αi 6= 0, |αi | ≤ 1, i = 1, 2, ..., N,ãàðàíòèðóþùèå êîððåêòíîñòü è óñòîé÷èâîñòü ìåòîäà.Êîððåêòíîñòü ìåòîäà ïðîãîíêè íèêàêîãî îòíîøåíèÿ íå èìååò ê êîððåêòíîñòè çàäà÷èëèíåéíîé àëãåáðû ñ òðåõäèàãîíàëüíîé ìàòðèöåé. Åñëè óñëîâèÿ Óòâåðæäåíèÿ íå âûïîëíåíû,âïîëíå ìîæåò áûòü, ÷òî çàäà÷à êîððåêòíà, ïðîñòî äëÿ åå ðåøåíèÿ íàäî âçÿòü äðóãîé ìåòîä. Ëåêöèè 1 èñïîëüçóþòñÿ äðóãèå îáîçíà÷åíèÿ:3-x äèàãîíàëüíûå ìàòðèöû. Ìåòîä ïðîãîíêè äëÿ 3-õ äèàãîíàëüíûõ ìàòðèö.α1 γ1A= 0 ···0β1α20β2...0...0...γ2 α3···.. .. .....βn−1... 0γn−1 αnα1 x1 + β1 x2 = b1γx+αi−1i−1i xi + βi xi+1 = bi , i = 2, ..., n − 1γx+αn−1 n−1n xn = bnÏóñòü ðåøåíèå ñóùåñòâóåò. Áóäåì åãî èñêàòü â âèäåxi = Ai+1 xi+1 + Bi+1(!)Íàéäåì {Ai }, {Bi } - ïðîãîíî÷íûå êîýôôèöèåíòû, à çàòåì xn . Ïîäñòàâëÿåì xi−1 = Ai xi + βiâ i-òîå óðàâíåíèåγi Ai xi + γi βi + αi xi + βi xi+1 = biãðóïïèðóåì(γi Ai + αi )xi = −βi xi+1 + bi − γi βiïîëó÷àåìAi+1 =(!!)bi − γi βi−βi, Bi+1 =γi Ai + αiγi Ai + αi| {z } 6=0Äëÿ âû÷èñëåíèÿ ïî ýòèì ðåêóððåíòíûì ñîîòíîøåíèÿì òðåáóþòñÿ íà÷àëüíûå óñëîâèÿ,êîòîðûå ñðàçó ïîëó÷àþòñÿ èç ïåðâîãî óðàâíåíèÿ èñõîäíîé ñèñòåìû óðàâíåíèéb1−β1.; B2 =α1α1Èç ïîñëåäíåãî óðàâíåíèÿ ñèñòåìû è âûáðàííîé ôîðìû ïðåäñòàâëåíèÿ ðåøåíèÿ¯½γn−1 xn−1 + αn xn = bn ¯¯¯ ⇒ ïîëó÷àåì xnxn−1 = An xn + BnA2 =Ïðè âû÷èñëåíèÿõ ïî âûâåäåííûì ôîðìóëàì âîçìîæíû ïðîáëåìû531.

äåëåíèå íà íîëü2. íåñîâìåñòíîñòü ïîñëåäíåé ñèñòåìû3. xn ïîëó÷åíà ñ ïîãðåøíîñòüþ, êîòîðàÿ çàòåì âîçðàñòàåò çà ñ÷åò "íåõîðîøèõ"ïðîãîíî÷íûõ êîýôôèöèåíòîâ.Óñëîâèÿ, ïðè êîòîðûõ ïðîáëåìû 1-3 ïðîïàäàþò:1)2)3)4)5)|αi | ≥ |γi−1 | + |βi |;α1 = αn = 1;|β1 | ≤ 1; |γn | ≤ 1;|β1 | + |γn | ≤ 2;∀i γi 6= 0, βi = 0(çäåñü âñå îïå÷àòêè åùå ïðåäñòîèò èñïðàâèòü!). Èç 1)-5) ïîëó÷àåòñÿ "Òåîðåìêà"|Ai | ≤ 1.2 ïî èíäóêöèè. Ïóñòü |Ai | ≤ 1.? ⇒?|Ai+1 | ≤ 1.Äàëüíåéøèé òåêñò íàäî âîñïðèíèìàòü, êàê äîêàçàòåëüñòâî|Ai γi + αi | − |βi | ≥ |αi | − |Ai γi | ≥1) |γi | + |βi | − |Ai γi | − |βi |: |γi |(1 − Ai |) ≥ 0. ⇒ Ai+1 =−βi≤1çíàìåíàòåëü⇒ |Ai γi + αi | ≥ |βi | >5) 0 ⇒ çíàìåíàòåëü 6= 0(i ≤ n − 1) xn−1 = An xn + BnB − bn /γnbn ⇒ xn = nαnαn xn−1 = − xn +An +γnγnγnñòðîãî!ëèáî1)|β1 | < 1 ⇒ |A2 | < 1, |An | < 1 ⇒ çíàìåíàòåëü â ôîðìóëå äëÿ xn 6= 03)⇒4)ëèáî2)|γn | < 1 ⇒ çíàìåíàòåëü 6= 0(àíàëîãè÷íî)Òàêîå âîò äîêàçàòåëüñòâî!21×èñëî îáóñëîâëåííîñòè ìàòðèö.Îöåíêà îòíîñèòåëüíîé îøèáêè â ðåøåíèèñèñòåìû àëãåáðàè÷åñêèõ óðàâíåíèéâñëåäñòâèå âîçìóùåíèÿ â ìàòðèöåè ïðàâîé ÷àñòè ñèñòåìû.Èç Ëåêöèè 2:54Ðàññìîòðèì âëèÿíèå íà ðåøåíèå âîçìóùåíèÿ ïðàâîé ÷àñòè ñèñòåìû àëãåáðàè÷åñêèõóðàâíåíèé:Ax = b,A(x + δx) = b + δbkδxk = kA−1 δbk ≤ kA−1 k kδbkAδx = δbkbk ≤ kAk kxkkA−1 kkAkkA−1 kkδbkkx − x̃kkδxkkδbk =≤≤≤kbkkxkkxkkxk= kA−1 kkAk ·k∆bk| {z }=condindex (A)èíäåêñ îáîçíà÷àåò êîíêðåòíóþ íîðìó - íàïðèìåð cond2 (A).Ax̃ − b- âåêòîð íåâÿçêè.kbkkδxkkAx̃ − bkcond(A) =kxkkbkÅñëè â çàäà÷å ëèíåéíîé àëãåáðû ìàòðèöà çàäàåòñÿ ñ ïîãðåøíîñòüþ èëè, êàê ãîâîðÿò,âîçìóùàåòñÿ ìàòðèöà:¶µkδAk kδbkcond(A)kx − x̃k.+≤kbk1 − kAδAk kAkkxkÌû ðàññìàòðèâàåì ñëó÷àé íåâûðîæäåííîé A.

Åñëè kAδAk ≥ 1 - íè÷åãî íåëüçÿ ñêàçàòü îïîãðåøíîñòè.det A - íè÷åãî íå ãîâîðèò î ìàòðèöå: ïðèìåðû −1100...0. 010−1 . .cond∞ (D) = 11) D = ....det D = 10−n..0 ...0 10−1 01 −1 ... −1. 01 ..2) A = cond∞ A = n · 2n−1 , det A = 1.. .... −1 0 ... 011 12 . . . 2n−2 0 ... ... ..... ..

..A−1 = ...2.. 0. 11 0... 0155Åùå ðàç î òîì æå:Äëÿ ìàòðèöû A : det(A) 6= 0 ïî îïðåäåëåíèþ ÷èñëî îáóñëîâëåííîñòècond(A) = kAk · kA−1 k.Åñëè ÷èñëî îáóñëîâëåííîñòè áîëüøîå, òî çàäà÷ó íåëüçÿ ðåøèòü ñ õîðîøåé òî÷íîñòüþ1,1 ≤íèêàêèì ìåòîäîì. Ïðèìåð ïëîõî îáóñëîâëåííîé ìàòðèöû - ìàòðèöà Ãèëüáåðòài+j−1i, j ≤ N . Åñëè ðåøåíèå äîëæíî áûòü âèäà {1, 0, 1, 0, 1, ...}, òî äëÿ N = 200 ïðè ðåøåíèèñèñòåìû óðàâíåíèé íà 32 ðàçðÿäíîé ìàøèíå è ïðè âû÷èñëåíèÿõ ñ äâîéíîé òî÷íîñòüþ ëþáûìïðÿìûì ìåòîäîì ïîëó÷èòñÿ âåêòîð, êîìïîíåíòû êîòîðîãî èìåþò âåëè÷èíû ïîðÿäêà 103 ñðàçíûìè çíàêàìè, è íè÷åãî ñ ýòèì íåëüçÿ ïîäåëàòü.Íåðàâåíñòâî äëÿ îøèáêè.

Ïðèáëèæåííîå (â ðåçóëüòàòå âû÷èñëåíèé ñ îêðóãëåíèÿìè)ðåøåíèå ñèñòåìû Ax = b ìîæíî òðàêòîâàòü êàê òî÷íîå äëÿ çàäà÷è Ax∗ = b∗ , ãäå x∗ =x + ∆x, b∗ = b + ∆b:Ax = b ⇒ kbk ≤ kAkkxk, A∆x = ∆b ⇒ k∆xk ≤ kA−1 kk∆bk⇒kb∗ − bkkx∗ − xk.≤ cond(A)kbkkxkÍåðàâåíñòâî äëÿ íåâÿçêè. Ìîæíî òðàêòîâàòü ïî äðóãîìó: êàê òî÷íîå ðåøåíèå äëÿçàäà÷è ñ âîçìóùåííîé ìàòðèöåé A∗ x∗ = b, ãäå A∗ = A + ∆A:r = b − Ax∗ − âåêòîð íåâÿçêè ⇒ ∆Ax∗ = r ⇒ kek ≤ k∆Akkx∗ k,kA∗ − AkkAx∗ − bk.≤kAkkAkkx∗ kÝòè äâà íåðàâåíñòâà íàçûâàþòñÿ íåðàâåíñòâà Óèëêèíñîíà.22Ñèíãóëÿðíîå ðàçëîæåíèå ìàòðèö.Ðåøåíèå ïåðåîïðåäåëåííûõ ñèñòåìëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé. Ëåêöèÿõ 2,3,4 âîò èìåííî ýòî áûëî íàïèñàíî (íå ðåäàêòèðîâàíî).  [1] âîïðîñû 22,23,24íå ðàññìàòðèâàëèñü!Ñèíãóëÿðíîå ðàçëîæåíèå ìàòðèöû.(SVD - Singular Value Decomposition)U T AV = Σ• A - èñõîäíàÿ ìàòðèöà• U, V - îðòîãîíàëüíûå ìàòðèöû, íàçûâàþòñÿ ëåâîé è ïðàâîé ñèíãóëÿðíûìè îáðàòíûìè(?)56• Σ - äèàãîíàëüíàÿ ìàòðèöà diag(σ1 .

. . σn ), σ1 ≥ σ2 ≥ · · · ≥ σr > σr+1 = · · · = σn = 0Èç ðàâåíñòâà ΣΣT = U T A |V {zV T} AT U ñðàçó ñëåäóåò, ÷òî ìàòðèöû ΣΣT è AAT ÿâëÿþòñÿ=Eîðòîãîíàëüíî ïîäîáíûìè. Òàêèì îáðàçîì äîêàçàíîÓòâåðæäåíèå. λi (AT A) = σi2 .kAk2 = kU ΣV T k = kΣV T k2 = kΣk2 =qmax |λi (AT A)|Ýòî äîêàçûâàåò, ÷òî ìàòðè÷íàÿ íîðìà, ñîãëàñîâàííàÿ ñ kxk2 - åñòü kAk2 .p−1kA−1 k = max |λi (AT A)| .×àñòíûé ñëó÷àé A = ATkAk2 = max |λi (A)|.Èòàê, äëÿ êâàäðàòíîé ìàòðèöû A(m × m) ñèíãóëÿðíîå ðàçëîæåíèå îçíà÷àåò íàëè÷èåìàòðèö U, V ∈ ìíîæåñòâà îðòîãîíàëüíûõ òàêèõ, ÷òî U T AV = Σ, ãäå Σ - äèàãîíàëüíàÿìàòðèöà, ðàíã êîòîðûé ðàâåí rσ10...Σ=σi −ñèíãóëÿðíûå ÷èñëà ìàòðèöûσr00Ðàññìîòðèì âîïðîñ, êîãäà ìàòðèöà ïðÿìîóãîëüíàÿ A(m × n) m > n rankA = r ≤ n.Ïóñòü ∃ U (m × m), V (n × n) - îðòîãîíàëüíûå è òàêèå, ÷òî U T AV = Σ, ãäåΣ=σ1..0.σr00ΣΣT = σ12..0.σr200(m×m)(m×m)Èç î÷åâèäíîé öåïî÷êè ðàâåíñòâΣΣT = (U T AV )(U T AV )T = U T A VV T} AT U = U T AAT U| {z=Eñëåäóåò, ÷òî ΣΣT îðòîãîíàëüíî ïîäîáíà AAT .

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

. . 0.. ....0(n)(1)(1)(n−2)..J = P ...P AQ ...Q=. en qn 0 ...0(ñðàâí. ñ êàíîíè÷åñêîé ïðàâîé ôîðìîé Æîðäàíà), òî ñïðàâåäëèâîÓòâåðæäåíèå. Ñèíãóëÿðíûå ÷èñëà ìàòðèö J 0 è A ñîâïàäàþò. (Ðàçóìååòñÿ áåçäîêàçàòåëüñòâà)Äàëåå â ëåêöèè ñ ïîìîùüþ èëëþñòðàöèé áûë îïèñàí èòåðàöèîííûé ìåòîä ïîñòðîåíèÿìàòðèöû J 0 , îñíîâàííûé íà èçáàâëåíèè îò "ïîääèàãîíàëüíûõ" ýëåìåíòîâ ïðè ïîìîùèýëåìåíòàðíûõ âðàùåíèé-ïðîãîíîâ. Âî ìíîãîì ýòîò ìåòîä àíàëîãè÷åí ñòàíäàðòíîìó QRàëãîðèòìó ðåøåíèÿ ïîëíîé ïðîáëåìû ñîáñòâåííûõ çíà÷åíèé. Òàê æå è â ýòîì ìåòîäå"ïîääèàãîíàëüíûå" ýëåìåíòû îáíóëÿþòñÿ, è èç ýëåìåíòîâ, îñòàâøèõñÿ íà "äèàãîíàëè" ,ìîæíî èçâëå÷ü èíôîðìàöèþ î ñèíãóëÿðíûõ ÷èñëàõ ìàòðèöû.Äàëåå áóäåò ðàññìàòðèâàòüñÿ çàäà÷à ëèíåéíîé àëãåáðû ñ ïðÿìîóãîëüíîé ìàòðèöåé.Òðåáóåòñÿ íàéòè "ðåøåíèå", òî-åñòü ðåøåíèå â êàêîì-òî (äàëåå îïðåäåëÿåòñÿ â êàêîì)ñìûñëåAx = bãäåA (m × n) , m ≥ n , rankA = r ≤ n , b ∈ Rm .Ïðèìåíèì ê ñèñòåìå óðàâíåíèé ñèíãóëÿðíîå ðàçëîæåíèåT{z } x = b|U ΣVAïîëó÷èì òðè çàäà÷èz = V T x,d = U T b,j≤r σj zj = dj ,0 · zj = dj , r < j ≤ nΣz = d ⇔0 = dj ,j>n58Âèäíî, ÷òî åñëè ïðè j > r dj 6= 0 - ðåøåíèÿ ( â îáû÷íîì ñìûñëå ) íåò.Ñôîðìóëèðóåì çàäà÷ó ïî-äðóãîìó.

Ïóñòü ~a1 ...~an - ñòîëáöû A:x1~a1 + ... + xn~an = ~bÏîïûòàåìñÿ ïîäîáðàòü xi òàê, ÷òîáûkb − Axk → minqPri2 - ò.å. ïîëó÷èëè çàäà÷ó ìèíèìèçàöèè íåâÿçêè. ÂÂåêòîð íåâÿçêè r = b − Ax, krk2 =ëåêöèÿõ ýòî íàçâàíîÇàäà÷à íàèìåíüøèõ êâàäðàòîâmin kb − Axk22 = krk22 î÷åâèäíàÿ îïå÷àòêàxÌîæåò îêàçàòüñÿ, ÷òî íîðìàëüíàÿ ñèñòåìà ñ êâàäðàòíîé ìàòðèöåéAT Ax = AT b, rankA = níåâûðîæäåíà,Óòâåðæäåíèå.

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

Список файлов ответов (шпаргалок)