Численные методы. Ионкин (2009), страница 2

Ïî ñâîéñòâó îïðåäåëèòåëåé:det Ai = det Bi · det CiÒàê êàê âñå ýëåìåíòû ãëàâíîé äèàãîíàëè ìàòðèöû Ñ ðàâíû 1, òîdet Ci = 1, ∀i = 1, m.det Bi = b11 · b22 · . . . · bmm ⇒ det Ai = det BiÈñõîäÿ èç ýòîãî óòâåðæäåíèÿ, à òàêæå èç âèäà îïðåäåëèòåëÿbii =ñëåäóåò:detAi, det A0 = 1 ⇒ b11 = a11detAi−1À òàê êàê âñå ãëàâíûå ìèíîðû (1) îòëè÷íû îò íóëÿ, òî âñåïîñòðîåíèþ.det Bi ,biiñóùåñòâóþò è åäèíñòâåííû ïîÐàçëîæåíèå ìàòðèöû íà ìíîæèòåëè. Ñâÿçü ýòîãî ðàçëîæåíèÿ ñ ìåòîäîì Ãàóññà8Ñâÿçü ìåòîäà Ãàóññà ñ ðàçëîæåíèåì ìàòðèöû íà ìíîæèòåëèÐàññìîòðèì ìåòîä Ãàóññà äëÿ ðåøåíèÿ ÑËÀÓ ñ ïðèìåíåíèåì ôàêòîðèçàöèè. ÏóñòüA = B·C ,ãäå B è C ìàòðèöû â ðàçëîæåíèè â ôîðìå (2) (ìàòðèöû ÍÏÒÔ è ÂÒÔ ñîîòâåòñòâåííî). ýòîì ñëó÷àå èñõîäíàÿ ñèñòåìà áóäåò âûãëÿäåòü ñëåäóþùèì îáðàçîì:B·C ·x=fÎáîçíà÷èìC · x = y.(5)Òîãäà ñèñòåìà (5) ðàñïàäàåòñÿ íà äâå ñèñòåìû:B·y =f(6)C · x = y,(7)Âûïèøåì óðàâíåíèÿ ñèñòåìû (6):bi1 y1 + bi2 y2 + .

. . + bii yi = fi , ∀i = 1, mÏîñêîëüêóbii 6= 0,bii , îòêóäà ïîëó÷èì:Pfi − i−1l=1 bil ylyi =, i = 1, mbiiìû ìîæåì ðàçäåëèòü íà(8)Ïîñ÷èòàåì ÷èñëî îïåðàöèé óìíîæåíèÿ è äåëåíèÿ, òðåáóåìûõ äëÿ ðåàëèçàöèè ïîëó÷åííîé ôîðìóëû. Äëÿ êàæäîãî óðàâíåíèÿ ýòîé ñèñòåìû ïîëó÷àåì (i 1) îïåðàöèé óìíîæåíèÿ è 1 îïåðàöèþäåëåíèÿ. Òî åñòü ïðè êàæäîì ôèêñèðîâàííîì i ïîëó÷àåòñÿ i îïåðàöèé. À òàê êàê i ìîæåò ìåíÿòüñÿ îò 1 äî m, ïîëó÷àåì ôîðìóëó:mXm · (m + 1)2i = 1 + 2 + . .

