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

Ñâÿçü ýòîãî ðàçëîæåíèÿ ñìåòîäîì Ãàóññà9Òåïåðü èç ôîðìóëû ýëåìåíòà ïðîèçâåäåíèÿ ìàòðèö âûäåëèì ñëàãàåìîåñbij :aij =j−1Xbil clj + bij cjj +l=1Èç âèäà ìàòðèöûCmXbil cljl=j+1ñëåäóåò, ÷òîmXbil clj = 0l=j+1Òàêèì îáðàçîì, ìîæíî çàïèñàòü:bij = aij −j−1Xbil clj ,i≥j(4)l=1Ëåãêî âèäåòü, ÷òî ôîðìóëû (3) è (4) ïîçâîëÿþò âû÷èñëèòü âñå ýëåìåíòûìàòðèöBèC.Äîêàæåì ñóùåñòâîâàíèå è åäèíñòâåííîñòü ôàêòîðèçàöèè ìàòðèöû A.Óòâåðæäåíèå.

Ïóñòü âñå ãëàâíûå ìèíîðû ìàðèöû À îòëè÷íû îò 0:A1 = a11a1,1 a1,2 6= 0, · · · , Ai 6= 0, ∀i = 1, m6 0, A2 = =a2,1 a2,2 Òîãäà ðàçëîæåíèå â ôîðìå (2) ñóùåñòâóåò è åäèíñòâåííî.Äîêàçàòåëüñòâî. Ïî ñâîéñòâó îïðåäåëèòåëåé:det Ai = det Bi · det CiÒàê êàê âñå ýëåìåíòû ãëàâíîé äèàãîíàëè ìàòðèöû Ñ ðàâíû 1, òîdet Ci =1, ∀i = 1, m.det Bi = b11 · b22 · . . . · bmm ⇒ det Ai = det BiÈñõîäÿ èç ýòîãî óòâåðæäåíèÿ, à òàêæå èç âèäà îïðåäåëèòåëÿdet Bi , ñëå-äóåò:bii =detAi, det A0 = 1 ⇒ b11 = a11detAi−1À òàê êàê âñå ãëàâíûå ìèíîðû (1) îòëè÷íû îò íóëÿ, òî âñåè åäèíñòâåííû ïî ïîñòðîåíèþ.bii ñóùåñòâóþòÐàçëîæåíèå ìàòðèöû íà ìíîæèòåëè. Ñâÿçü ýòîãî ðàçëîæåíèÿ ñìåòîäîì Ãàóññà10Ñâÿçü ìåòîäà Ãàóññà ñ ðàçëîæåíèåì ìàòðèöû íà ìíîæèòåëèÐàññìîòðèì ìåòîä Ãàóññà äëÿ ðåøåíèÿ ÑËÀÓ ñ ïðèìåíåíèåì ôàêòîðèçàöèè. Ïóñòü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,ìû ìîæåì ðàçäåëèòü íàyi =fi −bii ,îòêóäà ïîëó÷èì:Pi−1l=1 bil ylbii, i = 1, m(8)Ïîñ÷èòàåì ÷èñëî îïåðàöèé óìíîæåíèÿ è äåëåíèÿ, òðåáóåìûõ äëÿ ðåàëèçàöèè ïîëó÷åííîé ôîðìóëû. Äëÿ êàæäîãî óðàâíåíèÿ ýòîé ñèñòåìûïîëó÷àåì (i 1) îïåðàöèé óìíîæåíèÿ è 1 îïåðàöèþ äåëåíèÿ.

