Рекуррентное соотношение примеры. Метод рекуррентных соотношений

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

1. Формула
задает арифметическую прогрессию.

2. Формула
определяет геометрическую прогрессию.

3. Формула
задает последовательность чисел Фибоначчи .

В случае, когда рекуррентное соотношение линейно и однородно, т. е. выполняется соотношение вида

(p =const), последовательность
называется возвратной . Многочлен

называется характеристическим для возвратной последовательности
. Корни многочлена
называются характеристическими .

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

Описание общего уравнения соотношения (1) имеет аналоги с описанием решения обыкновенного дифференциального уравнения с постоянными коэффициентами.

Теорема 1. 1. Пусть - корень характеристического многочлена (2). Тогда последовательность
, где c – произвольная константа, удовлетворяет соотношению (1).

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

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

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

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

Корням характеристического многочлена
являются числа
. Следовательно, по теореме 3.1. общее решение имеет вид
. Используя начальные условия, получаем систему

решая которую, находим
и
. Таким образом,
.

Рассмотрим неоднородное линейное рекуррентное уравнение

Пусть
- общее решение однородного уравнения (1), а
- частное (конкретное) решение неоднородного уравнения (3). Тогда последовательность
образует общее решение уравнения (3), и тем самым справедлива.

Теорема 2. Общее решение неоднородного линейного рекуррентного уравнения представляется в виде суммы общего решения соответствующего однородного линейного рекуррентного уравнения и некоторого частного решения неоднородного уравнения.

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

В отдельных случаях имеются общие рецепты нахождения общего решения.

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

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

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

Пример. Найти решение уравнения

(4)

с начальным условием
.

Рассмотрим характеристический многочлен
. Так как
и правая часть
уравнения (3) равна n +1, то частное решение будем искать в виде
. Подставляя в уравнение (4), получаем . Приравнивая коэффициенты в левой и правой частях последнего равенства, получаем систему

откуда находим
. Таким образом, частное решение уравнения (4) имеет вид
. По теореме 3.1. общее решение однородного уравнения
задается формулой
, и по теореме 3.2. получаем общее решение уравнения (4):
. Из начального условия
находим
, т. е. . Таким образом,
.

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

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

Отсюда видно, что всегда может быть сведён к факториалу от меньшего числа.

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

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

Обозначим через количество пар кроликов по истечении месяцев с начала года. Тогда через месяц количество пар кроликов можно найти по формуле:

Эта зависимость называется рекуррентным соотношением . Слово «рекурсия» означает возврат назад (в нашем случае – возврат к предыдущим результатам).

По условию, и , тогда по соотношению имеем: , , и т.д., .

Определение 1: Числа называются числами Фибоначчи . Это – известная в математике последовательность чисел:

1, 1, 2, 3, 5, 8, 13, 21, ...

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

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

Возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: единицам соответствуют месяцы появления на свет одной из пар «предков» данной пары (включая и исходную), а нулями – все остальные месяцы. Например, последовательность устанавливает такую «генеалогию» – сама пара появилась в конце 11-го месяца, ее родители в конце 7-го месяца, «дед» – в конце 5-го месяца, и «прадед» в конце 2-го месяца. Первоначальная пара шифруется последовательностью . Ни в одной последовательности две единицы не могут стоять подряд – только что появившаяся пара не может принести приплод через месяц. Очевидно, различным последовательностям отвечают различные пары и обратно.

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

Теорема 1: Число находится как сумма биномиальных коэффициентов:. Если – нечетно, то . Если – четно, то . Иначе: – целая часть числа .

Доказательство: В самом деле, - число всех последовательностей из 0 и 1, в которых никакие две единицы не стоят рядом. Число таких последовательностей, содержащих ровно единиц и нулей, равно , при этом , тогда изменяется от 0 до . Применяя правило суммы, получаем данную сумму.

Это равенство можно доказать иначе. Обозначим:

