Численные методы. Ионкин (2012) (v1.1) (косяки есть), страница 2

. . , m ⇒mXi = 1 + 2 + ··· + m = {àðèôìåòè÷åñêàÿ ïðîãðåññèÿ}=i=1m(m − 1)2 ìåòîäå Ãàóññà íà ïðåîáðàçîâàíèå ïðàâîé ÷àñòè (â ïðÿìîì õîäå ìåòîäà Ãàóññà)óõîäèòm(m−1)äåéñòâèé.2Ðàññìîòðèì 1.7:PPxi = yi −Òåïåðüci,l xl → (m − i) óìíîæåíèé ïðè ôèêñèðîâàííîì i.m(m−1)îòïóñêàåì i ⇒ (m − 1) + (m − 2) + · · · + 1 =.2îáðàòíîì õîäå ìåòîäà Ãàóññà.Òàêèì îáðàçîì ìåòîä Ãàóññà òðåáóåòm33+ m2 −Ñòîëüêî æå âm3 .

Áîëüøàÿ ÷àñòü îïåðàöèéóõîäèò íà ôàêòîðèçàöèþ.Ÿ 3. Îáðàùåíèå ìàòðèö ìåòîäîì Ãàóññà-ÆîðäàíàÝòà òåìà ÿâëÿåòñÿ î÷åíü âàæíîé.Àëãåáðàè÷åñêàÿ ïîñòàíîâêà çàäà÷è: ïóñòü äàíà êâàäðàòíàÿ íåâûðîæäåííàÿìàòðèöàA(m, m), | A |6= 0.Ïî îïðåäåëåíèþ ìàòðèöà A íàçûâàåòñÿ îáðàòíîé, åñëèãäåE -åäèíè÷íàÿA−1 A = AA−1 = E ,ìàòðèöà.Ñóùåñòâóåò 2 ìåòîäà îáðàùåíèÿ:1)×åðåç àëãåáðàè÷åñêèå äîïîëíåíèå. Ýòî íåýêîíîìè÷íûé ìåòîä⇒ (m − 1)! äåé-ñòâèé.

À ìû ðåøàåì çàäà÷è áîëüøîãî ïîðÿäêà. Íàïðèìåð áûâàþò òðåõìåðíûåíåñòàöèîíàðíûå çàäà÷è äëÿ óðàâíåíèÿ òåïëîïðîâîäíîñòè ïîðÿäêàÏóñòüA−1 = X . ìàòðèöåX m2ýëåìåíòîâ. Òîãäà èìååìAX = EÑËÀÓ→mPai,l xl,j = σi,j106 .(1.8)ïî êîîðäèíàòàì. Ñàìûé ýêîíîìè÷íûé ìåòîä.

Äîêàæåì,l=1÷òî ìîæíî çàòðàòèòüÑèñòåìàAX = fm3îïåðàöèé íà ðàáîòó äàííîãî ìåòîäà.ìîæåò ðàñïàñòüñÿ íàêîëè÷åñòâî äåéñòâèé.8m ñèñòåì. Òàêèì îáðàçîì ìû ñîêðàòèì2)ÐàññìîòðèìîáðàùåíèåÃàóññà-Æîðäàíà.ÂâåäåìâåêòîðñòîëáåöXj=T(x1,j , . . . , xm,j )σ j = (0, 0, . . . , 0, 1, 0, . . . , 0, 0)TÄëÿ îáðàùåíèÿ íåîáõîäèìî ðåøèòümñèñòåìAX j = σ j , j = 1, 2, . .

