Диссертация (Некоторые методы проекционного типа численного решения одного класса слабо сингулярных интегральных уравнений), страница 7

ÌàòðèöàAnñýëåìåíòàìèaijíàçûâåòñÿòåïëèöåâîé, åñëè aij = ai−j äëÿ âñåõ 1 ≤ i ≤ n, 1 ≤ j ≤ n, òî åñòüåñëè åå ýëåìåíòû ïîñòîÿííû âäîëü êàæäîé èç äèàãîíàëåé, äðóãèìèñëîâàìè ýëåìåíòû An îäèíàêîâû íà êàæäîé ëèíèè i − j = k è ïîëíîñòüþîïðåäåëÿþòñÿ ýëåìåíòàìè å¼ ïåðâîãî ñòîëáöà è ïåðâîé ñòðîêè. a0 a−1 a−2 . . .

a2−n a1−n  aa0 a−1 . . . a3−n a2−n  1 a2a1a0 . . . a4−n a3−n .An =  ... ... ... ... ... ... aaa...aa0−1  n−2 n−3 n−4an−1 an−2 an−3 . . . a1a0(3.1.1)63Îïðåäåëåíèå 3.1.2. Òåïëèöåâà ìàòðèöà íàçûâàåòñÿ öèðêóëÿíòíîé,åñëè a−j = an−j äëÿ âñåõ 1 ≤ j < n. Òàêèì îáðàçîì, öèðêóëÿíòíàÿ ìàòðèöàèìååò âèä c0 c 1 c2Cn =  ...c n−2cn−1cn−1 cn−2 . . .c0cn−1 . . .c1c0............cn−3 cn−4 . . .cn−2 cn−3 . . .c2c1 c3 c2 c4 c3 ... ...

c0 cn−1 c1 c0(3.1.2)ßñíî, ÷òî îíà ïîëíîñòüþ îïðåäåëÿåòñÿ ýëåìåíòàìè ñâîåãî ïåðâîãî ñòîëáöà.Îïðåäåëèì ìàòðèöó Ôóðüå ïîðÿäêà n:1Fn = 11···111ω 1·1ω 1·2···ω 1·(n−2)ω 1·(n−1)1ω 2·1ω 2·2···ω 2·(n−2)ω 2·(n−1)··················1ω (n−2)·1 ω (n−2)·2 · · · ω (n−2)·(n−2) ω (n−2)·(n−1)1ω (n−1)·1 ω (n−1)·2 · · · ω (n−1)·(n−2) ω (n−1)·(n−1),ω = e−2πi/n .Óòâåðæäåíèå 3.1.1. Ìàòðèöà Ôóðüå îáðàòèìà è ïðè ýòîì îáðàòíàÿìàòðèöà èìååò âèäF−1n =Êàê ñëåäñòâèå, kFk2 = kF∗ k2 =√1 ∗Fn n(3.1.3)n.Òåîðåìà 3.1.1 (Òåîðåìà î öèðêóëÿíòàõ). Ïóñòü Cn - öèðêóëÿíòíàÿìàòðèöà ñ ïåðâûì ñòîëáöîì c=(c0 , c1 , ..., cn−1 )T .

Èìååò ìåñòîðàçëîæåíèåCn =1 ∗1Fn Dn Fn = F∗n diag(Fn c)Fn ,nn(3.1.4)64ãäå Fn ìàòðèöà Ôóðüå ïîðÿäêà n, à Dn äèàãîíàëüíàÿ ìàòðèöàñîáñòâåííûõ çíà÷åíèé ìàòðèöû Cn λ1 0 · · · 0  0 λ2 · · · 0 Dn = , ··· ··· ··· ··· 00 · · · λnâèäà λ1 λ2 ···λn c0  c1 . = Fn  ··· cn−1(3.1.5)Ñëåäñòâèå 3.1.1.

