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