पुनरावृत्ति संबंध

गणित में, पुनरावृत्ति संबंध एक समीकरण है जिसके अनुसार संख्याओं के अनुक्रम का $n$ वां पद पिछले पदों के कुछ संयोजन के बराबर है। सामान्यतः केवल $k$ अनुक्रम के पिछले पद समीकरण में दिखाई देते हैं, एक पैरामीटर के लिए $k$ जो कि $n$ से स्वतंत्र है ; इस संख्या $k$ को संबंध का क्रम कहा जाता है। यदि अनुक्रम में पहली $k$ संख्याओं का मान दिया गया है, तो शेष अनुक्रम की गणना बार-बार समीकरण को लागू करके की जा सकती है।

रैखिक पुनरावृत्तियों में, nवें पद $k$ पिछले पदों के एक रैखिक फलन के बराबर होता है। फिबोनैकी संख्याओं की पुनरावृत्ति एक प्रसिद्ध उदाहरण है,

$$F_{n}=F_{n-1}+F_{n-2}$$

जहां क्रम $k$ दो है और रैखिक फलन केवल पिछले दो पदों को जोड़ता है। यह उदाहरण स्थिर गुणांकों के साथ एक रैखिक पुनरावृत्ति है, क्योंकि रैखिक फलन (1 और 1) के गुणांक स्थिरांक हैं जो $n$ पर निर्भर नहीं करते हैं . इन पुनरावृत्तियों के लिए, अनुक्रम के सामान्य शब्द को $n$ एक बंद-रूप अभिव्यक्ति के रूप में व्यक्त किया जा सकता है I साथ ही, $n$ पुनरावर्ती समीकरण पर निर्भर करते हुए बहुपद गुणांकों के साथ रेखीय पुनरावर्तन भी महत्वपूर्ण हैं, क्योंकि कई सामान्य प्राथमिक और विशेष कार्यों में एक टेलर श्रृंखला होती है जिसके गुणांक ऐसे पुनरावृत्ति संबंध को संतुष्ट करते हैं (होलोनोमिक फ़ंक्शन देखें)।

पुनरावृत्ति संबंध को हल करने का अर्थ है $n$ के गैर-पुनरावर्ती कार्य के लिए एक संवृत-रूप समाधान खोजना है।

पुनरावृत्ति संबंध की अवधारणा को बहुआयामी सरणियों तक विस्तारित किया जा सकता है, अर्थात अनुक्रमित परिवार जो प्राकृतिक संख्याओं के टुपल्स द्वारा अनुक्रमित होते हैं।

परिभाषा

पुनरावृत्ति संबंध एक समीकरण है जो अनुक्रम के प्रत्येक तत्व को पिछले वाले के कार्य के रूप में व्यक्त करता है। अधिक सटीक रूप से, उस सम्बन्ध में जहां केवल पूर्ववर्ती तत्व सम्मिलित होता है, पुनरावृत्ति संबंध का रूप होता है

$u_{n}=\varphi (n,u_{n-1})\quad {\text{for}}\quad n>0,$

जहाँ

$\varphi :\mathbb {N} \times X\to X$

एक फलहाँ X एक समुच्च,के लिए यह इसके पहले तत्व के रूप में

एक फलन है, जहाँ X एक समुच्चय है जिससे अनुक्रम के अवयव संबंधित होने चाहिए। किसी भी $u_{0}\in X$ के लिए $u_{0}\in X$ यह इसके पहले तत्व के रूप में $u_{0}$के साथ एक अद्वितीय अनुक्रम को परिभाषित करता है, जिसे प्रारंभिक मूल्य।

अनुक्रमणिका 1 या उच्चतर की अवधि से अनुक्रम प्राप्त करने के लिए परिभाषा को संशोधित करना आसान है।

यह प्रथम कोटि के पुनरावर्तन संबंध को परिभाषित करता है। क्रम k के पुनरावृत्ति संबंध का रूप है

$u_{n}=\varphi (n,u_{n-1},u_{n-2},\ldots ,u_{n-k})\quad {\text{for}}\quad n\geq k,$