Ñïðàâåäëèâà ôîðìóëàC−1n =1 ∗ −1F D Fn .n n n(3.1.6)Óìíîæåíèå ìàòðèöû Ôóðüå Fn íà âåêòîð-ñòîëáåö x ∈ Cn íàçûâàåòñÿïðÿìûìïðåîáðàçîâàíèåìÔóðüåâåêòîðàx.Êëàññè÷åñêîåïðàâèëîóìíîæåíèÿ ìàòðèöû ïîðÿäêà n íà âåêòîð òðåáóåò n2 îïåðàöèé. Îäíàêîóìíîæåíèå ìàòðèöû Fn íà âåêòîð ìîæåò áûòü âûïîëíåíî çà O(n log2 n)îïåðàöèé. Ïðè ýòîì n íå îáÿçàíî áûòü ñòåïåíüþ äâîéêè.Èìååò ìåñòî ñëåäóþùèå óòâåðæäåíèÿ.Óòâåðæäåíèå 3.1.2.

Äëÿ ëþáîãî n ïðîèçâåäåíèå ìàòðèöû Fn íà âåêòîð(äèñêðåòíîå ïðåîáðàçîâàíèå Ôóðüå) è ïðîèçâåäåíèå ìàòðèöû F−1n íà âåêòîð(îáðàòíîå äèñêðåòíîå ïðåîáðàçîâàíèå Ôóðüå) ìîãóò áûòü âûïîëíåíû çàO(n log2 n) îïåðàöèé.Ñëåäñòâèå 3.1.2. Äëÿ ëþáîãî n óìíîæåíèå öèðêóëÿíòíîé ìàòðèöû Cníà âåêòîð ìîæåò áûòü âûïîëíåíî çà O(n log2 n) îïåðàöèé.Ñëåäñòâèå 3.1.3.

Äëÿ ëþáîãî n ñèñòåìà óðàâíåíèé ñ íåâûðîæäåííîéöèðêóëÿíòíîéìàòðèöåéàðèôìåòè÷åñêèõ îïåðàöèé.CnìîæåòáûòüðåøåíàçàO(n log2 n)65Ò¼ïëèöåâû ìàòðèöû îáëàäàþò ñëåäóþùèì çàìå÷àòåëüíûì ñâîéñòâîì.Ëåììà 3.1.1. Äëÿ ïðîèçâîëüíîé òåïëèöåâîé ìàòðèöû An ïîðÿäêà nìîæíî íàéòè îêàéìëÿþùèé å¼ öèðêóëÿíòB  AnCN = ,D AN −nèìåþùèé ïîðÿäîê N , ðàâíûé ñòåïåíè äâîéêè è óäîâëåòâîðÿþùèé äâîéíîìóíåðàâåíñòâó 2n 6 N 6 4n − 2.Ñëåäñòâèå 3.1.4.

Äëÿ ëþáîãî n ò¼ïëèöåâà ìàòðèöà ïîðÿäêà n ìîæåòáûòü óìíîæåíà íà âåêòîð ñ çàòðàòîé O(n log2 n) àðèôìåòè÷åñêèõîïåðàöèé.Äåéñòâèòåëüíî, âû÷èñëèâxu  = CN   ,0vïîëó÷èì u = An x.3.2Öèðêóëÿíòíî ïðåäîáóñëîâëåííûé ìåòîä ñîïðÿæåííûõãðàäèåíòîâ3.2.1Ìåòîä ñîïðÿæåííûõ ãðàäèåíòîâ.Ìåòîä ñîïðÿæåííûõ ãðàäèåíòîâ (ìåòîä CG1 ) ïî ïðàâó ðàññìàòðèâàåòñÿêàê îäèí èç íàèáîëåå ýôôåêòèâíûõ èòåðàöèîííûõ ìåòîäîâ ðåøåíèÿ ñèñòåìëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèéAn x = b1 îòàíãë. conjugate gradient(3.2.1)66ñ ñàìîñîïðÿæåííîé ïîëîæèòåëüíî îïðåäåëåííîé ìàòðèöåé An .Íàïîìíèì ýòîò ìåòîä.

