Найти положение равновесия рекуррентного уравнения

Рекуррентные соотношения и уравнения

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

Как решать рекуррентные соотношения?

Для решения рекуррентных соотношений применяют один из двух основных способов:

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

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

Метод производящих функций

Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен $k$) $$a_ <0>= …, \\ a_ <1>= …, \\ a_ = …, \\ … \\ a_ = …, n\geqslant k$$
Домножить каждую строчку на $z$ в соответствующей степени $z^ \cdot a_$ и сложить все выражения для $n \ge 0$. В левой части получится сумма $\displaystyle\sum_^ <\infty>a_nz^n$ — это производящая функция, назовем ее $G(z)$. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее $G(z)$.
Решить полученное уравнение относительно $G(z)$.
Разложить $G(z)$ в степенной ряд, тогда коэффициент при $z_n$ будет искомым выражением для $a_n$.

Метод характеристических функций

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

Записать соответствующее однородное рекуррентное уравнение (РУ): $$ p_ a_ + p_a_ + . + p_n a_n =f \to \\ \to p_ a_ + p_a_ + . + p_n a_n =0. $$
Выписать для него характеристическое уравнение и найти его корни $\lambda_i$ $$ p_ \lambda^ + p_\lambda^ + . + p_\lambda + p_n =0. $$
Выписать согласно полученным корням $\lambda_1, . \lambda_k$ общее решение однородного рекуррентного соотношения (подробнее теорию см. по ссылке [1] ниже). $$ C_1 \lambda_1^n +. +C_k \lambda_k^n \, \mbox < для случая различных простых корней>, $$ $$ C_1 \lambda_1^n + C_2 n\lambda_1^n +. +C_m n^m \lambda_1^n+. +C_k \lambda_k^n \mbox < для случая корня >\, \lambda_1 \, < кратности >\, m. $$
Подобрать частное решение неоднородного рекуррентного соотношения по виду правой части (особенно удобно для правых частей вида $\mu^n*P(n)$, $P(n)$ — многочлен от $n$).
Представить общее решение неоднородного РУ как сумму общего решения соответствующего однородного РУ и частного решения неоднородного РУ.
Подставить начальные условия $a_0, a_1, . a_$ и получить значения констант $C_1, . C_k$.

Решение для последовательности чисел Фибоначчи

Последовательность чисел Фибоначи — это последовательность, каждый элемент которой (кроме нулевого и первого) равен сумме двух предыдущих:

$$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 , . $$

Числа Фибоначчи растут быстро: $f_<10>=55$, $f_<20>=6765$, а $f_<100>=354224848179261915075$.

Общая формула данной рекуррентной последовательности имеет вид6

Способ 1. Производящяя функция

Начинаем с второго шага алгоритма, домножаем на $z^n$:

$$\begin 1\cdot f_0 &= &0\cdot 1,\\ z\cdot f_1 &= &1\cdot z,\\ z\cdot f_n & = &(f_+f_)\cdot z^n, \quad n\geq2.\\ \end $$

Складываем все строчки:

На третьем шаге алгоритма приводим все суммы к замкнутому виду:

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

Теперь разложим ее в степенной ряд. Для этого сначала разложим знаменатель на множители. Найдем корни уравнения:

Чтобы разложить данные дроби в ряды, используем известное разложение для дроби:

Рассмотрим первую дробь и поделим в ней числитель и знаменатель на $z_1$:

Аналогично (но с делением на $z_2$) действуем со второй дробью:

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

$$1/z_1=-z_2, \quad 1/z_2 = -z_1, \quad z_1-z_2=\sqrt <5>$$ $$f_n=\frac<1><\sqrt<5>>\left( \biggl( \frac<1+\sqrt<5>> <2>\biggr)^n — \biggl( \frac<1-\sqrt<5>> <2>\biggr)^n \right). $$

Способ 2. Характеристическое уравнение

Запишем характеристический многочлен для $f_n=f_+f_$, и найдем его корни:

Тогда общее решение однородного рекуррентного уравнения имеет вид:

Осталось найти значения произвольных постоянных $C_1, C_2$ из начальных условий $f_0=0, f_1=1$.

Решая систему, найдем

Итоговое выражение для последовательности чисел Фибоначчи:

Результаты обоих методов совпали, решение вторым методом оказалось проще и короче.

