А.А. Самарский - Введение в численные методы (1113832), страница 16
Текст из файла (страница 16)
е. для решения уравнения (4). Задача состоит е минимизации Д„(е) путем выбора В и параметров (т,). Начнем с простойп|нх итерационных методов. 2. Метод простой итерации. Для решения системы уравнений (1) мох~от быть пспользован метод простой игера~(ии у~,'-,1 = уЛ'~ — т (~~'„' апу)п — !'о, 1 — - 1, 2,..., х, (7) И==1 где т 0 — итерационный параметр. Запишем (7) в операторной форме: Ухе| ла +Ауь=/, й=0,1,..., для всех у,~7!. (8) Сравнивая с (3), видим, что метод простой итерации задается явной двухслойной схемой с постоянным параметром тт — т, $ 3. итегдционпыв мктоды 99 Существуют п другие варишггы метода простой итерации, например такой: ) ).м удтт = — ~ а пуд ((, ( ~~Р ал и,, Л 1вм Подставляя сюда 1+от я , (л ч и) (о (о я а(;Уд = ~~ а(,УА — апУд — — (АУ(,) — ())УА) Ф 1=1 где Б — (асбв) — диагональная матр)ща, получаем и) (о ( ~ е (о~ Уд, = Уд — —,~ адУ), я или, в каноническом виде, )) + Ауд =- ), (1 =- О, 1, ..., т = 1.
ад+1 — У), (0) (10) 1=1 1'=Ы 1 Из обеих формул компоненты вектора удд, находятся последовательно. Так, из (9) последовательно определяем (1) (2) (и) . уд.(1 уд-"1 . 1уА+1 чт (Л (-1 У сб — апуде() 1=1 и 'Ч (1) — а„уд 1=1-(-1 Хотя формально зта схема является неявной (В = 0 ~ Е), однако )) = (а((бо) — диагональная матрица и потому удз, определяется по явным формулам, 3. Метод Зейдезя.
Весьма широка на практике (особенно в тех случаях, когда информации о матрице А недостаточно) применяется итерационный метод Зейдеая в одной из двух форм; л 1=1 1 — 1(-1 1оо гл. Ит. Решение АлгевРАических уРАВнений Пользуясь (10), находим последовательно для 1 = й(, Я вЂ” 1, ...,1 и — 1 <и> ! <И> 'ь' с» Уз+1 — — — ~ ! —, ам,У1, 1=1 1 — 1 и 1=-1 1-М1 Запишем этот метод в матричной (операторной) форме.
Для этого представим матрицу А в виде суммы А=А +Р+А+, где Р = (а„бе) — диагональная матрица размера й Х 11', А (ац) — нижняя треугольная (поддпагопальная) матрица с пулями на главной диагонали, а„= О при 1~~ 1', ац =ац при 1~1', А'=- (а11) — верхняя треугольная (наддиагональпая) матрица с пулямп на главной дпагопали, ац = 0 ири 1<1, а„: =- ац прп ! >1.
!1з определения А, Р, А+ следует, что -1 Ру =- а»у, А у =- ~~ а»у <» <» — ц» ч~ 1'1 А у~» ~~~ ацу'л, (Л --; Р) уо» =- ~~драпу". ,: -;Е1 Поэтому уравнение (10) можно зашгсать в виде ((А~+Р)у1„,)»+(А уг)с» =!'", 1=1, 2, „й', или, в вгчгторной форме, (А+ + Р ) у,11 + А у1 =!, После очевпдныт преобразований (Аэ +Р)у1 ° 1+ А уь (Ае + Р)(у у1) + + (А + (Ле+ Р))у„= (А++ Р)(у,„, — у,) + Ау„ запшпем метод Зеяделя (10) в каноническом виде: (Р+ Аэ)(у1э1 — у,) +Ау, = !, й = О, 1, 2„... (1!) Сравнивая с (2), видим, что метод Зейделя (10) соответ- 1О2 ГЛ, гн. 1'ГП[ГПИГ ЛЛГГПРЛН'!ЕСННХ ХРЛВПЕШгй 5.
Сходимость стационарных итерационных методов. Метод Зейделя и метод верхней релаксации являются примерами неявных схем вида В "ь' '" -)-АУь=!', !г=-0,1,..., длЯ всех УввнН, т (14) с несамосопряженным оператором В, имеющим обратный оператор В '.
Метод (14) назь!веется стационарным итерационным методом, так как В и т не зависят от номера итерации. Для существования обратного оператора В ' достаточно потребовать положительности оператора В. Пусть В =П+юА . Так как А =А*~О, то (А у, у) = =(А+у, у), (А+)*-А, и значит, (Ау, у) =Фу, у)+ + 2(А у, у), т. е. (Л у, у) = — ((А — В)у,у). Подставляя это выражение в формулу (Ву, у) = (Ву, у) + + ы(А у, у), находим (Ву, у) =-. (1 — —, <в) (П!П у) + го (Ау, у) ) О, 1 если 0(ы(2, Для погрешности г„= у,— и мы получаем однородное уравнение Л =- О, 1, 2.... го = уо — и- (15) Теорема 1.
Пусть А — са!!осопрягсенный по,голгительный оператор и выполнено условие В ) — А. (10) Тогда метод итераций (14) сгодится в П„, т. е. !'г„1 =-. !!у„— и!)~ — 0 при й— Д о к а з а т е г ь с т в о. Пам понадобится энергетическое то!кдество 2 ! т т (17) где Ж=(Аг, г). Сначала преобразуем уравнение (15) 1ОЗ г 3. итевхционные метОды к виду В 2 А) + + 2 А (гг + гаях) О (18) подставив для этого гд = — (г„+ ( г,) (гг д — ха) 2 ~+х а 2 т /ха< — г, 1 Умножая (18) скалярио иа 2т( '' ! =-- 2(гге,— гг) и учитывая, что (Аг„„, г,) = (г„.„Лг„), так как Л = Аг и (А(г, + г,т,), гг~, — г„) = (Лг„„, г,ю) — (Лг„, г,) + + (Агх, г,,) — (Аг„, „г„) =(Аг.
о ггю) — (Агг, гг), получаем (17). Пусть выполнено условие В ~ тЛ/2. Тогда первое слагаегхое в левой части тождества (17) неотрицательио и ((гг+х)~л<~~(гг()а Отсюда следует, что 0==1гххх~~гя=!~гх1г< <... ( 1гхзг, т. е. последовательность (2гг!а) — яевозрастатощая и ограниченная снизу пулем. Поэтому в силу теоремы Вейерштрасса (2ггЛг) сходится при й — гг. Докажем, что )пп ~~гЛ = О. г в Оператор Р =-  — —, А положителен, а Р, = т =Вг — — А =- —, (Р+ Р*) положвтельио определеп, т, е. существует такое число 6- О (см. гл. 1 2 4), что (Ру, у) = (Р,у, у) ~ Му1г для всех у жН.
Поэтому из тохкдества (17) получаем иеравевство 26,, '3 — '! гге, — гг '1 + 1 гг; х )(й » () гг 1л. (*) В силу сходимости (гг,1г) отснгда следует, что существует )ип~гг+, — гх!/ = О. (19) Далее, пз уравиеппя (15) находим 1 1 Ага = — — В (гггх — гг), гг =. — — А-'В (ггь, — гх), т 1 (Агю гг) =- —, (А-'В (гд„х — га), В (ггт, — га)), х '1гг(~л„( —,)А-')1В)'1гге, — хгД, 1 т Отсюда и иа (19) заключаем, что 1пп ~~гх~', = О. и Щ 1'Л. ПЬ РКШВНИК ХЛГЕБРХИЧКСКИХ ХРЛВПВПИИ 3 а ы е ч а я пе.
Из перавепств («), (««) следует, что метод итераций (14) сходится при условии (16) со скоростью геометрической прогрессии, 1зьег ~гл (» Ре(~ хь 11л где 2дт ~1Л- ~Ц~В1~« ' Примевпы теорему 1 для доказательства сходимостп рассмотренных в пп. 2 — 4 итерационных методов. Метод простой итерации, В=Е. Учитывая, 1 что Е - — Л имеем ) Л! 2 2 ' --(~~Л!~ 21 1 при — — — > О.
Метод простой итерации сходится 1А1 2 при всех значениях т, удовлетворяющих иеравеяству т ( 2/~~Л1. Метод 3 е й д е л я, В = Р + А, т = 1. В этом случае  — — А = В + А — — (.4 + А+ + 1)) = 1 2 2 д = — + 2 (А- — Ае), ( — —,Л у,у = —,, (Ву,у)+ —,((Л- — Л )у,д)- ) )=' 1 =- — 2(Вд у)>0 осла В> О. 3 а и с ч а и и е.
Неравевство В > 0 следует пз условия Л >О. В саыом деле, пусть А >0 и $ (ф', 0,...,0); тогда (Лф, ф) = (В$, $) =ао(ф')'>О, т. е, а„> О. Авалогичяо убеждаемся, что аь > О, и, следовательно, .0 >О. Таким образом, метод Зейделя всегда сходится, если А— самосопряжелпый положительиый оператор.
Чтобы получить оцевку скорости сходимости, надо сделать более сильные предположения, Приведем одну пз теорем. Т е о р е ы а 2. Иетод Зейделя сходится со скоростью геометрической прогрессии со зногиенателеги д» 1, если А - (ас) — А*> О, и т«х Х (а11)»»д!а1,(, 1-1,2, ...,Х, у~1. (20) я 3 птгглгптоппьгг ыгтодьг В самом деле, для погрегпности з, = уо — и имеем Ги Чг ЕЗ Чг Ог ппго,, =- — кз аозо . — ~оаизо, г<г г>г ! а п ! ! зД ! . ~ ! а „! зо',~ г ! —,'- ~~ ! а „! ! зо' !. гг) Пусть гпах ! зг„, ! достгггается прп некотором г = го, так что $ зоог !)с .—.= ! ф)г !, ! а о о ! ! зоо г !!с С~ 2'.
! агог ! ' ! хо+ г !!с + гч'о + ~~Л~ ! л;,г ! !! со ))со гаго $~гьгг !с ! г ! лог!)(! "'о о! ~ ! лог!!~!!з""с' В силу условия (20) имеем ! а;о; ! ( Ч ! а гого ! Х г аг; ! < д 1'! а ! — ~~." ! аг; !'), гало и, следовательно, 11г„.„1!„, ~ г(1г„'~о < г)"+О с,1!о, что и требовалось доказать.
Условие (20) означает, что А (ао) — матрица с диагональным преобладанием. Метод верхней релаксации, В=Р+огА, т = ы. Найдем разность  — — А = Р + егА- — —" (А- -1- Ль+ Р) = = !1 — — "' ~) Р + —" (А- — Л-) 2) 2 я вычислим (( — — „, Л) у, у) =- ! 1 — —,~ (Ру, у) > 0 при 0 ю ( 2.
Танин образом, метод верхней релаксации сходится прн любых значениях ег гп (О, 2), если Л Ло > О. 6. Скорость сходимоети неявного метода простой итерации. Самого факта сходнмости птераций недостаточно, чтобы судить о пригодности для практики итерационного метода. Путина информация о скорости сходпмостп метода, т. е. фактически о числе итераций гг=л,(е), доста- (бь гл. тп. гкжкнил ачгкнелнчкских хглвнг~нп точных для решения задачи с требуемой точностью е > О. Число итераций п,(е) зависит от параметра т, который н следует выбирать из условия минимума числа итераций п =п(г), при котором выполняется условие 1у — иг == «е1у, — изь, где гл' — некоторый оператор, В )л" > О.
Мы будем рассматривать неявную стационарную схему (неявную схему простой итерации) В ет +Аул.= (., )г=0,1,..., длявсеху ыН, уа.ы уь (21) где А и  — положительные самосопряжепные операторы. Методы Зейделя и верхней релаксации пе принадлежат атому семенству схем, так как для них оператор В пе является самосопряженным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