. , mÏðèìåíèìBCX(j)ôàêòîðèçàöèþ.(j)= σ , CX ñîâîêóïíîñòèm2(j)=YÏóñòüóãëîâûå(1.9)ìèíîðûîòëè÷íûîòíóëÿ⇒(j)BY (j) = σ (j)(1.10)CX (j) = Y (j) , j = 1, 2, . . . , m(1.11)äåéñòâèé. Ò.ê. m ñèñòåìÎäèí ðàç ïðîâåäåì ôàêòîðèçàöèþ⇒ m3⇒ m3 +äåéñòâèé.m3 −m4 33 . Èòîãî 3 m−m3.Åñëè âîñïîëüçîâàòüñÿ ñïåöèôèêîé âèäà ìàòðèö, òî âîçìîæíî ïîëó÷èòüm3äåéñòâèé. Ïîêàæåì ýòî.Ïóñòü B íèæíÿÿ òðåóãîëüíàÿ ìàòðèöà. Ïîñìîòðèì ðåøåíèå ñèñòåìû 1.10:(j)(j)b1,1 y1 = 0 ⇒ y1 = 0(j)(j)b2,1 y1 + b2,2 y2 = 0 ⇒ y2j = 0àíàëîãè÷íî äî(j − 1)(j)(j)(j)bj−1,1 y1 + bj−1,2 y2 + · · · + b(j−1),i−1 yj−1 = 0 ⇒(j)yj = 0, i ≤ j − 1(j)(j)bj,j yj = 1 ⇒ yj =(j)1, i=jbj,j(j)(j)bi,j yj + bi,j+1 yj+1 + · · · + bi,i yi = 0 ⇒i−1P(j)yi = −l=j(j)bi,l ylbi,i, i = j + 1, j + 2, . .

. , mÑíà÷àëà ôèêñèðóåì i è j è ñ÷èòàåì êîëè÷åñòâî äåéñòâèé. Èòîãî 1 äåëåíèå è (i-j)óìíîæåíèé.Îòïóñêàåì èíäåêñ i:m − j + (m − j − 1) + . . . + 2 + 1 =9m−j+1+m−j2óìíîæåíèé ïðè ôèêñèðîâàííîì i. Åùå îäíî äåëåíèå ïðèÈòîãî ïðè ôèêñèðîâàííîìj⇒Îòïóñêàåì èíäåêñ j, ò.ê.j=Çàäà÷à 2:Äîêàçàòü, ÷òî äëÿ ðåøåíèÿ ñèñòåìû 1.10 íåîáõîäèìîñèñòåìû 1.11:Ðåøåíèå:Ïóñòüm(m−1),2(i = j)èm−jäåëåíèé.(m−j+1)(m−j+2)äåéñòâèé.2mP (m−j+1)(m−j+2)1, 2, . . . , m ⇒äåéñòâèé.2j=1j = 1, 2, .

. . , m ⇒âñåãîm(m+1)(m+2)è äëÿ ðåøåíèÿ6m2 (m−1)óìíîæåíèé è äåëåíèé.2k =m−j+1 ⇒mXk(k + 1)k=12=mXkk=12+mXk2k=12=k(k + 1) k(k + 1)(2k + 1) 3k(k + 1) + k(k + 1)(2k + 1) k(k + 1)(k + 2)+==.412126m(m−1)äåéñòâèé (ïðÿìîé õîä ìåòîäà Ãàóññà).2m2 (m−1)ñèñòåì ïîòðåáóåòñÿ ⇒äåéñòâèé óìíîæåíèÿ è äåëåíèÿ2Ðåøåíèå ñèñòåìû 1.11 òðåáóåòÏîñêîëüêó âñåãîäëÿ èõ ðåøåíèÿm⇒Îáùåå êîëè÷åñòâî äåéñòâèé íà îáðàùåíèå ìàòðèöû32m −m6=3322m −2m+m +3m +2m+3m−36m3 −m3+m(m+1)(m+2)6+= m3 .Ÿ 4. Ìåòîä êâàäðàòíîãî êîðíÿÐàññìîòðèì ñèñòåìóAx = f,(1.12)ãäå A-ýðìèòîâà íåâûðîæäåííàÿ ìàòðèöà.Ïî îïðåäåëåíèþ:ai,j = āj,i , A = A∗ , | A |6= 0, A(m, m).Ñóçèâ êëàññ, ìû äîëæíû ïîëó÷èòü áîëåå ñèëüíûé ðåçóëüòàò.

