Рецидив отношение - Recurrence relation


Из Википедии, свободной энциклопедии

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

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

содержание

Определение

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

это рекуррентное соотношение , которое определяет уникальную последовательность с в качестве первого члена.

Часто, последовательность начинается от термина индекса 1 или выше, и это легко изменить определение соответствующим образом.

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

В этом случае, K начальные значения необходимы для определения последовательности.

Примеры

Факториал

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

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

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

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

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

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

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

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

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

Явное, повторение дает уравнение

и т.п.

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

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

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

биномиальных коэффициентов

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

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

Отношение к разностным уравнениям узко

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

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

который может быть упрощена

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

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

На самом деле, легко видеть, что,

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

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

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

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

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

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

Из последовательностей в сетках

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

Решение

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

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

Заказ запасной д однородная линейные рекуррентный с постоянными коэффициентами является уравнением вида

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

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

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

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

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

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

Для порядка 1, рецидив

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

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

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

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

должно быть справедливо для всех  п  > 1.

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

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

в то время как , если они идентичны (при 2  + 4 В  = 0), имеем

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

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

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

где

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

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

где 1 и 2 являются начальными условиями и

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

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

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

с постоянным термином K , это может быть преобразовано в гомогенную форму следующим образом : устойчивое состояние определяются путем установки б пб п -1Ь п -2б * , чтобы получить

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

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

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

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

таким образом, что каждый с я соответствую каждому с я в первоначальном рекуррентном соотношении (см общего вида выше). Предположим , что λ является корнем р ( т ) , имеющее кратность г . Это говорит о том, что ( т -λ) г делит р ( т ). Следующие два свойства:

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

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

  1. Найти характеристический многочлен р ( т ).
  2. Найти корни р ( т ) с учетом кратности.
  3. Написать в п виде линейной комбинации всех корней ( с учетом кратности , как показано в приведенной выше теореме) с неизвестными коэффициентами Ь I .
Это общее решение исходного рекуррентного соотношения. ( Д кратность Л * )
4. Приравниваем каждый из части 3 (подсоединение п = 0, ..., д в общее решение рекуррентного соотношения) с известными значениями из исходного рекуррентного соотношения. Однако значения п от первоначального рекуррентного соотношения , используемого обычно не должны быть смежными: кроме исключительных случаев, только d из них необходимо (т.е. для первоначального однородного линейного рекуррентного соотношения порядка 3 можно использовать значение - , 1 , 4 ). Этот процесс будет производить линейную систему д уравнений с д неизвестными. Решение этих уравнений для неизвестных коэффициентов общего решения и затыкать эти значения обратно в общее решение будет производить частное решение исходного рекуррентного соотношения , которое соответствует начальным условиям исходного рекуррентного соотношения в (а также все последующие значения исходного рекуррентного соотношения ).

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

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

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

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

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

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

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

дан кем-то

или же

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

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

имеет решение

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

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

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

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

идентичен

Expanded с п-1 тождеств вида этого п-го порядка уравнение преобразуется в матрицу разностного уравнения системы линейных уравнений п- го порядка,

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

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

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

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

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

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

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

Решение с Z-преобразований

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

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

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

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

Вычитание из оригинального повторения этого уравнения дает

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

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

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

Если

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

из неоднородного рецидива

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

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

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

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

есть также хороший способ, чтобы решить:

Позволять

затем

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

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

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

дан кем-то

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

решается

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

с F появляться K раз локально устойчиво по одному и тому же критерию:

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

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

Отношение к дифференциальным уравнениям

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

с методом Эйлера и размера шага ч , один вычисляет значения

путем повторения

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

Приложения

Биология

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

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

с N T , представляющей хозяев, и Р т паразитов, в момент времени  т .

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

Информатика

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

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

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

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

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

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

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

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

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

и т.п.

экономика

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

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

Заметки

Рекомендации

внешняя ссылка