Green-sell.info

Новые технологии
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Метод парабол оптимизация

XII Международная студенческая научная конференция Студенческий научный форум — 2020

ИСПОЛЬЗОВАНИЕ УНИВЕРСАЛЬНОГО АЛГОРИТМА В МЕТОДЕ ПАРАБОЛ ПРИ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ

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

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

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

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

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

2. Основная идея квадратичной аппроксимации

Основной идеей метода являетсяприближенная аппроксимация, применяемая для целевой функции F ( x ), в которой применяется квадратическая парабола, имеющая вид P 2 ( x ) = C + C 1 x + C 2 x 2 .В силу того, что число неизвестных постоянных коэффициентов равно 3, для построения такой параболы требуется также задать три точки на плоскости. Как правило – это граничные точки исходного интервала[ a,b ], а также некоторая точка внутри его.

При этом набор уравнений для расчета неизвестных коэффициентов параболы принимает вид:

Искомая x экстр минимума на параболе (в случае C 2 >0 ) находится для дифференцируемой функции в стационарной точке, в которой удовлетворяется условие вида: P 2 ( x экстр ) = 2 C 2 x экстр + C 1 = 0 .

Вышеприведенные зависимости дают следующие формулы:

Такой метод достаточно точноприближает дифференцируемую функцию F(x) , поскольку в окрестности точки искомого минимума функция может быть разложена в ряд Тейлора 2-го порядка:

через o (( х-с ) 2 ) обозначено остаточное значение малого порядка.

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

1. Получаемые в результате аппроксимации точки могут уйти с довкерительного интервала.

2. Для недифференцируемой функции сходимость может быть очень медленной.

3. В тех случаях, когда точки для аппроксимации( a,F ( a )) , ( b,F ( b )) , ( c,F ( c ))попадают на одну прямую, метод вообще не работает.

лежат на одной прямой (например, у функции, график которой имеет вид ломаной), то

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

3.Исправленный универсальный алгоритм метода парабол

Назовем исправленный вариант метода универсальным .

1) [ a,b ] – границы заданного интервала,

Шаг 1 . Выяснениеблизостиимеющейся внутренней к крайним и ее коррекция.

Если ( с-a )/( b-a ) 0 переход на Шаг 5 либо 6.

Шаг 5 . C 2 . В этом случае парабола направлена вверх и в точке x экстр — локальный минимум.

Оценка близости пробной точки к средней точке c и соответствующая коррекция доверительного интервала.

Данная ситуация возникает, например, уже на втором шаге, если F(x) сама является квадратичной параболой.

Если a 3 2 на интервале [0,2;2]при помощи универсального алгоритма метода парабол с заданной внутренней точкой интервала с=0,4 при точности =0,5.

Решение . При последовательном выполнении шагов переходы к ним не оговариваются.

Шаг 0. Предварительные действия. Рассчитываем значения функции в точках a,b,c: F(a)=-0,10; F(с)=-0,35; F(b)=4.

Итерация 1. Шаг 1. Условия (с-a)/(b-a) 0 то переход на Шаг 6.

Шаг 6. В результате проверки выхода x экстр за пределы отрезка [a,b] и близости к средней точке c, выявлено, что ни одно из этих условий не выполняется, поэтому x min := x экстр .

Сокращение доверительного интервала.

Так как x min 2 – 10 3 и выше в среднем работает быстрее метода Фибоначчи – наиболее быстрого регулярного метода.. Поскольку сам он не является регулярным, для него в общем случае нет оценок скорости сходимости.

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

1. Аттетков А.В. Методы оптимизации / А.В.Аттетков, В.С. Зарубин, А.Н.Канатников.- М.: ИЦ РИОР, НИЦ ИНФРА-М,2013.-270 с.

2. Корнеенко В.П. Методы оптимизации / В.П. Корнеенко.- М.: Высшая школа, ИНФРА-М,2007.-664 с.

3. Измаилов А.Ф. Численные методы оптимизации / А.Ф. Измаилов, М.В.Солодов — М.: Физматлит, 2008.-320 с.