Ôàêòîðèçóåììàòðèöó A áîëåå õèòðûì ñïîñîáîì â âèäåd1,1 0 0 0 d2,2 0D=... ... ...00 0, ãäåA = S ∗ DS... 0 00... 0 00 ... ... ... ... . . . 0 0 dm,mdi,i = ±1, i = 1, . . . , m.s1,1 s2,2 0 s2,1S=. . . . . .0010. . . s1,m. . . s2,m ,... ... . . . sm,mãäåsi,i > 0, i = 1, 2, . . . , m.a1,1 a1,2d1,1 0s1,1 s1,2Ïóñòü A =, D =, S =.aa0d0s1,22,22,22,2s01,1S∗ = ST =s1,2 s2,2 d1,1 0s1,1 s1, 2d1,1 s1,1 d1,1 s1,2Òîãäà DS ==0d0s2,22,2 0 2d2,2 s2,2d1,1 s1,1 s1,1 d1,1 s1,2s1,1 0d1,1 s1,1 d1,1 s1,2∗S DS ==⇒s1,2 s2,20d2,2 s2,2s1,1 d1,1 s1,2 d2,2 s22,22 a1,1 = d1 s1,1a1,2 = s1,1 d1,1 s1,2a2,2 = d2,2 s22q⇒ d1,1 = sign a1,1 → s1,1 = | a1,1 |a1,2→ d2,2 = sign a2,2s1,1 d1,1q⇒ s2,2 = | a2,2 |⇒ s1,2 =⇒ s222 d22 = a22 − s212 d11 ⇒⇒ d22 = sign(a22 − s212 d11 ) ⇒q⇒ s22 = |a22 − d11 s212 |Äëÿ ôàêòîðèçàöèè ìàòðèöû ñèñòåìà äîëæíà áûòü ðàçðåøèìà.Òàêèì îáðàçîì, äëÿ âåùåñòâåííîé ñàìîñîïðÿæåííîé ìàòðèöû ðàçëîæåíèå âîçìîæíî è íàõîäèòñÿ ïî ÿâíûì ôîðìóëàì.Ïðèìå÷àíèå:Äëÿ êîððåêòíîñòè äåéñòâèé íåîáõîäèìî íàëîæèòü ñîîòâåòñòâóþùèå îãðàíè÷åíèÿ íà èñõîäíóþ ìàòðèöó (òàê êàê â ïðîöåññå ïðåîáðàçîâàíèé ìû âûïîëíÿëèäåëåíèå).

 äàííîì ñëó÷àå, îãðàíè÷åíèé, íàêëàäûâàåìûõ äëÿ îáåñïå÷åíèÿ âîçìîæíîñòè ôàêòîðèçàöèè ìàòðèöû, âïîëíå äîñòàòî÷íî.Ðàññìîòðèì òåïåðü îáùèé ñëó÷àé: ýðìèòîâó ìàòðèöóAâ êîìïëåêñíîì ïðî-ñòðàíñòâå, è ñîîòâåòñòâóþùóþ ñèñòåìó ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé:Ax = f, |A| =6 0, A(m × m), A = A∗Áóäåì èñêàòü ïðåäñòàâëåíèå ìàòðèöûAâ âèäåA = S ∗ DS,11(1.13)ãäåS âåðõíÿÿ òðåóãîëüíàÿ ïîëîæèòåëüíàÿD = diag(d11 , . . . , dmm ), dii = ±1S∗ íèæíÿÿ òðåóãîëüíàÿ ìàòðèöà ñ ýëåìåíòàìèÒàê êàêDìàòðèöà(sij > 0),s¯ji .- äèàãîíàëüíàÿ ìàòðèöà, òî:(DS)ij =mXdil slj = dii sij , sii > 0l=1Ó÷ò¼ì, ÷òî:sij = s̄ji .Òîãäà∗aij = (S DS)ij =mXs̄li dll slj , i ≤ jl=1i-ûéÂûäåëèì èç ñóììûýëåìåíò:∗aij = (S DS)ij =i−1Xs̄li dll slj + s̄ii dii sij +S sli = 0, l > i,äëÿ aii : ñèëó âèäà ìàòðèöû∗aii = (S DS)ii =ïîñëåäíÿÿ ñóììà ðàâíài−1Xs̄li dll sli + s̄ii dii siil=1.Òàê êàês̄li sli = |sli |2 ,òîs2ii dii= aii −i−1X|sli |2 dlll=1Îòñþäàdii = sign(aii −i−1X|sli |2 dll )l=1vui−1Xutsii = |aii −|s2li dll |l=1(ñ ó÷¼òîì ïîëîæèòåëüíîñòèsij ).Èç èñõîäíîé ôîðìóëû 1.14 îêîí÷àòåëüíî íàõîäèì:aij −sij =i−1Ps̄li dll sljl=i+1l=1Çàïèøåì âûðàæåíèåmXs̄li dll slj −l=1mPl=i+1s̄ii dii12s̄li dll slj0.(1.14)Ïðèìå÷àíèå:×åðòó íàäSsiiñòàâèòü íåîáÿçàòåëüíî, òàê äèàãîíàëüíûå ýëåìåíòû ìàòðèöûâåùåñòâåííû (ñì.

âûøå).Òàêèì îáðàçîì, ïðè îïðåäåëåííûõ óñëîâèÿõ èñõîäíóþ ìàòðèöó ìîæíî ïðåîá-ðàçîâàòü ê âèäó 1.13.Ðàññìîòðèì ïðèìåíåíèå äàííîãî ðàçëîæåíèÿ ê ðåøåíèþ ñèñòåìû ëèíåéíûõàëãåáðàè÷åñêèõ óðàâíåíèé:Ax = fS ∗ DSx = f(1.15)DSx = y.(1.16)Îáîçíà÷èìÒîãäà ïîëó÷èì äâå ñèñòåìû ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé:Òîãäà îáðàùàÿS ∗y = fDSx = yS , ìîæåì ëåãêî ïîñ÷èòàòü y , à ðåøàÿ óðàâíåíèå 1.16 - ïîñ÷èòàòüx.Îá ýôôåêòèâíîñòè ýòîãî ìåòîäà:Íàì ïðèä¼òñÿ ðåøàòü óðàâíåíèÿ òîëüêî ïðèi ≤ j,ñëåäîâàòåëüíî, äëÿ ðåøåíèÿm3ýòèõ äâóõ ñèñòåì ïîòðåáóåòñÿ, ãðóáî ãîâîðÿ,6 óìíîæåíèé è äåëåíèé (âûèãðûøïî ñðàâíåíèþ ñ ìåòîäîì Ãàóññà - â äâà ðàçà!), à òàêæåm èçâëå÷åíèé êâàäðàòíîãîêîðíÿ (îòñþäà, êñòàòè, ìåòîä íàçûâàåòñÿ ìåòîäîì êâàäðàòíîãî êîðíÿ).Òàêèì îáðàçîì, åñëè ìàòðèöà ýðìèòîâà, òî îäèí èç ýôôåêòèâíûõ ïðÿìûõ ìåòîäîâ ðåøåíèÿ ÑËÀÓ - ìåòîä êâàäðàòíîãî êîðíÿ, êîòîðûé òðåáóåò ìåíüøå äåéñòâèé, ÷åì ìåòîä Ãàóññà.Íà ïðàêòèêå, ìû ëåãêî ìîæåì àëãîðèòìè÷åñêè ðåàëèçîâàòü ðåøåíèå ÑËÀÓïðÿìûìè ìåòîäàìè, íàïðèìåð, ìåòîäîì Ãàóññà.

