Корн Г.А., Корн Т.М. - Справочник по математике для ученых и инженеров (947387), страница 152
Текст из файла (страница 152)
Дальнейшее развитие эт г д рст атегиям, включающим изменение шага и предпочтение определен- ных направлений, зависящих ст прошлых успехов илп про водит к стратегиям, махов, () слави й у . ый экстремум (см.также ап, 11,24, !14)я(1.43) залечи яа услаяяый аястрамум с уравнениями гвкасй ф) (х, х, «„) = мажяа решать методом ясаамагатеяьяых функций, дабааляя я еву ф ясса аман фуяяцив к / [х х ... к ) члеа Яица 2„' К!,'сг!(х х ..., к„)( или ~чы К,.ф, (х ...к ), 1 2 . а гда каждый множитель К,.— иекаюрае залысое пало р жительяае числа а и атысяаяяя минимума (атрицательиае — при отыскании ма симу ).
— „ . аа к ыа, а ся — четяае папажятекьяаа чакка, "у е . С щестауют араграыюы па аптиыиэацяя яа цифравык ЭВМ, включающие вы меяяющейся стратеги» пояска в случае медленно с Вс й ха вместя 00! расчета координат градиента, то предпочпта1от продолжать расчеты в вычисленном направлении до тех пор, пока больше нельзя уточнить исследуеыуп функцию, в только после этого снова пересчитывать координаты градиента. Ряс. 20 2 1.
График ясслелусмай яа минимум функции в случае двух яеэяяисямых пера. меяяык. Нассаэасса три ыияяыуыа, ливии уравяя и линии яаяскареащега спуска В агам пввыеРе зсе тРи мииимУма фУЯЯЦаа Р (ка х,) имеют оДно и та же ЯУлеаае эиачеиие. 20.2-8. Метод Ньютона и теорема Канторовича (см. также пп. 20.2-2 и 20ТНЗ). (а) Метод Н ь юто п а.
Выбирая некоторое начальное приближение х[О), находят последовательные понблцжения х['+'1 путем решения системы лянейиых уравнений (1=1, 2, ..., и), (20.2-31) дк з е-! гд: значения функций [/ и частных пронзводпых д[удха берутся прз х/с = х[„'1 ! = О, 1, 2, ... (Ь) Теорема Канторовичи о сходимости. Предполои(нм, что мзтрипз [д[удхй) имеет обратную матрицу (п.
13.2-3) [д[//дха] ! =— = — ',! ы [хы хз, ..., х„)) для рассматриваемых значений хй. Пусть Л, В, С вЂ” такая паложительиыс числа (нормы матриц, п. 13.2-!), щла а начальной толке х;=-х;: . , со! шах ~Д !Ги,[. Л, к=! п)ах .5' / Гсз[„ /щю В, С ~ зл/). (20.2-32а) К=) [.ели [с [х„х,, ..., х„) дзиждэс непрерывно диффлренс(ирусиас и удааллтаоряюас у лозсс о т лс/.
— ! — С (с =1, 2, ..., ) (20.2-32й) /, К=) д,т всех тачек (х„ха, ..., и) а кубической области шах х[о) = ' (! У' 1 2ЛВС), (20. 2 л33) 20. 3-1. (20.3-1) к »яду Т„Т„, ... Т,Ах= Т„Т„,,„т Ь уы ам а!з .. агк уз, Таз азз .. а, Тл! Тлз Тлэ " Уггл с помощью рекуррентных формул: уц=аи (1=1, 2...,, л); а!»ьм 1 (0=2, 3, ", л) лы й — 1 Т;й=а;а — ~,' Тна]з 1=1 (1, 1=2, 3, ..., л; 1»й), (20.3-3) Гл.
20 численныГ методы и конечные Рйэности то сислмма (27) илшст решение (хы хз, ..., хл) з той же области (33), и скорость сходимости оцсниеается так: шах х! — х[(1( ( = (2АВС)м Это указывает на относительно быструю сходимость. 20.3. СИСТЕМЫ ЛИНЕЙНЫХ УРАВНЕНИЙ И ОБРАЩЕНИЕ МАТРИЦ. СОБСТВЕННЫЕ ЗНАЧЕНИЯ И СОБСТВЕННЫЕ ВЕКТОРЫ МАТРИЦ 20.3-1.
Методы исключения. (а) Рсшенне системы линейных уравнений ацх, + а!эхе+... + ашх„= Ь(, а„х, + а,яхз+... + а,лх„= Ью (20.3-1) а„,х, + а„,хэ+... + а„„хл = Ь л по правилу Крамера (п. 1.9-2) требует слишком большого количества умяо- женнй, если л»4. Излагаемые неже методы позволяют решать систему П) путем последовательного исключения неизвестных. (Ы Метод исключения по главным элементам (метод Гаусса).
Пусть а — коэффициент, наибольший по абсолютной величине. Ы Чтобы исключить х из 1-го уравнения (1~1), уыножим 1-е уравнение па у а /а н вычтем нз 1-го уравнения. Затем повторяем этот процесс для исклю- Ы 1»' чения другого неизвестного из оставшихся л — 1 уравнений и т. д. (с) Компактная схема исключения.
Находим х„, х„(, ..., х, в указанном порядке из уравнений х(+ ашхх+ сс»зх, +... + а,лх„= 5„ х, + агзхз+ .. + ссэлхл = []я (20.3.2) хл=рл после вычисления элементов следующей л )( (л+1)-матрицы! ! — 1 а а) ~ Т.а!й (1,9=2,3,...,л;1(й), 1 гй 1=1 1 — ! (Ь ь [)1 И вЂ” о;1 ..., ) ти ) 1=1 20.3-2. 20.3. СИСТЕМЫ ЛИНЕГНЫХ УРАВНЕНИИ Н ОБРАЦ(ЕНИЕ МАТР!4Н ]ычисгснис олргз бе(!аш)=-У Уээ ... 1лю Ко»пзктпый метод требует меньшего количества промежуточных записе,'~, чем метод Гаусса, в стаповатся особенно простым, когда матрица [аы) сн».
ыетрпчна (ай! — — а!0). В этом вал(пом частном случае тщ аш= —" (1 ( й) (20.3-5) уг; Ш)М«тр ! гяяя ээл гсь метода ясклг*«еякя. Метод Гаусс» мажяо толкяяэть кэк лрссбрэээээяяэ данной системы (1) эядэ с гяьюспю яйглэчэвэтэтьяостк яэоссбсявьгх ьэтряц т, т...,, т „, яы ярэелых тэк «теме (2). 'гт бм О УШЮЦЭЛСЯ М«»Р ЦЭ тлтл ! ...
Г»А бЫЛЭ ТРЕУ- ЛЬ й "ЭТР Яэй. ЭХ Э Крэ э э э, э компактной сх мэ рэгь яцет эб ягы к»»як яря«гэй мэт эцы я б ээггггя т тэкйй, чтобы с( г«я» тлк = гй имела треугял! ную форму (2). В. дру, . лцы, я которых эмэстэ умяйжеявя г«эээ ярямэяя«тся уыяяжешге справа. э ° у '(2) стреляются Некоторые яэ ь«эдяфвцярэгэяяых схем, прввэдэяэых я актер»туре [20Л], позволяют умэяьшять кэкяялекяе ашвбэк округлеякя. 20.3-2.
Итерационные методы (см. также пп. 20.2-6 и 20.2-7). (а) Итерационные методы имеют преимущество перед методами ясключспвя для таких систем линейных уравнений, которые имеют достаточно «03. от ршьсшг;ю» матрицу [аш), т, е. для ьоторых многие из а, особенно вдали главной дпзгонали, равны нулю. Такие системы (и притом очень большие) ш встреча!отса в задачах чнсленвого интегрированна дифференциальных уравнений с шстньп!и процзподны:«и (п.
20.9-4). Излзгаемьге ниж итерационные методы для системы линейных уравие. пяи (1) с действительными коэффициентаьш да)от последовательные йрнближснпя решения х;(!'=1, 2, ..., л) в виде (20.2-29). Непязкв, получаемые иа кажйои шаге втерацни, будем обозначать через ы 1! И=] 2 "°, л( )=О, 1, 2, ). роза> Ъ [1] й.=! * я м э ч э к к с Для мяягях ятерэпнсяных схем требуется, чтобм мэтркцэ кяэфэя цясятся А == [л,,) бмлэ яэркэльяэ с пэложятэльяс оярэдэлэявэй сяммстрячясй ягтью иг, 13.3-4) яля !тобы мэтрзцэ А была сяыметрлчяой я полэгкятельяя лпредслэяьяй (я. !3 3--"), Если для дэякой лштряцы каэффяця«ятов это услаеке ке эыооляевэ, тэ :"г.г«ээ я.гг, гсбэээть тэк яэрс«тэвять ялк яре«бр«ээээ«э дэкяые урэвяеяяя, чтобы полу.гть ятяйся-.«лько большие пяэгэяэльяыэ кяэф„'гяцясяты, кля мяжня р«гяэть гкякээлгггтггую ел[тему л л л м Л» э л хй= „;л л„;Ь( (6=1,2...»л) (зош-т) (=-! й=! 1=- 1 цэгртгэ когффзцяеятээ котярой сбяээтелько свммятрячяэ и пэлшкятэльво опредэ«евэ, если только мэтрнгхэ А ве эыражпсвэ.
(Ь) Простая итерация и итерация Зейделя. Преобразуем данную систему (путем перестановки уравнений и,'или умножения пх на постоянные) к такому виду, чтобы диагональные коэффнцненты ан были положительными н возмон(по большими. Начиная с произвольных значений (20.З-Я) или по методу Зейделя (20.3-9) р= ~ .'[!], 1=.! р= — Х [[1!з !=1 (!(|3)з я У Х лл(1!3(л)3 а=|а=! ). (20.3.1 П (Л ГЛ 11! Ь13 хГЛ л=! „(Л л !(Л ВЛ а а л 664 ГЛ, зд ЧИСЛЕННЫЕ МЕТОДЪ| И КОНЕЧНЫЕ РЛЗНОСТИ 20.2-2. х( 3(1=1, 2, ..., л), вычислим последовательные приближения по формуле ! простой итерации х! — х! а.. ! '! а.. !! а=! (1=1,2,...,л; [=0,1,2,...) , Е .„,У~ ,) "и в=! ь=! (1=1, 2... и; 1=0, 1, 2, ...) Обе схемы яросты, яо могут сходит»ся медлеиио иля яе сходиться совсем. положительная опрелелешюст» мегряцы [а. ] гарантирует сзоцимость. Ю (с) М е т о д ы о е л а к с а ц н н позволяют ускорить сходимость итерационного процесса при вычисления вручную.
Нач!Ния с произвольного приближения х(03 (обычио просто х(03 = 1, х(03 = «(03 =...=х( = О), пробуют 03 ! находвть последовательные приблвзксвия х(Л таким образом, чтобы свести и невязок (6) к нулю. На каждом шаге выписывают невязки [,. н комбинл- ((3 ру|от следующие методы: 1. Коордииал(лая релаксация. На каждом шаге «ликвидируют» наибольшую по абсолютной велвчине невязку !)(1 путем всправления одного только х: 1(Л х(!1-613 — (Л вЂ” г [!+ П=х(Л (! ~ !) (20 3 10) Для начальных шагов допустйм грубый подсчет х!!!+ 3. 1(-1- !3 2. Блочная и груллогал релаксш(ии. В некотором миозкестве («блоке») координат х(!3 приладим вм равные прнращенвя х! ((з- !1 |з-13 — х(Л зак, чтобы ликвидировать одну из веввзок [(1!+ 3 пли чтобь| свести к нул1о сумму всех невязок.
Этот последнии метод првмепяется, в частности, когда все начальные неиязкн [1 3 имеют одина|,о- (03 вый знак. При групповой ргликгации для выбранного мно!кества коордшшт х(Л приращенвя могут быть различными. 3. Сггрхрелаксация. Иногда можно ускорить сходимость релаксацив, изменяя злак регулируемой невязка и уменьшая ее абсолютную величину, вместо того чтобы полностью ликвидвровать ее па данном этапе. Методы релзксецяи оссбеяяо удобны сря рсшесии вручную большогс коля !ее!ее простых лязеазых рззиостяыз урзеиеияа, исяользуемыз обычно для ярябляжсязего решения урез»еаза с чзстяымя яроязводяымя (я.
20,9-2), эбфектиеяссть методов релзясация ео мсогоы зависит от и«зыков я искусства еычяслителя, з тзкже от знания ям девического сущестзз »сороса, (д) Систематическая сверхрелаксация применяется ири решении «разреженных» систем, возникающих а задачах численного интегрирования уравнений с частнымн пронзводнымн. Рассмотрим систему уравие- 20.2-2, заз, системы линснных у лвненин н Оврлщение мдтрнн 666 ипй (1), преобрззовапную так, (тобы все диагональные коэффициенты были равны 1(ам=1), и за»!еяим итераци|о (9) па следующую: ц †! л .Ы.а .»=-1 !с=-! (1=1,2,...,л; 1=0,1,2,...), где сверхрелаксациоииый множитель щу) 1 выбирается для ускорения сходи- мости. Методы выбора множителей ш.
описаны в [20.6[. (е Г ( ) Град и е нт н ы е методы мииямвзвруют некоторую положитель! ную функцию типа способам, изложенным в п. 20.2ЛЛ Если матрица коэффициентов [и,,] симметрична н положительно определена, можно вести расчет по формулам Если с»слякость имеет колеблющийся характер, тс ее можне ускорять путем умнажш|ия яоследяего члеяз формулы (1!! иа 0,9 при яекоторых зязчеияях 1, (!) Метод взавыиых градиентов. Пусть дана система линейных уравиепий (1) с действительной, симле!иричиой и лозожигпсльмо определенной мал:оицсй коэффициентов [а;з], и пусть х! 3 — начальное приближение.
10 Поломав о!. 1=[1 3 и вычислим последовательно ('! = ! 2, ..., л,) [' "=[[!3 — "=' . ~; а. (Л 1 ( 0 1 2 '1, (20.3-12) я л а !11+ !)с(!3 ааа а "ь .,1(+!3,1(„913 а= ! ь=| !! ор е!1!3 ! я и "лапа пл . Значениа [,' уловлетворяют формуле (б), Поп ! е т('1= ~к~~ ~~ ((3.1|3 2=1а=! отсутствии ошибок округления этот метод дает то«иог решение хт=х(з| после л шагов; сверх того, этот метод имеет все преимущества втерациоппой схемы, ио требует многа умножений, 20.3-3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
