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

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

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

Ìàêñèìàëüíàÿ íîðìà (l∞ -íîðìà) kxk∞ = max |xi |iP4. Íîðìà üëüäåðà ñ ïîêàçàòåëåì p : kxkp = ( |xi |p )1/p äàëüíåéøåì áóäóò èñïîëüçîâàòüñÿ ñòàíäàðòíûå îáîçíà÷åíèÿ: ïóñòü x - òî÷íîå ðåøåíèåçàäà÷è, x̃ - ïðèáëèæåííîåkδxk = kx − x̃kkx − x̃kk∆xk =kxkÌàòðè÷íûå íîðìû.Îïðåäåëåíèå.kAk ≥ 0kαAk = |α|kAkàääèòèâíûå íîðìûkA + Bk ≤ kAk + kBkkABk ≤ kAkkBkñâîéñòâî ìóëüòèïëèêàòèâíîñòèÏðèìåðû:PkAk1 = max |aij |qj ikAk2 = max λi (AT A)i PkAk∞ = max |aij |ijkAkF = N (A) =rP Pijñòîëáöîâàÿñïåêòðàëüíàÿñòðî÷íàÿ|aij |2áåç äîê-âà ptr(AT A) ñôåðè÷åñêàÿ=Îïðåäåëåíèå.Íîðìû k.kI è k.kII íàçûâàþòñÿ ýêâèâàëåíòíûìè, åñëè αk.kI ≤ k.kII ≤ βk.kI .45Ïðèìåðû:√1√ k.k1 ≤ k.k∞ ≤ nk.k1n√1√ k.k2 ≤ k.k1 ≤ nk.k2nÃîâîðÿò, ÷òî ìàòðè÷íàÿ íîðìà ñîãëàñîâàíà c âåêòîðíîé, åñëè kAxk ≤ kAk kxk ∀ A, x.kAxk= sup kAxk íàçûâàåòñÿ íîðìîé, ïîä÷èíåííîé äàííîé âåêòîðíîékAk = supx6=0 kxkx,kxk=1íîðìå.kAk1ïîä÷èíåíà kxk1kAk2kxk2kAk∞kxk∞Òî, ÷òî ýòî ìàòðè÷íûå íîðìû - î÷åâèäíî(÷åòâåðòîåóñëîâèå îïðåäåëåíèÿ ïðîâåðÿåòñÿ òàê:¶µkBxkkAxkkAxk kBxkkAx + Bxk= kAk + kBk).+ sup≤ sup+≤ supkA + Bk = supkxkkxkkxkkxkkxkÏîä÷èíåííàÿ íîðìà ÿâëÿåòñÿ ñîãëàñîâàííîé:(∗)kABk = sup kABxk ≤ sup kAkkBxk ≤ sup kAkkBkkxk ≤ kAk kBkkxk=1kxk=1kxk=1kAxk≤ kAk(∗) ⇐kxkkEk â ïîä÷èíåííîé íîðìå ðàâíà 1, íî â ñëó÷àå ñôåðè÷åñêîé íîðìû kEkF =íîðìà íå ÿâëÿåòñÿ ïîä÷èíåííîé.max |aij | - íå ÿâëÿåòñÿ ìàòðè÷íîé íîðìîé:√n - ò.å.

