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

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

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

Определение

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

куда

- функция, где X - множество, которому должны принадлежать элементы последовательности. Для любого , это определяет уникальную последовательность с первым элементом, называемым начальным значением .

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

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

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

Примеры

Факториал

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

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

Логистическая карта

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

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

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

Числа Фибоначчи

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

с начальными условиями

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

и т.п.

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

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

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

Биномиальные коэффициенты

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

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

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

Учитывая упорядоченную последовательность из действительных чисел : первое различие определяются как

Второе различие определяется как

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

В более общем смысле: k -я разность последовательности a n, записанной как , определяется рекурсивно как

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

Собственно, нетрудно заметить, что

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

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

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

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

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

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

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

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

Решение

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

Корни характеристического многочлена

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

где коэффициенты d c i (для всех i ) являются константами, и .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

можно переписать как

куда

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

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

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

Таким образом, нет необходимости определять λ 1 и λ 2 .

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

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

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

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

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

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

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

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

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

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

  1. Найдите характеристический многочлен p ( t ).
  2. Найдите корни p ( t ) с учетом кратности.
  3. Запишите a n как линейную комбинацию всех корней (с учетом кратности, как показано в теореме выше) с неизвестными коэффициентами b i .
    Это общее решение исходного рекуррентного отношения. ( q - кратность λ * )
  4. Приравняйте каждое из части 3 (включение n = 0, ..., d в общее решение рекуррентного отношения) с известными значениями из исходного рекуррентного отношения. Однако значения a n из исходного используемого рекуррентного отношения обычно не обязательно должны быть смежными: за исключением исключительных случаев, необходимо всего d из них (т. Е. Для исходного однородного линейного рекуррентного отношения порядка 3 можно использовать значения a 0 , а 1 , а 4 ). Этот процесс приведет к линейной системе d уравнений с d неизвестными. Решение этих уравнений для неизвестных коэффициентов общего решения и включение этих значений обратно в общее решение приведет к получению частного решения исходного рекуррентного отношения, которое соответствует начальным условиям исходного рекуррентного отношения (а также всем последующим значениям исходного рекуррентного отношения ).

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

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

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

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

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

и в более общем плане

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

дан кем-то

или

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

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

есть решение

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

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

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

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

идентичен

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

Заметим , что вектор может быть вычислена по п применений матрицы компаньон , C , к исходному вектору состояния, . Таким образом, n -я запись искомой последовательности y является верхним компонентом .

Eigendecomposition , в собственных, и собственные векторы , используется для вычислений . Благодаря тому решающему факту, что система C сдвигает во времени каждый собственный вектор e , просто масштабируя его компоненты в λ раз,

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

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

Это также работает с произвольными граничными условиями , не обязательно с начальными,

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

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

Решение с z-преобразованиями

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

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

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

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

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

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

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

где - постоянные коэффициенты, а p ( n ) - неоднородность, то если p ( n ) - многочлен со степенью r , то эту неоднородную рекуррентность можно свести к однородной рекуррентности, применяя метод символического разложения r раз.

Если

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

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

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

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

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

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

есть также хороший способ решить эту проблему:

Позволять

Затем

Если мы применим формулу и возьмем предел h → 0, мы получим формулу для линейных дифференциальных уравнений первого порядка с переменными коэффициентами; сумма становится интегралом, а произведение становится экспоненциальной функцией интеграла.

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

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

дан кем-то

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

решается

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

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

Рациональное разностное уравнение первого порядка имеет вид . Такое уравнение можно решить, записав нелинейное преобразование другой переменной, которая сама изменяется линейно. Затем можно использовать стандартные методы для решения линейного разностного уравнения в .

Стабильность

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

повторением

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

Приложения

Биология

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

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

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

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

Информатика

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

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

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

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

временная сложность которого будет .

Цифровая обработка сигналов

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

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

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

и т.п.

Экономика

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

Смотрите также

использованная литература

Сноски

Список используемой литературы

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