4. Гданский Н.И., Карпов А.В., Марченко Ю.А. Оптимальное равномерное приближение произвольных непрерывных функций при помощи ломаных линий. Математические методы в технике и технологиях – ММТТ-23. Сб. трудов ХХIII МНК.: в 12 т.- Т.2. Секция 5 /под ред. В.С. Балакирева. Саратов, СГТУ, 2010, с. 32-36.

Методы одномерной оптимизации;

Эти методы строятся в предположении унимодальности функции F(x) на заданном интервале [a, b]. К функции не предъявляются требования непрерывности или дифференцируемости, предполагается лишь, что для любого x Î [a, b] значение F(x) может быть вычислено.

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

ü Методы последовательного поиска (методы сокращения интервалов, методы исключения интервалов)

Методы этой группы нацелены на построение такой стратегии поиска x*, при которой любая пара вычислений F(x) позволяет сузить область поиска (или интервал неопределенности). Вычисляя F(x) в точках x1 и x2 таких, что a

Основное различие между методами последовательного поиска состоит в стратегиях выбора значений x1 и x2.

· Метод дихотомии (половинного деления) – один из самых простых методов последовательного поиска.

Метод половинного деления (метод дихотомии) проиллюстрирован ниже.

· Метод золотого сечения предполагает такое сокращение интервала на каждом шаге, что отношение целого к большей части было равно отношению большей части к меньшей. Это отношение, равное 1.618, и называют «золотым сечением». (1 : 0,618 = 1,618; 0.618 : 0,382 = 1,618)

Значение коэффициента К (0,382) подобрано так, что в полученном отрезке меньшей длины одна из промежуточных точек совпадет с промежуточной точкой от предыдущего шага. Это позволяет сократить число вычислений целевой функции на всех шагах (кроме первого) в 2 раза.

Таким образом, требуется не более N шагов и N+1 вычисление целевой функции, где N можно рассчитать, используя соотношение (b–a)/ε = (1–a)N при заданной погрешности ε определения экстремума.

· Метод чисел Фибоначчи

Стратегия поиска связана с использованием чисел Фибоначчи, которые можно получить из рекуррентного соотношения Rk = Rk-1 + Rk-2 , k = 2, 3, …, R = R1 = 1. В отличие от метода золотого сечения, здесь коэффициент сокращения интервала изменяется от итерации к итерации, хотя он также близок к значению 0.382.

Читать еще:  Оптимизатор памяти для андроид

Норенков-2000: Согласно методу чисел Фибоначчи, используют числа Фибоначчи Ri, последовательность которых образуется по правилу Ri+2 = Ri+1 + Ri при R = R1 = 1, т.е. ряд чисел Фибоначчи имеет вид 1, 1, 2, 3, 5, 8, 13, 21, 34, . Метод аналогичен методу золотого сечения с тем отличием, что коэффициент K равен отношению Ri-2 /Ri, начальное значение i определяется из условия, что Ri должно быть наименьшим числом Фибоначчи, превышающим величину (b–a)/ε, где ε — заданная допустимая погрешность определения экстремума. Так, если (b–a)/ε = 100, то начальное значение i = 12, поскольку R12 = 144, и K = 55/144 = 0,3819, на следующем шаге будет K = 34/89 = 0,3820 и т.д.

Основной недостаток метода – необходимость задания числа шагов. Основное преимущество – быстрое сужение интервала неопределенности: при числе шагов n = 14 интервал неопределенности примерно в 5 раз меньше, чем получаемый по методу половинного деления. В то же время по сравнению с методом золотого сечения метод Фибоначчи позволяет получить интервал только на 17% меньше, и при большом числе шагов оба эти метода практически идентичны.

ü Методы полиномиальной аппроксимации

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

· Метод квадратичной интерполяции – один из популярных методов этой группы.

Метод заключается в замене нелинейной функции F(x) квадратичной параболой F2(x), построенной по трем точкам, принадлежащим F(x), так, чтобы значения аппроксимирующей функции F2(x) совпали со значениями F(x) в этих трех точках. Минимум квадратичной функции находится с использованием аналитического условия оптимальности: df/dx = 0.

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

В этих точках вычисляется f(x) и по полученным точкам f(x1), f(x2), f(x3) строится парабола

коэффициенты которой находятся из решения соответствующей системы уравнений:

