Бабенко - Основы численного анализа (947491), страница 121
Текст из файла (страница 121)
Докажем, что и для разностной задачи имеют место аналоги этих неравенств. Для простоты предположим, что в граничных условиях (1.2) константы Аш ф О, С1 = = Сз = О и что выполнены неравенства (7). Тогда в силу неравенства (8) п1ах)зу < б гпах )ь(. ь ь Из уравнений (6) вытекает, что л з~,~е ... ( < у — ,'9~я~! < 1 -;- 5 гптах9~ птах ~~(.
(24) Воспользуемся слелующими очевидными тождествами, справедливыми для произвольных сеточных функций дь: й ь ее~., 1еь: й ~-~ фь; т(д М =ыье ~'ь+<:ьМь. (26) ~1 (Ю)ь) =- Еь-т~ еь+ ~Згь(~ать+ Мьы) + тье1~1 Рь Второе тождество получается повторным применением первого. Из опре- деления второй разности следует, что ь — 1 зяь — ~1де = ~~' Ь з=е и поэтому 'тззь! < (Ьле(+/с щах (Ь'зз!. е<з<л — г (26) Злмвчлнив 2, зйетод прогонки обладает весьма посредственной устойчивостью, что наблюдается при анализе погрешностей округления.
Предлагаемый метод распараллеливания в этом смысле еще хуже, что видно невооруженным глазом. В самом деле, вычисление произведений матриц Е21... („>~ - процедура, которая может привести к значительному накоплению погрешности, поскольку Я, 1 > 1. Последующая процедура деления для нахождения величин г, не исправляет положения. И действительно, сравнительные вычисления, проводившиеся на ЭВ61 Сгау-1 (см. [144)), обнаружили, что алгоритм Стоуна значительно уступает по точности друтим алгоритмам и почти сравним с наихудшим из возможных алгоритмов, основанном ва правиле Крамера.
Таким образом, за параллелизм операций приходится платить не только излишними вычислениями, но и потерей точности, что вынуждает работать с чиелами большой разрядности. Это не означает, по так бывает всегда, когда приходится строить параллельный алгоритм,тля сугубо последовательного процесса, но тем не менее приведенный пример далеко не единичный. о 3, О решении краееьит задач методом прогонки 591 Применяя второе тождество (2о) к сеточным функциям аы згм получим при 6<и — 2 44 (зада) < |пах (оз )ь зь(+!Лць(еаза + (ьзь44() + шах;21,~ь щ(. Отсюда в ситу (24) и очевидных неравенств )Ьеь~ < С6, (Ьодь! < С6" следует неравенство 6 2,:Ьо(зьдьЯ < С1 рвах(Д + С6 ((Ьаь + )Ьзьы~).
з Неравенство (26) на основании (24) влечет )Ьзь' < (Ьзо, + п6 Гоп1ах Д ~, и гюэтому, поскольку п6 .=- 1, ~ра (зада < Сз гпах ~Д ~ 4-2С6 ~~Ьзо~. (27) Обратимся теперь к граничному условию предпоследнему уравнению системы (6). Учитывая вид коэффициентов ап, аг2 и замечание, следующее за формулой (5), имеем по Ага + Апяо = — А426(Уо — Чозо). 6 2 Поэтому 6. е12о~ < ~за~+ 6!Уо — чозо .д Ап 1 12 2 и, следовательно, из (27) вытекает неравенство 6' 2'А2(47ьзь), < С4 шах ~~. ~. Применяя оператор еа2 к уравнениям системы (6) при 6 = 1, 2,..., и — 3 и учитывая, что Ьа(,го ы г) = е14аь и получим 6 Лезь 4 = Ь-(ь — Ы(йьзь), откуда 6 — 4 еа4 ~ < 6 — 2~~2у ~+Сешах,е О помощью совершенно аналогичных выкладок можно получить оценку 6 а1Ь~зь г~ < 6 ~~Ь~ь~+ Со гпах ~Дф з Двя ЭТОГО дОСтатОЧНО ВОСПОЛЬЗОВатЬСя СООТНОШЕНИЕМ 412ЗЬ 2=41(Ьаео Г) и уравнениями (6).
Поэтому, если учесть полученные неравенства, то придем к следующей фундаментальной оценке: 4 2 гпах ~~ 6 з,Ьззь', < А шах ~~ 6 з Ьзо'ь, (28) О<о< -З ' О<о< -2 з=о з=о 592 Глаза у. Численное решение ироеомх задач 5. Система первого порядка. Вместо того чтобы рассматривать дискретизацию задачи (1.6), мы рассмотрим более общую задачу о решении системы линейных уравнений. В самом деле, в и. 1 З1 гл. 7 было показано, как произвольное уравнение т-го порядка свести к системе уравнений первого порядка.
В вопросах дискретизации такая редукция довольно небезобидная вещь н влечет за собой целый ряд последствий. Тохнически более удобно работать с системами уравнений, Пусть краевая задача рассматривается на отрезке 1е = (О, Ц. Обозначим через У(х) вектор-функцию У: 1о —. В.'", У = (уп ..., у„„)'. Линейная система имеет внд дУ вЂ” + Р(х)У вЂ”. Г(х), дз: (29) где Р(х) -- т х т-матрица, элементы которой принадлежат простран- ству С(0, Ц, а Г(х) = (уз(х), ..., уео(х))' -- правая часть. Граничные условия в соответствии с (1А) запишем в виде АУ(0) + ВУ(1) = С, (30) где А, В ги х т-матрицы, С .— —. (Сы ..., С,и)' вектор правых частей.
Если мы положим у = уп у' = уж ..., уй" В = у, то краевая задача (1,6) будет представлена в виде (29), (30), где 0 — 1 0 0 0 — 1 Р, /1зо РзГРо 1ПФо Г(Х) =(О, ..., ДХ))', А=(АЬЗЬ"'д и В = (ВЬЗ)зЗ и Рассмотрим наиболее простую дискретизацию задачи (29), (30). Будем удовлетворять уравнению (29) в точках х 17з = (1+ 1,)2)1е (1е = и, з —.. О, 1, ..., и — 1). Г1оложим Рзт17я — -- Р(холка), Гзэл7я — Г(хзжз7я); заменяя производную центральной разностью, получим 1;„.,— 1; 1 + . Рз-'1/2(Уз4-1 з 1з) = Гз~-'д 77з —,1/ш 2 где К .ьз7 = 0(ЬЯ), если У(х) й Сз(0, Ц. где константа Л не зависит от 6 и д.
Эта оценка является дискретным аналогом неравенства (1.8) в случае уравнения (1.Ц и з = 2. Тем самым корректность дифференциальной задачи по наследству переходит к ее дшкретному аналогу --. разносгной краевой задаче, если применить указанный выше способ дискретизации. Как реально воспользоваться соотношением (28) лля того, чтобы получить дополнительную информацию о решении, неясно. з 3. 0 решении кроеоых оодоч методом прогонки 393 Отбрасывая остаточный член аппроксимации, придем к следующей разностной краевой задаче: 1 1 -Ь(г,ь, — г,) Ь -Р„,дг(г,, - г,) —. Г,„.гд„Я, -Ь Вг„= С. 2 (31) у = О, 1, ..., и — 1, где Е () = О. 1 ..., и) искомые векторы, Е й В.о'.
Рассмотрим наборы с = Я,я ..: Г~ — ~,гю С) С = (Яо: ..., Е~) как точки (и -Ь 1) т-мерного пространства В.~" "г . Тогда система (31) определяет отображение Н: ( С, Н: В.~"+0 — Н1"+О '. Нас же интересует обратное отображение Н ', и прежде всего условия, при которых оно существует. Введем два комплекта пуюстранства В,О'+О~ для правых частей системы (31) и неизвестных и в ннх введем нормы ))Ц = шах( Гг гз(оо.... г )Г„гд(оы ~С ео)., где ~ ~,, — чебышевская норма вектора, и /Д, = шах(Ь !г3гОо ~, ..., Ь /гухо г!ы,) —,п1ах(,гОо!,о, ..., Я„/ .).
Уравнения (31) представляют одну из возможных дискретизаций краевой задачи, кстати, наиболее простую, и нашей главной целью будет выяснение вопроса о том„когда они разрешимы при любых правых частях.Естественно потребовать, чтобы разрешимость уравнений (31) ямала место тогда и только тогда, когда разрешима задача (29)г (30) прп любых правых частях. Имеет место следующая Теорема 1.
Если зада и (29),(30) разрешима при любых правых частях Г(х), С, то найдетея такое Ьо ) О, что при Ь ( Ьо отображение Н обратимо, и для любого вектора С б В.~" 0 выполняется неравенство Ы ° ( -'ЦЫ, (32) где ь —... Н 1г„а константа А не зависит от п. Наоборот, если неравенство (32) выполняепюя при Ь ( Ьо, то задача (29), (30) разрешима. ДоклзАтельстВО. Допустим, что неравенство (32) не выполняется при Ь < Ьо,и тогда найдется такая последовательность (10), Ьг ( О,что длЯ каждого Ьг сУществУют вектоРы сг ~г с Й,О' г такие, что ()Цг = 1 г,, = 1 и ег ) О.
Заметим, что используемые нормы также зависят от Ьь т. е, от Ь но для упрощения обозначений индекс 1 яе всегда будет указываться. Обозначим через Г г (х) кусочно-линейный сплайн, построенный по значениам в Узлахх (з =-О, 1, ..., п — 1) Равным Р цгЯ |-ЬЕ1)гг2. Таким образом, сплайн будет определен на огрезке (О, 1 — Ь). Дополним его на отрезке (1 — Ь, Ц, полагая Е1(х) =-.
Тг(1 — Ь). Аналогичным образом построим сплайны Ег(х), И(х) по значениям в узлах Ь ~г1Я, Гзг.г гг 0 = О, 1,..., и — 1) соответственно. Тогда первые уравнения системы (31) можно записать в эквивалентном виде: Е (х) -~- Е,(х) — -- М( ). Глава О. Численное резаение краееъсх задач Наконец, построим кусочно-линейный сплайн Аа(х) по значениям Уз в узлах у = О, 1с ..., п. Это построение мы проведем для каждого Ь| и в результате получим последовательности (Еы(х)) (й = О, 1, 2), (ЛО(х)).
В силу предположения последовательность (ЛХ~(х)) на (О, Ц равномерно стремится к нулю. Последовательность (бщ(х)) компактна в метрике равномерной сходимости на (О, 1 .. В самом дело, вектор-функция Бас(х) строится по значениям Яз~ в узлах, а поскольку Ц~~, = 1с то )УзЦ, < 1 О .=- О, 1, ..., пу), и поэтому шах ~Еа~(зс)! < 1. а<. <з Производная вектор-функции Ха~(х) существует вскату, за исключением узлов, и при хз < х < хз 4 без(х) дх и, следовательно, е1бо~(х) <1, г1х а поэтому ба~(х б) — Ле~(х)! < а.
Стало быть, последовательность (Еас(х)) удовлетворяет условиям теоремы 1 3 2 гл. 2, и, значит, она компактна в пространстве непрерывных вектор-функций, определенных на (О, Ц. Без ограничения общности можно считать, что последовательность (Хес(х)) сходится прн1 — ~ со. Пусть У(з) = !1пз Ащ(х). С оо Покажем, что гогда равномерно сходится последовательность (Лп(х)) и 1пп Ан(Х) = Р(х)1с(х).
В сакюм деле, пусть 1' = РзЯ (у = Е оо —.... О, 1, ..., и) н К(х) —. кусочно-линейный сплайн, построенный по этим значениям. Тогда, учитывая, что 1 1 1 — Ргьц~(Х, ~+У,) — РЕ, = — (Рзч.ц — Р,)(Е,-~+2,)-~ — РЬ2, — -- (1), получим, что йш з1(х) = 1пп бп(х). Далее, обозначая через У(х) Ы со ! - со кусочно-линейный сплайн со значениями в множестве пг х ш матриц, построенный по значениям Р в узлах хь (у = О, 1, ..., и), получим прих, <х<хз — р,+* "(р,,— Р,) г,+* „хз(г,,— г,) .—..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