Ïóñòü x(0) - íà÷àëüíîå ïðèáëèæåíèå ê ðåøåíèþ x̄,r(0) = b − An x(0) - íà÷àëüíîå çíà÷åíèå íåâÿçêè, p(0) = r(0) . Ïðèáëèæåíèÿx(k+1) è íåâÿçêè r(k+1) = b − An x(k+1) ïðè k ≥ 0 âû÷èñëÿþòñÿ ïî ôîðìóëàì:x(k+1)=x(k)(k)+ αk p ,kr(k) k2,αk =(An p(k) , p(k) )(3.2.2)(3.2.3)r(k+1) = r(k) − αk An p(k) ,(k+1)p(k+1)=r(k)+ βk p ,kr(k+1) k2βk =kr(k) k2(3.2.4)Ñïðàâåäëèâà ñëåäóþùàÿ îöåíêà ïîãðåøíîñòè ìåòîäà ñîïðÿæåííûõãðàäèåíòîâ:kx(n) − x̄kAn 6p2ρnkx(0) − x̄kAn ,2n1+ρ(3.2.5)cond2 (An ) − 1ãäå ρ = p, à cond2 (An ) = λmax (An )/λmin (An ) - ÷èñëîcond2 (An ) + 1îáóñëîâëåííîñòè ìàòðèöû An .3.2.2Ñâåðõëèíåéíàÿ ñêîðîñòü ñõîäèìîñòè ìåòîäà CG.Îöåíêà (3.2.5), êàçàëîñü áû, óêàçûâàåò íà òî, ÷òî ìåòîä ñîïðÿæåííûõãðàäèåíòîâ îáëàäàåò ëèíåéíîé ñêîðîñòüþ ñõîäèìîñòè.

Îäíàêî îíà ÷àñòîáûâàåò÷ðåçìåðíîïåññèìèñòè÷íîéèíåîáúÿñíÿåòòîíêèõñâîéñòâñõîäèìîñòè, ïðèñóùèõ ìåòîäó ñîïðÿæåííûõ ãðàäèåíòîâ. Äëÿ ìåòîäà ñkx(k+1) − x̄kAnëèíåéíîé ñêîðîñòüþ ñõîäèìîñòè îòíîøåíèåïðàêòè÷åñêè íåkx(k) − x̄kAnìåíÿåòñÿ ñ ðîñòîì k . Òåì íå ìåíåå, îïûò ïðèìåíåíèÿ ìåòîäà ñîïðÿæåííûõãðàäèåíòîâ ïîêàçàë, ÷òî ýòî îòíîøåíèå îáû÷íî óáûâàåò ñ ðîñòîì k , è â õîäåèòåðàöèîííîãî ïðîöåññà íàáëþäàåòñÿ óñêîðåíèå ñêîðîñòè ñõîäèìîñòè ìåòîäà. 1986 ã. Âàíäåðñëþèñ è Âàíäåðâîðñò äàëè òåîðåòè÷åñêîå îáîñíîâàíèåýòîãî ýôôåêòà [76], ïîëó÷èâøåãî íàçâàíèå ñâåðõëèíåéíîé ñõîäèìîñòè.67Îêàçàëîñü, ÷òî ìåòîä CG (â òî÷íîé àðèôìåòèêå) ÷åðåç íåêîòîðîå âðåìÿíà÷èíàåò âåñòè ñåáÿ òàê, áóäòî â ìàòðèöå An èñ÷åçëè êðàéíèå ñîáñòâåííûåçíà÷åíèÿ λ1 = λmin (An ) è λn = λmax (An ); çàòåì òàê, áóäòî èñ÷åçëèñîáñòâåííûå çíà÷åíèÿ λ2 è λn−1 , è òàê äàëåå.

Òàêèì îáðàçîì, âëèÿíèåêðàéíèõ ñîáñòâåííûõ çíà÷åíèé ñêàçûâàåòñÿ òîëüêî íà ïåðâûõ èòåðàöèÿõè ñóùåñòâåííûì îêàçûâàåòñÿ ðàñïðåäåëåíèå îñíîâíîé ÷àñòè ñîáñòâåííûõçíà÷åíèé.3.2.3Ïðåäîáóñëîâëåííûé ìåòîä ñîïðÿæåííûõ ãðàäèåíòîâ.×àñòî äëÿ ñèñòåì, âîçíèêàþùèõ â ïðèëîæåíèÿõ, cond2 (An ) >> 1. Òîãäàâ îöåíêå (3.2.5) âåëè÷èíà ρ ≈ 1 − 2/pcond2 (An ), îïðåäåëÿþùàÿ ñêîðîñòüñõîäèìîñòè ìåòîäà, áëèçêà ê åäèíèöå è ñêîðîñòü ñõîäèìîñòè ìåòîäà ìîæåòîêàçàòüñÿ íåäîñòàòî÷íî âûñîêîé.Äëÿ òîãî, ÷òîáû óñêîðèòü ñõîäèìîñòü èòåðàöèîííîãî ìåòîäà, èñïîëüçóþòïðåäîáóñëîâëèâàíèå çàìåíÿþò ñèñòåìó (3.2.1) ýêâèâàëåíòíîé ñèñòåìîé−1C−1n An x = Cn b,(3.2.6)äëÿ êîòîðîé ìåòîä ñõîäèòñÿ ñóùåñòâåííî áûñòðåå. Èñïîëüçóåìàÿ äëÿ òàêîãîïðåîáðàçîâàíèÿ ìàòðèöà Cn íàçûâàåòñÿ ïðåäîáóñëîâëèâàòåëåì.Ïóñòü Cnñîïðÿæåííûõ=C∗n>ãðàäèåíòîâ0.

