§ 4. Оценка скорости сходимости алгоритмов

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

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

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

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

а

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

выполнено неравенство

Из (27) и (28) следует

Обозначая матрицу

получим, что квадратичная форма 2 переменных является положительно определенной. Тогда, как

известно, существуют числа такие, что

где соответственно наименьшее и наибольшее характеристические числа матрицы

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

1°. Существует такое число что, начиная с некоторого выполнены неравенства

и

где число определяется соотношением (30).

2°. Существуют положительные числа такие, что, начиная с некоторого выполнено неравенство

3°. Для любого найдется такое что удовлетворяются соотношения

где В — константа, не зависящая от выбора А.

4°. Для любого найдутся такие числа что

Условия 3° и 4° отличаются от условий 1° и 2° соответственно лишь тем, что в этих последних условиях требовалось выполнение неравенств при конкретном а в условиях 3° и 4° — при произвольных положительных А.

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

либо

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

Проверим, например, что последовательность удовлетворяет условиям 1°. В этом случае левая часть соотношения (31) имеет вид

Логарифмируя это выражение, получаем

При последнее соотношение отрицательно, а следовательно, выражение (37) меньше единицы. Таким образом, условие (31) выполняется. Условие же (32) выполняется при любом

Аналогично показывается, что последовательность удовлетворяет условиям а также что последовательность удовлетворяет всем условиям 1° — 4°.

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

Говоря об оценке скорости сходимости процесса, необходимо договориться о том, в каких терминах эта оценка будет дана. Всюду далее будет оцениваться асимптотическое поведение двух последовательностей.

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

где, как и ранее,

Интересуясь поведением при мы будем оценивать изменение их математических ожиданий (теорема III), а также изменение самих этих величин на реализациях (теорема IV).

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

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

Замечание. Условие 1° или 2° фиксирует число именно оно и фигурирует в оценках для алгоритма § 2. Теорема III утверждает, что для первого алгоритма § 1 может быть найдено такое число , что имеют место оценки, приведенные в таблице I. В том специальном случае, когда фигурирующая в условиях 3° и 4° функция т. е. не зависит от А, в первой строке таблицы I можно положить Это утверждение непосредственно следует из хода доказательства теоремы III.

Доказательство теоремы III. Имея в виду использовать теорему XVI главы IV, покажем, что для

(кликните для просмотра скана)

первого алгоритма § 1 и алгоритма § 2 можно так выбрать последовательности чтобы одновременно выполнялись все условия этой теоремы. Второй алгоритм § 2 рассматривается специальным образом. Далее рассмотрим каждый из трех алгоритмов этой главы порознь.

Первый алгоритм § 1. Раньше, чем конкретизировать последовательности и в этом случае, установим связь между последовательностями Для этого покажем сначала, что в рассматриваемом алгоритме существует константа такая, что при всех выполнено неравенство

Согласно формуле (8) для рассматриваемого алгоритма можно записать

где Возводя обе части равенства (40) в квадрат и суммируя по от 1 до получим

При выводе формулы (41) учтено, что и что в силу ограниченности некоторой константой имеет место неравенство

Усиливая неравенство (41), получаем

Суммируя последнее неравенство по от до находим

Из последнего неравенства следует, что и поэтому

Тем самым неравенство (39) установлено. Из (39) вытекает

Из этого соотношения в силу (25) и левого неравенства в (30) следует

откуда, используя обозначение (38), получим

С другой стороны, в соответствии с неравенством Коши — Буняковского из определения функционала имеем

Поэтому из (30) следует, что

и

Далее из неравенства Коши — Буняковского следует

откуда с учетом (43) получим

Поэтому имеет место неравенство

Как отмечено в § 3 при доказательстве сходимости алгоритма, условия теоремы XIV в данном случае выполнены. Поскольку соотношение (42) совпадает с условием пункта Г леммы VI (гл. IV). В силу утверждения 1° леммы VI в условиях рассматриваемого алгоритма выполнено неравенство (217) теоремы XVI, где

Если теперь положить

где и где в свою очередь определяется левой частью неравенства (30), формулой (39), а функция определяется в соответствии с условиями 3° или 4°, то непосредственно проверяется, что выполнены соответственно условие (218) либо условие (219) теоремы XVI главы IV.

Таким образом, все условия теоремы XVI главы IV выполнены, и поэтому в силу этой теоремы существует такая константа что справедлива оценка

которая совпадает с первым неравенством, помещенным в первой строке последнего столбца таблицы Неравенство для следует из неравенства для и установленного выше неравенства (44).

