Прямые методы для разреженных матриц. О. Эстербю, З.Златев (984134), страница 7
Текст из файла (страница 7)
Например, если мы знаем, что матрица очень разрежена и остается таковой '>, то следует предпочесть СВЯЗНЫЕ СПИСКИ уПорЯДОЧЕННЫМ. Связные списки используются программой МА18 114), а упорядоченные списки — программами МА28 ~171 и И2М 197, 1021. ' Таблица 2.16. Зависимость чнсла сборок мусора н времени счета от свободного пространства. Показаны результаты двух серий вкспернментов с тестовымн матрицами класса Г2; п =100, МЕ =1110, ХМ = СС11ХТ+ за, Смысл барьера Т разънсняетсн в гл. 4. 3.1. Для ч880 йерестйВлять стрОки и стОлбяыР В ходе гауссова исключения необходимо обеспечить выполнение неравенства аф Ф О, так как мы должны делить на это число, При работе с плотными матрицами строки и/или столбцы переставляют обычно таким Образом, чтобы элемент аф был не только отличен от нуля, но и имел наибольший модуль в Е-м столбце А»„либо в Ы-Й строке А»„либо во всей этой подматрице.
При работе с разреженными матрицами хотелось бы ослабить это ограничение, потому что, совершая перестановки строк и столбцов, мы имеем и другую цель: минимизацию заполнении. Выберем поэтому вещественное число ц =.- 1 и будем требовать лишь выполнения одного из следующих ниже условий: ц ~ аф ~ ~ ~аф ~, 1 = К + 1 (1) и, (1.1) п~аф~~~аф~, 1=К+ 1(1)п, (1.2) ц~аф~~~аф1, 1, 1=1~(1)п. (1.3) Они отвечают соответственно стратегии частичного выбора главного элемента по столбцу (переставляются строки), стратегии частичного выбора по строке (переставляются столбцы) и стратегии полного выбора.
По соображениям численной устойчивости и желательно выбирать малым. Если Обозначить через 1»»~ максимальный модуль элемента в А~'», то для частичного выбора справедливо неравенство Величина 1», входит в априорные оценки 1651 величины элементов матрицы возмущения Е в (1.1.10), которую мы хотели бы сд~лать по воз~ожнос~и малой.
Не следует, однако, чересчур опасаться использовать не- скОлькО большие значения и, причем по ряду причин, ХАЯ для матриц специальной структуры оценка (1А) может достигаться ~107), для матриц, Встречающихся на практике, Она не реалистична, (В противном случае даже и = 1 приводило бы при бОльших п к катастрОфе.) Для разреженных матриц и в показателе (см, (1.4) ) нужно заменить числом ненулевых элементов в столбце 135~ — и даже такая оценка все еще не реалистична. И наконец, заметим, что в процессе исключения можно вычислять подлинные значения Ь~, сравнивая их с некоторым «коэффициентом безопасности». Тем самым мы будбм своевременно предупреждены„если рост элементов слиш- КОМ ВЕЛИК, Для полного выбора можно получить значительно лучшую оценку, чем (1.4), но и она пессимистична и неправдоподобна ',1104, 107). Работа, связанная с проверкой на каждом шаге всех элементов Ак, слишком велика и в общем случае не компенсируется большей устойчивостью или точностью резуль- татОВ.
В дос~аточной мере робастную и надежную программу можно получить на основе частичного выбора, если контролировать рост элементов в А<"> и проверять величину главных элементов с целью выявления Возможной почти вырождениости А. Замечание 3.1. Имеются примеры почти вырожденных матриц, для которых ни Один ~лав~ыЙ зле~~~~ не буде* мал 1107).
Подобные патологические случаи не будут обнару- ЖЕНЫ '>. В дальнейшем мы предполагаем, что и 1. Это дает некоторый произвол в выборе главного элемента, которым мы воспользуемся для минимизации заполнения. Мы не станем пытаться строить стратегию, ведущую к наименьшему возможному заполнению в процессе исключения в целом. Это с необходимостью потребовало бы очень обширного и дорогостоящего поиска, что абсолютно не реалистично, Мы даже не будем стараться найти элемент, дающий наименьшее запол~е~~е на шаге, ~о~~рый с~Й~~~ ~а~~нается.
Во-первых, такая стратегия выбора не обязательно соответствует наименьшему глобальному заполнению; во-вторых, поиск все еще будет довольно дорогим. Вместо этого мы обобщим и улучшим стратегию, впервые предложенную в 154~; стратегию, удобную в реализации и порожда~ощую заполнение, возможно, и не минимальное„но достаточно малое„для того чтобы процедура в целом была эффективна. 8.2. Стратегия Марковииа Предположим, что первые 1 — 1 шагов гауссова исключения уже закончены„и мы должны найти 1~-Й главный элемент. Пусть г (1, 1) ОбОзначает число ненулевых элементоВ В 1-й строке Л~, а с(1, 1) — число ненулевых элементов в ~-м'столбце Л~. Напомним, что Л~ определена в гл. 1 как нижняя угловая подматрица А~'> порядка и — К+ 1; она называется ~активной частью» матрипы А~"~.
Ее строки (столбцы) суть активные части строк (столбцов) А~">. Определение 3.2. Ценой Марковица элемента ап,.'> называется число Мцк=(г(1, 1) — 1)(с(~, 1) — 1), (1, 1= 1~(1) п). (2.1) Цена Мцк равна числу элементов, изменяющих значение при переходе от Аоо к А~"+'>, если главным Выбран элемент а~~); Она является Верхней Границей для размера заполнения, ВОзникающего при выборе а®. Положим М~ = пи'и (М;11, ~ 1, 1 = 1~ (1) и), (2.2) СтратеГия МаркОВица В ее ОриГинальном Варианте состоит В том, чтО на каждом ШЯГе к за ГлаВный принимается эле~ент с ц~ной Марковица М~. Это не Об~зате~ь~о ~значае~, что мы получим минимум заполнения на 1~-м шяГе; ОднакО находить цсны МаркОВица значительно прОще, чем Вычислять для каждого элемента Л~ величину порождаемого им заполнения; практически же результаты почти столь же хороши (см.
численные эксперименты В 167~). Стратегия Марковица имеет (по меньшей мере) два недостатка: 1. Просмотр все еще велик — все элементы Ак. 2. Мы можем натолкнуться на численную неустойчивость. Чтобы ограничить просмотр, авторы МА18 114) предусмотрели упорядочение строк и столбцов по возрастанию числа ненулевых элементов, что часто позволяет довольно быстро закончить поиск (см. ~ 3.5). Недостаток 2 связан с тем обстоятельством, что, если в качестве главных будут выбраны очень малые элементы, это может иметь разрушительные последствия для численной значимости результатов.
Отсюда следует, что наша стратегия должна быть компромиссом между требованиями максимальной устойчивости и минимального заполнения. 8.3. 0606щВиййя схротеГия МЙРКОВицй (ОМВ) Ч~~бы процесс был Чис~~~~о ус~ой~ивы~, мы не буде~ допускат~ на роль ~~ЯВны~ Очень малые элементы. С этой Целью введем коэффициент устойчивости и - 1, о котором Замечание 3.5. Стратегия Марковица в оригинальном варианте соответствует ЯМБ с и = оо и р = и, И В опубликованных программах использовались или рекомендОвались различньи значениЯ и и' р — см. табл. 3.1, где сокращение ирек,и означает, что данное значение рекомендуется, на не является обязательным.
Таблица 3.1. Используемые или рекомендуемые значении а и р и различных программах Автор(ы) Нужно отметить, что параметры ц и р в программе У12М те же, что и в ЗЯ.ЕЬТ (см, 1102~). Чтобы сравнить последствия выбора очень малых, соотВетственно больших з~а~ений р, мы провели эксперимент„ В3ЯВ 20 тестоВых матриц харуэллскОЙ кОллекции ~231 и значения 1, 3, и для р. При р = 1,3 использовалась программа БЯ.ЕБТ, а при р = и — программа МА28 117), Сравнение двух различных прОграмм„разумеется, Вносит услбжняющие побочные эффекты, ухудшая качество эксперимента.
Однако случай р =и был бы рассмотрен не вполне объективно, если бы мы просто положили р = и в 8Я.ЕЬТ, так как упорядочения строк в этом случае не требуется. МА28 мы взяли потому„что это программа, специально сконструированная для случая р = и, причем она счита~~~я очен~ эффе~~ивной. Используя ее, мы имеем более твердые основания для суждения о наилучшем значении р. В табл. 3.2 приведены Общие запросы к памЯти (измеряемые суммой значений переменной СОПЯТ вЂ” см.
$ 1.2) для всех 20 систем. Видно, что при переходе от р = и к р = 1 суммарное значение СОБСТ возрастает всего на 7,3 7а; зато суммарное время счета сокращается примерно наполовину. Промежуточное значение р = 3 представляется прекрасным компромиссом. "время счета приблизительно то же самое, но приращение значения СОПЯТ вдвое меньше. Замечание 3,6.
ЗДесь слеДует поДчеркнуть, что Для Отдельных матриц Вариации В значениЯх СО13ХТ были значительно больше, достигая 26 % (см. подробности в 186~ ). Поэтому мы не Должны претендоВать на то, что из таблицы 3,2 Уабдичо 8.2. Зависимость значения СОСЖТ и времени счета от р для 20 харувллсхих тестовых матриц Суммарное аначеннв СООХТ Суммарное время счета 71322 68836 66491 107.3 103,5 100.0 31.33 33.35 61.92 можно делать какие-то выводы общего характера.
Нужно упомянуть, что некоторые классы разреженных матриц могут быть очень чувствительны к Уменьшению р. Зто надлежит принимать ВО Внимание при ВыбОре стратеГии (программы) для конкретноЙ задачи. (От ТОГО, что проГрамма в среднем на 3% лучше других, мне не легче, если Она на 257о хуже для моеЙ задачи.) Ю 8„4. Рлуииенная обобщенная стратегия Марковица ~УОМЯ)' Уже первоначальные эксперименты с 6МЬ выявили некотОрые проблемы с численной устОЙчиВостью.
Мы Воспроизведем здесь два из них, чтобы показать, в чем заключаются проблемы и каким образом можно поправить дело. Пример 3.7. Рассмотрим матрицу 186~ 1 О ... О О +а — ч О 1+а О О А= Ф О .. ° 1 + а О ... 0 0 ММ5 — 111е 1гпрготед цеоега1аед Магй~а11х з1га1еду. — - Прим, ае Здесь ч ° 1+ а и положительное число а выбрано близким к машинной точности е. Поскольку Все строки и столбцы содержат лишь по два ненулевых элемента, то для данной матрицы стратегия выбора не зависит от значения р. Если ч е ц, то за главные можно брать элементы главной диаГонали. В этОм случае а(в) — 1 + а + п~(1 + )и-1 Это означает, что при большом п СтМЯ может давать неустойчивые результаты (и даже переполнения).
Заметим, однако, что вычисления будут устойчивы, если всегда выбирать наибольший элемент среди кандидатов на роль главного. Пример 3,8. Рассмотрим матрицу А = Е (2500, 50). Пользуясь программой МА28 на машине 1ВМ 3033 в МЕЛИСС (Вычислительный центр Северо-Европейского университета, Люнгбю, Данил), мы получили Ь =2.2Е7. Вычислительное решение было абсолютно ошибочным, Отметим, что если в качестве главного всегда брать наибольший элемент, то будут выбираться только диагональные элементы (см.
замечание 3.14)' и будет получено Ь„ = 4, что указывает на очень устойчивые вычисления. Система с матрицей А = Е(2500,50) решалась также посредством подпрограмм пакета т'12М (см. 197, 1021). Некоторые данные об этих вычислениях представлены в табл, 3.3. Они показывают, что утверждения, сделанные "т'ьеМ (ь хранится) '1'(2М (Ь нс хранится~ Время счета Память (СОПИТ) Значенне Ьн Погрешность 28,97 54145 4 О 82 Е-4 в конце разбора предыдущего примера, сохраняют силу и для матриц класса Е(п, с). Нужно еще отметить, что для этого класса матриц стратегия ММЯ (см, ниже определение 3.10), воплощенная в И2М, сохраняет разреженность гораздо лучше, чем 6МЯ, реализованная в МА28. Естественно, что это приводит к сильному сокращению времени счета. Напомним, что все компоненты точного решения равны 1. Замечание 3,9.
В то время как матрица примера 3.7 сконструирована искусственно, матрицы класса Е(п,с) очень схожи с теми, что возникают при численном решении некоторых эллиптических дифференциальных уравнений. Пример 3.8 поэтому является серьезным аргументом против ОМЯ и за улучшение этой стратегии; см. 186~. И Определение 3.10. Улучшенная обобщенная стратегия Марковица (16МБ) состоит в том, что на Ьм шаге гауссова исключения в качестве главного элемента выоирается наибольший по модулю из кандидатов, находящихся в С(,, ПОскольку Все кандидаты на роль ГлявнОГО элемента имеют одну и ту же цену Марковица, мы можем для выбора одного из них воспользоваться критериями устойчивости; в этом и заключается предлагаемое ~улучшение». Заметим, что любая последовательность главных элементов, проистекающая из применения ИМ8, может быть получена и посредством бМ8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
