Метод рекуррентных соотношений

Линейные рекуррентные соотношения с постоянными коэффициентами. Основные определения и примеры рекуррентных соотношений Часто решение одной комбинаторной задачи удается свести к решению аналогичных задач меньшей размерности с помощью некоторого соотношения называемого рекуррентным от латинского слова recurrere – возвращаться. Тем самым решение сложной задачи можно получить последовательно находя решение более легких задач и далее пересчитывая по рекуррентным соотношениям находить решение трудной задачи. Рекуррентным соотношением го...

2015-01-30

146.69 KB

54 чел.


Поделитесь работой в социальных сетях

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


аранов Виктор Павлович. Дискретная математика. Раздел 2. Элементы комбинаторики.

Лекция 5. Метод рекуррентных соотношений

Лекции 5. МЕТОД РЕКУРРЕНТНЫХ СООТНОШЕНИЙ

План лекции:

  1.  Основные определения и примеры рекуррентных соотношений.
  2.  Линейные рекуррентные соотношения с постоянными коэффициентами. Формула

Бине.

  1.  Основные определения и примеры рекуррентных соотношений

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

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

                             (1)

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

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

                                                        (2)

общим решением будет

.                                                         (3)

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

Так как эта система имеет решение при любых значениях  и , то решение (3) действительно является общим решением соотношения (2).

Пример 1. Числа Фибоначчи. В 1202 г. знаменитым итальянским математиком Леонардо Пизанским, который известен больше по своему прозвищу Фибоначчи (Fibonacci – сокращенное filius Bonacci, т. е. сын Боначчи), была написана книга «Liber abacci» («Книга об абаке»). До нас эта книга дошла во втором своем варианте, который относится к 1228 г. Рассмотрим одну из множества приведенных в этой книге задач.

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

Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары. A еще через месяц приплод дадут и исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов и т. д.

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

.                                                          (4)

Так как , то последовательно находим: и т. д. Эти числа составляют последовательность

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,…,

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

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

Будем называть такие слова правильными и обозначим их число через . Разобьем множество этих правильных слов на два класса: слова, оканчивающиеся на ноль, и слова, оканчивающиеся на единицу. Обозначим количество слов в этих классах  и  соответственно. По правилу сложения

                                                          (5)

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

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

.                                                           (6)

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

Таблица 1

1

2

3

4

5

6

7

8

9

10

2

3

5

8

13

21

34

55

89

144

Первые два значения находятся непосредственно ( – слова 0 и 1;  – слова 000, 010, 101), а остальные – по формуле (6).

Пример 2. Задача о расстановке скобок в выражении с неассоциативной бинарной операцией. Пусть “” обозначает некоторую бинарную операцию. Рассмотрим выражение , в котором символ  обозначает некоторую бинарную неассоциативную операцию. Сколько имеется различных способов расстановки скобок в этом выражении?

Как пример неассоциативной операции можно привести векторное произведение. Другой пример – обычное сложение и умножение, выполняемое на компьютере. В силу того, что представление каждого числа в памяти компьютера ограничено определенным количеством разрядов, при выполнении каждой операции возникает погрешность и суммарный результат этих погрешностей зависит от расстановки скобок. Пусть  – машинный ноль. Это означает, что . Тогда , в то время как .

Обозначим число всевозможных способов расстановки скобок через . Тогда

;

.

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

                                               (7)

где .

По определению количество способов расстановки скобок для вычисления первых  операндов равно , последних – . По правилу произведения число расстановок скобок для выражения (4) равно . По правилу сложения

,                                              (8)

Например, .

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

Пусть функция  в соотношении (1) является линейной

, ,                   (9)

где  – некоторые числа. Такие соотношения называют линейными соотношениями -го порядка с постоянными коэффициентами.

Сначала исследуем подробно соотношения второго порядка, а затем перейдем к общему случаю. При  из формулы (9) получим

, .                                        (10)

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

Лемма 1. Пусть  – решение соотношения (10), а  – любое число. Тогда последовательность  также является решением этого соотношения.

Лемма 2. Пусть  и  – решения соотношения (10). Тогда последовательность  также является решением этого соотношения.

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

Лемма 3. Размерность пространства решений рекуррентного соотношения (10) равна двум.

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

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

,                                                               (11)

где  – константа.

Если , то из (11) имеем

                                                           ,                                                               (12)

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

Будем искать решение рекуррентного соотношения второго порядка также в виде (12). Тогда, подставляя (12) в (9), получим

.                                                      (13)

При =0 имеем нулевое решение, которое не представляет интереса. Считая , поделим последнее соотношение на :

                                                          (14)

Таким образом, геометрическая прогрессия (12) является решением рекуррентного соотношения (10), если знаменатель прогрессии  является корнем квадратного уравнения (14). Это уравнение называется характеристическим уравнением для рекуррентного соотношения (9).

Построение базисных решений зависит от корней  и  характеристического уравнения (14).

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

                                                       (15)

путем соответствующего выбора констант можно получить любое решение соотношения (10). Рассмотрим произвольное решение . Выберем константы  и  так, чтобы  при  и :

                                                        (16)

Определитель линейной системы (16)

следовательно, система имеет единственное решение, а значит формула (15) – общее решения соотношения (10).

  1.   . В случае кратных корней характеристическое уравнение (13) имеет вид  или . Тогда , , а для соотношения (10) получим уравнение , которое дает два базисных решения  и . Общее решение представляется в виде

.                                                         (17)