Примеры решений

Задача 1. Решить рекуррентное соотношение $f(n+2)=-6f(n+1)+7f(n)+n-3$ с начальными условиями $f(0)=2$ и $f(1)=4$, сделать проверку

Задача 2. Решить рекуррентное соотношение $f(n+2)=-2f(n+1)+3f(n)-3^n$ с начальными условиями $f(0)=1$, $f(1)=3$ и сделать проверку

Задача 3. 1. Решить рекуррентное соотношение $f(n+2) =-5f(n+1) -4f(n) + 3n^2$ с начальными условиями $f(0) = 2$, $f(1) = 3$.
2. Проверить, удовлетворяет ли найденное решение начальным условиям и обращает ли оно рекуррентное соотношение в справедливое тождество.

Задача 4. Найти последовательность $$, удовлетворяющую рекуррентному соотношению $a_ + 4 a_ + 3 a_ = 0$ и начальным условиям $a_1=2$, $a_2=4$.

Часть вторая. Разностные (рекуррентные) уравнения.

Под перестройкой понимается попытка «сверху» реформировать экономическую и политическую систему советского общества. Связана с именем её инициатора М.С.Горбачева Хронологические рамки перестройки охватывают 1985—1991 гг. Причины перестройки — ставшие очевидными к началу 80-х гг. отставание СССР от ведущих стран мира по темпам экономического развития и застойные явления в социально-политической и духовной сферах советского общества. Темпы экономического роста в СССР стали падать с середины 70-х гг. Общество все острее осознавало необходимость перемен. Уже при Ю.В.Андропове в 1982—1984 гг. была начата борьба с негативными явлениями в обществе — коррупцией, злоупотреблением властью, потерями рабочего времени. Была разработана программа экономических преобразований, однако смерть Андропова не позволила ее реализовать. Новым Генеральным секретарем ЦК КПСС стал М.С.Горбачев. Первыми шагами на пути политических преобразований стало омоложение кадров. Появились элементы демократии: альтернативные выборы партийного руководства, коллективизм в принятии решений. Был взят курс на строительство «социалистического правового государства». Был создан новый законодательный орган — Съезд народных депутатов СССР. Выборы стали проводиться на альтернативной основе. Была отменена статья Конституции о руководящей роли КПСС в обществе. Начался процесс легального формирования многопартийной системы в стране. Произошёл распад СССР. В экономике: расширение самостоятельности предприятий, постепенное возрождение частной собственности, кооперативное движение. Экономические реформы привели к резкому сокращению объёмов производства, росту инфляции, к резкому падению уровня жизни.

Для перестройки характерно развитие гласности, становление многопартийности, повышение роли церкви. Во внешней политике: нормализация отношений с Западом, вывод советских войск из Афганистана.

Содержание программы учебного курса

«Дифференциальные и разностные уравнения»

для направления 521600 — Экономика,

специальность 351400. (вторая ступень высшего профессионального образования).

I. Программа соответствует требованиям Государственного
образовательного стандарта по направлению 521600 —
Экономика, утвержденного Министерством образования РФ
25.03.2000 г., номер гос. регистрации 433 гумУбак.

II. Содержание программы.

Часть первая. Обыкновенные дифференциальные уравнения. Глава I. Дифференциальные уравнения первого порядка.

Понятие дифференциального уравнения первого порядка. Определение решения уравнения. Интегральная кривая. Дифференциальное уравнение, разрешенное относительно производной. Метод изоклин. Задача Коши. Уравнение, правая часть которого не содержит искомой функции. Общее решение, частное решение. Теорема существования и единственности решения задачи Коши. Особое решение. Уравнение в дифференциалах.

1. Романко В.К. Курс дифференциальных уравнений и вариационного исчисления.-М.-С.Пб.: Физматлит, 2001.

2. Бурмистрова Е.Б., Лобанов С.Г. Математический анализ и дифференциальны уравнения.-М.-Изд. центр «Академия», 2010.

3. Понтрягин Л.С. Обыкновенные дифференциальные уравнения. —
М. Наука, 1961.

Глава II. Некоторые дифференциальные уравнения первого порядка, интегрируемые в квадратурах.

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

1. Романко В.К. Курс дифференциальных уравнений и вариационного исчисления.-М.-С.Пб.: Физматлит, 2001.

