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