. + (m − 1) + m =i=1Ìû ïîëó÷èëè â òî÷íîñòè ÷èñëî øàãîâ, òðåáóåìûõ äëÿ ïðåîáðàçîâàíèÿ ïðàâûõ ÷àñòåé ñèñòåìû(6) ïðè ïðÿìîì õîäå.Äëÿ ñèñòåìû (7) îöåíêàm·(m−1)ïîëó÷àåòñÿ àíàëîãè÷íî.2Çàäà÷à. Ïîêàçàòü, ÷òî ôàêòîðèçàöèÿ ìàòðèöû À òðåáóåòm3 −mîïåðàöèé óìíîæåíèÿ è3äåëåíèÿ.Äîêàçàòåëüñòâî. Âîñïîëüçóåìñÿ ôîðìóëàìè äëÿ ôàêòîðèçàöèè èç ïðåäûäóùåãî ïàðàãðàôà:bij = aij −j−1Xbil clj ,i≥jl=1Äëÿ âû÷èñëåíèÿ êàæäîãîbijïîòðåáóåòñÿ j-1 îïåðàöèÿ óìíîæåíèÿ. Îòïóñòèì èíäåêñ j:iXi(i − 1)(j − 1) =2j=1Òåïåðü îòïóñòèì èíäåêñ i:mXi(i − 1)i=12mm1X 2 1X=i −i2 i=12 i=1Îáðàùåíèå ìàòðèö ìåòîäîì Ãàóññà-Æîðäàíà9Âòîðàÿ ñóììà âû÷èñëÿåòñÿ ýëåìåíòàðíî, çíà÷åíèå ïåðâîé ñóììû íàì èçâåñòíî èç øêîëüíîãîm(m+1)(2m+1).êóðñà 6m(m + 1)(2m + 1) m(m + 1)(m − 1)m(m + 1)−=1246Äàëåå ñëåäóþùàÿ ôîðìóëà:aij −cijbil cljl=1cij =Äëÿ âû÷èñëåíèÿ êàæäîãîi−1Pbii,i<jïîòðåáóåòñÿ j-1 îïåðàöèÿ óìíîæåíèÿ è 1 îïåðàöèÿ äåëåíèÿ.

Îòïó-ñòèì èíäåêñ i:j−1Xj=i=1(j − 1)j2Îòïóñòèì èíäåêñ j:mmm1X1X 2 1Xm(m + 1)(2m + 1) m(m + 1)−=(j − 1)j =j −j=2 j=12 j=12 j=1124(m − 1)m(m + 1)6Ñóììèðóÿ ñ ïðåäûäóùåì ðåçóëüòàòîì, ïîëó÷àåì îêîí÷àòåëüíûé îòâåò:2(m − 1)(m + 1)m(m3 − m)=63Ïîëó÷àåòñÿ, ÷òî ñóììàðíàÿ ñëîæíîñòü ìåòîäà ñîâïàäàåò ñî ñëîæíîñòüþ êëàññè÷åñêîãî ìåòîäà Ãàóññà.Çàìå÷àíèå. Ôàêòîðèçàöèÿ äàåò ñóùåñòâåííûé âûèãðûø â òîì ñëó÷àå, åñëè ðåøàåòñÿ ÑËÀÓñ ïîñòðîÿíîé ìàòðèöåéŸ3Aè ìåíÿþùèìèñÿ ïðàâûìè ÷àñòÿìèf.Îáðàùåíèå ìàòðèö ìåòîäîì Ãàóññà-ÆîðäàíàÐàññìîòðèì ñèñòåìó ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé:Ax = f, A ∈ Rm×m , |A| =6 0(1)Îïðåäåëåíèå. Ìàòðèöà A−1 íàçûâàåòñÿ îáðàòíîé ê ìàòðèöå A, åñëè âûïîëíåíî:A · A−1 = A−1 · A = EÎáîçíà÷èìX = A−1 :A · X = E, X = xij i, j ∈ 1, mÇàïèøåì ÑËÀÓ ïîðÿäêà m (cm2íåèçâåñòíûìè):A·X =E(2)Îáðàùåíèå ìàòðèö ìåòîäîì Ãàóññà-Æîðäàíà10Äëÿ ðåøåíèÿ ïîäîáíîé ñèñòåìû êëàññè÷åñêèì ìåòîäîì Ãàóññà ïîòðåáóåòñÿ ïîðÿäêà3öèé. Ïîêàæåì, ÷òî ÷èñëî äåéñòâèé ìîæíî ñíèçèòü äî m .

