Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 62
Текст из файла (страница 62)
Определяют ао, 6о пясие, что г'(ао)г(Ьо) с О; выбирают каким-либо образом точку со б (оо, 6с), например берут со = (ао + Ьо)/2 или за ге борут точку пересечения секущей, проходящей через точки (ао г'(ао)) (Ьо ДЬо)), с осью т.. После вычисления Дсо) за (аз, Ьз) принимают тот из отрюков (ао со) (сэ 6о) на концах которого,с(эс) принимает противоположные знаки, и т.д. Важной задачей является разработка эффективных мотодов решения уравнений отдельных типичных классов. Для нахольцения корней мною- члена Р(л) = аол"'+ ° +а как с дейспзительиыми, так и с комплексными коэффициентами таким метсдоы является метод парабол. При заданных приближениях к корню л„з, в„з, а„приближение вптз определяется следующим образом.
Строится интерполяционный многочлен второй степени, совпадающий с Р(л) в тачках вв з, к„с, ап. За в з, принимается корень этого многочлеиа, наиболее близкий к в„. В стандартных программах метода парабол эга схема подвергнута некоторой модификг.цин. 5 3. Методы спуска Для решения задачи минимизации функционала наиболее часто применяются мспюдм спуска. При задашюм приближении определяется какое- либо направление, в котором фуикцнонал убывжт, и производится перемесцеиие приближения в этом нвлравлеаии. Рели величина перемещения йй7 )З М и пу взята не очень большой, то значение функционала обязательно уменьппп си. Рассмотрим примеры методов спуска.
При исследовании сходимости метс,за Зейделя в случае системы уравнений Ак = Ь при А > 0 мы описали циклический метод покоординат. ого спуска минимизации функции Ф(х„...,:се,): при заданном приближвнии Ф(х",..., х',~„) отыскивается значение х~ = х'„при котором доститается иКФ(тч, тз,..., т,„), затем отыскиваеття значение хэ = х!, при ю котором досчитается шГФ(х(, хз, хэм..., те ), и т.д. Процесс пиклически пошоряется. Обозначим через Рак приближение, получаемое при спуске из х по координате:сь. Присваивая приближению, получыощемусп при спупсе по очередной координате, следующий номер, можно записать приближения мнпща циклического покоординатного спуска в виде '=р,кэ к = Рэрх,..., э е к '=Рэ,...Р~х, х' =Р,Рм...Р~к,...
е ы а При практической реализации этого метода возникает проблема минимизацви функций одной переменной. Рассмотрим отдельно задачу минимизации функций одной переменной Ф(х) при начшпноы приближении к точке минимума х = х". Так как эта задача обычно не может быть решена точно, то часто поступают следующим образом: берут неюпорые значения хе, х", и строят параболу у = Оз(х), удовлетворяющую условиам Яз(х~) = Ф(хо), Сз(хе) = Ф(хе) (2з(хй") = Ф(х'). Абсциссу х точки минимума Цз[х) принимаьтг за следующее приближение х'. Уже в одномерном случае можно построить пример, когда последовательность точек, получаемых по описываемому методу, ве обязательно сходится к искомой точке экстремума функции Ф(х).
Даже если на каждом шаге отыскивается абсолютный экстремум функции Ф(хм.,., х,э) по соответствующей коордднате, то уже при ш = 2 может случиться, что итерационный процесс схццится не к искомой точке абсолютного экстремума, а к некоторой точке локального экс- ~Дс* тремума. На рис. 7чй1 изобрвлсены линии уровня такой функции и получаемые приближенна. Спуск в циклическом порядке необязателен. Если из рассмотрения проводившихся ранее вычислений видно, что Рис.
7.3.1 спуск по каким-либо координатам обеспе- Глава 7. Рмпеиие систем велиягииых уравнений 333 чивает еаиболыпее убывание Ф(я), то иногда целесообразен более частый глуск по вгим координатам. В других случаях при каждом и после получения приближения тх выбираетсп некоторая совокупность координат г'(" 1)' ' ''' 'сах у('))' производятся зинависимые спуски по ксюрдинатам игой группы исходя из приближения х", т.е. находят точки Р,(„щха.
Далее вычпгляетгя шш Ф(Р(ь Их"), гст су( и сгютветствующая мвнимуму то гка Р(„ь)х припимаецл за х'мгц Иногда номер очередной координаты, по которой осуществляется спуск. выбирается недетерл1инированно. В этом случае говорят е случай. яом пакаарс)пнаглиом гпйскс. Другой вариант метода спуска — мгяих) иапскарейизша (гроса)еягпяого) спуска.
Следующее приближение отыскивается в виде х""' = хх — бьйгж1Ф(х ) (рис. 7.3.2). Значение б„определяетгя нз условия пап Ф(х" — дх (чж1 Ф(х")), т.е. этот алгоритм опять онтонг в псюледоиательной минимизации функции одной переменной Б . Как и в методе поксюрдинатного спуска, в методе наискорейшего спуска вег песбходимости полного решения вспомогаттльпой зада си минимизации функции одной переменной. В окрестности точки своего минимуьга эта функция меняется мало, и тщательное нахождение ее точки минимума не приводит к существенному 'х эффекту.
В плучве метода наискорейшего спуска вопрос об объеме вычислений при минимизации вспомогательных функ- Р . 7.3.3 ций одной переменной должен решаться также с учетом относительной трудоемкости вычисления значений функции Ф(я) и ее градиента. Для иллюстрации решения вощххл о выборе метода рассмотрим следующую типичную задачу: решается нелинейная краевая задача для стлстемы обыкновенных дифференциальных уравнений.
В гл. 9 будет показано, что зта задача сводится к решении> нелинейной сисгемы уравнений г(х) = рл Д(х)=Л(хн,*м)=О, г=1,...,ш 1зм ж у облццаюпгей следующими свойствами. Количество операций при отыскании одного значения /.(х) и при одновременном отыскании всех значений /,(х), г = 1,..., гп, в той же точке одинаково; обозначим его че1кн А.
Количество операций при вевссредсгвенном отыскании значений д/г(х)/Нгэ и при одновременном отыскапии всех значений д/„.(х)/дям 1 = 1,..., т, в той же точке цвгшаково. Обозначим его через В; обычно В » А. Тогда при решении задачи методом Ньютона целесообразна вычислять производные д/,(х)/дзэ, 1 = 1,..., ш, пользуясь приближюшой формулой д/,(ям..., вм) /г(зп", ту-и тэ + ~Л, збэп--, х. ) — /,(хы"., з;,, в„,) /г Облвсп, сходимости метода Нью гона обычно невевика, поэтому по крайней мере иа начальном этапе итераций целесообразно свести решение этой задачи к минимизации некоторого функционала и приыепить какой- либо пз методов спуска.
Рассмотрим простейший случай функционала Ф(х) = ~(Л,/;(х))з; ш1 множители Л, = сопвь Н' б, нвзыввел~ые ыасюпюбпмын, подбираются из условий конкретной задачи. Пусть х" = (хэю..., и„,) — полученное приближение и решено сделать спуск в оаправлении /ь = (Ап,..., Ьм), ~Щ = 1. Вычисляют щгиближенные значения производных в этом направлении: ]г = (/г(х + е/Л) — /~(х ])/с. (2) На прямой х = х .1-1/г имеем /;(х) ю /,(хэ) + ИП ппэтому следующее приближение х"+~ = х +ЙХ определвют из условия гпш) (Л;(/г(х )+М,)) .
г=1 Отметим, гго в данном случае существен вопрос о разумном выборе с в формуле (2). (По этому поводу см. з' 2.16.) Задача минимизации функции при наличии ограничений, так назыввыэвл задача условной минимизацвв, формулируется следующим образом. Игцется величина А= шГ Ф(тг,...,х ] ! --л 1лева 7. Рпиение сястем нелинейных уравнений 340 при условивх 1се(хм..., Яы) > О, х = 1,..., 1, (4) (5) При решении втой задачи возникают дополнительные трудности по сравнению с решением задачи охыскания безусловного леинимума, в которой ипьстся 1п( Ф(хч,..., я,) 1 о..., 1ен — нижняя грань Ф(сс,..., х„,) по всему пространству Н Непосредственное использование многих из описанных вьппе методов ствновитгя невозможным, и возникает необходимость в их модификации.
В то же время зада се минимизации функции при ограничениях типа (4), (5) является весьма актуальной для приложений. Например, суще- ствует целый рездеес математики — линейное преграььипроеание,— занима- ющийся решением задачи (3) — (5) в случае, когда Ф, чв, Ф,— линейные функции аргументов ясг Среди других методов, связанных с решением зцдачи (3)-(б), упомя- нем ыешодшгврайп. Строится ощледовательиость функций Фл(яс, .,я„,), удовлетворяющая следующим условиям: 1) Фл(ие,..., я,) определена при всех (хп..., я,); 2) пКФх(хм..., т ) = Ал -+ А при Л е оо; н, 3) если существуют точки (яс,..., х,„) и (х~,..., х„",) такие, что Ф(ям..., я„,) = А Фл(ты..., ят) = Аж то (ялс,..., хл,) е (ям..., яе,) при Л вЂ” е сю.
Вместо решения исходной задачи (3) — (б) решается залача отыскания минимума (пУФл(хм..., я„,) при досгаточно больших л. н Часто вместо первого условия на функцию Фх требуют выполнения более слабого условия. Функция Фл опредесена в точках некоторой од- носвязной области Сх, Фл(ям..., х,е) -+ оо при приближении точки (хм..., Яе,) к гРаниЦе области или пРи Яз+ ° ° +уз -+ оо (в слУчае, когда обласп, Сл неограниченная). В отдельных случаях условие 3) также несколько мцлифипдруется.
Приведем пример построения такой функции Фл. Для етого соппю- шения (4), (5) записываются в таком виде, что ро Фс будут определены пРи всех (хм..., х„,) (или пРи всех хг,..., хм из 61). Ввалится некоторая невозрастающая функция 5(1), определенная при -оо < 1 < со, такая, что 1пп 5(1) > О, Опс Ь(1) = О. Например, можно с-е — се взять 1 1 5(1) = — — — агсйб й 2 н $4. Другие методы сведения В качестве Фл(хы ° ., х ) берется функция Ф(,..., „)+л) Ф„( ы...,: „,)+л~б(лег(х, ...,: )).
Величие сзагаемо~о ЛФт(лы..., хм) заставляет смещаться точку экстремума (х~,..., х„",) в область, где ф,(хь..., х„,) = — О; в то врелсн как наличие слывемого ЛЛ(ЛФ;(хп..., хвй) заставляет смещаться точку экстремума (хлы..., хл ) в область, где ФЛ(хы..., х„,) > О. Метод штрафа обладает следующим недостатком. Оказываается, что при больших Л структура линий уровня Фл, как правило, такова, что схсдимость методов минимизации существенно замедляется. Искусство применения метода штрафа при решении конкретных задюг состоит в удачном выборе функции Фл такой, что при заданной бвнзости значений нижней грани (А-Ал( < с эамедзевне скорости сходимооги применяемого ишрационного метода будет минимальным.
В связи с отмеченными недостатками метода штрафа разребснано большое число других методов решения задачи условной минимизации (З)-(5). В 4. Другие методы сведения многомерных задач к задачам меньшей размерности Иногда полщно рассмотреть следующую формальную процедуру сведения многомерных задач к одномерным. Пусть ищется минимум А функции Ф(хм,.., х„,) в области са (хи..., х ) > О, г = 1,..., 1, Ф (х,, х,) = О у' = 1,..., Ф Можно написать равенство А= плп Ф(хг,..., х„) = пппФ,„(хм), и —.,в где Ф (хт) = пнп Ф(хм..., хю); гь...,г -1 минимум каждый раз берется по области определения минимизируемой Функции в соответствии с условиями (1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