Условие оптимальности приводит к уравнению x4 = – C1 / 2C2 , где х4 – точка минимума параболы f2(x).

Далее выбирается новый отрезок, внутри которого находится точка х4, и c использованием х3, х4 строится новая парабола, по которой уточняется положение минимума f(x), и т. д. до тех пор, пока величина отрезка, внутри которого находится оптимум, не станет меньше заданной погрешности e. Таким образом, метод имеет итерационный характер.

К достоинствам метода относится высокая скорость сходимости, хотя метод может не всегда сходиться.

Например, на рис. ниже показана ситуация (для случая максимизации функции), когда метод параболической аппроксимации сходится к решению уже на третьем этапе: парабола 3, построенная по точкам х3, х4, х5, практически совпадает с исходной функцией 1.

Пример. Найти максимум функции f(x) = sin (x + 1)на интервале [-1; 2], точность e = 0,01.

Решение. Для построения аппроксимирующей параболы находим точки

Система уравнений для нахождения коэффициентов параболы примет вид:

Решение системы можно найти любым из известных способов, например, по формулам Крамера. На первом шаге получаем = 0,5571, f( ) = 0.9999. По этой точке, а также по второй и третьей исходным точкам, лежащим по обе стороны от точки максимума параболы, аналогично строится вторая парабола.

Методы одномерной оптимизации

Метод сканирования заключается в последовательном переборе всех значений х на [a,b] с шагом ε и вычислении критерияоптимальности R в каждой точке. Точка, в которой R принимает максимальное значение, принимается за решение задачи оптимизации.

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

Главный недостаток метода – возможность пропуска «острого» глобального максимума.

Метод дихотомии (половинного деления) заключается в делении заданного отрезка на две равные части с последующим выбором одной из них, в которой локализуется экстремум. Выбор отрезка осуществляется путем сравнения двух значений критерия оптимальности в точках, отстоящих от середины отрезка на ε/2.

Пусть х – середина [a,b]. Если R(x+ ε/2)=R(x- ε/2), то максимум достигается в точке х. Если R(x+ ε/2)>R(x- ε/2), то максимум располагается на правой половине текущего отрезка и для дальнейшего поиска выбирается отрезок [x- ε/2, b], в противном случае –
[a, x+ ε/2].

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

Метод золотого сеченияоснован на делении текущего отрезка [a,b]на неравные части, подчиняющиеся правилу золотого сечения, с последующим выбором отрезка, содержащего экстремум.

Золотое сечение определяется по правилу: отношение всего отрезка к большей части равно отношению большей части к меньшей. Этому правилу удовлетворяют две точки c и d , расположенные симметрично относительно середины отрезка: . Если R(c)>R(d), то для поиска максимума выбирается [a,d], в противном случае – [c,b]. Процесс поиска завершается при достижении отрезком, на котором находится экстремум, величины ε.

В методе парабол предлагается аппроксимировать оптимизируемую функцию f(x) с помощью квадратичной функции

Пусть имеются три точки x1

Минимум такой параболы равен

Если ,то точка u гарантированно попадает в интервал

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

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

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

Словесный алгоритм метода следующий:

Заданы начало и конец интервала.

Шаг 1.Рассчитывается количество итераций и формируется массив чисел Фибоначчи.

Шаг 2.Рассчитываются две точки и и значения в них целевой функции и, где – длина интервала.

, , ,

и рассчитывается одна новая точка

, ,

, , ,

и рассчитывается одна новая точка

Читать еще:  Виды оптимизационных задач

, .

Шаг 4. .

Шаг 5.Повторять шаги 1-3 до тех пор, пока .

Шаг 6.Результат .

11. Градиентные методы многомерной оптимизации

Метод покоординатного спуска (градиента) формирует шаг по переменным как функцию от градиента R(x) в текущей точки последовательности. Градиент – это вектор из частных производных, который показывает направление и скорость возрастания функции.

Алгоритм поиска minR(x) в векторной форме записывается в виде: , или в скалярном виде: , где h – величина рабочего шага, i – номер шага. Поиск максимума можно производить в обратном направлении градиента, т.е. или заменить на поиск минимума противоположной функции.

