Оптимальных методов не существует

Доказательство. Рассмотрим произвольный пассивный метод на отрезке [ a,b ]и разобьём интервалы между узлами { у ₁ ,у ₂ ,…,у_N } на пары интервалов (D_{2 s- 1}, D_{2 s}) = ([ у _{2 s- 1}, у _{2 s} ] [ у_2s, у_2s+1 ]) (s= 1 ,…,p) и одиночный последний интервал D _{N- 1} = [ у _{N - 1}, у_N ].

Из определения точности следует:

ïD_{2 s- 1}ï+ïD_{2 s} ï£e;(s= 1, …,p); ïD _{N- 1}ï<e ( так как ïD _{N- 2}ï+ïD _{N- 1}ï£e,ïD _{N- 2}ï>0).

Поскольку рассматриваемые интервалы в сумме дают весь отрезок [ a,b ], то из этих оценок вытекают неравенство:

(b-a)=ïD₁ï+(ïD₂ï+ïD₃ï)+…+(ïD _{N- 2}ï+ïD _{N- 1}ï)<e+e p= e(p+ 1).

Отсюда следует: e > (b-a)/(p+ 1)= e_min.

Данная точность асимптотически достигается на пассивных методах со следующим расположением узлов:

y ₁ = a; y_N = b; y _{2 s} = a + s×e_min -d; y _{2 s+ 1} = a + s×e _min +d; s = 1 ,…,p. (10.3)

Точность таких d - оптимальных методов равна e =e_min +d.

Как следует из Теорем 10.1,10.2, для нечетного n= 2 p+ 1 (10.1)и четного n= 2 p (10.2) чисел пробных точек пассивного метода минимальная гарантированная точность совпадает и равна e_min = (b–a)/(p +1). Однако, в первом случае оптимальные методы существуют, а во втором – нет.

Если при четном n= 2 p числе пробных точек необходимо получить гарантированную точность e, строго большую минимально возможной точности
e_min= (b–a)/(p+ 1), то d– оптимальный метод может быть всегда построен.

Пример 2. Рассмотрим построение пробных точек для пассивного метода на отрезке [ a,b ] для n= 2, N= 4 – при p =1 паре пробных точек (рис.10.6) в случае заданной точности e, которая строго превышает минимально возможную e_on = (b-a)/(p+ 1) = (b-a)/2.

Решение. Введем d = e - e _on. С учетом a + (b-a)/2 = (a+b)/2из (10.3) получим следующие узлы, обеспечивающие заданную точность e:

y ₁ = a; y ₂ = x ₁ = 0,5×(a+b) - d; y ₃ = x ₂ = 0,5×(a+b) + d; y ₄ = b.

Рис.10.6

При d® 0 гарантированная точность рассмотренного в примере 2 метода e ® 0,5×(a+b). В то же время, при равномерном распределении пробных точек (x ₁ = (a+b)/3; x ₂ = 2×(a+b)/3) гарантированная точность метода была бы равна 2×(a+b)/3, т.е. большей величине.

Пример 3. Построим пробные точки для пассивного метода на отрезке [ a,b ] для n= 4, N= 6 – при p =2 парах пробных точек (рис.10.7) в случае заданной точности e, строго превышающей минимально возможную e_on = (b-a)/(p+ 1) = (b-a)/3.

Решение. Обозначим d = e - e _on. Из (10.3) получим следующие узлы, обеспечивающие заданную точность e:

y ₁ = a; y ₂ = x ₁ = a + e _оп -d; y ₃ = x ₂ = a + e _оп +d;

y ₄ = x ₃ = a + 2 e _оп -d; y ₅ = x ₄ = a + 2 e _оп +d; y ₆ = b.

Рис.10.7

Из Теорем 10.1 и 10.2 вытекает следующий алгоритм выбора оптимального числа пробных точек n пассивного метода по заданному исходному доверительному отрезку [ a; b ]и точности e:

1) расчет числа полных пар пробных точек по формуле p = ](b - a)/e[;

2) расчет минимальной гарантированной точности, которую может обеспечить пассивный метод при найденном числе p: e _min = (b-a)/(p+ 1);

3) если e _min < e, то выбирая d=e-e _min, можно построить оптимальный пассивный метод с n = 2 p пробными точками;

4) если же e _min = e, то оптимального пассивного метода с четным числом точек не существует и надо принимать n = 2 p +1.

Пример 4. Найти доверительный интервал, содержащий точный минимум функции F (х) = х² – 2 х на исходном отрезке[0,2; 2]при заданной гарантированной точностиe =0,5 пассивным методом с предварительным расчетом числа узлов.

Решение. Из Теорем 10.1,10.2 следует, что для заданных нечетного n=2p+1 и четного n= 2 p чисел пробных точек пассивного метода минимальная гарантированная точность совпадает и равна e_min = (b-a)/(p+ 1). Отсюда с учетом соотношения e_min £ 0,5 получим:

(p+ 1)= (b - a) / e_min ³ (b - a) /0,5 = 1,8 /0,5 = 3,6.

Так как p -целое, отсюда следует: p =]3,6-1[=]2,6[=3.

Рассмотрим четное n= 2 p число пробных точек. Для него предельная гарантированная точность e_min = (b-a)/(p+1) = 1,8/4 = 0,45. Для достижения действительной точности 0,5 используем величину d = 0,5-0,45 = 0,05. Рассчитаем положение пробных точек и значение функции в них:

x 1 = a+ 0,45 -d =0,6;	F (x1)= -0,84;
x 2 = a+ 0,45+d =0,7;	F (x 2)= -0,91;
x 3 = a+ 2× 0,45 -d =1,05;	F (x3)= -0,9975;
x 4 = a+ 2× 0,45+d =1,15;	F (x4)= -0,9775;
x 5 = a+ 3× 0,45 -d =1,5;	F (x5)= -0,75;
x 6 = a+ 3× 0,45+d =1,6;	F (x6)= -0,64.

В качестве искомого минимума выбираем точку x₃ = 1,05 с минимальным найденным значением функции F (x ₃) = -09975.

Точный минимум, найденный аналитическим путем расположен в точке х= 1, значение функции в этой точке F (x)=–1.

Ответ. Для решения задачи пассивным методом с гарантированной точностью e = 0,5необходимо использование не менее 6 пробных точек. Точное значение минимума находится на отрезке [ x ₂, x ₄] = [0,7;1,15]. Найдено приближенное положение точки минимума x_min= 1,05, в котором значение функции F (x ₃)=-0,9975.

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

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

Оценим асимптотические (при n® ¥) скорости роста зависимостей e (n) и n (e) в оптимальных пассивных методах. Поскольку

и

то ε (n) и (b–a) /n имеют одинаковую скорость роста. Отсюда следует:

e (n) = O [(b-a)/ n ],

n (e) = O [(b - a)/e] = O [ М ].

Вопросы для проверки знаний.

1. Чему равна гарантированная точность пассивного метода?

2. Что называют минимальной гарантированной точностью пассивных методов?

3. Какие методы из заданной группы называют оптимальными?

4. Какие методы называют d- оптимальными?

5. Какие сетки называют равномерными?

6. Как располагаются узлы на обычных равномерных сетках и сетках со сдвигом на шаг?

7. Почему пассивный метод на сетке со сдвигом на шаг более предпочтителен по сравнению с методом на обычной сетке?

8. При каких числах пробных точек оптимальные пассивные методы существуют, а при каких – не существуют?

9. В чем заключаются преимущества и недостатки пассивных методов?