Разряженные матрицы. Р. Тьюарсон (984138), страница 15
Текст из файла (страница 15)
3. Лоаолнительные метооы минимизации оомети что для правого нижнего угла матрицы справедливо обратное утверждение. Другими словами, значение з„ вообще товоря, уменьшается с увеличением 1 от п — 2р+1 до п. Заметим также, что любые две строки матрицы В, отстоящие друг от друга боле~ чем на ширину ленты 2р+ 1, имеют пересечение, рав ное нулю.
Все изложенное выше может быть следующим образом применено для преобразования произвольной разреженной симметричной матрицы к ленточной форме. Вычислим обычный (не булев) квадрат матрицы В н обозначим его через У. Тогда (1,1)-й элемент матрицы (е' является длиной пересечения (-й строки с 1-й строкой и сумма тз длин пересечений (-й строки со строкамн матрицы В равна т,=е,'вт)т, (3.8.4) где )т есть и-мерный вектор-столбец, все элементы которого единицы, Теперь можно изложить метод в виде следующего алгоритма (Тьюарсон (1971)). 1.
Вычислить обычный квадрат матрицы В и обозначить его через 1ьт и затем найти т; в соответствии с формулой (3.8.4). 2. Вычислить й=шах(~ „", ~ '" '), где т — общее число единиц в матрице В, рыет — максимальное число единиц в одной строке матрицы В. (Замечание. Формула дает оценку снизу для величины р, так как величина (т — и)/2л получена из предположения, что лента является полной, а вели чина (ры„— 1)/2 — из допущения, что строка с максимальным числом элементов может быть переставлена так, что она войдет в число строк /з, указанных на рис.
3.8.4, и не имеет ни одного нуля внутри ленты.) 3. Расположить все т; в порядке возрастания нх величин. Обозначим часть индексов, соответствующих 8.8. Ленточная форма первым 2Р значениям чо через С1, а оставшуюся часть индексов через М1. Разделить группу индексов С1 на две подгруппы (х(% и ЬЕ (северо-западный и юго-восточный углы ленточной матрицы) следующим образом (рис. 3.8.5). Определить тр — ппп;ть ! я С1; если имеют место совпадения, то выбирать тр с минимальным значением р. Отнести р и все индексы ! из С1, для которых ерше~ Ф О, к подгруппе Х%.
Отнести к подгруппе (Х(% все индексы / из С1, для которых е,'Ф'ег Ф О и (ен (х)%. Повторить эту процедуру, "Ут С1 пока в С1 не останется ни одного индекса, который мог бы быть отнесен к И! подгруппе И%. Другими словами, е';Фея — — О для всех ! в (х(% й 4!ф)х)%, но из С1. Этим определяются все индексы для северо-западного ((х(%) уг- С1 ла матрицы. Подобным же образом из оставших- Рис. 3,8.5. Отнесение строки ся индексов группы С1 к одному из углов.
выделить индексы, которые относятся к юго-восточному ЬЕ углу матрицы. Все индексы группы С1, не вошедшие в подгруппы И% н ЬЕ, отнести к группе М1. Расположить строки (н столбцы) в подгруппах Х% и ЯЕ соответственно по возрастающим и убывающим значениям всех ть (Заметим, что всякий раз, когда производятся перестановки строк матрицы В (и А), таким же образом переставляются и столбцы матрицы В (и А), чтобы сохранялась симметрия.) Произвести дополнительные перестановки строк (и столбцов), если требуется, чтосы придать строкам, относящимся к Х% и ЬЕ, анд заштрихованных областей на рис.
3.8.5. Все эти перестановки строк (столбцов) необходимо регистрировать. 4. Отнести каждую из строк группы М1 к одной из подгрупп Х% или ЬЕ следующим образом 1ОВ Гл. 3. Дополнительные методы минимиеаини памяти (рис. 3.8.5). Пусть т' есть а-мерный вектор-столбец, такой, что е()т=1, если 1~ !ч%, и е)т'=0 в противном случае. Тогда вычислить ее=шах,(е1йг)т) для всех ! ~ М1. Отнести р к подгруйпе ХЮ. Повторить эту процедуру, пока приблизительно половина всех строк группы М! не будет отнесена к подгруппе Х'ьЧ.
Записать последовательность, в какой строки из М! отнесены к )ч!%. Таким же способом отнести строки к подгруппе 5Е и записать порядок, в котором онн отнесены к подгруппе ЬЕ. (Замечание. Сумма длин пересечений строки ! е= М1 со строками из подгруппы !Ч)% — это дважды заштрихованная область в северо-восточном углу матрицы на рис. 3.8.5. Ясно, что эта область будет максимальна для строки, смежной с последней строкой из )ч)%.) 5. Перестановки строк на шаге 3 и порядок, в котором строки из М1 относятся к )ч (Ч или 8Е на шаге 4, дают требуемую матрицу перестановок Р, так что матрица В = РВР' будет ленточной матрицей. Существует ряд других подходящих форм для гауссова исключения, но в наши цели не входит описывать в этой главе каждую из них. Многие из этих форм (часть из которых рассматривается в следующем разделе) имеют в своей основе одну из четырех форм ВРР, ВТР, ВОСТР и ВР, описанных в разд. 3.5, 3.6, 3.7 и 3.8.
3.9. Другие подходящие формы На рис. 3.9.1 приведены некоторые другие формы, к которым данная матрица может быть приведена (Тьюарсон (1971)). Диагональная блочная форма является частью односторонне окаймленной диагональной блочной формы (БВВРР) и двусторонне окаймленной диагональной блочной формы (РВВРР) . Формы ВТР и В!чТР являются частями соответственно окаймленной треугольной блочной формы (ВВТР) и окаймленной треугольной ленточной формы (ВВй)ТР). Ленточная матрица связана с односторонне окаймленной ленточной формой (5ВВР) и двусторонне окаймленной ленточной формой (РВВР), З.9. Другие подходящие формы 1О1 Заметим, что возможны также и комбинации различных форм, представленных на рис.
3.9.1,— две из них приведены на рис. 3.9.2 (Дженнингс (1966), (1968)) Матрицы второго типа являются результатом перенуыерации матриц коэффициентов жесткости башенных каркасов. Если матрица В имеет форму БВВРР, тогда в соответствующем строчном графе вершины, связанные ВВВВГ ВВВВГ ВВТГ ВВЧТГ ВВВГ ВВВГ Рнс. З.ВЛ. Некоторые простые желательные формы. с окаймляющими строками, имеют, вообще говоря, ббльшую степень, чем другие вершины. Более того, удаление этих вершин разбивает граф на ряд несвязных подграфов, каждый из которых соответствует отдельному диагональному блоку в матрице В.
В литературе по теории графов присоединенное множество это такое подмножество вершин, что их удаление (и всех связанных с ними ребер) разбивает граф на два или более несвязных подграфа (Майо (1965)). В энергетических системах трансформаторы связи соответствуют точкам присоединения (Рейд (1971, стр, 125)).
Если матрица В имеет форму РВВРР, то вершины, соответствующие окаймляющим строке и столбцу, образуют «присоединенное множество» графа матрицы В. Пусть тг определено формулой 102 Гл. 8. Доаолнительнне мегооы минимизации памяти (3.8.4). Тогда в случаях ЬВВРР и ЬВВР мы замечаем, что все окаймляющие строки имеют, вообще говоря, большие оь чем остальные (так как т; является суммой длин пересечений 1-й строки со всеми строками матрицы В), Этот факт может быть использован для определения окамляющих строк.
В случаях ОВВОР и ОВВР также легко определить строки н столбцы, принадлежащие окаймлению, так как нм Рис. Злх2. Две другие желательные формы. соответствуют, вообще говоря, ббльшие значения ть чем остальным строкам и столбцам (Огбуобири и др. (1970)). В случаях ВВТР н ВВИТР, если переместить окаймляющие строки на самый верх, получим слегка измененные формы ВТР и ВОСТР соответственно (см.
рис. 3.9.3). Очевидно, мы не можем пользоваться методами разд. 3.6 для приведения данной матрицы к модифицированной форме ВТР, представленной на рис. 3.9.3. Однако второй метод, изложенный в разд. 3.7, может быть применен для преобразования данной матрицы к треугольной ленточной форме, приведенной на рис. 3.9.3. За этим могут последовать (всякнй раз, когда это возможно) дальнейшие перестановки в соответствии с теоремой 3.7.13 для получения возможно большего числа уголковых блоков, 3.У. Другие подходящие форма так как первая матрица на рис.
3.9.3 может рассматриваться как форма В5(Тг с уголковыми блоками. Мы описали некоторые простые практические методы обращения с окаймленными матрицами. Они достаточно хороши для матриц, которые могут быть преобразованы к этим формам так, что ненулевые элементы равномерно распределены в заштрихованных областях. В настоящее время нет определенного алгоритма (подобного тем, что даны в разд. 3.5 и 3.6) Рис. 3,9.3. Модифицированные формы ВТР н ВЫТР. для определения строк и (или) столбцов, которые принадлежали бы к окаймлению (Харари 1971 б) в том случае, когда только небольшое число ненулевых элементов составляют это окаймление. Желательно было бы иметь простой практический метод определения наименьшего числа вершин графа (или направленного графа), удаление которых делает граф менее связным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
