Реализация алгоритма построения коммутирующих дифференциальных операторов по геометрическим данным (526733), страница 3
Текст из файла (страница 3)
Äàííàÿ ïðîöåäóðà íóæíà÷òîáû âîññòàíîâèòü îïåðàòîð ñ êîýôôèöèåíòàìè â âèäå äðîáíîðàöèîíàëüíûõ ôóíêöèé.Âñå âû÷èñëåíèÿ èñïîëüçóþò ïàêåò òî÷íûõ ðàöèîíàëüíûõ ÷èñåë, ïîýòîìó ëþáûå ðåçóëüòàòû ÿâëÿþòñÿ àáñîëþòíî òî÷íûìè è íå íóæäàþòñÿâ îöåíêå ïîãðåøíîñòè.7.1ÏñåâäîäèôôåðåíöèàëüíûåDPolynom.cpp, DPolynom.hîïåðàòîðû.Äëÿ ïðåäñòàâëåíèÿ ïñåâäîäèôôåðåíöèàëüíûõ îïåðàòîðîâ èñïîëüçóåòñÿøàáëîííûé êëàññ DPolynom<T>. Øàáëîí T ïðåäñòàâëÿåò òèï äàííûõ,èñïîëüçóåìûé â êà÷åñòâå êîýôôèöèåíòîâ.
Ïðåäóñìîòðåíî èñïîëüçîâàíèåìíîãî÷ëåíîâ, ðÿäîâ Òåéëîðà è ðàöèîíàëüíûõ ôóíêöèé, ðåàëèçîâàííûõñîîòâåòñâóþùèìè êëàññàìè. Äàëåå ïðèâåäåíû çàãîëîâêè è îïèñàíèå ÷ëåíîâ è ìåòîäîâ êëàññà. Ïñåâäîäèôôåðåíöèàëüíûé îïåðàòîð õðàíèòñÿ â14âèäå ìàññèâà êîýôôèöèåíòîâ ìîíîìîâ ñî ñòåïåíè n ïî ñòåïåíü m. Ìîíîìû ñòåïåíè o è ìëàäøå ìû ñ÷èòàåì íåèçâåñòíûìè. Åñëè îïåðàòîðïðåäñòàâëåí òî÷íî o = n + 1. Ýòî ïîçâîëÿåò ðåàëèçîâûâàòü êàê äèôôåðåíöèàëüíûå îïåðàòîðû, òàê è ïñåâäîäèôôåðåíöèàëüíûå îïåðàòîðû,íå èìåþùèå êîíå÷íîãî ÿâíîãî ïðåäñòàâëåíèÿ.template <typename T>class DPolynom{private:....public:int n;int m;int o;T* a; //......DPolynom(const T& b); //Ìàññèâ êîýôôèöèåíòîâêîíñòðóêòîð, ñîçäàþùèé îïåðàòîð íóëåâîéñòåïåíè ñ çàäàííûì êîýôôèöèåíòîì b//Ñëîæåíèå, óìíîæåíèå, âû÷èòàíèå, óíàðíûé ìèíóñDPolynom operator+ (const DPolynom&) const;DPolynom operator- (const DPolynom&) const;DPolynom operator* (const DPolynom&) const;DPolynom operator- () const;static DPolynom D(); //∂static DPolynom D(int);∂n//Ñîçäàåò îïåðàòîðÑîçäàåò îïåðàòîðÄàëåå, àðãóìåíò - ñòåïåíü ìîíîìà ñ òî÷íîñòüþ äî êîòîðîé íóæíî ïðîèçâåñòè âû÷èñëåíèåDPolynom sopr(int) const; //Âû÷èñëåíèå ñîïðÿãàþùåãî îïåðàòîðàDPolynom obr(int) const; //Âû÷èñëåíèå îáðàòíîãî îïåðàòîðàDPolynom sqr(int) const; //Âû÷èñëåíèå êîðíÿ};7.2.....Óìíîæåíèå(DPolynom.cpp)for (int i = n; i >= m;i)for (int j = b.n; j >= b.m; j) {big_int Cni = 1; //big_int ir = 0;dBj = b[j]; //bjåíòàáèíîìèàëüíûé êîýôôèöèåíòdBj - äèíàìè÷åñêè âû÷èñëÿåìàÿ ïðîèçâîäíàÿ êîýôôèöè15for (int p = i + j; p >= c.m; p) {c[p] = c[p] + ((*this)[i] * dBj) *(Cni); //ñ - ðåçóëüòàòèðóþùèé îïåðàòîðif (p > c.m) dBj = dBj.d(); //äèíàìè÷åñêîå âû÷èñëåíèå ïðîèçâîäíîéCni *= (i-ir);ir++;Cni /= ir;}}Ïðè óìíîæåíèè ÏÄÎan ∂ n1 + an1 −1 ∂ n1 −1 + ...
+ am ∂ m1 + ...bn ∂ n2 + bn2 −1 ∂ n2 −1 + ... + bm ∂ m2 + ...Ñëîæíîñòü àëãîðèòìà :êîëè÷åñòâî öèêëîâ: (n1 − m1 + 1) ∗ (n2 − m2 + 1) ∗ (n1 + n2 − min(n1 +m2 , n2 + m1 ))/2 = O(n3 ) ãäå n - êîëè÷åñòâî ÷ëåíîâ â ðåçóëüòèðóþùåìîïåðàòîðåÂíóòðè öèêëà äèíàìè÷åñêè ñ÷èòàþòñÿ ïðîèçâîäíûå è áèíîìèàëüíûå êîýôôèöèåíòû. Ñëîæíîñòü îäíîãî öèêëà îïðåäåëÿåòñÿ óìíîæåíèåìäâóõ êîýôôèöèåíòîâ è äèôôåðåíöèðîâàíèåì êîýôôèöèåíòà.7.3Èçâëå÷åíèå êîðíÿ(DPolynom.cpp)Áóäåì ðåøàòü óðàâíåíèå Ln = P , ãäå n - ïîðÿäîê îïåðàòîðà PÏðåäïîëàãàåì ÷òî P [n] = 1Ïóñòü íàì èçâåñòíû êîýôôèöèåíòû ñ 1 ïî j+1 îïåðàòîðà P;Lj - îïåðàòîð, êîýôôèöèåíòû êîòîðîãî ñ 1 ïî j+1 ñîâïàäàþò ñ êîýôôèöèåíòàìè L;Pj = Lnjñîñòàâèì óðàâíåíèå íà j-é êîýôôèöèåíò îïåðàòîðà L(Lj + L[j]∂ j )n = (∂ + L[0] + L[−1]∂ −1 + ...
+ L[j + 1]∂ j+1 + L[j]∂ j )n = PP [n + j − 1] = Pj [n + j − 1] + nL[j]L[j] = (P [n + j − 1] − Pj [n + j − 1])/nÒàêèì îáðàçîì, êîýýôèöèåíòû îïåðàòîðà L ìîæíî âû÷èñëÿòü ïîñëåäîâàòåëüíî. Êîä, ðåàëèçóþùèé èçâëå÷åíèå êîðíÿ:.............for (int m = 1; m >= accuracy; m) {L[m] = T::id_add();DPolynom<T> Pj(L);16for (int i = 1; i < n; i++) Pj = Pj * L;T k;k = ((*this)[n + m - 1] - Pj[n + m - 1]);if (m < 1) k = k / n;L[m] = k;}Ñëîæíîñòü àëãîðèòìà: Ïðè âû÷èñëåíèè êàæäîãî êîýôôèöèåíòà îïåðàòîðà L íóæíî âîçâåñòè â n-þ ñòåïåíü Lj , ïðîèçâåñòè âû÷èòàíèå êîýôôèöèåíòîâ.
Åñëè ìû ñ÷èòàåì ñ òî÷íîñòüþ äî - m -ãî ÷ëåíà êîëè÷åñòâîóìíîæåíèé O(m ∗ n) Ñëîæíîñòü óìíîæåíèÿ O(m3 ) Èòîãî O(n ∗ m4 ) ïðîèçâäåíèé è äèôôåðåíöèðîâàíèé êîýôôèöèåíòîâ.7.4Âû÷èñëåíèå îáðàòíîãî îïåðàòîðà(DPolynom.cpp)Ïóñòü ñòàðøèé ìîíîì S ñòåïåíè íîëü è ðàâåí åäèíèöå. Èäåÿ àëãîðèòìàòà æå, ÷òî è â ïðåäûäóùåì ðàçäåëå.
Áóäåì ðåøàòü óðàâíåíèåS −1 S = 1Ïóñòü Sj−1 - îïåðàòîð, êîýôôèöèåíòû êîòîðîãî äî j+1 ñîâïàäàþò ñêîýôôèöèåíòàìè S −1 ;Ñîñòàâèì óðàâíåíèå íà jé êîýôôèöèåíò S −1(Sj−1 + S −1 [j]∂ j ) · S = 1S −1 [j] = −(Sj−1 S)[j]Áóäåì ïîñëåäîâàòåëüíî âû÷èñëÿòü êîýôôèöèåíòû îïåðàòîðà S −1.......for (int k= -1; k>= accuracy; k) {S[k] = (*this)[k];S1[k] = T::id_add();S1[k] = -(S1 * S)[k];}Äëÿ âû÷èñëåíèÿ êàæäîãî ñëåäóþùåãî êîýôôèöèåíòà, òðåáóåòñÿ âûïîëíèòü îäíî óìíîæåíèå. Ýòî äàåò ñëîæíîñòü O(n4 ) ãäå n - êîëè÷åñòâî÷ëåíîâ èñõîäíîãî îïåðàòîðà.7.5Âû÷èñëåíèåñîïðÿãàþùåãîðà(DPolynom.cpp)îïåðàòî-Êàê è â ïðåäûäóùèõ ñëó÷àÿõ, áóäåì âû÷èñëÿòü êîýôôèöèåíòû S ïîñëåäîâàòåëüíî.
Ââåäåì âñïîìîãàòåëüíûé îïåðàòîð SxÊîýôôèöèåíòû áóäåì âû÷èñëÿòü ïî ðåêóðåíòíûì ñîîòíîøåíèÿìS[0] = 1, Sx [0] = 017S −1 [k + 1] = −(S −1 S)[k + 1]Sx [k] =RL[k] − (S −1 Sx )[k]S[k] = Sx [k]Äëÿ âû÷èñëåíèÿ êàæäîãî ñëåäóþùåãî êîýôôèöèåíòà, òðåáóåòñÿ âûïîëíèòü äâà óìíîæåíèÿ. Ýòî äàåò ñëîæíîñòü O(n4 ) ãäå n - êîëè÷åñòâî÷ëåíîâ èñõîäíîãî îïåðàòîðà.7.6Âîññòàíîâëåíèå äðîáíî-ðàöèîíàëüíîé ôóíêöèèÐÿä Òåéëîðà áóäåì õðàíèòü â âèäå ðàöèîíàëüíîé äðîáè r, ýòî ïîçâîëÿåòâû÷èñëÿòü îáðàòíûé ðÿä çà âðåìÿ O(1) à âû÷èòàòü êîíñòàíòó çà O(n) èäåëèòü íà x çà O(1).
Äëÿ âû÷èñëåíèÿ r0 íóæíî ïðîñòî ðàçäåëèòü íóëåâîé÷ëåí ÷èñëèòåëÿ íà íóëåâîé ÷ëåí çíàìåíàòåëÿ. Çàâåäåì äâà ãëîáàëüíûõìàññèâà - êîýôôèöèåíòîâ ÷èñëèòåëÿ è çíàìåíàòåëÿ, äëÿ âû÷èñëåíèÿ îáðàòíîé äðîáè èëè äåëåíèÿ íà x, äîñòàòî÷íî ïðîñòî ñäâèíóòü óêàçàòåëè íà÷àëà ìàññèâà. Äëÿ âû÷èòàíèÿ êîíñòàíòû èñïîëüçóåòñÿ ïðîöåäóðàminus_c(rational< >) êîòîðàÿ íà âõîä ïîëó÷àåò ÷èñëî, êîòîðîå íóæíîâû÷åñòü èç äðîáíî-ðàöèîíàëüíîé ôóíêöèè, ïðåäñòàâëÿþùåé èñõîäíûéðÿä Òåéëîðà.Ñäåëàåì ðåêóðñèâíóþ ôóíêöèþ MakeRat(int k), êîòîðàÿ íà âõîä ïîëó÷àåò îäèí ïàðàìåòð - k = n − m, ãäå n è m - îöåíêè êîëè÷åñòâà ÷ëåíîâ÷èñëèòåëÿ è çíàìåíàòåëÿ èñêîìîé äðîáíî-ðàöèîíàëüíîé ôóíêöèè.Åñëè k < 0 è r0 6= 0, âû÷èñëèì îáðàòíóþ äðîáíî-ðàöèîíàëüíóþ ôóíêöèþ r−1 è ñâåäåì çàäà÷ó ê âîññòàíîâëåíèþ äðîáè R = Q(x)/P (x).
Èñõîäíàÿ äðîáü âû÷èñëÿåòñÿ êàê 1/RÅñëè 0 ≤ k èëè r0 = 0,R = (R − r0 )/x, deg P ≤ n − 1, deg Q ≤ mÇàäà÷à ñâîäèòñÿ ê íàõîæäåíèþ äðîáè R. R = R · x + r0 .Èñïîëíÿåìûé êîä:RatFunc MakeRat(int k)if (n < 1)return RatFunc(rational< >(rn[0]) / rational< >(rd[0]));RatFunc res;rational< > tmp;Polynom<big_int> x(1);x[1] = 1;if (rn[0] == 0){rn = &(rn[1]);n -= 1;18res = MakeRat(k-1);res = res * x;}else {if (k >= 0) {tmp = rational< >(rn[0]) / rational< > (rd[0]);minus_c(tmp);res=(MakeRat(k)+RatFunc(tmp.numerator()))/RatFunc(tmp.denominator());}if (k<0) {sw = rn;rn = rd;rd = sw;res = MakeRat(-k);res = RatFunc::id_mult() / res;}}return res;}Ïóñòü ñòåïåíè ÷èñëèòåëÿ è çíàìåíàòåëÿ èñêîìîé äðîáíîðàöèîíàëüíîé ôóíêöèè íå áîëåå ÷åì n. Òîãäà íàì ïîòðåáóåòñÿ íåáîëåå ÷åì 2n âû÷èòàíèé.
Êàæäîå âû÷èòàíèå ðàáîòàåò ëèíåéíîå ïî nâðåìÿ. Ñëîæíîñòü àëãîðèòìà ïîëó÷àåòñÿ O(n2 )8ÏðèìåðûÏóñòü ñïåêòðàëüíàÿ êðèâàÿ C ðàöèîíàëüíàÿ êðèâàÿ zy 2 − x3 = 0 âP2 ñ îäíîé îñîáåííîñòüþ â íóëå â âèäå "êàñïà òî÷êà P = (0 : 1 : 0).Äëÿòàêîé êðèâîé â [2] áûëè âû÷èñëåíû âñå ïðåäñòàâèòåëè ïàð Øóðàäëÿ âñåõ âîçìîæíûõ ïó÷êîâ áåç êðó÷åíèÿ ðàíãà 2. Âñå òàêèå ïó÷êè ÿâëÿþòñÿ ëèáî ðàçëîæèìûìè, ò.å. ïðÿìûìè ñóììàìè äâóõ ïó÷êîâ ðàíãà1, ëèáî íåðàçëîæèìûìè.  ïîñëåäíåì ñëó÷àå åñòü äâà îäíîïàðàìåòðè÷åñêèõ ñåìåéñòâà ïó÷êîâ-ñå÷åíèé âåêòîðíûõ ðàññëîåíèé (ñåìåéñòâî Àòüè èäîïîëíèòåëüíîå ñåìåéñòâî), è îäèí âûäåëåííûé íå ëîêàëüíî ñâîáîäíûéïó÷îê.Ïðèìåð ðàáîòû àëãîðèòìà• Âõîäíûå äàííûå (ìàòðèöà ïðîñòàíñòâà äëÿ ïó÷êà èç äîïîëíèòåëüíîãî ñåìåéñòâà):Ïðèìåð 1.1900010010010010000 0 0 00 −4 0 −20 0 0 00 2 0 1Ðàíã ïàðû Øóðà - 2.• Ñîïðÿãàþùèé îïåðàòîð â âèäå ðÿäîâ, âîññòàíîâëåíûé ïî òåîðåìåÑàòî1 + o(x21 ):∂ −1 10/11907x19 − 1216/5103x18 + 4096/243x17 + 17/47628x16 −256/1701x15 + 1024/81x14 + 1/9072x13 − 52/567x12 + 256/27x11 −10/189x9 + 64/9x8 − 1/36x6 + 16/3x5 + 4x2 + o(x20 )....:∂ −2−100424/35721x18 + 13141/31752x17 − 28648/1701x16 −100397/47628x15 +160/567x14 −796/63x13 −14339/9072x12 +4/21x11 −3583/378x10 − 32/27x9 + 8/63x8 − 64/9x7 − 8/9x6 + 1/12x5 − 16/3x4 −2/3x3 − 4x1 + o(x19 )....:∂ −3 14342/1701x17 − 50173/95256x16 − 8/189x15 + 1195/189x14 −32/81x13 − 4/189x12 + 7169/1512x11 − 8/27x10 − 1/126x9 + 32/9x8 −2/9x7 + 8/3x5 − 1/6x4 + 2x2 + o(x18 )....∂ −4 −14342/1701x16 + 50173/95256x15 + 8/189x14 − 1195/189x13 +32/81x12 + 4/189x11 − 7169/1512x10 + 8/27x9 + 1/126x8 − 32/9x7 +2/9x6 − 8/3x4 + 1/6x3 − 2x1 + o(x17 ) +O(∂ −5 )•Ñîïðÿãàþùèé îïåðàòîð ñ êîýôôèöèåíòàìè â âèäå ðàöèîíàëüíûõäðîáåé−7x6 +1008x2 −1∂x7 −336x3 +25242x3 −504x−4∂x7 −336x3 +2521 ++21x5 −168x3 −1008x −2∂x7 −336x3 +252+−42x4 +504x2 −3∂x7 −336x3 +252+Ñîîòâåòñòâóþùèå êîììóòèðóþùèå îïåðàòîðû ñëèøêîì ãðîìîçäêè,ïîýòîìó ìû èõ çäåñü íå ïðèâîäèì.Ïðîñòðàíñòâî W äëÿ îäíîãî ïðåäñòàâèòåëÿ ñåìåéñòâàÀòüè âûãëÿäèò òàê:Ïðèìåð2.W = h−1 + z − z 2 , z −1 + 1 + z 2 , z −2 , z −3 , .
. .i.20Ñîïðÿãàþùèé îïåðàòîð:S =1−4x3 + 36x2 + 12−1∂+∂ −2 .x4 + 12x + 12x4 + 12x + 12Êîììóòèðóþùèå îïåðàòîðû:P4 = ∂ 4 − 16+32x6 − 12x3 − 36x2 + 36 2∂(x4 + 12x + 12)2x9 + 6x7 − 54x6 − 144x5 + 90x4 − 288x3 + 216x2 + 648x + 648∂(x4 + 12x + 12)3+85x12 − 60x10 + 708x9 + 1692x8 − 864x7 − 5040x6(x4 + 12x + 12)4−11232x5 − 19440x4 − 8640x3 − 25920x − 25920(x4 + 12x + 12)4P6 = ∂ 6 − 24+96−36x6 − 12x3 − 36x2 + 36 4∂(x4 + 12x + 12)2x9 + 3x7 − 54x6 − 144x5 + 45x4 + 252x3 + 216x2 + 540x + 540 3∂(x4 + 12x + 12)33x12 + 60x10 − 1140x9 − 3100x8 + 864x7 + 10800x6 + 24672x5 + 37488x4 +15552x3 − 9216x2 + 28224x + 37440 2∂(x4 + 12x + 12)4−144x15 − 64x13 + 1047x12 + 3188x11 − 720x10 − 21924x9 − 68868x8 − 91536x7 +9936x6 + 135648x5 + 106128x4 + 94464x3 + 70848x2 − 171072x − 188352∂(x4 + 12x + 12)5+727x18 − 238x16 + 3168x15 + 11200x14 − 1056x13 − 131640x12 − 494016x11 −639264x10 + 496800x9 + 2575808x8 + 4008960x7 + 3489408x6 + 214272x5 −4060800x4 − 2889216x3 − 725760x2 − 4271616x − 3815424(x4 + 12x + 12)621Ïðèìåð 3.ãëÿäèò òàê:Ïðîñòðàíñòâî W äëÿ âûäåëåííîãî ïó÷êà áåç êðó÷åíèÿ âûW = h1, z −1 , z −2 , z −3 + z 2 , z −4 , z −5 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