3. Понтрягин Л.С. Обыкновенные дифференциальные уравнения. — М. :Наука, 1961.

4. Chiang Alpha С. Fundamental methods of mathematical economics/
Mc.Grow-Hill, 1984.

5. Смирнов А.Д. Лекции по макроэкономическому моделированию.-М. Изд-во ГУВШЭ, 2000.

6. Тарасевич Д.С., Гальперин В.М., Гребенников П.И., Леусский А.И.

7. Макроэкономика. Учебник. С.Пб.:Изд-во Санкт-Петербургского университета экономики и финансов.1999.

Глава III. Системы обыкновенных дифференциальных уравнений.

Нормальная система уравнений n -ого порядка, её решение, интегральная кривая. Фазовое пространство, точки равновесия. Задача Коши. Теорема существования и единственности решения задачи Коши.

Автономная система уравнений. Положение равновесия. Свойства фазовых и интегральных кривых автономной системы уравнений.

Система линейных уравнений с переменными коэффициентами.Теорема существования и единственности решения задачи Коши. Однородная система линейных уравнений. Линейное пространство ее решений. Фундаментальная система решений. Определитель Вронского. Формула Лиувилля-Остроградского. Система линейных неоднородных уравнений. Структура множества решений. Принцип суперпозиции. Метод вариации постоянных. Метод исключения

1. Романко В.К. Курс дифференциальных уравнений и вариационного исчисления. -М.-С.Пб.: Физматлит, 2001.

3. Понтрягин Л.С. Обыкновенные дифференциальные уравнения. -М. :Наука, 1961.

Глава IV. Уравнения n- ого порядка.

Понятие уравнения n -ого порядка. Решение уравнения, интегральная кривая. Некоторые уравнения допускающие понижение порядка. Уравнение n-ого порядка, разрешенное относительно старшей производной. Сведение его к системе уравнений. Задача Коши. Теорема существования и единственности решения задачи Коши. Линейные уравнения n -ого порядка с переменными коэффициентами. Теорема существования и единственности решения задачи Коши. Линейное однородное уравнение. Линейное пространство его решений. Фундаментальная система решений. Определитель Вронского. Формула Лиувилля-Остроградского. Линейное неоднородное уравнение n -ого порядка с переменными коэффициентами. Структура множества решений. Принцип суперпозиции. Метод вариации постоянных.

1. Романко В.К. Курс дифференциальных уравнений и вариационного исчисления.-М.-С.Пб.: Физматлит, 2001.

3. Боярчук А.К., Головач Г.П. Справочное пособие по высшей математике. Том З.Дифференциальныеуравнения в примерах и задачах. -М. : Изд-во «УРСС», 1998.

Глава V. Комплексные числа.

Определение. Модуль и аргумент комплексного числа. Тригонометрическая форма записи. Сложение, умножение и деление комплексных чисел. Формула Эйлера. Корни n-ой степени комплексного числа. Вещественные и комплексно сопряженные корни многочлена с вещественными коэффициентами. Теорема Гаусса

1. Бурмистрова Е.Б., Лобанов С.Г. Математический анализ и дифференциальны уравнения.-М.-Изд. центр «Академия», 2010.

Глава VI, Методы решения линейных дифференциальных уравнений и систем линейных уравнений с постоянными вещественными коэффици-ентами.

Построение фундаментальной системы решений линейного однородного уравнения n-ого порядка по корням характеристического уравнения (метод Эйлера). Построение частного решения линейного неоднородного уравнения в случае, когда правая часть является квазимногочленом.

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

1. Романко В.К. Курс дифференциальных уравнений ивариационного исчисления.-М.-С.Пб.: Физматлит, 2001.

2. Бурмистрова Е.Б., Лобанов С. Математический анализ и дифференциальны уравнения.-М.-Изд. центр «Академия», 2010.

3. Понтрягин Л.С. Обыкновенные дифференциальные уравнения. —
М. -.Наука, 1961.

Глава VII. Устойчивость решений дифференциальных уравнений.

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

1. Романко В.К. Курс дифференциальных уравнений и

вариационного исчисления.-М.-С.Пб.: Физматлит, 2001.

3. Понтрягин Л.С. Обыкновенные дифференциальные уравнения. —
М. :Наука, 1961.

