पी-पुनरावर्ती समीकरण

Further information: holonomic function

गणित में पी-पुनरावर्ती समीकरण अनुक्रमों का एक रैखिक समीकरण है जहां गुणांक अनुक्रमों को बहुपद वलय के रूप में दर्शाया जा सकता है। पी-पुनरावर्ती समीकरण बहुपद गुणांकों के साथ रैखिक पुनरावृत्ति समीकरण (या रैखिक पुनरावृत्ति संबंध या रैखिक अंतर समीकरण) हैं। ये समीकरण गणित के विभिन्न क्षेत्रों में, विशेष रूप से साहचर्य में, महत्वपूर्ण भूमिका निभाते हैं। जो अनुक्रम इन समीकरणों के समाधान हैं उन्हें होलोनोमिक फ़ंक्शन, पी-पुनरावर्ती या डी-परिमित कहा जाता है।

1980 के दशक के उत्तरार्ध से, इन समीकरणों का समाधान खोजने के लिए पहला एल्गोरिदम विकसित किया गया था। सर्गेई ए. अब्रामोव, मार्को पेटकोवसेक और मार्क वैन होइज ने बहुपद, तर्कसंगत, हाइपरजियोमेट्रिक और डी'अलेम्बर्टियन समाधान खोजने के लिए एल्गोरिदम का वर्णन किया।

परिभाषा

होने देना ${\textstyle \mathbb {K} }$ विशेषता शून्य का एक क्षेत्र बनें (उदाहरण के लिए ${\textstyle \mathbb {K} =\mathbb {Q} }$), ${\textstyle p_{k}(n)\in \mathbb {K} [n]}$ के लिए बहुपद ${\textstyle k=0,\dots ,r}$,${\textstyle f\in \mathbb {K} ^{\mathbb {N} }}$ एक क्रम और ${\textstyle y\in \mathbb {K} ^{\mathbb {N} }}$ एक अज्ञात क्रम. समीकरण

$$\sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)$$

इसे बहुपद गुणांकों वाला एक रैखिक पुनरावृत्ति समीकरण कहा जाता है (इस आलेख में सभी पुनरावृत्ति समीकरण इसी रूप के हैं)। अगर ${\textstyle p_{0}}$ और ${\textstyle p_{r}}$ तो फिर दोनों शून्येतर हैं ${\textstyle r}$ समीकरण का क्रम कहलाता है. अगर ${\textstyle f}$ यदि शून्य है तो समीकरण को सजातीय कहा जाता है, अन्यथा इसे अमानवीय कहा जाता है।

इसे इस प्रकार भी लिखा जा सकता है ${\textstyle Ly=f}$ कहाँ ${\textstyle L=\sum _{k=0}^{r}p_{k}N^{k}}$ बहुपद गुणांकों वाला एक रैखिक पुनरावृत्ति ऑपरेटर है और ${\textstyle N}$ शिफ्ट ऑपरेटर है, यानी ${\textstyle N\,y(n)=y(n+1)}$.

बंद प्रपत्र समाधान

होने देना ${\textstyle \sum _{k=0}^{r}p_{k}(n)\,y(n+k)=f(n)}$ या समकक्ष ${\textstyle Ly=f}$ बहुपद गुणांकों के साथ एक पुनरावृत्ति समीकरण बनें। ऐसे कई एल्गोरिदम मौजूद हैं जो इस समीकरण के समाधान की गणना करते हैं। ये एल्गोरिदम बहुपद, तर्कसंगत, हाइपरजियोमेट्रिक और डी'अलेम्बर्टियन समाधानों की गणना कर सकते हैं। एक सजातीय समीकरण का समाधान रैखिक पुनरावृत्ति ऑपरेटर के कर्नेल (रैखिक बीजगणित) द्वारा दिया जाता है: ${\textstyle \ker L=\{y\in \mathbb {K} ^{\mathbb {N} }\,:\,Ly=0\}}$. अनुक्रमों के स्थान के उपस्थान के रूप में इस कर्नेल में एक आधार (रैखिक बीजगणित) होता है। होने देना ${\textstyle \{y^{(1)},y^{(2)},\dots ,y^{(m)}\}}$ का आधार बनें ${\textstyle \ker L}$, फिर औपचारिक योग ${\textstyle c_{1}y^{(1)}+\dots +c_{m}y^{(m)}}$ मनमाना स्थिरांक के लिए ${\textstyle c_{1},\dots ,c_{m}\in \mathbb {K} }$ सजातीय समस्या का सामान्य समाधान कहा जाता है ${\textstyle Ly=0}$. अगर ${\textstyle {\tilde {y}}}$ का एक विशेष समाधान है ${\textstyle Ly=f}$, अर्थात। ${\textstyle L{\tilde {y}}=f}$, तब ${\textstyle c_{1}y^{(1)}+\dots +c_{m}y^{(m)}+{\tilde {y}}}$ यह अमानवीय समस्या का समाधान भी है और इसे अमानवीय समस्या का सामान्य समाधान कहा जाता है।

