Математическая энциклопедия - половинного деления метод

метод дихотомии,1) Один из методов численного решения уравнений с одним неизвестным. Пусть имеется уравнение f(x) = 0 с непрерывной на отрезке [а, b]функцией f(х), принимающей на концах отрезка значения разных знаков и имеющей внутри [а, b]единственный корень х *. Для приближенного нахождения х * отрезок [ а, b]делят пополам и вычисляют значение f(x1). в средней точке x1=(a+b)/2. Если , то из двух отрезков [ а, х 1]и [ х 1, b]. для последующего деления пополам выбирается тот, на концах к-рого значения функции различны по знаку. Возникающая в процессе такого дробления последовательность середин отрезков х 1, х 2, . . . сходится к корню х * со скоростью геометрич. прогрессии:

(1)

причем в рассматриваемом классе функций оценка (1) неулучшаема. В случае, когда функция f(x).имеет на [ а, b] более одного корня, последовательность будет сходиться к одному из них.

2) Один из методов минимизации функций одного переменного. Пусть требуется найти минимум

унимодальной функции f(х).на отрезке [ а, b]и указать точку x*, в к-рой он достигается. Тогда отрезок [а, b]делят пополам и вблизи его середины вычисляют значения функции f(x).в двух точках , где число e>0, являющееся параметром метода, достаточно мало. Затем значения f(x1).и f(x2) сравнивают и с учетом унимодальности функции f(x).из двух отрезков [ а, х 2] и [xl, b]выбирают тот, к-рый заведомо содержит точку х *. Так, если , это будет отрезок [ а, х 2], в противном случае отрезок [a, b]. Выбранный отрезок вновь делят пополам, вблизи его середины берут две точки , сравнивают в них значения функции и т. д. В результате возникает последовательность срединных точек , для к-рой

(2)

За приближения к f* принимают значения при достаточно больших n.

Название метода объясняется тем, что на каждом следующем шаге описанного алгоритма отрезок, содержащий точку минимума, становится примерно вдвое короче. На классе унимодальных, функций П. д. м. не является наилучшим. Существуют более эффективные методы, позволяющие при том же количестве вычислений значений функции достигнуть лучшей по сравнению с (2) точности (см., напр., Фибоначчи метод).

Лит.:[1] Демидович Б. П., Марон И. А., Основы вычислительной математики, 3 изд., М., 196В; [2] Уайлд Д.-Дж., Методы поиска экстремума, пер. с англ., М., 1967.

М. М. Потапов.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985