Отношение рецидива

В математике , А рекуррентное соотношение является уравнением , что рекурсивно определяет последовательность или многомерный массив значений после того , как один или более начальные условия; каждый последующий член последовательности или массива определяется как функция предыдущих терминов.

Термин « разностное уравнение» иногда (и для целей данной статьи) относится к определенному типу рекуррентного отношения. Однако «разностное уравнение» часто используется для обозначения любого рекуррентного отношения.

Определение [ править ]

Рекуррентное соотношение является уравнением , которое выражает каждый элемент последовательности в зависимости от предыдущих. Точнее, в случае, когда задействован только непосредственно предшествующий элемент, рекуррентное отношение имеет вид

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

куда

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

- функция, где X - множество, которому должны принадлежать элементы последовательности. Для любого , это определяет уникальную последовательность с ее первым элементом, называемым начальным значением . ^[1]${\ displaystyle u_ {0} \ in X}$${\ displaystyle u_ {0}}$

Легко изменить определение для получения последовательностей, начиная с члена индекса 1 или выше.

Это определяет рекуррентное отношение первого порядка . Рекуррентное отношение порядка k имеет вид

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

где - функция, включающая k последовательных элементов последовательности. В этом случае для определения последовательности необходимы k начальных значений.${\ displaystyle \ varphi: \ mathbb {N} \ times X ^ {k} \ to X}$

Примеры [ править ]

Факториал [ править ]

Факториала определяется рекуррентным соотношением

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

и начальное условие

${\displaystyle 0!=1.}$

Логистическая карта [ править ]

Примером рекуррентного отношения является логистическая карта :

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

с заданной постоянной r ; при начальном члене x ₀ каждый последующий член определяется этим соотношением.

Решение рекуррентного отношения означает получение решения в замкнутой форме : нерекурсивной функции от n .

Числа Фибоначчи [ править ]

Повторяемость второго порядка, которой удовлетворяют числа Фибоначчи, является архетипом однородного линейного рекуррентного отношения с постоянными коэффициентами (см. Ниже). Последовательность Фибоначчи определяется с использованием повторения

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

с начальными условиями (начальные значения)

${\displaystyle F_{0}=0}$

${\displaystyle F_{1}=1.}$

В явном виде рекуррентность приводит к уравнениям

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

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

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

и Т. Д.

Получаем последовательность чисел Фибоначчи, которая начинается

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

Повторяемость может быть решена описанными ниже методами, в результате чего получается формула Бине , которая включает степени двух корней характеристического многочлена t ²  =  t  + 1; производящая функция последовательности является рациональной функцией

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

Биномиальные коэффициенты [ править ]

Простым примером многомерного рекуррентного отношения являются биномиальные коэффициенты , которые подсчитывают количество способов выбора k элементов из набора из n элементов. Их можно вычислить с помощью рекуррентного соотношения${\displaystyle {\tbinom {n}{k}}}$

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

с базовыми случаями . Использование этой формулы для вычисления значений всех биномиальных коэффициентов создает бесконечный массив, называемый треугольником Паскаля . Те же значения также можно вычислить напрямую по другой формуле, которая не является повторением, но требует умножения, а не просто сложения для вычисления:${\displaystyle {\tbinom {n}{0}}={\tbinom {n}{n}}=1}$${\displaystyle {\binom {n}{k}}={\frac {n!}{k!(n-k)!}}.}$

Связь с разностными уравнениями в узком смысле [ править ]

Учитывая упорядоченную последовательность из действительных чисел : первое различие определяются как${\displaystyle \left\{a_{n}\right\}_{n=1}^{\infty }}$ ${\displaystyle \Delta (a_{n})}$

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

Второе различие определяется как${\displaystyle \Delta ^{2}(a_{n})}$

${\displaystyle \Delta ^{2}(a_{n})=\Delta (a_{n+1})-\Delta (a_{n}),}$

который можно упростить до

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

В более общем смысле: k -я разность последовательности a _n, записанной как , определяется рекурсивно как ${\displaystyle \Delta ^{k}(a_{n})}$

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

(Последовательность и его различие связаны между собой биномиальным преобразованием ) . В более ограничительном определении разностного уравнения является уравнением , состоящим из более _п и его к - ^я разностей. (Широко используемое более широкое определение трактует «разностное уравнение» как синоним «рекуррентного отношения». См., Например, рациональное разностное уравнение и матричное разностное уравнение .)

Собственно, легко увидеть, что

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

Таким образом, разностное уравнение может быть определена как уравнение , которое включает в _п , а _{п -1} , а _{п -2} и т.д. (или , что эквивалентно а _п , а _{п +1} , а _{п + 2} и т.д.)

Поскольку разностные уравнения являются очень распространенной формой повторения, некоторые авторы используют эти два термина как синонимы. Например, разностное уравнение

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

эквивалентно рекуррентному соотношению

${\displaystyle 3a_{n+2}=4a_{n+1}-8a_{n}.}$

