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

В математике рекуррентное соотношение — это уравнение , согласно которому $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}},}$ все задействованные целые числа меньше конечного результата).

Разностный оператор

The Оператор разности — это оператор , который отображает последовательности в последовательности и, в более общем смысле, функции в функции. Обычно его обозначают $\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} },$ тот первая a это разница $\Delta a.$

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

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

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

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

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

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

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

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

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

От последовательностей к сеткам

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

Решение

Решение линейных рекуррентных соотношений

Основная статья: Линейная рекуррентность с постоянными коэффициентами

неоднородных рекуррентных соотношений первого порядка с

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

$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-рекурсивными . Для этих конкретных рекуррентных уравнений известны алгоритмы, которые находят полиномиальные , рациональные или гипергеометрические решения.

разностных уравнений первого

Основная статья: Рациональное разностное уравнение

Рационально-разностное уравнение первого порядка имеет вид $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.$

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

линейных матричных рекуррентов

Основная статья: Матричное разностное уравнение

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

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

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

нелинейных рекуррентов

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

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

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

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

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

Нелинейное рекуррентное соотношение может также иметь цикл периода $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$.

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

Информатика

Рекуррентные соотношения также имеют фундаментальное значение при анализе алгоритмов . Если алгоритм спроектирован так, что он разбивает проблему на более мелкие подзадачи ( «разделяй и властвуй »), время его работы описывается рекуррентным соотношением.

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

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

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

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

и т. д.

Экономика

См. также: анализ временных рядов и модель одновременных уравнений.

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

См. также

• Голономные последовательности
• Итерированная функция
• Ортогональные полиномы
• Рекурсия
• Рекурсия (информатика)
• Генератор Фибоначчи с запаздыванием
• Основная теорема (анализ алгоритмов)
• Доказательство сегментов точек круга
• Непрерывная дробь
• Расчет шкалы времени
• Комбинаторные принципы
• Бесконечная импульсная характеристика
• Интегрирование по формулам приведения
• Математическая индукция

Ссылки

Библиография

• Батчелдер, Пол М. (1967). Введение в линейные разностные уравнения . Дуврские публикации.
• Миллер, Кеннет С. (1968). Линейные разностные уравнения . В. А. Бенджамин.
• Филлмор, Джей П.; Маркс, Моррис Л. (1968). «Линейно-рекурсивные последовательности». СИАМ преп . Том. 10, нет. 3. С. 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-е изд.). Архивировано из оригинала 10 ноября 2014 г.
• Калл, Пол; Флахайв, Мэри ; Робсон, Робби (2005). Разностные уравнения: от кроликов к хаосу . Спрингер. ISBN  0-387-23234-6 . глава 7.
• Жак, Ян (2006). Математика для экономики и бизнеса (Пятое изд.). Прентис Холл. стр. 551–568 . ISBN  0-273-70195-9 . Глава 9.1: Разностные уравнения.
• Минь, Тан; Ван То, Тан (2006). «Использование производящих функций для решения линейных неоднородных рекуррентных уравнений» (PDF) . Учеб. Межд. Конф. Моделирование, моделирование и оптимизация, СМО'06 . стр. 399–404. Архивировано из оригинала (PDF) 4 марта 2016 г. Проверено 7 августа 2014 г.
• Полянин Андрей Дмитриевич "Разностные и функциональные уравнения: точные решения" . в EqWorld - Мир математических уравнений.
• Полянин Андрей Дмитриевич «Разностные и функциональные уравнения: Методы» . в EqWorld - Мир математических уравнений.
• Ван, Сян-Шэн; Вонг, Родерик (2012). «Асимптотика ортогональных многочленов посредством рекуррентных соотношений». Анальный. Приложение . 10 (2): 215–235. arXiv : 1101.4371 . дои : 10.1142/S0219530512500108 . S2CID   28828175 .

Внешние ссылки

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