बहुपद समाधान

Main article: Polynomial solutions of P-recursive equations

1980 के दशक के उत्तरार्ध में सर्गेई ए. अब्रामोव ने एक एल्गोरिदम का वर्णन किया जो पुनरावृत्ति समीकरण का सामान्य बहुपद समाधान ढूंढता है, अर्थात। ${\textstyle y(n)\in \mathbb {K} [n]}$, एक बहुपद दाहिनी ओर के साथ${\textstyle f(n)\in \mathbb {K} [n]}$. उन्होंने (और कुछ साल बाद मार्को पेटकोवसेक ने) बहुपद समाधानों के लिए एक डिग्री दी। इस प्रकार रैखिक समीकरणों की एक प्रणाली पर विचार करके समस्या को आसानी से हल किया जा सकता है। 1995 में अब्रामोव, ब्रोंस्टीन और पेटकोवसेक ने दिखाया कि एक विशिष्ट शक्ति आधार (यानी सामान्य आधार नहीं) में पुनरावृत्ति समीकरण के औपचारिक शक्ति श्रृंखला समाधान पर विचार करके बहुपद मामले को अधिक कुशलता से हल किया जा सकता है ${\textstyle (x^{n})_{n\in \mathbb {N} }}$).

अधिक सामान्य समाधान खोजने के लिए अन्य एल्गोरिदम (उदाहरण के लिए तर्कसंगत या हाइपरजियोमेट्रिक समाधान) भी एल्गोरिदम पर निर्भर करते हैं जो बहुपद समाधानों की गणना करते हैं।

तर्कसंगत समाधान

Main article: Abramov's algorithm

1989 में सर्गेई ए. अब्रामोव ने दिखाया कि एक सामान्य तर्कसंगत फ़ंक्शन समाधान, यानी। ${\textstyle y(n)\in \mathbb {K} (n)}$, बहुपद दाहिनी ओर के साथ ${\textstyle f(n)\in \mathbb {K} [n]}$, एक सार्वभौमिक हर की धारणा का उपयोग करके पाया जा सकता है। एक सार्वत्रिक हर एक बहुपद है ${\textstyle u}$ इस प्रकार कि प्रत्येक तर्कसंगत समाधान का हर विभाजित हो जाता है ${\textstyle u}$. अब्रामोव ने दिखाया कि कैसे इस सार्वभौमिक हर की गणना केवल पहले और अंतिम गुणांक बहुपद का उपयोग करके की जा सकती है ${\textstyle p_{0}}$ और ${\textstyle p_{r}}$. के अज्ञात हर के स्थान पर इस सार्वभौमिक हर को प्रतिस्थापित करना $y$ परिवर्तित समीकरण के सभी बहुपद समाधानों की गणना करके सभी तर्कसंगत समाधान पाए जा सकते हैं।

अतिज्यामितीय समाधान

Main article: Petkovšek's algorithm

एक क्रम ${\textstyle y(n)}$ यदि दो लगातार पदों का अनुपात एक तर्कसंगत कार्य है तो इसे हाइपरजियोमेट्रिक पहचान कहा जाता है $n$, अर्थात। ${\textstyle y(n+1)/y(n)\in \mathbb {K} (n)}$. यह मामला तभी है जब अनुक्रम बहुपद गुणांक वाले प्रथम-क्रम पुनरावृत्ति समीकरण का समाधान है। हाइपरजियोमेट्रिक अनुक्रमों का सेट अनुक्रमों के स्थान का उप-स्थान नहीं है क्योंकि यह जोड़ के तहत बंद नहीं है।