Íåïîñðåäñòâåííî ê ñèñòåìå (3.2.6) ìåòîäíåïðèìåíèì,òàêêàêìàòðèöàC−1n An íåîáÿçàíà áûòü ñàìîñîïðÿæåííîé. Ïðåäïîëîæèì, ÷òî ïðåäîáóñëîâëèâàòåëüïðåäñòàâëåí â âèäå Cn = B∗n Bn , ãäå Bn íåâûðîæäåííàÿ êâàäðàòíàÿ1/2ìàòðèöà. (Íàïðèìåð, ìîæíî âçÿòü Bn = Cn .) Óìíîæèì ñëåâà ëåâóþ èïðàâóþ ÷àñòè ñèñòåìû (3.2.6) íà Bn è ïîëîæèì y = Bn x.  ðåçóëüòàòå68ïðèäåì ê ýêâèâàëåíòíîé ñèñòåìå(3.2.7)ee n y = b,Ae = (B∗ )−1 b.e n = (B∗ )−1 An B−1 , bâ êîòîðîé Annnen = Ae ∗ > 0. Îáðàòèì òàêæå âíèìàíèå íà òî, ÷òîÇàìåòèì, ÷òî Aneìàòðèöû C−1n An è An ïîäîáíû; ñëåäîâàòåëüíî îíè îáëàäàþò îáùèì íàáîðîìñîáñòâåííûõ çíà÷åíèé.Ïðèìåíèì äëÿ ðåøåíèÿ ñèñòåìû (3.2.7) ìåòîä ñîïðÿæåííûõ ãðàäèåíòîâe−Ae n y(0) (3.2.2) - (3.2.4).

