341_3- Сборник задач по математике для втузов. В 4-х ч. Ч.3_ (ред) Ефимов А.В, Поспелов А.С_2002 -576с (987779), страница 48
Текст из файла (страница 48)
~ Выбрав начальное приблньчснпс х = (О, 0) н но — — 1, построим по<о> следоватсльность (4), записывая результаты вычислений в таблице 2.1. Таблица 2.1 Итак, х* а ( — 0,301, — 0,163), У* 0,772. с Для квадратичной функцш1 (3) формула (4) принимает вид х>ь+'> = х>а> — оа(Ях>а> + г), и = О, 1, . (7) В задачах 17.117-17.120 совершить один шаг градиентного спуска (4) из точки х(о> с шагом ао и сравнить значениа у(х(~>) и )(хО>): 17.117.
1(х) = хт + 2хт ~+ е*'+*', х(о> = (1, 1), а) гто = 0,1; 6) сто = 0,265; в) гта = О 5 17.118. ~(х) = 2х>~+х~т+х>хг+х>+ха, хОО = (О, 0), а) сто = 0,1; б) ао = 0,5; в) гто = 1 17.119. Дх) = х, + хз + хз + х>хз + хзхз, х( > = (О, 1, О), а) сто = 0,1; б) то = 0,638; в) сто = 10. 17.120. у" (х) = е* + (х> +ха+ха)т, х(о> = (1, 1, 1), а) сто = 0,1; 6) оа = 0,21268; в) сто = 1.
Гл. 17. Методы оптимизации 346 17.121. Показать, что если функция у(х) дифференцируема в точке х(~> и Г'(х(ь>) ~ О, то при достаточно малом шаге аь из (4) будет выполнено условие (5). Метод наискоребшеео спуска отличаетсп от метода градиентного спуска способола определения всличины аы которая находитсл из условия Фь(аь) = пцп Фл(а), где Фь(а) = ([х>ь> — ар'(х>ь>)!.
(8) в>о Такой выбор аь обеспечивает максимально возмоа~нос уменьшение функции у(х) вдоль направления се антиградиента — 1'(х>ь>) в точке х>~>. Таким образом, для определения аь на каждом шаге метода наискорейшего спуска решается одномерная задача минимизации (8), для чего можно использовать методы, рассмотренные в 3 1. Пример 5. Решить пример 4 методом наискорейшего спуска. Шаг 1. Положим х>о> = (О, О), тогда г'(х>о>) = (1; 1), Фо(а) = = >(Π— а 1, 0 — а 1) = Зат + е з . Для нахождения точки минимума функции Фо(а) используем метод перебора: т.
е. а = ао = 0,22, откуда хи> = (О, О) — 0,22 (1, 1) = ( — 0,22, — 0,22). Шаг 2. У'(хи>) = (0,204, — 0236), Ф~(а) = ( — 0,22 — 0,204а)т + + ( — 0,22+ 0,23ба)з + е ол4 лоозза >>1инимизиргем Ф,(а) т. е, а = а~ — — 0,32, откуда х1 > = ( — 0,22, — 0,22) — 0,32 (0,204, — 0,236) = = ( — 0,2853, — 0,1445), Ш а г 3. У'(хии) = (8,007, 7,268) 10 ~, Фз(а) = ( — 0,2853 — 8,007 х х 10 ~) +( — 0 1445 — 7268.10 ~ а) +е олза ~л згл'" . 51инил~изируем Ф2(а): т.е.
а = а = 0,24, х>з> = ( — 03045, — 0,1619), Г'(х<з>) = (1821 — 2,051) 10 '., позтому требуемая точность достигнута и х* и х~з> = = ( — 0,305, — 0,162), >* >(х>з>) 0 772 в З 2. Бедзтловная минимизация функций многих переменных 347 Если «(х) — квадратичнал функция (3), то величина оь моьдет быть найдена в явном виде (уды удтй) ать =- ', где Г' = ах~в~ + г. (б21дь] удь~) (9) Таким образом, длв квадратичной функции метод наискорейшего спуска состоит в построении последовательности (х~ь~) по формулам (7), (9) . 17.122*. Показать, что градиенты Г'(х1ь)) и Г'(х1"ч О) в последо- вательных точках итерационного процесса метода наискорейшего спуска ортогональны, т.е. (Г'(х1ь)), Г'(х(в+1))) = О, й = О, 1, ...
17.123. «(х) = х~1 + х~з + х1+ хз, х1~1 = (О, 0). 17.124. «(х) = хз + х1хз + хзз, х1о~ = (1, 1). 17.125. «(х) = хз + 2х~з + е" +~', х1о1 = (1, 1). 17.126. «(х) = 2хз + х~~+ х~хз+ х~ + хе, х~~) = (О, 0). 17.127. «(х) = х", + х~~+ ха~+ х1хз + хзхз: х(о1 = (О, 1, 0). 17.128. «(х) = е ~ + (х1+ хз + хз)~, х~~1 = (1, 1, 1). В задачах 17.129-17,144 минимизировать квадратичные функ- ции методом наискорейшего спуска, заканчивая вычисления при д«(х00) <001,1=1,2, ..., и: дх, 17.129. «(х) = 7х1~ + 2х~хз + 5х~ ~+ х1 — 10хз.
17.130. «(х) = Зх~1 — Зх~хз + 4хзз — 2х1 + хз. 17.131. «(х) = х1 + 4х1хз + 17хз + 5хз. 17.132. «(х) = бхз1 — 4х1хз + 5х~~ — х1 — хз. 17.133. «(х) = 4х1, + 4х1хз + бхз~ — 17хы 17.134. «(х) = 2х~~ — 2х1хг + Зх~~ + х1 — Зхз. 17.135. «(х) = 10х~1 + Зх1хз + хз + 10хз, 17.136. «(х) = хз1 — 2х1хз + бхз + х1 — хз. 17.137. «(х) = 4хз1 + 5хз~ + 7хз з— 2х1хз + х1тз + х1 — хз + хз. 17.138.
«(х) = Зхз+4х~з+5хз+2х~хз — х1хз — 2хзхз+х~ — Зхз. 17.139. «(х) = хз1+5хз~+8хзз — х|хз+х1хз-хзхз+5х1 — Зхз+хз. 17.140. «(х) =- 2х1 + 4хг+ 8х~+2х1хз — х1хз+ 2хвхз+ 6х1 — 7хз. 348 Гл. 17. Методы оптимизации 17.141. ) (х) = 7х~)+4хг+бхз~ — Зхлхг+х)хз — хгхз+х( — ха+ха, 17.142.
)'(х) = 5хг) + Зхгг + 2хгз + 2х) хг+ х) хз + хгхз + 5х ( + хз, 17.143. гс(~) = Зхг) + 5~~а +4хгг+ 2х)хз — х)хз — хгхз + 7х) + х). 17.144. 1(х) = 4х)+4х~+х~ — х)хг+2х)хз+тгхз — х(+хг хз, Метод сопряженных гродиентае состоит в построении последовательных приближений х(") к точке минимума функции г(х) следующим образом: х(ьею = х(") — олр(~), Й = О, 1, ..., х( ) Е Ен, (10) где х(о) — заранее выбранное начальное приблигаенис, шаг он выбира- ется аналогично (8): Фь(ол) = ш!пФь(о), где Фл(о) = Г(х(л) — ор(ь)), (11) а>о а направление спуска — р(л) определяется по формуле р(л) = Г (х( )) + Ар л л), 1 = 1, 2, ..., р( ) = У (х( )), где (12) Таким образом, метод сопряженных градиентов отличается от методе наискорейшего спуска только выборам направления уменьшения функции на каждом шаге (-р(л) вместо — Г'(х(л) )).
Отметим, что р(л) из (12) определяется не только антиградиентом — Г'(х(л)), но и направлением спуска — р(л ') на предыдущем шаге. Это позволяет более полно, чсл~ в градиентных методах, рассмотренных выше, учитывать особенности функции )(х) при построении последовательных приближений (10) к сс точке минимума. 1лритсрием достижения заданной точности вычислений в методе сопряженных градиентов обычно служат неравенства (6).
Часто для уменьшения влияния накапливающихся погрешностей вычислений через каждые%итерацийй (10) полагаютД„гг = О,т = О, 1, ..., т.с. производят обновление метода (Х вЂ” параметр алгоритма). Для минимизации выпуклой квадратичной функции в Ея требуется не более и итераций метода сопряженных направлений. Пример 6. Методом сопряженных градиентов найти точку минимума х" функции ('(х) = хл + 2х~з + хлхг — 7х~ — 7хг. 3 2. Безусловная минимизация функций многих переменных 349 а ~(х) — квадратичная функции, заданная в Ем Поэтому точка х' будет найдена после двух шагов метода сопряа.енных градиентов. Ш а г 1.
Выбрав начальное приближение х~е~ = (О, 0), по формулам (9Н11) находим рбб = Г'(хкп) = (2х1 + ха — 7, х1 + 4хт — 7)~и> = ( — 7, — 7), Фе(а) = 98(2ае — о). Из условия Фо(ае) = О минимума Фе(а) пол1 ~им 1 1 /7 71 ао — — —. Отсюда хО~ = (О, О) — -( — 7, — 7) = ~-, -). 4 ' 4 ' ~4'4) / 7 71 Ш а г 2. Г'(хрд ) = ~ — —, — ~, откуда с учетом (12) имеем 4' 4 А = —, Р~О = ~ — —, -) + — ( — 7, — 7) = ~ — —, — у).
Позтому 16' 1 4' 4) 16 ' 1, 16' 16/ Ф1(о) = — ~-а~ — 4а — 392( и а1 =- —. Окончательно хйй 32 12 ( 7 — — — = (3, 1) = х'. 17.145. Показать, что при обновлении метода сопряженных градиентов на каждом шаге (т. с. если Д,. = О, 1 = 1, 2, ... ) он перс- ходит в метод наискорейшего спуска. 17.146. Минимизировать одну из квадратичных функций задач 17.129-17.136, совершив две итерации метода сопряженных градиентов из произвольного начального приближения х~с) Е Ез. 17.147. Минимизировать одну из квадратичных функций задач 17.137--17.144 с помощью трех итераций метода сопряженных градиентов, используя произвольное начальное приближение х(0) е Ез, 17.148.
Минимизировать функцию Дх) = х~~ + х~ ~+ х~~ + х42— — 2хт+ 2хз — 2ха с помощью четыРех итеРаций метода сопРЯженных градиентов, используя произвольное начальное приближение хОО Е Е4. В задачах 17.149 — 17.174 минимизировать функцию ~(х) метод.ПЫ )) дом градиентов, заканчивая вычисления при < 10 з, дх; 1 = 1, 2, ..., ги 17.149. ДХ) = ХЗ + 2ХЗ2 + Е*1 Гяа — Х1 + 2жт, 1 1 пльо. нс =,й' гз+т ~ —,, — —,;. 17,1Ы.
~(х) = х1~ + 2х~~ + х1~х~~ + 2х1 + хт, 350 Гл. 17. Методы оптимизации 17.152. гг(х) = хг) + Зхг г+ соя (х) + хг). 17!53. 7) ) = 577 7 2, 5.. '5 .*'" " †.ч — ... 17.154. у (х) = х) + 5хг + е~!+""г. !7.155. !) ) = !,' 5 *:,' 5,/2 8-Н 77--Ч,' — 2 5 3: . 1Т.156. )'(х) = 2хг) + Зхгг — 2з)п + хг. 2 1Т.157.
~(х) = 1п(1+ Зхг+ 5хгг+ соя(х~ — хг)). 17.158. у (х) = хг + се!+*2 + 4х! + Зтг, 17.153. 7) ) =..:,-,-2,„„-3,7! ~ ',~5., г+1 г 17.160. у(х) = 2х) — 5хг + е*!+1*'. 17.161. у(х) = 2 3+ хг+ 2хгг+ хгз т) — хз. 17.162. Дх) = хг) + 2хгг + хгхг г+ хз + е*г+хг — хг + хз. 17.163. у(х) = 4 1+хг+хгг+ Зхз+ х) 2хг. 17 164. г (х) = 2х'", + хг + хгхг + хз + х) хз + х) + хг. 17.165. гг(х) = хг) + 5хгг + 2хз г+ сов (х) †.тг + хз). 17.166. у(х) = ес1+ '2 +1п(4+ хг ф 2хг), зг г.2 2 17.167. у (х) = х) + хг — 5хз + е*) ьгг'ге* .
17.138.)))=: 3 5.:, -5/5~.152),5:,5щ. г . 7' г)г+ гг — хзг) 17.169. Дх) = 2хг) +хгг+ 4хзг — 2в)п ( ). 2 17 173. Д*) = 2 77й 5 гс) 5 3 5 *,, — .:, — . 17.171. Дх) = хг -)- хг -~- ез) сгг ~*э + хг — хг. 17172 Д ) = ., !), 3- 3 3 3~)ь 5 75 1 ... *'е- . 17!73.7) )=2;5 '.51 ) 5 )5835*'15*2. 17.174. г'(х) = х) + 10хг — Зхз + е* +'г-)* . 3. Методы безусловной минимизации, использующие вторые производные функции.
Если при построении последоватсльности приближений в точно минимума фуннпии у(х) использовать инфориапию, содсржащук)с)! в значениях нс только первых, но и вторых производных у (х), то при определенных условипх можно обеспечип более быструю, чсл! в градиентных методах, сходимость втой последовательности. 3 2, Бсзусловнал минимизация функций многая переменных 351 Метод Ньютона применяется для безусловной минимизации выпуклых дважды диффсрснцирусмых функций.
В этом методе последовательные приближения х~ 4 к точке минимума функции /(х) строятся с ь) использованием первых и вторых производных слсдуюшим образом: х~ь" 0 = х00 — (/и(хйй)]-'У (хйй), ~ = О, 1, (13) где х~о~ 6 б„— начальное приближение, (/" (хйй)] ' — матрица, обратная матрипе вторых производных функции /(х) в точке х~"'>. 1(ритерием достижения требуемой точности вычислений обычно слув'ат неравенства (6). Если начальное приближение хйй достаточно блиако к точке минимума х*, то метод Ньютона сходится, как правило, гораздо быстрее гзетодов минимизации, использующих первые производные /(х), поэтому его часто используют на завсршаюшсм этапе минимизации при уточнении приближения к точке х', найденного другим, более простым методом.
Пример 7. Используя решение примера 4 в качестве начального прибли'кения метода Ньютона, найти точку минимума функции /(х) = = хе + 2хэ+ е*'ь*' с точностью]д/(хйб)/дх1] ( 10 ', 1= 1, 2. < Р1спользуя результаты решения примера 4, запишем 00 У 0 3012259~ у 69 У 2 6226об 1 . 10 з (о) 70~39319151 0~628678351 (,0,62867835 0,22329787/ ' Найдем ( си э Ййн-1 / 0 39319151 5 3404226 ' 10 1-5,3404226 10 э 0,22329787 откуда 7-0,30122591 ( 0,39319151 -5,3404226 10 э (,-0,1629096/ ( -5,3404226 10 ' 0,22329787 у 2,622655 1 10 э 7-0,31276411 " (,-2,296005/ ' (,-0,1563821/ ' Вычислив Г'(хы~) = (7,9 10 е, 7,9.10 ь), убеждаемся, что условие точности выполнено, т. с. х' х0~ = ( — 0,3127641, — 0,1563821).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
