§ 3. Сходимость алгоритмов

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

могут рассматриваться как алгоритмы минимизации соответствующих функционалов.

Выражения для функционалов, соответствующих алгоритмам настоящей главы, получим, подставив в формулу (162) главы IV функцию Тогда

где

— функция скалярного аргумента, выпуклая вследствие монотонности Для первого алгоритма § 1

для второго алгоритма § 1 и алгоритма § 2 с точностью до постоянного множителя

Сходимость первого алгоритма § 1 и алгоритма § 2 непосредственно следует из теоремы XV главы IV.

Действительно, для первого алгоритма § 1 имеет место неравенство

и, кроме того, Поэтому все условия теоремы XV выполняются, если выполнено условие существования математического ожидания

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

Для алгоритма § 2 функция очевидно, удовлетворяет условию 1° теоремы XIV при Условия (155) и (156) главы IV выполняются в соответствии с требованиями, наложенными в § 2 на помеху 1. Условие 2° теоремы XIV главы IV и условие существования приводят к естественному условию;

Таким образом, при использовании первого алгоритма § 1 и алгоритма § 2 оказываются выполненными условия теоремы XV главы IV, если только первого алгоритма § 1) и алгоритма § 2). В силу этой теоремы справедливо следующее утверждение.

Теорема Пусть выполнено условие

Тогда при использовании процедуры (5)

при т. е. процедура (5) приближает функцию Если, кроме того, то

при т. е. процедура (5) восстанавливает функцию

Пусть выполнено условие Тогда при использовании процедуры (16)

при т. е. процедура (16) приближает функцию Если, кроме того, то

при т. е. процедура (16) восстанавливает функцию

Замечание к теореме Рассуждения, доказывающие эту теорему, опираются только на теорему XV главы IV. Поэтому в задаче аппроксимации функций без помех в соотношении (4) могут быть использованы функции иного вида, лишь бы были выполнены условия этой теоремы.

При этом из теоремы XV будет следовать, что

если только

а при

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

Иначе обстоит дело в задаче аппроксимации функции при учете помех. В этом случае, когда функция линейная, помеха входит в процедуру аддитивно. Если же функция нелинейна, то получающаяся рекуррентная процедура не имеет вида процедуры (11) § 2 главы II, и теоремы XIV и XV главы IV в этом случае не могут быть непосредственно использованы.

Перейдем теперь к рассмотрению второго алгоритма § 1. Для него условия теоремы XV не выполняются, так как нарушено условие (14) в) § 2, главы II, и его сходимость должна быть установлена особо. Сходимость этого алгоритма устанавливает

Теорема II. Пусть Тогда при использовании процедуры (6)

если только выполнено условие (7).

Доказательство теоремы II. Имея в виду воспользоваться теоремой VI главы IV, покажем, что последовательности функций

удовлетворяют условиям этой теоремы.

В силу рекуррентной процедуры (9), эквивалентной (6), имеем:

Вспоминая, что

и что в силу условия

получаем из (23)

Обозначим теперь через а минимум по выражения, заключенного в квадратные скобки; в силу условия Тогда из (24) и из того факта, что

следует сразу, что конечно при любом .

Перейдем теперь в (24) к условным математическим ожиданиям, учитывая при этом, что

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

Теорема доказана.

Таким образом, если теорема I устанавливает, что первый алгоритм § 1 и алгоритм § 2 полностью решают задачу аппроксимации как в смысле восстановления, так и в смысле приближения функции то теорема II устанавливает лишь, что второй алгоритм § 1

- решает задачу восстановления в том случае, когда Вопрос о том, решает ли этот алгоритм задачу восстановления, если остается открытым. Вместе с тем простые примеры показывают, что второй алгоритм § 1 не решает задачи приближения функций, несмотря на то, что он является градиентным по отношению к функционалу

Иными словами, в случае, когда последовательность значений функционала

с ростом не стремится к какому-либо пределу.

Проиллюстрируем это следующим простым примером. Рассмотрим функции, заданные на отрезке [0,1]. Пусть система функции состоит из единственной функции а приближаемая функция есть Распределение вероятностей предположим, например, равномерным на отрезке [0, 1]. Функционал имеет в этом случае вид

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

образом, задачу приближения решает в данном случае функция

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

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

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