ýòài,jkAAk ≤ kAk kAk - íåâåðíî äëÿµA=1 11 1¶µ, A2 =2 22 2¶- ïðîòèâîðå÷èå 2 ≤ 1.Ðàññìîòðèì âëèÿíèå íà ðåøåíèå âîçìóùåíèÿ ïðàâîé ÷àñòè ñèñòåìû àëãåáðàè÷åñêèõóðàâíåíèé:Ax = b,A(x + δx) = b + δbAδx = δbkδxk = kA−1 δbk ≤ kA−1 k kδbkkbk ≤ kAk kxkkA−1 kkAkkA−1 kkδbkkx − x̃kkδxkkδbk =≤≤≤kbkkxkkxkkxk= kA−1 kkAk ·k∆bk| {z }=condindex (A)èíäåêñ îáîçíà÷àåò êîíêðåòíóþ íîðìó - íàïðèìåð cond2 (A).46Ax̃ − 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... 01Ïóñòü D = (λ1 ...λn ) - äèàãîíàëüíàÿ ìàòðèöà.Ðàññìîòðèì çàäà÷ó: íàéòè ìàòðè÷íóþ íîðìó,äèàãîíàëüíîé ìàòðèöû.ïîä÷èíåííóþåâêëèäîâîé,kDk2 = max kDxk2kxk2 =1kDk22 = max kDxk22 = max (Dx, Dx) = (∗)kxk2 =1kxk2 =1ei = (0...0 |{z}1 0...) − n − ìåðíûé áàçèñx=Piiαi ei , (ei , ej ) = δij òîãäà Dx == (∗) = kDk22 = PmaxPα2i =1 i⇒ kDk2 =qPiαi λi eiαi2 λ2i = max λ2i · Pmaximax λ2ii47α2i =1Pαi2λ2i= max λ2iimax λ2iäëÿÓòâåðæäåíèå 1.

kAk2 =| y Y Ax |kxk2 = 1 | {z }maxkyk2 = 1=(y,Ax)Ê-ÁÄîê-âî : |y Y Ax| = |(y, Ax)| ≤ kyk2 kAxk2 ≤ kyk2 kAk2 kxk2AxÅñëè kxk2 = 1, kAxk2 = kAk2 kxk2 , äëÿ y =kxk2¯¯¯¯¯ ¯ xT AT Ax ¯ (Ax, Ax)¯ (Ax)TkAxk2T¯=¯¯¯= kAxk2=Ax¯ = ¯|y Ax| = ¯kAxkkAxkkAxk ¯kAxkÓòâåðæäåíèå 2. kAT k2 = kAk2Äîê-âî : kAT k2 = max ky T AT x| =Óòâåðæäåíèåkxk,kyk=13. kAT Ak =kAT Ak =maxkxk,kyk=1maxkxk,kyk=1kxT Ay| = kAk2 .kAk2 .|y T AT Ax| ≥ max |xT AT Ax| = max kAxk2 = kAk2 .|x|=1Óòâåðæäåíèå 4. Åñëè Q - îðòîãîíàëüíàÿ, ò.å.

QT Q = E, kQk = 1, òîãäà kQAk2 = kAk2 =kAQk2 .18LU-ðàçëîæåíèåñèììåòðè÷íûõíåñèììåòðè÷íûõ ìàòðèö.èèç Ëåêöèè 1:Ðåøåíèå ñèñòåì àëãåáðàè÷åñêèõ óðàâíåíèé.Ðåøåíèå çàäà÷è Ax = b â ïðåäïîëîæåíèè ∃A−1 ñâîäèòñÿ ê ðàçëîæåíèþ ìàòðèöû Aíà ïðîèçâåäåíèå äðóãèõ ìàòðèö. Íàïðèìåð, A = LU (÷àñòíûé ñëó÷àé - ìåòîä Ãàóññà)ïðîèçâåäåíèå íèæíåòðåóãîëüíîé è âåðõíåòðåóãîëüíîé ìàòðèö.Ðåøåíèå çàäà÷è ëèíåéíîé àëãåáðû ñ òðåóãîëüíîé ìàòðèöåé dim n òðåáóåò O(n2 )àðèôìåòè÷åñêèõ îïåðàöèé.Ðàññìîòðèì âîïðîñ - ñêîëüêî ñòåïåíåé ñâîáîäû èìååò çàäà÷à ðàçëîæåíèÿ ìàòðèöû íàòðåóãîëüíûåu11 u12 . . . u1nl11 0 . . .