Таким образом, можно решить многие рекуррентные соотношения, перефразируя их как разностные уравнения, а затем решая разностное уравнение, аналогично тому, как решаются обыкновенные дифференциальные уравнения . Однако числа Аккермана являются примером рекуррентного отношения, которое не отображается в разностное уравнение, не говоря уже о точках решения дифференциального уравнения.

См. Исчисление шкалы времени для объединения теории разностных уравнений с теорией дифференциальных уравнений .

Уравнения суммирования относятся к разностным уравнениям, как интегральные уравнения относятся к дифференциальным уравнениям.

От последовательностей к сеткам [ править ]

Однопеременные или одномерные рекуррентные отношения относятся к последовательностям (то есть функциям, определенным на одномерных сетках). Многопараметрические или n-мерные рекуррентные отношения относятся к n-мерным сеткам. Функции, определенные на n-сетках, также можно изучать с помощью уравнений в частных разностях . ^[2]

Решение [ править ]

Решение однородных линейных рекуррентных соотношений с постоянными коэффициентами [ править ]

Корни характеристического многочлена [ править ]

Однородная линейная рекуррентность порядка d с постоянными коэффициентами - это уравнение вида

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

где коэффициенты d c _i (для всех i ) являются константами, и .${\displaystyle c_{d}\neq 0}$

Постоянная рекурсивная последовательность представляет собой последовательность , удовлетворяющая повторению этой формы. Решения этого повторения имеют d степеней свободы , т. Е. В качестве начальных значений могут приниматься любые значения, но тогда повторение однозначно определяет последовательность.${\displaystyle a_{0},\dots ,a_{d-1}}$

Те же коэффициенты дают характеристический многочлен (также «вспомогательный многочлен»)

${\displaystyle p(t)=t^{d}-c_{1}t^{d-1}-c_{2}t^{d-2}-\cdots -c_{d}}$

чьи корни d играют решающую роль в поиске и понимании последовательностей, удовлетворяющих повторению. Если корни r ₁ , r ₂ , ... различны, то каждое решение рекурсии принимает вид

${\displaystyle a_{n}=k_{1}r_{1}^{n}+k_{2}r_{2}^{n}+\cdots +k_{d}r_{d}^{n},}$

где коэффициенты k _i определены так, чтобы соответствовать начальным условиям повторения. Когда одни и те же корни встречаются несколько раз, члены этой формулы, соответствующие второму и последующим вхождениям одного и того же корня, умножаются на возрастающие степени n . Например, если характеристический многочлен можно разложить на множители как ( x - r ) ³ , причем один и тот же корень r встречается три раза, то решение будет иметь вид

${\displaystyle a_{n}=k_{1}r^{n}+k_{2}nr^{n}+k_{3}n^{2}r^{n}.}$^[3]

А также числа Фибоначчей , другие последовательности константных-рекурсивный включают номера Лукаса и Лукас последовательность , то число Якобстали , то число Пеллы и в более общем случае решения для уравнения Пелля .

Для порядка 1 повторение

${\displaystyle a_{n}=ra_{n-1}}$

имеет решение а , _п  =  г ^л с ₀  = 1 и наиболее общее решение _п  =  кр ^п с в ₀  =  K . Характеристический многочлен, приравненный к нулю ( характеристическое уравнение ), просто t  -  r  = 0.

Решения таких рекуррентных соотношений более высокого порядка находятся систематическими средствами, часто с использованием того факта, что a _n  =  r ⁿ является решением для рекуррентности именно тогда, когда t  =  r является корнем характеристического многочлена. К этому можно подойти напрямую или с помощью производящих функций ( формальных степенных рядов ) или матриц.

Рассмотрим, например, рекуррентное отношение вида

${\displaystyle a_{n}=Aa_{n-1}+Ba_{n-2}.}$

Когда у него есть решение того же общего вида, что и a _n = r ⁿ ? Подставляя это предположение ( анзац ) в рекуррентное соотношение, находим, что

${\displaystyle r^{n}=Ar^{n-1}+Br^{n-2}}$

должно быть истинным для всех  n  > 1.

Разделив на r ^{n −2} , мы получим, что все эти уравнения сводятся к одному и тому же:

${\displaystyle r^{2}=Ar+B,}$

${\displaystyle r^{2}-Ar-B=0,}$

которое является характеристическим уравнением рекуррентного соотношения. Решите относительно r, чтобы получить два корня λ ₁ , λ ₂ : эти корни известны как характеристические корни или собственные значения характеристического уравнения. В зависимости от природы корней получаются разные решения: если эти корни разные, мы имеем общее решение

${\displaystyle a_{n}=C\lambda _{1}^{n}+D\lambda _{2}^{n}}$

а если они идентичны (когда A ²  + 4 B  = 0), мы имеем

${\displaystyle a_{n}=C\lambda ^{n}+Dn\lambda ^{n}}$

Это наиболее общее решение; две константы C и D могут быть выбраны на основе двух заданных начальных условий a ₀ и a ₁ для получения конкретного решения.

