XIV Аттетков и др. Методы оптимизации (1081420), страница 13
Текст из файла (страница 13)
Метод средней точки напоминает метод дихотомии, но сходится к искомому значению х, быстрее, поскольку в отличие от (2.8) для метода средней точки после вычисления п значений производной минимизируемой на отрезке [О, Ц функции Т(х) для длины интервала неопределенности получаем 1 2" (2.22) Таким образом, для одинакового уменьшения значения 1„в методе средней точки нужно вычислить вдвое меньше значений производной функции по сравнению с числом значений самой функции в методе дихотомии.
у'(х) = 1'(хо) + уо(хо) (х — хо) (2.23) Метод Ньютона. Если строго унимодальная на отрезке [а, 6] функция Т'(х) дважды непрерывно дифференцируема на этом отрезке, то точку х„б [а, 6] минимума этой функции можно найти путем решения уравнения Т>(х) = О методом Иьютона, иногда называемым методом касательных. Пусть хо Е [а, 6] — - нулевое приближение к искомой точке х.> называемое обычно начальной точкой. Липеаризуем функцию Т"'(х) в окрестности начальной точки, приближенно заменив ду- гУ гРафика этой фУнкЦии касательной в точке (хо, Т'(хо)): 35 2.7.
Методы с исиоаьэоваиием ироиэводиыт Рис. 2.13 Выберем в качестве следующего приближения к х„точку х~ пересечения касательной с осью абсцисс (рис. 2.13). Приравнивая нулю правую часть (2.23), получаем первый элемент х1 = хс — ' итерационной последовательности ~хь). На у'(хо) Уцхс) (Й+ 1)-м шаге по найденной на предыдущем шаге точке хв можно найти точку Г(ха) хис1 хя ус~ (2.24) Для квадратичной функции ~(х) функция ~'(х) линейна. Поэтому в (2.23) равенство будет точным, а метод Ньютона будет сходиться за один шаг при любом выборе точки хо из области определения этой функции. В общем случае сходимость метода Ньютона существенно зависит от выбора наильной точки хш Для надежной работы этого метода необходимо, чтобы вторая производная ~в(х) в окрестности искомой точки х, сохраняла знак, а начальная точка хс выбиралась из такой окрестности.
В противном случае второе слагаемое в правой части (2.24) может стать неограниченным. Поскольку для дважды непрерывно дифференцируемой функции в точке минимума ув(х,) ) О, то должно быть и 1в(хс) ) О. ПоэтомУ говоРЯт, что метоД Ньютона обладает локальной сходимостью в том смысле, что надо выбрать 86 2. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ 2 )'(х, ) = О = ~'(хь) + )' и(хь) (х, — хь) + 2" и'(х) ' * где точка х лежит между хь и х,. Поэтому с учетом (2.24) имеем У'( '~) — 1"(х~) ха — хь + 2 — 1 2+ ~ У'(хя) Таким образом, последовательность (хь~ является монотонной, если, > О, т.е.
достаточным условием монотонной сходи- У"'(х) У'(х ) мости метода Ньютона будут постоянство в интервале между точками хо и х, знака производной Т (х) и совпадение его со знаком Т'(хо). Оказывается [1Ц, что в этом случае метод Ньютона обладает квадратичной скоростью сходимости в некоторой б-окрестности Н(х.,й) точки х„причем < (х, — хь 1)2 С 1пй1 / (о(х) ! шах ! ~"'(х) ! минимум и максимум вычисляются по множеству Н(х„о).
(2 25) хорошее начальное приближение, попадающее в такую окрестность точки х„, где 1и(х) > О. Однако проверка выполнения этого условия не всегда возможна. Достаточное условие надежной работы метода Ньютона при нахождении точки х„б (а, 6) минимума функции Т (х) можно установить в случае, если зта функция трижды непрерывно дифференцируема на отрезке (а, о~).
Ясно, что итерационная последовательность ~хь) будет сходиться к пределу х„монотонно, если О < * "'+' < 1. В соответствии с формулой Тейлора с остаточным членом в форме Лагранжа имеем 2.7. Ъ|етоды с использованием производных 87 Если радиус д-окрестности Цх„б) не превосходит С, а точка хь попадает в окрестность Цхсы д/2), то и следующая точка оказывается в этой окрестности, т.е. итерационная последовательность не выходит за пределы окрестности П(х„д/2).
В этом случае верна оценка [П] (2.26) [хь — х,[ < [хь ~ — хь[, которую можно использовать для оценки точности найденного решения уравнения 1'(х) = 0 (точки локального минимума функции). Пример 2.6. Найдем точку х„наименьшего значения функции 1(х) = х + 16/х на отрезке [1, 4].
Вычислим ~'(х) = 2х — 16/хз, 1о(х) = 2+ 32/хз и гв'(х) = = — 96/х4. Всюду на отрезке [1, .4] имеем 1п(х) > О, 1п'(х) < О. Поэтому, если начальную точку хо выбрать исходя из условия 1 (хо) < О, то построенная итерационная последовательность будет монотонной. Выберем хо = 1 и вычислим ~'(хо) = — 14, ~в(хо) = 34, а затем, используя (2.24) при и = О, получим Пхо) — 14 х1 = ХΠ— = 1 —, = 1,.4118. ,)'в(хо) 34 Далее при помощи (2.24) последовательно находим хз — 1,8010, хз — 1,9790, х~ = 1,9998. Предположим, что верна оценка (2.26). Тогда ]х4 — х.] < < [хз — хз[ — 0,0208 и, в силу того что последовательность (хь) возрастает, искомая точка х, должна лежать в интервале (хл, х4+0,0208) = (1,9998, .2,0206).
Так как )'(1,9998)— — — 0,0012 < О, )'(2,0206) — 0,1223 > О, то, действительно, уравнение ~о(х) = 0 в интервале (1,9998, 2,0206) имеет корень, который в силу условия 1п(х) > О, х б [1,4], является точкой минимума функции 1(х). Отметим, что функция 1(х) была рассмотрена в примере 2.4, где получено точное значение х„= 2 точки, в которой функция достигает наименьшего значения.
88 2. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ Модификации метода Ньютона. Вычисление второй производной Та(хь) минимизируемой функции 1[х) на каждом й-м шаге метода Ньютона может оказаться достаточно трудоемким. В этом случае целесообразно использовать унро!ценный метод Ньютона, положив в [2.24) То(хь) = То[хе) = сопя!: Т'[хь) х! ! —— хв— (2.27) Оказывается, что этот метод имеет линейную скорость сходимости. При этом если в интервале между точками х, и хс выполнено Условие ~'(хо)~нл[х) > О, то последовательность ~хе),построенная в соответствии с (2.27), сходится к точке х, монотонно.
Можно избежать вычисления второй производной минимизируемой на отрезке [а,6) функции Т(х), если располагать двумя приближениями хо,х!6 [а,6) к искомой точке х„ 6 [и,6) минимума этой функции. Заменяя в [2.24) при й = 1 производную Т а [х ! ) выражением Пх!) -Пхо) х! —:со получаем х! — хо х2 х1 Т![ ) Т![ ) ) [х!)~ а в случае произвольного номера й Е 1Ч приходим к формуле х/с хх — ! хь,. =хй-~,[,') '~,[х )1[.хй) [2.28) Метод решения нелинейного уравнения Т'[х) = О с применением рекуррентного соотношения [2.28) обычно называют методом сенди!их.
Геометрическая интерпретация этого метода состоит в том, что в качестве очередного приближения хьз ! выбирают точку пересечения с осью абсцисс не касательной к графику функции Т'~[х), как это делают в методе Ньютона, а секущей, 2.7. 11еходы с нсполозованнем производных 89 проходящей через две точки этого графика, найденные при выполнении двух предыдущих шагов метода. Выбор начальной точки хв в (2.28) при б = 1 проводят следующим образом. Если на отрезке [а, Ь] функция 1'(х) имеет знакопостоЯннУю тРетью пРоизвоДнУю уп'(х), то в качестве хв выбирают тот конец отрезка [а, Ь), на котором совпадают знаки ~'(х) и 1н'(х), а в ка ~естве а1'(Ь) — Ь1'(а) 1'(Ь) — 1'(а) (2.29) точку пересечения с осью абсцисс хорды, стягивающей дугу графика функции 1'(х) на отрезке [а,б1 (рис.
2.14). Таким образом, первый шаг метода секущих выполняют согласно методу хорд, а последующие шаги в соответствии с (2.28). Этот метод имеет сверхлинейную скорость сходильости [1Ц, причем [х„— хе~ ( С(х„— хь 1)', где С = сонв1, .а т = 1-ь Л 2 — 1,618 отношение золотого сечения,. Рис. 2.14 Модификации метода Ньютона обладают только локальной сходимостью, т.е. сходятся, если начальная точка выбрана в некоторой окрестности точки минимума функции.
Если же начальная точка расположена слишком далеко от точки минимума, то подобный метод может расходиться или сзацикливать- ОО 2. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ ся". В некоторых случаях целесообразно сочетать различные модификации метода Ньютона, чередуя их применение в зависимости от номера шага [П]. Метод кубической аппроксимации.
В методах полиномиаланой аппроксимации при построении многочлсна, аппроксимирую»пего минимизируемую функцию в окрестности искомой точки х, минимума, помимо зна»ений функции в отдельных точках могут быть использованы и значения ее производных. Пусть для непрерывно дифференцируемой функции Т"[х), строго выпуклой на отрезке [т», хз], известны значения Т» = =,~(х»), ~2 = 1(ха), )» = ~'(х») и Д = ~'[хз). Для строго выпуклой функции производная Т"'(х) возрастает на отрезке [1Ц. Поэтому если значения Т» и Тз одного знака, т.е. Т»Т2 > О,.
то дифференцируемая функция 1(х) не имеет стационарных точек на отрезке [х», хз] и, следовательно, не имеет на нем точки минимума. Если ДД = О, то один из концов отрезка является стационарной точкой функции 1 [»е), в которой эта функция имеет минимум. Наконец., если 1112 < О, то для строго выпуклой функции Т» < О и Т2 > О. Следовательно, лишь единственная точка х, Е (х», х2) будет стационарной, и в ней функция Т'(х) достигнет минимума. Таким образом, если ДД < О на отрезке [х», хз], то рассматриваемая функция строго унимодальна на этом отрезке.
Рассмотрим метод поиска точки х м (х», ха) при условии ДД < О, называемый методом кубической аппронсима»1ии, поскольку в этом случае на отрезке [х», хз] можно построить единственный многочлен третьей степени, располагая значениями 11, 12, 11, Д на концах этого отрезка [П]. Этот много"шен, называемый кубическим ино»ерполяиионным жного- членом Эрмита*., можно преобразовать к виду нз(х) = 11 + а»(х — х») + а2 (х — х») (х — ха) + аз (х — т») (х — хя) *Ш. Эрмит»1822 — 1901) французский математик. 91 2.7.
Методы с исполвзованиеы производных с коэффициентами 22 21 Х2 Х! ~2 — ~! Л !Х2 — Х1) Х2 — Х! !2.30) Л+Л л — л з — , — 2 !Х2 — Х1) 1Х2 — Х1) Заз!х — Х1) — 2 (х — и1) + з'! = О. 2Я + Д вЂ” За! Его решение, принадлежащее интервалу !х1, Х2), представим в виде х„= х! + 11 (х2 — и1) ., где и покажем, что р Е (О, 1). Действительно, поскольку Д (0 и 2'2 > О, имеем ео > !Х), !о+ з — 1'! > О, 2ш — 1'! + )'2 > О. Следова- тельно, ш+з — Д ш+з — !'1+(!о — х) 2ш — Я 2ш — 11+ 2'2 2!о — з'1+ з2 2ш — з'1+ з'2 и х„Е (Х1, х2). Несложно проверить, что Нз(х!) = 2'1, На! х2) = 12, Нз~(х!) = Д и Н11Х2) =Л.
Производная Н'(х) является квадратичной функцией, непрерывной на отрезке )Х1, Х2) и имеющей на его концах различные знаки. Поэтому в интервале она может изменить знак лишь один раз в точке х„которая является стационарной точкой многочлена Н21,Х), а именно точкой его минимума, так как производная меняет знак с минуса на плюс. Из необходимого условия Нз(х) = 0 экстремума этого многочлена получаем с учетом !2.30) квадратное уравнение 92 2. МЕТОДЫ ОДНОМЕРНОЙ МИНИМИЗАЦИИ Если Т"'(х„) = О, то т:„= х„— — искомая точка минимума функции т" (х) на отрезке (х|, .х2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