0 l21 l22 . . . 0   0u22 . . . u2n (aij )n×n =  .... ........ ... .  .···. ···00 . . . unnln1 ln2 . . . lnnÈìååì n2 óðàâíåíèé è n2 + n íåèçâåñòíûõ. Ñëåäîâàòåëüíî n ñòåïåíåé ñâîáîäû.Åñëè óæå åñòü ðàçëîæåíèå A = LU , òî èìååì òàêæå åùå ìíîãî ñïîñîáîâ ðàçëîæåíèÿ A =L0 U 0 , L0 = LD, U 0 = D−1 U , ãäå D - ïðîèçâîëüíàÿ íåâûðîæäåííàÿ äèàãîíàëüíàÿ ìàòðèöà.(Èñïîëüçîâàíû âñå ñòåïåíè ñâîáîäû)48Äëÿ íåâûðîæäåííîé ìàòðèöû A äîëæíî áûòü ljj 6= 0, uii 6= 0.Íå îãðàíè÷èâàÿ îáùíîñòè ìîæíî ïîòðåáîâàòü ïðè ïîñòðîåíèè ljj = 1 ∀j èëè uii = 1 ∀i.Áåðåì âòîðîé âàðèàíò.Äëÿ ïîñòðîåíèÿ ðàçëîæåíèÿ èñïîëüçóåòñÿ îáùèé Àëãîðèòì Êðàóòà nPlik ukj + lij = aij ,i = j, ..., nk=1nP(ljk ukj + ljj uji ) = aji , i = j + 1, ..., nk=1µ0 11 0¶Ñ òî÷êè çðåíèÿ ðåàëèçàöèè ðàñ÷åòîâ íà ÝÂÌ äëÿ ìàòðèöû A =ýòîò àëãîðèò쵶ε bïîäõîäèò ïëîõî, ïîñêîëüêó äàåò U =ñ ìàëûì ε.0 εÄëÿ òîãî, ÷òîáû èçáàâèòüñÿ îò ýòîé ïðîáëåìû, èñïîëüçóþò óìíîæåíèå èñõîäíîé çàäà÷èíà ìàòðèöó ïåðåñòàíîâêè (ñîñòîèò èç 0 è 1 - â êàæäîé ñòîêå è êàæäîì ñòîëáöå òîëüêî ïîîäíîé åäèíèöå)• äëÿ ñòðîê P Ax = P b,• äëÿ ñòîëáöîâ ASS −1 x = b.½L |{z}U x = b −→yLy = bO(n3 ) îïåðàöèéUx = yÄëÿ ñèììåòðè÷íûõ ïîëîæèòåëüíî îïðåäåëåííûõ ìàòðèö [ A = AT > 0, ò.å.

aij = ajiè A = B T B èëè (Ax, x) > 0 ∀x 6= 0 ⇒ aii > 0 ò.ê. (Aei , ei ) > 0 : (0... |{z}1 ...0) ] îäèí èçïîïóëÿðíûõ ìåòîäîâ - ìåòîä êâàäðàòíîãî êîðíÿ (Õîëåöêîãî).Ïðåäñòàâèì A = LLT è íàéäåì òàêîå ðàçëîæåíèå â ÿâíîì âèäå√l11 = a11li1 = sai1 /l11 , i > 1i−1P 2lij , i = 2, ..., nlii = aii −lij =19j=1i−1X1(aij −ljjiljk lik )k=1QR-ðàçëîæåíèå ìàòðèö ìåòîäàìè îòðàæåíèé èâðàùåíèé.Ïðèâåäåíèå ìàòðèö ê ïî÷òè òðåóãîëüíîé ôîðìåîðòîãîíàëüíûìè ïðåîáðàçîâàíèÿìè ïîäîáèÿ.Îáà ìåòîäà ÿâëÿþòñÿ ïðÿìûìè, òðåáóþò ïîðÿäêà O(n3 ) îïåðàöèé, ò.å.