В случае комплексных собственных значений (которые также приводят к комплексным значениям для параметров решения C и D ) использование комплексных чисел можно исключить, переписав решение в тригонометрической форме. В этом случае мы можем записать собственные значения как. Тогда можно показать, что${\displaystyle \lambda _{1},\lambda _{2}=\alpha \pm \beta i.}$

${\displaystyle a_{n}=C\lambda _{1}^{n}+D\lambda _{2}^{n}}$

можно переписать как ^{[4] : 576–585}

${\displaystyle a_{n}=2M^{n}\left(E\cos(\theta n)+F\sin(\theta n)\right)=2GM^{n}\cos(\theta n-\delta ),}$

куда

${\displaystyle {\begin{array}{lcl}M={\sqrt {\alpha ^{2}+\beta ^{2}}}&\cos(\theta )={\tfrac {\alpha }{M}}&\sin(\theta )={\tfrac {\beta }{M}}\\C,D=E\mp Fi&&\\G={\sqrt {E^{2}+F^{2}}}&\cos(\delta )={\tfrac {E}{G}}&\sin(\delta )={\tfrac {F}{G}}\end{array}}}$

Здесь E и F (или, что эквивалентно, G и δ) - действительные постоянные, которые зависят от начальных условий. С помощью

${\displaystyle \lambda _{1}+\lambda _{2}=2\alpha =A,}$

${\displaystyle \lambda _{1}\cdot \lambda _{2}=\alpha ^{2}+\beta ^{2}=-B,}$

можно упростить решение, данное выше, как

${\displaystyle a_{n}=(-B)^{\frac {n}{2}}\left(E\cos(\theta n)+F\sin(\theta n)\right),}$

где a ₁ и a ₂ - начальные условия, а

${\displaystyle {\begin{aligned}E&={\frac {-Aa_{1}+a_{2}}{B}}\\F&=-i{\frac {A^{2}a_{1}-Aa_{2}+2a_{1}B}{B{\sqrt {A^{2}+4B}}}}\\\theta &=\arccos \left({\frac {A}{2{\sqrt {-B}}}}\right)\end{aligned}}}$

Таким образом, нет необходимости решать λ ₁ и λ ₂ .

Во всех случаях - действительные различные собственные значения, действительные дублированные собственные значения и комплексно сопряженные собственные значения - уравнение является устойчивым (то есть, переменная a сходится к фиксированному значению [в частности, нулю]) тогда и только тогда, когда оба собственных значения меньше единицы в абсолютное значение . В этом случае второго порядка это условие на собственные значения может быть показано ^[5] как эквивалентное | А | <1 -  B  <2, что эквивалентно | B | <1 и | А | <1 -  Б .

Уравнение в приведенном выше примере было однородным в том смысле , что не было постоянного члена. Если начать с неоднородного повторения

${\displaystyle b_{n}=Ab_{n-1}+Bb_{n-2}+K}$

с постоянным членом K , это может быть преобразовано в однородную форму следующим образом: Установившееся состояние находится путем установки b _n =  b _{n −1} =  b _{n −2} =  b *, чтобы получить

${\displaystyle b^{*}={\frac {K}{1-A-B}}.}$

Тогда неоднородную рекуррентность можно переписать в однородном виде как

${\displaystyle [b_{n}-b^{*}]=A[b_{n-1}-b^{*}]+B[b_{n-2}-b^{*}],}$

который можно решить, как указано выше.

Условие устойчивости, сформулированное выше в терминах собственных значений для случая второго порядка, остается в силе для общего случая n- ^го порядка: уравнение является устойчивым тогда и только тогда, когда все собственные значения характеристического уравнения меньше единицы по модулю.

Для однородного линейного рекуррентного соотношения с постоянными коэффициентами порядка d пусть p ( t ) - характеристический многочлен (также «вспомогательный многочлен»)

${\displaystyle t^{d}-c_{1}t^{d-1}-c_{2}t^{d-2}-\cdots -c_{d}=0}$

такое, что каждый c _i соответствует каждому c _i в исходном рекуррентном соотношении (см. общую форму выше). Предположим, что λ - корень p ( t ) кратности r . Это означает, что ( t - λ) ^r делит p ( t ). Имеют место два следующих свойства:

1. Каждая из r последовательностей удовлетворяет рекуррентному соотношению.${\displaystyle \lambda ^{n},n\lambda ^{n},n^{2}\lambda ^{n},\dots ,n^{r-1}\lambda ^{n}}$
2. Любую последовательность, удовлетворяющую рекуррентному соотношению, можно однозначно записать как линейную комбинацию решений, построенных в части 1, когда λ изменяется по всем различным корням  p ( t ).

В результате этой теоремы однородное линейное рекуррентное соотношение с постоянными коэффициентами может быть решено следующим образом:

1. Найдите характеристический многочлен p ( t ).
2. Найдите корни p ( t ) с учетом кратности.
3. Запишите a _n как линейную комбинацию всех корней (с учетом кратности, как показано в теореме выше) с неизвестными коэффициентами b _i .