Ó÷èòûâàÿ ñïåöèàëüíûå âèäû ìàòðèö (äèàãîíàëüíûå, áëî÷íûå è ò.ä.), êîòîðûå ÷àñòî âñòðå÷àþòñÿ íà ïðàêòèêå, ìûñìîæåì ñîêðàòèòü êîëè÷åñòâî äåéñòâèé.Çà÷åì æå âîçíèêëà íåîáõîäèìîñòü ïðèìåíÿòü èòåðàöèîííûå ìåòîäû ðåøåíèÿ?Îá ýòîì - â ñëåäóùåì ïàðàãðàôå.Ÿ 5. Ïðèìåðû è êàíîíè÷åñêèé âèä èòåðàöèîííûõìåòîäîâ ðåøåíèÿ ÑËÀÓÐàññìîòðèì ÑËÀÓ:Ax = f,13(1.17)ãäåA- ìàòðèöà ðàçìåðà(m × m), |A| 6= 0, x = (x1 , . .

. , xm )T , f = (f1 , . . . , fm )T(Ìàòðèöà óæå íåîáÿçàòåëüíî ýðìèòîâà).Çà÷åì íóæíû èòåðàöèîííûå ìåòîäû ðåøåíèÿ? Âî-ïåðâûõ, íà ïðàêòèêå ïðàâûå÷àñòè ñèñòåìû îáû÷íî çàäàíû ñ íåêîòîðîé òî÷íîñòüþ. Ïðÿìîé ìåòîä äà¼ò òî÷íîåðåøåíèå ýòîé ñèñòåìû. Íàì æå äîñòàòî÷íî ðåøåíèÿ, âåðíîãî ñ òîé æå òî÷íîñòüþ,÷òî è ïðàâàÿ ÷àñòü.Âî-âòîðûõ, êîëè÷åñòâî äåéñòâèé ïðÿìûõ ìåòîäîâ ðåøåíèÿ ïðîïîðöèîíàëüíî3m.

