Разряженные матрицы. Р. Тьюарсон, страница 13

Пусть Р и Я являются такими матрицами перестановок, что В =РВЯ, (3.7.2) 84 Гл. 8. Лояояиитеяьиые методы мииимитации аамяти причем с-я строка и 1сй столбец матрицы В становятся соответственно р;-й строкой и сь,-м столбцом матрицы В. Нашей задачей является определение таких-матриц перестановок Р и Я, которые минимизируют шах сгс, где срс — расстояние от главной диагонали до крайнего левого ненулевого элемента рс-й строки матрицы В. Заметим, что фс О в том случае, когда нет ни одного ненулевого элемента левее диагонали в рс-й строке матрицы В.

Эта задача может быть решена следующим образом (Чень (1972) ). Пусть ненулевые элементы с-й строки матрицы В расположены в 1;„-ых столбцах, ес = 1, 2, ..., ть где т,— общее число ненулевых элементов с-й строки матрицы В. Если крайний левый ненулевой элемент р,-й строки матрицы В лежит в рс„-м столбце, то и для всех рс„, не лежащих справа от р,-го столбца, выполняется условие р,+ р ~срс.

Если мы пред!о пишем, чтобы чсс- О для всех 1, тогда для любого ненулевого элемента вправо от диагонали, скажем лежащего в р -м столбце, будет ссс р,— р <О, так как р,<сь, . сс и Поэтому имеем Рс ссс ич тс для всех а Учитывая изложенное выше, можно следующим абразом формулировать задачу: Соответственно всем значениям Оп =1 найти такие целые рь р; и срс, которые минимизируют шах фс о.7.

