Галеев Э.М., Тихомиров В.М. - Оптимизация (теория, примеры, задачи) (1050557), страница 3
Текст из файла (страница 3)
Метод Ньютона (метод касательных) Для того, чтобы решить залачу без ограничений нужно найти стационарные точки — решения уравнения /'(х) = О. Для решения таких уравнений численным способом можно воспользоватьря замечательным приемом, восходящим к Ньютону. Итак, пусть нам требуется решить уравнение Р(х) = О. (2) где 1гь мало, и в силу дифференцируемости функции Р О = Р(й) = Р(хь + Ьь) = Р(хь) + Р (хь)дь + о(дь).
Пренебрегая слагаемым о(дь), находим, что Ьь — — — Р(хь)/Р'(хо). Внеся эту поправку в формулу (2), получим новое уточненное приближенное значение корня: хьм = хь + Ьь. Таким образом, мы имеем следующее рекуррентное соотношение для нахождения последовательных приближений к нулю уравнения (1): Р(хь) хь«~ = хь— рч(хь) (3) Геометрически метод Ньютона эквивалентен замене дуги кривой у = Р(х) касательной, проведенной в некоторой точке кривой (см. рис. 1). Пусть для определенности нам надо найти корень уравнения (1), находящийся на отрезке [а, Ь[ и Р(Ь)Р"(Ь) > О. Положим хо —— Ь. Проведем касательную к кривой у = Р(х) в точке (Ь, Р(Ь)) = (хо, Р(хо)), В качестве первого приближения х~ берется абсцисса точки пересечения этой касательной с осью Ох.
Через точку (хиР(х~)) снова провалим касательную, абсцисса точки пересечения которой дает второе приближение хз корня х и т.д. (рис, 1). Очевидно, что уравнение касательной в точке (хь, Р(хь)) есть у = Р(хь) + Р (хь)(х — хь). Полагая в этом уравнении р = О, * = хь« „имеем формУлУ (3) 0 = Р(хь) + Р'(хь)(хьм — хь) «=ь ха м = хь — Р(хь)/Р'(хь). Здесь Р— двюклы непрерывно дифференцируемая функция одной пере- менной. Будем искать решение уравнения (1) методом последовательных приближений.
Если хь — приближенное значение корня, то точное значение корня Рис. 1. Заметим, что если в нашем случае положить хо — — а и, следовательно, Р(хо)Р'(хо) ( О, то, проведя касательную к кривой у = Р(х) в точке (а, Р(а)), мы получили бы точку хы лежащую вне отрезка [а, Ь[, т.е. при этом выбор начального значения в методе Ньютона оказался бы неудачным. Таким образом, в данном случае правильным начальным приближением х является условие Р(хо)Рь(хо) > О. Имеет место следующая ТЬорема. Нусть Р Е СЧ [а, Ь], В), значения функции Р(а) и Р(Ь) принимают разные знаки (Р(а)Р(Ь) ( 0), функция Р монотонна на отрезке [а, Ь], Р (х)Р«(х) Ф 0 ч х б [а, Ь].
Тогда, исходя из мочального приблихсения хо Е [а, Ь], удовлетворяющею неравенству Р(хо)Рь(хо) > О, махово вычислить па методу Ньютона единственный корень уравнения Р(х) = 0 с любой степенью точности. Если производная Р'(х) мало меняется на отрезке [а, Ь] или вычисление Р'(хь) слишком трудоемко, то в формуле (3) можно положить Р'(хь) = Р'(хо) для всех значений Ь = О, 1, 2,...; хь+~ = хь — Р(хь)/Р (хо). Такой метод нахождения корня уравнения называется модифицированным методом Ньютона. Геометрически этот способ означает, что мы заменяем касательные в точках (хь, Р(хь)) прямыми параллельными первой касательной, построенной в точке (хо, Р(хо)).
Подробнее о методе Ньютона можно прочитать в книге «Основы вычислительной математики* Б. П.Демидович и И.А. Марап [10]. Глава !. Экстремальные задачи 1.3. Правило решения Для решения конечномерной задачи без ограничен)гй следует: 1) Выписать необходимое условие экстремума ! г(прядка — аналог теоремы Ферма: У(х)=0 с=ь — =...
= г=О. дУ(х) дУ(х) дх! дх„ Найти точки х, удовлетворяющие необходимому условию 1 порядка (эти тачки называются стационарныма). 2) Проверить выполнение условий экстремума П порядка в каждой стационарной точке. Выписать матрицу вторых производных а) Проверить выполнение достаточных условий экстремума — исследовать ее знакоопределенность, т. е. посчитать последовательные главные миноры матрицы А: А! ь — — ссес((аб);,,), я = 1,...,п. Если все ее они положительны, т.е. А! ь > О, и = 1,...,п, то точка х доставляет локальный минимум в задаче, В б 1оспнп у. Если все ее последовательные главные миноры чередуют знак, начиная с отрицательного, т. е, (-1) г!ес А! ь > О, !е = 1,..., и, то точка доставляет локальный максимум, и б 1осшах у.
Ь) Есяи не выполняются достаточные условия экстремума, то надо проверить выполнение необходимых условий — исследовать ее слабую знакоопределенность, т.е. посчитать главные миноры матрицы А определители матриц размера !г х !г, составленных из строк и столбцов / асн, ... аг,г„~ с номерами !!,...,!ь! АЬ, ц: =!Се! аяа ...
аьй Если матрица А не является неатрицательно определенной (А р' 0), т,е. не выполняется условие, когда все ее главные миноры неотрицательны, т.е. Аь, ц > О, 1 < г! « ... 1ь < и, й = 1,...,п, то тачка х не доставляет локальный минимум, х К !оспин У. Если матрица А не является неположительно определенной (А ф 0), г. е. не выполняется условие, когда все ее главные миноры чередуют знак, начиная с неположительного, т.
е. ( — !)ьАО б > О, 1 < с, « ... !ь < и, Сг = 1,...,а, таточка х недоставляетлокальный максимум, х И!осгпахУ. 1 1. !ьанечнамериые задачи без ограничений 1.4. Прис!(еры Пример б У(х) = У(х!,х!) = хс — х!хс+ хз з— 2х! + хс — ехсг. Необходимое условие экстремума ! порядка: У (х) = 0 '"==а ду(й) ду(х) г 2х! — хс — 2 = 0; дх! дхс Решая эту систему, находим единственную стационарную точку х = (1, 0) /дсу(й) ! / 2 Матрица вторых производных = ~ ) по крн~дхсдх.у' 'с — 1 2 г' !а=! терию Сильвестра положительна определена. По достаточному условию локальнога экстремума функции нескольких переменных тачка (1,0) б 1оспнпУ.
Поскольку функционал является квадратичным, то (1, О) б аЬзгпсп У, а Я„,„= -с-са. пример 2. у(х) = у(хс,хз) = х", +х~з — х', — 2хсхз — х, — ! ехсг. Необходимое условие экстремума ! порядка: дУ(й) дУ(й) У 4х! — 2х! — 2хз = 0; У'(х) = 0 е=ь = = 0 х=ь дх! дхг 1. 4хсР— 2х! — 2х! = О. Решая эту систему уравнений, находим стационарные точки х ! (х„хз) = (1,1), х~ = ( — 1,— 1), х' = (0,0). Дси проверки условий П порядка выписываем матрицу вторых производных: дх;дх! . 2 12222 2 !р,,~ ( — 2 ~О) ' 1уц ( — 2 — 2) ' Матрица ( 2, у! по критерию Сильвестра положительно апре!' 10 — 2'! делена.
По достаточному условию локального экстремума функции нескольких переменных точки (1,1) н ( — 1, — !) доставляют локальный минимум функции У. / — 2 -21 Матрица ~ 2 ) по критерию Сильвестра не является ни положительно, ни отрицательно определенной. Она является неположительно определенной матрицей (А < 0) и не является неотрицательна определенной матрицей (А ~ 0).
Следовательно, не выполняется необходимое условие локального минимума. Поэтому х' = (О, 0) К !оспин У. Поскольку У(сс,— !с) = 21с" > 0 = У(хз) при малых !с ~ О, то хз Е!осгпаху. Очевидно, что 8 м = +со. 21 20 Глава 1. Экстремальные задачи У К 2 К 1(хг хг) 51п Хз Хг Пример 20. Имеется единственный локальный экстремум, не являюгцийся абсолютным: ?: К вЂ” К, 2(хг, хг) = х, — хз + 2е *'. Необходимое условие экстремума ! порядка в конечномерной залаче без ограничений: дхг дхз ( -2хг — — О, (= хг = О, 2е л' = 1 00 -хз = 1п -' = — )п 2 сь хг — — х ггг(п 2; Хз = О.
Получаем в задаче три стационарные точки й' = (0,0), х~ = (гг!и 2,0), х) = ( — чг(п 2, 0) . Для проверки условий П' порядка надо выписать матрицу вторых производных в каждой стационарной точке: д У(х) (2 — 4е *2+ 8х,е *2 0 дх;дх / 0 — 2/ 20=1 О -2)' ! ! ( О -2)' г' — 2 0 ) Матрица вторых производных ~ ( по критерию Сильвестра является отрицательно определенной: А, = — 2 < О, Аз = 4 > О.
Поэтому по лостаточному условию второго порядка стационарная точка х Е г !оси)ах. Очевидно, что д,ь,„„„—— +ао (/(хг, 0) — +са при хг — +са). ) 41п2 0 2 Матрица вторых производных ~ 2( па кРитеРию Сильвестра не является ни положительно, ни отрицательно определенной и более того не является ни неположительно определенной матрицей (А К 0) и ни неотрицательно определенной матрицей (А р' 0), Следовательно, не выполняется неабхолнмое условие ни локального максимума, ни локального минимума. Поэтому стационарные точки х, -2 хз (? 1асех(гг.
Очевидно„что Байзгпах — — +со. Действительно, функция 2(х1,0) = — лг хг + 2е *2 — +са при хг — +оа. Значит, у функции З имеется единственный локальный экстремум в точке У = (О, 0), не являюшийся абсолютным. б 1. Коиечномернме задачи без ограничений Пример ! 7. ))!о»гнали утверзкдать, что если функция одной леременной имеет в какой либо точке ггокальный минимум, то в некоторой достаточно малой окрестности этой точки слева от точки функция убывает, а справа возрастает? Нет. Контрпример: у(х) = 2, + знт л? (о, х = О. Ясно, чта х = 0 Е а)251п(п 2. С другой стороны, в любой окрестности нуля и справа, и слева производная 2" (х) = 2х(2+ 5(п -') — соз -', х Ф О, принимает как положительные, так и отрицательные значейия, т.е.
функция 1 и возрастает, и убывает. Пример !2. Имеетг» бесконечное число локальных максимумов, но нет ни одного локального минимума: Необходимое условие экстремума 1 порядка: дУ(*) дУ(*) (-2х, =О; /*, =О; Стационарные точки х = (О,-', + йя), й Е л.. Для проверки условий П порядка надо выписать матрицу вторых производных в каждой стационарной точке: дх дх 0 — гбпх2 ( — 2 О 1 А) =( 1, А! ( — 2 ОО! (0,2+2»г) ( Π— ),г ' (0,$+(2ь+1)г) ( О 1 / гг-2 0 ) Матрица ( 0 1 ! покритериюСильвестраявляетсяотрицательно определенйой: Аг — — -2 < О, Аз =- 2 > О.
Поэтому по достаточному условию второго порядка (О, 2 + 2пя) е !осгпах 2 '02 п е л.. гг -2 0) Матрица ~ у! по критерию Сильвестра не является неотрицательно определенной матрицей (А ~ 0). Следовательно, не выполняется необходимое условие локального минимума. Поэтому точки (О, 2 + (2п+!)Х) не поставляют локального минимума. Точки локального минимума могли быть только среди стационарных точек, но там их не оказалось. Следовательно, нет ни одного локального минимума. гг Глава !. Экстремальные задачи 1.5.
Задачи, упражнения В задачах !.1-!.17 без ограничений найти стационарные точки, проверить их на экстремальность, а также найти все локальные и глобальные минимумы и максимумы. 50 20 1.1. у(х„хз) = х,х, + — + — — > ехгг. х> хз 1.2. у(хи ха) = х~ — хз — 4х> + бхз ехгг. 13.
у(х>,хз) =5хз+4х,хз+хз — !бх, — !2хз — ехгг. 14, у(х>,хз,хз) = ха+ хз+ хз — х>хз+ х> — 2хз ехгг. 1 5. у(хьхз хз) = хз>+ хз~+ 2хз+ х>хз+2х хз+Зхзхз х> ехгг 1.4. у(хнхз) = х> +из — Зх>хз — ехгг. 1.7. у(х>,хз) = Зх>хз — х>хз — х>хз ехгг 2 з 18. у(х>,хз) =х, +хз (х>+хз) ехгг. 1,9, У(хи ха) = 2х, + х, — х', — 2х, ехзг. 1.10. у(х>,хз) = х,хз!п(х, + хз) ехгг.