Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 50

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

Текст из файла (страница 50)

Из уравнения Р'(х«<'«) = 2р< ">(х<"'> .— х< "<) + и< "< = О 2 получается формула и< "< х<""« = х<х< — — ~-. 2р'~< ' (9.18) Естественно, что для начала работы этого метода требуется выбор трех начальных приближений х<0>, х<<>; х<~~. Пусть функция ~трижды непрерывно дифференцируема в некото- рой окрестности точки х и удовлетворяет в ней условию ~"(х) > О. Можно показать, что в этом случае выбор начальных приближений х<0<, х<«, х<~1 из достаточно малой окрестности точки х гарантирует, что р<~«Ф О для всех х и метод последовательной параболической интерполяции сходится сверхлинейно, с порядком, приближенно равным 1.324.

Поэтому в качестве критерия окончания итерационного процесса можно принять неравенство (9.17). Отметим, что в описанном методе используются только значения функции ~ вычисляемые в точках х< "<, Поэтому (как и для методов прямого поиска) при его реализации на ЭВМ достижимая точность метода ограничена снизу величиной, равной радиусу е интервала неопределенности.

После того как очередное приближение х< "< попа- дет в интервал (х — е, х + а), дальнейшие вычисления теряют смысл (см. ~ 9.2). Существуют различные модификации метода последовательной параболической интерполяции. Одна из них, например, обеспечивает принадлежность очередного приближения предыдущему отрезку лока- лизации и дает последовательность стягивающихся к точке х отрезков.

4. Гибридные алгоритмы. Лучшими среди универсальных методов одномерной минимизации считаются так называемые <ибридмме (или ре<уляризов«««ме) алгоритмы. Они представляют собой комбинации надежных, но медленно сходящихся алгоритмов типа бисекции (если возможно вычисление ~'(х)) или золотого сечения с быстро сходящимися методами типа последовательной параболической интерполяции или Ньютона. Эти алгоритмы обладают высокой надежностью и гарантированной сходимостью, причем сходимость становится сверхлинейной, если в окрестности точки строгого минимума функция / (х) достаточно гладкая.

260 Примером эффективного гибридного алгоритма является алгоритм у'М1И, изложенный в [86]. Алгоритм ГМ1М осуществляет поиск минимума методом золотого сечения, переключаясь по возможности на параболическую интерполяцию. $ 9.5. Доиолипггелъные замечания 1. Дополнительную информацию о методах одномерной минимизации можно найти, например, в пособии [18]. 2. Описанные выше методы приспособлены, как правило, для минимизации унимодальных функций.

Если эти методы применить для минимизации непрерывной функции, не являющейся унимодальной на рассматриваемом отрезке, то мы получим, вообще говоря, лишь точку локального экстремума. Поэтому такие методы часто называют локальными методами минимизации. К настоящему времени разработан ряд методов, которые предназначены для поиска глобального минимума. С некоторыми из них можно ознакомиться в [18]. 3. Решение задачи минимизации существенно усложняетсл, если на значения функции накладываются случайные ошибки (помехи).

Так бывает, например, тогда, когда значения функции получают в результате измерений какой-либо физической величины. В том случае, когда ошибки являются случайными величинами и обладают определенными вероятностными характеристиками, для поиска минимума можно использовать метод стпохастической аппроксимации Понятие об этом методе можно получить из [18]; там же содержатся ссылки на соответствующую литературу. Глава 10 МЕТОДЫ МНОГОМЕРНОЙ МИНИМИЗАЦИИ Одной из наиболее часто встречающихся в инженерных расчетах и научных исследованиях вычислительных задач является задача минимизации' функции т действительных переменных 1 (хг, хт, ..., х„). Функция 1(целевая функция) минимизируется на некотором множестве Х С Ю».

В случае, когда Х = 1»г» (т. е. ограничения на переменные хг, х2,, х„отсутствуют) принято говорить о задаче безусловной минимизации. В противном случае (т. е. тогда, когда Х Ф .Кг») говорят о задаче условной иинимизации. В данной главе рассматриваются методы решения задачи безусловной минимизации. Многие из них являются основой для перехода к более сложным методам решения задач условной минимизации.

З 10.1. Задача безусловной минимизации функции многих переменных 1. Постановка задачи. Определения. Пусть 1(х) = 1(хг, хз, ..., х,„)— действительная функция многих переменных, определенная на множестве Х С Ю». Точка х Е Х называется точкой глобального минимума функции 1 на множестве Х, если для всех х Е Х выполняется неравенство 1(х) < 1(х). В этом случае значение 1 (х) называется минималънъгм значением функции 1 на Х. Точка х Е Х называется точкой локалъного минимума функции 1, если существует такая б окрестность Уб этой точки, что для всех 1 Как н в случае одной переменной, задача максимизации сводится к задаче минимизации заменой функции 1'на -1 262 е Х = Х П б~ выполняется неравенство ~(*) 4 ~(х). Если же для всех х Е Х~ (х Ф х) выполняется строгое неравенство 1(х) < ~(х), то х называется точкой стро1о1о локалъно1о минимуиа. Подавляющее большинство методов решения задачи безусловной минимизации в действительности являются методами поиска точки локального минимума.

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

2. Поверхность уровня, градиент и матрица Гессе. Необходимые и достаточные условия локального минимума. Напомним некоторые определения и факты, известные из стандартного курса теории функций многих переменных. Множество точек, для которых в целевая функция принимает постоянное значение ~ (х) = с, называется поверхностью уровня. В случае т = = 2 это множество называют линией уровня. На рис. 10.1 показано, как получаются линии уровня для функции двух переменных.

Функция ~~х1, ха) задает в трехмерном пространстве некоторую поверхность и = ~(х1, хг), низшая точка которой и дает решение задачи минимизации. Для того чтобы изобразить рельеф Рис. 10.1 этой поверхности, проведем несколько равноотстоящих плоскостей и = сопй. Проекции на плоскость Ох1х~ линий пересечения этих плоскостей с поверхностью и дают линии уровня. Для дифференцируемой функции определен вектор из первых частных производных ~дх1 ' дхэ ' "' дх ~ дУ дУ дУ 1т 263 Г радасня который называется ирадисято.е. (н"~ Х" Ю~ Если в точке х градиент не равен ф нулю, то он, как известно, пер Яичная араднн„ пендикулярен проходящей через ~М-1Й")мн" эту точку поверхности уровня и указывает в точке х направление Рис.