4. Арнольд В.И. Обыкновенные дифференциальные уравнения. Учебное
пособие для вузов. -М.: Наука, 1984.

Часть вторая. Разностные (рекуррентные) уравнения.

Глава I. Разностные (рекуррентные) уравнения первого порядка.

Разностное уравнение n-ого порядка в нормальной форме. Определение решения уравнения. Задача Коши. Линейное уравнение первого порядка с переменными коэффициентами. Метод вариации постоянной. Примеры: арифметическая прогрессия, геометрическая прогрессия, рост вклада в банке (простые и сложные проценты).

2. Гельфонд В.И. Исчисление конечных разностей.-М.: ГИФМЛ, 1959.

3. Романко В.К. Разностные уравнения.-М.:Лаборатория базовых знаний, 2000.

Глава II. Линейные разностные (рекуррентные) уравнения и системы с постоянными вещественными коэффициентами.

Линейное однородное разностное уравнение n-ого порядка. Линейное пространство его решений. Фундаментальная система решений. Общее решение однородного уравнения. Построение фундаментальной системы решений линейного разностного уравнения с постоянными вещественными коэффициентами. Структура общего решения линейного неоднородного уравнения. Частное решение линейного уравнения с постоянными коэффициентами в случае, когда правая часть — квазимногочлен (резонансный и нерезонансный случаи).

Линейная однородная система разностных уравнений. Линейное пространство её решений. Фундаментальная система решений. Общее решение. Построение фундаментальной системы решений линейной однородной системы разностных уравнений с постоянными вещественными коэффициентами. Структура общего решения неоднородной системы линейных разностных уравнений. Решение систем методом исключения.

2. Гельфонд В.И. Исчисление конечных разно стей.-М.: ГИФМЛ, 1959.

3. Романко В.К. Разностные уравнения.-М.:Лаборатория базовых знаний, 2000.

Глава III. Устойчивость положения равновесия разностных уравнений и систем разностных уравнений.

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

1. Бурмистрова Е Б., Лобанов С.Г. Математический анализ и дифференциальны уравнения.-М.-Изд. центр «Академия», 2010.

2. Романко В.К. Разностные уравнения.-М.:Лаборатория базовых знаний, 2000.

3. Chiang Alpha С. Fundamental methods of mathematical economics. Mc.Grow-Hill, 1984.

4. Смирнов А.Д. Лекции по макроэкономическому моделированию . -М.:Изд-во ГУВШЭ, 2000.

Типовые вопросы и задачи для контрольных, зачетной и экзаменационной работ:

1.Решите задачу Коши и укажите промежуток наибольшей длины, на котором решение этой задачи определено.

2.Решите задачу Коши и вычислите для

решения этой задачи значение .

3.Найдите решение уравнения , удовлетворяющее условию . Вычислите для этого решения значение .

4.Вычислите действительную часть числа .

5.Найдите все решения уравнения .

6.Решите задачу Коши и вычислите для решения этой задачи значение .

7.Для последовательности , удовлетворяющей рекуррентному уравнению и условию , вычислите величину .

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

9.Решите систему уравнений

10.Решите неоднородную систему уравнений

и изобразите фазовый портрет однородной системы.

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

12.Укажите все возможные значения дроби для всех тех решений уравнения , для которых она определена.

13.Решите уравнение .

14.Решите уравнение .

15.Решите уравнение

16.Решите одну из систем уравнений

или

17.Решите уравнение .

18.Решите уравнение .

19.Решите задачу Коши .

20.Решите задачу Коши .

21.Решите уравнение .

22.Решите уравнение .

23.Решите уравнение .

24.Найдите положения равновесия системы уравнений

определите их характер и начертите фазовые траектории соответствующих линеаризованных систем .

Дата добавления: 2014-12-15 ; просмотров: 15 | Нарушение авторских прав

Дискретная математика — рекуррентное соотношение

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

Определение

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

Пример — ряд Фибоначчи — F n = F n − 1 + F n − 2 , Ханойская башня — F n = 2 F n − 1 + 1

Линейные рекуррентные отношения

Линейное рекуррентное уравнение степени k или порядка k — это рекуррентное уравнение в формате x n = A 1 x n − 1 + A 2 x n − 1 + A 3 x n − 1 + d o t s A k x n k ( A n — константа, а A k n e q 0 ) на последовательности чисел как полинома первой степени.