Выбор величины рабочего шага в направлении градиента зависит от величины градиента и сильно влияет на эффективность метода. Существует ряд алгоритмов коррекции величины h. Остановимся на выборе постоянного рабочего шага.

Для оценки частных производных можно применить алгоритм с парными пробами:

, где gj– пробный шаг по j-й переменной, выбираемый достаточно малым.

Условием окончания поиска может являться , где

Основным недостатком метода является необходимость частого вычисления производных.

Метод наискорейшего спуска сочетает в себе метод градиента и методы одномерной оптимизации.

1. Выбирается начальная точка.

2. В текущей точке вычисляется градиент.

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

4. Повторяются пункты 2 и 3 до выполнения условия окончания

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

Метод Симпсона (парабол)

При вычислении определенного интеграла не всегда получаем точное решение. Не всегда удается представление в виде элементарной функции. Формула Ньютона-Лейбница не подходит для вычисления, поэтому необходимо использовать методы численного интегрирования. Такой метод позволяет получать данные с высокой точностью. Метод Симпсона является таковым.

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

Метод парабол – суть, формула, оценка, погрешности, иллюстрации

Задана функция вида y = f ( x ) , имеющая непрерывность на интервале [ a ; b ] , необходимо произвести вычисление определенного интеграла ∫ a b f ( x ) d x

Необходимо разбить отрезок [ a ; b ] на n отрезков вида x 2 i — 2 ; x 2 i , i = 1 , 2 , . . . , n с длиной 2 h = b — a n и точками a = x 0 x 2 x 4 . . . x 2 π — 2 x 2 π = b . Тогда точки x 2 i — 1 , i = 1 , 2 , . . . , n считаются серединами отрезков x 2 i — 2 ; x 2 i , i = 1 , 2 , . . . , n . Данный случай показывает, что определение узлов производится через x i = a + i · h , i = 0 , 1 , . . . , 2 n .

Суть метода парабол

Каждый интервал x 2 i — 2 ; x 2 i , i = 1 , 2 , . . . , n подынтегральной функции приближен при помощи параболы, заданной y = a i x 2 + b i x + c i , проходящей через точки с координатами x 2 i — 2 ; f ( x 2 i — 2 ) , x 2 i — 1 ; x 2 i — 1 , x 2 i ; f ( x 2 i ) . Поэтому метод и имеет такое название.

Данные действия выполняются для того, чтобы интеграл ∫ x 2 i — 2 x 2 i a i x 2 + b i x + c i d x взять в качестве приближенного значения ∫ x 2 i — 2 x 2 i f ( x ) d x . Можем вычислить при помощи формулы Ньютона-Лейбница. Это и есть суть метода парабол. Рассмотрим рисунок, приведенный ниже.

Графическая иллюстрация метода парабол (Симпсона)

При помощи красной линии изображается график функции y = f ( x ) , синей – приближение графика y = f ( x ) при помощи квадратичных парабол.

Вывод формулы метода Симпсона (парабол)

Исходя из пятого свойства определенного интеграла получаем ∫ a b f ( x ) d x = ∑ i = 1 n ∫ x 2 i — 2 x 2 i f ( x ) d x ≈ ∑ i = 1 n ∫ x 2 i — 2 x 2 i ( a i x 2 + b i x + c i ) d x

Для того чтобы получить формулу методом парабол, необходимо произвести вычисление:

∫ x 2 i — 2 x 2 i ( a i x 2 + b i x + c i ) d x

Пусть x 2 i — 2 = 0 . Рассмотрим рисунок, приведенный ниже.

Изобразим, что через точки с координатами x 2 i — 2 ; f ( x 2 i — 2 ) , x 2 i — 1 ; x 2 i — 1 , x 2 i ; f ( x 2 i ) может проходить одна квадратичная парабола вида y = a i x 2 + b i x + c i . Иначе говоря, необходимо доказать, что коэффициенты могут определяться только единственным способом.

Имеем, что x 2 i — 2 ; f ( x 2 i — 2 ) , x 2 i — 1 ; x 2 i — 1 , x 2 i ; f ( x 2 i ) являются точками параболы, тогда каждое из представленных уравнений является справедливым. Получаем, что

