Самарский А.А. Гулин А.В. - Численные методы (1078412), страница 73
Текст из файла (страница 73)
(26) Таким ооразом, нахождение уьы снова сводится к решенпю двух систем уравнений с треугольными матрицами. В следующей теореме получена оценка скорости сходимости итерационного метода (2), (26). Теорема 2. Пусть А=К'+)с. Предположилс, что существует самосапряженный положительный оператор 0 и положительные постоянньсе бь, Ль, для которых выполнены неравенства А~б О, (26) 4сс О 'Д(Л,А.
Положим 2 2 сев т= ) ВО "О тс+ б (29) 402 Если Р=Е, то получаем рассмотренный ранее поперемешютреугольный итерационный метод. Если О~В, то приходим к обобщению метода (2), (3), которое при правильном выборе матрицы 0 позволяет несколько уменьшить число итераций. Дополнительных трудностей при вычислении новой итерации у„, здесь не возникает. Вместо алгоритма (4а), (46) можно использовать следующий алгоритм определения у„„: (О+ ый) Уе и = с(сь с(л = ВУе — тАУе+ тсс, (О+ ы)сс) уес =Оуь-и. бо бо 1,' бобр 2(!+1/$о) ' Ьо 4 Тогда для погрешности итерационного метода (2), (26) лива оценка !!Уо У!!л ~Р~!!Уо У!!л где (30) справед- (31) о'соо ро = (+з )Г4р (32) Доказательство.
Погрешность метода (2), (26) г,=у„— у удозлетворяет однородному уравнению (0+вой*)0 '(0+вой) " о + Аго=О, (зз) и=О, 1,..., г,=у,— у. Поскольку 0"=0~0, существуют самосопряженпые положительные операторы 0", 0-". Сделаем в уравнении (ЗЗ) замену г,=0-' о, н обозначим К,=0-'Я0-", Ао=0 "А0 ". Тогда после умножения па оператор 0-и уравнение (33) приводится к виду (Е+ ьйо) (Е+ ооКр) "" о + Арро=О т (34) Выбирая оо и т согласно (29), (ЗО), получаем, что выполнены условия (10) и (11) теоремы 1. 11эзтому для решения уравнения (34) справедлива оценка (12), кспорая в данном случае принимает впд оо ~~рр !!ро)!ло где ро определено согласи; (32).
Заме,ая, что !!по!!лр=(Арро, оо) =(О ЛА0 '(О'до — 0 'у), (0иу» — 0нд)) =(А(до — у), д» вЂ” д) =!)Уо — у1л, приходим к оценке (31). Теорема 2 доказана. (о» 4ОЗ Так как А,=Ро+)г, уравнение (34) представляет собой уравнение длл погрешности немодифицнроваяного попеременно-треугольного итерационного метода (2), (3). При этом о„=х„ — х, где х=Е>оу является решением уравнения А х=0-'*)', а х„=0'*у„— прпблнжение к х, полученное на й-й итерации. Для оценки о„ применим теорему !.
Условия (27), (28) эквивалентны, соответственно, условиям Ар ~)брЕ, 4Крйр ~ ~ЬрАр. Смысл введения модифицированного попеременно-треугольного метода состоит в том, что при соответствующих 0 константа р, входящая в оценку (31), оказывается меньше, чем константа р из оценки (12). В 135, с. 425! указан способ выбора днагонал»ной матрицы 1), минимизирующей константу р, в случае разностных аппроксимаций уравнений эллиптического типа с переменными коэффициентами. В 4. Итерационный метод переменных направлений !. Формулировка метода и исследование сходимости.
Рассмотрим систему линейных алгебраических уравнений Ау=! (1) с невырожденной квадратной матрицей А порядка и» и предположим, что А=А,+А, представлена в виде суммы двух матриц Л, н А, более простой структуры. Например, в случае разностных аппроксимаций двумерных эллиптических задач матрица А„аппрокспмирует производные только по переменной х„, а= 1, 2. Тогда можно предложить следующий итерационный метод решения системы (!), аналогнчнын методу переменных направлений для двумерного уравнения теплопроводности (см. 2 4 гл. 4). Переход от я-й итерацпи к (я+!)-й осуществляется в два этапа. На первом этапе находится промежуточное значение и..., как решение системы уравнений Ум.м У» + А,д»,м + А,у»'='7. (2) т На втором этапе решается система уравнений У»+~ Уь.м + А,У»...
+ А,У»., =1, т (3) 404 из которой находится у,, Здесь т Π— итерационный параметр, предполагается, что задано произвольное начальное приближение у,. Записывая уравнения (2), (3) в виде (Е + тА,) у»,и = (Š— тЛ,) у» + т), (4) (Е + тА,) у»„= (Š— тА,) у»,и + т), (5) убеждаемся в том, что для нахождения у„„, необходимо решить две системы уравнений: первую с матрицей Е+тЛ, и вторук> — с матрицей Е+тА,. Таким образом, метод (2), (3) целесообразно применять лишь тогда, когда матрицы Е+тА„, с»=1, 2, гораздо легче обратить, чем исходную матрицу А. Например, в случае разностных аппроксимаций уравнений эллиптического типа системы (4), (5) можно решить последовательным применением одномерных прогонок сначала по направлению х, (для системы (4)) и затем — по направлению х, (для системы (5) ).
Обратимся к исследованию сходимостн итерационного метода (2), (3). Будем рассматривать систему (1) как операторное уравнение в конечномерпом линейном пространстве Н со скалярным произведением (у, о) и нормой 1)у(! =)((у, у). Определим погрешности г„,и, г,+, метода как разности А.и=Уьеь — У гь+~=Уь» У между решениями у„+,,„у„, систем (2), (3) и решением у исходной системы (1). Введенные погрешности удовлетворяют уравнениям (Е + тА,) гьи = (Š— тА,) гм (Е + тЛ,) ге н = (Š— тА!) гь н „ (6) (7) из которых можно легко исключить промежуточное значение г„, ь и получить уравнение, связывающее только г„и г„,: (Е+тА,) (Е+тА,) г,,, = (Š— тА,) (Š— тА.) ае (8) Теорем а 1.
Пусть А =А,+А„гдг А„= А > О, а=1, 2, А,Л,= =А,Л,. Тогда итерационный метод (2), (3) сходится при любом т)0. Если 0 =6Е =А„(ТхЕ, а=1, 2, т= 1/)(6Л (9) то при (1О) для погрешности справедлива оценка Ь вЂ” уЫр!(!у.— у(! гдг (12) Д о к а з а т е л ь с т в о. Запишем уравнение для погрешности в виде гь+1 — Егь где Я= (Е+тА.,)-'(Е+тА,) '(Š— тЛ,) (Š— тА2). (13) Оператор 5 является самосопряженным, так как по условно теоремы А, и А,— самосопряженные перестановочные операторы. Получим оценку для собственных чисел ).,(5), я=1, 2,..., т, оператора (13).
Любое собственное число можно представить в виде (! — тХь (А,)) (! — тХм (АД) )»(5)— (! г т).» (А,)) (! + т)чн (А,,)) (14) где)ь„(Л ) — собственные числа операторов Л, а=1, 2, (г,= =1, 2, ..., и. Из (14) видно, что при т~О все собственные числа 405 Х,(5) не превосходят по модулю единицу. Следовательно, '((5(= (пах !).р,(5)',( 1 1ф~а: и метод (2), (3) сходится. Далее, согласно (14) имеем ()м(5) !» ~ ! — т).а (АД ' ! — т).а (А,) ! !+, (А,)! (+ )., 1.4,1 ~ ' Из условия (9) получим ), )(Ат) ~~ х (15) следовательно, ! 1 — т).а (Аа] 1 +т)а (А~) ~ ))~)м <() ( )+ т6) (+та ~1 Еслп выбрать т согласно (10), то получим ! — т6 ! — та ! — )) $ 1+т6 !+та ! ( ~Г н позтому ! — т)м (А,) ! — — ~» Я, и=1, 2. Я~) (+ ! Отсюда н из (1б), (16), получаем 3 Р))=( ~ ) =р, ', !+!'с, ( 1=1 2, ()) — ! ))()(=! и метод переменных направлений (4), (8) принимает вид (т).М) () Л) ч(4) (ь-)) (~и)) ,т,(т) УГУ,н и ~ () 8) (19) где ) м =р() +ту-„;„((+т)(( (х] [х) (Й) Ф(() = д(4'М) + ту(— "' ..
+ т7((х х,х„п так что !1а~Д»р!~аД» р,''!г((, Теорема 1 доказана. 2. Пример. Рассмотрим применение метода к модельной задаче (14) нз $ 3. В данном случае (17) Уравнение (18) решается при каждом фиксированном =1, 2, ..., />/ — 1 с помощью метода прогонки по направлению х,. Для этого достаточно записать (18) в виде и+му >4 рн й 'л> 8> АУ>- / — СУ! " +ВУ>„> = — Р>1, 1=1 2, ..., ))/ — 1, ~~'и>=О, ум'>4>=О, где А=В=т//>', С=1+2т/Й', и применить формулы прогонки (43), (44) из п. 7 9 4 ч.
1. Точно так же уравнение (19) записывается в виде !а+и !еы> <ета (а) Ауп), — Суп + Вуп>„= — Ф г, /=1, 2, ..., Л/ — 1, у>е>1> =О, у>ь'о =О >е гм и при каждом фиксированном 1=1, 2, ..., 1>/ — 1 решается прогонкой по направлению х,. Применим теорему 1 к исследованию сходнмости метода (18). (19).
Операторы А, и А„ определенные согласно (17), пересталовочны, так как разностное выражение определено во всех внутренних точках сетки Р, причем (А,А,у)н =у,— „— „,, =(А,А,у)н. Таким образом, перестановочность является следствием того, что А, и А,— операторы с постояннымн коэффициентами и область 6 — прямоугольная. Нарушение хотя бы одного из этих условий приводит, как правило, к нарушению перестановочности. Предположение о перестановочности является, видимо, основным ограничением теоремы 1, не позволяющим применить ее к более общим разностным аппроксимациям уравнений эллиптического типа. В [32, с.
450) доказана сходимость метода переменных направлений без требования перестановояности. При условиях (9), (10) доказана оценка Ц (Е + 'гАз) (ал — у) 1 ~ г~ ) (Е + тАт) (ро — у) 1 где константа р, определена согласно (!2). Как мы видели ранее (см. $ 1,2 гл. 3), операторы 1„ сх= 1, '2, являются самосопряжепными в смысле скалярного произведения м-з (у, ') = ~к~'„у>!о>1/>', ь 1=1 причем для них выполнены операторные неравенства (9), где 4 ., па 4 зла 6 = — а)пв — ' —, Л = — соэ — ' Ьз 2 аз 2 Таким образом, при а' ь т= 25!и (нв> пч 402 для погрешности будет справедлива оценка (1!), (12), где 2 х(! 122 2 4 Число итераций п,(е), необходимых для достижения заданной точности а, в данном случае равно 1и (!/о) 1и (1(о) п,(е) = 4 )' $2па Эта примерно столько же итераций, сколько и в попеременно- треугольном итерационном методе.
Однако число арифметических действий на каждой итерации здесь больше. 3. Случай прямоугольной области. В теореме 1 предполагалось, что спектр операторов Л, и А, расположен на одном н том ж< от- резке (б, б). Рассмотрим теперь случай, когда вместо (9) выпол- няются условия О=-.боЕ =.А„=Л.Е, я=1, 2, где, вообще говоря, т,Фто. Как и в 1еореме 1, можно доказать, что данный метод сходится при любых т,)0, т, О. Оптимальные параметры т, и т, задаются следующим образом. Пусть известны константы б„б„Л„Ь, в неравенствах (20).
Вычислим величины (Л! — 60 (Ло — 60 ) И (Ло — 6 ) Ло (Л,+60(Л,+60/ (Л,+6,/ Л! ,~и х=(. (23) и найдем р — — Г— и — ( Л,— Л,+(Л+Л)р 1 — р д = и + — . (24) х+! 2Л,Ло Л! Нетрудно проверить, что 0((~1. Далее, определим н, наконец, положим ем+ г до~ — и !+рм' ' 1 — ро~ (25) Имеет место следующий аналог теоремы 1. 4ОВ гд бо и ˄— заданные положительные числа (под б„н Ло можно понимать наименьшее и, соответсзвенно, наибольшее собствезное значение оператора Л„). Типичным примером является разностная аппроксимация уравнения Пуассона на прямоугольной сетке, В случае (20) используется двухпараметрический итерационный метод переменных направлений ко,и — ро + Л!Уо„11+ А,Уо =(, т! вон ко~и * + Л!Уом( + АоУо~~ = 1.
(22) то где 5 (Е+т,А,) '(Е+т,А ) '(Š— «,А,) (Š— «,А,). Оценим собственные числа 2 — .д, ~А,)) ( —,Е,,(А,) ) Х» (5) = ! + «,Х (Л,) 1+ т,х», (Л») оператора 5. Для этого сделаем в (29) замену Л», (А,) = "',, ).», (А,) = е — «Х» ' г+ «Х» с не определенными пока параметрами р, д, г. Тогда получим (29) (30) (31) где т~ — т т,+г (»«= —, ы,= —" е — т1Р д+ т.,р Если выбрать т, и т, согласно (26), то получим, что «е,=«»,=е« (32) Подберем теперь параметры р, «), т таким образом, чтобы в результате замены (30) оба отрезка б,т ()» (Ап) ( бт, а = 1, 2, переходили бы в один и тот же отрезок 6~)» (Ь, а=1,2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
