Э.М. Галеев, В.М. Тихомиров - Оптимизация - теория, примеры, задачи (2000) (1125255), страница 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.
Экстремальные задачи У К О К 1(хг хг) 51п Х2 Хг Пример 20. Имеется единственный локальный экстремум, не являюгцийся абсолютным: ?: К вЂ” К, 2(хг, хг) = х, — хз + 2е *'. Необходимое условие экстремума ! порядка в конечномерной залаче без ограничений: дхг дхг ( -2хг — — О, (= хг = О, 2е л' = 1 00 -хг = 1п -' = — )п 2 сь хг — — х ггг(п 2; Х2 = О. Получаем в задаче три стационарные точки й' = (0,0), х~ = (гг!и 2,0), х) = ( — чг(п 2, 0) . Для проверки условий П' порядка надо выписать матрицу вторых производных в каждой стационарной точке: д У(х) (2 — 4е *г + 8х,е *! 0 дх;дх / 0 — 2/ Од=1 О -2)' ! ! ( О -2)' г' — 2 0 ) Матрица вторых производных ~ ( по критерию Сильвестра является отрицательно определенной: А, = — 2 < О, Аг = 4 > О. Поэтому по лостаточному условию второго порядка стационарная точка х Е г !оси)ах.
Очевидно, что д,ь,„„„—— +ао (/(хг, 0) — +са при хг — +са). ) 41п2 0 2 Матрица вторых производных ~ 2( па кРитеРию Сильвестра не является ни положительно, ни отрицательно определенной и более того не является ни неположительно определенной матрицей (А К 0) и ни неотрицательно определенной матрицей (А р' 0), Следовательно, не выполняется неабхолнмое условие ни локального максимума, ни локального минимума. Поэтому стационарные точки х, -2 хз (? 1асех(гг. Очевидно„что Байзгпах — — +со.
Действительно, функция 2(х1,0) = — лг хг + 2е т — +са при хг — +оа. Значит, у функции у имеется единственный локальный экстремум в точке У = (О, 0), не являюшийся абсолютным. б 1. Коиечномернме задачи без ограничений Пример ! 7. ))!о»гнали утверлкдать, что если функция одной леременной имеет в какой либо точке ггокальный минимум, то в некоторой достаточно малой окрестности этой точки слева от точки функция убывает, а справа возрастает? Нет.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
