Разряженные матрицы. Р. Тьюарсон (984138), страница 18
Текст из файла (страница 18)
Для того чтобы ошибки округления были малыми, не требуется никаких перестановок строк или столбцов. С другой стороны, если матрица А симметричная, но не положительно-определенная, то для удержания ошибок округления в разумных пределах необходимо производить выбор главных элементов, н это нарушает симметрию. Если на каждом шаге брать наибольший диагональный элемент, то это сохранит симметрию, но не гарантирует устойчивость с точки зрения ошибок округления.
В свете сказанного разложение Холецкого применимо к симметричным разреженным матрицам, если произвольный порядок разложения не влияет отрицательно на точность вычислений. К счастью, во многих '! я ! и р А,— и .рд. Ед Метод Холгцкого (квадратнык корнев, Банахгвича)119 „актических приложениях зто имеет место (например, см. Тинни и Уолкер (1967)). для минимизации заполнения в методе Холецкого „ажно использовать теорему 4.3.5. Однако в этом случае Вд=Тд, (4.5.4) что с учетом формул (4.3.1) и (4.3.2), очевидно, означает, что Лд симметричная. Поэтому ' из равенств (4,3,3) н (4.3.4) можно заключить, что сыд> = (ттчд')'. (4.5.5) Имея в виду вышеизложенное, можно вместо теоремы 4,3.5 использовать следующее следствие. Следствие 4.5.6.
Если т1д>=шах(ганг) и мы преа небрегаем воэможностью взаимного уничтожения слагаемых в скалярных произведениях формулы (4.5.3), то перемещение элемента а,+д ь,+д 1 в (й, й)-ю позицию в начале й-го шага метода Холецкого приводит к наименьшему заполнению. Доказательство. На любом шаге метода Холецкого только диагональные элементы матрицы А могут быть псреставлены друг с другом, в противном случае будет нарушена симметрия. Поэтому в теореме 4.3.5 необходимо брать гх = р. Учитывая равенство (4.5.5), отсюда получаем тчд1 + с<д' = гпах (Р<д1 + сыд)) г а или тик' = шах т1Д>. г а п Начиная с этого места, доказательство следствия такое же, как н доказательство теоремы 4.3.5 (с 1д„, замененным на ирд).
Изложенное выше следствие можно применить при моделировании метода Холецкого, если исходить из верхней треугольной части матрицы В1 (полученной из матрицы А путем замены в ней ненулевых элементов единицами) и произвести булевы умножения и суммирования в формуле (4.5.3) для регистрации заполне- 12О Гл 4. Лряиое треугольное разложение ния. Заметим, что нет нужды моделировать формулу (4.5,2). Кроме того, не нужно производить деления в формуле (4.5.3) при булевом моделировании, так как знаменатель всегда равен единице.
Поэтому может быть определена матрица перестановок Р и матрица А упорядочена с помощью уравнения А = РАР. Действительный метод Холецкого применяется затем к матрице А. 4.6. Подходящие формы для треугольного разложения В главе 3 были приведены некоторые элементарные формы, к которым может быть априорно преобразована данная матрица так, что заполнение, если оно имеется, ограничивается определенными областями этих форм. Теперь покажем, что такие же формы желательны и для треугольного разложения. В конце равд, 4.2 мы указали на то, что Е = Е ', где Е и Š— нижние треугольные матрицы, полученные соответственно в методе Краута и в гауссовом исключении, при условии, что порядок и выбор главных элементов в обоих случаях одинаковы.
Теперь, учитывая формулу (2.2.6), имеем Ен ' ' ' Е2Е!Е ~н и из формул (2.2.3) и (2.2.4) является очевидным, что матрица Ея преобразует й-й столбец матрицы Ен, ... ... ЕзЕ1Е к вектору ея, а все остальные столбцы остаются без изменений. Таким образом, можно заключить, что т11м = О, 4 ( й, ! 1 Лд (46А) Ч"'= — и Ц)е'= — — ", 4>й. Гяе Еяь ' Из всего сказанного с очевидностью следует, что элементы матрицы Е и нетривиальные элементы множителей в разложении Е имеют одну и ту же структуру распределения ненулевых элементов и могут поэтому храниться в одинаковых ячейках. Таким образом, в 4 7. Библиография и комментарии о 0$ бонх методах, и в методе Краута, и в гауссовом исключении, заполнение одно и то же, и поэтому для бонх методов желательны одни и те же формы.
Если Л является симметричной матрнцей или матрнцен с симметричной структурой распределения не(нулевых внедиагональных элементов, то ленточная форма (ВГ), двусторонне окаймленная ленточная фор„а (РВВГ), диагональная блочная форма (ВРГ), двусторонне .окаймленная диагональная блочная форма (РВВРГ) или комбинации этих форм являются желательными для метода Краута (для метода Холецкого, если Л = А'). Если матрица А несимметричная, она может быть преобразована перед применением метода Краута к односторонне окаймленной ленточной форме (ВВВГ), односторонне окаймленной диагональной блочной форме (6ВВРГ), треугольной ленточной форме (В(Х)ТГ), окаймленной треугольной ленточной форме (ВВ)нТГ), треугольной блочной форме (ВТГ), окаймленной треугольной блочной форме (ВВТГ) или к комбинации этих форм. 4.7.
Библиография и комментарии Задачу оптимального упорядочения для треугольного разложения матриц, встречающихся в некоторых практических приложениях, рассматривали Карпентьер (1963), Сато и Тинни (1963), Эдельман (1963, 1968), Чан (1969), Мак-Кормик (1969), Тинни (1969), Ашкенази (1971) и Дженнингс и Тафф (1971).
Во многих задачах электрических цепей треугольное разложение является особенно полезным (Тинни и Уокер (!967); Эрисман (1972) ). Некоторые теоретические результаты сравнения метода Краута с другими мето. дами даны Брейтоном и др. (1969). Метод Краута может быть обобщен в том смысле, что длЯ любого заданного й мы полагаем или инк = 1, или (кя =!.
В этом случае число делений часто может быть сокращено, если группа, имеющая меньшее число ненулевых элементов, нормализована (Густавсон " др (1970)). Глава б ИСНЛЮЧЕНИЕ ГАУССА- ЖОРДАНА 5.1. Введение Если на каждом шаге гауссова исключения (см, разд. 2.2) исключаются не только ненулевые элементы под диагональю, но и те ненулевые элементы, которые находятся над диагональю, то процесс называется исключением Гаусса в лхордана. Таким образом, заданная матрица коэффициентов А приводится непо.
средственно к единичной матрице в противоположность методу Гаусса, когда матрица А первоначально преобразуется к верхней треугольной (с единичной диагональю) матрице У, которая затем приводится к единичной матрице. В этой главе мы опишем метод исключения Гаусса — Жордана и покажем, каким образом используются матрицы, связанные с различными шагами процесса исключения, для представления обратной матрицы А-' в форме разложения на множители, которая называется мультипликатиеной формой обратной матрицы (РР1).
Мы также покажем, каким образом для данной разреженной матрицы может быть получена разреженная форма РР1. 5.2. Основной метод При исключении Гаусса — Жордана (ОЗЕ) к данной матрице А применяется последовательность эле. ментарных преобразований для приведения ее к единичной матрице У„. Та же последовательность преобразований, примененная к вектору Ь в правой части системы уравнений Ах = Ь, дает решение (Фаддеев и Фаддеева (1960); Фокс (1965)). Пусть Аао обозначает матрицу в начале й-го шага исключения, причем й = 1, 2, ..., и н А(н яи А, а Б.х.
Огненной метод 123 (5.2.1) (5.2.2) где Т,=1„+ (Р— е,) е.' и элементы вектора-столбца Ь<Ю даются в виде а«ьь' 1 ~<и= —,„>, < Ф 1<, и Ь<ьм= —. <и ' ь <и' аьь ахь (5.2.3) Теперь из формулы (5.2.1) и из условий А<в=А и А<"~и=1„имеем Т„... Т,Т,А = 1„, что дает нам мультипликативную форму обратной матрияы (РГ!) в виде А ' = Т„ ... Т,то (5.2.4) Если к концу й-го шага исключения Гаусса — Жордана (О)Е) вектор-столбец "«,ю хранится на месте Ьго столбца матрицы А<"+<! (который в дальнейшем не потребуется), тогда нетривиальные элементы формы РЕ! будут замещать матрицу А при завершении про цесса исключения.
Мультипликативная форма представления обратной матрицы является существенной частью большин; ства программ линейного программирования, где вопрос минимизации заполнения играет значительную Роль (Данциг и Орчард-Хейс (1954); Ларсон (1962); Смит и Орчард-Хейс (1963); Вулф и Катлер (1963); Тьюарсон (1966), (1967а); Орчард-Хейс (1968); Дан"нг н др. (1969); Брейтон и др„ (1969)), В разд. 5.4 "ы Рассмотрим минимизацию заполнения ненулевыми элементами в процессе исключения Гаусса †Жордана.
А<,е«1„. Обозначим (1, 1)-й элемент матрицы А<ю через о<«, Матрица А<ю в своих-первых й — 1 столбцах совпадает с единичной матрицей 1„. На й-м шаге у й столбеп матрицы А<ю преобразуется в вектор ех помощью элементарных преобразований строк. ймеех< Ам+<~=Т А<м ь 1224 Гл. Д Исключение Гаусса — Жердина В случае когда решение системы линейных урез. пений Ах = 5 требуется только для небольшого числа правых частей, нет необходимости хранить РГ1, тзз как каждая матрица преобразования Т„может быть применена также и к правым частям, когда она прн.
меняется к матрице Аск> в соответствии с формулоз (5.2.1). Даже в этом случае для больших разрежен ных матриц очень полезно минимизировать заполне. ние ненулевыми элементами при преобразовании мат. рицы Ам> в матрицу Ам+» в соответствии с формулой (5.2.1). В следующем разделе мы рассмотрим соотношение между элиминативной формой обратной матрицы (ЕГ1), которая была определена в разд. 2.4, и муль.
типликативной формой (РГ1). 5.3. Связь между формами РГ! и ЕГ1 Вспомним из равд. 2.2, что в процессе обратной подстановки метода Гаусса (ОЕ) для матрицы, об. ратной к верхней треугольной матрице У с единичной диагональю, разложение на множители получается путем выбора в качестве главных последовательно рас. положенных элементов диагонали, начиная с нижнего правого угла матрицы. В этом случае заполнения не. нулевыми элементами не может происходить и петра. виальные элементы множителей в разложении об. ратной матрицы У-' получаются только изменениея знаков у тех элементов матрицы У, которые лежат нзл диагональю, Однако для вычисления матрицы У ' тз.
ким способом необходимо, чтобы все строки матрнцн У были известны. Другими словами, необходима ждать завершения процесса прямого гауссова исклю. чения. Другим путем нахождения матрицы У-' является выбор диагональных элементов в качестве' главных, начиная с левого верхнего угла матрицы и двигаясь вниз по диагонали. В этом случае некоторое заполне. ние ненулевыми элементами, вообще говоря, буде~ происходить. Однако на й-м шаге прн любом частном значении й требуются только первые й строк матрицу> цз, Сеазь между формами РР! и ЕР! !25 ( Так как к моментУ завеРшениЯ й-го шага пРЯмого ова исключения первые Й строк матрицы У из- вестнь, иы, то матрица !!-' может быть вычислена в процессе прямого гауссова исключения. Это и есть в точ- „ сти то, что делается при методе исключения Гаус- саджордана (63Е).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