Из равенства , следует, что . Кроме этого, ясно, что и . Так как обе последовательности и удовлетворяют рекуррентному соотношению , то , и .

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

Например, – рекуррентное соотношение второго порядка, а рекуррентное соотношение 3-го порядка. Соотношение Фибоначчи является соотношением второго порядка.

Определение 3:Решением рекуррентного соотношения является последовательность, удовлетворяющая этому соотношению.

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

Например, соотношению Фибоначчи кроме рассмотренной выше последовательности 1, 1, 2, 3, 5, 8, 13, 21, ..., могут удовлетворять также и другие последовательности. К примеру, последовательность 2, 2, 4, 8, 12,... строится по тому же принципу. Но если задать начальные члены (их в последовательности Фибоначчи - 2), то решение определяется однозначно. Начальных членов берут столько, каков порядок соотношения.

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

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

Например, последовательность является одним из решений соотношения: . Это легко проверить обычной подстановкой.

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

Например, для соотношения общим решение будет .

В самом деле, легко проверяется, что оно будет решением нашего соотношения. Покажем, что любое решение можно получить в таком виде. Пусть и – произвольны.

Тогда найдутся такие и , что

Очевидно, для любых , система уравнений имеет единственное решение.

Определение 5: Рекуррентное соотношение называется линейным , если оно записывается в виде:

где - числовые коэффициенты.

Для решения произвольных рекуррентных соотношений общих правил, вообще говоря, нет. Однако для решения линейных рекуррентных соотношений есть общие правила решения.

Рассмотрим сначала соотношение 2-го порядка .

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

Теорема 2: Если и - являются решением данного рекуррентного соотношения 2-го порядка, то для любых чисел и последовательность также является решением этого соотношения.

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

Из теорем 2, 3 вытекает следующее правило решения линейных рекуррентных соотношений 2-го порядка.

Пусть дано рекуррентное соотношение .

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

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

а) Если это соотношение имеет два различных корня и , то общее решение соотношения имеет вид .

Действительно, из теорем 2, 3 следует, что - решение и система уравнений

Имеет единое решение, т.к. при условии .

Например, для чисел Фибоначчи, имеем . Характеристическое уравнение имеет вид: . Решая последнее уравнение, получим корни:, .

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

Если же, например, , то этому корню соответствуют решения:

данного рекуррентного соотношения. В общем решении этому корню соответствует часть .

Например , решая рекуррентное соотношение:

составляем характеристическое уравнение вида: .

Его корни , . Поэтому общее решение есть.

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

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

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

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

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

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

План лекции:

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

Бине.

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

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

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

(1)

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

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

(2)

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

. (3)

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

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