Òî åñòüïðè êàæäîì ôèêñèðîâàííîì i ïîëó÷àåòñÿ i îïåðàöèé. À òàê êàê i ìîæåòìåíÿòüñÿ îò 1 äî m, ïîëó÷àåì ôîðìóëó:mXi = 1 + 2 + . . . + (m − 1) + m =i=1m · (m + 1)2Ìû ïîëó÷èëè â òî÷íîñòè ÷èñëî øàãîâ, òðåáóåìûõ äëÿ ïðåîáðàçîâàíèÿïðàâûõ ÷àñòåé ñèñòåìû (6) ïðè ïðÿìîì õîäå.m·(m−1)Äëÿ ñèñòåìû (7) îöåíêàïîëó÷àåòñÿ àíàëîãè÷íî.2Çàäà÷à. Ïîêàçàòü, ÷òî ôàêòîðèçàöèÿ ìàòðèöû À òðåáóåòðàöèé óìíîæåíèÿ è äåëåíèÿ.m3 −mîïå3Ðàçëîæåíèå ìàòðèöû íà ìíîæèòåëè. Ñâÿçü ýòîãî ðàçëîæåíèÿ ñìåòîäîì Ãàóññà11Äîêàçàòåëüñòâî. Âîñïîëüçóåìñÿ ôîðìóëàìè äëÿ ôàêòîðèçàöèè èç ïðåäûäóùåãî ïàðàãðàôà:bij = aij −j−1Xi≥jbil clj ,l=1bijÄëÿ âû÷èñëåíèÿ êàæäîãîïîòðåáóåòñÿ j-1 îïåðàöèÿ óìíîæåíèÿ. Îò-ïóñòèì èíäåêñ j:iX(j − 1) =j=1i(i − 1)2Òåïåðü îòïóñòèì èíäåêñ i:mXi(i − 1)m2i=1m1X 2 1X=i −i2 i=12 i=1Âòîðàÿ ñóììà âû÷èñëÿåòñÿ ýëåìåíòàðíî, çíà÷åíèå ïåðâîé ñóììû íàìm(m+1)(2m+1)èçâåñòíî èç øêîëüíîãî êóðñà .6(m − 1)m(m + 1)m(m + 1)(2m + 1) m(m + 1)−=1246Äàëåå ñëåäóþùàÿ ôîðìóëà:aij −bil cljl=1cij =Äëÿ âû÷èñëåíèÿ êàæäîãîi−1Pbiicij,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Îáðàùåíèå ìàòðèö ìåòîäîì Ãàóññà-Æîðäàíà12Ñóììèðóÿ ñ ïðåäûäóùåì ðåçóëüòàòîì, ïîëó÷àåì îêîí÷àòåëüíûé îòâåò: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)Äëÿ ðåøåíèÿ ïîäîáíîé ñèñòåìû êëàññè÷åñêèì ìåòîäîì Ãàóññà ïîòðåáó6åòñÿ ïîðÿäêà m îïåðàöèé.

