Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 31
Текст из файла (страница 31)
Пример 5.11. Используя метод Гаусса с выбором главного элемента по' столбцу вычислим определитель матрицы 150 2 -9 5 1.2 -5.3999 6 1 -1 -7.5 на 6-разрядной десятичной ЭВМ. Повторяя преобразования из примера 5.9, получим матрицу 2 -9 5 А2' = 0 35 -10 0 0 3.00029 Так как была сделана одна перестановка строк, то формула (5.50) дает йе1(А) в (-1) 2 3.5 3.00029 м -21.0020. Можно с достаточной степенью уверенности предположить, что во многих технических науках, где традиционно используются определители, в ближайшее время неизбежен переход к использованию других более содержательных характеристик линейных моделей. Такими естественными характеристиками могут служить, например, собственные числа и собственные векторы матриц (см.
гл. 8). $5.7. Метод Гаусса и разложение матрицы на множители. Ь У-разложение (5.51) 1. Схема единственного деления и Хб-'-разложение. При выполнении вычислений 1-го шага исключения по схеме единственного деления система уравнений приводится к виду (5.52) А(ы х — Ь(1), где 151 Вернемся еще раз к методу Гаусса с тем, чтобы рассмотреть его с более общих позиций. Излагаемый ниже подход оказался чрезвычайно плодотворным и привел не только к более глубокому пониманию метода, но и позволил создать высокоэффективные машинные алгоритмы его реализации, а также рассматривать другие точные методы с единой точки зрения. Рассмотрим сначала простейший вариант метода Гаусса для решения системы линейных алгебраических уравнений Ь(1) г А'1> = Ь(1) з Ь(1) Ь<ы а коэффициенты а(<1>, Ь<.1> (з, )' = 2, 3, ..., т) вычисляются по формулам (5.29), (5.31).
Введем матрицу -п„) О О Как нетрудно проверить, справедливы равенства А('> = М"~А, Ь<'> = ЩЬ, т. е. преобразование системы (5.51) к виду (5.52) эквивалентно умноже-' нию левой и правой частей системы на матрицу М). Аналогично можно показать, что вычисления 2-го шага исключения приводят систему (5.52) к виду А(г) х = Ь'2', где А(г) = М2А(1), Ь(г) = МгЬ(1), Ь<') 2 А( 2)— , Ь( 2) = Ь(2) з Иг = О -дго...1 6(2) После (т — 1)-го шага, завершающего прямой ход, система оказывается приведенной к виду А<~ '>х= Ь("'> (5.53) с верхней треугольной матрицей А<»> '>. Здесь 152 <з>1 ((>г О агг агз ...
аг»> (1> <1> <1) а( ' > (((1' ... а< 1 > ~З2 ЗЗ " З>з 1 О О ... О -пг> 1 О ...О -пз< О 1»> О (( ... <) (1) (1) (1) О О (><2> ... ()(2> зз " з» 1 О О ... О О 1 О ... О О -)(>зг 1 ... О А>т)) = М >А>т г) Ь(щ-1) = М„1Ь(т-г) ап а)г а) з 1т ~ Мт-1 А1т ') = О 0 О ...
а>т)' тт Ь''' г Ь>т>> = Ь>г) з Ь>т 1> т Заметим, что матрица А>т '> получена из матрицы А последовательным умножением на М), Мг, ..., Мт>. А>" '> = Мт> ... МгМ)А. (5.54) Аналогично, Ь1 т"1 > — Мт 1 ... МгМ1Ь. (5.55) Из равенства (5.54) вытекает следующее представление: А = М1)Мг>...
М„-')А)т 1'. (5.56) Как легко проверить, ,Мг = 1 М~~~ = 0 ртг 0...1 »т)0 0...1 Для этого достаточно перемножить матрицы М> и М>, (Й = 1, 1 >)з — 1), в результате чего получится единичная матрица. 153 а'1> а'1> ... а11> гг агз " 'гт азз " азт 1 0 0 ... 0 »г 1 0...0 ,аз)0 1 ...О 1 0 0 ... 0 0 О 1 0 ... 0 0 0 0 О ... 1 0 0...>тт)1 1 0 0...0 0 0 1 0 ... 0 О 1 0 0 ... 0 0 1 О ... 0 рзг 1...0 Введем обозначения У = А)н)), Х = М))Мг) ...
М)). Вычисляя матрицу Ь, убеждаемся в том, что она имеет следующий вид: 1 0 0 ... 0 ~иг) 1 0 ...0 ра) Рзг 1 ...О (5.57) Фн) Рвг Фаз " Тогда равенство (5.56) в новых обозначениях примет вид А= ХГ (5.58) а)г "а)а агг '" аг~ аг,а+) а)н ... а))) гн Иг) Рйг ... аД ) а~)~~Д ... а~~~ )) а)") а' ") р),, ... аь, ь а~), ~„) а1+ Фь+),) Рнг " Рай ан, ~~) (й ) Обозначения треугольных матриц буквамм Ь и У вызваны тем, что эти буквы являются начальными в английских словах 1о)чет — "нижний" и ))ррет — "верхний". 154 Это и есть) ХУ-разложение матрицы А — представление матрицы А в виде произведения нижней треугольной матрицы Х и верхней треугольной матрицы Г Таким образом, прямой ход метода Гаусса без перестановок можно рассматривать как процесс вычисления Ь У-разложения матрицы системы, на Й-и шаге которого определяются элементы а-го столбца матрицы Ь и ьй строки матрицы К Возможность Ь У-разложения обосновывается следующей теоремой.
Т е о р е м а 5.3. Если все плавные миноры матрицы А отпличны от нуля, то су)цеству)от единстпвенные ниленяя треугольная матприца Ь вида (о.5У) и верхняя треугольная матрица У такие, что А = л К Структура матриц Х и У позволяет организовывать компактное размещение элементов этих матриц в памяти ЭВМ по мере их вычисления. На й-м шаге исключения в области памяти, где первоначально располвгвлвсь матрица А, размещается матрица При этом вся необходимая для дальнейших вычислений информация сохраняется. Пример 5.12. Проиллюстрируем 1 У-разложение на примере решения системы (5.35). На основании данных табл.
5.2 можно записать 1 0 0 О 0.5 1 0 0 0.3 — 1.6 1 0 0 — 3 25 1 10 6 2 0 0 -2 -3 4 0 0 -4.4 5.4 0 0 0 0.5 Следовательно, 1 У-разложение матрицы системы имеет вид 10 б 2 0 Π— 2 — 3 4 0 0 -4.4 5.4 0 О 0 05 6 2 0 1 — 2 4 5 1 — 1 б — 2 2 10 5 0 1 0 0 0 0.5 1 0 0 0.3 -1.6 1 0 0 -3 2.5 1 2 Использование Х б'-разложения. В современных программах, реализующих метод Гаусса на ЭВМ, вычисления разбивают на два основных этапа. Первый этап — это вычисление ЬУразложения матрицы системы.
Второй этап — обработка правых частей и вычисление решения. Смысл выделения первого этапа состоит в том, что он может быть выполнен независимо, для его проведения не нужна информация о правой части системы. Это как бы этап предварительной подготовки к быстрому вычислению решения, Именно для получения ЬУ-разложения производится основная масса вычислений (примерно яз) тз арифметических операций) . На втором этапе выполняют следующие действия: 1о. Преобразуют правую часть Ь по формулам прямого хода; необходимые для вычисления коэффициенты р,у берут из матрицы Ь.
В результате получают вектор Ь'~ ы, связанный с вектором Ь формулой (5.55). 2о. С помощью обратной подстановки решают систему Уз = Ь~ ~ ~~. Для непосредственного вычисления решения з на втором этапе требуется примерно 2тт арифметических операций. В случае, если необходимо решить р систем уравнений с фиксированной матрицей А и различными правыми частями Ы~~~, И<т~, И~р~, первый этап проводят лишь один раз. Затем последовательно р раз проводят вычисления второго этапа для получения решений х<~>, з~г~, ..., т<,>. ДлЯ этого, как и в 3 5.6, тРебУетсЯ пРимеРно Яз)тз + + 2риР арифметических операций. 155 Пример 5.13.
Решим систему 10х( + 6хг + 2хз — — 8, 5х( + хг — 2хз + 4х.( — — 7, Зх( + 5хг + хз — х.) = 2, 6хг — 2хз + 2ха = 2. Воспользуемся ЬУ-разложением матрицы системы, указанным в примере 5.12. Сначала преобразуем вектор правой части Ь = (8, 7, 2, 2)т по формулам прямого хода. 1-и ш а г, Ьг~ = Ьг дг(Ь> = 7 0.5 8 3, Ь(> = Ьз — )((з)Ь) = 2— — 0.3 8 = -0.4, Ь')' = Ь4 — 7л~)Ь) —— 2 — 0 ° 8 = 2. После 1-го шага получим Ь()) — (8 3 04 2)т 2-и ш а г. Ьз(г> = Ь<(> — дзгЬг()> = -0.4 — (-1.6) 3 = 4.4, Ь<г' = Ь4<(> — р4гЬг((> = 2 — (-3) 3 = 11.
После 2-го шага найдем Ь' г' = (8, 3, 4.4, 11)т. 3-и ш а г. Ь<з) = Ь<г> — )((43Ьз<л) 11 25.4,4 = О. В результате прямого хода получен вектор Ь< з > = (8, 3, 4.4, 0)т и система приведена к виду 10х( + 6хг + 2хз =8, — 2хг — Зхз + 4х( = 3, — 4.4лз + 5.4х( = 4.4, 0.5хл = О, Обратный ход дает значения неизвестных х4 = О, хз = -1, хг = О, х( = 1. 3. Метод Гаусса с выбором главного элемента и разложение матрицы на множители. В отличие от схемы единственного деления схема частичного выбора предполагает на Ь-м шаге прямого хода перестановку уравнений системы с номерами л>< и Ь (при выборе в качестве главного элемента Ь-го шага элемента а.
ь). Это преобразование эквивалентно умножению системы на матрицу Р~, которая получается из единичной матрицы перестановкой )Ь-й и Й-й строк (см. пример 5.14). Исключение неизвестного на х-м шаге по-прежнему эквивалентно умножению системы на матрицу М><. Таким образом, после 1-го шага система Ах = Ь преобразуется к виду А"'х = Ь'", где А''> = М>Р(А, Ь''> = М>р(Ь.
После 2-го шага система преобразуется к виду А'г'х = Ь'г>, где А'г' = МгргА'", Ь(г) = МгРгЬ(1>. После завершающего (т — 1)-го шага прямого хода система оказывается приведенной к виду А'" '> х = Ь(и '>, где А<"' '> М„>Р„,А< ~-г) Ь(~) > М„,Р„,Ь(~-г) Как нетрудно видеть, 156 15.59) (5.60) А~т ы = Мт-1Рт-1, МгРгМ1Р1А, в' " " = М -1Рин " МгРгМ1Р1 а. Равенство (5.59) равносильно следующему разложению матрицы А на множители: (5.61) где У = А' " ы — верхняя треугольная матрица.
Разложение (5.61) не является ЬУ-разложением матрицы А. Однако прямой ход по-прежнему равносилен Ьб'-разложению, но уже не самой и матрицы А, а матрицы А, полученной из нее в результате соответствующей перестановки строк. Это разложение имеет вид А=ИУ, (5.62) ФФ где А = Рт1Рт г ... РгР|А, Ь вЂ” нижняя треугольная матрица, отличающаяся от матрицы (5.57) перестановкой множителей в столбцах.
Пример 5.14 Найдем разложение вида (5.62) для матрицы системы (5.39), используя результаты вычислений примера 5.9. Так как 1-й шаг прямого хода не потребовал перестановки, а на 2-м шаге были переставлены второе и третье уравнения, то 2 -9 5 1 — 1 — 7.5 1.2 — 5.3999 6 1 0 0 0 0 1 О 1 0 о о 0 1 0 0 0 1 А= Рг Р1 = Для матрицы А прямой ход уже проводится по схеме единственного деления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
