Диссертация (1149591), страница 10
Текст из файла (страница 10)
Ýòè ìåòîäû îïèñàíû âñëåäóþùåé ãëàâå.654.3. Îïðåäåëåíèå àìïëèòóä ðàññåÿíèÿ4.3.1. Îïðåäåëåíèå àìïëèòóä ðàññåÿíèÿ ïðîåêöèîííûì ìåòîäîì äàííîì ðàçäåëå ïðèâîäèòñÿ ïðèìåðíàÿ âû÷èñëèòåëüíàÿ ñõåìà ãèáðèäíîãî ïîäõîäà, îïèñàííîãî â ðàçäåëå 2.5. Íåñìîòðÿ íà òî, ÷òî îñíîâíûå øàãè îïèñûâàåìîé âû÷èñëèòåëüíîé ñõåìû ñîîòâåòñòâóþò ìåòîäó ïðèâåäåííîìóâ [46], èñïîëüçóåìàÿ çäåñü ðåàëèçàöèÿ ñîäåðæèò îðèãèíàëüíûå îñîáåííîñòè,êîòîðûå ïðèíîñÿò ñõåìå íîâîå êà÷åñòâî.
Ìû îïèøåì ïðîñòåéøèé ñëó÷àé, ñîîòâåòñòâóþùèé êâàðòåòíîìó ðàññåÿíèþ J = 3/2, è ïðåäïîëîæèì îïèñàííóþâûøå ñõåìó äèñêðåòèçàöèè óðàâíåíèÿ (2.8), õîòÿ ñàì ìåòîä îïðåäåëåíèÿ àìïëèòóä ïîäõîäèò äëÿ ðàçëè÷íûõ ñõåì.Óðàâíåíèå (2.8) ïîñëå äèñêðåòèçàöèè ïðèíèìàåò âèä (4.6) è ìîæåò áûòüêðàòêî çàïèñàíî â âèäå−U(ρ − ∆ρ) + 2 U(ρ) − U(ρ + ∆ρ)(∆ρ)−2 H − E U ≡+B(ρ)U(ρ)−EU(ρ) = 0.(∆ρ)2(4.7)Çäåñü B(ρ) ìàòðèöà ðàçìåðà Nθ × Nθ , êîòîðàÿ ñîîòâåòñòâóåò äèñêðåòèçîâàííîé äèàãîíàëüíîé ïî ρ ÷àñòè îïåðàòîðà èç óðàâíåíèÿ (2.8). Äëÿ ïðåäñòàâëåíèÿ ãðàíè÷íîãî óñëîâèÿ äëÿ ðåøåíèÿ óðàâíåíèÿ (4.7) ïðåäïîëîæèì, ÷òîïîñëåäíåå çíà÷åíèå ãèïåððàäèóñà ρNρ äîñòàòî÷íî áîëüøîå äëÿ òîãî, ÷òîáûðåøåíèå U(ρNρ ) íàõîäèëîñü â àñèìïòîòè÷åñêîé îáëàñòè (2.29). Ýòî ïîçâîëÿåòïðåäñòàâèòü ðåøåíèå ïðè ρNρ + h êàêU(ρNρ + ∆ρ) = φ0 (θ|ρNρ + ∆ρ) Y0 (q, ρNρ + ∆ρ) + a0 (q)H0 (q, ρNρ + ∆ρ) ++∞X√φk (θ|ρNρ + ∆ρ)ak (E)Hk ( E, ρNρ + ∆ρ),k=1ãäå φ0 (θ|ρNρ + ∆ρ) è φk (θ|ρNρ + ∆ρ) ïðè θ ∈ Nθ ïîíèìàþòñÿ êàê âåêòîðà ñ÷èñëîì êîìïîíåíò Nθ .
Èñïîëüçóÿ äàííîå âûðàæåíèå â ïîñëåäíåì óðàâíåíèè66(4.7) äëÿ ρ = ρNρ ìû ïðèõîäèì ê óðàâíåíèþ−U(ρNρ − ∆ρ) + 2U(ρNρ ) + (∆ρ)2 B(ρ)U(ρ) − (∆ρ)2 EU(ρ) =φ0 (θ|ρNρ + ∆ρ)Y0 (q, ρNρ + ∆ρ) + a0 (q)φ0 (θ|ρNρ + ∆ρ)H0 (q, ρNρ + ∆ρ)+XNφ+√ak (E)φk (θ|ρNρ + ∆ρ)Hk ( E, ρNρ + ∆ρ).(4.8)k=1Çäåñü ÷èñëî Nφ îáîçíà÷àåò êîëè÷åñòâî áàçèñíûõ ôóíêöèé èñïîëüçóþùèõñÿäëÿ ïðåäñòàâëåíèÿ ðåøåíèÿ. Ýòî âíåøíèé ïàðàìåòð, êîòîðûé îïðåäåëÿåò òî÷íîñòü ðåøåíèÿ è ôèêñèðóåòñÿ ïðè ðåøåíèè çàäà÷è. Àññîöèèðóÿ âåêòîðû Φ00 ,Φ10 è Φk ñî ñëàãàåìûìè â ïðàâîé ÷àñòè (4.8), ìû ìîæåì çàïèñàòü äèñêðåòíûé âàðèàíò óðàâíåíèÿ (4.7) ñ ââåäåííûìè ñîãëàñíî (4.8) àñèìïòîòè÷åñêèìãðàíè÷íûì óñëîâèåì â âèäå íåîäíîðîäíîãî ìàòðè÷íîãî óðàâíåíèÿH − (∆ρ) E U =2Φ00+a0 Φ10+NφXak Φk .(4.9)k=1Êîýôôèöèåíòû a0 è ak íåèçâåñòíû.
Äëÿ ïîëó÷åíèÿ ðåøåíèÿ, íåîáõîäèìîñäåëàòü ñëåäóþùåå:1) ðåøèì óðàâíåíèÿH − (∆ρ)2 E U00 = Φ00 ,H − (∆ρ)2 E U01 = Φ10 ,H − (∆ρ)2 E Uk = Φk , k = 1, 2, . . . , Nφ .2) ïîñòðîèì âåêòîðU=U00+a0 U01+NφXak Uk .(4.10)k=1ßñíî, ÷òî ýòîò âåêòîð äàåò ðåøåíèå äëÿ (4.9), åñëè èçâåñòíû êîýôôèöèåíòûa0 è ak .Äëÿ âû÷èñëåíèÿ íåèçâåñòíûõ êîýôôèöèåíòîâ a0 è ak , ìû ðàññìîòðèìU èç (4.10) ïðè ãèïåððàäèóñå ρ = ρNρ .  àñèìïòîòè÷åñêîé îáëàñòè ìîæíî67çàïèñàòüU00 (ρNρ , θ)+a0 U01 (ρNρ , θ)+NφXak Uk (ρNρ , θ) =k=1φ0 (θ|ρNρ )Y0 (q, ρNρ ) + a0 (q)φ0 (θ|ρNρ )H0 (q, ρNρ )++NφX(4.11)√ak (E)φk (θ|ρNρ )Hk ( E, ρNρ ).k=1Èñïîëüçóÿ îðòîãîíàëüíîñòü áàçèñíûõ ôóíêöèé è ïðîåöèðóÿ óðàâíåíèÿ (4.11)íà áàçèñíûå ôóíêöèè φl (.|ρN ), l = 0, .
. . , Nφ , ìû ïîëó÷àåì ñèñòåìó, ñîñòîÿùóþ èç Nφ + 1 óðàâíåíèé äëÿ Nφ + 1 íåèçâåñòíûõ àìïëèòóä alφ X1a0 hφ0 (.|ρNρ )|U0 (ρNρ , .)i − H0 (q, ρNρ ) +ak hφ0 (.|ρNρ )|Uk (ρNρ , .)i =Nk=1Y0 (q, ρNρ ) − hφ0 (.|ρNρ )|U00 (ρNρ , .)i,a0 hφl (.|ρNρ )|U01 (ρNρ , .)i +NφXak hφ0 (.|ρNρ )|Uk (ρNρ , .)i − δkl Hk (q, ρNρ ) =k=1−hφl (.|ρNρ )|U00 (ρNρ , .)i,l = 1, 2, . . . , Nφ .(4.12)Ðåøàÿ ýòó ñèñòåìó óðàâíåíèé è ïîäñòàâëÿÿ âû÷èñëåííûå êîýôôèöèåíòû a0è ak â (4.10), ìû îêîí÷àòåëüíî ïîëó÷àåì ÷èñëåííîå ðåøåíèå óðàâíåíèÿ (2.8).4.3.2.
Îïðåäåëåíèå àìïëèòóä ðàññåÿíèÿ èç ðåøåíèÿ íà äâóõ äóãàõÀìïëèòóäà áèíàðíîãî êàíàëà è àìïëèòóäà ðàçâàëà ìîæåò áûòü íàéäåíàïî ìåòîäó îïèñàííîìó â ðàáîòå [82].  ýòîì ìåòîäå, ðåøåíèå íà äóãå ρN +1âûðàæàåòñÿ ÷åðåç ðåøåíèå íà ïðåäûäóùåì øàãå, ρN , ñ÷èòàÿ àìïëèòóäû ðàññåÿíèÿ ïîñòîÿííûìè íà ñîîòâåòñòâóþùèõ äóãàõ. Àìïëèòóäà ðàçâàëà A(E, θ)ïðåäñòàâëÿåòñÿ ÷åðåç èñêîìîå ðåøåíèå√UN = φ0 (θ|ρN )(sin qρN + a0 exp iqρN ) + A(E, θ) exp i EρN68íà äóãå ρN è áèíàðíóþ àìïëèòóäó a0 êàê√A(E, θ) = exp (−i EρN )[UN − φ0 (θ|ρN )(sin qρN + a0 exp iqρN )].Çäåñü φ0 (θ|ρN ) ∼(4.13)√ρN ϕ(x) ïðè ρN → ∞, à ϕ(x) âîëíîâàÿ ôóíêöèÿ, äâóõ÷àñòè÷íîé ïîäñèñòåìû (2.3). Ïîëó÷åííîå âûðàæåíèå äëÿ àìïëèòóäû ðàçâàëàèñïîëüçîâàíî äëÿ ïðåäñòàâëåíèÿ èñêîìîãî ðåøåíèÿ íà ïîñëåäíåé äóãå ρN +1êîíå÷íî-ðàçíîñòíîé ñõåìû:UN +1 = φ0 (θ|ρN +1 )(sin qρN +1 + a0 exp iqρN +1 )+√+ exp i E(ρN +1 − ρN )[UN − φ0 (θ|ρN )(sin qρN + a0 exp iqρN )] ≡√≡ Φ0 + exp i E(ρN +1 − ρN )UN + a0 Φ1 .Çäåñü íåèçâåñòíûìè ÿâëÿþòñÿ òîëüêî èñêîìîå ðåøåíèå íà øàãå UN è àìïëèòóäà áèíàðíîãî êàíàëà a0 .
Òàêèì îáðàçîì, ñèñòåìà óðàâíåíèé çàìûêàåòñÿ.Ïåðåíîñÿ èçâåñòíûå âåêòîðû Φ0 è Φ1 â ïðàâóþ ÷àñòü, ìû ïðèõîäèì ê íåîäíîðîäíîìó óðàíåíèþ âèäà:√−UN −1 + 2UN − exp i E(ρN +1 − ρN )UN+ BUN = (∆ρ)−2 (Φ0 + a0 Φ1 ). (4.14)(∆ρ)2Ðåøåíèå ïîëó÷åííîãî íåîäíîðîäíîãî óðàâíåíèÿ èùåòñÿ â âèäå U = U0 +a0 U1 . ìåòîäå ðàáîòû [82], àìïëèòóäà áèíàðíîãî êàíàëà íàõîäèòñÿ èç ðàâåíñòâà ðåøåíèÿ àñèìïòîòèêå â òî÷êå ìàêñèìóìà âîëíîâîé ôóíêöèè φ0 (θ|ρN ):[U0,N + a0 U1,N = φ0 (θ|ρN )(sin qρN + a0 exp iqρN )]θ=θmaxÈç ïîëó÷åííîãî çíà÷åíèÿ a0 àìïëèòóäà ðàçâàëà A(E, θ) îïðåäåëÿåòñÿ ïî ôîðìóëå (4.13). íàñòîÿùåé äèññåðòàöèè äàííûé àëãîðèòì íàõîæäåíèÿ êîìïîíåíòû Ôàääååâà áûë ñêîìáèíèðîâàí ñ ïðîåêöèîííûì ìåòîäîì îïèñàííûì â ïðåäûäóùåìðàçäåëå. Ðåøåíèå íåîäíîðîäíîãî óðàâíåíèÿ (4.14) ïðèðàâíèâàåòñÿ àñèìïòîòè69êåU0,N + a0 U1,N = φ0 (θ|ρN )(sin qρN + a0 exp iqρN ) +NφX√ai φi (θ|ρN ) exp i EρNi=1(4.15)è ïðîåöèðóåòñÿ íà îðòîíîðìèðîâàííûé áàçèñ (2.13) èçâåñòíûõ ôóíêöèé φi (θ|ρ),i = 1, .
. . , Nφ . Ïîñëå ïðîåöèðîâàíèÿ íà áàçèñ ïîëó÷àåòñÿ ñèñòåìà ëèíåéíûõóðàâíåíèé àíàëîãè÷íàÿ (4.12) è èç íå¼ îïðåäåëÿåòñÿ àìïëèòóäà áèíàðíîãîêàíàëà a0 è êîýôôèöèåíòû ðàçëîæåíèÿ ai àìïëèòóäû ðàçâàëàA(E, θ, ρ) =NφXai φi (θ|ρ).i=14.4. Âûâîäû ê äàííîé ãëàâå äàííîé ãëàâå ïðåäñòàâëåí ìåòîä äèñêðåòèçàöèè ãðàíè÷íîé çàäà÷è, êîòîðûé èñïîëüçóåòñÿ äëÿ ðåøåíèÿ çàäà÷è ðàññåÿíèÿ äëÿ s-âîëíîâîãî óðàâíåíèÿ Ôàääååâà. Ñàì ïî ñåáå äàííûé ìåòîä íå ïîçâîëÿåò îïðåäåëèòü àìïëèòóäûðàññåÿíèÿ. Áèíàðíàÿ àìïëèòóäà è àìïëèòóäà ðàçâàëà ìîãóò áûòü íàéäåíû ñïîìîùüþ ïîäõîäîâ, êîòîðûå äåòàëüíî îïèñûâàþòñÿ â äàííîé ãëàâå. Ïðåäñòàâëåíû ïðîåêöèîííûé ïîäõîä äëÿ îïðåäåëåíèÿ àìïëèòóä è ìåòîä îïðåäåëåíèÿ àìïëèòóä èç ðåøåíèÿ çàäà÷è íà äâóõ äóãàõ.
Êàæäûé èç ýòèõ ïîäõîäîâîñíîâàí íà ðàçëè÷íûõ ñïîñîáàõ ó÷åòà ãðàíè÷íûõ óñëîâèé, âîññòàíîâëåíèÿêîìïîíåíòû Ôàääååâà è ïîëó÷åíèÿ àìïëèòóä ðàññåÿíèÿ. Äàííûå ïîäõîäû âîïðåäåëåííîé ñòåïåíè íå çàâèñÿò îò ìåòîäà äèñêðåòèçàöèè ãðàíè÷íîé çàäà÷è.70Ãëàâà 5Ñòðåëîâèäíàÿ äåêîìïîçèöèÿ äëÿáëî÷íî-òð¼õäèàãîíàëüíîé ÑËÀÓ äàííîé ãëàâå ïðåäñòàâëåí ìåòîä ñòðåëîâèäíîé äåêîìïîçèöèè, îáåñïå÷èâàþùèé ýôôåêòèâíîå ïàðàëëåëüíîå ðåøåíèå áëî÷íî-òð¼õäèàãîíàëüíîé ñèñòåìû ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé (ÑËÀÓ), âîçíèêàþùåé ïîñëå äèñêðåòèçàöèè êðàåâîé çàäà÷è, îïèñàííîé â ïðåäûäóùåé ãëàâå. Âû÷èñëèòåëüíîåóñêîðåíèå ïî îòíîøåíèþ ê ñòàíäàðòíîìó ìåòîäó ìàòðè÷íîé ïðîãîíêè îöåíåíî àíàëèòè÷åñêè ïóòåì ó÷åòà ÷èñëà ýëåìåíòàðíûõ îïåðàöèé óìíîæåíèÿ äëÿïàðàëëåëüíûõ è ïîñëåäîâàòåëüíûõ ÷àñòåé ìåòîäà äåêîìïîçèöèè.
Ïîêàçàíî,÷òî ìàêñèìàëüíîå óñêîðåíèå äîñòèãàåòñÿ ïðè êîíå÷íîì ÷èñëå ïàðàëëåëüíûõïðîöåññîðîâ. Äëÿ çàäàííîãî ðàçìåðà èñõîäíîé ÑËÀÓ ïîëó÷åíû ïàðàìåòðûâû÷èñëèòåëüíîé ñèñòåìû, ïðè êîòîðûõ äîñòèãàåòñÿ ìàêñèìàëüíîå óñêîðåíèå.Âû÷èñëèòåëüíûå ýêñïåðèìåíòû ïîäòâåðæäàþò àíàëèòè÷åñêèå îöåíêè âû÷èñëèòåëüíîãî óñêîðåíèÿ.5.1. ÂâåäåíèåÌíîãèå çàäà÷è ïðèêëàäíîé ìàòåìàòèêè è âû÷èñëèòåëüíîé ôèçèêè ïîñëå äèñêðåòèçàöèè ñâîäÿòñÿ ê ñèñòåìå ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé(ÑËÀÓ)Tx = fñ áëî÷íî-òð¼õäèàãîíàëüíîé ìàòðèöåé T .
 êà÷åñòâå ïðîñòåéøåãî ïðèìåðàìîæíî ïðèâåñòè êîíå÷íî-ðàçíîñòíóþ àïïðîêñèìàöèþ ãðàíè÷íîé çàäà÷è äëÿäâóìåðíîãî óðàâíåíèÿ Ïóàññîíà íà ðàâíîìåðíûõ ñåòêàõ ïî êàæäîé êîîðäèíàòå [85, 86].  ýòîì ñëó÷àå áëîêè ìàòðèöû T áóäóò ðàçðåæåííûìè.  äåéñòâèòåëüíîñòè, ìàòðèöà ÑËÀÓ áóäåò ïÿòèäèàãîíàëüíîé, íî ñ áëî÷íîé ñòðóê71òóðîé.