जहाँ $\varphi :\mathbb {N} \times X^{k}\to X$ एक ऐसा फंक्शन है जिसमें k अनुक्रम के लगातार तत्व सम्मिलित है । इस स्थिति में, किसी क्रम को परिभाषित करने के लिए k प्रारंभिक मानों की आवश्यकता होती है।

उदाहरण

क्रमगुणित

क्रमगुणित को पुनरावृत्ति संबंध द्वारा परिभाषित किया गया है

$n!=n(n-1)!\quad {\text{for}}\quad n>0,$

और प्रारंभिक स्थिति

$0!=1.$

यह सरल बहुपद के साथ क्रम 1 के बहुपद गुणांकों के साथ रैखिक पुनरावृत्ति का एक उदाहरण है

$f(n)=n$

इसके एकमात्र गुणांक के रूप में।

लॉजिस्टिक मानचित्र

पुनरावृत्ति संबंध का एक उदाहरण तार्किक मानचित्र है:

$x_{n+1}=rx_{n}(1-x_{n}),$

दिए गए स्थिरांक के साथ $r$; दिया गया आरंभिक पद $x_{0}$ प्रत्येक अनुवर्ती पद इस संबंध द्वारा निर्धारित होता है।

फाइबोनैचि संख्या

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

$F_{n}=F_{n-1}+F_{n-2}$

प्रारंभिक शर्तों के साथ

$F_{0}=0$

$F_{1}=1.$

स्पष्ट रूप से, पुनरावृत्ति से समीकरण प्राप्त होते हैं

$F_{2}=F_{1}+F_{0}$

$F_{3}=F_{2}+F_{1}$

$F_{4}=F_{3}+F_{2}$

आदि।

हम फाइबोनैचि संख्याओं का क्रम प्राप्त करते हैं, जो शुरू होता है

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

पुनरावर्तन को नीचे वर्णित उपायों से समाधान किया जा सकता है, जो बिनेट के सूत्र को दर्शाता है, जिसमें विशेषता बहुपद की दो जड़ों की शक्तियां सम्मलित होती हैं। $t^{2}=t+1$; अनुक्रम का उत्पादक फ़ंक्शन तर्कसंगत फ़ंक्शन है

${\frac {t}{1-t-t^{2}}}.$

द्विपद गुणांक

बहुआयामी पुनरावृत्ति संबंध का एक सरल उदाहरण द्विपद गुणांक ${\tbinom {n}{k}}$, द्वारा दिया गया है, जो $k$ को चुनने के उपायों की गणना करते हैं। k तत्व $n$ तत्वों के एक समुच्च से बाहर है। इनकी गणना पुनरावृत्ति संबंध द्वारा की जा सकती है

${\binom {n}{k}}={\binom {n-1}{k-1}}+{\binom {n-1}{k}},$

आधार स्थिति के साथ ${\tbinom {n}{0}}={\tbinom {n}{n}}=1$. सभी द्विपद गुणांकों के मूल्यों की गणना करने के लिए इस सूत्र का उपयोग करने से पास्कल का त्रिकोण नामक एक अनंत सरणी उत्पन्न होती है। समान मूल्यों की सीधे एक भिन्न सूत्र द्वारा गणना की जा सकती है जो पुनरावृत्ति नहीं है, लेकिन तथ्यात्मक, गुणन और विभाजन का उपयोग करता है, न कि केवल जोड़:

${\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.$

द्विपद गुणांकों की गणना एक आयामी पुनरावृत्ति के साथ भी की जा सकती है:

${\binom {n}{k}}={\binom {n}{k-1}}(n-k+1)/k,$

प्रारंभिक मूल्य के साथ ${\textstyle {\binom {n}{0}}=1}$ (विभाजन को एक अंश के रूप में प्रदर्शित नहीं किया जाता है, यह बल देने के लिए कि इसे गुणा के बाद गणना की जानी चाहिए, भिन्नात्मक संख्याओं को दर्शाने के लिए नहीं)।यह पुनरावृत्ति कंप्यूटर में व्यापक रूप से उपयोग की जाती है क्योंकि इसमें तालिका बनाने की आवश्यकता नहीं होती है जैसा कि द्वि-आयामी पुनरावृत्ति करता है, और इसमें बहुत बड़े पूर्णांक सम्मिलित होते हैं जैसा कि क्रमगुणित के साथ सूत्र (यदि कोई उपयोग करता है) ${\textstyle {\binom {n}{k}}={\binom {n}{n-k}},}$ सभी सम्मिलित पूर्णांक अंतिम परिणाम से छोटे हैं)।

