Н.И. Ионкин - Электронные лекции (2008) (1135232), страница 2

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

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

Äàëåå,bj1 = aj1è íàéäåí ïåðâûé ñòîëáåö ìàòðèöûíàõîäèì âòîðóþ ñòðîêó ìàòðèöûýëåìåíòû ìàòðèöBèCC.B.Çàòåìb22 = a22 − b21 c12èÏðîäîëæàÿ òàêèì îáðàçîì, íàõîäèìïî ÿâíûì ôîðìóëàì.Óòâåðæäåíèå 1 (Î äîñòàòî÷íîì óñëîâèè ôàêòîðèçàöèè). Ïóñòü âñå ãëàâíûå ìèíîðû ìàòðèöû À îòëè÷íû îò íóëÿ (|Ai | =6 0). Òîãäà ïðåäñòàâëåíèåìàòðèöû A â âèäå (1.4) âîçìîæíî.Ãëàâà 1. ×èñëåííûå ìåòîäû ëèíåéíîé àëãåáðû10Äîêàçàòåëüñòâî.Ai = Bi Ci ⇒ |Ai | = |Bi ||Ci ||Bi |:Çàïèøåì âûðàæåíèå äëÿ|Bi | = b11 b22 . . .

bi−1i−1 bii|{z}|Bi−1 ||Ci | = 1 ⇒ |Ai | = |Bi |Òàêèì îáðàçîì ïîëó÷àåì:bii =|Ai |, i = 1, n|Ai−1 ||A0 | = 1 ⇒ b11 = a111.2.1Ñâÿçü ôàêòîðèçàöèè ñ ìåòîäîì ÃàóññàAx = f(1.7)A = BC(1.8)Ïîäñòàâèâ âûðàæåíèå (1.8) äëÿ ìàòðèöû A â ñèñòåìó (1.7) ïîëó÷èì:B |{z}Cx = fyÒàêèì îáðàçîì, ñèñòåìà (1.7) ñâåëàñü ê äâóì ñèñòåìàì:By = f(1.9)Cx = y(1.10)Çàäà÷à 1. Äîêàçàòü, ÷òî ðåàëèçàöèÿ ôîðìóë (1.5) è (1.6) òðåáóåòm3 −m3îïåðàöèé (ýòî ÷èñëî ñîâïàäàåò ñ ÷èñëîì îïåðàöèé ïðè ñâåäåíèè ìàòðèöûA ê âåðõíåòðåóãîëüíîìó âèäó).Çàïèøåì ïîêîîðäèíàòíî ñèñòåìó (1.9):bi1 y1 + .

. . bii yi = fi , i = 1, mfi −Ïðèbii 6= 0 : yi =i−1Xbil yll=1, i = 1, mbiiÏîñ÷èòàåì ÷èñëî îïåðàöèé äëÿ ðåøåíèÿ (1.9). Ôèêñèðóåì i, ïîëó÷àåìi−1îïåðàöèé óìíîæåíèé è 1 îïåðàöèþ äåëåíèÿ.Èòàê, ïðè ôèêñèðîâàííîìiìû èìååìiîïåðàöèé. Òàê êàêi = 1, m,÷èñëî îïåðàöèé íåîáõîäèìûõ äëÿ ðåàëèçàöèè ñèñòåìû (1.9) ðàâíî:mXi=1i = m + (m + 1) + . . . + 1 =m(m + 1)2òî1.3. Îáðàùåíèå ìàòðèöû ìåòîäîì Ãàóññà-Æîðäàíà11m(m+1) ÷èñëî äåéñòâèé â ïðÿìîì õîäå ìåòîäà Ãàóññà äëÿ ïðåîáðàçî2âàíèÿ ïðàâûõ ÷àñòåé ñèñòåìû. ×èñëî îïåðàöèé äëÿ ðåøåíèÿ (1.10):xi + cii+1 xi+1 + . .