ñòîëüêî æå, ñêîëüêîâ ìåòîäå Ãàóññà. Äëÿ ðåøåíèÿ ñèñòåì Ax = b âðó÷íóþ íå èñïîëüçóþòñÿ.49 îáîèõ ìåòîäàõ ìàòðèöà çàäà÷è Ax = b, N × N ïðè ïîìîùè ïðîñòîãî àëãîðèòìàïðèâîäèòñÿ ê âèäó ïðîèçâåäåíèÿ îðòîãîíàëüíîé ìàòðèöû Q : Q−1 = QT è òðåóãîëüíîéìàòðèöû R. Ïðÿìîé õîä â îáîèõ ìåòîäàõ - ìàíèïóëÿöèè îòðàæåíèé èëè âðàùåíèé ñèñõîäíîé ìàòðèöåé è ïðàâîé ÷àñòüþ. Îáðàòíûé õîä - ðåøåíèå ñèñòåìû ëèíåéíûõ óðàâíåíèéñ òðåóãîëüíîé ìàòðèöåé, àíàëîãè÷åí îáðàòíîìó õîäó â ìåòîäå Ãàóññà. îáîèõ ìåòîäàõ èñïîëüçóåòñÿ ñâîéñòâî îðòîãîíàëüíûõ ìàòðèö - ïðîèçâåäåíèå äâóõîðòîãîíàëüíûõ ìàòðèö áóäåò îïÿòü îðòîãîíàëüíîé ìàòðèöåé.Ïðè èçëîæåíèè ýòèõ ìåòîäîâ ïðèíÿòî èñõîäíóþ çàäà÷ó óìíîæàòü íà îðòîãîíàëüíûåìàòðèöû, ïðè ýòîì ïîëó÷àþòñÿ íîâûå çàäà÷è, èìåþùèå òî æå ðåøåíèå, ÷òî è èñõîäíàÿ:QAx = Qb −→ A1 x = b1 −→ Q1 A1 x = Q1 b1 −→ A2 x = b2 −→ .

. . −→ AK x = bK .(Û) ïðîöåññå ýòèõ ïåðåõîäîâ îáíóëÿþòñÿ ýëåìåíòû ìàòðèö òàê, ÷òîáû â ðåçóëüòàòå ÷åðåçíåêîòîðîå ÷èñëî øàãîâ K ìàòðèöà AK èìåëà áû âåðõíþþ òðåóãîëüíóþ ôîðìó.Ìîæíî áûëî áû ïðèâîäèòü ìàòðèöó ê íèæíåé òðåóãîëüíîé ôîðìå. Ìîæíî áûëî áûâîîáùå èñïîëüçîâàòü âàðèàíòAQx = b −→ A1 x1 = b −→ A1 Q1 x1 = b −→ A2 x2 = b −→ . . . −→ AK xK = b,çàïîìèíàÿ ìàòðèöû Qi , çàòåì íàéòè xK è ïåðåîòðàæàòü (ïåðåâðàùàòü) íàçàä x =QT QT1 QT2 · · · QTK xK .Áóäåì èñõîäèòü èç òðàäèöèîííîãî âàðèàíòà (Û). Ôîðìóëû ìåòîäà âðàùåíèé áîëååíàãëÿäíû. Ïåðâàÿ îðòîãîíàëüíàÿ ìàòðèöà âûáèðàåòñÿ ñëåäóþùèì îáðàçîì: íà ìåñòî ïåðâîéñòðîêè ìàòðèöû A1 çàïèñûâàåòñÿ ñóììà ñòðîê èñõîäíîé ìàòðèöû, óìíîæåííûõ íà cos ϕ è− sin ϕ, íà ìåñòî âòîðîé ñòðîêè - ëèíåéíàÿ êîìáèíàöèÿ ïåðâîé è âòîðîé ñòðîê èñõîäíîéìàòðèöû ñ êîýôôèöèåíòàìè sin ϕ è cos ϕ. Óãîë ϕ âûáèðàåòñÿ òàê, ÷òîáû â ìàòðèöå A1(1)ýëåìåíò a21 áûë ðàâåí íóëþ:cos ϕ = p−a11a211+a221,sin ϕ = pa21a211+ a221.Ýòî ýêâèâàëåíòíî óìíîæåíèþ ñëåâà ìàòðèöû A íà ìàòðèöó âðàùåíèÿcos ϕ − sin ϕ 0 .

. . 0 1a11 a112 . . . a11N sin ϕ cos ϕ0...0 0a122 . . . a12N 001 ... 0 A =  ... ... ... .... ....... . . .. . . . a1N 1 a1N 2 . . . a1N N000 ... 1 = A1 .Çàìåòèì, ÷òî ñòðîêè ìàòðèöû ñ òðåòüåé ïî N -íóþ ïðè ýòîì íå èçìåíÿþòñÿ.Çàòåì âûáèðàåòñÿ ñëåäóþùàÿ îðòîãîíàëüíàÿ ìàòðèöà ýëåìåíòàðíîãî âðàùåíèÿ ìàòðèöû Ãèâåíñàcos ϕ 0 − sin ϕ 0 . . . 0 2a11 a212 . . . a22N 0100...0 0a222 . .