अवकल ऑपरेटर और अवकल समीकरण

अवकल ऑपरेटर एक ऑपरेटर (गणित) है जो अनुक्रमों को मैप करता है, और, अधिक सामान्यतः, फ़ंक्शन (गणित) को कार्यों के लिए। यह सामान्यतः $\Delta ,$ डेल्टा से निरूपित किया जाता है और कार्यात्मक संकेतन में परिभाषित किया जाता है, जैसा कि

$(\Delta f)(x)=f(x+1)-f(x).$

इस प्रकार यह परिमित अवकल का एक विशेष विषय है।

अनुक्रमों के लिए सूचकांक संकेतन का उपयोग करते समय, परिभाषा बन जाती है

$(\Delta a)_{n}=a_{n+1}-a_{n}.$

$\Delta f$ तथा $\Delta a$ के आसपास कोष्ठक सामान्यतः छोड़े जाते हैं, और $\Delta a_{n}$अनुक्रम में अनुक्रमणिका n के शब्द के रूप में समझा जाना चाहिए न कि $\Delta$ तत्व पर लागू $a_{n}.$ दिया गया क्रम $a=(a_{n})_{n\in \mathbb {N} },$ a का पहला अवकल है $\Delta a.$

दूसरा अवकल है $\Delta ^{2}a=(\Delta \circ \Delta )a=\Delta (\Delta a).$ एक साधारण गणना यह दर्शाती है

$\Delta ^{2}a_{n}=a_{n+2}-2a_{n+1}+a_{n}.$

अधिक सामान्यतः k अवकल को पुनरावर्ती रूप से परिभाषित किया जाता है $\Delta ^{k}=\Delta \circ \Delta ^{k-1},$ और एक के पास है

$\Delta ^{k}a_{n}=\sum _{t=0}^{k}(-1)^{t}{\binom {k}{t}}a_{n+k-t}.$

यह रिश्ता उलटा हो सकता है, दे रहा है

$a_{n+k}=a_{n}+{k \choose 1}\Delta a_{n}+\cdots +{k \choose k}\Delta ^{k}(a_{n}).$

कोटि k का अवकल एक ऐसा समीकरण है जिसमें किसी अनुक्रम या फलन k के पहले अवकल सम्मलित होते हैं, ठीक उसी तरह जैसे k क्रम का अवकल समीकरण किसी फलन के k पहले अवकलजों को संबंधित करता है।

उपरोक्त दो संबंध क्रम k के पुनरावृत्ति संबंध को बदलने की अनुमति देते हैं और इसके विपरीत, क्रम k के अवकल समीकरण को क्रम के अवकल समीकरण में ,k के पुनरावृत्ति संबंध में बदलने की अनुमति देते हैं। प्रत्येक परिवर्तन दूसरे का व्युत्क्रम है, और अनुक्रम जो अवकल समीकरण के समाधान हैं, ठीक वही हैं जो पुनरावृत्ति संबंध को संतुष्ट करते हैं।

उदाहरण के लिए, अवकल समीकरण

$3\Delta ^{2}a_{n}+2\Delta a_{n}+7a_{n}=0$

पुनरावृत्ति संबंध के बराबर है

$3a_{n+2}=4a_{n+1}-8a_{n},$

इस अर्थ में कि दो समीकरण एक ही क्रम से संतुष्ट होते हैं।

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

अवकल समीकरण समान होते हैं, और इस समानता का उपयोग अधिकांशतः अवकल समीकरणों को समाधान करने के लिए भिन्न -भिन्न समीकरणों को समाधान करने के उपायों की नकल करने के लिए किया जाता है,और इसलिए पुनरावृत्ति संबंध।