1992 में मार्को पेटकोवसेक ने पुनरावृत्ति समीकरण का सामान्य हाइपरज्यामितीय समाधान प्राप्त करने के लिए पेटकोवसेक का एल्गोरिदम दिया जहां दाईं ओर $f$ हाइपरज्यामितीय अनुक्रमों का योग है। एल्गोरिथ्म एक तर्कसंगत फ़ंक्शन के गोस्पर-पेटकोवसेक सामान्य-रूप का उपयोग करता है। इस विशिष्ट निरूपण के साथ, परिवर्तित समीकरण के बहुपद समाधानों पर विचार करना फिर से पर्याप्त है।

एक अलग और अधिक कुशल दृष्टिकोण मार्क वैन होइज के कारण है। पहले और अंतिम गुणांक बहुपद की जड़ों पर विचार करना ${\textstyle p_{0}}$ और ${\textstyle p_{r}}$ - जिसे विलक्षणताएं कहा जाता है - कोई भी इस तथ्य का उपयोग करके चरण दर चरण एक समाधान बना सकता है कि प्रत्येक हाइपरज्यामितीय अनुक्रम ${\textstyle y(n)}$ प्रपत्र का एक प्रतिनिधित्व है

$$y(n)=c\,r(n)\,z^{n}\,\Gamma (n-\xi _{1})^{e_{1}}\Gamma (n-\xi _{2})^{e_{2}}\cdots \Gamma (n-\xi _{s})^{e_{s}}$$

कुछ के लिए ${\textstyle c\in \mathbb {K} ,z\in {\overline {\mathbb {K} }},s\in \mathbb {N} ,r(n)\in {\overline {\mathbb {K} }}(n),\xi _{1},\dots ,\xi _{s}\in {\overline {\mathbb {K} }}}$ साथ ${\textstyle \xi _{i}-\xi _{j}\notin \mathbb {Z} }$ के लिए ${\textstyle i\neq j}$ और ${\textstyle e_{1},\dots ,e_{s}\in \mathbb {Z} }$. यहाँ ${\textstyle \Gamma (n)}$ गामा फ़ंक्शन को दर्शाता है और ${\textstyle {\overline {\mathbb {K} }}}$ क्षेत्र का बीजगणितीय समापन ${\textstyle \mathbb {K} }$. फिर ${\textstyle \xi _{1},\dots ,\xi _{s}}$ समीकरण की विलक्षणताएँ होनी चाहिए (अर्थात् मूल ${\textstyle p_{0}}$ या ${\textstyle p_{r}}$). इसके अलावा कोई घातांक के लिए सीमा की गणना कर सकता है ${\textstyle e_{i}}$. निश्चित मानों के लिए ${\textstyle \xi _{1},\dots ,\xi _{s},e_{1},\dots ,e_{s}}$ एक अंसत्ज़ बनाना संभव है जो उम्मीदवारों को देता है ${\textstyle z}$. किसी विशिष्ट के लिए ${\textstyle z}$ परिमेय फलन प्राप्त करने के लिए कोई फिर से ansatz बना सकता है ${\textstyle r(n)}$ अब्रामोव के एल्गोरिदम द्वारा। सभी संभावनाओं पर विचार करने पर पुनरावृत्ति समीकरण का सामान्य समाधान प्राप्त होता है।

डी'एलेम्बर्टियन समाधान

एक क्रम $y$ यदि डी'अलेम्बर्टियन कहा जाता है ${\textstyle y=h_{1}\sum h_{2}\sum \cdots \sum h_{k}}$ कुछ हाइपरजियोमेट्रिक अनुक्रमों के लिए ${\textstyle h_{1},\dots ,h_{k}}$ और ${\textstyle y=\sum x}$ मतलब कि ${\textstyle \Delta y=x}$ कहाँ ${\textstyle \Delta }$ अंतर ऑपरेटर को दर्शाता है, अर्थात ${\textstyle \Delta y=Ny-y=y(n+1)-y(n)}$. यह मामला तभी है जब प्रथम-क्रम रैखिक पुनरावृत्ति ऑपरेटर हों ${\textstyle L_{1},\dots ,L_{k}}$ ऐसे तर्कसंगत गुणांकों के साथ ${\textstyle L_{k}\cdots L_{1}y=0}$.

