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

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

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

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

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

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

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

परिभाषा

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

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

कहाँ पे

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

एक समारोह है, जहां 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$ तत्वों के एक सेट से बाहर $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}},}$ सभी शामिल पूर्णांक अंतिम परिणाम से छोटे हैं)।

अंतर ऑपरेटर और अंतर समीकरण

difference operatorएक ऑपरेटर (गणित) है जो अनुक्रमों के अनुक्रमों को मैप करता है, और, अधिक सामान्यतः, फ़ंक्शन (गणित) को कार्यों के लिए। यह आमतौर पर निरूपित किया जाता है $\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,$ और नहीं $\Delta$ तत्व पर लागू होता है $a_{n}.$ दिया गया क्रम $a=(a_{n})_{n\in \mathbb {N} },$ first differenceका a है $\Delta a.$ second differenceहै

$\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}).$

एdifference equationआदेश की k एक समीकरण है जिसमें शामिल है 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},$

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

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

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

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

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

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

सुलझाना

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

Main article: Linear recurrence with constant coefficients

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

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

$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)$

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

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

Main article: Rational difference equation

पहले क्रम के तर्कसंगत अंतर समीकरण का रूप है $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.$

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

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

Main article: Matrix difference equation

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

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

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

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

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

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

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

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

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

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

$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$.

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

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

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

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

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

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

$c_{1}=1$

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

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

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

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

उदाहरण के लिए, देरी के फीडफॉरवर्ड IIR कंघी फिल्टर के लिए समीकरण $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: time series analysis and simultaneous equations model

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

यह भी देखें

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

संदर्भ

ग्रन्थसूची

• 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)