Jump to content

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

В математике (включая комбинаторику , линейную алгебру и динамические системы ) линейная рекуррентность с постоянными коэффициентами [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 повторяемость есть решение с и наиболее общее решение с . Характеристический многочлен, равный нулю ( характеристическое уравнение ), представляет собой просто .

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

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

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

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

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

а если они идентичны (когда ), у нас есть

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

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

можно переписать как [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.

См. также

[ редактировать ]
  1. ^ Чан, Альфа (1984). Фундаментальные методы математической экономики (Третье изд.). Нью-Йорк: МакГроу-Хилл. ISBN  0-07-010813-7 .
  2. ^ Перейти обратно: а б Баумол, Уильям (1970). Экономическая динамика (Третье изд.). Нью-Йорк: Макмиллан. ISBN  0-02-306660-1 .
  3. ^ Грин, Дэниел Х.; Кнут, Дональд Э. (1982), «2.1.1 Постоянные коэффициенты - A) Однородные уравнения», Математика для анализа алгоритмов (2-е изд.), Биркхойзер, стр. 17 .
  4. ^ Чан, Альфа К., Фундаментальные методы математической экономики , третье издание, McGraw-Hill, 1984.
  5. ^ Папаниколау, Василис, «Об асимптотической устойчивости класса линейных разностных уравнений», Mathematics Magazine 69 (1), февраль 1996 г., 34–43.
  6. ^ Заторский Роман; Гой, Тарас (2016). «Парапостоянство треугольных матриц и некоторые общие теоремы о числовых последовательностях» . Дж. Межд. Сек . 19 :16.2.2.
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 2d0624bad8e473ec10105b1410161465__1715882280
URL1:https://arc.ask3.ru/arc/aa/2d/65/2d0624bad8e473ec10105b1410161465.html
Заголовок, (Title) документа по адресу, URL1:
Linear recurrence with constant coefficients - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)