. cim xm = yi , i = 1, mmXxi = yi −cil xll=i+1i òðåáóåòñÿ m − i îïåðàöèé óìíîæåíèÿ. Òàê êàê i =1, m, òî ÷èñëî îïåðàöèé íåîáõîäèìûõ äëÿ ðåàëèçàöèè ôîðìóëû (1.10) ðàâíî:Ïðè ôèêñèðîâàííîìmXi = (m − 1) + (m − 2) + . . . + 1 =i=1m(m − 1)2m(m − 1)2 ÷èñëî äåéñòâèé â îáðàòíîì õîäå ìåòîäà ÃàóññàÂñåãî äåéñòâèé íà ôàêòîðèçàöèþ è íà ðåàëèçàöèþ ôîðìóë (1.9), (1.10)m(m + 1) m(m − 1)m3 − m++3 }22| {z ÷èñëî äåéñòâèé â ìåòîäå ÃàóññàôàêòîðèçàöèÿÇàìå÷àíèå. Åñëè ðåøàåòñÿ ïîñëåäîâàòåëüíîñòü ñèñòåì (1.7) ñ ïîñòîÿííîéìàòðèöåé A è ìåíÿþùèìèñÿ ïðàâûìè ÷àñòÿìè f , òî ðàññìîòðåííûé ïîäõîääà¼ò çíà÷èòåëüíóþ ýêîíîìèþ ïðè ðåøåíèè (1.7), òàê êàê ôàêòîðèçàöèÿ ââèäå (1.8) îñóùåñòâëÿåòñÿ òîëüêî îäèí ðàç, à ìåíÿþòñÿ òîëüêî ïðàâûå ÷àñòè.1.3Îáðàùåíèå ìàòðèöû ìåòîäîì Ãàóññà-ÆîðäàíàA(m × m),ãäe A íåâûðîæäåííàÿ ìàòðèöà (òî åñòü ó íåå ñóùåñòâóåò îáðàòíàÿ)Îïðåäåëåíèå 1.ÌàòðèöàA−1 îáðàòíàÿ äëÿ ìàòðèöû A, åñëèAA−1 = A−1 A = EÎáîçíà÷èìA−1 = X, X = {xij } i, j = 1, m.

Ñèñòåìà óðàâíåíèé ïîðÿäêà m2 :AX = EÄëÿ åå ðåøåíèÿ ìåòîäîì Ãàóññà ïîíàäîáèòñÿ÷èñëî ëåãêî óìåíüøèòü äî2m(1.11)∼ m6îïåðàöèé, îäíàêî ýòî. Îáîçíà÷èìx(j) = (x1j . . . xmj )T , j = 1, m,δ (j) = (0, 0, . . . , 0, |{z}1 , 0, . . . , 0).jÒåïåðü ñèñòåìà (1.11) ñâîäèòñÿ êm ñèñòåìàì ñ m íåèçâåñòíûìè, ñ îäíîéè òîé æå ìàòðèöåé:Ax(j) = δ (j) , j = 1, m(1.12)Ãëàâà 1. ×èñëåííûå ìåòîäû ëèíåéíîé àëãåáðû12Ôàêòîðèçóåì(j)(j)A = BC ⇒ B |Cx{z } = δy (j)By (j) = δ (j)(1.13)Cx(j) = y (j)(1.14)Òàê êàê ìàòðèöà A íå ìåíÿåòñÿ, òî ôàêòîðèçàöèþ íàäî äåëàòü òîëüêîm3 −mîïåðàöèé.32Ïðè ôèêñèðîâàííîì j íà ôîðìóëû (1.13), (1.14) òðåáóåòñÿ m îïåðàöèé,3è òàê êàê j = 1, m, òî íà íèõ òðåáóåòñÿ m îïåðàöèé.4m3 −mÈòàê, íà ðåøåíèå ñèñòåìû (1.11) òðåáóåòñÿîïåðàöèé.3Ýòî ÷èñëî îïåðàöèé òàê æå ìîæíî óìåíüøèòü çà ñ÷¼ò ôîðìû ìàòðèöûîäèí ðàç, ïîýòîìó íà íåå åäèíîâðåìåííî óõîäèòB.Ðàññìîòðèì óðàâíåíèå(1.13) :(j)(j)b11 y1 = 0 ⇒ y1 = 0(j)(j)(j)b21 y1 + b22 y2 = 0 ⇒ y2 = 0(j)...yj−1 = 0(j)bjj yjÒàêèì îáðàçîì,(j)yi(1)= 0 i < j, yj==11bjj , i= j.Âûïèøåì îñòàâøèåñÿ óðàâíåíèÿ:(j)(j)(j)bij yj + bi,j+1 yj+1 + .

. . + bii yi = 0, bii 6= 0 ⇒Pi−1(j)l=j bil yl(j)yi = −, i = j + 1, mbiiÔèêñèðóåì îáà èíäåêñà i è j: òîãäà òðåáóåòñÿ 1 äåëåíèå èæåíèé. Ñíà÷àëà îòïóñòèì èíäåêñi = j + 1, m.(m − j + 1) + (m − j) + . . . + 2 + 1 =Äàëåå îòïóñêàåì èíäåêñmXj=1j = 1, m.(m − j + 1)(m − j + 2)2(m − j + 1)(m − j + 2)2(1.15)m(m+1)(m+2).6 ñèñòåìå (1.14) íè÷åãî óïðîñòèòü íå óäàñòñÿ. Îíà òðåáóåòj = 1, m.ñëåäîâàòåëüíî, âñåãîóìíî-Òàêèì îáðàçîì, ÷èñëî îïåðàöèé:Çàäà÷à 2.

Äîêàçàòü, ÷òî (1.15) ðàâíîñòâèé.(i − j)×èñëî îïåðàöèé ðàâíî:m(m−1)m2=2m(m−1)äåé2m (m−1)äåéñòâèé.2Íà ðåøåíèå ñèñòåìû òðåáóåòñÿ:m3 − mm(m + 1)(m + 2) m2 (m − 1)++= m3362| {z }|{z} |{z}ôàêòîðèçàöèÿ(1.13)(1.14)Òàêèì îáðàçîì, íà ðåøåíèå ñèñòåìû (1.11) ïîíàäîáèòñÿm3îïåðàöèé.1.4. Ìåòîä êâàäðàòíîãî êîðíÿ1.413Ìåòîä êâàäðàòíîãî êîðíÿAx = f,|A| =6 0, AÎïðåäåëåíèå 2.(1.16)ñàìîñîïðÿæåííàÿÌàòðèöà A ñàìîñîïðÿæåííàÿ, åñëèA = A∗ , aij = ajiÏðåäñòàâèì ìàòðèöó A â âèäå:A = S ∗ DS,(1.17)ãäåd11..D= , dii = ±1 i = 1, m.0s11 0S=00dmms12s22s1ms2m  , sii > 0 i = 1, msmm.........Åñëè òàêàÿ ôàêòîðèçàöèÿ âîçìîæíà, òî âîçìîæíî ñëåäóþùåå ïðåäñòàâëåíèå ñèñòåìû(1.16):S ∗ D |{z}Sx = fY∗S DY = f(1.18)Sx = Y(1.19)SÐàññìîòðèì ìåòîä íàõîæäåíèÿ ìàòðèöèDíà ïðèìåðå âåùåñòâåííûõìàòðèö âòîðîãî ïîðÿäêà:A=a11a21s12s22s11s120s22d1100d22S, S∗:d11 s11DS =0D= ATs110S∗ =Ïåðåìíîæèì ìàòðèöûS=S=a12a22èd11 s12d22 s22Ãëàâà 1.

×èñëåííûå ìåòîäû ëèíåéíîé àëãåáðû14∗S (DS) =s11s120s22d11 s110d11 s12d22 s22d11 s211s11 s12 d11=d11 s12 s11d22 s222 + d11 s212Èñõîäÿ èç ñîîòíîøåíèÿ (1.17) è óñëîâèÿ ðàâåíñòâà ìàòðèö, ïîëó÷àåì: a11a12a22d11 s211(∗)s11 s12 d11(∗∗)s212 d11 + d22 s222 (∗ ∗ ∗)===Èç (*) ïîëó÷àåì:d11 = sgna11ps11 = |a11 |Èç (**) ïîëó÷àåì:a12d11 s11s12 =Èç (***) ïîëó÷àåì:d22 = sgn(a22 − s212 d11 )qs22 = |a22 − s212 d11 |Ïåðåéäåì ê îáùåìó ñëó÷àþ:(DS)ij =mXdil slj = dii sijl=1(S ∗ DS)ij =mXsli dll slj = {âûäåëèì i-ûéýëåìåíò}=l=1=i−1XmXsli dll slj + sii dii sij +l=1sli dll slj = aiil=i+1|mXsli dll slj = 0,ò.ê.{z0sli = 0ïðè}l>il=i+1i−1Xsli dll slj + sii dii sij = aij , i ≤ j(1.20)l=1Èç (1.20) ïðèi = j:|sii |2 +i−1X|sli |2 dll = aijl=1dii = sgn(aii −i−1Xl=1|sli |2 dll )(1.21)1.5. Ïðèìåðû è êàíîíè÷åñêèé âèä èòåðàöèîííûõ ìåòîäîâvui−1Xusii = t|aii −|sli |2 dll |15(1.22)l=1Èç (1.20):aii −A = A∗ ,òî òðåáóåòñÿsli dll sljl=1sij =Åñëèi−1X, i<jsii dii∼m36+m(1.23)îïåðàöèé (èçâëå÷åíèå êîðíÿ òàêæåñ÷èòàåòñÿ çà îïåðàöèþ).1.5Ïðèìåðû è êàíîíè÷åñêèé âèä èòåðàöèîííûõ ìåòîäîâ ðåøåíèÿ ÑËÀÓÍåîáõîäèìîñòü èñïîëüçîâàíèÿ èòåðàöèîííûõ ìåòîäîâ çàêëþ÷àåòñÿ â òîì,÷òî ïðè áîëüøîì ïîðÿäêå ÷èñëà óðàâíåíèé ïðÿìûå ìåòîäû òðåáóþò áîëüøîãî ÷èñëà îïåðàöèé.

Ïðè ýòîì ðåàëüíûå äàííûå âñåãäà áûâàþò ñ íåêîòîðîé ïîãðåøíîñòüþ, è, ïîýòîìó, íåò ñìûñëà èñêàòü òî÷íîå ðåøåíèå, òàê êàêåãî ìîæíî íàéòè ñ òîé æå ïîãðåøíîñòüþ, çàòðàòèâ íà ýòî ìåíüøå âðåìåíè.Îñíîâíûå âîïðîñû, ñâÿçàííûå ñ èçó÷åíèåì ìåòîäîâ:1. Âûÿñíåíèå âîïðîñà î ñõîäèìîñòè ìåòîäà.2.

Ïîëó÷åíèå îöåíêè ñêîðîñòè ñõîäèìîñòè ìåòîäàÇàïèøåì ÑËÀÓ:Ax = f,ãäåA(1.24)- êâàäðàòíàÿ íåâûðîæäåííàÿ ìàòðèöàm-ãîïîðÿäêàx = (x1 , ..., xn )T f = (f1 , ..., fn )TÂâåäåì îáîçíà÷åíèÿ:xni - i-ÿ êîîðäèíàòà n-îé èòåðàöèè.x0 - íà÷àëüíîå ïðèáëèæåíèå (âûáîð x0 - ýòî îòäåëüíàÿ çàäà÷à).n0 (ε) - ÷èñëî èòåðàöèé, íåîáõîäèìîå äëÿ äîñòèæåíèÿ çàäàííîéòî÷íî-ñòè.Îá ýôôåêòèâíîñòè ìåòîäà ìû áóäåò ñóäèòü ïîn0 (ε). Ïåðåïèøåì ïîêîîðäè-íàòíî ñèñòåìó (1.24):mXaij xj = fi , i = 1, mj=1Ïåðåãðóïïèðóåì (1.25):i−1Xj=1aij xj + aii xi +mXj=i+1aij xj = fi(1.25)Ãëàâà 1. ×èñëåííûå ìåòîäû ëèíåéíîé àëãåáðû16Ïðåäïîëîæèì, ÷òîaii 6= 0äëÿxi = −i−1Xaijj=11.5.1∀i = 1, m.aiixj −Òîãäà:mXfiaijxj +aaiij=i+1 ii(1.26)Ìåòîä ßêîáèxn+1=−ii−1Xaijaiij=1xnj −mXfiaij nxj +, n = 0, 1, .

. .aaiij=i+1 iiÑ÷èòàåì, ÷òî íà÷àëüíîå ïðèáëèæåíèåx0(1.27)çàäàíî. Î÷åðåäíîå ïðèáëèæåíèåâû÷èñëÿåòñÿ äî òåõ ïîð ïîêà íå áóäåò äîñòèãíóòà çàäàííàÿ òî÷íîñòü:kxn − xk < εÕàðàêòåðèñòèêè:•Ïðîñò â ðåàëèçàöèè•Íåýôôåêòèâåí1.5.2Ìåòîä Çåéäåëÿxn+1=−ii−1Xaijj=1aiixn+1−jmXaij n fixj + , n = 0, 1, . . . x0 −−− çàäàíîaaiiiij=i+1(1.28)Ðàçóìíî îðãàíèçîâàâ âû÷èñëåíèå, ìû ïîëó÷èì, ÷òî àëãîðèòì âû÷èñëåíèÿèòåðàöèé íå ñèëüíî óñëîæíÿåòñÿ.i=1xn+1=−1i=2xn+12mXa1j nf1xj +aa11j=2 11ma21 n+1 X a2j nf2=−x+xj +a22 1aa22j=3 22Òî åñòü ïðè âû÷èñëåíèè i-îé êîîðäèíàòû (n+1)-é èòåðàöèè, ìû èñïîëüçóåìòîëüêî n-þ èòåðàöèþ è êîîðäèíàòû äî i-1 (n+1) èòåðàöèè, à îíè óæå ïîñ÷èòàíû.Ìåòîäû ßêîáè è Çåéäåëÿ ñõîäÿòñÿ ñ îäèíàêîâîé ñêîðîñòüþ, íî óñëîâèå ñõîäèìîñòè ê ìåòîäà Çåéäåëÿ ïðîâåðèòü ïðîùå.1.5.3Ìàòðè÷íûé âèä ìåòîäîâ ßêîáè è ÇåéäåëÿÇàïèøåì ðàçëîæåíèå ìàòðèöû A:0..R1 = aijA = R1 + D + R20a1100.., D =  , R2 = .00ann0.aij...01.5. Ïðèìåðû è êàíîíè÷åñêèé âèä èòåðàöèîííûõ ìåòîäîâ17Òîãäà ñèñòåìó (1.24) ìîæíî çàïèñàòü â ñëåäóþùåì âèäå:R1 x + Dx + R2 x = f,èëèDx = f − R1 x − R2 xÏóñòü ó D ñóùåñòâóåò îáðàòíàÿ ìàòðèöàD−1(òî åñòü(1.29)|D| =6 0, ñëåäîâàòåëü-íî âñå äèàãîíàëüíûå ýëåìåíòû D îòëè÷íû îò 0)Èç (1.29) ïîëó÷èì:x = D−1 f − D−1 R1 x − D−1 R2 xÏîëó÷àåì ìàòðè÷íóþ çàïèñü äëÿ ìåòîäà ßêîáè:xn+1 = D−1 f − D−1 R1 xn − D−1 R2 xnÄëÿ ìåòîäà Çåéäåëÿ:xn+1 = D−1 f − D−1 R1 xn+1 − D−1 R2 xnÄðóãàÿ ôîðìà çàïèñè ìåòîäîâ:Ìåòîä ßêîáèDxn+1 = −R1 xn − R2 xn + fÌåòîä Çåéäåëÿ(D + R1 )xn+1 = −R2 xn + fÏåðåïèøåì ìåòîä ßêîáè, äîáàâèâ ê îáåèì ÷àñòÿì òåì, ÷òîDxnè âîñïîëüçóåìñÿA = R1 + D + R2D(xn+1 − xn ) + Axn = fÀ ìåòîä Çåéäåëÿ çàïèøåòñÿ òàê:(D + R1 )(xn+1 − xn ) + Axn = f )Äëÿ òîãî, ÷òîáû ïîâûñèòü ñêîðîñòü ñõîäèìîñòè ýòèõ ìåòîäîâ ââîäÿò èòåðàöèîííûé ïàðàìåòðτn+1 > 0.Ìåòîä ßêîáèD(xn+1 − xn )+ Axn = fτn+1Ìåòîä Çåéäåëÿ(D + R1 )(xn+1 − xn )+ Axn = f )τn+1Íàëè÷èå ðàçëè÷íûõ ôîðì çàïèñè èòåðàöèîííûõ ìåòîäîâ ïðèâåëî ê ïîÿâëåíèþ êàíîíè÷åñêîé ôîðìû.Ãëàâà 1.

