1625915343-86705b7cdbdb8beb07b7d1cf5a49c66a (843918), страница 67
Текст из файла (страница 67)
Для вычисления коэффициентов !. Ле Ь.~Р ..., ьу б мы используем только коэффициенты аь Ьь с! при 1=1, 2, ..., 1 — 1. Поэто! му, если М(2М+1)б< —, то мы можем утверждать, что )Л! ~,)< ~ 2М и что, следовательно, ! сг — с, ~ = ~ — (а1 ! — !, + Ьг) Л, + д / < (М 2М + М) 6 = М (2М+ 1) б.
Этим индукция полностью завершается. ! Таким образом, показано, что если 6<, +, то )с,— с,(< <М(2М+1)6 для всех б и для всех прогоночных коэффициентов выполнены неравенства )Л! 1г,)<2М, (а(! ы,+Ьг)=- и— , 1 Мы видим, что в течение всего нашего вычислительного процесса нам никогда не придется делить на нуль. Теперь из наших формул для ф, ф б! следуют неравенства (ф — ф,'<6, (ф — ф~<6, ( д, — д, ( < Мб + М (2М + 1) 26 = М (4М + 3) 6. Оказывается, что допуская на каждом шагу вычислительного процесса ошибки не ббльшие б, мы тем самым решили систему с возмущенными коэффициентами и правыми частями.
Эти возмущения не превышают Мьб, где М* зависит только от М и не зависит от числа уравнений системы: Ма=шах»1, (4М+ 3)М». З зз1 ИТЕРАЦИОННЫЕ ПРОЦЕССЫ ДЛЯ ЗАДАЧИ ДИРИХЛЕ 403 Как было показано раньше, такое возмущение коэффициентов и правых частей приводит к погрешностям в п„не большим, чем Мккб. (Здесь Меа опять-таки ззвисит лишь от М.) Тем самым показано, что, совершая при вычислениях по методу прогонки ошибки порядка 6 на каждом шагу процесса (чнсло таких шагов»"-юА(), мы получим в ответе ошибки не больше, чем сопз1 6, где сопя( не зависит от А(.
Ошибки не только не нарастают, но даже не накапливаются. Это замечательное свойство прогонки и послужило основанием для ее широкого распространения. В 39. Итерационные процессы решения разностной задачи Дирихле Формальная схема. Сведение вопроса о сходимости к случаю нулевых граничиых условий. Специальный ортоиормироваиный базис в простраистве сеточных функций, равных нулю иа границе. Аналогия с процессом выравнивания температур и ее использование Лля »придумывания» итерационных процессов решения разиостиого уравнения Лапласа. Выбор параметра т лля простейшего итерационного процесса. Оценка рабаты, нужной для того, чтобы уменьшить погрешность в заданное число раз.
Процесс Дугласа — Рэхфорда, использующий «расщеплеиие» итерационного оператора иа одномерные. Циклическое изменение параметров. Леммы о произведении собственных значений и оценка скорости сходимости. В этом парзграфе речь пойдет о методах решения задачи Дирнхле для разностного уравнения Лапласа Ахки+()»ууц 0 «(г=ф' Здесь символами А„хц, Ау и обозначены для краткости разностные аналоги вторых производных: и (х+Ьх, у) — 2и (х, р)+и(х — И, р) кхи Ь' х и (х, у+Ау) — 2и (х, у)+и(х, р — Ь ) Ьуу и— Для простоты ограничимся случаем, когда облзсть, для которой решается задача, является единичным квадратом О~ж(1, О~у(1 и разностная сетка также квадратная: )»„=)» =1/А(. К сожалению, в настоящее время не существует удобного прямого метода решения такой задачи, который был бы хорош при достаточно большом числе точек сетки, имеющем порядок №. (Аккуратный подсчет показывает, что нашз сетка содержит (А) — 1)' внутренних точек и 4(А( — 1) граничных; четыре угловых точки в урзвнениях не участвуют).
Поэтому я огрзничусь тем, что разберу два итерационных метода решения. Один из них очень простой и был известен уже давно. Его нельзя считать удовлетворительным, так кзк скорость его сходимости существенно замедляется при увеличении А(. Другой метод, который мы изучим, был предложен в пятидесятые годы уже после широкого распространения вычислительных машин. Он сходится быстрее. В настоящее 1 4О4 юл ч илзностныв мвтоды время есть целый ряд других методов, сходящихся еше быстрее. Однако они являются логически более сложными.
Кроме того, идея, лежащая в основе второго метода, получила очень широкое распространение. Поэтому я остановился на этих двух методах для того, чтобы проиллюстрировать вопросы, возникающие при анализе методов решения двумерных разностных уравнений, и рассказать о том, с помощью каких ухищрений это решение сейчас обычно проводится. Итерационные процессы ведутся по следующей схеме: и<"> (х, у)=Р и<" '> (х, у). Здесь и<'>, и<'>, ..., и<">, ... последовательные приближения к решению, а Р— некоторые линейные операторы.
В обозначении этих операторов поставлен знзчок т, чтобы подчеркнуть возможную ззвисимость этих оперзторов от 'номера итерации. Зля того чтобы процесс был легко осуществим, надо, чтобы эти линейные операторы удавалось применять к сеточным функциям и[" '> с помощью не слишком большого числа зрифметическнх операций. Предположим, что Р,„удовлетворяют следующим требованиям: 1) Ржи< '> принимает в точках сетки на границе квадрата те же значения, что и и< '>.
2) Если сеточная функция и(х, у) удовлетворяет уравнениям ~ ~ххи + ~ууи — О то при любом т Ри и. Пусть теперь и(х, у) — точное решение разностной задачи кирилле АкЛ+ [~ууи = О и [у=9, которое, как мы знаем, существует при любой граничной сеточной функции <р. Пусть начальное приближение и<я> (х, у) для итерационного процесса удовлетворяет граничным условиям и[а>[г =<р. Тогда, по свойству 1) операторов Р , на всех итерациях граничное условие и[м><г = <р будет выполнено. Вычитав почленно равенства [хь> р [е-т> и=Ржи, получим [и[ — и)=Р,х[и[ ' — и[.
Сеточная функция и[">=и[ ' — и обращается на тра>)нце в нуль и представляет собой погрешность приближенного решения и<м>. Поэтому для изучения скорости сходимости наших итерзционных процессов нам достаточно оценить скорость убывания с ростом т той или иной нормы функций и< >, связанных равенствами п[ж> [г = О, 'о[~> = Р„р[~т>.
Э 391 ИТЕРАЦИОННЫЕ ПРОЦЕССЫ ДЛЯ ЗАДАЧИ ДИРИХЛЕ 405 В качестве такой нормы мы возьмем эвклидову норму ~ и1м> ~ = фГ 4 Я (о1 1х1 (х, У)]Я Ьхй . к, у Сумма под корнем берется по всем внутренним точкам разностной сетки (в граничных точках ппк1(х, у)=0), Пространство сеточных функций, обращающихся в нуль на границе, имеет размерность (М вЂ” 1)я. В самом деле, очевидно, что существует (М вЂ” 1)а линейно независимых таких функций, принимающих в одной из внутренних точек сетки значение 1/2 1/л„л =М/2, а в остальных точках значение ноль. Норма каждой из таких функций равна 1, и нетрудно проверить, что они ортогональны друг другу.
Под скалярным произведением функций е(х, у), тэ(х, у) (е ~Р=О, си ~с=О) мы понимаем (ТА ти) = 4 ~ч , 'е (х, у) ти (х, у) й„ь . Х,у При изучении тех линейных операторов Р, которые у нас встретятся, удобно перейти к другому базису в том же (М вЂ” 1)'-мерном пространстве. Этот базис состоит из функций Е1Р И(х, у)= з!пцрх з1п иду р = 1, 2, „ М 1, д 1, 2, ..., М вЂ” 1.
Очевидно, что таких функций точно (М вЂ” 1)Я. й(ы докажем, что их взаимные скалярные произведения вычисляются по формулам 1, если рт=р„у,—,д„ (и~у, Я >, мо' Рй) = О в противном случае. Тем самым будет показано, что эти функции образуют ортонормированный базис. Следовательно, любая сеточная, обращающаяся в нуль на границе функция п(х, у) может быть единственным образом представк лена в виде Ф вЂ” 1 е(х, у)= 5 ср, ясФ я1, р, я-! причем м — 1 1е(1а=4Ь Ьу~ ез(.е, у)= ~Ч'~ ср, х у р яьн Операторы Р„будут строиться таким образом, что векторы п1р и будут являться их собственными векторами с некоторыми вещественными соб.
ственными знзчениями Л~~и Я~. Поэтому ! (! Р и ) = 1/ У, '~Ф М сж я)1я = щах ( Л1р' М ~~ ")/" ~ ср, я — — щах ( 4' и ~ ~ е1 406 рлзностные,митоды !гл, ч и скорость сходнмости можно оценивать с помощью наибольшего по модулю собственного числа оператора Р .
Локажем ортоиормироваг2ность базиса, состоящего из функций и!Р Б1, с помощью следующих трех лемм. Лемма 1. ь с! если р/М вЂ” целое число, если р//т/ — нецелое число, а-и — ! Х а=в р — целое, если р — полуцелое (р//аг при этом нецелое). Еокзз атель ство. Если р//а/ — целое, то п — кратно 2п и, сле2пр У 2пр ! довательно, сов(п — )=1. Утверждение леммы 1 в этом случае оче- У) , 2ра видно. Если р/М вЂ” нецелое, то е н ~1, и поэтому можно воспользоваться следующей выкладкой Л-! гн — ! Бар) ! — и .2ра 2пр (жч еа — ~ е и — 1 совп — =Ке 7 е н~=Ке У ~ а~в ) .гр.
а О а О 'н е — ! Еввеа ! =Ке е — 1 и и — ! Если р — целое, то е = 1 и, следовательно, р сов и = О. Если р— !Бра %! 2пр У а=з полуцелое, то е'БР'= — 1, ( ! и ) — 2(сов — -!в!и Р— 1) е — 1 е — ! !е — 1( — !/ 2(1 — с!а Р ) В этом случае -Т' , +; ! — СО — / Лемма полностью доказана. 2рп 1 — савв У 2рп 1 — савв У Ф вЂ” ! Х 2пр в!БР 1 совп — =Ке =Ке у 2ра а=в е и — 1 2рп 2рп Б!П— з!и— У У 2рп + 2рп 1 — соз— У 1 — савв У итвэлционные пгоцессы для задачи дннихлв 407 Лемма 2.
Пусть й, 1 — любые из целых чисел 1, 2, 3, ..., М вЂ” 1. Тогда № если й=/, О, если й~ 1, й и 1 одинаковой четности и — ! лг соа(п — ° — )= л О ((й — /) /2 — целое), 1, если й ~ 1, й и 1 разной четности ((й — /) /2 — полуцелое); М вЂ” 1 I й-1-! 2п! ( О, если й и 1 одинаковой четности, соа (и — — )= 1, если й и 1 разно/1 четности.
л О Эта лемма выводится ив леммы 1. Для вывода первого равенства надо положить р=(й — /)/2 и заметить, что р=(й — 1)/2 может принимать значения У У 3 ! ! У 3 У вЂ” — 1. 2 ' 2 + 2 ' ' ' 2 ' ' 2 ' '''' 2 2 ' 2 Очевидно, что для всех этих р, кроме р=О, отношение р/М вЂ” нецелое. Значение р=О получается лишь при й=/. Для обоснования второго равенства достаточно заметить, что полусумма (й+/)/2 может принимать только значения р=1, 3/2, 2, б/2, 3, ..., /!/ — 1/2, М вЂ” 1, ни для одного из которых отношение р/М не является целым.
Лемма 3. Если й, 1 — любые аз чисел 1, 2, ...,.№ — 1, то л-! 1 О, если йФ1. Для доказательства нам удобно добавить в исследуемую сумму нуйа . /п левое слагаемое а!п 0 — з!п 0 — и записывать ее так: У У н-! и — ! и-! Х = Х йп . /л 1 ст / й — 12н! ! %! / й+!2п! 3!пи — 5!пи — = — 7 соа! и — — ) — — 7 ООО (и — — ). У У 2 лТь ~ 2 У) 2 ь~~ '! 2 У)' л=а л О л О Из этого представления, полученного с помошью элементарного тож- 1 1 дества з!пес з!п!)= — соа(сс — р) — — соа(сс+р), и из леммы 2 следует 2 2 утверждение леммы 3.
Теперь давайте вспомним, что мы рассматриваем сетку на единичном квадрате 0(х(1, 0(у(! с шагами Ь„=1/№ й =1/№ Фиксировав некоторое у, мы получаем одномерную последовательность точек 1 хл=п/№ Это позволяет нам переписать лемму 3 в виде и — 1 1 Х 1 —, если й=/, з!и йпхл аш /пх„= 2й О, если й~/, 408 РАзностные методы !гл ч или более символично 1 ~з!пйпх з!и!пх= 2/~„' ! —, если л=1, « О, если А~l, 1, А=!,2,..., — — 1.
л Суммирование здесь подразумевается по всем внутренним точкам х, принадлежащим сетке. Аналогично ~ —, если л=! 1 х' -' "=1ж х ( О, если 1~3 л, 1=1, 2,...,— — 1. '''''Ь Теперь мы уже можем переходить к докззательству того, что функции ин'М(х, у) образуют в пространстве сеточных функций ортонормированный базис. Напомним, что и!я м=з!п(рхп)з!п(дул) и что ска- лярное произведение (ио' т1, и!а ° ен) вычисляется у нас по формуле 4!г,й„~ и!я ед (х, у) ига* яи (х, у). Поэтому «,Я (иоч т 1, инч чд)= 48 ь ~ 3!прахи т!п дтуп зйпрзхп 3!пдзуп= «,у = ~2А« ~Ч~ гйпрдпх и!п рапх < !'2Ь„'~ ~гйп д,пу з!п д пу) = « /1 1, если рт=р„д1=у„ О в противном случае.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
