§ 3.18. Упрощенные наилучшие алгоритмы

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

,   (3.63)

откуда при условии малости , аналогично тому, как это было сделано в предыдущем параграфе, находим

.                       (3.64)

Рассмотрим еще один способ определения упрощенного приближенно наилучшего алгоритма, для которого бы не требовалась малость . Меру качества алгоритмов выберем в виде функционала (3.49). Обозначая

,

запишем алгоритм (3.53), в котором диагональная матрица заменена скаляром

.                (3.65)

Найдем условное математическое ожидание квадрата евклидовой нормы :

   (3.66)

Предположим далее, что при любом

   (3.67)

Тогда, учитывая соотношение

                (3.68)

и заменяя в (3.66) слагаемые соответственно их оценками (3.67), получим

.    (3.69)

Для нахождения безусловного математического ожидания среднеквадратического отклонения (3.49) произведем осреднение (3.69) по .

Тогда с учетом обозначения (3.49) получим

.      (3.70)

Теперь уже можно найти оптимальное значение . Дифференцируя правую часть (3.70) по   и приравнивая результаты нулю, находим

.                       (3.71)

По-видимому, найденное значение  и определяет то, что можно сделать в общем случае при произвольной норме  и отсутствии информации о плотности распределения.

Подставляя значение  (3.70), имеем

.    (3.72)

Отсюда можно оценить число шагов, по истечении которого  достигает некоторого достаточно малого значения

.                    (3.73)