§ 6. Оценка скорости сходимости

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

и, следовательно, Потенциальная функция также выбирается в виде конечного ряда

Сделаем два следующих дополнительных предположения:

1°. Система функций и распределение вероятностей предъявления точек таковы, что на любом множестве с X положительной вероятности выполнено условие

для любой функции вида

2°. Имеет место соотношение

Относительно предположений 1° и 2° сделаем следующие замечания.

Замечание 1. Предположение 1° является более сильным, нежели предположение, определяемое формулой (28) § 4 главы VI. Соотношение (30) § 4 главы VI является следствием формулы (28) и поэтому имеет место и при выполнении условия Г,

Замечание 2. Несмотря на то, что предположение 1° является более жестким, чем предположение, которое вводилось в § 4 главы VI, оно не слишком стеснительно. Так, например, предположение Г выполнено, если существует непрерывная плотность вероятности показов, а система функций такова, что обращается в нуль не более чем в счетном числе точек.

Замечание 3. Из предположения 2° следует, что имеется ненулевая вероятность появления точек из множества, где т. е. что рассматриваемая задача является вероятностной по существу и не может быть сведена к детерминистской задаче разделения ситуаций на классы. Поэтому предположение 2° естественно при рассмотрении вероятностной задачи распознавания образов.

Переходя к получению оценок скорости сходимости алгоритма, в качестве показателей сходимости возьмем

Так же как и в главе VI, в данном случае приходится накладывать ограничения не только на вид восстанавливаемой функции и распределение показов, но и на выбор фигурирующей в алгоритмах последовательности Именно, будем предполагать, что последовательность удовлетворяет условию 3° § 4 главы VI (формулы (34) и (35) § 4 главы VI).

В этих условиях имеет место следующая теорема.

Теорема II. Если выполнены условия 1° и 2° этого параграфа и условие 3° § 4 главы VI, то при использовании второго и третьего алгоритмов для любого существуют константы (вообще говоря, различные для второго и третьего

алгоритмов), такие, что вероятность тех реализаций алгоритмов, для которых выполнены неравенства

больше, чем

Доказательство теоремы II.

Установим связь между и С этой целью покажем, что если выполнены предположения 1° и 2° и

где некоторая константа, то существует число не зависящее от такое, что

Из предположения 2° следует, что существует достаточно малое такое, что

Дадим оценку снизу для величины Поскольку

и вместе с тем

то

Заметим, что из (59) следует

В самом деле, если то

откуда

где так как функции ограничены на

Учитывая, что при имеет место неравенство

величина в силу (62) может быть оценена следующим образом:

В § 4 главы VI было показано, что из условия (28) следует, что наименьшее собственное число матрицы (29) положительно (см. стр. 286—287). Если теперь ввести в рассмотрение матрицу условных математических ожиданий

то, исходя из условий (53) и (61), рассуждая так же, как в § 4 главы VI, устанавливаем, что собственные значения такой матрицы также положительны. Следовательно, существует такое число что

Теперь из (61), (63) и (64) следует

что и доказывает соотношение (60), если положить

Соотношение (60) эквивалентно условию 2° леммы VI главы IV, так как в силу В силу утверждения этой леммы выполнено неравенство (239) теоремы XVIII главы IV, если

и последовательность подобрана соответствующим образом. Для выбора последовательности используем условие 3° § 4 главы VI. Для каждого определим так, чтобы были выполнены соотношения (34) и (35) (стр. 287), и положим

Поскольку, начиная с некоторого и так как то при и в качестве числа мажорирующего последовательность можно взять Поскольку в условии 3° § 4 главы VI функция без ограничения общности не превышает, например, единицы, то в качестве последовательности минорирующей последовательность можно взять

При сделанном выборе и выполнено условие 1° теоремы XVIII (в силу соотношений (34) и (35), стр. 287) и условие 2° этой теоремы (в силу леммы VI гл. IV). Утверждение теоремы XVIII приводит поэтому к неравенству (57). Для доказательства неравенства (58) воспользуемся неравенством (43), из которого следует, что

и неравенством

где некоторая константа. Неравенство (67) следует из неравенства (30) § 4 главы VI, которое, как указано в замечании 1 к доказываемой теореме, справедливо. Утверждение (58) следует теперь из (66), (67). Теорема доказана полностью.