Метод деления интервала пополам.

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

Шаг 1. Положить х_m =(а+b)/2 и L=b-a. Вычислить значе­ние f(x_m).

Шаг 2. Положить х₁ = а + L/4 и х₂ = b - L/4. Заметим, что точ­ки х₁, х_m, х₂ делят интервал (а, b) на четыре равные части. Вычис­лить значения f(х₁₎ и f(х₂).

Шаг 3. Сравнить f(х₁₎ и f(х_m).

(1) Если f(х₁₎ < f(х_m), исключить интервал (x_m, b), положив b=Х_т.

Средней точкой нового интервала поиска становится точка х₁. Сле­довательно, необходимо положить x_m = х₁. Перейти к шагу 5.

(2) Если f(х₁₎ ³ f(х_m) перейти к шагу 4.

Шаг 4. Сравнить f(х₂₎ и f(х_m).

(1) Если f(х₂₎ < f(х_m), исключить интервал (a, х_m), положив а = х_m. Так как средней точкой нового интервала становится точка х₂, положить х_m = х₂. Перейти к шагу 5.

(2) Если f(х₂₎ ³ f(х_m), исключить интервалы (а, х₁) и (х₂, b). Положить а = х₁ и b=х₂. Заметим, что х_m продолжает оставаться средней точкой нового интервала. Перейти к шагу 5.

Шаг 5. Вычислить L=b-a. Если величина |L| мала, закон­чить поиск. В противном случае вернуться к шагу 2.

Замечания

1. На каждой итерации алгоритма исключается в точности по­ловина интервала поиска.

2. Средняя точка последовательно получаемых интервалов всег­да совпадает с одной из пробных точек х₁, х₂ или х_m, найденных на предыдущей итерации. Следовательно, на каждой итерации тре­буется не более двух вычислений значения функции.

3. Если проведено n вычислений значения функции, то длина полученного интервала составляет (1/2)^n/2 величины исходного интервала.

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