Ïóñòü y(0) - íà÷àëüíîå ïðèáëèæåíèå, s(0) = bíà÷àëüíîå çíà÷åíèå íåâÿçêè è q(0) = s(0) . Ïðèáëèæåíèÿ y(k+1) è íåâÿçêèe−Ae n y(k+1) ïðè k ≥ 0 âû÷èñëÿþòñÿ ïî ôîðìóëàì:s(k+1) = by(k+1)=y(k)(k)+ αk q ,αn =ks(k) k2e n q(k) , q(k) )(A,e n q(k) ,s(k+1) = s(k) − αk Aq(k+1) = s(k+1) + βk q(k) ,βk =ks(k+1) k2.ks(k) k2Èñïîëüçóÿ òåïåðü ôîðìóëû ñâÿçè y(k) = Bn x(k) , s(k) = (B∗n )−1 r(k) , q(k) =Bn p(k) , ïðèõîäèì ê ïðåäîáóñëîâëåííîìó ìåòîäó ñîïðÿæåííûõ ãðàäèåíòîâ(ìåòîäó PCG2 ):r(0) = b − An x(0) ,x(k+1)=x(k)s(0) = (B∗n )−1 r(0) ,(k)+ αk p ,(0)p(0) = B−1n s ,ks(k) k2αk =,(An p(k) , p(k) )r(k+1) = r(k) − αk An p(k) ,s(k+1) = (B∗n )−1 r(k+1) ,p(k+1)=z(k+1)(k+1)z(k+1) = B−1,n s(k)+ βk p ,ks(k+1) k2.βk =ks(k) k2Ôîðìóëû ýòîãî ìåòîäà ìîæíî ïåðåïèñàòü òàê, ÷òîáû ðàáîòàòü òîëüêî ñ2 îòàíãë.

preconditioned conjugate gradient69ìàòðèöåé Cn :r(0) = b − An x(0) ,x(k+1)(k+1)p=x(k)(0)p(0) = C−1n r ,(k)+ αk p ,(3.2.8)z(0) = p(0) ,(r(k) , z(k) )αk =,(An p(k) , p(k) )(3.2.9)r(k+1) = r(k) − αk An p(k) ,(3.2.10)(k+1)z(k+1) = C−1,n r(3.2.11)(k+1)=z(k)+ βk p ,(r(k+1) , z(k+1) ).βk =(r(k) , z(k) )(3.2.12)Îñíîâíûå âû÷èñëèòåëüíûå çàòðàòû â ìåòîäå CG (3.2.2) - (3.2.4) ñâÿçàíûñ óìíîæåíèåì ìàòðèöû An íà âåêòîð p(k) . Ïîñêîëüêó íà êàæäîé èòåðàöèèìåòîäà PCG (3.2.8) - (3.2.12) ïðèõîäèòñÿ äîïîëíèòåëüíî ðåøàòü ñèñòåìûñ ìàòðèöåé Cn , òî âðåìÿ, çàòðà÷èâàåìîå íà ðåøåíèå ýòèõ ñèñòåì, äîëæíîáûòü ñðàâíèìî ñ âðåìåíåì, íåîáõîäèìûì äëÿ óìíîæåíèÿ ìàòðèöû íà âåêòîð.Êðîìå òîãî, íåîáõîäèìî ó÷èòûâàòü ïðåäâàðèòåëüíûå çàòðàòû íà ïîñòðîåíèåïðåäîáóñëîâëèâàòåëÿ Cn .Îáû÷íî, ðóêîâîäñòâóÿñü îöåíêîé (3.2.5) ñòàðàþòñÿ âûáðàòüe n ) << cond2 (An ).