В случае соотношения -го порядка (9) имеют место утверждения, аналогичные тем, которые были рассмотрены для уравнений 2-го порядка.

  1.   Совокупность всех решений уравнения (9) является подпространством в пространстве всех последовательностей.
  2.   Размерность этого пространства равна , то есть каждое решение однозначно определяется своими первыми  значениями.
  3.   Для определения базиса подпространства решений составляется характеристическое уравнение

.                                            (18)

Многочлен

                                      (19)

называется характеристическим многочленом рекуррентного соотношения (9).

  1.   Если характеристическое уравнение имеет  различных корней , то общее решение рекуррентного соотношения (9) имеет вид

.                                            (20)

При заданных начальных значениях решения , , константы  находятся из системы

  1.   Если  – корень характеристического уравнения кратности , то соотношение (9) имеет следующие решения

.

Пусть характеристическое уравнение (18) имеет корни: , ,…,  кратности соответственно , ,…, , причем . Тогда характеристический многочлен и общее решение соотношения (9) представятся в виде

,

.

Пример 3. Формула Бине. Поставим задачу получить формулу в явном виде для чисел Фибоначчи. Для этого найдем решение рекуррентного соотношения (4) при условии, что . Составим характеристическое уравнение , найдем его корни  и получим общее решение . Константы  и  определим из начальных условий: . Тогда  или

,                                (21)

где  – золотое сечение. Формула (21) называется формулой Бине. При этом . Из формулы Бине следует, что .



 

Другие похожие работы, которые могут вас заинтересовать.
3792. Рациональность соотношений в активе предприятия 113.83 KB
  Бухгалтерский баланс — основная форма бухгалтерской отчетности. Он характеризует имущественное и финансовое состояние организации на отчетную дату. В балансе отражаются остатки по всем счетам бухгалтерского учета на отчетную дату. Эти показатели приводятся в бухгалтерском балансе в определенной группировке.
8407. Константный метод 17.82 KB
  Говорят, что метод объекта обладает свойством неизменности (константности), если после его выполнения состояние объекта не изменяется.Если не контролировать свойство неизменности, то его обеспечение будет целиком зависеть от квалификации программиста. Если же неизменный метод в процессе выполнения будет производить посторонние эффекты, то результат может быть самым неожиданным,отлаживать и поддерживать такой код очень тяжело.
13457. Метод фазовой плоскости 892.42 KB
  Метод фазовой плоскости впервые был применен для исследования нелинейных систем французским ученым Анри Пуанкаре. Основное преимущество этого метода – точность и наглядность анализа движений нелинейной системы. Метод является качественным
2243. МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ 113.98 KB
  Идея метода возможных направлений МВН заключается в том что в каждой очередной точке находится направление спуска такое что перемещение точки по этому направлению на некоторое расстояние не приводит к нарушению ограничений задачи. Направление определяемое вектором называется возможным направлением в точке если достаточно малое перемещение из в направлении не выводит точку за пределы допустимой области т. Очевидно если является внутренней точкой множества то любое направление в этой точке является возможным. Возможное...
12947. МЕТОД ГАРМОНИЧЕСКОЙ ЛИНЕАРИЗАЦИИ 338.05 KB
  Переходя непосредственно к рассмотрению метода гармонической линеаризации будем считать что исследуемая нелинейная система приведена к виду показанному на. Нелинейный элемент может иметь любую характеристику лишь бы она была интегрируемой без разрывов второго рода. Преобразование данной переменной для примера нелинейным элементом с зоной нечувствительности показано на рис.
2248. Графический метод решения ЗЛП 219.13 KB
  Точки лежащие внутри и на границе этой области являются допустимыми планами. А именно все точки отрезка АВ являются оптимальными планами задачи на которых достигается максимальное значение линейной формы. Метод последовательного улучшения плана Метод основан на упорядоченном переборе угловых точек множества планов задачи в сторону увеличения или уменьшения линейной формы и содержит три существенных момента. Вопервых указывается способ вычисления опорного плана.
7113. Метод гармонической линеаризации 536.48 KB
  Метод гармонической линеаризации Поскольку этот метод является приближённым то полученные результаты будут близки к истине только при выполнении определённых допущений: Нелинейная система должна содержать только одну нелинейность; Линейная часть системы должна представлять собой фильтр низких частот ослабляющий высшие гармоники возникающие в предельном цикле; Метод применим только к автономным системам. Изучается свободное движение системы то есть движение при ненулевых начальных условиях в отсутствие внешних воздействий....
10649. Индексный метод анализа 121.13 KB
  Индивидуальные индексы. Общие агрегатные индексы. Средние преобразованные индексы. Индексы переменного и постоянного состава индексы структурных сдвигов.
12914. Метод наименьших квадратов 308.27 KB
  Пусть из теоретических соображений мы знаем что . Поэтому можно сказать что наша задача состоит и в том чтобы провести прямую наилучшим образом. Будем считать что вся ошибка заключена в . Будем подбирать искомые коэффициенты из соображений чтобы случайная добавка была наименьшей.
9514. Метод бухгалтерського обліку 1002.23 KB
  Бухгалтерські рахунки та їх побудова. Він складається з ряду елементів головні з яких: документація; інвентаризація; рахунки; подвійний запис; оцінка; калькуляція; баланс; звітність. Рахунки бухгалтерські призначені для обліку наявності активів і пасивів. Бухгалтерські рахунки та їх побудова.
© "REFLEADER" http://refleader.ru/
Все права на сайт и размещенные работы
защищены законом об авторском праве.