Прямые методы для разреженных матриц. О. Эстербю, З.Златев (984134), страница 16
Текст из файла (страница 16)
Эта стратегия~ Основанная на идее, принадлежащей Джентльмену 1381, реализована в программе 1.Е5801 189„95, 96~. . Пусть мы находимся в начале 1-го большого шага (1~. а 1 = п). Тогда выполняем следующие действия; (а) Находим столбец (пусть его номер з) с наименьшим числом (за+ 1) активных элементов (т. е. элементов, чей строчный индекс больше или равен Ы). (б) Переставляем К-й и з-й столбцы. (в) Для 1=1(1)зв находим две строки и (с ненулевыми элементами В ВеДущем столбце), имеющие наименьшее числО активных элементов. Аннулируем в одной из них элемента> в соответствии с алгоритмом (5,3) — (5,6). (г) Пусть г-я строка — единственная, содержащая ненулевой элемент в ведущем столбце. Переставляем М-ю:-и г-ю строки.
Заметим, что ведущий столбец на каждом большом шаге фиксирован, а перестановка столбцов выполняется до начала операций данного шага точно так же, как это происходит в гауссовом исключении. Перестановка же строк производится в конце большого шага, потому что ведущая строка на каждом малом шаге изменяется. Это сделано, чтобы лучше со- и Активной подматрицы,— Прим, перев. ~~ Ведущего столбца, — Прим. перев. хранить разреженность и уменьшить количество вычислений.
Отметим„что в отличие От ме~ода Гаусса ведущая стрОка претерпевает заполнение, которое все увеличивается, если та же строка повторно используется как ведущая, Замечание 5.31. Заметим, что критерий устойчивости (5.3) не может быть применен, поскольку заранее определено, где будут создаваться нули. В Рис.
5.7 — 5.11 иллюстрируют поведение двух стратегий в отношении сохранения разреженности (рассмотрены два больших шага для матрицы с малыми размерами). В стратегии переменной ведущей строки на первом большом шаге комбинируются строки (1, 8), (12, 13), (1, 12), а на втором х х х х х О Х Х Х Х Х х х Х Х Х Х О и В М Х Х о в и х х х Рис. 5.9.
Переменная ведущая строка. Первый большой шаг. Три малых шага. Новых ненул~в~~ влементов — 6. Рис. 5.7. Исходная мат- Рис. 5.8. Фиксированрица, ная ведущая строка. Первый большой шаг. Три малых шага. Новых ненулевых элементов — 8. Замечание 5.30. Дафф ~161 предложил стратегию, использующую фиксированную ведущую строку. Заменим ~ пункты (в) и (г) на (в') Пус~~ г-я строка и~еет Ми~и~ал~ное читало ненулевых элементов среди строк'~ с ненулевыми элементами в ведущем столбце, Переставляем 1-ю и г-ю строки. (г') Аннулируем поддиагональные элементы ведущего столбца, работая с фиксированной ведущей (Е-й) строкой, а прочие строки беря в порядке возрастания числа ненулевых элементов.
а Рис. 5.1О. Фиксированная ведущая стрОка. Второй большой шаг. Четыре малых шага. Новых ненулевых элементов — 8. Рис. 5.11. Переменная ведущая стрОка. Второй большой шаг. Трн малых шага. Новых ненулевых влементов— 7, Если число ненулевых элементов в ведущем столбце' > не превосходит 3, то размер заполнения для обеих стратегий будет одинаковым. В противном случае, стратегия переменной Ведущей строки, вероятно, будет давать лучшие результаты В том смысле, чтО число Операций для Вычисления матрицы $ ~~н~ше, особе~но если матрица не сл~шком разрежена; при этом числоа1 элементов в 8 может уменьшиться ненамного (см.
1161). Некоторые результаты в этом направлении получены В 189), там же высказанное выше утверждение подкрепляется данными мнОГих численных экспериментОВ. Стратегия переменной Ведущей строки имеет недостаток, не позволяющий эффективно использовать ее, когда нужно факторизовать последовательность матриц одинаковой структуры. Слишком много памяти потребовалось, чтобы для каждого малого шага сохранить информацию о том, какие строки В нем участВОвали. '> Большом.
— Прим. перев, ~~ Активной нодматрицы. — Прим. перга. '> Ненулевых. — Прим. нарев, большом шаге — строки (2,9), (2,8), (2, 12). Заметим, что на Втором Ц шаГе мы не пользОвались ВОзможнОстью изменять ведущую строку. Тем не менее заполнение и вычислительная Работа меньше„чем при фиксированноЙ Ведущей СТРОКЕ, 5.7. Дву~е~йеОв~|Й л~егод, Осиовййиеей нй Оргоеоййлайа~~е щэ еОбрйВОВйниях Теперь мы кратко оп~шем ре~лизац~ю (в программе 1Л,ЬЯО1) двухшагового метода из примера 5.23.
В выражении (3.15) длЯ вектора у1 = Нс матрица 5 пОЯвлЯетсЯ дважды, что может Оказаться не о~~~~ хорошо, так как если А плохо обусловлена, это отразится во Ь. Поэтому мы скомбинируем наш метод с методом примера 5.22, в котором у,=НЬ; Н=~,~-~1~-~йтр,. (7.1) Как уже отмечалось, мы не хотели бы хранить матрицу К, поскольку она велика и, вероятно, не очень разрежена. Тем не менее мы можем воспользоваться методом (7.1) для вычисления прямого решения, если параллельно с разложением матрицы будем те же операции проделывать с правой частью, что приведет к вектору Ь' = КтР~Ь.
Если мы решаем (одну вслед за другой) несколько задач с одной и той же матрицей коэффициентов, в частности если мы применяем обобщенное итерационное уточнение (4.1) — (4.3), то для последующих вычислений используется матрица Н ~З 'В '(Ь ) '©т. (7.2) Заметим, что> несмОтря на (3.14а), матрица В1=А А нигде не вычисляется. Вычисление невязок (4.1) проводится по формулам г*. = Ь вЂ” Ау., г, = Атг'. (7,3) Для ортогонального разложения используется метод Джентльмена — Гнвенса, а для лучшего сохранения разреженности вводится барьер Т, Выбор главного элемента основан на стратегии переменной ведущей строки, описанной в $ 5.6. Хранение информации организовано аналогично тому, как это было описано для гауссова исключения.
Используются массивы А, СХК„КХК, А1, СХ вЂ” последние два для того, чтобы хранить исходную матрицу А. Вследствие заполнения в ведущей с~роке, а та~же в свя~и с нефиксированностью ведущих строк возникают дополнительные осложнения. Массив НА разделен на две части НА1(т,4) и НА2(п,4) с общим числом столбцов, меньшим, чем число столбцов в НА(п, 11)'~. Уменыпение связано с тем, что мы не храним матрицу перестановки Р1„а также информацию об упорядочении строк и столбцов по возрастанию числа ненулевых эле- н Плохой обусловленности. †Пр. перев. е' Использовавшемся в И2М. — Прим. перев, ментов. Иным образом организованы и перестановки при ВыбОре ГлаВноГО элемента. Скалярные произведения в формулах (2.10) и (4.1)— (4.3) накапливаются и хранятся с двойной точностью, как это предложено Бьорком 151.
Дополнительные сведения можно найти в работах 195,961. Нужно отметить, что недавно Бьорк и Дафф 17) и Джордж и л.ит 1391 предложили два других эффективных алгоритма для разреженных линейных задач наименьших квадратов. Второй из них легко приспособить к случаю, когда необходимо использование внешней памяти; см. 140). Эффективность комбинации — техника разреже~~~х матриц+ с~ра~е~~я выбора ~лавнО~О элемента+ большой барьер + итерациОнное уточнение — демонстрируется несколькими экспериментами с тестовыми матрицами класса Р2(т, и, с„ Г, Я). В кажДом из следуюших примероВ мы сохранЯем фиксированные значения четырех из пяти параметров с тем, чтобы проследить за эффектом изменения оставшегося параметра.
Кроме ТОГО, мы берем различньге значениЯ для Т, чтобы ВыЯВить влияние Т на памЯть, Время и точность. Эксперименты выполнялись в ХЕ11СС на машине 1ВМ ЗОЗЗ, для которой п~ — — 7 и п~ — — 16 ~ 2п~ (см. ф 4,6, стратеГия В). Правые части ВО Всех случаях Выбирались таким Образом, чтобы задачи были совместны (г = О) и их решением был вектор с компонентами х~ — — 1, 1=1(1)п, Испытывались и другие правые части, для которых компоненты г~ невязок принадлежали интервалу 1100, 10000~.
Результаты были аналогичны, хотя число итераций несколько больше. Пример 5.32. Рассматриваются матрицы вида Р2(гп,100, 11,6, 10), п1 = 100(10)200; таким образом, изменяется отношение гп/и. Использовались два значения барьера (Т = О и Т = 0.01). Из данных табл. 5.12 видно, что большее значение барьера приводит к уменьшению памяти и времени счета при приблизительно той же точности. й Пример 5.33. Рассматриваются матрицы вида Р2(150, 100„ с, 6, 10), с = 20(5) 65; таким образом, изменяется распределение ненулевых элементов. В табл. 5.13 приведены результаты для Т=О и Т=0.01. И Пример 5.34.
Рассматриваются матрицы вида Р2 (150, 100, 11, г, 10), г = 5(1) 10; таким образом, изменяется ширина ав в е' в ' ' еЕв 11 1 3! !! 1 $ Ф 1 ° а е а ° $ а 'а$ * ° а ° е ° $ 1 11 ! 1 а ° ° !а" $$ $ Ф $ $ И . В- в ° ° в ° 1 в ! ° ФВ ° е ° а В ° ! 1!$3 ваяв ФФ в ° ' ФВ ° ° ' ° Ф ° в а в В 1 В Ф Ф Ф $$ $ $ ° $ $ а ° ° $ е $ '$ ь $$ ° ° ° ° а ! $1$ 1111! ФВ а ° ° В в й.а. Численные результаты 105 т ю ~ т=оо! ° Р э» * м вх~» в О ВИЛ» У УВ С !1 » В $ в »$ $ »1 в $$ в ю ю Ф У $1 11 а Ю в в.» °, $ й» В 1 В » в» ° ° ' ! в $ Ф В Ф в» ° »$ $ ° Ф Ф в в Х В Ф $ Ф 4 ° $ Ф * $ !» 4 в $1» Ф в в ° $! ! в в 1 Ф ' Ф $* 1 ° $» $' 1 '1 Ф ~ 1 » ° ° 1 ° $ 1 1 1 1 $ ° $ » $ 1" в 1 1 1 в 1 в 1 1 ° (б) Для метода из $ 5.7 1К плюс большое Т приводит к сокрашению как памяти, так и Времени счета, (В) 08 несколько быстрее, чем 1Й при том же Т', однако точнОсть 1К значительно Выше.
(г) 1Й может сходиться, даже если матрица очень плохо масштабирОВана; при этОм нужно Взять значение Т поменьше. Сформулированные Выводы из Экспериментов с Ме~одом $ 5.7 очень хорошо согласуются с нашими результатами из гл. 4, относящимися к гауссовому исключению для квадратных матриц. Можно отметить в этой связи, что обычно для задач метода наименьших кВадратОВ строчное ураВНОВешиВание не допускается; пОэтому приходится принимать плОЖО масштабированные матрицы т~~ими, Какие Они есть (и бра~ь Ме~ьшие значения Т). В зтом приложении перечислены программы, упоминаемые в тексте, программные библиОтеки, куда Они включены, и вычислительные центры, где проводились тестовые расчеты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