a i ( x 2 i — 2 ) 2 + b i · x 2 i — 2 + c i = f ( x 2 i — 2 ) a i ( x 2 i — 1 ) 2 + b i · x 2 i — 1 + c i = f ( x 2 i — 1 ) a i ( x 2 i ) 2 + b i · x 2 i + c i = f ( x 2 i )

Полученная система разрешается относительно a i , b i , c i , где необходимо искать определитель матрицы по Вандермонду. Получаем, что

( x 2 i — 2 ) 2 x 2 i — 2 1 x 2 i — 1 ) 2 x 2 i — 1 1 ( x 2 i ) 2 x 2 i 1 , причем он считается отличным от нуля и не совпадает с точками x 2 i — 2 , x 2 i — 1 , x 2 i . Это признак того, что уравнение имеет только одно решение, тогда и выбранные коэффициенты a i ; b i ; c i могут определяться только единственным образом, тогда через точки x 2 i — 2 ; f ( x 2 i — 2 ) , x 2 i — 1 ; x 2 i — 1 , x 2 i ; f ( x 2 i ) может проходить только одна парабола.

Можно переходить к нахождению интеграла ∫ x 2 i — 2 x 2 i ( a i x 2 + b i x + c i ) d x .

f ( x 2 i — 2 ) = f ( 0 ) = a i · 0 2 + b i · 0 + c i = c i f ( x 2 i — 1 ) = f ( h ) = a i · h 2 + b i · h + c i f ( x 2 i ) = f ( 0 ) = 4 a i · h 2 + 2 b i · h + c i

Для осуществления последнего перехода необходимо использовать неравенство вида

∫ x 2 i — 2 x 2 i ( a i x 2 + b i x + c i ) d x = ∫ 0 2 h ( a i x 2 + b i x + c i ) d x = = a i x 3 3 + b i x 2 2 + c i x 0 2 h = 8 a i h 3 3 + 2 b i h 2 + 2 c i h = = h 3 8 a i h 2 + 6 b i h + 6 c i = h 3 f x 2 i — 2 + 4 f 2 2 i — 1 + f x 2 i

Значит, получаем формулу, используя метод парабол:

∫ a b f ( x ) d x ≈ ∑ i = 1 n ∫ x 2 i — 2 x 2 i a i x 2 + b i x + c i d x = = ∑ i = 1 n h 3 ( f ( x 2 i — 2 ) + 4 f ( x 2 i — 1 ) + f ( x 2 i ) ) = = h 3 f ( x 0 ) + 4 f ( x 1 ) + f ( x 2 ) + f ( x 2 ) + 4 f ( x 3 ) + f ( x 4 ) + . . . + + f ( x 2 n — 2 ) + 4 f ( x 2 n — 1 ) + f ( x 2 n ) = = h 3 f ( x 0 ) + 4 ∑ i = 1 n f ( x 2 i — 1 ) + 2 ∑ i = 1 n — 1 f ( x 2 i ) + f ( x 2 n )

Формула метода Симпсона имеет вид ∫ a b f ( x ) d x ≈ h 3 f ( x 0 ) + 4 ∑ i = 1 n f ( x 2 i — 1 ) + 2 ∑ i = 1 n — 1 f ( x 2 i ) + f ( x 2 n ) .

Формула оценки абсолютной погрешности имеет вид δ n ≤ m a x [ a ; b ] f ( 4 ) ( x ) · ( b — a ) 5 2880 n 4 .

Примеры приближенного вычисления определенных интегралов методом парабол

Метод Симпсона предполагает приближенное вычисление определенных интегралов. Чаще всего имеются два типа задач, для которых применим данный метод:

  • при приближенном вычислении определенного интеграла;
  • при нахождении приближенного значения с точностью δ n .

На точность вычисления влияет значение n , чем выше n , тем точнее промежуточные значения.

Вычислить определенный интеграл ∫ 0 5 x d x x 4 + 4 при помощи метода Симпсона, разбивая отрезок интегрирования на 5 частей.

По условию известно, что a = 0 ; b = 5 ; n = 5 , f ( x ) = x x 4 + 4 .

Тогда запишем формулу Симпсона в виде