योग समीकरण अवकल समीकरणों से संबंधित होते हैं क्योंकि अभिन्न समीकरण अवकल समीकरणों से संबंधित होते हैं। अवकल समीकरणों के सिद्धांत के साथ अवकल समीकरणों के एकीकरण के लिए समय पैमाने की गणना देखें।

अनुक्रम से ग्रिड तक

एकल-चर या एक-आयामी पुनरावृत्ति संबंध अनुक्रमों के बारे में हैं (अर्थात एक-आयामी ग्रिड पर परिभाषित कार्य)। बहु-चर या $n$-आयामी पुनरावृत्ति संबंध $n$-आयामी ग्रिड के बारे में हैं। आंशिक अवकल समीकरणों के साथ $n$-ग्रिड्स पर परिभाषित कार्यों का भी अध्ययन किया जा सकता है।

सुलझाना

निरंतर गुणांकों के साथ रैखिक पुनरावृत्ति संबंधों को समाधान करना

Main article: निरंतर गुणांक के साथ रैखिक पुनरावृत्ति

चर गुणांकों के साथ प्रथम-क्रम गैर-सजातीय पुनरावृत्ति संबंधों को समाधान करना

इसके अतिरिक्त, चर गुणांक के साथ सामान्य प्रथम-क्रम गैर-सजातीय रैखिक पुनरावृत्ति संबंध के लिए:

$a_{n+1}=f_{n}a_{n}+g_{n},\qquad f_{n}\neq 0,$

इसे समाधान करने का एक अच्छा उपाय भी है:

$a_{n+1}-f_{n}a_{n}=g_{n}$

${\frac {a_{n+1}}{\prod _{k=0}^{n}f_{k}}}-{\frac {f_{n}a_{n}}{\prod _{k=0}^{n}f_{k}}}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}$

${\frac {a_{n+1}}{\prod _{k=0}^{n}f_{k}}}-{\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}$

होने देना

$A_{n}={\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}},$

फिर

$A_{n+1}-A_{n}={\frac {g_{n}}{\prod _{k=0}^{n}f_{k}}}$

$\sum _{m=0}^{n-1}(A_{m+1}-A_{m})=A_{n}-A_{0}=\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}$

${\frac {a_{n}}{\prod _{k=0}^{n-1}f_{k}}}=A_{0}+\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}$

$a_{n}=\left(\prod _{k=0}^{n-1}f_{k}\right)\left(A_{0}+\sum _{m=0}^{n-1}{\frac {g_{m}}{\prod _{k=0}^{m}f_{k}}}\right)$

यदि हम सूत्र को $a_{n+1}=(1+hf_{nh})a_{n}+hg_{nh}$ पर लागू करते हैं और $h\to 0$ की सीमा लें, हमें चर गुणांक वाले रैखिक अवकल समीकरणों के पहले क्रम का सूत्र मिलता है; योग एक अभिन्न बन जाता है, और उत्पाद एक अभिन्न अंग का घातीय कार्य बन जाता है।

सामान्य सजातीय रैखिक पुनरावृत्ति संबंधों को समाधान करना

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

$J_{n+1}={\frac {2n}{z}}J_{n}-J_{n-1}$

द्वारा दिया गया है

$J_{n}=J_{n}(z),$

बेसेल फंक्शन, जबकि

$(b-n)M_{n-1}+(2n-b-z)M_{n}-nM_{n+1}=0$

द्वारा समाधान किया जाता है

$M_{n}=M(n,b;z)$

संगम अतिज्यामितीय श्रृंखला। अनुक्रम जो बहुपद गुणांक वाले रैखिक अवकल समीकरणों के समाधान हैं, P-पुनरावर्ती कहलाते हैं।समीकरण के समाधान हैं इन विशिष्ट पुनरावृत्ति समीकरणों के लिए कलन विधि

ज्ञात हैं जो बहुपद, परिमेय या अतिज्यामितीय समाधान खोजते हैं।

प्रथम-क्रम तर्कसंगत अवकल समीकरणों को समाधान करना

