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

3.3. Поскольку матрица А симметрична, должна запоминаться только ее нижняя треугольная часть, содержащая элементы, которые лежат на главной диагонали или ниже. Хранение производится с помощью двух массивов: ЧŠ— значений ненулевых элементов и РР— положений диагональных элементов в массиве Л»Е. Для каждой строки в Л»Е хранятся крайний левый ненулевой элемент и все следующие элементы, расположенные справа от него вплоть до диагонального включительно. Поэтому »-я строка матрицы А требует О»+! ячеек для хранения и ЪЕ будет состоять из н 2 (О;+1) элементов. Добавляя и элементов, необхо! ! димых для РР, получим общее требуемое количество н в ~ 9»+ 2п ячеек для хранения А.

Если лента яв! ! ляется полной, т. е. а;, чь 0 для всех ! — 1( О! при !.3, унанаванная форма хранення т — и ! - 1, тогда ) О;= — и требуемый объем памяти т+ Зн будет составлять — ячеек. 2 Проиллюстрируем эту схему хранения на примере матрицы с ненулевыми элементами ап, ам, ааь аеь акь ам, аы, азм аы, азы лежащими на диагонали и под ней. Заметим вначале, что крайние левые ненулевые элементы в третьей, четвертой и пятой строках распрложены во втором столбце.

Поэтому нулевые элементы аы и аы должны также храниться в ЧЕ, Матрица будет запоминаться в виде ЧЕ=(ап, ааь а„, аев азъ аен О, ам, ам, анз, О, а„), РР=(1, 3, 5, 8, 12). Элемент ап исходной матрицы может быть восстановлен по этой схеме следующим образом. Положение ап в ЧЕ определяется значением РР(!) — (! — !), если только РР(!) — (1 — !) = РП(1 — 1). Последнее условие означает, что ам не будет лежать влево от первого ненулевого элемента 1-й строки, иначе ап = 0 и не хранится в ЧЕ. Например, чтобы найти элемент аы в массиве ЧЕ, вычисляем РР (5) — (5 — 3) = 12 — 2 = 10 ) 8 = РР (4) и, следовательно, аы хранится в ЪЕ(10).

Главное преимущество этой схемы упаковки состоит в следующем. Если в процессе вычислений (например, при исключениях по методу Гаусса, гл. 2) создаются дополнительные ненулевые элементы только вправо от крайнего левого элемента каждой строки, то они могут запоминаться в ЧЕ без перемещений всех следующих за ними элементов. Некоторые зимечапил о схемах упаковки Теперь укажем вкратце возможные пути дополнительной экономии памяти для приведенных выше схем упаковки.

Если матрица А симметрична, то хранятся, как в схеме 111, только ненулевые элементы нижней Гл. П Предварительные сведения (или верхней) треугольной ее части, включая диагональ, В связном списке можно объединять две или более записи в блоки последовательно расположенных ячеек. В этом случае каждая запись блока, кроме последней, может состоять из двух, а не из трех ячеек.

Само собой разумеется, что включение или исключение записи становится при такой форме хранения довольно сложным. Если длина (чнсло двоичных разрядов) ячейки па. мяти ЭВМ достаточно велика, то для экономии памяти во всех описанных выше схемах можно хранить в ячейке по два и более индекса строк (или столбцов). Это требует знакомства с программированием на уровне языка машин н, вообще говоря, не является приемлемым при использовании алгоритмических языков высокого уровня, подобных ФОРТРАНУ или АЛГОЛУ.

