§ 3.14. О правиле остановки

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

Рис. 3.6.

Для надежного определения  необходимо каким-либо образом «сгладить» последовательность . Одна из таких возможностей состоит в использовании скользящего среднего

.        (3.38)

Если, начиная с какого-то номера , для всех

                       (3.39)

(где — достаточно малая величина), то величина  определяет тог момент времени, при котором можно считать, что

                                              (3.40)

Сглаживание  может быть достигнуто иным путем на основе модифицированного алгоритма, представляющего частный случай (3.27):

,          (3.41)

где, например,

,                (3.42)

или

.             (3.43)

Здесь сглаживанием  достигается за счет предварительной обработки .