Main article: तर्कसंगत अंतर समीकरण

पहले क्रम के तर्कसंगत अवकल समीकरण का रूप $w_{t+1}={\tfrac {aw_{t}+b}{cw_{t}+d}}$ होता है . इस प्रकार के एक समीकरण को $w_{t}$को एक अन्य चर $x_{t}$ के गैर-रैखिक परिवर्तन के रूप में लिखकर समाधान किया जा सकता है जो स्वयं रैखिक रूप से विकसित होता है। फिर $x_{t}$ में रैखिक अवकल समीकरण को समाधान करने के लिए मानक विधियों का उपयोग किया जा सकता है।

स्थिरता

रैखिक उच्च-क्रम पुनरावृत्तियों की स्थिरता

आदेश की रैखिक पुनरावृत्ति $d$,

$a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots +c_{d}a_{n-d},$

विशेषता बहुपद है

$\lambda ^{d}-c_{1}\lambda ^{d-1}-c_{2}\lambda ^{d-2}-\cdots -c_{d}\lambda ^{0}=0.$

पुनरावृत्ति स्थिरता सिद्धांत है, जिसका अर्थ है कि पुनरावृत्त एक निश्चित मूल्य के लिए असम्बद्ध रूप से अभिसरण करते हैं,और केवल आइगेनवैल्यूज़ ​​​​( विशेषता समीकरण की जड़ें), चाहे वास्तविक या जटिल, पूर्ण मूल्य में एकता (गणित) से कम हैं I

रैखिक प्रथम-क्रम मैट्रिक्स पुनरावृत्तियों की स्थिरता

Main article: मैट्रिक्स अंतर समीकरण

पहले क्रम के मैट्रिक्स अवकल समीकरण में

$[x_{t}-x^{*}]=A[x_{t-1}-x^{*}]$

स्टेट वेक्टर के साथ $x$ और संक्रमण मैट्रिक्स $A$, $x$ असम्बद्ध रूप से स्थिर अवस्था वेक्टर $x^{*}$ में परिवर्तित हो जाता है यदि केवल यदि संक्रमण मैट्रिक्स $A$ के सभी आइजन मूल्य(चाहे वास्तविक हो या जटिल) का एक निरपेक्ष मान होता है जो 1 से कम होता है।

अरेखीय प्रथम-क्रम पुनरावृत्तियों की स्थिरता

अरेखीय प्रथम-क्रम पुनरावृत्ति पर विचार करें

$x_{n}=f(x_{n-1}).$

यह पुनरावृत्ति स्थिरता सिद्धांत है, जिसका अर्थ है कि यह अनुक्रम को एक निश्चित बिंदु $x^{*}$ से पर्याप्त रूप से $x^{*}$ के निकट बिंदुओं से अभिसरण करता है, यदि $x^{*}$ के पड़ोस में $f$ का स्लोप निरपेक्ष मान में एकता से छोटा है: अर्थात

$|f'(x^{*})|<1.$

एक अरेखीय पुनरावृत्ति में कई निश्चित बिंदु हो सकते हैं, इस स्थिति में कुछ निश्चित बिंदु स्थानीय रूप से स्थिर हो सकते हैं और अन्य स्थानीय रूप से अस्थिर हो सकते हैं; निरंतर च के लिए दो आसन्न निश्चित बिंदु दोनों स्थानीय रूप से स्थिर नहीं हो सकते।

एक अरैखिक पुनरावृत्ति संबंध में $k>1$ के लिए $k$ अवधि का एक चक्र भी हो सकता है। ऐसा चक्र स्थिर होता है, जिसका अर्थ है कि यह सकारात्मक माप की प्रारंभिक स्थितियों के एक समुच्चय को आकर्षित करता है, यदि समग्र कार्य

$g(x):=f\circ f\circ \cdots \circ f(x)$

$f$ $k$ बार प्रदर्शित होने के साथ समान मानदंड के अनुसार स्थानीय रूप से स्थिर है:

$|g'(x^{*})|<1,$