Ðàññìîòðåííûå íèæå ìåòîäû ïîçâîëÿþò íàéòè ðåøåíèå âñåãî çàm èòåðàöèé.Ðàññìîòðèì èòåðàöèîííûå ìåòîäû ßêîáè (êîòîðûé òàêæå íàçûâàþò ìåòîäîìïðîñòîé èòåðàöèè) è Çåéäåëÿ.Èç íåâûðîæäåííîñòè ìàòðèöû ñëåäóåò, ÷òî ðåøåíèå ÑËÀÓ ñóùåñòâóåò è åäèíñòâåííî. Ïåðåïèøåì ñèñòåìó 1.17 ïîêîîðäèíàòíî:mXaij xj = fi , i = 1, . . . , m(1.18)j=1Íà÷íåì ñ ìåòîäà ßêîáè (Ìß). Âûäåëèì èç ñóììûi−1Xaij xj + aii xi +j=1Ïóñòüaii 6= 0.mXi-îåñëàãàåìîå:aij xj = fi , i = 1, . . .

, mj=i+1Òîãäà ìîæíî âûðàçèòüxi :mfi − Σi−1j=1 aij xj − Σj=i+1 aij xjxi =aiiÎáîçíà÷èì ÷åðåçxni i n-óþèòåðàöèþi-îéêîîðäèíàòû.Çàïèøåì ìåòîä ßêîáè (Ìß). ×òîáû åãî îðãàíèçîâàòü, íàâåøèâàåìn+1âëåâîé ÷àñòè:xn+1ii−1mXfi X aij naij n=−xj −xj , n = 0, 1, . . . , i = 1, . . . , maii j=1 aiiaiij=i+1(1.19)Äëÿ òîãî, ÷òîáû íà÷àòü âû÷èñëåíèå, íóæíà íåêîòîðàÿ íóëåâàÿ èòåðàöèÿ. Ìûñ÷èòàåì, ÷òî îíà çàäàíà (ò.å.x0 )- íà÷àëüíîå ïðèáëèæåíèå). Ïîçæå ìû ïîêàæåì,÷òî íà÷àëüíîå ïðèáëèæåíèå ìîæåò áûòü ëþáûì.Èòàê, ïîëó÷àåì èòåðàöèîííûé ìåòîä, ïðè÷åì âû÷èñëåíèå êàæäîé èòåðàöèèìû ïðîèçâîäèì ïî ÿâíûì ôîðìóëàì.Ìåòîä, êîíå÷íî, íóæíî îáîðâàòü íà êàêîì-òî ýòàïå, îí äîëæåí áûòü êîíå÷íûì.

