БлогNot. Дихотомия или бисекция?

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

Слова "метод дихотомии" часто используют для описания как метода половинного деления отрезка (бисекции) при поиске корня нелинейного уравнения 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 [15484 просмотра]


теги: числа mathcad

К этой статье пока нет комментариев, Ваш будет первым