Оценка скорости сходимости методов спуска

Теорема 8. Пусть:

1) функция сильно выпуклая, непрерывно дифференцируемая, ее градиент удовлетворяет условию Липшица;

2) последовательность строится по формулам (5.4.2) ;

3) величины (3,4,6) удовлетворяют неравенствам .

4) параметры в (5.4.8) удовлетворяют условию .

Тогда справедливы оценки:

, (5.5.1)

, (5.5.2)

где .

Доказательство. На основании неравенства (3.1.13)

, (5.5.3)

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

, (5.5.4)

которое справедливо и для одномерной функции . Поэтому

, (5.5.5)

где - минимум по функции .

На основании неравенства (3.1.11)

(5.5.6)

найдем верхнюю оценку возможного убывания функции

. (5.5.7)

Из (5.5.5), в силу (5.4.8), будем иметь

Отсюда, на основании (5.5.7), получим

.

Следовательно

Используя рекуррентно полученное неравенство, придем к оценке (5.5.1). Оценка (5.5.2) следует из неравенства (3.1.8)

.