${\displaystyle a_{n}=\left(b_{1}\lambda _{1}^{n}+b_{2}n\lambda _{1}^{n}+b_{3}n^{2}\lambda _{1}^{n}+\cdots +b_{r}n^{r-1}\lambda _{1}^{n}\right)+\cdots +\left(b_{d-q+1}\lambda _{*}^{n}+\cdots +b_{d}n^{q-1}\lambda _{*}^{n}\right)}$

Это общее решение исходного рекуррентного отношения. ( q - кратность λ _* )

4. Приравняйте каждое значение из части 3 (включение n = 0, ..., d в общее решение рекуррентного отношения) с известными значениями из исходного рекуррентного отношения. Однако значения a _n из исходного используемого рекуррентного отношения обычно не обязательно должны быть смежными: за исключением исключительных случаев, необходимо всего d из них (т. Е. Для исходного однородного линейного рекуррентного отношения порядка 3 можно использовать значения a ₀ , а ₁ , а ₄ ). Этот процесс приведет к линейной системе d уравнений с d${\displaystyle a_{0},a_{1},\dots ,a_{d}}$${\displaystyle a_{0},a_{1},\dots ,a_{d}}$неизвестные. Решение этих уравнений для неизвестных коэффициентов общего решения и включение этих значений обратно в общее решение даст частное решение исходного рекуррентного отношения, которое соответствует начальным условиям исходного рекуррентного отношения (а также всем последующим значениям исходного рекуррентного отношения ).${\displaystyle b_{1},b_{2},\dots ,b_{d}}$${\displaystyle a_{0},a_{1},a_{2},\dots }$

Метод решения линейных дифференциальных уравнений аналогичен описанному выше методу - «интеллектуальное предположение» ( анзац ) для линейных дифференциальных уравнений с постоянными коэффициентами - это e ^{λ x,} где λ - комплексное число, которое определяется путем подстановки предположения в дифференциальное уравнение. .

Это не совпадение. Рассматривая ряд Тейлора решения линейного дифференциального уравнения:

${\displaystyle \sum _{n=0}^{\infty }{\frac {f^{(n)}(a)}{n!}}(x-a)^{n}}$

можно видеть, что коэффициенты ряда задаются n- ^й производной функции f ( x ), вычисленной в точке a . Дифференциальное уравнение представляет собой линейное разностное уравнение, связывающее эти коэффициенты.

Эту эквивалентность можно использовать для быстрого решения рекуррентной зависимости для коэффициентов в решении степенного ряда линейного дифференциального уравнения.

Практическое правило (для уравнений, в которых многочлен, умножающий первый член, не равен нулю в нуле), заключается в следующем:

${\displaystyle y^{[k]}\to f[n+k]}$

и вообще

${\displaystyle x^{m}*y^{[k]}\to n(n-1)...(n-m+1)f[n+k-m]}$

Пример: рекуррентное соотношение для коэффициентов ряда Тейлора уравнения:

${\displaystyle (x^{2}+3x-4)y^{[3]}-(3x+1)y^{[2]}+2y=0}$

дан кем-то

${\displaystyle n(n-1)f[n+1]+3nf[n+2]-4f[n+3]-3nf[n+1]-f[n+2]+2f[n]=0}$

или же

${\displaystyle -4f[n+3]+2nf[n+2]+n(n-4)f[n+1]+2f[n]=0.}$

Этот пример показывает, как проблемы, обычно решаемые с использованием метода решения степенного ряда, преподаваемого в классах нормальных дифференциальных уравнений, могут быть решены гораздо проще.

Пример: дифференциальное уравнение

