9.3. Теоремы об оценках

Обозначим

Из выпуклости функции φ (x) следует соотношение

(9.1)

справедливое для всех точек x_k, ввиду предположения

В основе большинства дальнейших исследований сходимости релаксационных методов минимизации лежит следующая элементарная теорема об оценке.

Теорема 9.1.Если

3) последовательность {x_k} релаксационна, то имеет место оценка

(9.2)

Доказательство. Так как (см. (9.1))

то, применяя к этому соотношению лемму 9.1, приходим к оценке (9.2). Очевидно, что если при m→∞ ряд, стоящий в правой части неравенства (9.2), расходится, то имеет место слабая сходимость (то есть φ (х_m) → φ (х^*)-сходимость по функционалу) релаксационного процесса. Сильная же выпуклость функции φ(х) гарантирует в этом случае (см. (2.24)) сильную сходимость процесса (то есть сходимость последовательности {x_k} к решению х^*). Таким образом, для исследования сходимости релаксационных процессов при помощи формулы (9.2) следует уметь оценивать снизу величину

Заметим, что

Это обстоятельство для определенных классов релаксационных методов позволяет находить такую величину C > 0, не зависящую от числа итераций k, что

и, следовательно, получать оценки вида φ(х_m)-φ(x^*)≈ O(1/m). Рассмотрим теперь задачу отыскания безусловного минимума функции φ(х), то есть тот случай, когда X = Е_n.

Функция φ(х) по-прежнему выпукла и дифференцируема. Очевидно, что для задач безусловной минимизации в определении релаксационной последовательности условие x_k∈X становится излишним.

Теорема 9.2. Если

4) последовательность {х_k} релаксациопна, то справедливо неравенство

(9.3)

где μ₀=φ(x₀)-φ(x^*).

Доказательство есть очевидное следствие оценки (9.2), поскольку

Замечание. Если существует такой номер m₀, что φ(х_m0) > φ(x_m0+1). то из (9.3) следует неравенство

Теорема 9.3.Если Х=Е_n, функция φ(х) сильно выпукла и дифференцируема, а последовательность {x_k} релаксационна, то справедливы неравенства

(9.5)

и

(9.6)

где ρ-параметр сильной выпуклости

Доказательство с очевидностью следует из свойств сильной выпуклости (см. (2.26)):

и (см. (2.24))

и из леммы 9.2:

Оценки (9.4) - (9.6) позволяют в процессе вычислений накапливать информацию о скорости приближения φ(х_m) к φ(x^*), а в случае сильной выпуклости-о скорости приближения х_m к x^*. Заметим, что до тех пор, пока порядок величины

не ниже, чем О (1/k), релаксационный процесс минимизации остается сходящимся. В реальных ситуациях используют следующий прием. Задаются величиной ε>0, например, выбранной на данном этапе точностью вычислений, и продолжают процесс до тех пор, пока не нарушится неравенство

Но как только начинает устанавливаться ситуация

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