∫ a b f ( x ) d x ≈ h 3 f ( x 0 ) + 4 ∑ i = 1 n f ( x 2 i — 1 ) + 2 ∑ i = 1 n — 1 f ( x 2 i ) + f ( x 2 n )

Чтобы применить ее в полной мере, необходимо рассчитать шаг по формуле h = b — a 2 n , определить точки x i = a + i · h , i = 0 , 1 , . . . , 2 n и найти значения подынтегральной функции f ( x i ) , i = 0 , 1 , . . . , 2 n .

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

h = b — a 2 n = 5 — 0 2 · 5 = 0 . 5

Найдем значение функции в точках

i = 0 : x i = x 0 = a + i · h = 0 + 0 · 0 . 5 = 0 ⇒ f ( x 0 ) = f ( 0 ) = 0 0 4 + 4 = 0 i = 1 : x i = x 1 = a + i · h = 0 + 1 · 0 . 5 = 0 . 5 ⇒ f ( x 1 ) = f ( 0 . 5 ) = 0 . 5 0 . 5 4 + 4 ≈ 0 . 12308 . . . i = 10 : x i = x 10 = a + i · h = 0 + 10 · 0 . 5 = 5 ⇒ f ( x 10 ) = f ( 5 ) = 5 5 4 + 4 ≈ 0 . 00795

Наглядность и удобство оформляется в таблице, приведенной ниже

Сравнение методов одномерной оптимизации: метод золотого сечения и метод квадратичной параболы

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

Задача в виде, пригодном для решения методом оптимизации, состоит в минимизации (максимизации) вещественнозначной функции f(x) N-мерного аргумента x. Такая задача называется задачей условной оптимизации. Если задача не содержит ограничения и рассматривается на всем пространстве, то это задача безусловной оптимизации. Задачи без ограничений с N = 1 называются задачами одномерной оптимизации, с N 2 — многомерной оптимизации.

Задачей одномерной оптимизации является поиск локального минимума целевой функции f(х) вдоль заданного направления.

Задача нахождения минимума функции одной переменной min f(x) нередко возникает в практических приложениях. Кроме того, многие методы решения задачи минимизации функции многих переменных сводятся к многократному поиску одномерного минимума. Поэтому разработка все новых, более эффективных одномерных методов оптимизации продолжается и сейчас, несмотря на кажущуюся простоту задачи.

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

Читать еще:  Дефрагментация и оптимизация дисков

Введем некоторые определения:

Монотонность функции. Функция f(x) является монотонной на интервале, если для любых x1 и x2 из этого интервала, таких, что x1 f(x2), если функция монотонно убывающая.

Унимодальность. Функция f(x) является унимодальной на отрезке, если она монотонна по обе стороны от единственной на отрезке точки х, то есть функция f(x) в полуинтервале [а,х) убывает, а в полуинтервале (х,b] возрастает. Примеры графиков унимодальных функций приведены на рис. 1.

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

Рис. 1. Графики унимодальных функций

Определение глобального минимума. Функция f(x), определённая на множестве D, достигает глобального минимума в точке x* D, если f(x*) 0( 0. Однако проверка выполнения этого условия не всегда возможна. Достаточным условием монотонной сходимости метода Ньютона будут постоянство в интервале между точками x и х* знака производной f»'(x) и совпадение его со знаком f'(x). Оказывается, что в этом случае метод Ньютона обладает квадратичной скоростью сходимости в некоторой окрестности точки х*.

Метод секущих похож на метод Ньютона, но строится не касательная к графику производной, а секущая. Геометрическая интерпретация этого метода состоит в том, что в качестве очередного приближения xk+1 выбирают точку пересечения с осью абсцисс секущей к графику функции f'(x).

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

Метод кубической аппроксимации

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

Пусть для непрерывно дифференцируемой функции f(x), строго выпуклой на отрезке [x1, x2], известны значения y1 = f(x1), y2 = f(x2) функции и значения ее производной y11 = f'(x1), y12 = f'(x2). Если y11*y12 2 +-1=0 (2)

Рис. 2. Золотое сечение отрезка.

Из определения золотого сечения следует, что .
Действительно,

Алгоритм золотого сечения.

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

1. Выполняем присваивания:

r = 1, a 1 = a, b 1 = b,

2. Вычисляем величины (Рис. 3)

3. Вычисляем значения f(), f() функции f(x).

4. Если f() r+1 = a r , b r+1 = ,

Иначе — выполняем присваивания

a r +1 = , b r +1 = r ,

5. Если , то заканчиваем вычисления. Иначе — выполняем присваивание r=r+1 и переходим на п.2. Здесь — требуемая точность решения

Рис. 3. Определение величин ,

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

Некоторые свойства алгоритма золотого сечения:

Точки , расположены симметрично относительно концов текущего интервала неопределенности.

Действительно, из (3) следует, что точка отстоит от точки b r на величину (b r -a r ); точка отстоит от точки a r на ту же величину.

Для любого r?1 алгоритм золотого сечения обладает следующим свойством: одна из точек , совпадает с одной из точек ,.

Пусть на r-й итерации f() r ,] причем, очевидно, ТИНr+1. Для того, чтобы доказать справедливость утверждения достаточно показать, что верно отношение:

Из соотношений (3) следует, что

(b r — ) = (b r — a r )

b r — — a r + a r = (b r — a r )

(b r — a r )-(-a r )=(b r — a r )

— a r = (b r — a r )(1-)

Разделив первый из этих результатов на второй, получим

Из уравнения (2) следует, что 1- = 2 . Отсюда и из (5) следует справедливость (4). Аналогично проводится доказательство для случая f() > f().

Указанное свойство алгоритма золотого сечения позволяет на каждой итерации (кроме первой) производить испытания только в одной точке.

В результате одной итерации алгоритма золотого сечения длина текущего интервала неопределенности сокращается в раз.

Поэтому количество итераций N, необходимых для нахождения минимума функции с точностью x, находится из условия x ? (b-a) N

2.2 Метод квадратичной параболы

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

Рассмотрим квадратичную аппроксимацию (рис. 4). Пусть в процессе решения задачи поиска минимума функции f(x) тем или иным образом получены попарно не совпадающие точки x1, x2, x3, принадлежащие области допустимых значений D (не обязательно упорядоченные слева направо).

Рис. 4. Квадратичная аппроксимация

Построим квадратичную функцию

Коэффициенты a,b,c функции (6) удовлетворяют системе линейных алгебраических уравнений (СЛАУ)

Определитель СЛАУ (7) является определителем Вандермонда, который отличен от нуля, если величины x1,x2,x3 попарно различны.

Таким образом, в сделанных предположениях СЛАУ (7) имеет решение и притом единственное. Поскольку определитель СЛАУ (7) равен ), это решение имеет вид:

Подставим найденные значения коэффициентов a,b,c в необходимое условие y’=2ax+b=0 минимума квадратичной функции (6), получим стационарную точку этой функции:

Метод квадратичной аппроксимации.

Рассмотрим следующую задачу условной оптимизации: найти минимум одномерной унимодальной функции f(x), определенной в замкнутой области допустимых значений D=[a,b],

Метод квадратичной аппроксимации относится к классу методов сокращения текущего интервала неопределенности. Пусть при решении задачи (8) каким-либо методом получены три точки x1 f(x2) r и находим значение функции f(x) в этой точке r = f( r )

4. Находим следующие три точки:

случай (а) — если r [, ], то = , = r , = (рис. 5а);

случай (б) — если r [, ], то = , = r , = (рис. 5б).

5. В качестве следующего текущего интервала неопределенности принимаем

6. Если , то заканчиваем вычисления. Иначе — выполняем присваивание r=r+1 и переходим на п.2. Здесь — требуемая точность решения.

Рис. 5. Метод квадратичной аппроксимации:

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

В силу условий , точка r всегда принадлежит текущему интервалу неопределенности ТИНr = [].

Текст программы метода квадратичной параболы размещен в Приложении 1. Блок-схема алгоритма представлена в Приложении 2.

3. Полученные результаты

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

Минимизировать функцию f(x)=x 2 +2x на интервале (-3,5). Допустимая погрешность = 0,2.

Ссылка на основную публикацию
Adblock
detector