Ïîêàæåì, ÷òî ÷èñëî äåéñòâèé ìîæíî ñíèçèòü3äî m . Äëÿ ýòîãî îáîçíà÷èì:δij =mXail Xlj(3)l=1X (j) = (x1j , x2j , . . . , xmj )T , j = 1, m(4)Îáðàùåíèå ìàòðèö ìåòîäîì Ãàóññà-Æîðäàíà13δ (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 ñèñòåì.

Ñîîòâåòñòâåííî, ôàêòîðèçàöèþ ìàòðèöû À íóæíî ïðîâîäèòüòîëüêî îäèí ðàç. Ïðè ôèêñèðîâàííîì j äëÿ ðåøåíèÿ ôîðìóë (7) è (8)2òðåáóåòñÿ m îïåðàöèé. À ïîñêîëüêó îáùåå êîëè÷åñòâî ñèñòåì ðàâíî m,3îáùàÿ ñëîæíîñòü ðåøåíèÿ ñîñòàâëÿåò m . Ñóììèðóÿ ýòîò ïîêàçàòåëüm3 −mñ ÷èñëîì îïåðàöèé, òðåáóåìûõ äëÿ ôàêòîðèçàöèè ìàòðèöû A ()34m3 −mïîëó÷àåì îáùóþ ñëîæíîñòü. Ïîëó÷åííàÿ îöåíêà íå ïðåäåë. Äëÿ3åå óëó÷øåíèÿ ðàññìîòðèì ñòðóêòóðó ìàòðèöû B ïîäðîáíåå.Ðàñïèøåì ñèñòåìó (7):(j)(j)b11 y1 = 0 ⇒ y1 = 0(j)(j)(j)b21 y1 b22 y2 = 0 ⇒ y2 = 0...(j)yi−1(j)=0yi = 1Îáðàùåíèå ìàòðèö ìåòîäîì Ãàóññà-ÆîðäàíàÒàêèì îáðàçîì(j)(j)yi = 0, i < j; yj =1,bjj14i = j.Îñòàâøèåñÿ óðàâíåíèÿ:(j)(j)(j)bi,j yj + bi,j+1 yj+1 + .

. . + bi,i yi = 0, bii 6= 0 ⇒(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) ðàâíàÄîêàçàòåëüñòâî. Ïðîâåäåì çàìåíó:mXk(k + 1)k=12=(9)m(m+1)(m+2).6k = m − j + 1:mXkk=12Îòêóäà ñëåäóåò, ÷òî ïåðâàÿ ñóììà ðàâíà+mXk2k=12k(k+1)k(k+1)(2k+1), à âòîðàÿ ,412÷òî â ñóììå è äàåò òðåáóåìóþ îöåíêó.m(m−1)äåéñòâèé, à, ïîñêîëüêó òàêèõ ñèñòåì m2m2 (m−1)øòóê (ò.ê. j = 1, m ), òî äëÿ èõ ðåøåíèÿ ïîòðåáóåòñÿîïåðàöèé.2Òàêèì îáðàçîì, ñóììàðíîå êîëè÷åñòâî îïåðàöèé, òðåáóåìûõ íà ðåøåíèåÑèñòåìà (8) òðåáóåò(1) ðàâíî:m3 − m3 }| {zôàêòîðèçàöèÿ (1)+m(m + 1)(m + 2) m2 (m − 1)+= m362|{z} | {z }ðåøåíèå (7)ðåøåíèå (8)Ìåòîä êâàäðàòíîãî êîðíÿŸ415Ìåòîä êâàäðàòíîãî êîðíÿÐàññìîòðèì ñèñòåìó ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé:Ax = f, A ∈ Rm×m , |A| =6 0(1)Îïðåäåëåíèå. Ìàòðèöà A íàçûâàåòñÿ ýðìèòîâîé (èëè ñàìîñîïðÿæåííîé) ìàòðèöåé, åñëèA = A∗ , aij = ajiÏóñòü A - ýðìèòîâà ìàòðèöà. Ïðåäñòàâèì åå â âèäå:A = S ∗ DS(2)ãäå:D - äèàãîíàëüíàÿ ìàòðèöà dii = ±1; i = 1, m,S - âåðõíÿÿ òðåóãîëüíàÿ ìàòðèöà sij > 0, i < j, i, j = 1, m,S ∗ - ìàòðèöà, ñîïðÿæåííàÿ ê S.Ðàññìîòðèì ìåòîä íàõîæäåíèÿ ìàòðèö S è D íà ïðèìåðå âåùåñòâåííûõìàòðèö âòîðîãî ïîðÿäêà:a11 a12A=a21 a22s11 0∗S =s12 s22Ïåðåìíîæèì ìàòðèöûS ∗Ds11 s12, S =0 s22d11 0, D =0 d22S:d11 s11 d11 s12DS =0d22 s22è,∗S DS =s11 0s12 s22 d11 s11 d11 s12d11 s211d11 s11 s12=0d22 s22d11 s11 s12 d11 s212 + d11 s222Èç (2) è óñëîâèÿ ðàâåíñòâà ìàòðèö ïîëó÷àåì ñîîòíîøåíèÿ:a11 = d11 s211(3)a12 = d11 s11 s12(4)Ìåòîä êâàäðàòíîãî êîðíÿ16a22 = 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ñòðîêàìè èâèäå (2).

Èç òîãî, ÷òîDmñòîëáöàìè è íàéäåì äëÿ íåå ðàçëîæåíèå âÿâëÿåòñÿ äèàãîíàëüíîé ìàòðèöåé, ïîëó÷àåì:(DS)ij =mXsil dlj = dii sij ,sii > 0l=1Äàëåå çàïèøåì âûðàæåíèå äëÿaij :∗aij = (S DS)ij =mXsli dll slj ,i≤j(6)l=1Âûäåëèì èç ñóììûi-ûéýëåìåíò:∗aij = (S DS)ij =i−1Xsli dll slj + sii dii sij +j=isli dll sljl=i+1l=1ÏðèmXáóäåì èìåòü:aii = (S ∗ DS)ii =i−1Xl=1sli dll sli + sii dii sii +mXl=i+1sli dll sli(7)Ìåòîä êâàäðàòíîãî êîðíÿ ñèëó âèäà ìàòðèöû17S sli = 0,äåò ðàâíà 0.

Ó÷èòûâàÿ ðàâåíñòâîl > i, ïîýòîìó ïîñëåäíÿÿ èç ñóìì áósli sli = |sli |2 , ïåðåïèøåì ïîëó÷èâøååñÿâûðàæåíèå â âèäå: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;Äëÿ ðåøåíèÿ ýòèõ äâóõ ñèñòåì ïîòðåáóåòñÿ ïîðÿäêàäåëåíèé, à òàêæånèçâëå÷åíèé êâàäðàòíîãî êîðíÿ.n3óìíîæåíèé è6Ïðèìåðû è êàíîíè÷åñêèé âèä èòåðàöèîííûõ ìåòîäîâ ðåøåíèÿ ÑËÀÓ18Ÿ5Ïðèìåðû è êàíîíè÷åñêèé âèä èòåðàöèîííûõ ìåòîäîâ ðåøåíèÿ ÑËÀÓÐàññìîòðèì ÑËÀÓ:Ax = f,ãäåA(1)(m × m), |A| =6 0, ìàòðèöà ðàçìåðàx = (x1 , .