1994 अब्रामोव और पेटकोवसेक ने एक एल्गोरिदम का वर्णन किया जो पुनरावृत्ति समीकरण के सामान्य डी'अलेम्बर्टियन समाधान की गणना करता है। यह एल्गोरिदम हाइपरजियोमेट्रिक समाधानों की गणना करता है और पुनरावृत्ति समीकरण के क्रम को पुनरावर्ती रूप से कम करता है।

उदाहरण

हस्ताक्षरित क्रमपरिवर्तन मैट्रिक्स

आकार के सामान्यीकृत क्रमपरिवर्तन मैट्रिक्स की संख्या $n\times n$ अनुक्रम स्थान द्वारा वर्णित किया जा सकता है ${\textstyle y(n)\in \mathbb {Q} ^{\mathbb {N} }}$. एक हस्ताक्षरित क्रमपरिवर्तन मैट्रिक्स एक वर्ग मैट्रिक्स है जिसमें प्रत्येक पंक्ति और प्रत्येक कॉलम में बिल्कुल एक गैर-शून्य प्रविष्टि होती है। अशून्य प्रविष्टियाँ हो सकती हैं ${\textstyle \pm 1}$. अनुक्रम बहुपद गुणांक वाले रैखिक पुनरावृत्ति समीकरण द्वारा निर्धारित किया जाता है

$$y(n)=4(n-1)^{2}\,y(n-2)+2\,y(n-1)$$

और प्रारंभिक मूल्य ${\textstyle y(0)=1,y(1)=2}$. हाइपरजियोमेट्रिक समाधान खोजने के लिए एल्गोरिदम लागू करने से कोई सामान्य हाइपरज्यामितीय समाधान पा सकता है

$$y(n)=c\,2^{n}n!$$

कुछ स्थिरांक के लिए ${\textstyle c}$. प्रारंभिक मूल्यों, अनुक्रम पर भी विचार करें ${\textstyle y(n)=2^{n}n!}$ हस्ताक्षरित क्रमपरिवर्तन मैट्रिक्स की संख्या का वर्णन करता है।

इन्वोल्यूशन

इन्वोल्यूशन की संख्या (गणित) ${\textstyle y(n)}$ के साथ एक सेट का ${\textstyle n}$ तत्व पुनरावृत्ति समीकरण द्वारा दिया गया है

$$y(n)=(n-1)\,y(n-2)+y(n-1).$$

उदाहरण के लिए पेटकोवसेक के एल्गोरिदम को लागू करने पर यह देखना संभव है कि इस पुनरावृत्ति समीकरण के लिए कोई बहुपद, तर्कसंगत या हाइपरज्यामितीय समाधान नहीं है।

अनुप्रयोग

एक समारोह ${\textstyle F(n,k)}$ हाइपरजियोमेट्रिक यदि कहा जाता है ${\textstyle F(n,k+1)/F(n,k),F(n+1,k)/F(n,k)\in \mathbb {K} (n,k)}$ कहाँ ${\textstyle \mathbb {K} (n,k)}$ में तर्कसंगत कार्यों को दर्शाता है ${\textstyle n}$ और ${\textstyle k}$. हाइपरज्यामितीय योग रूप का एक सीमित योग है ${\textstyle f(n)=\sum _{k}F(n,k)}$ कहाँ ${\textstyle F(n,k)}$ हाइपरजियोमेट्रिक है. डोरोन ज़िल्बर्गर का रचनात्मक टेलीस्कोपिंग एल्गोरिदम ऐसे हाइपरज्यामितीय योग को बहुपद गुणांक के साथ पुनरावृत्ति समीकरण में बदल सकता है। इस समीकरण को उदाहरण के लिए हाइपरज्यामितीय समाधानों का एक रैखिक संयोजन प्राप्त करने के लिए हल किया जा सकता है जिसे बंद रूप समाधान कहा जाता है ${\textstyle f}$.