. a22N  sin ϕ 0cos ϕ0 ... 0 22 0a...aA= 01313N  = A2 .001 ... 0 ... ... ... ... . ... ....... . . ..a2N 1 a2N 2 . . . a2N N0000 ... 150Ïðè ýòîì ïðåîáðàçîâàíèè èçìåíÿþòñÿ òîëüêî ïåðâàÿ è òðåòüÿ ñòðîêè. Óãîë ϕ äëÿ ýòîãîâûáèðàåòñÿ òàêa131−a111p.,sinϕ=cos ϕ = p 1(a111 )2 + (a131 )2(a11 )2 + (a131 )2Ïðîäîëæàåì â òîì æå äóõå, ïîêà íå çàíóëèòñÿ âåñü ïåðâûé ñòîëáåö, êðîìå âåðõíåãî ýëåìåíòà.Ïîòîì ïåðåõîäèì êàê áû ê ïîäìàòðèöå, ðàçìåðîì (N − 1) × (N − 1) è îáíóëÿåìâòîðîé ñòîëáåö, êðîìå ýëåìåíòà íà ìåñòå (2,2). Ýòî äåëàåòñÿ ýëåìåíòàðíûìè âðàùåíèÿìè- óìíîæåíèÿìè íà ìàòðèöû Ãèâåíñà1000...

01000 ... 0 0 cos ϕ 0 − sin ϕ . . . 0  0 cos ϕ − sin ϕ 0 . . . 0  0010...0 0 sin ϕ cos ϕ0 ... 0  0 sin ϕ 0cos ϕ . . . 0 , 0···001 ... 0  0001...0.. ... ............ ... ... .......0000 ... 10000... 1Ïðè ýòèõ ïðåîáðàçîâàíèÿõ ïåðâàÿ ñòðîêà íå èçìåíÿåòñÿ.Ôîðìóëû ìåòîäà îòðàæåíèé ïðèâåäåíèÿ ìàòðèöû ê âåðõíåòðåóãîëüíîìó âèäó ìåíååíàãëÿäíû. Â ýòîì ìåòîäå èñõîäíàÿ ìàòðèöà óìíîæàåòñÿ íà ìàòðèöû âèäà Q = I − 2wwT ,NPêîòîðûå íàçûâàþòñÿ ìàòðèöàìè Õàóñõîëäåðà.

 ýòèõ ìàòðèöàõ kwk2 = ( wi )1/2 =i=11, wwT = ((wij )) = ((wi wj )).Ðàññìîòðèì ñâîéñòâà ìàòðèöû Õàóñõîëäåðà. Òî, ÷òî îíà ñèììåòðè÷íàÿ è îðòîãîíàëüíàÿâñåì èçâåñòíî. Âîçüìåì äâà ëþáûõ íå ðàâíûõ âåêòîðà (ñòîëáöà) åäèíè÷íîé äëèíû y, e :y−eè ïîñìîòðèì êàêîå ñâîéñòâî áóäåòkyk2 = kek2 = 1. Âîçüìåì âåêòîð (ñòîëáåö) w =ky − ek2ó ìàòðèöû Õàóñõîëäåðà.P2(yi − ei ) k (yk − ek )yk2(yi − ei )(kyk − (e, y))==2wi wk yk =(2ww · y)i =2kyk2 − 2(e, y) + kek2ky − ekk=12(yi − ei )(1 − (e, y))= (y − e)i ,=2 − 2(e, y)TNXñëåäîâàòåëüíî (I − 2wwT )y = e.Ïðåäïîëîæèì, ÷òî ïåðâûé ñòîëáåö ìàòðèöû A íå êîëëèíåàðåí âåêòîðó e = {1, 0, ..., 0}T ,ò.å.

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

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