Пример 1 . Числа Фибоначчи. В 1202 г. знаменитым итальянским математиком Ле о нардо Пизанским, который известен больше по своему прозвищу Фибоначчи ( Fib o nacci – сокращенное 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

Первые два значения находятся непосредственно (– слова 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
	Бухгалтерські рахунки та їх побудова. Він складається з ряду елементів головні з яких: документація; інвентаризація; рахунки; подвійний запис; оцінка; калькуляція; баланс; звітність. Рахунки бухгалтерські призначені для обліку наявності активів і пасивів. Бухгалтерські рахунки та їх побудова.

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

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

Пример 1¢. Последовательность a n =a 0 +nd a n =a n - 1 +d . Это - формула общего члена арифметической прогрессии с разностью d и с начальным членом прогрессии a 0 .

Пример 2¢. Последовательность b n =b 0 ×q n является общим решением соотношения b n =b n - 1 ×q . Это - формула общего члена геометрической прогрессии со знаменателем q ¹0 и с начальным членом прогрессии b 0 .

Пример 3¢. Так называемая формула Бине j n =является частным решением соотношения j n =j n - 2 +j n - 1 при j 0 =j 1 =1.

Так как простые корни x 1 ,…,x k попарно различные, то D¹0. Значит, система (5) имеет (единственное) решение.

Задача 1. Найти общий член геометрической прогрессии по формуле (4).

Решение b n =qb n - 1 имеет вид . Поэтому .

Задача 2. Найти общее решение соотношения Фибоначчи a n + 2 =a n +a n + 1 .

Решение . Характеристический многочлен рекуррентного соотношения a n + 2 =a n +a n + 1 имеет вид . Поэтому .

Приведем без доказательства следующее обобщение теоремы 1.

Теорема 2 . Пусть характеристический многочлен однородного линейного рекуррентного соотношения (3) имеет k корней: a 1 кратности , …, a k кратности , , . Тогда общее решение рекуррентного соотношения (3) имеет следующий вид:

Задача 3. Найти общее решение соотношения .

Решение. Характеристический многочлен имеет корень 2 кратности 3. Поэтому .

Замечание . Общее решение неоднородного линейного соотношения (2) можно найти как сумму общего решения однородного линейного соотношения (3) и частного решения неоднородного линейного соотношения (2).

4. Производящие функции. Формальный ряд a 0 +a 1 x +a 2 x 2 +…+a k x k +… называется производящей функцией последовательности a 0 ,a 1 ,a 2 ,…,a k ,…

Производящая функция является или сходящимся рядом, или расходящимся рядом. Два расходящихся ряда могут быть равны как функции, но быть производящимися функциями различных последовательностей. Например, ряды 1+2x +2 2 x 2 +…+2 k x k +… и 1+3x +3 2 x 2 +…+3 k x k +… определяют одну и ту же функцию (равную 1 в точке x =1, неопределенную в точках x >1), но являются производящими функциями различных последовательностей.

Свойства производящих функций последовательностей:

сумма (разность) производящих функций последовательностей a n и b n равна производящей функции сумме (разности) последовательностей a n +b n ;

произведение производящих функций последовательностей a n и b n является производящей функцией свёртки последовательностей a n и b n :

c n =a 0 b n +a 1 b n - 1 +…+a n - 1 b 1 +a n b 0 .

Пример 1. Функция является производящей для последовательности

Пример 2. Функция является производящей для последовательности 1, 1, 1, …

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

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

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

ее логарифм. Последний всегда можно представить в виде

Логарифм функции правдоподобия для совокупности данных наблю­дения без последнего значения, а

Логарифм условной плотности вероятности значения при заданных значениях и .

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

которое отличается от (7.1.6) только введением индекса п у логарифма функции правдоподобия.

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

Уравнение (7.5.19) можно переписать с учетом (7.5.16) в следующем виде:

Разложим левую часть (7.5.20) в ряд Тейлора в окрестности точки . При этом

(7.5.22)

Вектор градиента функции в точке ; слагаемое обращается в нуль благодаря тому, что , является решением уравнения правдоподобия для предыдущего (п - 1)-го шага:

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

где - матрица, обратная .

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

По форме соотношение (7.5.24) очень похоже на (7.5.8), реализую­щее итеративный способ вычисления оценки максимального правдоподо­бия по методу Ньютона. Однако на самом деле они существенно отли­чаются друг от друга. В (7.5.8) поправка к предыдущему значению оцен­ки определяется величиной градиента логарифма всей функции правдо­подобия, который всегда зависит от всех имеющихся данных наблюде­ния , что требует запоминания всей этой совокупности. В соответствии с (7.5.24) поправка к определяется величиной гра­диента , который благодаря свойствам условной плотности вероятностифактически зависит только от тех значений (), которые находятся в сильной статистической связи с х n . Это различие является следствием специального выбора предыдущего приближения как оценки максимального правдоподобия, найденной по уменьшенной на одно значение совокупности данных наблюдения , и особенно ярко проявляется при независимых значениях (). В этом последнем случае

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

Аналогично, в случае марковской последовательности данных на­блюдения, то есть при

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

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

Первый из них основан на более последовательном использовании основного предположения о малом различии двух очередных значений оценки и , которое является основой для получения рекур­рентного соотношения (7.5.24). Это позволяет получить аналогичное ре­куррентное соотношение для весовой матрицы .Действительно, используя малость из (7.5.23), имеем

Введя обозначение

из (7.5.24) и (7.5.25) получим систему рекуррентных соотношений для вектора и весовой матрицы

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

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

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

где аналогично (7.5.26)

Заменяя в (7.5.24) матрицу матрицей , получаем ре­куррентное соотношение

для приближенного вычисления оценок максимального правдоподобия, предложенное Сакрисоном (в оригинале для независимых одина­ково распределенных , когда и . Это рекуррентное соотношение проще системы (7.5.27), поскольку оптимальная весовая матрица заменена ее мате­матическим ожиданием, и для ее нахождения не требуются имеющиеся данные наблюдения, кроме тех, которые сконцентрированы в значении оценки . В то же время очевидно, что подобная замена означает необходимость выполнения дополнительного по сравнению с (7.5.27) требования близости матрицы вторых производных к своему математи­ческому ожиданию.

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

Математическое ожидание матрицы (информационная матри­ца Фишера для одного наблюдения ), взятое в точке . Эта система отличается от (7.5.27) тем, что во втором из рекуррентных соот­ношений (7.5.31) не участвуют непосредственно данные наблюдения .

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

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

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

Стоит отметить, что любые итерационные или рекуррентные про­цедуры нахождения оценок максимального правдоподобия в общем случае являются приближенными. Поэтому, вообще говоря, для оценок, получающихся в результате применения этих процедур, состоятельность, асимптотическую эффективность и асимптотическую нормальность нуж­но доказывать заново. Для итеративных процедур необходимые свой­ства оценок гарантируются тем, что в принципе такие процедуры при соответствующем числе итераций дают решение уравнения правдоподо­бия с любой наперед заданной точностью. Для рекуррентных процедур типа (7.5.27), (7.5.30), (7.5.31) и других имеются специальные доказа­тельства. При этом, помимо требования регулярности, предъявляются некоторые дополнительные требования:

На поведение функции (7.2.2) при различных значениях ||, для достижения с помощью рекуррентной процедуры глобаль­ного максимума этой функции в точке , соответствующей истинно­му значению параметра;

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

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

является оценкой максимального правдоподобия и может быть пред­ставлена в рекуррентном виде:

что является самым простым частным случаем (7.5.30) при

Другой пример - это нерегулярная оценка максимального правдо­подобия для параметра - ширины прямоугольного распределения – из (7.4.2), которая также может быть определена рекуррентным соот­ношением

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

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

7.5.3. Переход к непрерывному времени. Дифференциальные уравнения для оценок максимального правдоподобия

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

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

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

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

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

Пусть - оценка максимального правдоподобия параметра , построенная по реализации процесса на интервале ,то есть решение уравнения максимального правдоподобия

Дифференцируя левую часть этого уравнения по времени, получаем

Вводя обозначения

и решая уравнение (7.5.42) относительно , получаем диффе­ренциальное уравнение для оценки максимального правдоподобия

Матрица , в свою очередь, согласно (7.5.37) определяется диффе­ренциальным уравнением

Так же, как в дискретном случае, матрица в (7.5.45), (7.5.47) мо­жет быть заменена своим математическим ожиданием - информационной матрицей Фишера при значении , а диф­ференциальное уравнение (7.5.46) для весовой матрицы - урав­нением

где аналогично дискретному случаю

Математическое ожидание матрицы вторых производных .

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

Вводя обозначение

, где I

и дифференцируя по времени соотношение , где I - единич­ная матрица, получаем с помощью (7.5.46) дифференциальное уравне­ние, определяющее непосредственно матрицу :

(и аналогично при замене на ), которое совместно с уравнением (7.5.45)

определяет оценку , не требуя обращения матриц. При этом имеет место переход от простейшего линейного дифференциального уравнения (7.5.46) к нелинейному относительно дифференциальному уравне­нию (7.5.51) типа Риккати.