Ìû ïðåêðàùàåì âû÷èñëåíèÿ, êîãäà â íåêîòîðîé íîðìå äîñòèãíåì íóæíîéòî÷íîñòè, ò.å. êîãäà||xn − x|| < epsïðè íåêîòîðîì14n.Çàïèøåì òåïåðü ìåòîä Çåéäåëÿ (ÌÇ):xn+1ii−1mXfi X aij n+1aij n=−xj −xj , n = 0, 1, . . . ; i = 1, . . . , maii j=1 aiiaiij=i+1Íà÷àëüíîå ïðèáëèæåíèåx0(1.20)òàêæå ñ÷èòàåì çàäàííûì èçíà÷àëüíî.Ìåòîä ßêîáè ÿâëÿåòñÿ ÿâíûì, òàê êàê âû÷èñëÿåòñÿ ïî ÿâíûì ôîðìóëàì. Ìåòîä Çåéäåëÿ - íåÿâíûé. Íî åñëè ðàçóìíî îðãàíèçîâàòü ïðîöåññ âû÷èñëåíèé, àèìåííî íà÷èíàòü ïðîöåññ âû÷èñëåíèé ñ ïåðâîé êîîðäèíàòû, òî êàæäóþ èòåðàöèþ ìû âû÷èñëèì â ÿâíîì âèäå:mxn+11X a1jf1−xnj=a11 j=2 a11mxn+12f2a21 n+1 X a2j n=−x−xja22 a22 1a22j=3è ò.ä.Ïîçæå, êîãäà ìû äîêàæåì òåîðåìó î äîñòàòî÷íûõ óñëîâèÿõ ñõîäèìîñòè èòåðàöèîííûõ ìåòîäîâ, òî óâèäèì, ÷òî ïðîâåðêà äëÿ ÌÇ ïðîùå, ÷åì äëÿ Ìß.

 ýòîìïðåèìóùåñòâî ìåòîäà Çåéäåëÿ. Ïðè ýòîì ñòàíåò âèäíî, ÷òî ñêîðîñòü ñõîäèìîñòèîáîèõ ìåòîäîâ ìåäëåííàÿ ïî ñðàâíåíèþ ñ äðóãèìè èòåðàöèîííûìè ìåòîäàìè.Ïðè ðàññìîòðåíèè èòåðàöèîííûõ ìåòîäîâ ðåøåíèÿ ÑËÀÓ îáû÷íî âîçíèêàåò 2âîïðîñà:1. Âîïðîñ ñõîäèìîñòè: eñòü ëè óñëîâèÿ, ïðè êîòîðûõ ìåòîä áóäåò ñõîäèòüñÿ?Ïðè ýòîì âàæíî ïîíèìàòü, ÷òî êàê òîëüêî ìû ãîâîðèì î ñõîäèìîñòè íåêîòîðîãî ìåòîäà, íóæíî óêàçûâàòü, â êàêîé íîðìå äîêàçàíà ñõîäèìîñòü. Èçñõîäèìîñòè â îäíîé íîðìå, âîîáùå ãîâîðÿ, íå ñëåäóåò ñõîäèìîñòü ïî äðóãîéíîðìå.(Ýòî èíîãäà âûòåêàåò èç íåêîòîðûõ òåîðåì (èç 4 êóðñà) - èç áîëåå ñèëüíîé ìåòðèêè ìîæíî ïîëó÷èòü ñõîäèìîñòü â áîëåå ñëàáîé, íî íå âñåãäà).2. Ñêîðîñòü ñõîäèìîñòè: à íàäî ëè ïîëó÷èòü íàèáîëåå áûñòðóþ ñêîðîñòü ñõîäèìîñòè, è ïðè êàêèõ óñëîâèÿõ ñõîäèìîñòü áóäåò íàèáîëåå áûñòðàÿ? ÇÛ:êîíå÷íî íàäî!Äëÿ èññëåäîâàíèÿ ýòèõ äâóõ âîïðîñîâ óäîáíî ñèñòåìû ðàññìàòðèâàòü â ìàòðè÷íîì âèäå.Ïðåäñòàâèì ìàòðèöóAâ âèäåA = R1 + D + R2 ,15ãäå00 ...