Лекция №33 Методы дихотомии и золотого сечения

Метод дихотомии

Метод дихотомии применяется для унимодальных функций. Метод дихотомии заключается в том, что исходный интервал [а,b] делится средней точкой на два подинтервала [а,с] и [с,b] в одном из которых лежит точка минимума .

Для выбора подинтервала, для хорошо дифференцируемой функции вычисляют в точке c производную и анализируют ее знак. Если , то лежит слева от точки c, т.е. В отрезке [а,с]; если , то лежит справа от точки c, т.е. В отрезке [с,b], а при найдена точка минимума .

Если не дифференцируемая, то выясняется направление убывания унимодальной функции. С этой целью задается точка с+h (где h>0 − малая величина, соизмеримая с ε и вычисляется ордината f₀(с+h).

Если приращение функции , то точка лежит справа от точки c, т.е. принадлежит отрезку [с,b].

Если , то точка лежит сktdf от точки c, т.е. принадлежит отрезку [a,c].

При имеем точку минимума .

После выбора подинтервала, в котором находится , например [с,b], переопределяем левую границу а=с (при выборе [а,с] следует поменять правую границу b=с).

Проверяем , если нет, то вновь делим отрезок [b-a] пополам и опять определяем, в каком подинтервале находится точка минимума.

Алгоритм поиска минимума:

1. Вводим границы [а,b] и ε. h = 100⋅ε.

2. Делим отрезок пополам с = (b+a)/2.

3. Вычисляем приращение функции . Если , то a=с, иначе если , то b=с.

4. Проверяем условие ? Если нет, то переходим на п.2, да – переход на п.5.

5. Печать: "точка минимума ", с, , . Конец.

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

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

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

Метод "золотого" сечения требует только унимодальности функции .

"Золотое" сечение, открытое Евклидом, состоит в разбиении интервала [а,b] точкой x₁ на две части таким образом, чтобы отношение большей части к длине всего интервала было равно отношению меньшей части к большей.

. (33.1)

Представим интервал [а,b] как совокупность двух отрезков:

. (7.2)

Разделив уравнение (33.2) на (b-а), получим:

.

Так как и , имеем , корни которого определяются по формуле:

т.е. .

Из уравнения (33.1) следует

. (33.3)

Проведем "золотое" сечение относительно точки а, получим

. (33.4)

Из уравнения (33.4) получим формулу для определения точки x₂:

. (33.5)

Заметим, что точка x₁ производит "золотое" сечение интервала [а,x₂], а точка x₂ – интервала [x₁,b].

Для унимодальной функции, зная значения функции в точках золотого сечения и , можно определить интервал неопределенности, в котором находится . После выбора на оставшемся интервале нужно определить только одну точку, производящую "золотое" сечение. Для выбранного интервала [а,x₂] следует положить b=x₂, x₂=x₁ и пересчитать точку x₁ по формуле (33.3), а для [x₁,b] – a=x₁, x₁=x₂ и пересчитать точку x₂ по формуле (33.5). На каждом шаге итерации длина интервала неопределенности уменьшается и составляет примерно 0,62 длины предыдущего интервала неопределенности. Итерационную процедуру следует закончить, когда длина интервала неопределенности станет меньше или равна заданной точности.

Алгоритм метода "золотого" сечения:

1. Ввод a, b, ε. Вычисляем значения x₁ и x₂ по формулам (33.3), (33.5).

2. Вычисляем и .

3. Если , то находится в интервале [а,x₂] (рис.33.1б), т.е. b=x₂. Переопределяем точки x₂=x₁ и f₂=f₁, пересчитываем точку x₁ по формуле (33.3) и вычисляем f₁. Переходим на п.4.

Если , то находится в интервале [x₁,b] (рис.33.1а), т.е. a=x₁, x₁=x₂, f₁=f₂. Пересчитываем точку x₂ по формуле (33.5) и вычисляем f₂.

4. Проверка (b–а)<ε, если нет, то переходим на п.3, да – на п.5.

5. Печать , оптимального значения критерия , для контроля правильности полученных данных.

Рис.33.1