В.Б. Андреев - Численные методы, страница 3

. , n,j = i, . . . , min[n, p + i],k=max[1,j−p]1 £lij =aij −ujjj−1Xlik ukj¤k=max[1,i−p]j = 1, . . . , n,i = j + 1, . . . , min[n, p + j].(2.14)Ïðåîáðàçóåì ôîðìóëû (1.20) è (1.21). Â ôîðìóëàõ (1.20) â ñèëó (2.13) i − k 6 p, àâ ôîðìóëàõ (1.21) â ñèëó (2.12) j − k 6 p. Ïîýòîìóyi = bi −i−1Xlik yk ,i = 1, . . . , n,k=max[1,i−p]min[n,k+p]iX1 hyk −ukj xj ,xk =ukkj=k+1(2.15)k = n, . . .

, 1.20Ÿ 2. ËÅÍÒÎ×ÍÛÅ ÌÅÒÎÄÛ2.4 Îöåíêà òðóäîåìêîñòèÎöåíèì òðóäîåìêîñòü LU - ðàçëîæåíèÿ ëåíòî÷íîé ìàòðèöû A, èìåþùåé ïîëóøèðèíóp, è òðóäîåìêîñòü ðåøåíèÿ ñèñòåìû (2.1) ñ òàêîé ìàòðèöåé. Äëÿ ýòîãî ïîäñ÷èòàåì÷èñëî óìíîæåíèé è äåëåíèé, íåîáõîäèìûõ äëÿ ðåàëèçàöèè ôîðìóë (2.14) è (2.15). Íàðèñ. 6 èçîáðàæåíû ïîðòðåòû ìàòðèö L è Un−p|1|∗|∗p (p + 1∗n−pn11∗ 1∗ ∗ 1∗ ∗ ∗ 1 ∗ ∗ ∗ 1Lz }|1pp+1∗ ∗ ∗| ∗ ∗ ∗| ∗ ∗∗| ∗ ∗∗ ∗∗{n∗∗∗∗UÐèñ. 6Ïåðåïèøåì ôîðìóëû (2.14), îòäåëèâ ôîðìóëû äëÿ ýëåìåíòîâ uij è lij , îáâåäåííûõòðåóãîëüíèêàìè íà ðèñ. 6.uij = aij −i−1Xlik ukj ,i = 1, .

. . , p,j = i, . . . , p,(2.16)k=1uij = aij −i−1Xlik ukj ,j = p + 1, . . . , n,i = j − p, . . . , j,(2.17)k=j−p"#j−1X1lij =aij −lik ukj , j = 1, . . . , p,ujjk=1(2.18)i = j + 1, . . . , p,"#j−1X1lij =aij −lik ukj , i = p + 1, . . . , n,ujjk=i−p(2.19)j = i − p, . . . , i − 1.Ïîäñ÷èòàåì ÷èñëî óìíîæåíèé è äåëåíèé, íåîáõîäèìûõ äëÿ ðåàëèçàöèè ôîðìóë (2.16)(2.19). Èç ñðàâíåíèÿ (2.16), (2.18) ñ (1.19) ñëåäóåò, ÷òî ýòè ôîðìóëû ïðè p = nñîâïàäàþò. Ïîýòîìó, ñ ó÷åòîì (1.22)p(p2 + 1).Q16 (Up ) + Q18 (Lp ) =3(2.20)2.4.

ÎÖÅÍÊÀ ÒÐÓÄÎÅÌÊÎÑÒÈ21Çäåñü Q òðóäîåìêîñòü, íèæíèé èíäåêñ íîìåð ôîðìóëû, à àðãóìåíò îáúåêòâû÷èñëåíèé.ÄàëååQ17 (uij ) = i − 1 − j + p + 1 = i − j + p,jnPP(i − j + p),Q17 (U ) =j=p+1 i=j−pQ19 (lij ) = j − 1 − i + p + 1 + 1 = j − i + p + 1,j−1ni−1nPPPPQ19 (L) =(j − i + p + 1) =(i − j + p + 1),i=p+1 j=i−pj=p+1 i=j−pè, ñëåäîâàòåëüíî,Q17 (U ) + Q19 (L) ==2nXnX"p+j=p+1"p−1p+j=p+1Xj−1X#(i − j + p + i − j + p + 1) =i=j−p#k = (n − p)p(p − 1).k=1Îòñþäà è èç (2.20) íàõîäèì, ÷òî îáùåå ÷èñëî óìíîæåíèé è äåëåíèé ïðè ïîñòðîåíèèL U -ðàçëîæåíèÿ åñòüQ=p(p + 1)2(3n − 2p − 1) = n(p2 + p) − p3 + O(p2 ).33(2.21)Çàìå÷àíèå 2.1. Ïîëóøèðèíà ïîëíîé ìàòðèöû p = n − 1. Ïîäñòàâëÿÿ ýòî çíà÷å-íèå p â íàéäåííîå âûðàæåíèå, ïîëó÷èì âûðàæåíèå äëÿ òðóäîåìêîñòè òðåóãîëüíîãîðàçëîæåíèÿ, ñîâïàäàþùåå ñ (1.22).

Ïîëàãàÿ æå çäåñü p = 1, ïîëó÷èì (2.5).Îáðàòèìñÿ ê ôîðìóëàì (2.15)."i − 1, i = 1, . . . , p,Q15 (yi ) =i − 1 − i + p + 1 = p,Q15 (y) =nXi=1Q15 (x) =Q15 (yi ) =#i = p + 1, . . . , n,p(p − 1)p(2n − p − 1)+ p(n − p) =,22p(2n − p − 1)+n2è ñëåäîâàòåëüíîq = Q15 (x) + Q15 (y) = p(2n − p − 1) + n = (2p + 1)n − p(p + 1)(ñð. ñ (1.23) ïðè p = n − 1 è (2.6) ïðè p = 1).Ïðîàíàëèçèðóåì ôîðìóëû (2.21), (2.22). Ðàññìîòðèì òðè ñëó÷àÿ.(2.22)22Ÿ 2.

ËÅÍÒÎ×ÍÛÅ ÌÅÒÎÄÛ1◦ . p = O(n), íàïðèìåð, p = αn, α < 1. Òîãä൶2 3 32α2 32Q≈α n − α n =α 1−n3 .33Ëåãêî ïðîâåðèòü, ÷òî ïðè 0 < α < 1 êîýôôèöèåíò ïðè n3 ìåíüøå 1/3.2◦ . p = o(n), íî p → ∞ ïðè n → ∞.  ýòîì ñëó÷àå ÷àñòíîñòè, ïðè p =√Q ≈ p2 n,q ≈ 2pn.Q ≈ n2 ,q = 2n3/2 .n3◦ . p = const (p = 1, 2, .

. . ).Q ≈ p(p + 1)n,q ≈ (2p + 1)n.Ïðè p = 1 Q < q , ïðè p > 2 Q > q .2.5LU - ðàçëîæåíèå äëÿ òðåõäèàãîíàëüíîé ìàòðèöû.Ëèíåéíàÿ ñèñòåìà (2.1) ñ òðåõäèàãîíàëüíîé ìàòðèöåé A ïðåäñòàâëÿåò îñîáûé èíòåðåñâ ñèëó òîãî, ÷òî ÷àñòî âñòðå÷àåòñÿ â ïðèëîæåíèÿõ. Ïîëó÷èì ôîðìóëû LU - ðàçëîæåíèÿ äëÿ ýòîãî ñëó÷àÿ, íå àïåëëèðóÿ ê (2.14), (2.15). Çàïèøåì ñèñòåìó (2.1) â âèäå (2.2).Íàéäåì òàêîå LU - ðàçëîæåíèå ìàòðèöû A, â êîòîðîì U (à íå L!) èìååò åäèíè÷íóþãëàâíóþ äèàãîíàëü (ñì.

çàìå÷àíèå 1.1). Ìàòðèöà ñèñòåìû (2.2) èìååò âèäb1 c1 0 . . . 0a2 b2 c2 . . . 0 A=(2.23) 0 a3 b3 . . . 0 . . . . . . . . . . . . . . . . . . . 0 0 0 . . . bnÏóñòüÒîãäàγ1 0 0 . . . 0 δ 2 γ2 0 . . . 0 ,0δγ...0L=33. . . . . . . . . . . . . . . . .

. .0 0 0 . . . γn1 −α10 ... 00 1 −α2 . . . 0.001...0U =. . . . . . . . . . . . . . . . . . . . .0 00 ... 1γ1−γ1 α1 δ2 −δ2 α1 + γ2−γ2 α2δ3−δ3 α2 + γ3−γ3 α3LU = δ4−δ4 α3 + γ4 . . ..............................................2.5. LU - ÐÀÇËÎÆÅÍÈÅ ÄËß ÒÐÅÕÄÈÀÃÎÍÀËÜÍÎÉ ÌÀÒÐÈÖÛ.23Ñðàâíèâàÿ ýòó ôîðìóëó ñ ìàòðèöåé (2.23), íàõîäèì ôîðìóëû äëÿ ýëåìåíòîâ ìàòðèöU è L:αi = −ci /γi , i = 1, . . . , n − 1,γi = bi + δi αi−1 , i = 2, .

. . , n, γ1 = b1 ,(2.24)δi = ai , i = 2, . . . , n.Îáðàòèìñÿ ê ðåøåíèþ ñèñòåìû (2.2) ñ èñïîëüçîâàíèåì LU - ðàçëîæåíèÿ. ÏóñòüU x = β . Òîãäà Lβ = d. Çàïèñûâàÿ ïîñëåäíþþ ñèñòåìó â ðàçâåðíóòîì âèäå, áóäåìèìåòüγ1 β1= d1 ,δ2 β1 + γ2 β2= d2 ,.................................................δi βi−1 + γi βi= di ,.................................................δn βn−1 + γn βn = dn .Îòñþäàβi = (di − δi βi−1 )/γi ,i = 2, . . . , n,β1 =d1.γ1(2.25)Àíàëîãè÷íî íàõîäèì, ÷òî ðåøåíèå ñèñòåìû U x = β îïðåäåëÿåòñÿ ôîðìóëàìèxi = αi xi+1 + βi ,i − n − 1, . . . , 1,x n = βn .(2.26)Ñðàâíåíèå ôîðìóë (2.24) - (2.26) ñ ôîðìóëàìè (2.3),(2.4) ïîêàçûâàåò, ÷òî ìåòîä ïðîãîíêè ÿâëÿåòñÿ íå ÷åì èíûì êàê ÷àñòíûì ñëó÷àåì ëåíòî÷íîãî âàðèàíòà ìåòîäà èñêëþ÷åíèÿ Ãàóññà.Îïðåäåëåíèå 2.3. Ãîâîðÿò, ÷òî ìàòðèöà A ëåíòî÷íàÿ ñ ëåíòîé íèæíåé ïîëóøèðèíûp1 è âåðõíåé ïîëóøèðèíû p2 , åñëè aij = 0 ïðè i − j > p1 è j − i > p2 .Óïðàæíåíèå 2.1.

Ïîñòðîèòü ìîäèôèêàöèþ ôîðìóë (2.14), (2.15) äëÿ ñëó÷àÿ ìàò-ðèöû ñ ðàçíîé ïîëóøèðèíîé.24Ÿ 2. ËÅÍÒÎ×ÍÛÅ ÌÅÒÎÄ۟ 3Ìåòîäû Õîëåöêîãî è áëî÷íîãîèñêëþ÷åíèÿ. Âû÷èñëåíèå îáðàòíîéìàòðèöû3.1Ìåòîä Õîëåöêîãî (êâàäðàòíûõ êîðíåé)Âíîâü îáðàòèìñÿ ê ñèñòåìåAx = b.(3.1)Íà ýòîò ðàç áóäåì ïðåäïîëàãàòü, ÷òî ìàòðèöà A ñèììåòðè÷íà è ïîëîæèòåëüíî îïðåäåëåíà, ò.å.A = AT è A > 0.(3.2)Ïîñëåäíåå îçíà÷àåò, ÷òî êâàäðàòè÷íàÿ ôîðìà xT Ax > 0 äëÿ ëþáîãî íåíóëåâîãî âåêòîðà x. Íàïîìíèì, ÷òî ñèììåòðè÷íàÿ ìàòðèöà èìååò òîëüêî äåéñòâèòåëüíûå ñîáñòâåííûå çíà÷åíèèÿ, à ïîëîæèòåëüíî îïðåäåëåííàÿ òîëüêî ïîëîæèòåëüíûå.

 ñèëóêðèòåðèÿ Ñèëüâåñòðà íåîáõîäèìûì è äîñòàòî÷íûì óñëîâèåì ïîëîæèòåëüíîé îïðåäåëåííîñòè ìàòðèöû A ÿâëÿåòñÿ ïîëîæèòåëüíîñòü âñåõ åå óãëîâûõ ìèíîðîâ ∆i > 0,i = . . . , n.Ïîñòðîèì àëãîðèòì ðåøåíèÿ ñèñòåìû (3.1), êîòîðûé èñïîëüçóåò ñâîéñòâà (3.2)ìàòðèöû A. Ýòî áóäåò ìåòîä Õîëåöêîãî. Îñíîâîé ìåòîäà Õîëåöêîãî ÿâëÿåòñÿÒåîðåìà 3.1. Åñëè A = AT > 0, òî ñóùåñòâóåò åäèíñòâåííîå ðàçëîæåíèåA = LLT ,(3.3)ãäå L íèæíÿÿ òðåóãîëüíàÿ ìàòðèöà ñ ïîëîæèòåëüíûìè äèàãîíàëüíûìè ýëåìåíòàìè.Îïðåäåëåíèå 3.1. Ðàçëîæåíèå (3.3) íàçûâàåòñÿ ðàçëîæåíèåì Õîëåöêîãî, à ìàòðèöàL ìíîæèòåëåì Õîëåöêîãî.2526Ÿ 3.

ÌÅÒÎÄÛ ÕÎËÅÖÊÎÃÎ È ÁËÎ×ÍÎÃÎ ÈÑÊËÞ×ÅÍÈßÄîêàçàòåëüñòâî òåîðåìû. Ñíà÷àëà äîêàæåì åäèíñòâåííîñòü. Ïóñòü ñóùåñòâóþòäâà ðàçëîæåíèÿA = L1 LT1 = L2 L2T .Îáðàùàÿ ìàòðèöû L2 è LT1 , áóäåì èìåòü¡ T ¢−1TL−1.2 L1 = L2 L1Ïðèíèìàÿ âî âíèìàíèå, ÷òî (AB)T = B T AT , à äëÿ íåâûðîæäåííûõ ìàòðèö (AB)−1 =B −1 A−1 , íàéäåì, ÷òî¡L−11 L2¢−1¡ T ¢−1 ¡ −1 ¢TT= L−1= L1 L2 .2 L1 = L2 L1(3.4) ñèëó ëåììû 1.1 îáðàòíàÿ ê íèæíåé òðåóãîëüíîé ìàòðèöå åñòü íèæíÿÿ òðåóãîëüíàÿ ìàòðèöà è ïðîèçâåäåíèå òàêèõ ìàòðèö åñòü ñíîâà íèæíÿÿ òðåóãîëüíàÿ ìàòðèöà.Èç ñêàçàííîãî ñëåäóåò, ÷òî â ëåâîé ÷àñòè (3.4) ñòîèò íèæíÿÿ òðåóãîëüíàÿ ìàòðèöà, àñïðàâà âåðõíÿÿ.

Ðàâåíñòâî (3.4) âîçìîæíî òîëüêî òîãäà, êîãäà îáå ìàòðèöû äèàãîíàëüíûå. Íî äèàãîíàëüíàÿ ìàòðèöà ñîâïàäàåò ñî ñâîåé òðàíñïîíèðîâàííîé. Ïîýòîìóèç (3.4) ñëåäóåò, ÷òî¡ −1 ¢−1L1 L2= L−11 L2 = D.Ýòî ñîîòíîøåíèå óòâåðæäàåò, ÷òî äèàãîíàëüíàÿ ìàòðèöà D ñîâïàäàåò ñî ñâîåé îáðàòíîé, ÷òî âîçìîæíî òîëüêî â òîì ñëó÷àå, åñëè ó ýòîé ìàòðèöû äèàãîíàëüíûìèýëåìåíòàìè ÿâëÿþòñÿ ÷èñëà ±1. Ïîñêîëüêó L2 = L1 D, à äèàãîíàëüíûå ýëåìåíòû L1 èL2 ïîëîæèòåëüíû, òî äèàãîíàëüíûå ýëåìåíòû D òîæå äîëæíû áûòü ïîëîæèòåëüíû,ò.å. D ≡ I è, ñëåäîâàòåëüíî, L2 = L1 .

Åäèíñòâåííîñòü äîêàçàíà.Ïîñòðîèì òåïåðü ôîðìóëû äëÿ âû÷èñëåíèÿ ýëåìåíòîâ L, îòêóäà è áóäåò ñëåäîâàòüñóùåñòâîâàíèå. Òàê êàê aij = aji , à lij = 0 ïðè i < j , òî áóäåì ñ÷èòàòü, ÷òîi > j.Òîãäàaij =nXk=1=j−1XTlik lkj=nXlik ljk =k=1j−1Xk=1nXlik ljk + lij ljj +0klik ljk =k=j+1lik ljk + lij ljj .k=1Ïðè i = j íàõîäèì, ÷òîvuj−1uXt2ljj = ajj −ljk,k=1j = 1, . . . , n.(3.5)3.1. ÌÅÒÎÄ ÕÎËÅÖÊÎÃÎ (ÊÂÀÄÐÀÒÍÛÕ ÊÎÐÍÅÉ)Äàëåå,"#j−1X1lij =aij −lik ljk ,ljjk=127i = j + 1, .

. . , n,(3.6)j = 1, . . . , n − 1Âû÷èñëåíèÿ ìîæíî âåñòè ïî ñòîëáöàì j = 1, . . . , n äëÿ i = j + 1, . . . , n.√ai1a11 , li1 =, i = 2, . . . , nl11q12= a22 − l21[ai2 − li1 l21 ] ,, li2 =l22j=1:l11 =j=2:l22i = 3, . . . , nè ò.ä.Îñòàëîñü äîêàçàòü, ÷òî âñå ljj ïîëîæèòåëüíû, ò.å. ïîëîæèòåëüíû ïîäêîðåííûåâûðàæåíèÿ.

Äîêàæåì, ÷òîqljj = ∆j /∆j−1 , ãäå ∆0 = 1.Ïóñòü, êàê ðàíüøå,·¸Aj A12A=,A21 A22Òîãäà·¸Lj0L=.L21 L22Aj = Lj LTj .ÎòñþäàÃ∆j = det Aj = (det Lj )2 =jY!2lkk.k=1Àíàëîãè÷íî∆j−1 =à j−1Y!2lkkk=1è, ñëåäîâàòåëüíî,2ljj= ∆j /∆j−1 > 0,j = 1, . . . , n.Òåîðåìà äîêàçàíà.Óïðàæíåíèå 3.1. Ïîêàçàòü, ÷òî äëÿ ðåàëèçàöèè ôîðìóë (3.5), (3.6) ïðè âñåõ i è jòðåáóåòñÿn3n(n + 1)(n + 2)≈66îïåðàöèé óìíîæåíèÿ, äåëåíèÿ è èçâëå÷åíèÿ êîðíÿ.Q=(3.7)Çàìå÷àíèå 3.1.

Èç (3.7) ñëåäóåò, ÷òî ðàçëîæåíèå Õîëåöêîãî â äâà ðàçà áîëåå ýêîíîìè÷íî, ÷åì òðåóãîëüíîå ðàçëîæåíèå.28Ÿ 3. ÌÅÒÎÄÛ ÕÎËÅÖÊÎÃÎ È ÁËÎ×ÍÎÃÎ ÈÑÊËÞ×ÅÍÈßÎáðàòèìñÿ òåïåðü ê ðåøåíèþ ñèñòåìû (3.1). Ïîñêîëüêó Ax = LLT x = b, òî,ïîëàãàÿ LT x = y , ïîëó÷èì Ly = b. Ïðè ýòîì"#i−1X1yi =bi −lik yk , i = 1, . . . , n,liik=1"#nX1yi −lki xk , i = n, . . . , 1.xi =liik=i+1(3.8)Çàìå÷àíèå 3.2. Î÷åíü ÷àñòî èñïîëüçóåòñÿ ìîäèôèêàöèÿ ðàçëîæåíèÿ Õîëåöêîãî,íàçûâàåìàÿ LDLT -ðàçëîæåíèåì.

Ñóòü åå â òîì, ÷òî âìåñòî ðàçëîæåíèÿ (3.3) ñòðîèòñÿðàçëîæåíèå ìàòðèöû A âèäàA = LDLT ,ãäå L ïîïðåæíåìó íèæíÿÿ òðåóãîëüíàÿ ìàòðèöà, íî â îòëè÷èå îò (3.3) åå äèàãîíàëüíûå ýëåìåíòû ðàâíû 1, à D äèàãîíàëüíàÿ ìàòðèöà. Äîñòîèíñòâî LDLT -ðàçëîæåíèÿñîñòîèò â òîì, ÷òî ïðè åãî âû÷èñëåíèè íå òðåáóåòñÿ íàõîäèòü êâàäðàòíûå êîðíè, àïîòîìó îíî ñóùåñòâóåò íå òîëüêî äëÿ ïîëîæèòåëüíî îïðåäåëåííûõ ìàòðèö. Óñëîâèåìñóùåñòâîâàíèÿ òàêîãî ðàçëîæåíèÿ äëÿ ñèììåòðè÷íîé ìàòðèöû ÿâëÿåòñÿ îòëè÷èå îòíóëÿ âñåõ åå óãëîâûõ ìèíîðîâ.Óïðàæíåíèå 3.2.