Вот некоторые примеры линейных рекуррентных уравнений —

Читайте также:

I ВВОДНАЯ ЧАСТЬ
I часть «Механика».
I часть. РОССИЯ
I. ВВОДНАЯ ЧАСТЬ
I. Вводная часть
I. ПАСПОРТНАЯ ЧАСТЬ
I. Паспортная часть.
I. Паспортная часть.
I. Паспортная часть.
I. Практическая часть.

Рецидив отношений	Начальные значения	Решения
F _n = F _n-1 + F _n-2	a ₁ = a ₂ = 1	Число Фибоначчи
F _n = F _n-1 + F _n-2	а ₁ = 1, а ₂ = 3	Номер Лукаса
F _n = F _n-2 + F _n-3	a ₁ = a ₂ = a ₃ = 1	Падовская последовательность
F _n = 2F _n-1 + F _n-2	a ₁ = 0, a ₂ = 1	Число Пелла

Как решить линейное рекуррентное соотношение

Предположим, что два упорядоченных линейных рекуррентных соотношения имеют вид — F n = A F n − 1 + B F n − 2 , где A и B — действительные числа.

Характеристическое уравнение для вышеуказанного рекуррентного соотношения —

x 2 − A x e − B = 0

Три случая могут возникнуть при поиске корней —

Случай 1 — Если это уравнение учитывается как ( x − x 1 ) ( x − x 1 ) = 0 и оно дает два различных реальных корня x 1 и x 2 , то F n = a x n 1 + b x n 2 является решение. [Здесь a и b являются константами]

Случай 2 — Если это уравнение вычисляется как ( x − x 1 ) 2 = 0 , и оно порождает один действительный корень x 1 , то решением является F n = a x n 1 + b n x n 1 .

Случай 3 — Если уравнение дает два различных комплексных корня, x 1 и x 2 в полярной форме x 1 = r a n g l e t h e t a и x 2 = r a n g l e ( − t h e t a ) , то F n = r n ( a c o s ( n t h e t a ) + b s i n ( n t h e t a ) ) является решением.

Решите рекуррентное соотношение F n = 5 F n − 1 − 6 F n − 2 , где F 0 = 1 и F 1 = 4 .

Характеристическое уравнение рекуррентного соотношения —

Итак, ( x − 3 ) ( x − 2 ) = 0

x 1 = 3 и x 2 = 2

Корни реальны и различны. Итак, это в форме дела 1

F n = a x n 1 + b x n 2

Здесь F n = a 3 n + b 2 n ( A s x 1 = 3 a n d x 2 = 2 )

1 = F 0 = a 3 0 + b 2 0 = a + b

4 = F 1 = a 3 1 + b 2 1 = 3 a + 2 b

Решая эти два уравнения, мы получаем a = 2 и b = − 1

Следовательно, окончательное решение —

$$ F_n = 2,3 ^ n + (-1). 2 ^ n = 2,3 ^ n — 2 ^ n $$

Решите рекуррентное соотношение — F n = 10 F n − 1 − 25 F n − 2 , где F 0 = 3 и F 1 = 17 .

Характеристическое уравнение рекуррентного соотношения —

x 2 − 10 x − 25 = 0

Итак, ( x − 5 ) 2 = 0

Следовательно, существует один действительный корень x 1 = 5

Поскольку существует единый действительный корень, он имеет вид случая 2

F n = a x n 1 + b n x n 1

3 = F 0 = a .5 0 + b .0 .5 0 = a

17 = F 1 = a .5 1 + b .1 .5 1 = 5 a + 5 b

Решая эти два уравнения, мы получаем a = 3 и b = 2 / 5

Следовательно, окончательное решение — F n = 3.5 n + ( 2 / 5 ) . n .2 n

Решите рекуррентное соотношение F n = 2 F n − 1 − 2 F n − 2 , где F 0 = 1 и F 1 = 3

Характеристическое уравнение рекуррентного соотношения —

источники:

http://lektsii.net/1-30527.html

http://coderlessons.com/tutorials/akademicheskii/diskretnaia-matematika/diskretnaia-matematika-rekurrentnoe-sootnoshenie