Кіріспе
Сандар тізбесін шексіз анықтайтын үлгі. Математикада қайталану қатынасы – сандар тізбегінің n-ші мүшесі алдыңғы мүшелердің белгілі бір комбинациясына тең болатын теңдеу. Көбінесе, теңдеуде тек тізбектің k мүшесі пайда болады, мұнда k – тізбекке тәуелсіз параметр, ал бұл сан қатынастың реті деп аталады. Егер тізбектегі алғашқы k сандардың мәндері берілген болса, тізбектің қалған бөліктерін теңдеуді қайталап қолдану арқылы есептеуге болады. Сызықтық қайталануларда n-ші мүше алдыңғы k мүшелердің сызықтық функциясына теңестіріледі. Белгілі мысал – Фибоначчи сандарының қайталануы, онда реті екіге тең және сызықтық функция тек алдыңғы екі мүшені қосады. Бұл мысал тұрақты коэффициенттері бар сызықтық қайталану, себебі сызықтық функцияның коэффициенттері (1 және 1) – n-ге тәуелді емес тұрақтылар. Мұндай қайталанулар үшін тізбектің жалпы мүшесін жабық түрдегі өрнек түрінде беруге болады. Сонымен қатар, полиномиялық коэффициенттері бар сызықтық қайталанулар да маңызды, өйткені көптеген таралған элементарлық және арнайы функциялардың Тейлор қатарының коэффициенттері осындай қайталану қатынасын қанағаттандырады (холономиялық функцияны қараңыз). Қайталану қатынасын шешу – жабық формадағы шешімді табу, яғни рекурсивті емес функцияны алу. Қайталану қатынасының түсінігін көп өлшемді массивтерге, яғни табиғи сандардың топтамаларымен индекстелген индекстелген отбасыларға кеңейтуге болады.
In mathematics, a recurrence relation is an equation according to which the th term of a sequence of numbers is equal to some combination of the previous terms. Often, only previous terms of the sequence appear in the equation, for a parameter that is independent of ; this number is called the order of the relation. If the values of the first numbers in the sequence have been given, the rest of the sequence can be calculated by repeatedly applying the equation. In linear recurrences, the nth term is equated to a linear function of the previous terms. A famous example is the recurrence for the Fibonacci numbers,
where the order is two and the linear function merely adds the two previous terms. This example is a linear recurrence with constant coefficients, because the coefficients of the linear function (1 and 1) are constants that do not depend on For these recurrences, one can express the general term of the sequence as a closed form expression of As well, linear recurrences with polynomial coefficients depending on are also important, because many common elementary and special functions have a Taylor series whose coefficients satisfy such a recurrence relation (see holonomic function). Solving a recurrence relation means obtaining a closed form solution: a non recursive function of
The concept of a recurrence relation can be extended to multidimensional arrays, that is, indexed families that are indexed by tuples of natural numbers.
Тізбеден торға дейін
Бір айнымалы немесе бір өлшемді рекурренттік қатынастар тізбектер (яғни бір өлшемді торларда анықталған функциялар) туралы. Көп айнымалы немесе n өлшемді рекурренттік қатынастар n өлшемді торлар туралы. Торларда анықталған функцияларды дербес айырмашылық теңдеулерімен де зерттеуге болады.
Бірінші реттік рационалдық айырмалылық теңдеулерін шешу
Бірінші реттік рационалды айырма теңдеуі мына түрде келеді: Мұндай теңдеуді жаңа айнымалының сызықтық емес түрленуі ретінде жазу арқылы шешуге болады, ал бұл жаңа айнымалы сызықты түрде өзгереді. Содан кейін, жаңа айнымалыдағы сызықтық айырма теңдеуін шешу үшін стандартты әдістер қолданылуы мүмкін.
Математикалық биология
Ең танымал айырмашылық теңдеулердің кейбірінің пайда болуы популяциялық динамиканы модельдеу әрекеттерінен басталады. Мысалы, Фибоначчи сандары бір кезде қоян популяциясының өсуін модельдеу үшін қолданылған. Логистикалық карта халық санының өсуін тікелей модельдеуге немесе халық динамикасының толыққанды модельдеріне бастапқы нүкте ретінде қолданылады. Осы ретте, біріктірілген айырмашылық теңдеулері екі немесе одан көп популяциялардың өзара әрекеттесуін модельдеу үшін жиі пайдаланылады. Мысалы, Nicholson–Bailey моделінде ие және паразит арасындағы қарым-қатынас иелерді және паразитті арқылы көрсетіледі, мұндағы – уақыт. Интегродіфференциалдық теңдеулер кеңістіктік экология үшін маңызды рекурренттік қатынастардың бір түрі болып табылады. Бұл және басқа да айырмашылық теңдеулер бір рет көбейетін популяцияларды модельдеуге ерекше қолайлы.
with representing the hosts, and the parasites, at time
Integrodifference equations are a form of recurrence relation important to spatial ecology. These and other difference equations are particularly suited to modeling univoltine populations.
Компьютерлік ғылым
Қайталану қатынастары алгоритмдерді талдауда да маңызды рөл атқарады. Егер алгоритм мәселені кішігірім кіші-мәселелерге бөлуге (бөліп-бас иелену) құрылған болса, оның орындалу уақыты қайталану қатынасымен сипатталады. Мысалы, реттелген вектордағы элементті табуға алгоритмнің ең жаман жағдайда кеткен уақытын қарастырайық. Наive алгоритм солдан оңға қарай бір элементтен бірін іздейді. Ең нашар жағдай – қажетті элемент соңғы болып шыққанда, онда салыстырулар саны болады.
A better algorithm is called binary search. However, it requires a sorted vector. It will first check if the element is at the middle of the vector. If not, then it will check if the middle element is greater or lesser than the sought element. At this point, half of the vector can be discarded, and the algorithm can be run again on the other half. The number of comparisons will be given by
the time complexity of which will be .
Кейіннен жасалған жақсырақ алгоритм – бинарлық іздеу. Бірақ, ол сұрыпталған векторды талап етеді. Алдымен, алгоритм элементтің вектордың ортасында екенін тексереді. Егер ортада болмаса, ортаңғы элемент ізделіп жатқан элементтен үлкен немесе кіші екенін тексереді. Осы кезде вектордың жартысын жойып, алгоритмді қалған жартысында қайта іске қосуға болады. Салыстырулар саны келесі формуламен беріледі:
A better algorithm is called binary search. However, it requires a sorted vector. It will first check if the element is at the middle of the vector. If not, then it will check if the middle element is greater or lesser than the sought element. At this point, half of the vector can be discarded, and the algorithm can be run again on the other half. The number of comparisons will be given by
the time complexity of which will be .
Оның уақыт күрделілігі болады.
A better algorithm is called binary search. However, it requires a sorted vector. It will first check if the element is at the middle of the vector. If not, then it will check if the middle element is greater or lesser than the sought element. At this point, half of the vector can be discarded, and the algorithm can be run again on the other half. The number of comparisons will be given by
the time complexity of which will be .
Экономика
Қайталану қатынастары, әсіресе сызықтық қайталану қатынастары, теориялық және эмпирикалық экономикада кеңінен қолданылады. Атап айтқанда, макроэкономикада экономиканың әртүрлі кең секторларының (қаржы секторы, тауар секторы, еңбек нарығы сияқты) үлгісі жасалуы мүмкін, онда кейбір агенттердің іс-әрекеттері кешіктірілген айнымалыларға байланысты болады. Содан кейін модель негізгі айнымалылардың (пайыздық ставка, нақты ЖІӨ және т.б.) ағымдағы мәндері басқа айнымалылардың өткен және ағымдағы мәндері арқылы есептеліп шығарылады.