Название: Информатика - Алгоритмы и программы (Н.В. Усольцев)

Жанр: Информатика

Просмотров: 972


2.3. методы трихотомии, фибоначчи и золотого сечения

В этих методах производится последовательное уменьшение интервала поиска  по двум значениям функции в промежуточных точках  и  .

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

Процедура итерационно повторяется, пока ширина интервала  не станет меньше заданной погрешности .

Суть различных методов заключается в оптимальном выборе точек   и . Их можно выбирать  равноотстоящими (метод трихотомии):

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

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

Метод Фибоначчи использует разбиение интервала в пропорции двух соседних чисел Фибоначчи. Эти числа образуют ряд: 1, 1, 2, 3, 5, 8, 13, 21, 34, …

В этом ряду каждое последующее значение равно сумме предыдущих    с начальными значениями .

В методе Фибоначчи  шаги выполняются в обратной последовательности n-1, n-2, n-3, …, 2.

На k-том шаге интервал делится в пропорции

где       - длина интервала на этом шаге. При выполнении любого из присваиваний  или  (см. выше) и выполнении нового разбиения одна из точек "остается на месте" и в ней нет необходимости повторно вычислять значение функции.

После исполнения цикла по k точки  и  сливаются в одну (т.к. , а ), которая и принимается за координату . Можно выполнить и параболическую интерполяцию по точкам ,  и .

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

Метод золотого сечения предполагает деление отрезка в отношении двух соседних чисел Фибоначчи при

 

Эти соотношения образуют известное "золотое сечение". Первоначально значения  и  рассчитываются по формулам:

                                  

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

 

 

Рис.1. Блок-схема алгоритма метода Фибоначчи. Входными данными алгоритма являются a и b - начальные границы интервала поиска и n - число повторений тела цикла. Выходными данными являются координата мин/макс  и значение функции в ней .

                                  

 

 

Рис.2. Блок-схема алгоритма метода золотого сечения. Входными данными алгоритма являются a и b - начальные границы интервала поиска и eps - погрешность поиска. Выходными данными являются координата мин/макс  и значение функции в ней .

 

3. Методы поиска min/max функции нескольких переменных

Методы поиска min/max функции нескольких переменных, в зависимости от требований к вычислению производных, можно разделить на:

методы нулевого порядка, требующие вычисления только самой функции;

методы первого порядка, требующие вычисления функции и расчета ее первых производных;

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

Методы более высоких порядков имеют большую эффективность. С ростом числа аргументов поиск усложняется.