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

Постановка задачи.

Тебуется наути безусловный минимум функции f(x) одной переменной, т.е. такую точку , что .

Стратегия поиска.

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

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

Алгоритм.

Шаг 1. Задать начальный интервал неопределенности и требуемую точность .

Шаг 2. Положить k=0.

Шаг 3. Вычислить среднюю точку , длину интервала и значение функции в средней точке .

Шаг 4. Вычислить точки: , , а также значения функции в этих точках: ,

Шаг 5. Сравнить значения и :

а) если < , исключить интервал , положить . Средней точкой нового интервала становится точка : . Перейти к шагу 7.

б) если , перейти к шагу 6.

Шаг 6. Сравнить значения и :

а) если < , исключить интервал , положить . Средней точкой нового интервала становится точка Перейти к шагу 7.

б) если , исключить интервалы : , положить . Средней точкой нового интервала остается точка . Перейти к шагу 7.

Шаг 7. и проверить условие окончания:

a) если , процесс поиска заканчивается и . В качестве приближения можно взять середину этого интервала .

б) если , то положить k=k+1 и перейти к шагу 4.

Сходимость.

Для метода дихотомии характеристика относительного уменьшения начального интервала неопределенности находится по формуле , где N - количество вычислений функции.

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

Пример.

Задание. Определить методом дихотомии минимум функции , заданной на отрезке , при .

Решение.

Метод Золотого сечения.

Постановка задачи.

Тебуется найти безусловный минимум функции f(x) одной переменной, т.е. такую точку , что .

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

Определение. Точка производит «золотое сечение» отрезка, если отношение длины всего отрезка к большей части равно отношению большей части к меньшей.

Рассмотрим для простоты отрезок [0,1] единичной длины.

Ясно, что на отрезке имеется две таких точки и , они симметричны относительно концов. Точка производит золотое сечение отрезка [A,C] , а точка производит золотое сечение отрезка [BD]. Положим |AB|= x. Тогда |BD|=1-x. В соответствии с определением точки «золотого сечения» имеем: . Решив эту пропорцию, получим .

Стратегия поиска.

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

Алгоритм.

Шаг 1. Задать начальный интервал неопределенности и требуемую точность .

Шаг 2. Положить k=0.

Шаг 3. Вычислить точки , .

Шаг 4. вычислить значения : ,

Шаг 5. Сравнить значения и :

а) если , исключить интервал , положить . Перейти к шагу 6.

б) если > , то исключить интервал , положить

.

Перейти к шагу 6.

Шаг 6. Вычислить

а) если , то поиск завершен . В качестве приближения можно взять середину этого интервала .

б) если то положить k=k+1 и перейти к шагу 4.

Сходимость.

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

Пример.

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

Решение.