Îäíàêî,ïðåäîáóñëîâëèâàòåëü Cn òàê, ÷òîáû cond2 (Aíàëè÷èå ó ìåòîäà ñîïðÿæåííûõ ãðàäèåíòîâ ñâîéñòâà ñâåðõëèíåéíîéñõîäèìîñòè ïîçâîëÿåò èñïîëüçîâàòü è äðóãóþ ñòðàòåãèþ ïðåäîáóñëîâëèâàíèÿ.Ïðåäîáóñëîâëèâàòåëü ìîæíî âûáèðàòü òàê, ÷òîáû îñíîâíàÿ ÷àñòü ñïåêòðàe n îêàçàëàñü êëàñòåðèçîâàííîé âáëèçè åäèíèöû è ëèøü íåáîëüøàÿìàòðèöû A÷àñòü ñîáñòâåííûõ ÷èñåë îêàçàëàñü îòäåëåíà îò åäèíèöû.3.2.4Öèðêóëÿíòíîïðåäîáóñëîâëåííûéìåòîäñîïðÿæåííûõãðàäèåíòîâ. 1986 ãîäó Strang [77] è Olkin [78] íåçàâèñèìî ïðåäëîæèëè èñïîëüçîâàòüöèðêóëÿíòíûåìàòðèöûâêà÷åñòâåïðåäîáóñëîâëèâàòåëåéâìåòîäå70ñîïðÿæåííûõ ãðàäèåíòîâ ïðè ðåøåíèè ñèñòåì ñ òåïëèöåâûìè ìàòðèöàìè.Ïóñòü Cn = C∗n > 0 - öèðêóëÿíòíûé ïðåäîáóñëîâëèâàòåëü.

 ñèëóðàçëîæåíèÿ Cn =1 ∗n Fn Dn Fnåãî ìîæíî ïðåäñòàâèòü â âèäå Cn = B∗n Bn ,1 1/2nöèðêóëÿíòíî ïðåäîáóñëîâëåííûé ìåòîä ñîïðÿæåííûõ ãðàäèåíòîâ (ìåòîäãäå Bn = √ Dn Fn . Ìåòîä PCG ñ òàêèì ïðåäîáóñëîâëèâàòåëåì è åñòüCPCG). Çàìåòèì, ÷òî äëÿ ïîñòðîåíèÿ äèàãîíàëüíîé ìàòðèöû Dn òðåáóåòñÿëèøü O(n log2 n) îïåðàöèé.Íà êàæäîé èòåðàöèè ýòîãî ìåòîäà íåîáõîäèìî óìíîæàòü òåïëèöåâó1 ∗Fn Dn Fn r(k+1) . Òàêèìnñîñòàâëÿþò ëèøü O(n log2 n)ìàòðèöó An íà âåêòîð p(k) è âû÷èñëÿòü z(k+1) =îáðàçîì,çàòðàòûíàîäíóèòåðàöèþàðèôìåòè÷åñêèõ îïåðàöèé.Ïåðâûå âû÷èñëèòåëüíûå ýêñïåðèìåíòû ïîêàçàëè, ÷òî ýòîò ìåòîä ñõîäèòñÿî÷åíü áûñòðî è ïîçâîëÿåò ñ âûñîêîé òî÷íîñòüþ íàõîäèòü ðåøåíèÿ ñèñòåìñ òåïëèöåâûìè ìàòðèöàìè ëèøü çà O(n log2 n) àðèôìåòè÷åñêèõ îïåðàöèé.Òåîðåòè÷åñêîå îáîñíîâàíèå ñâåðõëèíåéíîé ñõîäèìîñòè ìåòîäà äëÿ øèðîêîãîêëàññà òåïëèöåâûõ ìàòðèö áûëî äàíî â [79].

Îêàçàëîñü, ÷òî îïðåäåëÿþùóþðîëü â íàëè÷èè áûñòðîé ñâåðõëèíåéíîé ñõîäèìîñòè èãðàåò êëàñòåðèçàöèÿñîáñòâåííûõ çíà÷åíèé ïðåäîáóñëîâëåííîé ìàòðèöû âáëèçè 1.Îïðåäåëåíèå 3.2.1. Ïóñòü εe n ) ÷èñëî ñîáñòâåííûõ> 0 è Nε (Ae n , óäîâëåòâîðÿþùèõ íåðàâåíñòâó |λi (Ae n ) − 1| >çíà÷åíèé ìàòðèöû Aε.Ãîâîðÿò,÷òîñîáñòâåííûåçíà÷åíèÿñåìåéñòâàìàòðèöe n}{Aenêëàñòåðèçóþòñÿ âáëèçè 1, åñëè äëÿ âñåõ ε > 0 è âñåõ ìàòðèö Ae n) ≤ N ε ñèç ðàññìàòðèâàåìîãî ñåìåéñòâà ñïðàâåäëèâà îöåíêà Nε (Ae n.ïîñòîÿííîé N ε , íå çàâèñÿùåé îò A71Ïðè íàëè÷èè êëàñòåðèçàöèè äëÿ ìåòîäà CPCG ñïðàâåäëèâà îöåíêà [79]kx(k) − xkAb n ≤ C(ε)εk kx(0) − xkAb n ,−1/2ãäå Ân = Cnb n = C−1/2 An C−1/2 .ãäå Ann−1/2An CnÏåðâûé öèðêóëÿíòíûé ïðåäîáóñëîâëèâàòåëü Cn , ïðåäëîæåííûé Ñòðýíãîìâ [77] îïðåäåëÿåòñÿ ýëåìåíòàìè ñàìîñîïðÿæåííîé òåïëèöåâîé ìàòðèöû Anñëåäóþùèì îáðàçîì: ck = ak äëÿ 0 ≤ k < n/2, ck = Re ak äëÿ k = n/2 èck = ak−n äëÿ n/2 < k < n.Îäíî èõ ñâîéñòâ ïðåäîáóñëîâëèâàòåëÿ Ñòðåíãà ñîñòîèò â òîì, ÷òîîí ìèíèìèçèðóåò íîðìû kCn − An k1 è kCn − An k∞ íà êëàññå âñåõñàìîñîïðÿæåííûõ öèðêóëÿíòíûõ ìàòðèö.Çàòåì áûëî ïðåäëîæåíî çíà÷èòåëüíîå ÷èñëî äðóãèõ öèðêóëÿíòíûõïðåäîáóñëîâëèâàòåëåé (ñì., íàïðèìåð, [79][87], îïòèìàëüíûõ â òîì èëèèíîì ñìûñëå.