${\displaystyle ay''+by'+cy=0}$

есть решение

${\displaystyle y=e^{ax}.}$

Преобразование дифференциального уравнения в разностное уравнение коэффициентов Тейлора имеет вид

${\displaystyle af[n+2]+bf[n+1]+cf[n]=0.}$

Легко видеть , что п - й производной е ^ах оценивается в точке 0 ^п

Решение с помощью линейной алгебры [ править ]

Линейно рекурсивная последовательность y порядка n

${\displaystyle y_{n+k}-c_{n-1}y_{n-1+k}-c_{n-2}y_{n-2+k}+\cdots -c_{0}y_{k}=0}$

идентичен

${\displaystyle y_{n}=c_{n-1}y_{n-1}+c_{n-2}y_{n-2}+\cdots +c_{0}y_{0}.}$

Расширенное с помощью n −1 тождеств , это уравнение n-го порядка переводится в систему матричных разностных уравнений из n линейных уравнений первого порядка,${\displaystyle y_{n-k}=y_{n-k}}$

${\displaystyle \mathbf {y} _{n}={\begin{bmatrix}y_{n}\\y_{n-1}\\\vdots \\\vdots \\y_{1}\end{bmatrix}}={\begin{bmatrix}c_{n-1}&c_{n-2}&\cdots &\cdots &c_{0}\\1&0&\cdots &\cdots &0\\0&\ddots &\ddots &&\vdots \\\vdots &\ddots &\ddots &\ddots &\vdots \\0&\cdots &0&1&0\end{bmatrix}}{\begin{bmatrix}y_{n-1}\\y_{n-2}\\\vdots \\\vdots \\y_{0}\end{bmatrix}}=C\mathbf {y} _{n-1}=C^{n}\mathbf {y} _{0}.}$

Заметим , что вектор может быть вычислена по п применений матрицы компаньон , C , к исходному вектору состояния, . Таким образом, n -я запись искомой последовательности y является верхним компонентом .${\displaystyle \mathbf {y} _{n}}$${\displaystyle y_{0}}$${\displaystyle \mathbf {y} _{n},y_{n}=\mathbf {y} _{n}[n]}$

Eigendecomposition , в собственных, и собственные векторы , используется для вычислений . Благодаря тому важному факту, что система C сдвигает во времени каждый собственный вектор e , просто масштабируя его компоненты в λ раз,${\displaystyle \mathbf {y} _{n}=C^{n}\,\mathbf {y} _{0}=a_{1}\,\lambda _{1}^{n}\,\mathbf {e} _{1}+a_{2}\,\lambda _{2}^{n}\,\mathbf {e} _{2}+\cdots +a_{n}\,\lambda _{n}^{n}\,\mathbf {e} _{n}}$${\displaystyle \lambda _{1},\lambda _{2},\ldots ,\lambda _{n}}$${\displaystyle \mathbf {e} _{1},\mathbf {e} _{2},\ldots ,\mathbf {e} _{n}}$${\displaystyle \mathbf {y} _{n}}$

${\displaystyle C\,\mathbf {e} _{i}=\lambda _{i}\mathbf {e} _{i}=C{\begin{bmatrix}e_{i,n}\\e_{i,n-1}\\\vdots \\e_{i,1}\end{bmatrix}}={\begin{bmatrix}\lambda _{i}\,e_{i,n}\\\lambda _{i}\,e_{i,n-1}\\\vdots \\\lambda _{i}\,e_{i,1}\end{bmatrix}}}$

то есть, со сдвигом во времени вариант собственного вектора, е , имеет компоненты А раз больше, компоненты собственного вектора силы Х , и, таким образом, рецидивирующий однородное линейное решение уравнения представляет собой комбинацию показательных функций, . Компоненты могут быть определены из начальных условий:${\displaystyle \mathbf {e} _{i}={\begin{bmatrix}\lambda _{i}^{n-1}&\cdots &\lambda _{i}^{2}&\lambda _{i}&1\end{bmatrix}}^{\mathrm {T} },}$${\displaystyle \mathbf {y} _{n}=\sum _{1}^{n}{c_{i}\,\lambda _{i}^{n}\,\mathbf {e} _{i}}}$${\displaystyle c_{i}}$

${\displaystyle \mathbf {y} _{0}={\begin{bmatrix}y_{0}\\y_{-1}\\\vdots \\y_{-n+1}\end{bmatrix}}=\sum _{i=1}^{n}{c_{i}\,\lambda _{i}^{0}\,\mathbf {e} _{i}}={\begin{bmatrix}\mathbf {e} _{1}&\mathbf {e} _{2}&\cdots &\mathbf {e} _{n}\end{bmatrix}}\,{\begin{bmatrix}c_{1}\\c_{2}\\\vdots \\c_{n}\end{bmatrix}}=E\,{\begin{bmatrix}c_{1}\\c_{2}\\\vdots \\c_{n}\end{bmatrix}}}$

Решая для коэффициентов,

${\displaystyle {\begin{bmatrix}c_{1}\\c_{2}\\\vdots \\c_{n}\end{bmatrix}}=E^{-1}\mathbf {y} _{0}={\begin{bmatrix}\lambda _{1}^{n-1}&\lambda _{2}^{n-1}&\cdots &\lambda _{n}^{n-1}\\\vdots &\vdots &\ddots &\vdots \\\lambda _{1}&\lambda _{2}&\cdots &\lambda _{n}\\1&1&\cdots &1\end{bmatrix}}^{-1}\,{\begin{bmatrix}y_{0}\\y_{-1}\\\vdots \\y_{-n+1}\end{bmatrix}}.}$

Это также работает с произвольными граничными условиями , не обязательно с начальными,${\displaystyle \underbrace {y_{a},y_{b},\ldots } _{n}}$

${\displaystyle {\begin{bmatrix}y_{a}\\y_{b}\\\vdots \end{bmatrix}}={\begin{bmatrix}\mathbf {y} _{a}[n]\\\mathbf {y} _{b}[n]\\\vdots \end{bmatrix}}={\begin{bmatrix}\sum _{i=1}^{n}{c_{i}\,\lambda _{i}^{a}\,\mathbf {e} _{i}[n]}\\\sum _{i=1}^{n}{c_{i}\,\lambda _{i}^{b}\,\mathbf {e} _{i}[n]}\\\vdots \end{bmatrix}}={\begin{bmatrix}\sum _{i=1}^{n}{c_{i}\,\lambda _{i}^{a}\,\lambda _{i}^{n-1}}\\\sum _{i=1}^{n}{c_{i}\,\lambda _{i}^{b}\,\lambda _{i}^{n-1}}\\\vdots \end{bmatrix}}}$

${\displaystyle ={\begin{bmatrix}\sum {c_{i}\,\lambda _{i}^{a+n-1}}\\\sum {c_{i}\,\lambda _{i}^{b+n-1}}\\\vdots \end{bmatrix}}={\begin{bmatrix}\lambda _{1}^{a+n-1}&\lambda _{2}^{a+n-1}&\cdots &\lambda _{n}^{a+n-1}\\\lambda _{1}^{b+n-1}&\lambda _{2}^{b+n-1}&\cdots &\lambda _{n}^{b+n-1}\\\vdots &\vdots &\ddots &\vdots \end{bmatrix}}\,{\begin{bmatrix}c_{1}\\c_{2}\\\vdots \\c_{n}\end{bmatrix}}.}$

Это описание действительно не отличается от общего метода, приведенного выше, однако оно более сжатое. Это также хорошо работает в таких ситуациях, как

${\displaystyle {\begin{cases}a_{n}=a_{n-1}-b_{n-1}\\b_{n}=2a_{n-1}+b_{n-1}.\end{cases}}}$

где есть несколько связанных повторений. ^[6]

Решение с Z-преобразованиями [ править ]

Некоторые разностные уравнения - в частности, линейные разностные уравнения с постоянными коэффициентами - могут быть решены с помощью z-преобразований . В Z -преобразования представляют собой класс интегральных преобразований , которые приводят к более удобным алгебраическим преобразованиям и более простых решениям. Бывают случаи, когда получение прямого решения практически невозможно, но решить проблему с помощью тщательно подобранного интегрального преобразования несложно.

Решение неоднородных линейных рекуррентных соотношений с постоянными коэффициентами [ править ]

Если повторение неоднородно, частное решение может быть найдено методом неопределенных коэффициентов, и решение представляет собой сумму решения однородного и частного решений. Другой метод решения неоднородной рекуррентности - это метод символического дифференцирования . Например, рассмотрите следующее повторение:

${\displaystyle a_{n+1}=a_{n}+1}$

Это неоднородное повторение. Если мы подставим n ↦ n +1, мы получим рекуррентность

${\displaystyle a_{n+2}=a_{n+1}+1}$

Вычитание исходной рекуррентности из этого уравнения дает

${\displaystyle a_{n+2}-a_{n+1}=a_{n+1}-a_{n}}$

или эквивалентно

${\displaystyle a_{n+2}=2a_{n+1}-a_{n}}$

Это однородная повторяемость, которую можно решить описанными выше методами. В общем случае, если линейная рекурсия имеет вид

${\displaystyle a_{n+k}=\lambda _{k-1}a_{n+k-1}+\lambda _{k-2}a_{n+k-2}+\cdots +\lambda _{1}a_{n+1}+\lambda _{0}a_{n}+p(n)}$

где - постоянные коэффициенты, а p ( n ) - неоднородность, то если p ( n ) - многочлен со степенью r , то эту неоднородную рекуррентность можно свести к однородной рекуррентности, применяя метод символического разложения r раз.${\displaystyle \lambda _{0},\lambda _{1},\dots ,\lambda _{k-1}}$

Если

${\displaystyle P(x)=\sum _{n=0}^{\infty }p_{n}x^{n}}$

- производящая функция неоднородности, производящая функция

${\displaystyle A(x)=\sum _{n=0}^{\infty }a(n)x^{n}}$

неоднородной повторяемости

${\displaystyle a_{n}=\sum _{i=1}^{s}c_{i}a_{n-i}+p_{n},\quad n\geq n_{r},}$

с постоянными коэффициентами c _i получается из

${\displaystyle \left(1-\sum _{i=1}^{s}c_{i}x^{i}\right)A(x)=P(x)+\sum _{n=0}^{n_{r}-1}[a_{n}-p_{n}]x^{n}-\sum _{i=1}^{s}c_{i}x^{i}\sum _{n=0}^{n_{r}-i-1}a_{n}x^{n}.}$

Если P ( x ) - рациональная производящая функция, A ( x ) - также единица. Рассмотренный выше случай, когда p _n = K - константа, возникает как один из примеров этой формулы, где P ( x ) = K / (1 - x ). Другой пример, повторяемость с линейной неоднородностью, возникает при определении шизофренических чисел . Решение однородных повторений включается как p = P = 0.${\displaystyle a_{n}=10a_{n-1}+n}$

Решение неоднородных рекуррентных соотношений первого порядка с переменными коэффициентами [ править ]

Более того, для общего неоднородного линейного рекуррентного соотношения первого порядка с переменными коэффициентами:

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

есть еще хороший способ решить эту проблему: ^[7]

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

${\displaystyle {\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}}}}$

