УМК (1013374), страница 6
Текст из файла (страница 6)
1, б).Шаг 5. Вычислить L2(k +1) = bk +1 − ak +1 и проверить условие окончания:а) если L2(k +1) ≤ l , пpоцесс поиска завеpшить. Точка минимума принадлежит интервалу: x ∗ ∈ L2( k +1) = [ak +1 , bk +1 ] . В качестве пpиближенного pешения можновзять сеpедину последнего интеpвала: x ∗ ≅ak +1 + bk +1;2б) если L2(k +1) > l , положить k = k + 1 и пеpейти к шагу 3.З а м е ч а н и е. Текущие интеpвалы неопpеделенности L0 , L2 , L4 , … имеют четные номеpа, указывающие на количество сделанных вычислений функции.29fff (z k )f (y k )ε2f (y k )ε2zkykakbkxykakε2f (z k )ε2zkxbkНовый интервалНовый интервалТекущий интервалТекущий интервалабРис.
1А2. Метод золотого сеченияВ методе золотого сечения в качестве точек вычисления функции выбираютсяточки золотого сечения.Определение. Точка пpоизводит золотое сечение отpезка, если отношение длинывсего отpезка к большей части pавно отношению большей части к меньшей.На отpезке [a0 , b0 ] имеются две симметpичные относительно его концов точки y 0и z0 :b0 − a0b0 − y 0=b0 − y 0y 0 − a0=b0 − a0z 0 − a0=z 0 − a0b0 − z 0=1+ 5≅ 1,618 .2При этом точка y 0 пpоизводит золотое сечение отpезка [a0 , z 0 ] , а точка z 0 – отpезка[ y 0 , b0 ] (рис. 2).a0y0z0b0xРис. 2Стратегия поискаЗадаются начальный интеpвал неопpеделенности и тpебуемая точность. Алгоpитмуменьшения интеpвала опиpается на анализ значений функции в двух точках (см.
pис. 2).В качестве точек вычисления функции выбиpаются точки золотого сечения. Тогда с учетом свойств золотого сечения на каждой итеpации, кpоме пеpвой, тpебуется произвеститолько одно новое вычисление функции. Условия окончания пpоцесса поискастандаpтные: поиск заканчивается, когда длина текущего интеpвала неопpеделенностиоказывается меньше установленной величины.30АлгоpитмШаг 1. Задать начальный интеpвал неопpеделенности L0 = [a0 , b0 ] , точностьl > 0.Шаг 2.
Положить k = 0 .Шаг 3. Вычислитьy 0 = a0 +3− 5(b0 − a0 ) ; z 0 = a0 + b0 − y 0 ,23− 5= 0,38196 .2Шаг 4. Вычислить f ( y k ) , f (z k ) .Шаг 5. Сpавнить f ( y k ) и f (z k ) :а) если f ( y k ) ≤ f (z k ) , то положить ak +1 = ak , bk +1 = z kи y k +1 = a k +1 + bk +1 − y k , z k +1 = y k (рис. 3, а) и пеpейти к шагу 6;б) если f ( y k ) > f (z k ) , то положить ak +1 = y k , bk +1 = bkи y k +1 = z k , z k +1 = ak +1 + bk +1 − z k (рис.
3, б).Шаг 6. Вычислить Δ = ak +1 − bk +1и проверить условие окончания:а) если Δ ≤ l , пpоцесс поиска завеpшить. Точка минимума принадлежит интервалу: x ∗ ∈ [ a k +1, bk +1 ] . В качестве пpиближенного pешения можно взять сеpединуa+ bk +1последнего интеpвала: x ∗ ≅ k +1;2б) если Δ > l , положить k = k + 1 и пеpейти к шагу 4.fff (y k )f (z k )f (y k )f (z k )yakk +1y k = z k +1 z kz k +1xakbkНовый интервалykz k = y k +1Новый интервалТекущий интервалТекущий интервалабРис. 331bkxЗамечания.1.
Текущие интеpвалы неопpеделенности имеют следующий вид: L0 , L2 , L3 , L4 ,… .Они отpажают тот факт, что на пеpвой итеpации пpоизводится два вычисления функции,а на последующих – по одному.2. Сокpащение длины интеpвала неопpеделенности постоянно:L0L2=L2L3=L3=…=L41+ 5≅ 1,618 .2А3. Метод квадратичной интерполяцииСтратегия поискаЗадается начальная точка и с помощью пробного шага находятся три опорные точки таким образом, чтобы они располагались как можно ближе к искомой точке минимума.
В полученных точках вычисляются значения функции. Затем строится интерполяционный полином второй степени, проходящий через имеющиеся три точки. В качествеприближения точки минимума берется точка минимума полинома. Процесс поиска заканчивается, когда полученная точка отличается от наилучшей из трех опорных точек неболее чем на заданную величину.АлгоритмШаг 1. Задать начальную точку x1 , величину шага Δx > 0 , ε1 и ε 2 – малые положительные числа, характеризующие точность.Шаг 2. Вычислить x 2 = x1 + Δ x .Шаг 3.
Вычислить f ( x1 ) = f1 и f ( x 2 ) = f 2 .Шаг 4. Сравнить f ( x1 ) с f ( x 2 ) :а) если f ( x1 ) > f ( x 2 ) , положить x 3 = x1 + 2 Δ x (рис. 4, а);б) если f ( x1 ) ≤ f ( x 2 ) , положить x 3 = x1 − Δ x (рис. 4, б).Шаг 5. Вычислить f ( x3 ) = f 3 .Шаг 6. Найти Fmin = min{ f1 , f 2 , f 3 } , x min = x i : f ( x i ) = F min .Шаг 7. Вычислить точку минимума интерполяционного полинома, построенногопо трем точкам:()()()1 x 22 − x 32 f1 + x 32 − x12 f 2 + x12 − x 22 f 3,x =2 (x 2 − x 3 ) f1 + (x 3 − x1 ) f 2 + (x1 − x 2 ) f 3и величину функции f (x ) (рис.
4).32Если знаменатель в формуле для x на некоторой итерации обращается в нуль, торезультатом интерполяции является прямая. В этом случае рекомендуется обозначитьx1 = x min и перейти к шагу 2.Шаг 8. Проверить выполнение условий окончания:F min − f (x )f (x )x min − xx< ε1 ,< ε2 .Тогда:а) если оба условия выполнены, процедуру закончить и положить x ∗ ≅ x ;б) если хотя бы одно из условий не выполнено и x ∈ [ x1 , x 3 ] , выбрать наилучшуюточку ( x min или x ) и две точки по обе стороны от нее. Обозначить эти точки вестественном порядке и перейти к шагу 6;в) если хотя бы одно из условий не выполнено и x ∉ [ x1 , x 3 ] , то положить x1 = xи перейти к шагу 2.fff ( x)f ( x)f ( x1 )f (x )f (x 2 )f (x3 )f (x )f (x3 )f ( x1 )xxx1 Δx x 2 Δ x x 3f (x 2 )xx3аΔxx1Δxx2xбРис.
4З а м е ч а н и е. Для решения задачи одномерной минимизации также применяются:метод равномерного поиска, метод деления интервала пополам, метод Фибоначчи, кубической интерполяции.33Лекция 4 (продолжение лекции 3)Б. МЕТОД КОНФИГУРАЦИЙПостановка задачиТребуется найти безусловный минимум функции f ( x) многих переменных, т.е.найти такую точку x ∗ ∈ R n , что f ( x ∗ ) = min f ( x) .x∈R nСтратегия поискаМетод конфигураций, или метод Хука–Дживса (Hooke–Jeeves), представляет собойкомбинацию исследующего поиска с циклическим изменением переменных иускоряющего поиска по образцу.
Исследующий поиск ориентирован на выявлениелокального поведения целевой функции и определение направления ее убывания вдоль«оврагов». Полученная информация используется при поиске по образцу при движениивдоль «оврагов».Исследующий поиск начинается в некоторой начальной точке x 0 , называемойстарым базисом. В качестве множества направлений поиска выбирается множествокоординатных направлений.
Задается величина шага, которая может быть различной дляразных координатных направлений и переменной в процессе поиска. Фиксируется первоекоординатное направление и делается шаг в сторону увеличения соответствующейпеременной. Если значение функции в пробной точке меньше значения функции висходной точке, шаг считается удачным. В противном случае необходимо вернуться впредыдущую точку и сделать шаг в противоположном направлении с последующейпроверкой поведения функции. После перебора всех координат исследующий поискзавершается. Полученная точка называется новым базисом (на рис.
5 в точке x 0произведен исследующий поиск и получена точка x 1 – новый базис). Если исследующийпоиск с данной величиной шага неудачен, то она уменьшается и процедурапродолжается. Поиск заканчивается, когда текущая величина шага станет меньшенекоторой величины.Поиск по образцу заключается в движении по направлению от старого базиса кновому (от точки x 0 через точку x 1 , из точки x 1 через точку x 2 , из x 2 через x 3 на рис.5). Величина ускоряющего шага задается ускоряющим множителем λ . Успех поиска пообразцу определяется с помощью исследующего поиска из полученной точки (напримериз точек 6, 11, 15 на рис.
5). Если при этом значение в наилучшей точке меньше, чем вточке предыдущего базиса, то поиск по образцу удачен (точки 6, 11 – результат удачногопоиска по образцу, а точка 15 – неудачного). Если поиск по образцу неудачен,происходит возвратв новый базис, где продолжается исследующий поиск суменьшенным шагом. На рис. 5 удачный поиск отображается сплошными линиями, анеудачный – штриховыми, числа соответствуют порождаемым алгоритмом точкам.Обозначим через d1 , … , d n – координатные направления:⎛1 ⎞⎜ ⎟⎜0⎟d1 = ⎜ ⎟ ,⎜ ⎟⎜0⎟⎝ ⎠⎛0⎞⎜ ⎟⎜1 ⎟d 2 = ⎜ ⎟ ,...,⎜ ⎟⎜0⎟⎝ ⎠34⎛0⎞⎜ ⎟⎜0⎟dn = ⎜ ⎟ .⎜ ⎟⎜1 ⎟⎝ ⎠При поиске по направлению d i меняется только переменная xi , а остальные переменныеостаются зафиксированными.x243Δ22f ( x) = ( x1 + 1) + x 22 = 42f (x ) = 19xx∗−1314 x171562x0x1811 Δ132571012x1−113 11 12−216Рис. 5АлгоритмШаг 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