जहां $x^{*}$ चक्र पर कोई बिंदु है।

अराजकता सिद्धांत में पुनरावृत्ति संबंध, चर $x$ एक बंधे हुए क्षेत्र में रहता है लेकिन कभी भी एक निश्चित बिंदु या एक आकर्षक चक्र में परिवर्तित नहीं होता है; समीकरण के कोई निश्चित बिंदु या चक्र अस्थिर हैं। लॉजिस्टिक मैप, युग्मक परिवर्तन और तम्बू का चित्र भी देखें।

अवकल समीकरणों से संबंध

एक साधारण अवकल समीकरण संख्यात्मक साधारण अवकल समीकरण को समाधान करते समय, एक विशिष्ट रूप से एक पुनरावृत्ति संबंध का सामना करना पड़ता है। उदाहरण के लिए, प्रारंभिक मूल्य समस्या को समाधान करते समय

$y'(t)=f(t,y(t)),\ \ y(t_{0})=y_{0},$

यूलर की विधि और एक कदम आकार के साथ $h$, मूल्यों की गणना करता है

$y_{0}=y(t_{0}),\ \ y_{1}=y(t_{0}+h),\ \ y_{2}=y(t_{0}+2h),\ \dots$

पुनरावृत्ति द्वारा

$\,y_{n+1}=y_{n}+hf(t_{n},y_{n}),t_{n}=t_{0}+nh$

रेखीय प्रथम क्रम के अवकल समीकरणों के प्रणाली को विवेचनात्मक लेख में दिखाए गए उपायों का उपयोग करके स्पष्ट रूप से विश्लेषणात्मक रूप से विखंडित किया जा सकता है।

अनुप्रयोग

गणितीय जीव विज्ञान

जनसंख्या की गतिशीलता को मॉडल करने के प्रयास में कुछ सबसे प्रसिद्ध अवकल समीकरणों की उत्पत्ति हुई है। उदाहरण के लिए, फाइबोनैचि संख्याओं को एक बार खरगोशों की आबादी के विकास के लिए एक मॉडल के रूप में प्रयोग किया गया था।

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

$N_{t+1}=\lambda N_{t}e^{-aP_{t}}$

$P_{t+1}=N_{t}(1-e^{-aP_{t}}),$

$N_{t}$ मेजबान का प्रतिनिधित्व करते हुए, और $P_{t}$ समय पर $t$

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

कंप्यूटर विज्ञान

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

सबसे खराब स्थिति में $n$ तत्वों वाले गण किए गए सदिश में किसी तत्व को खोजने में लगने वाला समय एक सरल उदाहरण है।

एक भोली कलन विधि एक समय में एक तत्व को बाएं से दाएं खोजेगा। सबसे खराब संभावित परिदृश्य तब होता है जब आवश्यक तत्व अंतिम होता है, इसलिए तुलना की संख्या $n$ होती है I

एक अच्छा कलन विधि को बाइनरी खोज कलन विधि कहा जाता है। चूँकि, इसके लिए एक क्रमबद्ध वेक्टर की आवश्यकता होती है। यह पहले जांच करेगा कि तत्व वेक्टर के बीच में है या नहीं। यदि नहीं, तो यह जाँच करेगा कि मध्य तत्व वांछित तत्व से अधिक या कम है या नहीं। इस बिंदु पर, आधे वेक्टर को छोड़ दिया जा सकता है, और कलन विधि को दूसरे आधे हिस्से पर फिर से चलाया जा सकता है। तुलना की संख्या द्वारा दिया जाएगा

$c_{1}=1$

$c_{n}=1+c_{n/2}$

जिसकी समय जटिलता होगी $O(\log _{2}(n))$.

अंकीय संकेत प्रक्रिया

डिजिटल संकेत प्रसंस्करण में, पुनरावृत्ति संबंध एक प्रणाली में प्रतिक्रिया को मॉडल कर सकते हैं, जहां एक समय में आउटपुट भविष्य के समय के लिए इनपुट बन जाते हैं। वे इस प्रकार अनंत आवेग प्रतिक्रिया (आईआईआर) डिजिटल फिल्टर में उत्पन्न होते हैं।

