А.А. Самарский, П.Н. Вабищевич, Е.А. Самарская - Задачи и упражнения по численным методам (1113878), страница 11
Текст из файла (страница 11)
После этого процесс повторяется — в соответствии с правиломзолотого сечения делится точкой ж3 отрезок [а,ж'].Для минимизации функции одной переменной широко используютсяметоды полиномиальной интерполяции. В этом случае с использованиемранее найденных точек строится интерполяционный полином, точкаминимума которого принимается за очередное приближение. В методепарабол используется интерполяционный многочлен второго порядка.Пусть, например, известны три приближения ж*-2 < ж*"' и2ж*" < хк < хк~\ причем f(xk) < /(ж* - 2 ) и /(ж*) < /(ж*" 1 ).
Новоеприближение ищется как решение задачи минимизацииL2 (ж) —> min,(7.5)где Ь2{х) — интерполяционный многочлен второго порядка, построенныйпо узлам ж* - 2 ^* - 1 и хк.Интерполяционный многочлен Ньютона имеет видЬг(х) = /(ж*) + (х~ ж*)/(ж\ж*-') +(х-хк)(х-хк-*)/(хк,хк-\хк-2),+где/ 0 е >х)=~к—ZiTiх —х'„ J ,*-, ^ _ /(»*-,*fc-2)-;(«V-')/(Ж ,ж ,ж ; ^к2^к— разделенные разности первого и второго порядка соответственно.Решение задачи (7.5) приводит нас к следующей формуле для новогоприближения для точки минимумаоJfc+l _ * . _*-•/ V Е 'Х )/7А\/(ж*,д.*-1 хк~2]2ж = ж + ж - —т-г—._,....(7.6)7.2.
Методы решения задач оптимизации93Для дифференцируемой функции f(x) строятся итерационные методы, основанные на решении уравнения (необходимое условие минимума)/'(*)=0.(7.7)Корень этого уравнения х* € X является точкой минимума, если/"(ж) > 0 (достаточные условия минимума). Для приближенного решения нелинейного уравнения используются итерационные методы.В итерационном методе Ньютона новое приближение для точкиминимума определяется в соответствии с формулой„*+> _хкх_f \х ).
_ „ ,/ 7 сч= 01(7 8)~ 7ч^)' * ' '"---Различные модификации метода Ньютона рассматривались в главе 7.7.2.2. Минимизация функций многих переменныхДля функции многих переменных f(x), х — {xi,X2,-.. ,хп} определимвектор первых частных производных (градиент)'<•>-{£<"}•{&«<<•>ЫМатрица вторых частных производный (гессиан) в точке х есть'<•>-{*&<•>}•Будем рассматривать задачу безусловной оптимизации (7.3). Пустьфункция f(x) дифференцируема в точке локального минимума х = х*,тогда (необходимые условия оптимальности)/V) = 0.(7.9)Пусть функция f(x) дважды дифференцируема в точке х = х* и выполнено (7.9). Если матрица /"(х) положительно определена, т.
е.(/"(**)», у) > 0,Vj/^0,(7.10)94Глава 7. Задачи минимизации функцийтогда х* — точка локального минимума. Условия (7.9), (7.10) есть достаточные условия оптимальности.Для итерационных методов минимизации будем использовать обозначениях*+| =xk + akhk, fc = 0 , l , .
. . ,(7.11)где hk — вектор, который определяет направление (fc + 1)-го шага минимизации, а коэффициент а* — длину этого шага.Вектор h задает направление убывания функции /(х) в точке х, если/(х + ah) < /(х) при достаточно малых а > 0. Если вектор ft* задаетнаправление убывания функции /(х) в точке хк, а ак > 0 такое, чтоf(xk+i)<f(xk),то итерационный метод (7.11) называется методом спуска. В фадиентномметодеft*= -/'(х*), т.е.xk+t=xk-akf'(xk),k = 0,1,....(7.12)Особое внимание уделяется выбору итерационных параметров а*,к — 0,1,...
в методе (7.11). Их можно определять из условияf(xk +akhk) = min / (хк + ah"),т. е. из решения дополнительной одномерной задачи минимизации.В вычислительной практике широко используется процедура дробления шага, когда параметр а уменьшается, например, в два раза, до техпор пока не будет выполнено неравенство/(х* +aft*) </(**)•При применении метода Ньютона для решения системы нелинейныхуравнений (7.9) получимf"(xk){xk+l-xk)+ / ' ( * ' ) = 0,* = 0,1,-...(7-13)Он записывается в виде (7.11) приa, = l, ft* = - ( / " ( * * ) ) " № ) •(7-14)7.2.
Методы решения задач оптимизации95Среди модификаций метода Ньютона отметим метод Ньютона с регулировкой шага, когда вместо (7.14) используется«*>о, л» = -(/"(«*))-у(«*).В квазиньютоновских методахft* = - Я * / ' ( * * ) ,где Нк — матрица, которая аппроксимирует матрицу (/"(ж*)).7.2.3. Задачи условной минимизацииПри минимизации функций с ограничениями широко используются подходы, аналогичные разработанным для задач безусловной минимизации.Наиболее просто это реализуется при переходе от задачи условной минимизации к задаче минимизации без ограничений.Рассмотрим задачу минимизации с ограничениями типа равенств:/(z)-»min,gi(x) = 0,z=l,2,...,m.(7.15)Эту задачу можно записать в общем виде (7.1), задав допустимое множествоХ = { х € К " | л ( * ) = 0, » = l , 2 , . .
. , m } .При некоторых ограничениях задача условной минимизации (7.15)эквивалентна задаче безусловной минимизации функции ЛагранжатФ{х,у) = f(x) +^2yi9i(x),:=lгде j/j — неизвестные множители Лагранжа. Тем самым мы приходимк задаче минимизации функции п + т переменных.Более сложно перейти к задаче безусловной оптимизации при учетеограничений в виде неравенств. Рассмотрим, например, задачу/(ж)-ишп,#(х)<0,i=l,2,...,го,т.е. в (7.1)X = {х € R" | 9i(x) ^ О, i = l , 2 , .
. . , r o } .(7.16)96Глава 7. Задачи минимизации функцийВместо функции fix) в методе штрафов минимизируется функция<b(x,e) = f(x)+f(x,e),(7.17)где 1р{х,е) — штрафная функция, е > О — параметр штрафа. Выборштрафной функции на допустимом множестве подчинен условиям•ф(х,е)^0,ip(x, е) -» 0, если е —• О,х е X,а вне допустимого множества —•ф(х, е) -* оо, если е -+ 0,a; g X.В качестве характерного примера приведем штрафную функцию для задачи условной минимизации (7.16):f(x,s)1 ™2= -2_,[тах{0,з,(а:)}] .После этого рассматривается задача безусловной минимизацииФ(х,е) —• min,ас € R".Помимо выбора штрафной функции в методах этого класса очень важенвыбор величины параметра штрафа е.7.3.
УпражненияПриведены примеры решения задач, связанных с построением и исследованием численных методов приближенного решения задач минимизациифункций.Упражнение 7.1. Пусть точка х] проводит золотое сечение отрезка [а,Ь],причем х1 > а+ (Ь — а)/2, ах2— точка золотого сечения отрезка [а,х ].Покажите, что точки х\х2 расположены симметрично относительносередины отрезка [а,Ь] и поэтому х' есть точка золотого сечения и отрезка [х2,Ь].Решение. Точка х1 является точкой золотого сечения, еслиb— аа;1 - ах1 — аЬ - ж1977.3.
УпражненияИсходя из этого определения имеемх = а+2va).Аналогично для х2 имеемх1 - ох2 — аи поэтомух =а+х2 - ах1 - х232В силу этогох'-(с-~Va).v»-.Ч_a+o-- aт.е. точки х1 и х 2 расположены симметрично относительно центра отрезка [а, Ъ].Упражнение 7.2. Функция f(x) называется выпуклой на X, если/(А* + (1-Л)у)<А/(*) + (1-А)/(у)для всех х,у & X и \£ [О,1J. Пусть функция f(x) выпукла на R" и дифференцируема в точке х* € R". Покажите, что если выполнено/'(**) = 0,(7.18)то х* — точка минимума функции / ( х ) .Решение. Для любых х € R" и А € (0,1] имеем/(Ах + (1 - А)х*) < А/(х) + (I - А)/(х*).Принимая во внимание дифференцируемость функции / ( х ) в точке х*,получим/(х* + А ( х - х * ) ) - / ( х * )/(*)-/(*•)£X( / ' ( х * ) , А ( х - х ' ) ) + о ( А ) о(А)АА 'Предельный переход А —» 0 дает искомое неравенство /(х) ^fix*).Глава 7.
Задачи минимизации функций98Важно отметить, что условие (7.18) есть необходимое условие минимума. Мы установили, что это условие является и достаточным при поискеминимума выпуклой функции.Упражнение 7.3. Покажите, что итерационный метод Ньютона сходитсза одну итерацию при минимизации квадратичной функции/ 0 Е ) = -(Ах,х) + (Ъ,х),где А — симметричная положительно определенная матрица пхп.Решение.
В нашем случаеf'(x) - Ах -b,f"(x) = A.При применение метода Ньютона (7.13) при произвольном начальномприближении ж0 имеемf'(x*) = Axl - 6 = 0,!*т. е. х — х .Упражнение 7.4. Для задачи условной минимизации (7.16) приведите несколько примеров штрафных функций.Решение. Ограничения в виде неравенств д,(х) < О, г = 1,2,... ,т учитываются выбором штрафных функций1 т•Ф(х,е) = -^2[тях{0,д{(х)}]р,6р>\,i=iV>(a;,e) = X ] e x p ( ё9'(хЧ'(7.19)«=i(гр(х,е)=<mj]С~7л't=1если5i v*/S.
(*) < °, *= 1,2,...,тп,оо, в противном случае,т(х,е)-е 5 3 In [-9i(x)},если &(а;) < 0, * = 1,2,..., m,i=lоо, в противном случае.7.4. Задачи99Наиболее часто используется квадратичная штрафная функция (7.19)с р = 2.7.4. ЗадачиЗадача 7.1. Найдите длину отрезка локализации минимума одномернойфункции после N шагов минимизации на отрезке [о, Ь] методом золотогосечения.Задача 7.2. В методе дихотомии первая пара точек есть1ха+b=—+*,а+ьс«= —-«.2Каждая последующая пара точек выбирается на расстоянии 6 по обестороны от середины отрезка локализации.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
