Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 33
Текст из файла (страница 33)
В частности, это гарантирует существование решения системы (5.69) и его единственность. При выполнении тех же условий коэффициенты а, при всех 1 удовлетворяют неравенству 163 ~ЬЬ~ > )аЬ~ + )сЬ~, ~Ьу,~ > ~аЬ~ (1<6<т). (5.77) Тогда у; Ф О и ~ а;~ ~ 1 для всех 1 = 1, 2,..., т.
и Воспользуемся принципом математической индукции. Из условий теоремы имеем 71 = Ь~ ~ О и ! а~) = ) с~ ~/~ 6| ~ < 1. Пусть теперь ц-~ ~ О и ~ аЬ ~~ 4 1 для некоторого 6 > 1. Тогда )уЬ~ = ~ЬЬ+ аьаь ~) 1 ~ЬЬ( — ~аЬ~ ~аЬ ~~ Э ~ЬЬ~ — ~аь~, Из полученной оценки в силу условий (5.7Т) вытекает справедливость неравенств ~ТЬ~ > О и ~ТЬ~ 1 ~сьев. Следовательно, уЬ ~ О и ~аЬ~ = ~сЬ~/~уЬ~ ~ 1. ° 4.
Метод прогонки и разложение матрицы на множители. Описанный вариант метода прогонки можно рассматривать как одну из схем метода Гаусса (без выбора главного элемента), в результате прямого хода которого исходная трехдиагональная матрица Ь~ с~ 0 0 ... 0 аг Ьг сг 0 ... 0 0 ав Ьг св ... О О 0 0 0 0 0 0 0 О 0 ... ан-ь Ьн-ь сн-~ О О О О ... О а Ь представляется в виде произведения двух двухдиагональных матриц: (5.78) Здесь 1-а~ 0 ...0 0 0 1 -аг...О 0 70 О...О О аг 'уг 0 "0 0 аг 73 - 0 4 0 0 0 ...ан О 0 0 ...1 — а 0 0 0 ...0 1 Так как для определения Ь и У нет необходимости вычислять коэффициенты Д, то общее число операций на получение разложения (5.78) составляет примерно Зт. 164 ~ а,~ 4 1, а следовательно, обратная прогонка по формуле (5.Т6) устойчива по входным данным (см.
пример 3.27). Положим а~ — — О, 6 = О. Т е о р е и а 5.4. Пусть коэффиииентм системы (5.69) удовлетворяют следующим условиял диаьональноьо преобладания: Подобно тому как это описано в С 5.7, разложение (5.78) можно использовать для решения систем с многими правыми частями. Если нужно решить р систем с матрицей А, то общее число операций составит примерно Зпт + 5тр.
К сожалению, при обращении матрицы А теряется ее трехдиагональная структура. Обратная матрица является заполненной, однако для ее вычисления с помощью разложения (5.78) требуется примерно 2.5т2 арифметических операций. Так как деС А = йеС Ь ~$еС К а с$еС 0 = 1, то определитель трехдиагональ ной матрицы, после того как получено разложение (5.78), вычисляется по элементарной формуле ЙеС А = 'у~ уз ...
'1д,. 5. Некоторые варианты метода прогонки. Наряду с изложенным выше "стандартным" вариантом метода прогонки (правой прогонкой) существует большое число других вариантов этого метода. Это методы левой прогонки, встречных прогонок, немонотонной прогонки, потоковый вариант метода прогонки. В ряде случаев эти модификации могут существенно улучшить обусловленность прогонки.
Для систем уравнений, обладающих близкой к (5.69) структурой, разработаны методы циклической прогонки, матричной прогонки и др. С указанными вариантами метода прогонки можно подробно ознакомиться в [42], 172]. З 5.10. ЦЯ-разложение матрицы. Методы вращений и отражений Метод Гаусса не является единственным методом исключения, используемым для решения систем линейных уравнений и приведения матриц к треугольному виду. Рассмотрим два метода исключения, обладающих в отличие от метода Гаусса гарантированной хорошей обусловленностью — метод вращений и метод отражений. Оба этих метода позволяют получить представление исходной матрицы А в виде произведения ортогональной' матрицы Я на верхнюю треугольную матрицу В: ~ Напомним, что матрица Ц называется ортогональной, если для нее выполнено условие Ц' = ~~~, что эквивалентно равенству С~К7 = 1ь 165 (5.79) Представление (5.79) — это ЯК-раззожение ватри))з) на множители, 1.
Метод вращений. Опишем прямой ход метода. На 1-м шаге неизвестное х) исключают из всех уравнений, кроме первого. Для исключения х) из второго уравнения вычисляют числа а)1 ))г 1 > з)г= > (5.80) С1г = >~2 .2. 22 >22 обладающие следующими свойствами: сг + з) = 1, -з)гап + с)гаг) — — О. (5.81) а11 с)+ а1г сг+ а1З сЗ+ .. + а1»> с»>= Ь) 11) (.1) (1) 11) (1) агг гЪ+ агз зз+ "-+ аг»> с>з= Ьг 11) (1) 11) 11) >)з)з) + азгсг + аззсз + " + азасв = Ьз (5.82) >)»>1 1 + а»>г~г + а»>ззз + " + >)»жзл> — Ьв в которой аг~ — — -з)га1, + с)гагу (1 4 14 )и), (1) Ьг — — -з)гЬ) + с)гЬг.
(1) 11) а)) = с)га)~ + з)гагг> Ь) = с)гЬ) + з)гЬг, <1) (5.83) Заметим, что аг)~ = — з)гап + с)гаг1 — — 0 в силу специального выбора (1) чисел с)г и з)г (см. равенства (5.81)). Естественно, что в случае аг) — 0 исходная система уже имеет вид (5.82) и в исключении неизвестного х) из второго уравнения нет необходимости. В этом случае полагают с)г — 1 и з)г = О. Как нетрудно видеть, преобразование исходной системы (5.1) к виду (5.82) эквивалентно умножению слева матрицы А и правой части Ф на матрицу Т)г, имеющую вид с)г з)г О О ...
О -з)г с)г О О ... О О О 1 О."О О О О 1 ... О Т1г = О О О О ... 1 166 Затем первое уравнение системы заменяют линейной комбинацией первого и второго уравнений с коэффициентами с)г и з)г, а второе уравнение — аналогичной линейной комбинацией с коэффициентами — з)г и с)г. В результате получают систему Для исключения неизвестного х) из третьего уравнения вычисляют числа (1) ((1 1 аЗ1 С)З = > з)З= >(дш)2 ~,г >(,'пт)г ~,> (5.84) такие, что с)з + з)з — 1, -з)за)1 + с)заз1 — — О. Затем первое уравнение 2 2 (1) системы '(5,82) заменяют линейной комбинацией первого и третьего уравнений с коэффициентами с)з и з)з, а третье уравнение — аналогичной комбинацией с коэффициентами — згз и с)з.
Это преобразование системы эквивалентно умножению слева на матрицу с)з О з)з О... О О 1 О О ... О -з)з О с1з О - О О О О 1 ... О Т О О О О ... 1 и приводит к тому, что коэффициент при х) в преобразованном третьем уравнении обращается в нуль. Таким же образом х) исключают из уравнений с номерами 1 = 4, ..., (г). В результате 1-го шага (состоящего, как мы видели, из ))з — 1 "малых" шагов) система приводится к виду а( »> 1) + а( ») 1) + а( ") 1) х + + а()>) 1) = 1)( з) 1) а) 1 х) + а) 2 хг а( з хз ...
а(») х»> = ()22 хг +((гЗ хЗ +" +((г х =62 (1) ( 1) ( 1) ( 1) (5.85) + ((зз хз + - + ((зв х — — (з (1) (1) (1) (1) ()3 2 Х2 ((>зг хг + ()»>з хз (1) (1) В матричной записи получаем А(1) х = Ь(1) где А(') = Т1>з ." Т1зТ)2А, $(" = Т)~ .. Т1зТ125. Здесь и далее через Т),1 обозначена матрица элементарного преобРазования, отличающаяся от единичной матрицы Ж только четырьмя элементами. В ней элементы с индексами ()1, й) и (1, 1) равны сн, эле- 167 мент с индексами (х, () равен зН, а элемент с индексами ((, х) равен — з)(1, причем выполнено условие с),1 + з$1 = 1. (5.86) т Ть( = Ть( и, следовательно, матрица Т)(1 ортогональная. На 2-м шаге метода вращений, состоящем из т — 2 "малых" шагов, из уравнений системы (5.85) с номерами 1 = 3, 4, ..., т исключают неизвестное хг.
Для этого каждое з-ое уравнение комбинируют со вторым уравнением. В результате приходим к системе а( 1) , + а( " ') , + ( 1) х + ... + а(а 1) = Ь(а 1) а11 Х1 а1г Х2 а1З ХЗ " а)т (в 1) + (а" 1) + + (в 1) а(в 1) азз хз +" + аза ха =Ьз (г) ! 2) ( 2) ааз хз +" + ааа ха Ьа (г) (2) (г) В матричной форме записи получаем А(2) х - Ь(г) где А(2) = Тга" Т24ТгзА(" Ь'2' = Тга ...
Тг(ТгзЬ"). После завершения (т — 1)-го шага система принимает вид ( т-1) ( а-1) ( а-1) ( в-1) ( т-1) а(1 х) + а(г хг+ а)з хз+ ". + а)в х„= Ь) ( в-1) ( а-1) ( в-1) ( в-1) а22 х2+ а22 хз + "+ а2а ха Ь2 ( а-1) ( а-1) ( а-1) азз хз+" + азв ха= Ьз ( а-)),( т-1) авт ха — ут или в матричной форме записи 168 Действие матрицы Т((1 на вектор х эквивалентно его повороту вокруг оси, перпендикулярной плоскости Охьх( на угол (о),1 такой, что сц = = сов ((оц, за( = в)п ()2)С1 (существование такого угла гарантируется равенством (5.86)). Эта геометрическая интерпретация и дала название методу вращений. Операцию умножения на матрицу Т),1 часто называют плос)(ил) оращениел) (или преобразоааниел) Гиоенса).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