Второй алгоритм § 1. Имея в виду, что для этого алгоритма функционал имеет вид

используем условие (30). При этом получим

или, используя обозначение (38),

Переходя в (46) к математическим ожиданиям, находим

Воспользуемся теперь формулой (24) из § 3, вспоминая, что Введя величину

из (24) можно получить неравенство

Переходя в этом неравенстве к математическим ожиданиям (условному и безусловному соответственно), определяем

Воспользовавшись левым неравенством в (47), получим с помощью (50)

Из (61) сразу следует доказываемая оценка для если положить Соответствующая оценка для получается с помощью правого неравенства в (47).

Алгоритм § 2. Для алгоритма § 2 выполнены все условия теоремы XIV главы IV и Кроме того, функционал, минимизируемый алгоритмом § 2, совпадает с функционалом второго алгоритма § 1, и поэтому соотношение (46) справедливо и для алгоритма § 2. Тем самым выполнено условие 1° леммы VI (гл. IV), и в силу утверждения леммы VI выполнено неравенство (217) теоремы XVI главы IV, где

Выберем теперь в качестве последовательности последовательность

Тогда непосредственно проверяется, что:

а) если последовательность удовлетворяет условиям 1° этого параграфа, то выполняется условие 1° (соотношение (218)) теоремы XVI главы IV;

б) если последовательность удовлетворяет условиям 2° этого параграфа, то выполнены условия 2° (соотношение (219)) той же теоремы.

В силу утверждения теоремы XVI и правой части неравенства (46) устанавливаем справедливость неравенств третьей строки последнего столбца таблицы Теорема доказана.

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

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

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

Замечание. Замечание о выборе чисел приведенное после формулировки теоремы III, полностью относится и к теореме IV.

Доказательство теоремы IV. Для доказательства этой теоремы мы покажем, что при использовании каждого из трех алгоритмов, и при обозначениях последовательностей а", принятых выше при доказательстве теоремы III (эти обозначения вводились

(кликните для просмотра скана)

порознь для каждого алгоритма), выполнены все условия теоремы XVIII главы IV. Тогда из утверждений этой теоремы будут следовать оценки, приведенные в последнем столбце таблицы II.

Первый алгоритм § 1 и алгоритм § 2. Обратим внимание на то, что условие 1° (соотношение (238)) теоремы XVIII главы IV совпадает с условием 1° (соотношение (218)) теоремы XVI той же главы, если только последовательности числовые последовательности, не зависящие от С. Кроме того, условия на выбор в доказываемой теореме те же, что и в предыдущей теореме III. Поэтому, если выбрать и к" так же, как и при доказательстве теоремы III, и принять во внимание, что при этом выполнено соотношение (218) главы IV, то условие 1° теоремы XVIII для первого алгоритма § 1 и алгоритма § 2 будет выполнено. Тем самым остается проверить, что при выбранных выполнено условие 2° теоремы XVIII (неравенство (239)). Для этого достаточно заметить, что, как и показано при доказательстве теоремы III, в рассматриваемых алгоритмах выполнено условие пункта 1° леммы VI (гл. IV) и, в соответствии с замечанием к лемме VI, справедливо утверждение пункта 2° этой леммы, которое и устанавливает справедливость соотношения (239) для выбранных числовых последовательностей а", и

Таким образом, оба условия теоремы XVIII выполнены, причем последовательности не зависят от С (и, следовательно, от б). В силу утверждения теоремы XVIII оценки для приведенные в соответствующих строках последнего столбца таблицы II, доказаны. Оценки для следуют сразу из оценки для в силу неравенств (43) (для первого алгоритма § 1) и (46) (для алгоритма § 2).

Второй алгоритм § 1. Воспользуемся соотношениями (46) и (49), которые были получены для рассматриваемого алгоритма при доказательстве теоремы III. Из этих соотношений следует

где Выберем и положим Условие 1° теоремы XVIII при этом выполнено.

Проверим выполнение условия 2°. Выбранная последовательность для каждого порождает последовательность множеств реализаций, удовлетворяющих условиям (235) главы IV (см. текст гл. IV, предшествующий формулировке теоремы XVIII). Если умножить теперь обе части неравенства (53) на плотность вероятности проинтегрировать их по множеству и воспользоваться обозначениями (236) и (237) главы IV, то получим как раз условие 2° теоремы XVIII. Из утверждения теоремы XVIII сразу следуют оценки, приведенные во второй строке последнего столбца таблицы II, если учесть еще неравенство (46). Теорема IV доказана полностью,