Рекуррентные методы. Общие и частные решения рекуррентных соотношений Метод рекуррентных соотношений матрицы и характеристическое уравнение

В математике весьма часто употребляют такие термины как «рекурсивные функции», «рекуррентные последовательности», «рекуррентные соотношения», «рекурсивные алгоритмы». Все эти термины имеют один корень, происходящий от латинского слова гесиггеге - возвращаться. Общим для рекурсивных функций, рекурсивных алгоритмов и рекуррентных последовательностей является то, что для вычисления очередного значения функции, получения очередной реализации алгоритма, определения очередного члена последовательности необходимо обращаться к предшествующим их значениям, вычисленным раньше. В свою очередь, вычисление предшествующих значений требует обращения к вычисленным перед этим требуемым значениям и т.д. Таким образом, для того чтобы получить значение функции, реализацию алгоритма или значение члена ряда на п-м шаге необходимо знать их значения на (п - 1)-м шаге, а следовательно, на первом шаге. Правило, которое определяет способ вычисления очередного значения функции или очередного члена последовательности, с учетом того, что эти значения известны для первого шага, называется рекуррентным соотношением. Разработка рекуррентных соотношений - это один из методов решения различных задач. В комбинаторике этот метод применяется весьма широко.

Простейшим примером рекуррентного соотношения являются формулы для вычисления числа перестановок «-элементного множества. Эти формулы имеют вид Р х = 1, Р п = Р п _ х п и могут быть получены следующим образом.

Пусть имеется п элементов /, / 2 , ..., /„, множества I. Лю

бую перестановку этих элементов можно получить так: взять некоторую перестановку элементов /, / 2 , ..., и всеми возможными способами между указанными элементами, включая начало и конец, поставить элемент / и. Ясно, что таких способов будет п. Вследствие ЭТОГО ИЗ перестановки /, / 2 , ..., / д _, будет получено п перестановок. Это означает, что перестановок из п элементов в п раз больше, чем перестановок из п -1 элементов множества I. Тем самым установлено рекуррентное соотношение Р п = Р п _ х п. Пользуясь этим соотношением, последовательно получаем Р п -пР п _ х =п(п-)Р п _ 2 - п{п - ){п -2)...2Р Х. Но Р х - 1, поскольку из одного элемента можно сделать лишь одну перестановку. Поэтому Р п = п(п -1)(« - 2)___2-1 = п. На основании изложенного

правомерна и такая запись: Р п = (п -1)!«, 1! = 1.

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

Из условия задачи следует, что через месяц будет две пары кроликов (приплод принесет первая пара кроликов). Через два месяца - три пары, а через три месяца - пять пар, так как даст приплод еще та пара, которая появилась после первого месяца.

Обозначим через /„ количество пар кроликов по истечении п месяцев с начала года. Тогда в начале года / 0 = 1, через месяц /, = 2, через два месяца / 2 = / 0 + /, = 3, через три месяца / 3 = = / 2 + /1 =5. Поэтому в общем случае для вычисления числа кроликов в конце любого месяца получаем рекуррентное соотношение /„ = + / я _ 2 . Это соотношение дает возможность

вычислить количество пар кроликов в конце года по выражению /12 = /п + /ю П Р И условии, что / 0 = 1, /, = 2. Оно равно 377. Числа, которые получаются в результате применения приведенного рекуррентного соотношения, т.е. последовательность 1, 2, 3, 5, 8, 13, ... называются числами Фибоначчи. Примечательно, что при помощи рекуррентного соотношения, описывающего этой числовой ряд, решаются многие задачи комбинаторики. Вот одна из них.

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

/я = /«-1 +/я- 2-

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

Пусть число последовательностей длиной п +1, в которых две единицы не стоят рядом и которые оканчиваются на нуль, равно g n . Возьмем теперь последовательность ДЛИНОЙ /7 + 1, в которой две единицы не стоят рядом и которая оканчивается на единицу. Так как две единицы не стоят рядом, перед последней единицей последовательности стоит нуль, т.е. последовательность оканчивается на 01. Отбрасывая эти цифры, получим последовательность длиной п - 1, в которой две единицы не стоят подряд. Число таких последовательностей g n _^. Так как каждая последовательность длиной п + 1, в которой две единицы не стоят подряд оканчивается на единицу или нуль, для общего числа таких последовательностей по правилу суммы получаем g n+ ^ - g n + g n _ x . При этом для последовательностей длиной п = 1 существует две последовательности: 0 и 1, в которых две единицы не стоят рядом, вследст-

