Учебник - Практические занятия по вычислительной математике - Аристова (1238839), страница 19

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

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

Обе параболы методаБрендта в первой итерации дают близкие между собой результаты, весьма далекие от истинного положения минимума rmin = 21/6 d.Рис. 5.1. Одна итерация метода Брендта в применении к потенциалу Леннарда–Джонса при четырех точках начального приближенияa = d, b = 1.5d, c = 2d, d = 2.5dЗамечание. Количество достижимых верных знаков при поискекорней уравнения Φ(u) = 0 – это почти количество верных разрядов взадании переменной. Количество верных знаков при поиске положенияминимума вдвое меньше:1(u )  (u*)  (u*)(u  u*)2 ,2т.е. разницу в значениях функции можно увидеть только лишь при смещениях u – u*, при которых заметна величина (u – u*)2.122V.4.

Поиск минимума функции многих переменныхV.4. Поиск минимума функции многих переменныхV.4.1. Методы спускаОсновная идея методов спуска состоит в том, чтобы построить алгоритм, позволяющий перейти из точки начального приближенияu(0)  {u1(0) ,, un(0) } в следующую точку u(1)  {u1(1) , , un(1) } таким образом, чтобы значение целевой функции приблизилось к минимальному.Одним из способов достижения этой цели является использование методов минимизации функции одного переменного. В качестве этого переменного выступают либо поочередно координаты, либо параметр движения вдоль определенного направления в пространстве переменных.V.4.1.1.

Метод покоординатного спускаЭтот метод является редукцией поиска функции многих переменных к методам поиска функции одной переменной. Пусть u(0)  U –начальное приближение к положению минимума Φ(u).Рассмотрим Φ(u) = Φ(u1,…,un) как функцию одной переменной u1при фиксированных u2(0) , , un(0) и находим одним из приведенных методов поиска минимума функции одной переменнойmin (u1 , u2(0) ,u U1, un(0) ).Полученное значение u1, доставляющее минимум Ф(u1), обозначим u1(1) ;при этом(u1(1) , u2(0) ,, un(0) )  (u1(0) ,, un(0) ).Далее, при фиксированных значениях u1(1) , u3(0) ,min (u1(1) , u2 , u3(0) ,u2U, un(0) ищем, un(0) ) ,как функции от u2; соответствующее значение u2 обозначим u2(1) ; при этом(u1(1) , u2(1) , u3(0), un(0) )  (u1(1) , u2(0) ,123, un(0) ).V.

ЗАДАЧИ НАХОЖДЕНИЯ ЭКСТРЕМУМА ФУНКЦИИЭтот процесс продолжаем аналогичным образом и для оставшихсякоординат; в результате получим(u1(1) ,, un(1) )  (u1(1) ,, un(0) ).Таким образом, за цикл из n одномерных спусков переходим из точки u(0) в точку u(1). Этот процесс повторяется до тех пор, пока не будетвыполнено условие окончания вычислительного процесса, например:(u ( s 1) )  (u ( s ) )   ,где ε > 0 - заданная точность.Пример 1. Найти минимум функции двух переменных(u)  u12  u22 .Выбрав некоторую точку начального приближения, напримерu0 = (2, 2), получим минимум целевой функции за один цикл из двух шагов, так как ее линии уровня – окружности с центром в начале координат(рис.

5.2).(u1(1),u2(0))(u1(0),u2(0))(u1(1),u2(1))22Рис. 5.2. Метод покоординатного спуска для целевой функции (u)  u1  u2 .Окружностями изображены линии уровня целевой функции, пунктирнымистрелками – два шага метода покоординатного спускаПример 2. Если же целевой функцией является, например,(u)  5u12  5u22  8u1u2 ,124V.4.2. Метод градиентного спускакоторая поворотом системы координат на угол –45° и преобразованиемu1 v1  v2; u2 (v1  v2 )22приводится к виду (v)  v12  9v22 , то ее линиями уровня являются эллипсы v12 / 9  v22  с2 ,(рис.

5.3).поэтому спуск будет иметь иной характерu1(u1(1), u2(0))(u1(0), u2(0))1(u1(1), u2(1))u22Рис. 5.3. Метод покоординатного спуска для целевой функции(u)  5u12  5u22  8u1u2 , . Окружностями изображены линии уровня целевойфункции, пунктирными стрелками – шаги метода покоординатного спускаV.4.2. Метод градиентного спускаНапомним, что градиент функции  grad (u)  , ,uun  1есть вектор, ортогональный линиям уровня целевой функции, а егонаправление совпадает с направлением наибольшего роста Φ(u) в данной точке.

В точке минимума grad Φ(u) = 0.125V. ЗАДАЧИ НАХОЖДЕНИЯ ЭКСТРЕМУМА ФУНКЦИИМетод градиентного спуска основан на движении в направлениимаксимального убывания функции, т.е. в направлении – grad . Построим итерационный процесс следующим образом:u( s 1)  u( s)   grad ( s) , u(0)  a ,где τ – шаг спуска (итерационный параметр движения в направлениинаиболее быстрого убывания функции). Итерации продолжим до выполнения заданного условия окончания процесса поиска минимума, например,grad (u( s1) )  ,   0.Пример.