×èñëåííûå ìåòîäû ëèíåéíîé àëãåáðû18Îïðåäåëåíèå 3.Êàíîíè÷åñêîé ôîðìîé çàïèñè äâóõñëîéíîãî èòåðàöèîí-íîãî ìåòîäà ðåøåíèÿ ñèñòåìû óðàâíåíèé âèäà (1.24) íàçûâàåòñÿ åãî çàïèñüâ âèäå:Bn+1xn+1 − xn+ Axn = f,τn+1−1τn+1 > 0, . ∃Bn+1, n = 0, 1, . . . , x0 çàäàíîÇàìå÷àíèå 1:ñóùåñòâåííî.Òðåáîâàíèåτn+1 > 0Çàìå÷àíèå 2: Bn+1 , τn+1 > 0Åñëèτn+1 = τ ,ãäåâëèÿþò íà ñêîðîñòü ñõîäèìîñòè.òî ìåòîä ÷àñòî íàçûâàåòñÿ ìåòîäîì ðåëàêñàöèè.Îïðåäåëåíèå 4.Åñëèτn+1 = τ, Bn+1 = B(íå çàâèñèò îò èòåðàöèè), òîìåòîä íàçûâàåòñÿ ñòàöèîíàðíûì.Îïðåäåëåíèå 5.ÅñëèÎïðåäåëåíèå 6.Íàáîð ïàðàìåòðîâ ïðè êîòîðîì äîñòèãàåòñÿ íàèëó÷øàÿBn+1 = E ,òî ìåòîä íàçûâàåòñÿ ÿâíûì.ñõîäèìîñòü íàçûâàåòñÿ îïòèìàëüíûì.1.5.4Ìåòîä ïðîñòîé èòåðàöèèxn+1 − xn+ Axn = f,τ−1τ > 0, .

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

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