вие чего g l - 2. Для последовательностей длиной п - 2 существует три последовательности, в которых две единицы не стоят рядом: 00, 01 и 10. Поэтому = 3. Таким образом, рекуррентное соотношение g n+l = g n + g n _ { , g^ = 2, g 2 =3 эквивалентно рекуррентному соотношению / я+1 = /„ + /, =2, / 2 = 3, описывающему ряд

Фибоначчи. Следовательно, для любого /7 = 1,2, ..., используя это соотношение, можно решить сформулированную выше задачу.

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

Рекуррентное соотношение имеет порядок k , если оно позволяет выразить f(n+k) через f(n), f(n+1), …, f(n+k-1).

Пример.

f(n+2)=f(n)f(n+1)-3f 2 (n+1)+1 – рекуррентное соотношение второго порядка.

f(n+3)=6f(n)f(n+2)+f(n+1) – рекуррентное соотношение третьего порядка.

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

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

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

Пример . Последовательность 2, 4, 8, …, 2 n является решением для соотношения f(n+2)=3∙f(n+1) – 2∙f(n).

Доказательство . Общий член последовательности имеет вид f(n)=2 n . Значит, f(n+2)= 2 n+2, f(n+1)= 2n+1 . При любом n имеет место тождество 2 n+2 =3∙2 n+1 – 2∙2 n . Следовательно, при подстановке последовательности 2 n в формулу f(n+2)=3f(n+1) – 2f(n) соотношение выполняется тождественно. Значит, 2 n является решением указанного соотношения.

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

Пример . Дано рекуррентное соотношение: f(n+2)=5f(n+1)-6f(n). Докажем, что его общее решение имеет вид: f(n)= α 2 n + β3 n .

1. Сначала докажем, что последовательность f(n)=α 2 n + β3 n является решением рекуррентного соотношения. Подставим данную последовательность в рекуррентное соотношение.

f(n)= α 2 n + β 3 n , значит, f(n+1)= (α 2 n+1 + β 3 n +1), f(n+2)= α 2 n+2 + β 3 n +2 , тогда



5f(n+1)-6f(n)=5∙(α 2 n+1 + β 3 n +1)-6∙(α 2 n + β 3 n)= α (5 2 n+1 –6 2 n)+ β (5 3 n +1 –6 3 n)= =α2 n ∙(10–6)+ β 3 n ∙(15 – 6)= α 2 n+2 + β 3 n +2 = f(n+2).

Рекуррентное соотношение выполняется, следовательно, α 2 n + β 3 n является решением данного рекуррентного соотношения.

2. Докажем, что любое решение соотношения f(n+2)=5f(n+1)–6f(n) можно записать в виде f(n)= α 2 n + β 3 n . Но любое решение рекуррентного соотношения второго порядка однозначно определяется значениями первых двух членов последовательности. Поэтому достаточно показать, что для любых а=f(1) и b=f(2) найдутся α и β такие, что 2 α +3 β =а и 4 α +9 β =b. Легко видеть, что система уравнений имеет решение для любых значений а и b.

Таким образом, f(n)= α 2 n + β 3 n является общим решением рекуррентного соотношения f(n+2)=5f(n+1)–6f(n).

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

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

f(n+k)=c 1 f(n+k-1)+c 2 f(n+k-2)+…+c k f(n).

Найдем решение общего линейного рекуррентного соотношения с постоянными коэффициентами первого порядка.

Линейное рекуррентное соотношение с постоянными коэффициентами первого порядка имеет вид: f(n+1)=c f(n).

Пусть f(1)=а, тогда f(2)=c∙f(1)=c∙a, f(3)=c∙f(2)=c 2 ∙a, аналогично f(4)=c 3 ∙a и так далее, заметим, что f(n)=c n -1 ∙f(1).

Докажем, что последовательность c n -1 ∙f(1) является решением рекуррентного соотношения первого порядка. f(n)=c n -1 ∙f(1), значит, f(n+1)=c n f(1). Подставляя это выражение в соотношение, получим тождество c n f(1)=с∙ c n -1 ∙f(1).

Рассмотрим теперь подробнее линейные рекуррентные соотношения с постоянными коэффициентами второго порядка , то есть соотношения вида

f(n+2)=C 1 ∙f(n+1)+C 2 ∙f(n). (*).

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

Свойства решений :

1) Если последовательность x n является решением (*), то и последовательность a∙x n тоже является решением.

Доказательство.