Äëÿ ýòîãî îáîçíà÷èì:mXδij =ail Xljm6îïåðà-(3)l=1X (j) = (x1j , x2j , . . . , xmj )T , j = 1, m(4)δ (j) = (|{z}0 , 0, . . . , |{z}0 , |{z}1 , |{z}0 , . . . , |{z}0 )1j−1jj+1(5)mÒåïåðü ñèñòåìà (2) ñâîäèòñÿ ê m ñèñòåìàì ñ m óðàâíåíèÿìè â êàæäîé. Ïðè ýòîì ìàòðèöà Àîäíà è òà æå äëÿ âñåõ ñèñòåì:A · x(j) = δ (j) , j = 1, m(6)Ôàêòîðèçóåì ìàòðèöó À è ïåðåïèøåì ïîëó÷åííûå ñèñòåìû (6):A=B·CB = {bi,j , i ≥ j; i, j ∈ 1, m} (Íèæíÿÿ ïî÷òè òðåóãîëüíàÿ ôîðìà) 1, i = j; ci,j , i < j; (i, j ∈ i, m) (Âåðõíÿÿ òðåóãîëüíàÿ ôîðìà)C=0, i > j;Îáîçíà÷èìCx(j) = y (j) .Ñèñòåìà óðàâíåíèé ïðèìåò âèä:By (j) = δ (j)(7)Cx(j) = y (j)(8)Åù¼ ðàç îòìåòèì òîò ôàêò, ÷òî ìàòðèöà A îñòàåòñÿ îäèíàêîâîé äëÿ âñåõ m ñèñòåì. Ñîîòâåòñòâåííî, ôàêòîðèçàöèþ ìàòðèöû À íóæíî ïðîâîäèòü òîëüêî îäèí ðàç. Ïðè ôèêñèðîâàííîì j2äëÿ ðåøåíèÿ ôîðìóë (7) è (8) òðåáóåòñÿ m îïåðàöèé. À ïîñêîëüêó îáùåå êîëè÷åñòâî ñèñòåì3ðàâíî m, îáùàÿ ñëîæíîñòü ðåøåíèÿ ñîñòàâëÿåò m . Ñóììèðóÿ ýòîò ïîêàçàòåëü ñ ÷èñëîì îïå4m3 −mm3 −mðàöèé, òðåáóåìûõ äëÿ ôàêòîðèçàöèè ìàòðèöû A () ïîëó÷àåì îáùóþ ñëîæíîñòü.33Ïîëó÷åííàÿ îöåíêà íå ïðåäåë.

Äëÿ åå óëó÷øåíèÿ ðàññìîòðèì ñòðóêòóðó ìàòðèöû B ïîäðîáíåå.Ðàñïèøåì ñèñòåìó (7):(j)(j)b11 y1 = 0 ⇒ y1 = 0(j)(j)(j)b21 y1 b22 y2 = 0 ⇒ y2 = 0...(j)yi−1 = 0(j)yi = 1Òàêèì îáðàçîì(j)(j)yi = 0, i < j; yj =1,bjji = j.Îñòàâøèåñÿ óðàâíåíèÿ:(j)(j)(j)bi,j yj + bi,j+1 yj+1 + . . . + bi,i yi = 0, bii 6= 0 ⇒Ìåòîä êâàäðàòíîãî êîðíÿ11(j)Pi−1(j)yibi,l yl, i = j + 1, m.biil=j=−Îöåíèì ÷èñëî îïåðàöèé äëÿ ðåàëèçàöèè óêàçàííîãî ìåòîäà ðåøåíèÿ. Ôèêñèðóåì èíäåêñû i èj: â ýòîì ñëó÷àå íàì ïîòðåáóåòñÿi = j + 1, m(i − j)óìíîæåíèé è 1 äåëåíèå.

