Метод дихотомии (половинного деления)

В данном случае общее количество вычислений f(x) четное, т.е. N = 2/, l = 1,2,", на j-м шаге (j-й итерации) производится пара вычислений xjj) и x^j), отстоящих на расстоянии е /2 по обе стороны от середины текущего отрезка локализации [a(j-1), b(j-1)].

Если fj(j) < f2(j), то отбрасывается часть отрезка, расположенная справа от x^j); если f1(j) > f2(j), то отбрасывается

часть отрезка, расположенная слева от x1( j) .

Используются два условия окончания вычислений:

а) выполнение заданного количества вычислений N;

б) достижение заданной величины 5 уменьшения отрезка локализации.

Итак, алгоритм поиска минимума унимодальной функции методом дихотомии заключается в следующем.

Задаются N (либо 5) и е, полагается j=1.

На j-й итерации вычисляются

x1 j) =1 (a(j-1) + b( j-1))--, x2 j) =1 (a(j-1) + b (j-1)) + -, 1 2 2 2 2 2

f( j) = f (x1j)), f2( j) = f (x2j)).

Если f( j) < f2( j), то a(j) = a(j-1), b( j) = x^).

Если f(j) > f2(j), то a(j) = xПроверяется условие окончания вычислений:

L2 j

а) j=N/2 либо б) <5.

L0

Если оно выполняется, то определяются итоговый отрезок

локализации, оценки точки минимума x* и величины минимума

* *

f = f (x ), и вычисления завершаются.

Если условие не выполняется, то полагается j = j +1 и

осуществляется переход к п.2.

Отметим, что для определения оценки точки минимума надо рассмотреть все исследованные точки итогового отрезка локализации и выбрать ту из них, для которой значение функции минимально.

Пример. Определить методом дихотомии минимум функции f (х) = х4 -6х2 +10, заданной на отрезке А=[ 1,3], при N=8, ?=0,1.

Решение.

В данном случае будут выполнены N/2=4 итерации.

Результаты вычислений заносим в табл. 4.3.

Таблица 4.3 Номер итерации х{ J) х (J) 2 f1( J) < > f(J) a(J) b( J ) 0 1 1,95 2,05 1,644 < 2,446 1 1 3

2,05 2 1 ,475 1,575 1,680 > 1,270 1 ,475 2,05 3 1,713 1,813 1,004 < 1,082 1 ,475 1,813 4 1,594 1,694 1,211 > 1,017 1,594 1,813 Поскольку j=N/2=4, то вычисления завершаются. Точка минимума локализована на отрезке А8 = [1,594; 1,813]. На данном отрезке исследованы 4 точки: (4)

a

1,594 ^ f (a(4)) = 1,211; (4)

,(3)

1,713, f * = f (х13)) = 1,004.

> х = х

b(4) = 1,813 ^ f (bw) = 1,082;

(4)

= 1,694 ^ f (х24)) = 1,017; (3Ъ

X(3) = 1,713 ^ f (х(3)) = 1,004; Ответ: А8 = [1,594; 1,813], х = 1,713, f = 1,004.

<< | >>
Источник: Харчистов Б.Ф.. Методы оптимизации. 2004

Еще по теме Метод дихотомии (половинного деления):

  1. 1.6.6.Метод деления неразложимого остатка
  2. Метод деления интервала пополам
  3. § 2. Предмет и метод правового регулирования как основания деления права на отрасли и институты
  4. 4.7.2. ПРЕДМЕТ И МЕТОД ПРАВОВОГО РЕГУЛИРОВАНИЯ КАК ОСНОВАНИЯ ДЕЛЕНИЯ ПРАВА НА ОТРАСЛИ И ИНСТИТУТЫ
  5. 2. ПРЕДМЕТ И МЕТОД ПРАВОВОГО РЕГУЛИРОВАНИЯ КАК ОСНОВАНИЯ ДЕЛЕНИЯ ПРАВА НА ОТРАСЛИ И ИНСТИТУТЫ
  6. § 2. Предмет и метод правового регулирования как основания деления норм права на отрасли
  7. 6.7. Классическая ДИХОТОМИЯ
  8. 6-7. Заключение: классическая дихотомия
  9. 5.4. КОЛИЧЕСТВЕННАЯ ТЕОРИЯ ДЕНЕГ. КЛАССИЧЕСКАЯ ДИХОТОМИЯ
  10. 2.1. Деление гражданского процесса
  11. § 2. ДЕЛЕНИЕ ГРАЖДАНСКОГО ПРОЦЕССА НА IUS И IUDICIUM
  12. 2.1. Деление гражданского процесса