Дихотомия или бисекция?

Слова "метод дихотомии" часто используют для описания как метода половинного деления отрезка (бисекции) при поиске корня нелинейного уравнения f(x)=0, так и для метода дихотомии поиска минимума функции f(x) на интервале [a,b].

Терминологическая разница здесь не столь принципиальна, как вычислительная. В методе половинного деления на каждом шаге цикла значение функции вычисляется в одной новой точке отрезка (чаще всего, в середине), а в методе дихотомии - в двух.

Кроме того, в методе бисекции изменение пропорции, в которой делится отрезок, вряд ли что-то даст (см. пример ниже), а при поиске минимума функции методом дихотомии лучше всего делить отрезок в пропорции золотого сечения.

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

Покажем реализацию в MathCAD метода золотого сечения для поиска минимума функции f(x) на интервале [a,b]:

Метод золотого сечения для поиска минимума нелинейного уравнения

 Метод золотого сечения для поиска минимума функции, скачать файл MathCAD 15 (42 Кб)

Функция Gold возвращает вектор-столбец из 2 значений - найденное значение x, доставляющее минимум функции на интервале, и количество выполненных шагов (итераций). Во избежание зацикливания последняя величина ограничена значением 10000.

Для поиска максимума вместо минимума следует заменить в операторе if внутри функции знак "больше или равно" на "меньше или равно".

Напомню также, что для поиска экстремумов функции в MathCAD есть готовые операторы Maximize и Minimize.

А вот при дихотомии-бисекции мы вряд ли улучшим сходимость к корню уравнения, деля отрезок не пополам, а, допустим, в отношении той же константы золотого сечения, как делает функция G:

Бисекция и деление отрезка в отношении золотого сечения

Функция D делит отрезок классически пополам. Мне лично не удалось найти такого общего случая, чтоб золотое сечение отрезка давало какой-либо выигрыш в сходимости.

 Бисекция и деление отрезка в отношении золотого сечения, скачать файл MathCAD 15 (51 Кб)

04.12.2014, 13:24 [15859 просмотров]