उदाहरण के लिए, विलंब $T$ के आगे आईआईआर कंघी फिल्टर के लिए समीकरण है:

$y_{t}=(1-\alpha )x_{t}+\alpha y_{t-T},$

जहां $x_{t}$ समय पर इनपुट है $t$, $y_{t}$ समय पर आउटपुट है $t$, तथा $\alpha$ यह नियंत्रित करता है कि कितने विलंबित संकेत को आउटपुट में वापस फीड किया जाता है। इससे हम यह देख सकते हैं

$y_{t}=(1-\alpha )x_{t}+\alpha ((1-\alpha )x_{t-T}+\alpha y_{t-2T})$

$y_{t}=(1-\alpha )x_{t}+(\alpha -\alpha ^{2})x_{t-T}+\alpha ^{2}y_{t-2T}$

आदि।

अर्थशास्त्र

See also: समय श्रृंखला विश्लेषण and एक साथ समीकरण मॉडल

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

यह भी देखें

• होलोनोमिक फ़ंक्शन
• पुनरावृत्त समारोह
• ओर्थोगोनल बहुपद
• प्रत्यावर्तन
• रिकर्सन (कंप्यूटर विज्ञान)
• लैग्ड फाइबोनैचि जनरेटर
• मास्टर प्रमेय (एल्गोरिदम का विश्लेषण)
• सर्कल पॉइंट्स सेगमेंट प्रूफ
• निरंतर अंश
• टाइम स्केल कैलकुलस
• संयुक्त सिद्धांत
• अनंत आवेग प्रतिक्रिया
• कमी सूत्रों द्वारा एकीकरण
• गणितीय अधिष्ठापन

संदर्भ

ग्रन्थसूची

• Batchelder, Paul M. (1967). An introduction to linear difference equations. Dover Publications.
• Miller, Kenneth S. (1968). Linear difference equations. W. A. Benjamin.
• Fillmore, Jay P.; Marx, Morris L. (1968). "Linear recursive sequences". SIAM Rev. Vol. 10, no. 3. pp. 324–353. JSTOR 2027658.
• Brousseau, Alfred (1971). Linear Recursion and Fibonacci Sequences. Fibonacci Association.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 1990. ISBN 0-262-03293-7. Chapter 4: Recurrences, pp. 62–90.
• Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics: A Foundation for Computer Science (2 ed.). Addison-Wesley. ISBN 0-201-55802-5.
• Enders, Walter (2010). Applied Econometric Times Series (3 ed.). Archived from the original on 2014-11-10.
• Cull, Paul; Flahive, Mary; Robson, Robbie (2005). Difference Equations: From Rabbits to Chaos. Springer. ISBN 0-387-23234-6. chapter 7.
• Jacques, Ian (2006). Mathematics for Economics and Business (Fifth ed.). Prentice Hall. pp. 551–568. ISBN 0-273-70195-9. Chapter 9.1: Difference Equations.
• Minh, Tang; Van To, Tan (2006). "Using generating functions to solve linear inhomogeneous recurrence equations" (PDF). Proc. Int. Conf. Simulation, Modelling and Optimization, SMO'06. pp. 399–404. Archived from the original (PDF) on 2016-03-04. Retrieved 2014-08-07.
• Polyanin, Andrei D. "Difference and Functional Equations: Exact Solutions". at EqWorld - The World of Mathematical Equations.
• Polyanin, Andrei D. "Difference and Functional Equations: Methods". at EqWorld - The World of Mathematical Equations.
• Wang, Xiang-Sheng; Wong, Roderick (2012). "Asymptotics of orthogonal polynomials via recurrence relations". Anal. Appl. 10 (2): 215–235. arXiv:1101.4371. doi:10.1142/S0219530512500108. S2CID 28828175.

बाहरी संबंध

• "Recurrence relation", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Weisstein, Eric W. "Recurrence Equation". MathWorld.
• "OEIS Index Rec". OEIS index to a few thousand examples of linear recurrences, sorted by order (number of terms) and signature (vector of values of the constant coefficients)