Рекуррентное соотношение

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

В линейных рекуррентах n - й член приравнивается к линейной функции предыдущих членов. Известным примером является рекуррентность для чисел Фибоначчи , где порядок равен двум, а линейная функция просто складывает два предыдущих члена. Этот пример представляет собой линейную рекуррентность с постоянными коэффициентами , поскольку коэффициенты линейной функции (1 и 1) являются константами, не зависящими от Для этих рекуррент можно выразить общий член последовательности как выражение в замкнутой форме . Кроме того, линейные рекуррентности с полиномиальными коэффициентами, зависящими от, также важны, поскольку многие общие элементарные и специальные функции имеют ряд Тейлора , коэффициенты которого удовлетворяют такому рекуррентному соотношению (см. голономную функцию ).${\displaystyle к}$$${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$$${\displaystyle к}$${\displaystyle сущ.}$${\displaystyle n}$${\displaystyle n}$

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

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

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

${\displaystyle u_{n}=\varphi (n,u_{n-1})\quad {\text{для}}\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{для}}\quad n\geq k,}$

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

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

${\displaystyle n!=n\cdot (n-1)!\quad {\text{для}}\quad n>0,}$

и начальное состояние

${\displaystyle 0!=1.}$

Это пример линейной рекуррентности с полиномиальными коэффициентами порядка 1, с простым полиномом (в n )

${\displaystyle n}$

как его единственный коэффициент.

Примером рекуррентного отношения является логистическая карта, определяемая формулой

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

для заданной константы Поведение последовательности существенно зависит от начальных условий, но остается стабильным, когда они изменяются.${\displaystyle р.}$${\displaystyle r,}$${\displaystyle x_{0}}$

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

${\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, ...

Рекуррентное уравнение можно решить с помощью методов, описанных ниже, что дает формулу Бине , которая включает степени двух корней характеристического многочлена ; производящая функция последовательности является рациональной функцией${\displaystyle t^{2}=t+1}$

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

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

${\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 {\binom {n}{k}}={\binom {n}{k-1}}(n-k+1)/k,}$

с начальным значением (Деление не отображается как дробь, чтобы подчеркнуть, что оно должно быть вычислено после умножения, чтобы не вводить дробные числа). Эта рекуррентность широко используется в компьютерах, поскольку она не требует построения таблицы, как двумерная рекуррентность, и не включает очень большие целые числа, как формула с факториалами (если использовать все задействованные целые числа, то они будут меньше конечного результата).${\textstyle {\binom {n}{0}}=1}$${\textstyle {\binom {n}{k}}={\binom {n}{n-k}},}$

TheОператор разности — этооператор, который отображаетпоследовательностив последовательности и, в более общем смысле,функциив функции. Он обычно обозначаетсяи определяется вфункциональной нотациикак ${\displaystyle \Delta ,}$

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

Таким образом, это частный случай конечной разности .

При использовании индексной записи для последовательностей определение становится

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

Скобки вокруг и обычно опускаются и должны пониматься как член индекса n в последовательности , а не применяться к элементу${\displaystyle \Delta f}$${\displaystyle \Delta a}$${\displaystyle \Delta a_{n}}$${\displaystyle \Delta a,}$${\displaystyle \Delta }$${\displaystyle a_{n}.}$

Приведенная последовательность ​${\displaystyle a=(a_{n})_{n\in \mathbb {N} },}$Первое отличиеaравно${\displaystyle \Delta a.}$

TheВторое отличие : Простой расчет показывает, что${\displaystyle \Delta ^{2}a=(\Delta \circ \Delta )a=\Delta (\Delta a).}$

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

В более общем случае: k -я разность определяется рекурсивно как и имеем${\displaystyle \Delta ^{k}=\Delta \circ \Delta ^{k-1},}$

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

Это отношение можно инвертировать, получив

${\displaystyle 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 в рекуррентное соотношение порядка k . Каждое преобразование является обратным другому, и последовательности, являющиеся решением разностного уравнения, — это в точности те, которые удовлетворяют рекуррентному соотношению.

Например, разностное уравнение

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

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

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

в том смысле, что оба уравнения удовлетворяются одними и теми же последовательностями.

Поскольку для последовательности эквивалентно удовлетворять рекуррентному соотношению или быть решением разностного уравнения, два термина «рекуррентное соотношение» и «разностное уравнение» иногда используются взаимозаменяемо. См. Рациональное разностное уравнение и Матричное разностное уравнение для примера использования «разностного уравнения» вместо «рекуррентного соотношения»

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

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

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

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

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

есть также хороший метод решения этой проблемы: ^[3]

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

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

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

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

Линейная рекуррентность порядка ,${\displaystyle 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^{*}]}$

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

Рассмотрим нелинейную рекуррентность первого порядка

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

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

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

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

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

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

с появляющимися временами локально устойчиво по тому же критерию:${\displaystyle f}$${\displaystyle k}$

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

где находится любая точка цикла.${\displaystyle x^{*}}$

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

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

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

с помощью метода Эйлера и размера шага вычисляются значения${\displaystyle 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}}),}$