Рассмотрим функцию двух переменных(u1 , u2 )  u12 4  u22 .В соответствии с методом градиентного спуска получимu1( s 1)  u1( s )  u1( s ),2u2( s 1)  u2( s )   2u2( s ) .Пустьначальноеприближениеu(0)  {1;1} ;  0,1 ;тогда 0,95; 0,80; u  0,9025; 0,6400 ; u  0,8574;0,5120 ;Ф(u(0)) = 1,25; Ф(u(3)) = 0,446. Если взять τ = 2, то u(1) = {0, - 3} и(1)Ф(u ) = 9, в то время как min (u)  0 .

Выбор шага оказывается сущеu(1)(2)(3)Uственным в этом методе, поэтому чаще используются методы с переменным шагом.V.4.3. Метод наискорейшего спускаМетод наискорейшего спуска основан на поиске минимума функции одного переменного (τ) в направлении максимального убыванияфункции, т.е. в направлении –grad . Для этого в методе градиентногоспуска выберем шаг τ так, чтобы функция Φ(u) максимально уменьшаласвое значение:(u( s 1) )  min (u( s )   grad (u( s ) ))  min (, u( s ) ) .126V.4.3.

Метод наискорейшего спускаВ предыдущем примере выбор шага в точке u(0) сводится к задачепоиска минимума функции121   / 2   (1  2 )2 ,4откуда   10 9, поскольку( , u(0) ) 2u (0) 1(u )  (, u )   u1(0)   1   (u2(0)  2u2(0) )2 42 (1)(0) 1   / 2  4  (1  2)2 ,2u1(0)  u2(0)  1.На следующих шагах τ будет зависеть от ui( s ) , s > 0, i = 1, 2.Общий случай этого метода, а также метод сопряженных градиентов рассмотрены в части, посвященной численным методам решениясистем линейных алгебраических уравнений.Отметим следующее важное обстоятельство.

Решение экстремальных задач в Ln зачастую сопряжено со значительными трудностями, особенно для многоэкстремальных задач. Некоторые из этих трудностейисчезают, если ограничиться рассмотрением только выпуклых функцийна выпуклых множествах.Определение. Функция Φ(u), заданная на выпуклом множествеU  Ln, называется выпуклой, если для любых точек u, v  U и любого α  [0, 1] выполнено u  (1  )v  (u)  (1  )(v).Опр е де ле н ие .

Функция Φ(u) называется строго выпуклой, еслидля всех α  [0, 1] выполнено строгое неравенство u  (1  )v  (u)  (1  )(v).Это определение имеет наглядный геометрический смысл: графикфункции Φ(u) на интервале, соединяющем точки u, v, лежит ниже хорды,проходящей через точки {u,Φ(u)} и {v,Φ(v)}.127V. ЗАДАЧИ НАХОЖДЕНИЯ ЭКСТРЕМУМА ФУНКЦИИРис. 5.4. К определению выпуклости функцииДля дважды непрерывно дифференцируемой функции Φ(u) положительная определенность матрицы Гессе u (u ) есть достаточное условие строгой выпуклости.Теорема. Пусть Φ(u) – выпуклая функция на выпуклом множестве U, u  U. Тогда любой ее локальный минимум на U является одновременно и глобальным.Глобальный минимум строго выпуклой функции Φ(u) на выпукломмножестве U достигается в единственной точке.Доказательство . Предположим противное, т.е. u0 – точка локального, а u* – глобального минимума Φ(u) на U, u* ≠ u0 и Ф(u0) > Ф(u*).Отсюда с учетом выпуклости Φ(u) имеем  u * (1   )u0   (u*)  (1   )(u0 )  (u0 ).При α → +0 точка u = αu* + (1 – α)u0 попадает в сколь угодно малуюокрестность u0.

Поэтому полученное неравенство Ф(u) < Ф(u0) противоречит предположению о том, что u0 – точка локального минимума (первая часть теоремы доказана).Пусть u(1), u(2) – две различные точки глобального минимума. Изстрогой выпуклости Φ(u) следует, что для всех α  [0, 1] выполняетсястрогое неравенство u (1)  (1  )u (2)   (u (1) )  (1  )(u (2) )  *  min (u),Uчто противоречит предположению о том, что u(1), u(2) – точки глобального минимума.128V.4.4.

Метод наискорейшего спуска для решения систем нелинейныхуравненийV.4.4. Метод наискорейшего спуска для решения систем нелинейных уравненийРешение системы нелинейных уравнений можно свести к задаченахождения минимума функционала:nF(x) = 0  Φ(x )   ( fi (x ))2  (F(x ), F(x ))  min.i 1В соответствии с методом градиентного спуска будем искать новоеприближение в видеx( s 1)  x( s)   grad ( s) , x(0)  a ,где параметр спуска τ в методе наискорейшего спуска определяется минимумом функционала в выбранном направлении, т.е. обращением внуль производной: x( s )   (x( s ) )  0 .Рассмотрим скалярную функциюW ()   x( s )  (x( s ) ) .Уравнение, определяющее оптимальный выбор параметра τ,  x( s )    x( s )  0,необходимо, вообще говоря, решать численно, что довольно сложно.Поэтому укажем лишь приближенный метод нахождения оптимальногопараметра τs.W ( ) Предположим, что τ – малая величина.

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

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