${\displaystyle {\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}}}}$

Позволять

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

потом

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

${\displaystyle \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}}}}$

${\displaystyle {\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}}}}$

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

Если мы применим формулу и возьмем предел h → 0, мы получим формулу для линейных дифференциальных уравнений первого порядка с переменными коэффициентами; сумма становится интегралом, а произведение становится экспоненциальной функцией интеграла.${\displaystyle a_{n+1}=(1+hf_{nh})a_{n}+hg_{nh}}$

Решение общих однородных линейных рекуррентных соотношений [ править ]

Многие однородные линейные рекуррентные соотношения могут быть решены с помощью обобщенных гипергеометрических рядов . Их частные случаи приводят к рекуррентным соотношениям для ортогональных многочленов и многих специальных функций . Например, решение

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

дан кем-то

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

функции Бесселя , в то время как

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

решается

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

вырожденная гипергеометрическая серии . Последовательности, являющиеся решениями линейных разностных уравнений с полиномиальными коэффициентами , называются P-рекурсивными . Для этих конкретных рекуррентных уравнений известны алгоритмы, которые находят полиномиальные , рациональные или гипергеометрические решения.

Решение рациональных разностных уравнений первого порядка [ править ]

Рациональное разностное уравнение первого порядка имеет вид . Такое уравнение можно решить, записав как нелинейное преобразование другой переменной, которая сама изменяется линейно. Затем можно использовать стандартные методы для решения линейного разностного уравнения в .${\displaystyle w_{t+1}={\tfrac {aw_{t}+b}{cw_{t}+d}}}$${\displaystyle w_{t}}$${\displaystyle x_{t}}$${\displaystyle x_{t}}$