Во всех схемах упаковки, за исключением схемы ГЧ, описывалось хранение матрицы по столбцам. Во многих приложениях предпочтительнее хранение по строкам. Нет необходимости его описывать, так как оно вполне аналогично хранению по столбцам (это то же самое, что и хранение транспонированной к А матрицы по столбцам). 1А. Масштабирование Матрица А часто связана с системой линейных уравнений Ах = Ь, где х и Ь являются вектор-столбцами и-го порядка. Часто элементы х; и Ь; векторов х и Ь соответственно измеряются в единицах, которые значительно отличаются друг от друга порядком величины. Например, Ьс измеряется в сантиметрах, а Ьа— в километрах, так что в результате первая ст(уока матрицы А и Ь~ значительно больше (в какой-либо норме), чем вторая строка и Ьа.

Положение может быть исправлено, если обе строки сделать в какой-либо норме равными. Для этого обычно рекомендуется строки и столбцы заданной матрицы преобразовать так, чтобы онн были величинами одного порядка. Такое преобразование называется масштабированием. /.4. Масштабирование (1.4.2) Решением (1,4.1) является х=0,(0аАР,) 'Р,Ь, (1.4.3) Как видно, вместо вычисления А-' производится вычисление обращенной масштабированной матрицы 0тАРь Если О/ =/„, то имеет место только масштабирование строк и (1.4.3) будет иметь вид х= (РтА) ' Р,Ь. (1.4,4) 1.5, Библиография и комментарии Ниже приводятся некоторые ссылки на литературу по разреженным матрицам в различных приложениях. а) Линейное программирование: Маркович (1957), Ларсон (1962), Вольф н Катлер (1963), Данциг (1963 а, б), Смит и Орчард-Хейс (1963), Диксон Простой способ масштабирования матрицы А состоит в делении каждой строки на наибольший по абсолютному значению элемент этой строки. Масштабврованию строк может предшествовать масштабирование столбцов, а именно деление каждого столбца матрицы А на наибольший по абсолютному значению элемент этого столбца.

Многие программы задач линейного программирования предусматривают масштабирование, так как полученная в ЭВМ обратная матрица содержит меньшие ошибки округления, если исходная матрица до обращения масштабируется, Мы можем следующим образом описать влияние масштабирования на решение уравнения Ах = Ь. Пусть е, обозначает /-й столбец единичной матрицы /„и-го порядка.

Тогда решение х для Ах = Ь является тем же, что и для РтАР/О~ «= РтЬ, (1.4. 1) где О, и Рз — диагональные матрицы, такие, что е'Р,е = (шах ~ а, ~ ) ', е',Рве/ = (шах(е/АР,е/ !1 '. Гм 1. Предваригеяьньсе сведения (1965), Тьюарсон (1966), (1967а), Орчард-Хейс (1968), Данциг и др. (1969), Орчард-Хейс (1969),Смит (1969), Вулф (1969), Томлин (1970), Бил (1971), Де Бюше (1971), Карре (!971), Форрест н Томлин (1972). б) Структурный анализ: Ливсли (1960 †19), Стьюард (1962), Олвей и Мартин (1965), Дженнингс (1968), Розен (1968), Катхил и Мак-Ки (1969), Мак. Кормик (1969),' Пэлекол (1969), Олвуд (!97!), Катхил (1971), Джордж (1972). в) Теория цепей и систем распределения энергии: Брейнин (1959), Рот (1959), Крон (1963), Сато и Тинни (1963), Тинни и Уокер (1967), Эдельман (!968), Чен (1969), Тинни (1969), Бети и Стьюарт (1971), Бауман (1971), Черчилл (1971), Огбуобири (1971).

г) Численное решение дифференциальных уравнений: Варга (1962), Карре (1966), Лайниджер и Уиллегби (1969), Гир (!971), Ивенс (1972), Гимон и Кинг (1972). д) Теория графов: Басейкер и Саати (1965), Дал. мейдж и Мендельсон (!967), Харари, (1967, 1971 а, б), Беллман и др. (1970). е) Теория'генетики: Фалкерсон и Гросс (1965). ж) Поведенческие науки: Харари (1960), Меримонт (1959), Росс и Харари (1959). 3) Программирование для ЭВМ: Меримонт (1960).

и) Другие области: Ашкенази (1971), Глейзер (1972), Гимон и Кинг (1972). Связные списки описали Маурзер (1968), Кеттлер и Вейл (1969), Огбуобири (1970), Черчилл (1971), Густавсон (1972). Другие схемы хранения дали Джен. нингс (1966), Хименес (1969), Иенсон и Парке (1970), Надинг и Калерт-Уормболд (!970), Берри (1971), Де Бюше (1971), Густавсон (1972), Дженнингс и Тафф (1971). Общее введение к методам разреженности дано Тяпни и Огбуобири (1970), Масштабирование строк (даже если ему предшествует масштабирование столбцов) не является реше. нием проблемы масштабирования в целом.