с представлением хозяев и паразитов в определенный момент времени .${\displaystyle N_{t}}$${\displaystyle P_{t}}$${\displaystyle t}$

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

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

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

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

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

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

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

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

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

Например, уравнение для гребенчатого фильтра задержки с прямой связью (БИХ) выглядит следующим образом:${\displaystyle T}$

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

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

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

и т. д.

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

• Батчелдер, Пол М. (1967). Введение в линейные разностные уравнения . Dover Publications.
• Миллер, Кеннет С. (1968). Линейные разностные уравнения . WA Benjamin.
• Fillmore, Jay P.; Marx, Morris L. (1968). «Линейные рекурсивные последовательности». SIAM Rev. Vol. 10, no. 3. pp. 324–353. JSTOR  2027658.
• Бруссо, Альфред (1971). Линейная рекурсия и последовательности Фибоначчи. Ассоциация Фибоначчи.
• Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Стайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 1990. ISBN 0-262-03293-7 . Глава 4: Повторяющиеся явления, стр. 62–90. 
• Грэм, Рональд Л.; Кнут, Дональд Э.; Паташник, Орен (1994). Конкретная математика: основа компьютерной науки (2-е изд.). Эддисон-Уэсли. ISBN 0-201-55802-5.
• Эндерс, Уолтер (2010). Прикладные эконометрические временные ряды (3-е изд.). Архивировано из оригинала 2014-11-10.
• Калл, Пол; Флэхайв, Мэри ; Робсон, Робби (2005). Разностные уравнения: от кроликов к хаосу . Springer. ISBN 0-387-23234-6.глава 7.
• Жак, Ян (2006). Математика для экономики и бизнеса (Пятое изд.). Prentice Hall. С. 551–568. ISBN 0-273-70195-9.Глава 9.1: Разностные уравнения.
• Minh, Tang; Van To, Tan (2006). "Использование производящих функций для решения линейных неоднородных рекуррентных уравнений" (PDF) . Proc. Int. Conf. Simulation, Modelling and Optimization, SMO'06 . pp. 399–404. Архивировано из оригинала (PDF) 2016-03-04 . Получено 2014-08-07 .
• Полянин, Андрей Д. «Разностные и функциональные уравнения: точные решения».в EqWorld — Мире математических уравнений.
• Полянин, Андрей Д. «Разностные и функциональные уравнения: Методы».в EqWorld — Мире математических уравнений.
• Ван, Сян-Шэн; Вонг, Родерик (2012). «Асимптотика ортогональных многочленов с помощью рекуррентных соотношений». Anal. Appl . 10 (2): 215–235. arXiv : 1101.4371 . doi :10.1142/S0219530512500108. S2CID  28828175.

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