Стабильность [ править ]

Устойчивость линейных повторений высшего порядка [ править ]

Линейная рекуррентность порядка d ,

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

имеет характеристическое уравнение

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

Повторяемость является стабильной , что означает, что итерации асимптотически сходятся к фиксированному значению тогда и только тогда, когда собственные значения (т. Е. Корни характеристического уравнения), действительные или комплексные, меньше единицы по абсолютной величине.

Устойчивость линейных матричных повторений первого порядка [ править ]

В матричном разностном уравнении первого порядка

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

с вектором состояния x и матрицей перехода A , x сходится асимптотически к вектору x * устойчивого состояния тогда и только тогда, когда все собственные значения матрицы перехода A (действительные или комплексные) имеют абсолютное значение, меньшее 1.

Устойчивость нелинейных повторений первого порядка [ править ]

Рассмотрим нелинейное возвращение первого порядка

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

Это повторение является локально устойчивым , что означает, что оно сходится к фиксированной точке x * из точек, достаточно близких к x *, если наклон f в окрестности x * меньше единицы по абсолютной величине: то есть

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

Нелинейное возвращение может иметь несколько фиксированных точек, и в этом случае некоторые фиксированные точки могут быть локально устойчивыми, а другие - локально нестабильными; для непрерывного f две соседние неподвижные точки не могут быть обе локально устойчивыми.

Нелинейное рекуррентное соотношение может также иметь цикл периода k для k > 1. Такой цикл является устойчивым, что означает, что он привлекает набор начальных условий положительной меры, если составная функция

${\displaystyle g(x):=f\circ f\circ \cdots \circ f(x)}$

с f, появляющимся k раз, является локально устойчивым по тому же критерию:

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

где x * - любая точка цикла.

В хаотическом рекуррентном соотношении переменная x остается в ограниченной области, но никогда не сходится к фиксированной точке или к циклу притяжения; любые неподвижные точки или циклы уравнения неустойчивы. См. Также логистическую карту , диадическую трансформацию и карту палатки .

Связь с дифференциальными уравнениями [ править ]

При численном решении обыкновенного дифференциального уравнения обычно встречается рекуррентное соотношение. Например, при решении задачи начального значения

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

с помощью метода Эйлера и шага h вычисляются значения

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

повторением

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

Системы линейных дифференциальных уравнений первого порядка могут быть дискретизированы точно аналитически, используя методы, указанные в статье о дискретизации .

Приложения [ править ]

Биология [ править ]

Некоторые из наиболее известных разностных уравнений возникли в результате попытки моделирования динамики популяции . Например, числа Фибоначчи когда-то использовались в качестве модели роста популяции кроликов.

Логистическое отображение либо используется непосредственно для роста модели населения, или в качестве отправной точки для более детальных моделей динамики популяций . В этом контексте связанные разностные уравнения часто используются для моделирования взаимодействия двух или более популяций. Например, модель Николсона – Бейли для взаимодействия паразит- хозяин дается выражением

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

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

где N _t представляет хозяев, а P _t - паразитов в момент времени  t .

Уравнения интегроразличия - это форма рекуррентного соотношения, важная для пространственной экологии . Эти и другие разностные уравнения особенно подходят для моделирования одновольтных популяций.

Информатика [ править ]

