Метод покрытий

Метод ломаных

Положим х₁ = а, x₂ = b. Пусть вычисления проведены в точках В силу условия Липшица

и потому

.

Нетрудно видеть, что функция , является точной минорантой для функций, удовлетворяющих условию Липшица и принимающих в точках х₁,..., х_i значения соответственно y₁, …, y_i . Точка x_i+1 выбирается по правилу

.

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

Число вычислений N может быть задано заранее. Если же требуется обеспечить отыскание значения минимума с точностью не хуже , то следует прекратить вычисления, как только

Пусть требуется обеспечить отыскание минимума с точ­ностью не хуже.

Обозначим через минимальное число отрезков длины r =2/М, которыми можно покрыть отрезок Х = [а, b]. Очевидно, что . Выберем

.

Нетрудно видеть, что отрезки длины r с центром в точках сетки (2.3) по­крывают X.

Пусть вычисления проведены в точках . Опишем (i+1)-й шаг алгоритма. Для этого введем обозначение

,

где функция определена формулой (2.2). Ясно, что множество X_i является объединением не более i+l промежутков. Обозначим число этих промежутков через m_i (на рис. 2.2 они выделены жирной линией). Пусть j-й промежуток есть . Обозначим через N_i, минимальное число отрезков длины r, которыми можно покрыть множество X_i. Очевидно, что

, где .

Выберем

.

Ясно, что отрезки длины r с центрами в точках сетки (2.4) покрывают X_i.

Процесс останавливается на s-м шаге, если Х_s = Æ. При этом величина принимается в качестве приближения к значению минимума.

В силу пустоты множества X_s имеем

Это означает, что требуемая точность обеспечена, поскольку

.