Ëåíòî÷íûå èëè çàïîëíåííûå áëîêè â òàêîé çàäà÷å ìîæíî ïîëó÷èòü,åñëè ñîâìåñòèòü êîíå÷íî-ðàçíîñòíóþ äèñêðåòèçàöèþ ïî îäíîé êîîðäèíàòå ñðàçëîæåíèåì ïî ñïëàéíàì èëè èíûì ôóíêöèÿì ïî äðóãîé êîîðäèíàòå.Ñðàâíèòåëüíî áûñòðûì ïðÿìûì àëãîðèòìîì äëÿ ðåøåíèÿ áëî÷íî-òð¼õäèàãîíàëüíûõ ñèñòåì ÿâëÿåòñÿ ìåòîä ìàòðè÷íîé ïðîãîíêè [87]. Òàêàÿ àäàïòàöèÿ êëàññè÷åñêîãî ìåòîäà Ãàóññà (LU -ðàçëîæåíèÿ) ðàññìàòðèâàåò áëîêè èñõîäíîé ìàòðèöû ìèíèìàëüíûìè ýëåìåíòàìè ê êîòîðûì ïðèìåíÿåòñÿ ìåòîä. îòëè÷èå îò ìåòîäà Ãàóññà äëÿ ïîëíîñòüþ çàïîëíåííîé áëî÷íîé ìàòðèöû ñN áëîêàìè íà äèàãîíàëè, âû÷èñëèòåëüíàÿ ñëîæíîñòü êîòîðîãî îòíîñèòåëüíî îïåðàöèé ñ áëîêàìè O(N 3 ), ìåòîä ìàòðè÷íîé ïðîãîíêè èìååò ñëîæíîñòüíà äâà ïîðÿäêà ìåíüøå O(N ).
Òàêèì îáðàçîì, äàííûé ìåòîä íå òîëüêî îáëàäàåò ñâîéñòâîì óñòîé÷èâîñòè äëÿ ìàòðèöû T ñ áëîêàìè ñ äèàãîíàëüíûìïðåîáëàäàíèåì, íî è ÿâëÿåòñÿ îïòèìàëüíûì îòíîñèòåëüíî îïåðàöèé ñ áëîêàìè. Íåäîñòàòêîì ìåòîäà ÿâëÿåòñÿ åãî ïîñëåäîâàòåëüíîñòü è òðóäíîñòü ïàðàëëåëèçàöèè íà ñîâðåìåííûõ ñóïåðêîìïüþòåðíûõ è êëàñòåðíûõ ñèñòåìàõ.Åäèíñòâåííîé âîçìîæíîñòüþ ïàðàëëåëèçàöèè â äàííîì ñëó÷àå ÿâëÿåòñÿ ïàðàëëåëèçàöèÿ íà óðîâíå ìàòðè÷íûõ îïåðàöèé óìíîæåíèÿ è îáðàùåíèÿ áëîêîâ.Ïàðàëëåëüíûå ìåòîäû ðåøåíèÿ òð¼õäèàãîíàëüíûõ ÑËÀÓ ðàçðàáàòûâàëèñü ñ êîíöà øåñòèäåñÿòûõ ãîäîâ äâàäöàòîãî âåêà.
Ê òàêèì ìåòîäàì ìîæíîîòíåñòè øèðîêî èçâåñòíûé ìåòîä öèêëè÷åñêîé ðåäóêöèè [88], à òàêæå ìåòîäÂîíãà [89], êîòîðûé óñïåøíî ïðèìåíÿåòñÿ â ñîâðåìåííûõ ðàñ÷åòàõ [90]. ÌåòîäÂîíãà áûë îáîáùåí äëÿ ñëó÷àÿ ëåíòî÷íûõ ìàòðèö â ðàáîòå [91]. Èç ïåðå÷èñëåííûõ ìåòîäîâ, íàèáîëåå áûñòðûì è ýôôåêòèâíûì ÿâëÿåòñÿ ìåòîä öèêëè÷åñêîé ðåäóêöèè. Òåì íå ìåíåå, ìàêñèìàëüíàÿ ýôôåêòèâíîñòü äàííîãî ìåòîäàäîñòèãàåòñÿ òîëüêî ïðè êîëè÷åñòâå ïàðàëëåëüíûõ ïðîöåññîðîâ, ñðàâíèìûì ñ÷èñëîì ýëåìåíòîâ íà äèàãîíàëè.  ïðîòèâíîì ñëó÷àå, êîãäà êîëè÷åñòâî ïàðàëëåëüíûõ âû÷èñëèòåëüíûõ óçëîâ íà ïîðÿäêè ìåíüøå ðàçìåðà ìàòðèöû,ýôôåêòèâíîñòü äàííîãî ìåòîäà ïàäàåò è ñòàíîâèòñÿ ìåíüøå, ÷åì ó ìåòîäà72Âîíãà.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
