Разряженные матрицы. Р. Тьюарсон (984138), страница 26
Текст из файла (страница 26)
рой йга! даются соотношениями (8.2.5) и Й~~! — фориУ' лой (8,2АО). Рассмотрим, каким образом столбец матрицы А скажем столбец да„заменить столбцом и,. Легка проверить, что Га,б,Т,О 1.„... 1!, (8.2.П) где матрица у'а'а' получена из матрицы уга путе» (а! замены ее е1;й строки и а,-го столбца соответственаз е'„О,А'"+ пе = (е„' + вге!) Уе = =е'е =О, 1~д, так как Уа+! ... У„ преобразует последние п — г столбцов матрицы У в соответствующие столбца единичной матрицы 1, (см. равд. 2,2). Кроме того, так как а!ба —— ег, 1чь д, МатРРца Ого заданнаЯ фоРмУ. лой (8.2.9), является желаемой матрицей„которая при. водит все недиагоиальные элементы д-й строки мат рицы А!"+'! к нулю, а остальные строки сохраняет без изменений. Пусть 169 В.З. Метод разбиения Крона „а ее, и ее„а матрицы Тр, и (ур, получены из матрнцы Те(1е1.„...
Е,А тем же способом, каким матрицы Т, и (7р получаются из Е„... Е,А. Нет необходимости преобразовывать д-й столбец матрицы ((„Аы ~ к единичному вектору е, если запомнить, что ври обращении матрицы О,А'"+и ее е1-й столбец должен быть сперва преобразован к единичному вектору (Форрест и Томлнн (1972)). В этом случае матрицы Те в Т„в формуле (8.2.11) отсутствуют. Однако при обращении матрицы (7'е'ез д-й и д,-й столбцы (вначале столбец с меньшим индексом) должны быть приведены х единичным векторам ранее, чем другие столбцы матрицы. 8.3.
Метод разбиения Крона Пусть К, Е и С обозначают матрацы соответственно размеров пХ», гХг и г Х и и А=А+ КЕС. Тогда легко проверить непосредственным умножением, что А '=(7„— А 'КЕ(7,+СА 'КЕ) С1А '. (83,1) Если матрица А-' может быть представлена в виде разложения на множители, то матрица А — ' может быть вычислена следующим образом: 1. Вычислить матрицу У = А — 'КЕ размеров и Х г.
2. Решить уравнение (7, + СУ)'Л' = У' относительно матрицы Л' размеров г Х и. 3, Вычислить А-' = (1„— ЕС)А-'. Для хранения А-' нам требуется хранить только матрицы 2, С и А-'. Мы теперь покажем, что первый метод предыдущего параграфа является частным случаем метода Крона. Если К=А — а, Е=! и С=е', е' то матрица, которая умножается справа на матрицу А-' в уравнении (8.3.!), если принять во внимание 170 Гз. а. Изменение оазиса и разные волросм соотношения (8.2.3) и (8.2.4), равна -1 -1 7„— А (бв — а,) Г1+ е,А (ае — ае)1 ее= =ӄ— (б~"+и — е,)[1+е,'(а'„л+и — е,)1 'е,'= =7„— (д"'+и — е,)~й~ вп) 'е' =Т~, Таким образом, уравнение (8.3.1) становится такая же, как и уравнение (8.2.2).
В следующем разделе мы покажем, каким образом матрицы типа (8.2.9) могут быть использованы для представления матрицы А-' в факторизованноз форме (Цолленкопф (1971)). 8.4. Бифакторизация Матрица (7, полученная в конце прямого гауссова исключения в равд. 2.2, может быть преобразована в единичную матрицу.)„с помощью элементарных опе.
раций над столбцами, таких, что И7,й, ... 0„,=7„. где Цз>=О, 1<й, и Цм = — иы, 1) й. (8.4,3) Из формулы (8.4.1) имеем (О,, О„,)0=7„, откуда, принимая во внимание формулы (2.2.6) а (2.2.7), получаем, что й, ... Ол,г.л ... 7.,А=7„ В этой формуле матрица Ол для й = 1, 2, ..., п — 1 преобразует Ью строку матрицы Уй, ... й, в е', путем вычитания умноженного на различные коэффи.циенты й-го столбца матрицы И7, ...
Ои и который равен е», из последующих столбцов. Очевидно, все ос. тальные строки матрицы И/, ... Уз, остаются без изменений и последние а — л строк такие же, как в у матрицы К Позтому матрица Ол имеет вид йе —— 1„+ еД' ', (8,4.2) 171 8.5. Библиография и комментарии а, следовательно, =й, ... й„,7.„... Бо (8.4.4) Так как матрица 41'+н определяется формулами (2.2.2), (2.2.3) и (2.2.4), а матрица У вЂ” формулами (2 2.6) н (2.2.7), то первые А строк обеих матриц совпадают. Из этого условия и из соотношений (8.4.2) и (8.4.3) следует, что матрица Ь» может быть вычислена, как только будет известна матрица А12+1!.
Другими словами, все матрицы 7.2 и все матрицы (72 могут быть вычислены в следующем порядке: 7'1~ (г 1~ л 2 (' 2~ ' ' ' г г а 1(7я — 1г г а Обратная подстановка, которая рассматривалась в р азд. 2.2, здесь отсутствует. 8.6. Библиография и комментарии Первый метод, описанный в равд. 8.2, хорошо известен в линейном программировании, если «базисная» обратная матрица хранится в мультипликативной форме (Данциг (1963а)).
Схемы упаковки для хранения мультнпликативной формы обратной матрицы (РР1) даются Смитом (!969) и Де-Вюше (1971). Э21иминативная форма обратной матрицы (ЕР1), которая требуется для второго и третьего методов, впервые рекомендовалась 1'!арковичем (1957) и позднее Данцигом (1963б) для специальных структур «лестничных» матриц. Данциг и др. (1969) показали превосходство формы ЕР! над формой РР1 для матриц общего типа в линейном программировании с точки зрения скорости, точности вычисления обратной матрицы и ее разреженности.
Данциг (1963б) для своего «лестничного» алгоритма исследовал изменеяие формы ЕР1, при котором сохранялась особая структура множителей, Бартельс и Голуб (!969) предложили треугольную схему изменений, которая имеет определенные желаемые свойства. Однако Форрест и Томлпн (1972) отметили, что возникают некоторые прак. тпческие затруднения при использовании этой схемы 172 Гл. З.
Изменение базиса и разные вопросы для разреженных матриц больших размеров. Третнк метод равд. 8.2, предложенный Брейтоном и др. (1969) и примененный и развитый Томлиным (!970) и Фор. рестом и Томлиным (!972) в линейном программнро. ванин, признан, по-видимому, наиболее пригодным для решения задач атой области с разреженными матра. цами больших размеров. Этот метод используется з настоящее время для решения реальных практических задач линейного программирования (Форрест и Том. лин (1972)). Если сравнить первый и второй методы равд. 8.2, то, принимая во внимание соотношения (8.2.1)— (8.2.4) и (8.2.5) — (8.2.7), мы можем заключить, что не только вычисление матрицы 7, в первом методе более трудоемко, ио и сама матрица имеет тенденцию быть более плотной, чем матрица 7в во втором методе. Кроме того, во втором методе матрица У замещается матрицей У в отличие от первого метода, в котором матрица 7 становится дополнительным множителеи в разложении Л-'.
Таким образом, второй метод, во. обще говоря, лучше первого. В работах Шуберта (!970) и Бройдена (197!) рассматривается выбор коррекций ранга 1 для разреженных матриц при решении нелинейных разреженных систем методами квазиньютоновского типа, при котором результирующая матрица тоже разрежена, но представляет собой лучшее приближение для якобиана. Метод Крона (Крон (1963)) описан также Ротом (1959) и Спиллерсом (1968).
.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
