Разряженные матрицы. Р. Тьюарсон (984138), страница 16
Текст из файла (страница 16)
Опишем теперь метод разрезания Стьюарда (1969) (или удаления дуг направленного графа для разбиения циклов). Он особенно полезен в случаях, когда удаление небольшого числа дуг разбивает большие направленные циклы и соответствующие диагональные блоки в форме ВТг становятся меньше (см. Разд. 3.6). Этот метод практичен только для разрезания небольших блоков. Мы поясним его на примере. Рассмотрим матрицу и ее граф, приведенные на 104 Гм В.
Дополнительные методы минимизации намети рис. 3.9.4. Определим один из наиболее длинных цпк. лов [1, 4,3,6, 5, 1[. Два пути между теми же верши. нами, направленные в одну сторону, не имеющие 7 1 3 С 5 5 Рас, 3,9.4. Матрица и ее направленный граф. 43515  — 1 — Е1 и ! В Е , 'Ь Е , ' — с йсряйек 0 3 е е~ Рис. 3.9.5. Диаграмма шунтирования длинного цикла. общей дуги и не содержащие циклов, называются параллельными. Путь, параллельный дуге в длинном цикле, называется шунтом. На рис.
3.9.4 четыре шунта помечены а, Ь, с и В. Порядок шунта — это длина шунтированного пути в длинном цикле минус длина шунта. Например, дуга с — это [5. 4[, а путь длинного цикла, который она укорачивает, что [5, 1, 4], и, следовательно, порядок дуги с равен 2 — 1 = 1.
Если дуга длинного цикла, имеющая шунт, разрезается, 39. другие подходящие формы 105 то остается цикл, проходящий через шунт, и длина Всего цикла уменьшится на порядок шунта. Длинный цикл разрезается в тех местах, где нет слишком большого числа шунтов, так как шунты тоже подлежат разрезанию. На рис. 3.9.5 дана диаграмма шунтирования длинного цикла графа, приведенного на рнс.
3.9.4. На диаграмме В обозначает начало шунта, а Š— его конец. Очевидно, если разрезать дугу 16, 5], то потребуется разрезать только шунт с), и поэтому такой выбор места разреза является наилучшим. Если дугу !6, 5] и ! Дх х шунт ]3, 4] удалить !вырезать) из направленного ]х х~ ~х х графа на рис. 3 9 4, то вершина 5 становится амиттером, и она номе- ]к] х чается первой вершиной.
Теперь, при удалении дуг В х и !5, !] и 15, 4], становится эмнттером вершина 1 — Рис. 3.9.6. Матрица, связанная она пОмечается вторОй с перемененным направленным вер шиной и так далее. графом. В левом нижнем углу находится Матрица, соотВетстВую алемеит, подлежащий удалению. шая перемеченному графу, представлена на рис.
3.9.6. Она имеет форму ВТЕ, если не считать элемент в нижнем левом углу матрицы, подлежащий удалению. Матрица на рис. 3.9.6 является частным случаем формы ВВТГ, когда окаймляющая группа блоков состоит всего из единственного недиагонального элемен. та. Если в процессе разрезания графа нужно удалить ряд элементов, то строки и столбцы матрицы, содержащие эти элементы, могут быть переставлены так, чтобы они стали последними строками и столбцами и матрица приобрела бы форму ВВТЕ. Теперь покажем, каким образом для форм ВТЕ и ВВТГ могут быть получены элимннативные формы обратных матриц (ЕГ1), 106 Гл. 3. Дополнительные методы минимизации яимяти 3.10. Обратные матрицы для ВТГ н ВВТГ Рассмотрим форму ВВТГ, которая дается форму лой (3.3.1). Пусть все матрицы Ан (1= 1, 2, ..., р) неособенные.
Метод обращения может быть описан следующим алгоритмом (Тьюарсон (1972); Дафф (1972)). 1. Выполнить следующие шаги для т = р — 1, р— — 2,...,2,1: а) Преобразовать матрицу Ла в верхнюю треугольную матрицу 0ы с равными единице диагональными элементами н матрицу Арт в нулевую матрицу с помощью прямого гауссова исключения (ОЕ). Это приведет к заполнению подматриц Атр и Арр.
б) Применить обратную подстановку гауссова исключения для преобразования матрицы Утт в единичную матрицу 7 и матриц Ан в нулевые матрицы для всех 1( т. Это приводит к заполнению всех матриц А;„,1<В 2. Прямым гауссовым исключением преобразовать матрицу Арр' к верхней треугольной матрице Урр, а обратной подстановкой преобразовать матрицу У „ в единичную матрицу 7 и все модифицированные Л „, 1 чы Р, к нУлю.
Очевидно, в этом методе не будет никакого запол- нениЯ матРиц Лть 1( т и т Ф Р. Если задана матрица в форме ВТГ, то для каждого 1 (т' = р, р — 1, ..., 2, 1) выполняются два шага: а) преобразовать матрицу Ан в матрицу Уть б) привести матрицу Уте к единичной матрице 7 н матрицы Ан, 1'( т, к нулю. Ясно, что в этом случае не будет заполнения матриц Ан, 1' = й Обе приведенные выше модификации гауссова исключения легко реализовать, и полученные обратные матрицы в форме ЕГ1 являются разреженными.
В обоих методах могут быть использованы изложенные в этой и предыдущей главах способы уменьшения заполнения при преобразовании матрицы Ан в матрицу Ун. 3.!Л Библиография и комментарии 107 3.11. Библиография и комментарии Интерпретация с помощью теории графов различных подходящих форм матриц, рассмотренных в на.
стоящей главе, дана Харари (1971, а, б). Метод, который аналогичен первому методу равд. 3.7 и минимизнрует2;ф; вместо тахефь предложен Тьюарсоном (1967с). Олвей и Мартин (1965) получили программу, осуществляющую направленный поиск возможных перестановок для определения такой, которая преобразует матрицу к форме ВГ. Программы для ЭВМ по первому и третьему методам равд. 3.8 разработали розен (1968) и Эйкиуз и Утку (1968).
Методы теории графов для гауссова исключения даны Партером (1961) и Роузом (1970б). Эквивалентность гауссова исключения и исключения узлов показана Огбуобирн н др. (1970). Партер (1960) и Меримонт (1969) используют разрезание. Применение методов теории графов для анализа структур и разбиения матриц дано Венке (1964), Ойфингером и др.
(!968), Ойфингером (!970). Хорошая схема хранения матриц различных форм, приведенных на рис. 3.9.2, описана Дженнингсом (1966), (1968). Алгоритм решения для симметричных положительно определенных ленточных матриц дается в работе Кантика (197!). Другой алгоритм для симметричной матрицы дается Иенсеном и Парксом (!970). Разбиение матриц и исключение блоков рассматриваются н работах Джорджа (1972) и Роуза и Банча (1972).
Для нахождения «точек присоединения» можно пользоваться также теорией рассечения (Бэти и Стьюарт (1971)), которая также называется «теорией декомпозиции» в линейном программировании (Данциг н Вулф (!961); Бендере (1962)). Она включает в себя определение матрицы близости узлов с помощью обычных (не булевых) степеней матрицы В.
Элементы матрицы близости узлов затем используются для определения присоединенного множества. Глава 4 ПРЯМОЕ ТРЕУГОЛЬНОЕ РАЗЛОЖЕНИЕ 4.1. Введение В этой главе мы опишем методы представления заданной матрицы А как произведения нижней треугольной матрицы ь' и верхней треугольной матрицы У вида (4.1.1) Нас будет главным образом интересовать вопрос о пригодности этих методов для случая больших разреженных матриц. Эти методы связаны с именами'Краута, Дулитла, Холецкого, Банахевича и других (Уэст- лейк (1968); Уилкинсон (1965)).
Если разложение (4.1.1) известно, то из него следует, что А '=У 'Х '. (4.1.2) Ху=Ь и =у (4.1 8) (4,1.4) соответственно для у н х. Разложение матриц У-' и ь-' иа множители нетрудно определить, так как обе они треугольные матрицы. Поэтому для представления обратной матрицы А-' в факторизованной форме можно применить приведенный выше метод вместо метода, изложенного в гл. 2. Если решение системы уравнений Ах = Ь желательно иметь только для одной правой части, то нет необходимости вычислять обратную матрицу по формуле (4.1.2). В этом случае решение х может быть получено применением обратной подстановки к системам е.е.
Метод Краута 109 Методы, описанные в этой главе, являются по существу модификациями гауссова исключения, изложенного в гл. 2. Они обладают тем преимуществом, что промежуточные редуцированные матрицы А!">, о которых говорилось в гл. 2, не запоминаются, и, кроме того, если скалярные произведения вычисляются с накоплением, эти методы обеспечивают исключительную точность. 4.2. Метод Краута Обозначим (е, 1)-е элементы Е и У соответственно через 1о и пеь Потребуем, чтобы матрица 0 была верх. ней треугольной матрицей с единицами на диагонали, т. е. иее = 1, /г = 1, 2, ..., и. Если допустить, что первые й — 1 строк и столбцов матриц Е и У уже определены (см. рис.
4.2.1), тогда, учитывая формулу (4.1.1) и то, что 1ер=О для Р>1, ире=О для р)й и ие! = 1, имеем е-! аы — — 1!ь+ Е 1<рирм 1>й р что дает е-! 1!ь= ам — Х «рееры ! Ъ й. (4.2.1) р ! Таким образом, й-й столбец матрицы Е теперь известен. Из формулы (4.1.1) и из того, что 1ер = О для Р й, имеем е-! '~!=(ива+ Х 1,ррь 1> й р ! что дает 1> Й, (4.2.2) и теперь известна й-я строка У. Таким образом, мы убедились, что если первые й — 1 строк матрицы 0 и первые й — 1 столбцов матрицы Е известны, то й-я строка матрицы У н й-й столбец матрицы Е могут быть легко вычислены, Первый столбец матрицы Е По Га 4, Прямое треугольное разложение определяется равенствами 1„ = аг„ ! = 1, 2, ..., п.
(4.2.3) Это следует из формулы (4.1.1) и из того, что первым столбцом матрицы У является вектор еь Первую строку матрицы У так же легко найти из формулы (4.1.!) Рис. 4гй1. Схема хранения для метода Краута. и на основании того факта, что первая строка матрицы Е есть !пеп а именно ан им — ! (4.2.4) ! > 1. «-! Если допустить, что для й = 1 сумма 2., (... ) = О, то р формулы (4.2.3) и (4.2.4) являются частными случаями соответственно формул (4.2.1) и (4.2.2).
Принимая во внимание изложенное выше, все строки и столбцы матриц Х и 0 легко могут быть определены. Рис. 4.2.1 наглядно показывает, каким образом хранятся различные матрицы к началу й-го шага метода Краута. Первые й — 1 строк матрицы У вЂ” это [1+ + Уь Уа, Уа), а первые й — 1 столбцов матрицы ь'— 4.2.
Метод Кранта это Е) Заметим, что единичная диагональ матрицы У не хранится. На й-м шаге мы прежде всего используем уравнение (4.2.1) для преобразовании элемента ааа и сеолбца Ам в нетривиальные элементы й-го столбца мвтрицы Е. Имеем А, = А г 11м (4 2.Б) причем 1аа=йаа и 1~+а,а=е(Ааь Затем следует вычисление нетривиальных элементов Й-й строки матрицы У по формуле (4.2.2).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