Для дальнейшего знакомства с вопросами масштабирования, которое кногда называют также уравновешиванием, 1.б. Библиография и комментарии 29 читатель может обратиться к Уилкинсону (1965), Форсайту и Молеру (1967) и Уэстлейку (1968). Более совершенные методы масштабирования рассмотрели Фалкерсон и Вулф (1962), Бауер (1963), Ван-дерСлюис (1969) и Кертис и Рейд (1971 б), В этой книге мы будем заниматься главным образом прямыми методами обращения разреженных матриц.

Непрямые (или итеративные) методы для разреженных матриц не будут описаны, так как они хорошо известны (Варга (1962)). В общих руководствах по численному анализу и в периодической литературе обычно рассматриваются прямые методы обращения для небольших полных матриц. Однако во многих прикладных задачах (например, линейного программирования, структурного анализа, электрических цепей и систем генерирования и распределения энергии) получили широкое развитие и внедрены в программы для ЭВМ прямые методы обращения больших разрежен.

иых матриц: Ливсли (1960 — 1961), Смит и Орчард. Хейс (1963), Диксон (1965), Дженнингс (1968), Данциг и др. (1969), Ли (1969), Густавсон и др, (1970), Берри (1971), Де Бюше (1971), Кантин (197!), Форрест и Томлин (1972). Глава 2 МЕТОД ИСКЛЮЧЕНИЯ ГАУССА 2.1. Введение В этой главе описывается метод исключения Гаус. са для решения систем линейных уравнений.

Мы покажем, каким образом матрицы, связанные с различными стадиями процесса исключения, могут быть использованы для представления в факторизованной форме матрицы, обратной для матрицы коэффициентов линейных уравнений. Доказываются некоторые теоремы, с помощью которых определяются разрежен. ные множители разложения обращенных разреженных матриц.

2.2. Основной метод Наиболее известным методом решения системы уравнений Ах =Ь (2.2,!) (где, как и в гл. 1, х и Ь вЂ” и-мерные векторы-столб. цы, а А — неособенная матрица и-го порядка) является метод исключения Гаусса (Уилкинсон (1965)). Он состоит из двух частей: прямого исключения, в котором с помощью ряда элементарных преобразований (операций над строками) матрица А приводится к верхней треугольной 'матрице У с единичной диагональю, и так называемой обратной подстановки, которая приводит к обращению У.

Прямое гауссово исключение состоит из п шагов. Пусть Аеп обозначает матрицу в начале й-го шага, причем Ап! = А и Ам+и = У. Пусть а!ы являетск элементом Ьй строки и 1-го столбца ((21)-м элемен. том) матрицы'А<"!. Другими словами, пусть а<.">= =е,'Апое1, где е; является Ьм столбцом единичной мат.

2.2. Основной метод рицы т'„гг-го порядка, как уже указывалось в равд. 1.3. 1(ля первых й — 1 столбцов матрица Аро уже имеет форму верхней треугольной матрицы (рис. 2.2.1). На л(ь «-а оаеабец Рнс. 2.2.1. Матраца в начале й-го шага. в-й гшеабец Рнс. 2.2.2. Элементарная матрица на Ь-м шаге.

й-и шаге л-я строка матрицы Ади делится на ее (й, л) -й элемент, умножается на различные коэффициенты и вычитается из всех следующих за ней строк так, чтобы все ненулевые элементы й-го столбца, лежащие ниже й-й строки, становились нулями. Гл. Д Метод исключения Гаусса Получающаяся в результате матрица обозначается через А<»+'1 В матричных обозначениях этот процесс может быть по-другому сформулирован следующим обра.

зом. Прямое гауссово исключение состоит в вычислении А<»+о=7.»А<»>, Й=1,2,..., п, (2.2.2) где элементарная нижняя треугольная матрица (рис. 2.2.2) задается в виде л-» = < „+ (<1<м — е,) е' „ (2.2,3) с элементами вектора-столбца т)<»>, определяемыми следующим образом: Ч<м=о, 1(й, 1 а<»< т<<»»< = <,, <1<<»' = — <»<, <' > й. (2.2А) Таким образом, диагональные элементы матрицы С» равны 'единицам во всех столбцах, за исключением й-го, в котором элементы, лежащие на диагонали н под ней, равны т<)»> ((=й, й+ 1, ..., и).