Самарский А.А., Гулин А.В. Численные методы (1989) (1095856), страница 69
Текст из файла (страница 69)
!и (2/е) о Основной вывод, который можно отсюда сделать, сводится к следующему: при решении с помощью чебышевского итерационного метода разностных задач, аппроксимирующих уравнения эллиптического типа, число итераций п,(е), необходимых для получения заданной точности з, является величиной 0(й-'). Напомним, что метод простой итерации и метод Зейделя требуют О(/г ') итераций, что при /г=0,1 на порядок больше. Порядок числа итераций в чебышевском методе тот же, что и в методе верхней релаксации с оптимальным выбором релаксационного параметра от.
В данном случае интересно провести сравнение необходимого числа итераций в методе верхней релаксации н в чебышевском методе по числу е. Согласно (32) из э 1 в методе верхней релаксации необходимое число итераций определяется формулой 21пе ' л!ель! (е) о в то время как для чебышевского итерационного метода 1п(2е ') ло (е) = ил Таким образом, л! аь1(з) — ло (з) = !и (!/(2з)) о и/ Следовательно, метод верхней релаксации требует большего числа итераций. Естественно требовать, чтобы погрешность е итерационного метода имела тот же порядок ао, что и погрешность аппроксимации разностной схемы.
Поэтому положим е=0,5 айо, где а)0 — постоянная, не зависящая от Ь. Тогда получим л!'оо (е) — ло (е) = 1и 1/(ало) / 1 1 ! =О~ — 1и — ~. ль ~ь а~ 3. Применение чебышевского метода к разностным аппроксимациям уравнений эллнптичесного типа. В случае более общих аппроксимаций уравнений эллиптического типа схема применения чебышевского метода остается той же, что и раньше, однако точ- 391 д ди'1 д / ди 1 — (й, (х„х,) — 1+ — ~й,(х„х,) — 1 — ц(х„х,)а= — ~(х„х,) дх1 (, дх1) дхх ~ ' дквп ) (12) в прямоугольнике 6= (0<х,<1„а=1, 2). На границе Г прямоугольника б задано условие а (х$ хх) — 11 (х х2) (х х2) е 1 (13) Предполагаем, что при всех (х„х,)~0 выполнены неравен- ства 0<си (й„(хо х,) <с,л, а=1, 2, 0<4<у(хь х,) (Н,.
(14) Введем в О прямоугольную сетку 11 с шагами Ь, и Ь, по направлениям х„ х, соответственно и обозначим х19 — й1 «хн = 159 хц (х1о «х~ ) Ь! 51~ = 1ь ДМх =1г. уи =у (хи), 1=0, 1,...,'Уь 1=0, 1, ..., У„ 1 ~ Умкц Уц Уц Умц 1 (а,у-)„,ц = — ~а,х,ьт ' — а,,ц 1 / Угц+1 Уц Уц — Уеу-~ 1 (а2Ух)к~ ц (ахд 2+1 аКц ) ' «а й' а ~ а Обозначим через у сеточную границу, т.
е. пересечение й с границей Г. Заменим исходную дифференциальную задачу (12), (13) разностной схемой второго порядка аппроксимации (а,у- )„ц + (а,у-„), ц — г(цуц = — )и, 1=1, 2,..., )х',— 1, 1=1, 2,..., У,— 1, (15) уи — — рц, если хаен"(. (16) Здесь А =ци а,,ц = 0,5(и,(х'„", хо') + й,(хк ", х,"1)), акц = 0,5(йх(х,", х~я) + А,(х19, х," ")). 392 ные границы спектра (, и („как правило, не удается найти в аналитической форме.
Поэтому используют те или иные оценки для границ спектра. В качестве примера рассмотрим аппроксимацию задачи Дирихле для уравнения эллиптического типа Покажем, что разностную задачу (15), (16) можно записать в операторной форме (1), где А — самосопряженный оператор, и получим для этого оператора оценки вида (2). Прежде всего заметим, что, изменив соответствующим образом правую часть уравнения (15), можно считать, что у„=О при хцен р Таким образом, придем к эквивалентной (15), (16) системе уравнений (а,у-„)„„» + (а,у„-)„» — И»у» = — ~;ь (17) 1=1,2,...,№ — 1, 1=1,2,...,№ — 1, Уз=О, если хц~Т, (18) где )ц отличается от )ц только в приграничных точках сетки. Рассмотрим пространство Н функций, заданных на сетке й и обращающихся в нуль на т.
Определим в Н скалярное произведение и норму У~-1 Ф~-1 (у, о) = ~~1', Ь, '~~ й,у»ц», 1у~ = 1/(у, у). Ф~-1 Ма »11 цз1 + 'Я й, 'Я Ьза,с у„-» о-„„+ ~~~~ йт ~', ЙЙА!у»о» (20) 4=1 /=1 с=1 г=1 Отсюда, меняя местами у и о, легко установить, что (Ау, о) = = (у, Ао) при любых у, и~Н. Следовательно, разностной схеме (15), (16) соответствует самосопряженный оператор А. Далее, полагая в тождестве (20) у=с, получим л, и,— (Ау, у) = ~ч~" „й, ~к~ й,аь» (у-„,. )з + 1=1 /=1 и,-1 и, »,-1 + ~~ Ьт ~ Йзаз,» (у-„») + '~~ Йт '~~ Ьу(» (у»)'. (21) а=1 у 1 !=1 !=1 Отсюда, учитывая неравенства (14), приходим к оценкам р,(Ау, у) +с(,'1у1' ='(Ау, у) <Ц(Ау, у) + Из~у!~', (22) звз Далее, зададим в Н оператор А формулами (Ау)» = — (а,у„-)„„» — (а,у„-)„, » + А;у», (19) 1=1,2, ...,№ — 1, 1=1,2, ..., № — 1.
Тогда разностную схему (17), (18) можно записать в виде операторного уравнения (1) в пространстве Н. Из разностной формулы Грина (см. (15) из $ 3 гл. 1) следует, что для оператора (19) при любых у, оенН справедливо тождество ца уг1 (Ау,о) =~й, "~ ~Ь,а,»у-„,. с-„- »+ где №-1 № М» №-1 (Ау, у) = ~' 61 'Я Ьа (у-, 1 )'+ ~ а1 ~я~ !(1(у1, )а, (23) (24) р»=С» 1+С»,1 р»= С» 1+С»1. Обозначение (Ау, у) объясняется тем, что сумма, стоящая в правой части (23), представляет собой скалярное произведение двух векторов у и Ау, где Поскольку 5И<(Ау, у) ~бЬГ, где 5= —,зш — + —, з(п —, 4 .
1па1 4 . 1п((» Ь~~ 2(1 Ь1 2(1 (25) Ь = —,соз — + —,соз— 4 1 аа» 4 1»»а1 а~ 2(1 «~ 2(1 (26) (см. 3 ! гл. 3), из (22) следуют операторные неравенства (2) с кон- стантами (27) 3 3. Попеременно-треугольный итерационный метод 1. Алгебраическая теория. Пусть дана система линейных алгебраических уравнений Ау=1 (1) с симметричной положительно определенной матрицей А порядка 394 11=(615+((1» "11 =5»б+А. Отсюда по формулам (4) можно вычислить итерационные параметры т, и оценить согласно (5), (6) величину погрешности, Отметим, что приведение разностной схемы (15), (16) к виду (17), (!8) потребовалось нам только для того, чтобы определить оператор А и получить оценки его спектра.
После того как параметры т„найдены, итерации можно проводить непосредственно для схемы (15), (16). Сначала вычисляется невязка гц = — (а,у,— )„, — (ату;)„, + (12 (1( (и ! ()иуф — 1((, 1= 1, 2,..., У1 — 1, 1 = 1, 2,..., Уа — 1, а затем находится новое приближение у(; =уи — т1„гц, 1=1, 2,..., У1 — 1, 1=1, 2, ...,У1 — 1. (М-1( й) Р> Граничные условия доопределяются согласно (16): у(! =ра, (К»1( если х„~у. т. Зададим матрицу В= (гч) следующим образом: ац, если 1 ь/, гц = 0,5 ац, если О, если 1(у. Тогда матрицу А можно представить в виде суммы А=к+К', где через В* обозначена матрица, сопряженная с матрицей В (транспонированная к В в случае действительных матриц и комплексно- сопряженная — в случае комплексных матриц).
Ясно, что  — нижняя треугольная матрица и )г' — верхняя треугольная, причем диагонали матриц )т и В* совпадают. В дальнейшем удобно рассматривать систему уравнений (1) как операторное уравнение с самосопряженным положительным оператором А, действующим в коиечномерном евклидовом (унитарном — в комплексном случае) пространстве. Попеременно-треугольный итерационный метод, который будет рассматриваться в настоящем параграфе, относится к неявным итерационным методам вида В "' ' +Ауь=) с самосопряженным положительным оператором В.
А именно, оператор В в попеременно-треугольном итерационном методе определяется как произведение В = (Е+аК*) (Е+в)т), (3) где Š— единичный оператор и ы)0 — числовой параметр. В дальнейшем параметры в и т будут выбраны исходя из условий сходимости итерационного метода (2), (3). Если в и т известны, то новая итерация у„~, находится из уравнения (2) в два этапа. На первом этапе находится промежуточное значение, которое мы обозначим через у,~,д, как решение уравнения (Е+ый.')у.~ в=ам (4а) где р,=Ву,— тАу,+т1.
На втором этапе, используя найденное значение у„.о„решается относительно у„„уравнение (Е+аР.)у~+ =У эп ° (4б) Решение уравнений (4а), (4б) не представляет труда, поскольку матрицы Е+аР и Е+вй являются треугольными. Исследование сходимости попеременно-треугольного метода (2), (3) основано на теореме 1 из $ 4 гл. 2 ч. П о сходимости неявных итерационных методов с самосопряженными операторами А, В. В основе этой теоремы лежит предположение о том, что операторы А и В связаны неравенствами '(,В(А (Т,В, (5) 396 где Т, и Т, — положительные постоянные. Поэтому нам прежде всего надо доказать неравенства (5) для оператора (3).
Л е м м а 1. Пуста существуют положительные постоянные 6, Л такие, что выполнены операторные неравенства А)ЬЕ, 4Р'Й < 1ьА. Тогда для операторов А=К'+Р и В= (Е+ай') (Е+вЯ) справедливы неравенства (5), где /! взо'1 х 1 Ух=~ — +а+ — ~ Тз= '16 4 ~ 2в Д о к а з а т е л ь с т в о. Рассмотрим операторы В =В(а) =(Е+ ай*) (Е+ аР) =Е+ аА+ азй*Р, В( — а) =(Š— вй*)(Š— вР)=Š— вА+ взй'Р. Отсюда получим В(а) — В( — в) =2вА, следовательно, В=В(в) )2аА, поскольку В( — в))0. Таким образом, А(Т,В, где Тз= (2а)-'.
Далее, учитывая предположения (б), (7), получим В=Е+ вА+азрс')ч( — А+аА+ — А, 6 4 Таким образом, иэ (7) следует неравенство о йй*+ Р*й( — (Р+ й*). 2 (9) С другой стороны, воспользовавшись тождеством 2 (й'й+ Рй') = (й*+ й) '+ (й* — й) (й* — й) *, й'й+Рй*) 0,6(й'+Р) '. получим Отсюда и из (9) приходим к неравенств) (Р*+й)з( Ь(Р*.+й), 396 т.
е. А)Т,В, где константа Т, определена согласно (8). Лемма 1 доказана. Замечание 1. В качестве константы 6 в условии (6) можно взять минимальное собственное значение Хенн(А) оператора А илн любую положительную постоянную, не превосходящую Леон(А). Замечание 2. Докажем, что если выполнено условие (7) с некоторой константой а>0, то пРи А=й*+Р)0 выполнЯетсЯ неРавенство 6)ймнх (А), где 1., (А) — максимальное собственное значение оператора А. Преобразуем (7) с помощью следующей цепочки эквивалентных преобразований (см. п,4 61 гл. 3): о Ь 6 йчй < — (й'+ Р), Е < — (Р '+ Р* '), йй* ( — (й+ й').
4 4 4 которое эквивалентно неравенству А =)с*+Я(ЬЕ, означающему, что Хм, (А)(Л. Учитывая замечание 1, видим, что если выполнены неравенства (6), (7) и амь(А) чьХмэа(А), то Ь)6. Обратимся теперь к исследованию сходимости попеременнотоеугольного итерационного метода.
Теорема 1. Предположим, что А=Я'+Я и существуют положительные постоянные 6, Л, при которых выполнены неравенства А = ЬЕ, 4В'К - 6тА. Пусть от= =, т= 2 2 (10) р'6Ь та+ 7, где 6 6 У 66 71 = — уз= ). )сй) Л 4 Тогда итерационный метод (2), (3) сходится, причем для погрешности справедлива оценка !!у.— у!! (р"!!у.— у!1, (12) (11) где 397 1 — Фа (13) 1+3 г'а Д о к а з а т е л ь с т в о. В лемме 1 установлено, что при любом ю)0 операторы А и В рассматриваемого итерационного метода свЯзаны неРавенствами (5), где 7,=7,(оз) и 7,=7з(от) опРеделены согласно (8). Поэтому выполнены все предположения теоремы 1 из $4 гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
