Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 53
Текст из файла (страница 53)
Отсюда получаем оценку числа итераций, обсспечггвагощих получение решения с то шестью е: и > пг =!оуц,(2/е) — — (!пЛо) !г~(2/с). Для многих задач число М/р оказывается очень большиы. Поэтому прн М/д — г со илгеем Ле = 1+ 2Л/д/М-~- О(д/М). Таким образом, 1в Ло 21/р/М, и, 0,5Г/51/!г 1в(2/е). Для сравнения расслштрим оптимальвый линейный одгввпаговый прог!все., иысющий, согласно (13), оценку погрешности ))х" — Х))з < ( ) ()х — Х))з; /М+Р! а (,М- д/ отскща получаем оценку числа итераций п>из= (йг ) !п М+дЛ 1 М вЂ” д е При М/р — г оо имеем М+р 2д 1М 1 !п — и от — — 1п —. М-д М 2 д е Глава 8. Численные методы алгебры "Галим образом, в этом сравнении оптимальный итерационный процес~ дает выигрыш в числе итераций примерно в ь/М/д раз.
Задача 2. Рассматривается итерационный процесс х' = х' г — т; г(Ах' ' — Ь), 1 = 1, 2, Пусть р нечетное и при всех Л совокупности те,..., трь — совпадают с совгжупно«тами т(2г — 1) 1 1г г = 2 (М4-д — (М вЂ” р)сги /1, с = 1,..., р"'. 2рь / Проверитгь что прн всех г = рь приближения х' совпадают с прибли- жениями, получаемыми по оптимавьнолгу линейному итерационному про- цессу. у, = 2 (М + р — (ЛХ вЂ” р) гое, ), 1 = 1,, 2 . Показать, что для такого итерационного процесса при вснх и = 2ь+г справедлива оценюг "— х < 4 хв — Х ((х — Х((т < „,, „, ((х -Х((з, ((хв - Х((т = О(Л;"дхе - Х((х.
Рассмотрим тгшичиую задачу математической физики, свгжящуккя к решению словены уравнений с большим глвошением М/р. Пусть в квадрате 0 < хм тз < 1 решается уравнение Пум:сова — Хги = / при нулевых условиях на границе. Зададг1мся сеткой «шагами Л = 1/1 и ншпплем систему уравнений, аппроксимирующих дяфферснцииьву|о зада ~у: О,е~ „— 2О„,„+ К,„ь„и„, лы — 2О„, +П ь„~ НР 1Р (28) лри 0 < пь и < 1; и„ш = О, если гп(1 — т)(1 — п)п = О. Матрица шой систел1ы является положительно определенной, и дпя все П = пйп Лг = И зш 1 — ) 2х, 3 гтЛ~ 2 (2) М = ипах Л, = 81 сое ( — / 81, Гябт (2/ т.е.
т/м/и 21/я. например, при шаге 1 = 30 выигрыш в числе итераций примерно е 20 раэ. Задача 3. Пусзь те = 2/(ЛХ+ р), тг = 1/М, тт = 1/д и совокупности ттг-... тхьм при каждом Л > 1 совпадают с совокупностнми величин 233 92. М л Зейд Прамлчаппе. При и — л ао илгеем М+р') т. М ) '-( -~.. ('Мед) «уМ+ л)1' +1 '«М — 1л/ Таким сбразом, прп бопьшвх а итерзцваннзя форлюула (23) близка к формуле 2 я'*+' = я" -~- ыл(я" — я" л) — — (1 -~- ил)(Ая" — Ь Р И+и (29) Если при п > 1 итерации будут пронззпаиться па мой формуле, то прп условии я" = х", я' = у' мот еторзпвониый процесс требует примерна малька >ке итерапвй, сколько итерационный процесс (23).
Задача 4. Для итерационного процесса (29) получить оценку погрошности [[лл" [[я с 2+ (*л- 1)(1 — 2е') 1 . (30) гл Указание. Пред<тавить погрешность в виде г" = ~ хмель где (ел.) — полл — — 1 вая ортогональная система собственных векторов матрицы А. Пцц(шзновкой в (29) получить разнастное уравнение, связывающее ял ', ял', я>~~ . Получить Явное выРажеиие Дпв Ял ли с его памошыо полУчить тРебУс мую оценку (30).
Задача б. Показать, что оценка (30) не мгакет быть улучшала на мно- жестве лгатриц, удовлетваумющих усзови«~ о(А) С [р, М]. 5 7. Метод Зейделя Пусть решается система уравнений Ах = Ь, все диыанвльныа злеменгы которой ненулевые. В итерационнолг методе Зейделя погз|ццавазгльно Гточняются компоненты решения, причелг уья компонента находится из Его уравнения.
Именно, если х" = (з|', ..,, х )т, то следующее прибли- В иачвле етого параграфа было упомянута, что при симметриззцни системы ее свойства могут ухудшаться. Действительно, пусть ззтгг процесс применяется к уже симметричной матрице А, т.е. переходим ат системы Ах = Ъ к системе А х = АЬ. Если у старой системы отншпение з лшксимельного и минимального собственных значений равнялась ЛХ/и, то у новой она будет (М/1л)з и скорость сходнмасти итерационных процессов будет меньше.
Глана 6. Численные меюды алгебры 286 аггхг 1-аггхг -1-.. + апвт =- бм аггхг -~-аггхг +аггхг-1- ° +аг х' =бг, гг -ы Вх"гг 4 Схв = Ь, [2) Отсюда получаел~ хшю =-В 'Сх" +В 'Ь. Таким образом, метод Зсйделя вквивалентеи некоторому методу простой итерации; пгитому для ого шкугимосги гтрн любом печальном приближь пии нсабхсдимо и достаточно, чтобы все гюбстеенггые значения ьютрицы В ~С по модулю были мсвыпе 1. Вгледгтвие равенства г1ег( — В-'С вЂ” ЛВ) = 1е11 — В г) г)егбС+ ВЛ) собствениыг значения матрицы (-В" 'С) являются корнями уравнения г)ег(С+ ВЛ) = О. Такилг образом, псобходимоо и достаточное условие сходимогти метода Зейделя можно сформулировать следующим образом: вге корни урав- нения агг агг 14) цолжвы быть по модулю меньша 1.
Часто можно предложить более удобные Лля применения достаточные усховия схолимости метода Зейдоая. Получить оценку ))хп — Х)), « ° ° д"))х — Х)) жение определяется из систеьпг гиотношсний Систему (1) можно представить в виде щ и аы О О ... О аю агг О ... О аг, Л агг аы Л аггЛ г1ег аггп Л она Л Задача 1. Пусть при всех г Е )агг) < 4)аа), д < 1. ггл О аш аы - ав» О О аю" аг„, О О О О 287 17.
М .д Зейл Рис. 6.7.2 Риг. 6.7.1 Проблема решения систем ли- х, иейпых уравнений яэляетгя модельной относительно более аю»кных задач рошення систем нелинейных уравнений и минимизации функций многих переменных. Для перенесения метода на более глож- 7« ные задачи важно понять его гиггГюлее «грубые» качссгэениые свой- х, сева, обсч:почина«ощип гхсдимостм Рис. 6.7>6 С этой целью наиболсс желательно получить гсометрическуго инчэриреяигщю метода. Обозначим черо:«Х„ плоглость ~ ойхг — Ь, = О. При получении приближения (з",»',..., тэ«', 1=1 хч г,...,г,",) из приближоиия (х~г+~,...,х,".»г, а, «~, ..., х„',] проис<опят перемещение приближения параллельно оси х, до перечечения с плоскостью бе Т»акиь« образом, геометрически метод Зейделя состоит э циклическом перемещении точек, глхггж.гствующих послгдоеа|оаьно получаемым приближениям, параллельно координатным осям к» до пересечения с плоскостями Тч.
Рис. 6.7.1-6.7.3 иллгострирунгг при гл. = 2 случаи, когда мепд Згйдгля сходится, расходини, имеет цикл (как ~оворяч; «зациклиэает«и»). Сравнение первых двух рисунков показывает, что сходимость погода Зейделя мсжсг изменить характер при пересганоэкс уран»юлий. Особенно интересная геометрическая картина возникает э случае, корса матрица А силгметричная.
Тео1»ема. Пусгпь А — еещесглвснисл сил«матричная полоэмотглько опрсселсинал моглроца. ТЬгдо же»иод уайда«л сходю»щся. 2(окаэаглсльсщво. При симметричной А имеем Р(у) = (А(у — Х), у — Х) — (АХ, Х) =(Ау, у) — 2(АХ, у) = (Ау, у) — 2(Ь, у). Если А > О, то (А(у — Х), у — Х) > О при у ~ Х, поэтому функция Р(У) ямеет минимум, и притом единственный, при у = Х. Таким образом, за- Глава 6. Числеввые меголм авгебрн 288 Рл=8()' алглг Ьл =О г г'=-1 (б) что и в случгю метода Зейделя. Таким образом, приближения покгюрдипвтного спуска минимизации функции Р(у) и метода Зейделя решения иг:ходной системы совпадают.
Если хп Р Х, то хотя бы одна из уравнений системы не удовлгнворяетсв и соответствующее значенио Р.'„, (х") д О. Выберол~ среди таких наименьшее. Тогда при уточнении компонент тз,..., гл г мы осчвемл в точке х", а при угочнепии компоненты хь происходит гмшцение з сторону меньших значений Р(х); щзи уточнении остальных компонент значение Р(х) пе вазраставг. Таким абрагом, Р(» Ш) ( Р(» ), Рс(х Ш) ( Ре(х ); Ро(х"Ш)/Ре(х ) < 1 завгому (6) дача оты«кения решении системы Ах = Ъ оказалась равносильной задаст отыскания единственного минимулга фу.нкпии Р(у]. Одвиы ллз методов минимизации функции многих исрсыенпмх является мшпод птоардиггаглггого спуска. Пусть имеется гзр1гблиэксззие (хг,..., з„„) к точке эксгремума фунт- а .е ции Р(хн..., я: ). Расс:мотриы фувкцшо Р(хг, тгс,..., я,"„) как функцик1 переменной а:з в найдем тачку хз ее х, минимума.
Затем, исходя из приближения (ял, хз,..., т„,), путам минимизация функции Р(тз, хг, хзе,..., ге,) но переменной хт находим следуюх'" щн. приближенна (х), .сг, хо зта ) Процесс циклически иовторянггя. Прв уто шенигг компоненты:сл происходят смещение по прямой, параллельной оси тл., до точки с наименьшим на атон прямой значением Р(х) = с. ЯсРис. 6.7.4 ио, чта зла точка будет точкой каса- ния рассматриваемой прямой и линии уровня Р(х) = с. Пгнтому в двумерном случва картина прибнижсний выглядит квк на рис. 6.7.4. Применим могол покоорлвпгатного спуска для отыскания экстремума функции Р(у).
Обозначвм Р(х) д (АХ, Х) =- (А(х — Х), х — Х) через Ро(х). При минимизации па иеременвой хл происходит пелюмещсние параллельно оси хл до точки, ще Т'„.'„==. О. Следовательно, новос значение яг оиргдшвнпзя из того же уравнения 37. Метод Зейлеля 269 при хв ф Х. Вследствие (3) имеем равенство г""~ = — В ~Сг", где гЯ = х" — Х. Соотношение (6) можно переписать в виде (АВ гСг", Ю гСг") р(гЯ) .=, — < 1 (Агв, гЯ) (7) Ро(х э')Уйэ(х ) < Л', Гэ(х") < Ла'Ко(х"). (8) и, таким образом, Из (3.8), (3.6) следуют неравенства гншЛА ((У вЂ” ХЦ < со(У) < шах Лл()У вЂ” Х)(~т Отюсда получаем оценку скорости сходимости — ., 6~" 7) —,-6~"~( .,"(! "-~)( (9) '7(ш(пЛл '() пш~Л'„Д пйпЛ' Теорема доказана.
Из рис. 6.7.5 можно усмсггреть, что метод Зейделя сходится быстрое, если направление осей эллишюидов блгюко к направлению координатных осей, т.е. матрица А близка к диагогяьчьпой. В случае, изображенном па рис. 6.7А, последовательные приближе- ния смещаются все время монотонно влево и вниз. Ъыая картина- монотонноо смещение отдельных компонент все время в одном и том х, же направлении †характер для раца «ластов матриц. При этом довольно часто монотонное смещение наблюдается именно у компононт решения, ~корость сищимости которых наиболсю пногал.
В этих случаях для ускорения пюдимости прибегают к мсшоду рслакаиспи, который заключаетсн в следующем. После угочнеиия каждой коордигаты по мепвб Зейделя произвсшится :мещение в том же направлении на ро часть этого смещения. Таким обраРис. 6.7.5 а эээ при г" Р' О. На сфере ((г ((г = 1 величина гс(г ) непрерывна, пснтому сна достигает своего наибольшего значения ро. Тйк как А > О, то всегда Р(г") > О и поэтомУ 1со > О. Положим эГРэ = Л. Всэедствие (7) имеем ЛЗ < 1. Очевидно, 1о(сг ) = Р(г") при зпобом с ,—1 О, поэтому р(гл) = фг" /()г" 1э) < Л при любви г". Отсюода получаем веравепсгво Глава 6.
'1исленные »ге»ольг алгебры 290 зом, приближения отыскивагаггя из соотнопгеггия ух"т' -!- рх" з ( — П)х ш+Р~ )+Сх =уг, ~1.,) (10) П вЂ” диагональная матрица с злементамв а„. по дишонали. Как показ практика вычислений, при А > 0 целыпобразно брать показатель рел сацни Р в пгелелел — 1 < Р < 1; в слУчв» О < Р < 1 метоД Резак»а. ции обычно называют мсгпадам сверярслаксацпа (или мшпш!ам аср релакшцпя).
На рис. 6.7.4 изображены символами о приближения метла Зейдгля, г — метода верхней релаксации прн р = 1/4. Например,,пля уменьшения погрешности в» ' рлз прн решении системы (6.26) метоцом Зейдсля требуется порядка с6 з!п(г ') итераций. Если применить метод верхней релаксации при р = 1 — ы6, ы > О, то потребуется порядка с(ы)!г '!п(г г) итераций. Подбор параметра ы в этой задаче требует летального рассмотрения. В частности, во многих случаях оптимальное значение параметра релаксации р опредегшется экгперимепгшьно, Иногда параметр релаксации р выбиршег завигзпцим от и и ь Для ~зучая А > 0»ще раз обратимся к гоометрической картине [см.
рис. 6.7.4). Поело уточнения колпзонсвты г, по мегцпу релаксации при -1 < р < 1 мы попадаем в точку, лежап1ую внутри илн на границе эллипсоида Р(х) = Р(х"). Рассуждая шк же, как при обосновании схаднмости иегова Зейдели, заключаем, что при — 1 < р < 1 всегда Ра(х"ш) < Ее(х"), зели х" и Х. ЗвДача2. Докззатгз что пРи У<шанин (Ря( < 4 < 1 метцц Релаксании хщснтся са скоростью геометричегкой прогрегсии. З 8. Метод наискорейшего градиентного спуска Распространенным методом минимизации функций большшо числа пере- генных является мсшад градпеншнага спуска.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