Отношения рекуррентности также имеют фундаментальное значение при анализе алгоритмов . ^{[8] [9]} Если алгоритм разработан так, что он разбивает проблему на более мелкие подзадачи ( разделяй и властвуй ), время его выполнения описывается рекуррентным соотношением.

Простым примером является время, необходимое алгоритму для поиска элемента в упорядоченном векторе с элементами в худшем случае.${\displaystyle n}$

Наивный алгоритм будет искать слева направо, по одному элементу за раз. Наихудший из возможных сценариев - когда требуемый элемент является последним, поэтому количество сравнений равно .${\displaystyle n}$

Более лучший алгоритм называется двоичным поиском . Однако для этого требуется отсортированный вектор. Сначала он проверит, находится ли элемент в середине вектора. Если нет, то он проверит, больше или меньше средний элемент искомого. На этом этапе половину вектора можно отбросить, а алгоритм можно запустить снова на другой половине. Количество сравнений будет выражено

${\displaystyle c_{1}=1}$

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

временная сложность которого будет .${\displaystyle O(\log _{2}(n))}$

Цифровая обработка сигналов [ править ]

При цифровой обработке сигналов рекуррентные отношения могут моделировать обратную связь в системе, где выходы в один момент времени становятся входами для будущего времени. Таким образом, они возникают в цифровых фильтрах с бесконечной импульсной характеристикой (БИХ) .

Например, уравнение для гребенчатого БИХ- фильтра «с прямой связью» задержки T следующее :

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

где - вход в момент времени t , - выход в момент времени t , а α контролирует, какая часть задержанного сигнала возвращается на выход. Из этого мы видим, что${\displaystyle x_{t}}$${\displaystyle y_{t}}$

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

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

и Т. Д.

Экономика [ править ]

Рекуррентные отношения, особенно линейные рекуррентные отношения, широко используются как в теоретической, так и в эмпирической экономике. ^{[10] [11]} В частности, в макроэкономике можно разработать модель различных широких секторов экономики (финансовый сектор, сектор товаров, рынок труда и т. Д.), В которой действия некоторых агентов зависят от лаговых переменных. Затем модель будет решена для текущих значений ключевых переменных ( процентная ставка , реальный ВВП и т. Д.) С точки зрения прошлых и текущих значений других переменных.

См. Также [ править ]

Ссылки [ править ]

Сноски [ править ]

Библиография [ править ]

• Батчелдер, Пол М. (1967). Введение в линейные разностные уравнения . Dover Publications.
• Миллер, Кеннет С. (1968). Линейные разностные уравнения . WA Бенджамин.
• Филмор, Джей П .; Маркс, Моррис Л. (1968). «Линейные рекурсивные последовательности». SIAM Ред . 10 (3). С. 324–353. JSTOR  2027658 .
• Бруссо, Альфред (1971). Линейная рекурсия и последовательности Фибоначчи . Ассоциация Фибоначчи.
• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 1990. ISBN 0-262-03293-7 . Глава 4: Рецидивы, стр. 62–90. 
• Грэм, Рональд Л .; Knuth, Donald E .; Паташник, Орен (1994). Конкретная математика: фонд компьютерных наук (2-е изд.). Эддисон-Уэсли. ISBN 0-201-55802-5.
• Эндерс, Уолтер (2010). Прикладные эконометрические серии Times (3-е изд.). Архивировано из оригинала на 2014-11-10.
• Калл, Пол; Флайв, Мэри ; Робсон, Робби (2005). Разностные уравнения: от кроликов к хаосу . Springer. ISBN 0-387-23234-6. Глава 7.
• Жак, Ян (2006). Математика для экономики и бизнеса (Пятое изд.). Прентис Холл. стр.  551 -568. ISBN 0-273-70195-9. Глава 9.1: Разностные уравнения.
• Минь, Тан; Ван То, Тан (2006). «Использование производящих функций для решения линейных неоднородных рекуррентных уравнений» (PDF) . Proc. Int. Конф. Моделирование, моделирование и оптимизация, SMO'06 . С. 399–404.
• Полянин, Андрей Д. "Разностные и функциональные уравнения: точные решения" . в EqWorld - Мир математических уравнений.
• Полянин, Андрей Д. "Разностные и функциональные уравнения: методы" . в EqWorld - Мир математических уравнений.
• Ван, Сян-Шэн; Вонг, Родерик (2012). «Асимптотика ортогональных многочленов через рекуррентные соотношения». Анальный. Appl . 10 (2): 215–235. arXiv : 1101.4371 . DOI : 10.1142 / S0219530512500108 . S2CID  28828175 .

Внешние ссылки [ править ]

• "Отношение рекуррентности" , Энциклопедия математики , EMS Press , 2001 [1994]
• Вайсштейн, Эрик В. "Уравнение повторяемости" . MathWorld .
• "Индекс OEIS Rec" . Индекс OEIS на несколько тысяч примеров линейных повторов, отсортированных по порядку (количеству терминов) и сигнатуре (вектор значений постоянных коэффициентов)