Лекция: И т е р а ц и я 1.
Шаг 1. Находим x2=0,5, f(x2) = 0,669. Переходим к шагу 2.
Шаг 2. Определяем x1 = 0,25, f(x1) = 0,783. Переходим к шагу 3.
Шаг 3. f(x1) > f(x2), поэтому полагаем x3 = 0,75, вычисляем f(x3) = 0,789 и переходим к шагу 4.
Шаг 4. f(x1) < f(x2), поэтому полагаем а = 0,25, b = 0,75 и переходим к шагу 5.
Шаг 5. Находим en = 0,25 > 0,1, т.е. переходим к следующей итерации, начиная с шага 2.
Результаты вычислений на остальных итерациях записаны в табл. 2.4.
Таблица 2.4
Номер итерации | а | b | en | x1 | x2 | x3 | f(x1) | f(x2) | f(x3) | Сравнениеf(x1) и f(x2) |
0,250 | 0,750 | 0,25 | 0,375 | 0,500 | 0,625 | 0,707 | 0,669 | 0,688 | f(x1) > f(x2) f(x2) < f(x3) | |
0,375 | 0,625 | 0,13 | 0,438 | 0,500 | 0,563 | 0.669 | 0,669 | 0,670 | f(x1) > f(x2) f(x2) < f(x3) | |
0,438 | 0,563 | 0,06 | 0,06 < 0,1 — точность достигнута |
Таким образом, x* » x2 = 0,5, f* » f(x2) = 0,67. Сравните этот ответ с результатами решения предыдущих примеров.
Замечание. На первой итерации второго метода деления отрезка пополам вычисляется не более трех значений f(x) а на остальных — не более двух. Поэтому N вычислений f(x) гарантируют осуществление (N-1)/2 итераций, и достигнутая точность определения x* составляет
. (2.18)
Сравнение методов исключения отрезков и перебора. При сравнении прямых методов минимизации обычно учитывают количество N значений f(x), гарантирующее заданную точность определения точки х* тем или иным методом. Чем меньше N, тем эффективнее считается метод. При этом вспомогательные операции такие, как выбор пробных точек, сравнение значений f(x) и т.п., не учитываются. Во многих практических случаях определение значений целевой функции требует больших затрат (например, времени ЭВМ или средств для проведения экспериментов) и вспомогательными вычислениями можно пренебречь. А эффективность метода минимизации особенно важна именно в таких случаях, поскольку позволяет сократить указанные затраты.
Эффективность методов минимизации можно также сравнивать, на основании гарантированной точности e(N) нахождения точки х*, которую они обеспечивают в результате определения N значений f(x). Из анализа формул (2.10), (2.14), (2.17) и (2.18) следует, что наиболее эффективным из сравниваемых методов является метод золотого сечения, за ним идут методы деления отрезка пополам и наименее эффективен метод перебора. Этот вывод иллюстрирует табл. 2.5 значений достигнутой точности e(N) в зависимости от количества Nнайденных значенийf(x) на отрезке длины 1 для указанных методов.
Таблица 2.5
Методы минимизации | Количество найденных значений f(x) | |||
N = 5 | N = 11 | N = 21 | N = 51 | |
Метод золотого сечения | 0,073 | 4,1 ×10-3 | 3,3 ×10-5 | 1,8 ×10-11 |
Методы деления отрезка пополам *) | 0,125 | 1,6 ×10-2 | 4,9 ×10-4 | 1,5 ×10-8 |
Метод перебора | 0,250 | 0,100 | 0,050 | 0,020 |
* ) Из формул (2.14)и (2.18)следует приблизительно одинаковая эффективность обоих методов деления отрезка пополам. В табл. 2.5 представлены значения e(N)для второго из них