x n является решением (*), следовательно, выполняется тождество x n +2 =C 1 x n +1 +C 2 x n . Домножим обе части равенства на a. Получим a∙x n +2 =a∙(С 1 ∙x n +1 +С 2 ∙x n)= С 1 ∙a∙x n +1 +С 2 ∙a∙x n . Это означает, что ax n является решением (*).

2) Если последовательности x n и y n являются решениями (*), то и последовательность x n +y n тоже является решением.

Доказательство.

x n и y n являются решениями, следовательно, выполняются следующие тождества:

x n +2 =C 1 x n +1 +C 2 x n .

y n +2 =C 1 y n +1 +C 2 y n .

Выполним почленное сложение двух равенств:

x n +2 +y n +2 =С 1 ∙x n +1 +С 2 ∙x n + С 1 ∙y n +1 +С 2 ∙y n = С 1 ∙(x n +1 + y n +1)+С 2 ∙(x n +y n). Это означает, что x n +y n является решением (*).

3) Если r 1 является решением квадратного уравнения r 2 =С 1 r+С 2 , то последовательность (r 1) n является решением для соотношения (*).

r 1 является решением квадратного уравнения r 2 =С 1 r+С 2 , значит, (r 1) 2 =C 1 r 1 +C 2 . Помножим обе части равенства на (r 1) n . Получим

r 1 2 r 1 n =(С 1 r 1 +С 2) r n .

r 1 n +2 =С 1 r 1 n +1 +С 2 r 1 n .

Это означает, что последовательность (r 1) n является решением (*).

Из этих свойств вытекает способ решения линейных рекуррентных соотношений с постоянными коэффициентами второго порядка:

1. Составим характеристическое (квадратное) уравнение r 2 =С 1 r+С 2 . Найдём его корни r 1, r 2. Если корни различны, то общее решение имеет вид f(n)= ar 1 n +βr 2 n .

2. Найдём коэффициенты a и β. Пусть f(0)=a, f(1)=b. Система уравнений

имеет решение при любых а и b. Этими решениями являются

Задача. Найдем формулу для общего члена последовательности Фибоначчи.

Решение. Характеристическое уравнение имеет вид х 2 =х+1 или х 2 -х-1=0, его корнями являются числа , значит, общее решение имеет вид f(n)= . Как нетрудно видеть, из начальных условий f(0)=0, f(1)=1 вытекает, что a=-b=1/Ö5, и, следовательно, общее решение последовательности Фибоначчи имеет вид:

.

Что удивительно, это выражение при всех натуральных значениях n принимает целые значения.

Данный метод состоит в том, что решение комбинаторной задачи с n предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, называемого рекуррентным. Говорят, что последовательность элементов u0 , u1 , … un , … над полем комплексных чисел C удовлетворяет рекуррентному соотношению порядка k, если

где a1 , … , ak - коэффициенты из C. Соотношения такого типа естественным образом возникают при решении комбинаторных задач.

Пример. Пусть имеется последовательность позиций, занумерованных числами 1, 2, … , n, … и в начальный момент предмет находится в 1-ой позиции. За один ход предмет продвигается вперед на 1 и 2 позиции. Найти число способов попадания в n-ю позицию.

♦ Пусть un - интересующее нас число. Ясно, что u2 = 1, u3 = 2 . Далее, разобьем все способы попадания в позицию с номером n на два класса: те, при которых на последнем шаге предмет передвигается на 1 шаг и те, при которых он передвигается на 2 шага. Ясно, что в первом случае имеем un-1 вариантов, во втором un-2 вариантов. Следовательно, имеем

Многочлен P(x) называется характеристическим для линейного рекуррентного соотношения (2). Заметим, что всякая рекуррентная последовательность k-го порядка однозначно определяется заданием k ее первых членов.

Пусть λ - корень характеристического многочлена P(x).

Теорема 1. Последовательность u0 , u1 , … un , … , где un = cλ n , c - произвольная константа из C, удовлетворяет линейному рекуррентному соотношению (2).

♦ Подставляя данные значения un , n = 0, 1, … в (2), имеем

cλ n - a1 cλ n-1 - a2 cλ n-2 - … - ak cλ n-k = cλ n-k (λ k - a1 λ k-1 - … - ak ) ≡ 0. ♦

Теорема 2. Пусть последовательности un , vn , n = 0, 1, … удовлетворяют линейному рекуррентному соотношению (2). Тогда этим свойством обладает последователь-

ность rn , n = 0, 1, … , где rn = α un + β vn , n , α, β - произвольные константы из C.

♦ Доказательство очевидно. ♦

Теорема 3. Пусть λ 1 , … , λ k - простые (т.е. не являющиеся кратными) корни характеристического многочлена P(x) для последовательности (2).

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