Ñíà÷àëà îòïóñòèì èíäåêñ i (), òîãäà ÷èñëî îïåðàöèé áóäåò ðàâíî:(m − j + 1) + (m − j) + . . . + 2 + 1 =Äàëåå îòïóñòèì èíäåêñ j (j = 1, m(m − j + 1)(m − j + 2)2):mX(m − j + 1)(m − j + 2)2j=1Çàäà÷à. Ïîêàçàòü, ÷òî ñóììà(9) ðàâíàÄîêàçàòåëüñòâî. Ïðîâåäåì çàìåíó:m(m+1)(m+2).6k = m − j + 1:mXk(k + 1)k=1(9)2Îòêóäà ñëåäóåò, ÷òî ïåðâàÿ ñóììà ðàâíà=mXkk=12+mXk2k=12k(k+1)k(k+1)(2k+1), à âòîðàÿ , ÷òî â ñóììå è äàåò òðå412áóåìóþ îöåíêó.m(m−1)äåéñòâèé, à, ïîñêîëüêó òàêèõ ñèñòåì m øòóê (ò.ê.

j = 1, m ), òî2m2 (m−1)äëÿ èõ ðåøåíèÿ ïîòðåáóåòñÿîïåðàöèé. Òàêèì îáðàçîì, ñóììàðíîå êîëè÷åñòâî îïåðàöèé,2òðåáóåìûõ íà ðåøåíèå (1) ðàâíî:Ñèñòåìà (8) òðåáóåòm3 − m3 }| {zôàêòîðèçàöèÿ (1)Ÿ4m(m + 1)(m + 2) m2 (m − 1)++= m362|{z} | {z}ðåøåíèå (7)ðåøåíèå (8)Ìåòîä êâàäðàòíîãî êîðíÿÐàññìîòðèì ñèñòåìó ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé:Ax = f, A ∈ Rm×m , |A| =6 0(1)Îïðåäåëåíèå. Ìàòðèöà A íàçûâàåòñÿ ýðìèòîâîé (èëè ñàìîñîïðÿæåííîé) ìàòðèöåé, åñëèA = A∗ , aij = ajiÏóñòü A - ýðìèòîâà ìàòðèöà.

Ïðåäñòàâèì åå â âèäå:A = S ∗ DSãäå:D - äèàãîíàëüíàÿ ìàòðèöà dii = ±1; i = 1, m,S - âåðõíÿÿ òðåóãîëüíàÿ ìàòðèöà sij > 0, i < j, i, j = 1, m,(2)Ìåòîä êâàäðàòíîãî êîðíÿS∗12- ìàòðèöà, ñîïðÿæåííàÿ ê S.Ðàññìîòðèì ìåòîä íàõîæäåíèÿ ìàòðèöêà:SD íà ïðèìåðå âåùåñòâåííûõ ìàòðèö âòîðîãî ïîðÿäa12s11 s12, S =a220 s220d11 0, D =s220 d22èa11a21sS ∗ = 11s12A=Ïåðåìíîæèì ìàòðèöûS ∗DèS:d11 s11 d11 s12DS =0d22 s22, s11 0d11 s11 d11 s12d11 s211d11 s11 s12S DS ==s12 s220d22 s22d11 s11 s12 d11 s212 + d11 s222∗Èç (2) è óñëîâèÿ ðàâåíñòâà ìàòðèö ïîëó÷àåì ñîîòíîøåíèÿ:a11 = d11 s211(3)a12 = d11 s11 s12(4)a22 = d11 s212 + d11 s222(5)Èç óðàâíåíèÿ (3) èìååì:d11 = sign(a11 )ps11 = |a11 |Èç óðàâíåíèÿ (4):s12 =a12s11 d11Èç óðàâíåíèÿ (5):d22 = sign(a22 − d11 s212 )qs22 = |a22 − d11 s212 |Òàêèì îáðàçîì, âñå ýëåìåíòû ìàòðèöSèDîäíîçíà÷íî îïðåäåëåíû.A ñ m ñòðîêàm ñòîëáöàìè è íàéäåì äëÿ íåå ðàçëîæåíèå â âèäå (2).

Èç òîãî, ÷òî D ÿâëÿåòñÿ äèàãîíàëüíîéÐàññìîòðèì òåïåðü íåâûðîæäåííóþ ýðìèòîâó (èëè ñèììåòðè÷åñêóþ) ìàòðèöóìè èìàòðèöåé, ïîëó÷àåì:(DS)ij =mXdil slj = dii sij ,sii > 0l=1Äàëåå çàïèøåì âûðàæåíèå äëÿaij :aij = (S ∗ DS)ij =mXsli dll slj ,i≤j(6)l=1Âûäåëèì èç ñóììûi-ûéýëåìåíò:∗aij = (S DS)ij =i−1Xl=1sli dll slj + sii dii sij +mXl=i+1sli dll slj(7)Ïðèìåðû è êàíîíè÷åñêèé âèä èòåðàöèîííûõ ìåòîäîâ ðåøåíèÿ ÑËÀÓÏðèj=i13áóäåì èìåòü:∗aii = (S DS)ii =i−1Xsli dll sli + sii dii sii +mXsli dll slil=i+1l=1 ñèëó âèäà ìàòðèöû S sli = 0,l > i, ïîýòîìó ïîñëåäíÿÿ èç ñóìì áóäåò ðàâíà 0. Ó÷èòûâàÿ2ðàâåíñòâî sli sli = |sli | , ïåðåïèøåì ïîëó÷èâøååñÿ âûðàæåíèå â âèäå:s2ii dii= aii −i−1X|sli |2 dlll=1Òåïåðü ìîæíî çàïèñàòü ôîðìóëû äëÿ ýëåìåíòîâ ìàòðèödii = sign(aii −i−1XSèD:|sli |2 dll )l=1vui−1Xutsii = |aii −|sli |2 dll |l=1Èç (7) ïîëó÷èì:sij =aij −Pi−1l=1sli dll slj −sii diiPml=i+1sli dll sljÏî äàííûì ôîðìóëàì îäíîçíà÷íî íàõîäÿòñÿ âñå ýëåìåíòû ìàòðèöSèD.Ðàññìîòðèì ïðèìåíåíèå äàííîãî ðàçëîæåíèÿ ê ðåøåíèþ ñèñòåì ëèíåéíûõ àëãåáðàè÷åñêèõóðàâíåíèé:Ax = fS ∗ DSx = fÎáîçíà÷èìSx = y ,ïîëó÷èì äâå ñèñòåìû ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé:S ∗ Dy = f,Sx = y;Äëÿ ðåøåíèÿ ýòèõ äâóõ ñèñòåì ïîòðåáóåòñÿ ïîðÿäêàm3óìíîæåíèé è äåëåíèé, à òàêæå6mèç-âëå÷åíèé êâàäðàòíîãî êîðíÿ.Ÿ5Ïðèìåðû è êàíîíè÷åñêèé âèä èòåðàöèîííûõ ìåòîäîâ ðåøåíèÿ ÑËÀÓÐàññìîòðèì ÑËÀÓ:Ax = f,ãäåA ìàòðèöà ðàçìåðà(m × m), |A| =6 0,x = (x1 , .

. . , xm )T ,(1)Ïðèìåðû è êàíîíè÷åñêèé âèä èòåðàöèîííûõ ìåòîäîâ ðåøåíèÿ ÑËÀÓ14f = (f1 , . . . , fm )T .Èç íåâûðîæäåííîñòè ìàòðèöûAñëåäóåò, ÷òî ðåøåíèå ñèñòåìû (1) ñóùåñòâóåò è åäèíñòâåííî.Ïåðåïèøåì ñèñòåìó (1) â âèäå:mXaij xj = fi ,i = 1, . . . , mj=1Âûäåëèì èç ñóììûi-îåñëàãàåìîå:i−1Xaij xj + aii xi +j=1Ïóñòüaii 6= 0,xni i-óþx0êîìïîíåíòón-îé(2)èòåðàöèè.

Çàïèøåì ìåòîä ßêîáè (Ìß):i−1mXXaij naij nfi−xj −xj ,aii j=1 aiiaiij=i+1n = 0, 1, . . . ; i = 1, . . . , m- íà÷àëüíîå ïðèáëèæåíèå. Çàïèøåì ìåòîä Çåéäåëÿ (ÌÇ):xn+1=ix0i = 1, . . . , mxi :Pi−1Pfi − j=1aij xj − mj=i+1 aij xjxi =aiixn+1=iÂåêòîðaij xj = fi ,j=i+1òîãäà ìîæíî âûðàçèòüÎáîçíà÷èì ÷åðåçÇàäàí âåêòîðmXi−1mXXaij n+1aij nfi−xj −xj ,aii j=1 aiiaiij=i+1n = 0, 1, . .

. ; i = 1, . . . , m;òàêæå èçíà÷àëüíî çàäàí.Ïðåäñòàâèì ìàòðèöóAâ âèäå:A = R1 + D + R2 ,ãäå00 ··· 0 a210 · · · 0R1 =  ........ ....am1 am2 · · · 0 íèæíåòðåóãîëüíàÿ ìàòðèöà ñ íóëÿìè íà ãëàâíîé äèàãîíàëè,a11 0 · · ·0 0 a22 · · ·0 D =  .... ....  ....00 · · · amm äèàãîíàëüíàÿ ìàòðèöà,0 a12 · · · a1m0 0 · · · a2m R2 =  .. .. . .. . . ...0 0 ···0(3)Ïðèìåðû è êàíîíè÷åñêèé âèä èòåðàöèîííûõ ìåòîäîâ ðåøåíèÿ ÑËÀÓ15 âåðõíåòðåóãîëüíàÿ ìàòðèöà ñ íóëÿìè íà ãëàâíîé äèàãîíàëè. Î÷åâèäíî, òàêîå ðàçëîæåíèåâñåãäà îñóùåñòâèìî.

Ïîäñòàâèì ïðåäñòâàëåíèå (3) â (1):(R1 + D + R2 )x = fDx = f − R1 x − R2 xÏðåäïîëîæèì òåïåðü, ÷òî∃D−1 .Òîãäà:x = D−1 f − D−1 R1 x − D−1 R2 xÌåòîä ßêîáè ìîæíî çàïèñàòü ñëåäóþùèì îáðàçîì:xn+1 = D−1 f − D−1 (R1 + R2 )xnèëèD(xn+1 − xn ) + Axn = fÌåòîä Çåéäåëÿ:xn+1 = D−1 f − D−1 R1 xn+1 − D−1 R2 xnèëè(D + R1 )(xn+1 − xn ) + Axn = fÈç ïðèâåäåííûõ çàïèñåé âèäíî, ÷òî èòåðàöèîííûå ìåòîäû ìîæíî çàïèñàòü â ðàçëè÷íîì âèäå.Ïîýòîìó öåëåñîîáðàçíî èìåòü åäèíóþ ôîðìó çàïèñè èòåðàöèîííîãî ìåòîäà.Îïðåäåëåíèå. Êàíîíè÷åñêîé ôîðìîé çàïèñè äâóõñëîéíîãî èòåðàöèîííîãî ìåòîäà ðåøåíèÿÑËÀÓ (1) íàçûâàåòñÿ åãî çàïèñü â âèäå:Bn+1xn+1 − xn+ Axn = f,τn+1n = 0, 1, . .

. ; x0 çàäàí(4)τn+1 > 0 - èòåðàöèîííûé ïàðàìåòð,Bn+1 - îáðàòèìàÿ ìàòðèöà.ÅñëèBn+1 = E ,òî ìåòîä (4) íàçûâàåòñÿ ÿâíûì. ÅñëèBn+1 = B , τn+1 = τ ,òî ìåòîä (4)íàçûâàåòñÿ ñòàöèîíàðíûì.Ìåòîä ïðîñòîé èòåðàöèè (ÏÈ, èëè ìåòîä ðåëàêñàöèè) èìååò ñëåäóþùèé âèä:xn+1 − xn+ Axn = f,ττ >0Ðàññìîòðèì áîëåå ïîäðîáíî ïîïåðåìåííî-òðåóãîëüíûé èòåðàöèîííûé ìåòîä (ÏÒÈÌ):(E + ωR1 )(E + ωR2 )Çäåñüτn+1 > 0, ω > 0xn+1 − xn+ Axn = f,τn+1 èòåðàöèîííûå ïàðàìåòðû,a0 a21 a222R1 =  .... ..am1 am2112n = 0, 1, . .