Треугольная ленточная форма при следующих ограничениях; 1 ~» Р!, р! ~ а; 0( чр! ( а — 1, (3.7,4) Р,— р! — чуг(0; а=1, 2, ..., г, (3.7.6) !! Р! Ф Рь И! Ф Р! длЯ !' Ф 1'.. (3.7.6) Это есть за(ьача Чебышева при наличии ограничений, которая мо ет быть выражена как задача целочисленного прог ммирования (Рабинович (1968)) и затем решена обйчным способом (Данциг (1963 а)).

Второй метод йреобразоваиия матрицы В к форме В)ч' Тл". Этот метод основан на использовании мер для строк и столбцов, полученных из вероятностных соображений. Метод не минимизирует Р, но приводит к величине, достаточно мало отличающейся от минимума. Однако он намного проще первого метода, данного уравнениями с (3.7.3) по (3.7.6). Меры строк и столбцов, используемые в этом методе для преобразования матрицы В к форме ВАХТЕ, получаются следующим образом. Пусть г =г!го, с = с">, где ги! и с!н определены уравненидми (3.2.2), причем В! = В. Пусть А» множество всех столбцов в г-й строке матрицы В, для которых бм = 1; положим г(! = я' е! (3.7.7) 7оя! Для дальнейшего рассмотрения предположим, что матрица В уже приведена к форме В()ТР и единицы в области 1') ! — Р распределены случайным образом так, что каждый элемент этой области имеет одинаковую вероятность оказаться ненулевым. Пусть Е(6) обозначает математическое ожидание 6, Тогда все Е(г;) будут, вообще говоря, уменьшаться с увеличением ! от 1 до и.

С другой стороны, Е(о!) будут, вообще говоря, возрастать с увеличением 1. В соответствии с формулой (3.7.7) для данного ! среднее зна. чение всех с; при 1'енЛ! равно А/г!. Нетрудно 86 Гл. 3, дапалпительиме метадье минимизации памяти обнаружить, что величины Е(е(,/«;), вообще говоря, возрастают с увеличением Е Для заданной 1-й строки стандартное отклонение н; для сг при 1' ~Ле имеет вид ~Е (Х ~)* !ела Ль «то с учетом формулы (3,7.7) дает ХВ 1 ~ Ле.

(3.7.8) Мт — — «, + 6 ( — „' ) + фпь (3,7.9) где 6 и ф — некоторые числа, выбранные таким образом, чтобы величины «е, 6(«;/е(е) и фпт были одного порядка. Очевидно, все Е(Мт) будут,,как правило, уменьшаться с увеличением ~'. Меры Я; для,столбцов могут быть рпределены по такой же формуле (3.7.9), как и Мь ~'именно Мг=сг+ 6~ ~ )+ фйи (3.7.!О) Фг где е7; определяется подобно е(е в формуле (3.7.7) следующим образом: А=1«; (3.7.11) для всех значений Е при которых Ьн = 1, а йг даются следующим уравнением, похожим на уравнеш1е Принимая во внимание допущения относительно характеристик матрицы В, которые были сделаны нами в начале настоящего рассмотрения, нетрудно видеть, что математические ожидания и; будут, как правило, ' уменьшаться с увеличением Е Ранее в нашем рассмотрении мы также видели, что с увеличением ! все Е(«,) и все Е(«Щ), вообще говоря, уменьшаются.

Поэтому разумная мера Мь соответствующая 1-й строке, которая учитывает все три величины «е, и; и «;/Ит, может быть взята в виде 8.7, Треугольная лентонная форма 87 (3.7.8): (3.7.12) для всех значений 1, при которых Ьы = 1. Величины Е(/3г) будут, вообще говоря, возрастать с увеличением 1. Выше мы 'видели, что если матрица В имеет достаточно хорошукь форму ВОСТР, то с возрастанием ( и / все Е(М;) уменьшаются, в то время как все Е(Я;) увеличиваются. Теперь предположим, что матрица В является некоторой разреженной матрицей, не обязательно в форме ВЬ(ТР, со случайно распределенными ненулевыми элементами. Если вычислить все М; и все Я; для такой матрицы В и затем упорядочить ее строки по нисходящим значениям всех Ма а столбцы по возрастающим значениям всех Ягэ то можно ожидать, что форма преобразованной матрицы В будет достаточно хорошо приближаться к ВОСТР.

Нам еще предстоит определить значения Ь и ьр в (3.7.9) и (3.7.10) в случае произвольной разреженной матрицы В (ненулевые элементы матрицы В случайным образом распределены по всей матрице). На практике нами найдено, что, по-видимому, вполне удовлетворительные результаты получаются, если принять Ь = та/по и ф = 2 (т — общее число ненулевых элементов матрицы В) (Тьюарсон (1967с)). Эвристическое обоснование такого выбора значений Ь н ф может быть получено, если молчаливо предположить, что для всей матрицы В Е(гь) м Е(с~) ж т/и, Е (А) ~ Е (Й~) ж Е (гг) Е (с , )м т /п, Е(Я = Е(г,)/Е (Ы,) 2пг = Е (с1) — гп1п с1 88 Гл. 8. Дополнительные методы минимизации памяти для всех значений 1', при которых Ьп = 1.

Таким об. разом, и поэтому ф=2 и сь Ь= нт. й, =Рь-(1,— 1,), что, если учесть, что С,>т„означает рь <Рй (3.7,14) В некоторых случаях, после того как матрица В преобразована к форме ВАХТЕ, можно осуществить дополнительные перестановки строк для создания под диагональю треугольных уголков. Треугольные уголки определяются следующим образом. Если в матрице В элементы Ьц — — О, когда 1) р, и ! < а, или 1> р, и а,(1(оь причем д,(~ (Р1 < Рт и ч1 < др-~~ рт, то треугольник с вершинами (Рь %), (Рь %) и (рь дг) называется треугольным уголком (см. рис. 3.7.1).

Если р, =о, и р,=а, то треугольный уголок является половиной диагонального блока. Вспомним определение рь данное формулами (3.7.1), и тот факт, что тахь рь ) р для всех матриц, полученных из В перестановками строк и столбцов. Пусть матрица В имеет форму ВХТг и Л,обозначает непустое множество индексов 1 строк, д я которых р; = р. Имеем следующую теорему. Теорема 3.7.13. Если матрица В имеет форму В1МТГ и р, — р, >с,— 1, для некоторьсх (г ) (ь то или (ь не принадлежит множеству Л, или Л включает йо меньшей мере еще один (кроме (г) индекс строки. Доказательство.

Переставим (ию и (,-ю строки матрицы В и обозначим новые значения (), и б, соответственно через р, и р,. Тогда 3.7. Треугольная ленточная форма 89 Также Рь=йт,+(; — 2,), что, учитывая неравенство рт — р, ) г,— го дает ()т, < Рь (3.7.!5) Если бы 22 был единственным элементом множества Л„, то из неравенств (3.7.14) и (3.7.15) ясно, что мы уменьшили значение р. Это невозможно, поскольку мы предположили, что матрица имеет форму ВАХТЕ, Поэтому или 22 не принадлежит множеству Л, или если оно ему принадлежит, то в множестве Л имеется по меньшей мере один индекс другой строки, чтобы сохранить значение р.

Этим завершается доказательство теоремы. Эта теорема может быть применена для перестановок строк матрицы В до тех пор, пока для всех 12)й Рт Рт н 12 юп К этому моменту вычислений в матрице может появиться некоторое количество треугольных уголков, потому что всякий раз, когда 21 с. (2 и йт — р, =г',-г„ (3.7.16) для всех 1,(2 12 справедливо равенствойт — гг= =22 — й Если ря и р, являются максимумом й минимумом значений соответственно (2 и гь для которых равенство (3.7.16) верно, и крайние левые единицы в рг-й и (ря+1)-й строках находятся соответственно в дкм и (де+ 1)-м столбцах, то треугольник с вершинами (род,), (р2,42) и (ря,дг) является треугольным уголком (см. рис.

3.7.1). Поэтому мы можем применить методы настоящего .раздела, чтобы преобразовать матрицу В к форме ВХТг, а затем, переставляя строки, получить под диагональю треугольные уголки в таком количестве, в каком это возможно. Если имеется один или несколько треугольных уголков, для которых р, = д~ и ря — — д„то матрица В имеет форму ВТГ, как показано на рис. 3.7.2.

Все элементы, расположенные на границе заштрихованной области под 90 Гл. 8. дополнительныв метоВы минимааации памхти диагональю, равны единицам, за исключением тех элементов, которые расположены на горизонтальных участках границы этой области. Все другие элементы заштрихованной области матрицы и элементы, расположенные на горизонтальных участках границы, могут быть и единицами, и нулями. Все элементы, ут Рнс. 3,73. Треугольный уголок. Рнс. 3.7ХЬ Треугольная блоч- ная форма. лежащие в незаштрихованной области матрицы, яв. ляются нулями. Пунктиром указаны дцагональные блоки.

Заключим этот раздел замечанием, что упомянутая выше перестановка строк может бьрь применена даже в тех случаях, когда матрица р'имеет форму, только приближающуюся к форме ВХТг. В этом случае гпахт рв может, согласно теореме 3.7.13, уменьшаться, н мы не только создаем треугольные уголки, но в определенных случаях ближе приближаемся к форме ВМТг'. 3.8. Ленточная форма Во многих приложениях матрица А является симметричной и положительно определенной, и поэтому в целях сохранения симметрии обычно предпочтительней выбирать главные элементы на диаго- З.д Ленточная форма 91 наля Согласно теореме 2.5.19, это позволит хранить тько ненулевые элементы матрицы, расположенные иад диагональю. Для преобразования матрицы А к подходящей для гауссова исключения форме в этом случае производятся одинаковые перестановки строк „столбцов.

Это можно себе представить как перестановку диагональных элементов матрицы А, Такая перестановка описывается уравнениями (3.3.2) и РВР' = В. (3,8.!) Если положить (тт г ф, ч1ч (г, (3.8.2) где 1 и т1е — индексы элемента йч ЯвлЯющегосЯ крайней левой единицей 1-й строки матрицы В, то нашей целью будет определение минимальной ширины ленты 2р+ 1 и матрицы перестановок Р, таких, что и= гп1пгпах ~о (3.8.3) т Эта задача может быть выражена как задача Чебышева аналогично тому, что изложено в предыдущем параграфе для первого метода преобразования матрицы В к форме В(чТГч Такую постановку задачи мы здесь описывать не будем, так как она обычно не годится для практических целей. Ниже излагаются четыре практических метода перестановок строк и столбцов матрицы, преобразующих ее к ленточной форме (ВР).