10.2 наискорейшего возрастания функции. Вектор — у (х) называется антиьрадиснтпом и указывает направление наискорейшего убывания функции (рис. 10.2). Известно также, что равенство нулю градиента в точке х является необходимым условием того, чтобы внутренняя для множества Х точка х была точкой локального минимума дифференцируемой функции 1 Точка х, для которой выполняется равенство Аеииград ф~ н~~ 1'(х) = О, (10.1) д1 — (х~, х2, ...„ха) = О, дх~ (10.2) — (хпх2, ...,х„) =О. д1 ~3В Однако не всякая стационарная точка является точкой локального минимума.

Пусть функция 1 дважды непрерывно дифференцируема. Тогда достаточным условием того, чтобы стационарная точка х была точкой локального минимума, является положительная определенность' матрицы — 2(х) -. — (х) д2~ д2 г дх2 дх~ дх С( ) = Г(х) = (10.3) 1 д21 д21 — (х) ... — (х) дх„дх дх2 1 Определение положительно определенной симметричной матрицы см. в $ 5.3. 264 называется сгпационармой точкой функции 1. равенство (10.1) предс- тавляет собой систему т нелинейных уравнений относительно компо- нент хп х2, ..., ха вектора х, имеющую вид составленной из вторых частных производных функции ~ Матрицу (10.3) принято называть матприцей Гессе~.

3. Выпуклые функции Понятие выпуклости ц играет значительную роль в теории методов минимизации. Функция ~ называется старо~о омвуклой, если для любых в Ф у, 0 < Л ( 1 выполняется неравенство у(Л *+ (1 — Л)у) < Л Дв) + (1 — Л) 1 (у). Это определение имеет наглядный геометрический смысл — график функции ~ на интервале, соединяющем точки х и. у, лежит строго ниже хорды, проходящей через точки (а, ~(х)) и (у, Х(у)) (рис. 10.3). Для дважды непрерывно дифференцируемой функции положительная определенность матрицы Гессе ~"(в) является достаточным условием строгой выпуклости. Функция ~ называется сально выпуклой с постоянной ж > О, если для любых я, у, 0 ( Л < 1 выполнено неравенство Рис. 10.8 ~(Лв+ (1 — Л)у) < Л~(я) + (1 — Л) Ду) - — Л(1 — Л) ~т- у~2.

(10.4) где ж > 0 — постоянная, входящая в неравенство (10.4). 4. Задача минимизации квадратичной функции. Часто первоначальное исследование свойств методов безусловной минимизации проводится применительно к задаче минимизации квадратичной функции и я и Г(х~, х2, ..., ю„) = — Е Е а~рсх~- Е ~рь 2,=~ ~=~ (10.5) коэффициенты а;~ которой являются элементами симметричной поло- жительно определенной матрицы А. Используя матричные обозначе- ния, запишем функцию г' так: ~ Людвиг Отто Гессе (1811 — 1874) — немецкий математик. 265 Дважды непрерывно дифференцируемая функция ~ является сильно выпуклой тогда и только тогда, когда для всех х матрица Гессе удов- летворяет условию Вычислим градиент и матрицу Гессе для функции (10.5).

Характеристики

Список файлов книги