Разряженные матрицы. Р. Тьюарсон (984138), страница 9
Текст из файла (страница 9)
3. Дополнительние методи минимиааиии намети Для больших разреженных матриц, хранимых в упакованной форме, это может привести к значительной экономии времени и усилий. Однако значения т'," даваемые формулами (3.2.13) н (3.2.14), были получены на основании вероятностей гипотезы и поэтому являются только аппроксимациями действительных значений всех ф. Для больших разреженных матриц при малых значениях й такая аппроксимация вполне приемлема, но по мере увеличения й она становится все хуже.
Поэтому рекомендуется, если можно, периодически через определенные интервалы вычислять точные значения г'~>, пользуясь соответствующими мат/ рицами Вн. В некоторых случаях можно точно определять все значения г)е~, не затрачивая слишком много труда. Например, если Асо хранится в виде связного списка, описанного в разд. 1.3, то соответствующее значение 'т~тго может быть легко изменено всЯкий Раз, когда в соответствии с формулой (2.5.2) создается новый ненулевой элемент или ненулевой элемент обращается в нуль.
Можно следующим образом суммировать методы этого раздела. Вначале применяем все с!н~, все у<м / l или все А<и', определенные соответственно формулами (3.2.2), (3.2.4) и (3.2.5), для определения матриц Л и Я в формуле (3.2.9). Затем полагаем АП~=Л и используем матрицу Вь связанную с матрицей А01, для вычисления г',", согласно формуле (3.2.2). Положим г<п=г~в и преобразуем матрицу Ано в матрицу Ам.ьн для й =1, 2, ..., п, пользуясь формулами (3.2,11), (3.2.10), (2.5.2), (2.2.3) и (2.5.4). При этом переход от всех значений тФ ко всем соответствующим значениям ге~и+и производится по формулам (3,2.16), (3.2.13) и (3.2.14). Таким путем матрица А преобразуется в некоторую верхнюю треугольную матрицу О = А(п+'>. Пользуясь формулами (3.2.10) и (2.5.2), можно записать З.З.
Формы, подходяп)не для гауссово исключения яли; с учетом формулы (3.2.9), 0= !.„Р„... ЕзР,АО=!.АЯ, где ~=!.„!з„... ~1Рн Поэтому А-' = ОО-'~., что дает формулу (2.5.13) разложения матрицы А-' на множители. В следующем разделе рассматривается, каким образом матрицы Р и Я в формуле (3.2.1) могут быть определены априорно так, чтобы матрица А имела форму, при которой заполнение или отсутствует, или ограничено только определенными частями матрицы Л. 3.3. Формы, подходящие для гауссова исключения Одной из наиболее простых форм, исключающих заполнение, когда в качестве главных выбираются диагональные элементы, является полная ленточная форма, которая определяется следующим образом.
Определение. Матрица А, у которой ап = О при 11 — !'!) 5, называется ленточной матрицей. Если к тому же ап Ф О для всех (! — !(( 5, то она называется полной ленточной матрицей. Величина 25+1 называется шириной ленты'). Отметим, что для симметричной матрицы с переменной локальной шириной ленты, определенной в разд. !.3, имеем = шахеОЬ Если матрица А — полная ленточная матрица н главные элементы выбираются на диагонали начиная с крайнего элемента в верхнем левом углу, тогда из доказательства теоремы 2.5.5 следует, что никакого ') Лвтор называет шириной ленты (ЬапдвЫ)Ь) величину р.
В русской литературе с понятием ширины ленты связывают величину 25+ 1. Прим. перев, 60 Гл. д, Дополнительные методы минимизации намети заполнения не будет, потому что матрица Вд является полной ленточной матрицей, и всякий раз, когда йй='оЦ=1, будет Ь)т'=1.
С другой стороны, если матрица А не является полной, некоторые элементы внутри ленты будут нулями н заполнение ограничивается числом таких элементов внутри ленты. Рассмотрим еще некоторые подходящие формы. Для этого предположим, что путем перестановки строк и столбцов матрицы А по формуле (3.2.1) ее можно привести к матрице А, имеющей следующую форму: Ап Ам ... Аь 1 А1р О Ам ° ° . Аь~-~ Атр О О (3.3.1) Ар нр 1 Ар ьр Ар,, А,р О О А, А, где диагональные подматрицы Ам, 1 = 1, 2, ..., р, являются неособенными матрицами: Если главные элементы выбираются из ненулевых элементов диагональных блоков Ап, начиная с блока Ан, тогда заполнение может иметь место только в тех блоках матрицы (3.3.1), которые не отмечены нулями.
В равд. 3.10 описывается другой порядок выбора главных элементов, который приводит к тому, что отсутствует заполнение даже в матрицах Ан, 1 ( 1, (АР. В свете изложенного желательно было бы определить такие две матрицы перестановок Р и Я, чтобы матрица А в выражении (3.2.1) имела форму (3.3.1). Если матрица А симметричная, то, вообще говоря, является предпочтительным выразить матрицу А также в симметричной форме, так как в этом случае требуется хранить только ненулевые элементы матрицы А, расположенные на главной диагонали и выше нее. Кроме того, в силу теоремы 2.5.19, если диагональные 8.4.
Матрицы и графы 61 элементы' могут быть выбраны в качестве главных (например, если матрица А положительно определенная), то симметрия сохраняется во время процесса исключения и нижняя треугольная часть матрицы не хранится. В этом случае вместо формулы (3.2.1) имеем РАР'=А, и в матрице (3.3.1) подматрицы А;;=0 для всех 1чь1, за исключением г = р или 1 = р. В следуюшем разделе мы опишем некоторые методы для определения таких матриц Р н Я в формулах (3.2.1) и (3,3.2), которые приводят к различным подходящим формам матрицы,А, частично представленным матрицей (3.3.1). При рассмотрении этих методов нам потребуются некоторые простые понятия теории графов, которые также приведены в следующем разделе.
Дополнительные подробности читатель может найти в работах Басейкера н Саати (1965), Харари (1969), Беллмана и др. (1970). ЗА. Матрицы и графы Пусть Ьи обозначает (1,1)-й элемент матрицы В, полученной в результате замещения единицей каждого ненулевого элемента матрицы А. Приведем в соответствие с матрицей В помеченный граф 11, поме-' ченный направленный граф Гго, помеченньгй двудольный граф Йв, помеченный строчной граф Ггп и помеченный столбцовый граф йс согласно следующим определениям. Определения Помеченный граф И является набором из и веригин, помеченных 1, 2.
.. п, и та ребер. Говорят, что существует ребро (р,у), соединяюшее вершину р с другой вершиной д, если или Ь„, или Ьар (или оба) равны единице. Отсюда следует, что та равно общему числу ненулевых элементов матрицы В+В', расположенных над диагональю. би Гл. 3. Лололнительные методы минимиэоции нимнти Помеченный направленный граф !ло явйяется набором из и вершин, помеченных 1, 2, ..., и, и та дуг.
Говорят, что существует дуга (р, д] от вершины р к другой вершине д тогда и только тогда, когда бр —— 1. Таким образом, то равно общему числу недиагональных элементов матрицы В. Помеченный двудольный граф !лв состоит из двух различных наборов вершин Я н С, причем каждый набор содержит и элементов, помеченных 1, 2, ..., и, б, (~ ЯД~) (Дг) (д) Рис. Злв!, Помеченные графы, соотаетстиуиицие матрице. и из набора в т ребер, соединяющих вершины К н С. Ребро !р, д) с вершиной р из набора В и вершиной д из набора С существует тогда и только тогда, когда (эрч — 1. Таким образом, т является общим числом ненулевых элементов матрицы В. , Помеченный строчный граф Йи и помеченный столбцовый граф !!с являются помеченными графами соответственно матриц В«В' и В'«В, где символ « означает, что при вычислении скалярных произведений векторов в этих матричных произведениях следует применять только булеза сложение Я, т.
е, полагать 1 9 1 = 1. Так как и матрица В«В', и матрица В'« В симметричны, то ти (число ребер в а!и) и тс (число ребер в !!с) равны общему числу единиц, расположенных над диагоналями соответственно матриц В«В' и В'«В. На рис. 3.4.1 приведены матрица и соответствующие ей графы (), (!и, (!и, йи и Йс.
Если строки и столбцы матрицы В переставлены так, что все ее диагональные элементы остаются на З.4. Матрицы и графы аз диагонали, а именно когда РВР'=В (3.4.1) (Р— матрица перестановок), то единственное изменение в соответствующих графах (г и (го будет заключаться в том, что вершины будут помечены подругому — во всем остальном эти графы остаются без изменений. Применение различных матриц для перестановки строк и столбцов матрицы В, когда РВЯ= В (3.4.2) (Р и Я матрицы перестановок), оставляет граф (гв без изменений, за исключением перенумерации вершин вВ и С. Перестановки строк матрицы В с помощью матрицы перестановок Р приводят к перенумерации вершин в графе ьгп, а перестановка столбцов с помощью матрицы перестановок Я приводит к перенумерации вершин графа ьгс.
Из формулы (3.4.2) имеем РВ и В'Р' = В и В' и Я'В' г ВЯ = В' и В, (3.4.3) и, следовательно, исходя из определений (га и (ге, можно заключить, что матрицы Я и Р в формуле (3.4.2) не оказывают никакого влияния соответственно на графы йп и йс. Если вершины графов (г, (го, (гв, (гп и Ис не имею~ меток, тогда в их названиях слово помеченный опускается и они называются соответственно г)таф, направленный граф, двудольный граф, строчньгй граф и столбцовый граф. Так, матрицам В и В в формуле (3.4.1) соответствуют один и тот же граф, направлен. ный граф, строчный граф и столбцовый граф.
Мат. рицы В и В в формуле (3.4.2) имеют одинаковый двудольный граф, строчный граф и столбцовый граф Инвариантность графов, направленных графов, двудольных графов, строчных графов и столбцовых графов к перестановкам строк и столбцов делают их особенно полезными при исследовании заполнения и при 64 Гл. 3. Вополкительньсе методы минимизации памяти опрсделении подходящих форм для гауссова исключения.
Нам потребуются некоторые дополнительные определения для этих целей. Онн относятся к графам й, Йо, йя и йо, но не к графу йз. Дополнительные определения для графа Йз будут даны позже. Определения Вершины р и а, соединенные ребром в графах Й, йя или Йс или дугой в графе Йо, называются смежными вершинами. Если существует подмножество различных вершин ос, оь ..., осс, оь+с, таких, что для с = 1, 2, ..., а вершины ос и о;+с являются смежными, та говоРЯт, что веРшины ос и осс+с свЯзаньс пУтем 1ос, оь ., о„+с) длиною о в графах й, йя нли йс или направленным путем длиною о в графе йо. Если в пути (оь оз, ..., очтс) начальная вершина ос та же, что и конечная вершина о +„то говорят, что путь является циклом длиною о в графах й, йя или йс или направленным циклом в графе йо длиною о.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
