Линейная рекуррентность с постоянными коэффициентами
В математике (включая комбинаторику , линейную алгебру и динамические системы ) линейная рекуррентность с постоянными коэффициентами [1] : гл. 17 [2] : гл. 10 (также известное как линейное рекуррентное соотношение или линейное разностное уравнение ) устанавливает равным 0 многочлен , который является линейным в различных итерациях переменной , то есть в значениях элементов последовательности . Линейность полинома означает, что каждый из его членов имеет степень 0 или 1. Линейная рекуррентность обозначает эволюцию некоторой переменной во времени, при этом текущий период времени или дискретный момент времени обозначается как t , один период ранее обозначался как t - 1 , на один период позже как t + 1 и т. д.
Решение , а не каких-либо итеративных значений, что такого уравнения является функцией t дает значение итерации в любой момент времени. Чтобы найти решение, необходимо знать конкретные значения (известные как начальные условия ) n итераций, и обычно это n самых старых итераций. Уравнение или его переменная называется устойчивой, если из любого набора начальных условий существует предел переменной при стремлении времени к бесконечности; этот предел называется установившимся состоянием .
Уравнения разностей используются в различных контекстах, например, в экономике для моделирования эволюции во времени таких переменных, как валовой внутренний продукт , уровень инфляции , обменный курс и т. д. Они используются при моделировании таких временных рядов , потому что значения этих переменных переменные измеряются только через дискретные интервалы времени. В эконометрических приложениях линейные разностные уравнения моделируются с использованием стохастических терминов в форме моделей авторегрессии (AR) и в таких моделях, как векторная авторегрессия (VAR) и модели авторегрессионного скользящего среднего (ARMA), которые сочетают AR с другими функциями.
Определения
[ редактировать ]Линейная рекуррентная функция с постоянными коэффициентами представляет собой уравнение следующего вида, записанное через параметры a 1 , ..., a n и b :
или эквивалентно как
Положительное целое число называется порядком повторения и обозначает наибольшую временную задержку между итерациями. Уравнение называется однородным, если b = 0 , и неоднородным , если b ≠ 0 .
Если уравнение однородное, коэффициенты определяют характеристический полином (также «вспомогательный полином» или «сопутствующий полином»).
корни которого играют решающую роль в поиске и понимании последовательностей, удовлетворяющих повторяемости.
Преобразование в гомогенную форму
[ редактировать ]Если b ≠ 0 , уравнение
говорят, что он неоднороден . Для решения этого уравнения удобно привести его к однородному виду, без постоянного члена. уравнения Это делается путем нахождения значения устойчивого состояния — значения y * такого, что, если все n последовательных итераций имели это значение, то же самое будет и со всеми будущими значениями. Это значение находится путем установки всех значений y равными y * в разностном уравнении и решения, таким образом получая
при условии, что знаменатель не равен 0. Если он равен нулю, установившегося состояния не существует.
Учитывая установившийся режим, разностное уравнение можно переписать в терминах отклонений итераций от установившегося состояния:
который не имеет постоянного члена и который можно более кратко записать как
где x равно y - y * . Это гомогенная форма.
Если стационарного состояния нет, то разностное уравнение
может быть объединено с его эквивалентной формой
чтобы получить (путем решения обоих для b )
в котором подобные члены могут быть объединены в однородное уравнение на один порядок выше исходного.
Пример решения для небольших заказов
[ редактировать ]Корни характеристического полинома играют решающую роль в поиске и понимании последовательностей, удовлетворяющих рекуррентности. Если есть отдельные корни тогда каждое решение рекуррентного уравнения принимает вид где коэффициенты определяются так, чтобы соответствовать начальным условиям рекуррентности. Когда одни и те же корни встречаются несколько раз, члены в этой формуле, соответствующие второму и последующим появлениям одного и того же корня, умножаются на возрастающую степень . Например, если характеристический полином можно разложить как , с тем же корнем повторится три раза, то решение примет вид [3]
Заказ 1
[ редактировать ]Для заказа 1 повторяемость есть решение с и наиболее общее решение с . Характеристический многочлен, равный нулю ( характеристическое уравнение ), представляет собой просто .
Заказ 2
[ редактировать ]Решения таких рекуррентных соотношений более высокого порядка находятся систематическим путем, часто используя тот факт, что является решением для повторения именно тогда, когда является корнем характеристического многочлена. К этому можно подойти напрямую или с помощью производящих функций ( формальных степенных рядов ) или матриц.
Рассмотрим, например, рекуррентное соотношение вида
Когда оно имеет решение того же общего вида, что и ? Подставив это предположение ( анзац ) в рекуррентное соотношение, мы находим, что должно быть верно для всех .
Разделив на , мы получаем, что все эти уравнения сводятся к одному и тому же:
что является характеристическим уравнением рекуррентного соотношения. Решите для чтобы получить два корня , : эти корни известны как характеристические корни или собственные значения характеристического уравнения. В зависимости от природы корней получаются разные решения: если эти корни различны, мы имеем общее решение
а если они идентичны (когда ), у нас есть
Это наиболее общее решение; две константы и может быть выбран на основе двух заданных начальных условий и для получения конкретного решения.
В случае комплексных собственных значений (что также приводит к комплексным значениям параметров решения и ), от использования комплексных чисел можно избавиться, переписав решение в тригонометрической форме. В этом случае мы можем записать собственные значения как Тогда можно показать, что
можно переписать как [4] : 576–585
где
Здесь и (или, что то же самое, и ) — действительные константы, зависящие от начальных условий. С использованием
можно упростить решение, данное выше, как
где и являются начальные условия и
Таким образом, нет необходимости решать и .
Во всех случаях — вещественных различных собственных значений, вещественных дублированных собственных значений и комплексно-сопряженных собственных значений — уравнение устойчиво (т. е. переменная сходится к фиксированному значению [в частности, к нулю]) тогда и только тогда, когда оба меньше единицы собственных значения по абсолютной величине . В этом случае второго порядка это условие на собственные значения можно показать [5] быть эквивалентным , что эквивалентно и .
Общее решение
[ редактировать ]Характеристический полином и корни
[ редактировать ]Решение однородного уравнения
предполагает сначала решение его характеристического многочлена
для его характеристических корней λ 1 , ..., λ n . Эти корни можно решить алгебраически, если n ≤ 4 , но не обязательно в противном случае . Если решение необходимо использовать численно, все корни этого характеристического уравнения можно найти численными методами . Однако для использования в теоретическом контексте может оказаться, что единственная информация, необходимая о корнях, — это то, больше ли какой-либо из них или равен 1 по абсолютной величине .
Возможно, все корни действительны , или некоторые из них могут быть комплексными числами . В последнем случае все комплексные корни образуют комплексно-сопряженные пары.
Решение с различными характеристическими корнями
[ редактировать ]Если все характеристические корни различны, то решение однородной линейной рекуррентной задачи
можно записать через характеристические корни как
где коэффициенты c i можно найти, вызвав начальные условия. В частности, для каждого периода времени, для которого известно значение итерации, это значение и соответствующее ему значение t можно подставить в уравнение решения, чтобы получить линейное уравнение с n пока еще неизвестными параметрами; n таких уравнений, по одному для каждого начального условия, могут быть решены одновременно для n значений параметров. Если все характеристические корни действительны, то все значения коэффициентов c i также будут вещественными; но с недействительными комплексными корнями некоторые из этих коэффициентов, как правило, также будут недействительными.
Преобразование комплексного решения к тригонометрической форме
[ редактировать ]Если есть комплексные корни, они входят в пары сопряженных, как и комплексные члены в уравнении решения. Если два из этих комплексных членов равны c j λ т
j и c j +1 λ т
j +1 корни λ j можно записать как
где i — мнимая единица , а M — модуль корней:
Тогда два комплексных члена уравнения решения можно записать как
где θ — угол, косинус которого равен α / M и чей синус β / М ; последнее равенство здесь использовало формулу де Муавра .
Теперь процесс нахождения коэффициентов c j и c j +1 гарантирует, что они также являются комплексно-сопряженными, что можно записать как γ ± δi . Использование этого значения в последнем уравнении дает следующее выражение для двух комплексных членов уравнения решения:
что также можно записать как
где ψ — угол, косинус которого равен γ / √ γ 2 + д 2 и чей синус δ / √ γ 2 + д 2 .
Цикличность
[ редактировать ]В зависимости от начальных условий, даже если все корни действительны, итерации могут испытывать временную тенденцию подниматься выше и ниже значения устойчивого состояния. Но истинная цикличность предполагает постоянную тенденцию к колебаниям, и это происходит, если имеется хотя бы одна пара комплексно-сопряженных характеристических корней. Это можно увидеть в тригонометрической форме их вклада в уравнение решения, включающего cos θt и sin θt .
Решение с повторяющимися характеристическими корнями
[ редактировать ]В случае второго порядка, если два корня идентичны ( λ 1 = λ 2 ), их можно обозначить как λ , а решение может иметь вид
Решение преобразованием к матричной форме
[ редактировать ]Альтернативный метод решения предполагает преобразование разностного уравнения n- первого порядка го порядка в матричное разностное уравнение . Это достигается записью w 1, t = y t , w 2, t = y t −1 = w 1, t −1 , w 3, t = y t −2 = w 2, t −1 и так далее. . Тогда исходное единственное уравнение n -го порядка
можно заменить следующими n уравнениями первого порядка:
Определив вектор w i как
это можно представить в матричной форме как
Здесь A — матрица размера n × n, которой первая строка содержит 1 в , ..., n , а все остальные строки имеют одну 1, а все остальные элементы равны 0, а b — вектор-столбец с первым элементом b и с остальные его элементы равны 0.
Это матричное уравнение можно решить, используя методы, описанные в статье Матричное разностное уравнение .В однородном случае y i является параперманентом нижней треугольной матрицы [6]
Решение с использованием производящих функций
[ редактировать ]Повторение
можно решить с помощью теории производящих функций . Сначала мы пишем . Тогда рекуррентность эквивалентна следующему уравнению производящей функции:
где является полиномом степени не более корректировка первоначальных условий.Из этого уравнения мы можем решить, чтобы получить
Другими словами, не беспокоясь о точных коэффициентах, можно выразить как рациональную функцию
Замкнутую форму затем можно получить путем разложения на частичные дроби . В частности, если производящая функция записана как
тогда полином определяет начальный набор поправок , знаменатель определяет экспоненциальный член , и степень вместе с числителем определить коэффициент полинома .
Связь с решением дифференциальных уравнений
[ редактировать ]Метод решения линейных дифференциальных уравнений аналогичен описанному выше методу — «интеллектуальное предположение» ( анзац ) для линейных дифференциальных уравнений с постоянными коэффициентами: где — комплексное число, которое определяется путем подстановки предположения в дифференциальное уравнение.
Это не совпадение. Рассматривая ряд Тейлора решения линейного дифференциального уравнения:
видно, что коэффициенты ряда определяются выражением -я производная от оценивается в точке . Дифференциальное уравнение представляет собой линейное разностное уравнение, связывающее эти коэффициенты.
Эту эквивалентность можно использовать для быстрого решения рекуррентного соотношения для коэффициентов в решении степенного ряда линейного дифференциального уравнения.
Эмпирическое правило (для уравнений, в которых полином, умножающий первый член, не равно нулю в нуле) заключается в следующем:
и вообще
Пример: рекуррентное соотношение для коэффициентов ряда Тейлора уравнения:
дается
или
Этот пример показывает, как проблемы, которые обычно решаются с использованием метода решения степенных рядов, изучаемого на уроках обычных дифференциальных уравнений, могут быть решены гораздо проще.
Пример: дифференциальное уравнение
имеет решение
Преобразование дифференциального уравнения в разностное уравнение коэффициентов Тейлора имеет вид
Легко видеть, что -я производная от оценивается в является .
Решение с помощью z-преобразований
[ редактировать ]Некоторые разностные уравнения — в частности, линейные разностные уравнения с постоянными коэффициентами — можно решить с помощью z-преобразований . Z , которые приводят к более удобным алгебраическим -преобразования представляют собой класс интегральных преобразований манипуляциям и более простым решениям. Бывают случаи, когда получение прямого решения практически невозможно, однако решение проблемы с помощью тщательно выбранного интегрального преобразования является простым.
Стабильность
[ редактировать ]В уравнении решения
член с действительными характеристическими корнями сходится к 0 по мере того, как t становится неопределенно большим, если абсолютное значение характеристического корня меньше 1. Если абсолютное значение равно 1, член будет оставаться постоянным по мере роста t , если корень равен +1, но будет колеблются между двумя значениями, если корень равен -1. Если абсолютное значение корня больше 1, член со временем будет становиться все больше и больше. Пара слагаемых с комплексно-сопряженными характеристическими корнями будет сходиться к 0 при затухании колебаний, если абсолютное значение модуля М корней меньше 1; если модуль равен 1, то колебания постоянной амплитуды в объединенных слагаемых сохранятся; и если модуль больше 1, объединенные члены будут демонстрировать колебания постоянно возрастающей величины.
Таким образом, развивающаяся переменная x будет стремиться к 0, если все характеристические корни имеют величину меньше 1.
Если наибольший корень имеет абсолютное значение 1, ни сходимости к 0, ни расхождения к бесконечности не произойдет. Если все корни с величиной 1 действительны и положительны, x будет сходиться к сумме их постоянных членов c i ; в отличие от устойчивого случая, это сходящееся значение зависит от начальных условий; разные отправные точки приводят к разным точкам в долгосрочной перспективе. Если какой-либо корень равен -1, его член будет способствовать постоянным колебаниям между двумя значениями. Если какой-либо из корней единичной величины является комплексным, то колебания x с постоянной амплитудой будут сохраняться.
Наконец, если какой-либо характеристический корень имеет величину больше 1, то x будет расходиться до бесконечности с течением времени или будет колебаться между все более большими положительными и отрицательными значениями.
Теорема Иссаи Шура утверждает, что все корни имеют величину меньше 1 (стабильный случай) тогда и только тогда, когда все определители определенной цепочки положительны. [2] : 247
Если неоднородное линейно-разностное уравнение было преобразовано к однородной форме, которая была проанализирована, как указано выше, то свойства устойчивости и цикличности исходного неоднородного уравнения будут такими же, как и у полученной однородной формы, со сходимостью в стабильный случай - это установившееся значение y * вместо 0.
См. также
[ редактировать ]- Рекуррентное отношение
- Линейное дифференциальное уравнение
- Теорема Скулема–Малера–Леха
- Школьная проблема
Ссылки
[ редактировать ]- ^ Чан, Альфа (1984). Фундаментальные методы математической экономики (Третье изд.). Нью-Йорк: МакГроу-Хилл. ISBN 0-07-010813-7 .
- ^ Перейти обратно: а б Баумол, Уильям (1970). Экономическая динамика (Третье изд.). Нью-Йорк: Макмиллан. ISBN 0-02-306660-1 .
- ^ Грин, Дэниел Х.; Кнут, Дональд Э. (1982), «2.1.1 Постоянные коэффициенты - A) Однородные уравнения», Математика для анализа алгоритмов (2-е изд.), Биркхойзер, стр. 17 .
- ^ Чан, Альфа К., Фундаментальные методы математической экономики , третье издание, McGraw-Hill, 1984.
- ^ Папаниколау, Василис, «Об асимптотической устойчивости класса линейных разностных уравнений», Mathematics Magazine 69 (1), февраль 1996 г., 34–43.
- ^ Заторский Роман; Гой, Тарас (2016). «Парапостоянство треугольных матриц и некоторые общие теоремы о числовых последовательностях» . Дж. Межд. Сек . 19 :16.2.2.