где c1 , … , ck - подходящие константы из C.

♦ Согласно предыдущему замечаем, что последовательностьun , n = 0, 1, … есть решение соотношения (2). Чтобы доказать, что любое решение имеет вид (5) достаточно показать, что для произвольной последовательности vn , n = 0, 1, … , удовлетворяющей

(2), существуют константы c1 , … , ck , такие, что un = vn , n . Для этого достаточно, чтобы выполнялось v0 = u0 , v1 = u1 , … , vk-1 = uk-1 . Рассмотрим данные условия

относительно c1 , c2 , … , ck . Определитель этой системы есть определитель Вандермонда и согласно (7, стр. 118).

= ∏ (λi − λj ) ≠ 0

λ k− 1

λ k− 1

L λ k − 1

согласно предположению о корнях λ 1 , … , λ k . Отсюда и следует утверждение. ♦ В качестве примера рассмотрим рекуррентное соотношение (3). Имеем характеристический многочлен

P(x) = x2 - x -1

Его корни равны λ 1 = 1 + 2 5 , λ 2 = 1 − 2 5 , Общее решение имеет вид

u n = c 1 1+ 2 5 n + c 2 1− 2 5 n

Система уравнений для констант c1 , c2 : c1 1 + 2 5 + c2 1 − 2 5 = 1

1− 5

Откуда получаем c1

C2 = -

Пусть теперь λ - корень кратности r характеристического многочлена P(x). Аналогично предыдущему доказывается

Теорема 4. Последовательности c1 λ n , c2 nλ n ,K , cr n r − 1 λ n , n = 0, 1, … для про-

извольных констант c1 , … , cr из C удовлетворяют соотношению (2).

Теорема 5. Пусть характеристический многочлен P(x) имеет корни λ 1 , … , λ s кратностей r1 , … , rs (r1 + … + rs = k) . Тогда общее решение рекуррентного соотношения

Укажем еще одно полезное свойство линейных рекуррентных соотношений. Теорема 6. Пусть имеем соотношение

un = a1 un-1 + … + ak un-k

с начальными условиями u1 , … , uk . Тогда справедливо соотношение при всех n ≥ k

a 1 a 2

A k n − k uk

u k− 1

u n− 1

u n− k+ 1

♦ Доказательство индукцией по n. При n = k равенство (8) справедливо. Пусть оно верно при n. При n + 1 имеем

a 1 a 2

A k n + 1 − k uk

u k− 1

0 . . 1 0

a 1 a 2

a k a 1 a 2

a k n − k uk

u k− 1

a 1 a 2

u n+ 1

u n− 1

1 0 un − k + 1

u n− k+ 2

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

Теорема 7. Пусть C(n, k) - число подстановок n-элементного множества, имеющих точно k циклов. Тогда справедливо

C(n - 1, k - 1) + (n - 1)C(n - 1, k)

1, C(0, 1) = 0

♦ Разобьем множество подстановок множества X = {1, 2, … n,} имеющих точно k циклов, на два класса - подстановки, в которых элемент n содержится в единичном цикле, и подстановки, в которых элемент n находится в цикле длины l, l > 1. В первом случае число подстановок совпадает с числом подстановок множества X′ = {1, 2, …, n - 1}, имеющих k - 1 циклов, т.е. C(n - 1, k - 1). Во втором случае, удаляя элемент n, полу-

чаем подстановку множества X′ = {1, 2, …, n - 1} с k циклами, число которых равно C(n - 1, k). Выясним теперь, каким числом способов в подстановку степени n - 1 с k циклами можно добавить элемент n. Если имеется цикл длины i, то это можно сделать i способами. Общее число способов равно i1 + … + ik , где i1 , … , ik - длины циклов подстановки. Однако i1 + … + ik = n - 1. Значит число подстановок второго класса равно

(n - 1)C(n - 1, k). Отсюда и получаем (9). ♦

Полученные числа C(n, k) связаны с известными числами Стирлинга первого рода sn,k , которые определяются так:

sn,k = (- 1)n+k C(n, k)

Приведем таблицу нескольких первых значений чисел sn,k .

s n,1

s n,2

s n,3

s n,4

s n,5

Табл. Числа Стирлинга первого рода

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

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

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

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

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

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

Представление (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) типа Риккати.

Рекуррентным соотношением , рекуррентным уравнением или рекуррентной формулой называется соотношение вида , которое позволяет вычислять все члены последовательности
, если заданы ее первые 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):
. Из начального условия
находим
, т. е. . Таким образом,
.

mob_info