Б.П. Демидович, И.А. Марон - Основы вычислительной математики (1132358), страница 63
Текст из файла (страница 63)
Л. Мвроя Предполагается, что вектор-функпия «р(х) определена и непрерывна вместе со своей производной «р (х) = «Г — 1 в выпуклой ограниченГд р;1 ) дхт~ ной замкнутой области 0«=Е„. В атом параграфе мы будем пользоваться двумя нормами: )) х)) = шах) х«) л )) х))« =,Я~ ) х;). «=« Относительно области 0 введем нормы: )) «р'(х) Ц«=шах)) «р'(х) Ц хчо (2) )) ф' (х) Пп = шах )) «р' (х) )) „ (3) «ео гдв л )) «р' (х) )) „= шак „~, ~ — ' « (2') (3'] Теорема. Пусть «рункции «р(х) и «р'(х) непрерывны в области О, причем в 0 выполнено неравенство !) «р' (х) )), ~ ц < 1, (4) где ц †некотор постоянная.
Если последовательные приближения х«я+и «р(х«е«) (р=О, 1, 2, ...) не выходят аз области О, то процесс итерации (5) сходится и предельный вектор хе= 1)ш хпн О~ пвляется в области О единственным решением системы (1). Доказательство. В силу теоремы 1 предыдущего параграфа достаточно показать, что отображение н=«р(х) (6) прн наличии условна (4) явлается сжимающим в области О в смысле л«- нормы.
482 птивлижкннок ткшкник снсткм нклннкйных ттлвнкний [гл. хш 9 1 П втотов достлточное ьсловие сходимости пгоцессх итеткции 483 Пусть х„х Е О и у« = «р (х,) (« = 1, 2). На основании следствия 1 к лемме 1 из $ 2 имеем: Ц у, — у, Ц вЂ” — Ц «р (х,) — «р (х,) Ц„( ( Ц х, — х, Ц„Ц «р' (ь) Ц„('11 х, — х, Ц„Ц «р' (х) Ц,. Отсюда Цу,— у, Ц„(д Ц х,— х, Ц„, где О (д < 1, что и требовалось доказать. Следствие.
Процесс итерации (5) сходится, если с»и~ дх ~~«7;» 1 («=1, 2, ..., и) (7) !=« при х Е««. Очевидно, нз системы неравенств (7) вытекает условие (4) теоремы. 3 а м е ч а н и е. На основании теоремы 1 из 9 9 для приближения х«ю получаем следующую оценку: Цх"-х Ц„( —,Цх"-х' Ц. (р=О, 1, 2, ...), где х"'=«р(х«ы) й 11е. Второе достаточное условие сходимости процесса итерации Прежде чем переходить к доказательству теоремы сходимости, использующей нормы Ц«р (х)Цп, выведем предварительно одну оценку для разности значений вектор-функции, аналогичную теореме о среднем и представляющую также самостоятельный интерес. Л е м м а.
Если вектор-функ««ил Л (к) у(х) = ,~„(х) непрерывна, вместе со своей производной у'(х)» в.выпуклой области. содержащей точки х и х+«ьх, то Цу(х+ «1х) — у(х) Ц, ~ Ц дх Ц«. Цу'($) Ц„(1) где $=х+0«ьх и 0 < 0 < 1. до к аз а тел ь ство. рассмотрим вспомогательную функцию Ф(1) = ~е«1~«(х+уйх) — ~«(хЦ, г « где 0(1(1-скалярный аргумент н е« вЂ” система чисев, прииммв)о. щих значения — 1, О, 1. Очевидно, Ф(0)=0. Применяя теорему 1Ь» 484 пгивлижкннок гашении систкм нклинейных хгавнений [гл. хш Лагранжа о конечном приращении функции, получим: ~'. з,.
[у, (х+ Лх) — у, (х)1 =-Ф(1) — Ф (О) =Ф'(О) = С=~ )ю(%) Дх дху где й=х+ОАх и 0<0(1. Отсюда, учитывая, что [е;[(1, будем иметь: и ~~', е, [у; (х+ Ах) — у'; (х)1 ( и и л л -ХЕ!'М"! [,[=Х[,(Е~";„"'! (2) Так как л л Е ~ д ~ ( ~ ~ ( ш 3 х ~ ~ ! д ~ й ) ~ ц у ( н ) ц Гт *у 1 Сиь у то, усиливая неравенство (2), получаем: и л .кл в~ [у;(х+ гьх) — у;(х)1 = лл [дх>! Цу'(й) Ц,= л =ЦХ(в) Ц, Х [йх,[=ЦУ'(~) Ц, ЦйхЦг Полаган в последнем неравенстве ее=ада[у;(х+Ьх) — у~(х)) (1=1, 2, ..., л), окончательно находим: Х [у,(х+дх) — у,(х)[~Цу'Д) Ц,ЦдхЦ„ т.
е. Ц У(х+ йх) — У (х) й ~ Ц йх Ц с Ц У (и) Ц что и требовалось доказать "). ") Если непосредственно применить теорему о среднем к каждой компоненте вектора У(к+ ох) — у(л), то получается оценка. зависящая от значений производных в ра зли ч н ых точках в; (1=1, 2, ..., л) дЛ(й;) дху интервале (х, к+ йх). Неравенство (2') показывает, что можно ограничиться значениями производных ' з одной и той же точке ф~ (х, я+Ах). д6 (й) дху $12] метод скотейшего спзскл (метод гтлднентл) 485 Т е о р е и а.
Пусть вектор-функция ц~ (х) непрерывна, вместе со своей производной ~р' (х), в ограниченной выпуклой замкнутой области О и ((др'(х))Ц! (Ч < 1 (3) где д — постоянная. Если х'ь' Е О и всв послгдовательныг приближения »'"+"=др(х"') (р=О, 1, 2,,) (4) также содержатся в О, то процесс итерации (4) сладится к единственному решению уравнения х=- ц~(х) (5) (д = 1, 2, ..., п). Замечание. На основании теоремы из й ния хмч имеем следующую оценку: Ц х" — хов Ц м Е Ц х'д' — х'ь' е где хсо = ~р (х'ь') 1О для приближе- Цд й 12".
Метод скорейшего спуска (метод градиента) Пусть имеем систему уравнений уд(хд, х, ..., х„)=0, гд(хдг хд~ 1 хь) ~' (х„х, ..., х„) =0 в области О. До к азате л ь ство. Докажем, что отображение у =др(х) является сжимающим в О в смысле 1-нормы. Пусть хд, х, ~ 0 и уд = ~р(х;) (1= 1, 2). Используя лемму, имеем: (!У,— уд Ц =Ц р(хд) — р(хд) Цд(Ц»д — хдЦд Цт'(8) Ц„(5) где $ЕО. Так как Ц др' (8) Цд ( шах )! ~р' (х) Ц, = Ц <р (х) Ц1д ( у, то из неравенства (6) получим: !!уд-уаЦд =ЧЦхд — хд(!д, где 0 д(1.
В силу теоремы из $ 10 теорема является доказанной. Следствие. Процесс итерации (4) сходится к единственному решению уравнения (5), если при х ц 0 выполнены неравенства 486 пгивлижвннов гашение систем нелинейнык тглзнений [гл. хш или в матричной форме ,у(х) =О, (2) уа )а где у= ул Предположим, что функции Д; действительны и непрерывно дифференцируемы в их общей области определения. Рассмотрим функцию У(х) = ~~р ~[у;(х))а =(у(х), у(х)). г=г Очевидно, что каждое решение системы (1) обращает в нуль функцию У(х); наоборот, числа хы х, ..., х„, для которых функция У(х) равна нулю, являются корнямн системы (1).
Будем предполагать, что система (1) имеет лишь изолированное решение, которое представляет собой точку строгого минимума функции У(х). Таким образом, задача сводится к нахождению минимума функции У(х) в л-мерном пространстве р(хан> Е„= [х„х„..., х„). Пусть х †вект-корень системы (1) и хин в его нулевое приближение. Через точку хш' проведем поверхность уровни функции У(х). Если точка х'е' достаточно близка к корню х, то при наших предположениях поверхность уровня У(х) = У(х'а') будет похожа на эллипсоид.
Рнс. 60. Из точки хш' двигаемся по нормали к по- верхности У(х) =У(х'м) до тел пор, пока эта нормаль не коснется в некоторой точке х'н какой-то другой поверкности уровня (рис. 60) У (х) = У(х<1>). Затем, отправляясь от точки х'", снова двигаемся по нормали к поверхности уровня У(х) = У(х'и) до тех пор, пока эта нормаль не коснется в некоторой точке х'а' новой поверхности уровня У(х) =У(х'"), и т. д. Так как У(х'е') ) У(х'н) ) У(х'") )..., то, двигаясь по такому пути, мы быстро приближаемся к точке с наименьшим зна- $ 12) метод скогвйшего спгска (мвтод ггадианта) 487 ченнем У (дно «ямы»), которая соответствует искомому корню х системы (1). Обозначим через д1/ о»г 7У(х) = д[l — й»«в градиент») функции У(х).
Из векторных треугольников ОМ М„ОМ,М„... заключаем, что х'г+п=х'гч — Х ЧУ(хоо) (р=О, 1, 2, ...). г Остается определить множители Х . Для этого рассмотрим скалярную функцию Ф())=У(х — ) рУ(х )1. Функция Ф (Х) дает изменение уровня функции Увдоль соответствующей нормали к поверхности уровня в точке х'г'.
Множитель Х = а надо выбрать таким образом, чтобы Ф (Х) имела минимум. Беря производную по Х и приравнивая ее нулю, получаем уравнение Ф Ю-,— "„У[х — )рУ(х И=О. (4) Наименьший положительный корень уравнения (4) и даст нам значение Х . Уравнение (4), вообще говоря, нужно решать численно. Поэтому уйажем метод приближенного нахождения чисел Х . Будем считать, что )«-малая величина, квадратом и высшими степенями которой можно пренебречь. Имеем: » Ф(ц=Х (гг(х' — Ари(х )ц*. Разлагая функции у~ по степеням Х с точностью до линейных членов, получим: *) Градиент функции 0(х) (обозначается ягайло илн рУ,.где символ и называется ноблей) есть вектор, приложенный в точке х, имеющий напра.
вленне нормалн и к поверхности уровня функции в данной точке в сто- дУ рону возрастанив 0 н длину, равную —. дл Справедлива формула йи зи аи 70 = — аз+ — ез+... + — ею даг дк» ' Эл„ где аг (»=1, 2, ..., и)-орты пространства е . ф 12] метод скооейшеГО спгскА (метод ГРАднентА) 489 где для краткости положено ]"г =у( ' '); ЧУ =]3(хш), Р причем хо+и=«в' — ]г Уl'ЯУ' (р=О, 1, 2, ...). (6) о Если допустить, что функция у(х) дважды непрерывно дифференцируема в окрестности искомого корня х, то можно получить более точные формулы для поправок Ххш'=холоп — «вл (см. 121).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
