Прямые методы для разреженных матриц. О. Эстербю, З.Златев (984134), страница 9
Текст из файла (страница 9)
Добавим к этому, что первые Е позиций в НА(,7) и НА( „8) (и последние Е позиций в НА(*, 11)) не нужны после К-го шага исключения и могут использоваться для хранения информапии о перестановках строк и столбцов. Чтобы Определить элементы множества Ск, приходится просматривать все элементы р 4лучшихФ строк, Поэтому комендуется малое значение р (р -=: 3). В Ск берется наибольший элемент, т.
е, в У12М реализована 1ЙМЗ, но нашу стратегию легко модифицировать„например„так, чтобы главными выбирались только диагональные элементы. Роль столбцов 7, 8 и 11 массива НА иллюстрируется рисунками 3.6, где показано для матрицы примера 2.1 их содержимОе в начале гауссОва исключения, и 3.7, где зафиксирована си~уаци~ после 1-го шага, в ~~~~ром ~лав~ы~ был элемент (1, 1), Для сравнения мы приведем беглОе оп~саине того, реализована в программе МА28 стратегия выбора с большим значением р. Снова было бы неэффективно вести поиск элемента с минимальной ценой Марковица по всей подматрице Аа, если этого можно избежать. Лучше просматривать строки в порядке возрастания числа ненулевых элементов, но на этот нужн~ ~р~с~а~р~ва~ь и сто~бцы.
Сл~до~~тельно, буются дополнительные целые массивы для упорядочения столбцов. Теперь обходим строки и столбцы в порядке возрастания числа элементов, и если имеются строки и столбцы с одинаковым числом элементов, то вначале исследуем строки. Для каждого элемента проверяем условие устойчивости (1.2) — поэтому строчный порядок обхода гораздо удобней столбцового — и вычисляем цену Марковица Мца. Рис. 3.6. Содержимое столбцов 7, 8 и 11 массива НА перед 1-м шагом дли матрицы примера 2,1. Рис.
3.7. Содержимое столбцов 7, 8 и 11 массива НА после 1-го шага для матрицы примеров 2.1 и 2.6. Если исследуемая сейчас строка (или столбец) имеет в активной части з ненулевых элементов, а наилучшее найденное до сих пор М~1а не превосхОдит ($ — 1) 2 (или Я (Я вЂ” 1) ), то поиск можно прекратить, поскольку ни один из оставшихся эл~менто~ Ак не ~о~е~ ~блада~~ м~~ьш~й цсной Марковица. Этим путем длительность поиска можно несколько уменьшить.
Дафф 117, стр. 251 сообщает, что для матрицы по- рядка 199 в среднем '~ просматривались 14 строк и столбцов. Техника, использованная в МА28, соответствует ИМЯ и при адаптации к 16МЬ, по всей видимости, будет очень неэффективна, Злемент, выбираемый как главный в МА28„— это любой элемент из С~, Для того, чтобы найти наибольший элемент, нужно продолжать просмотр строк (или столбцов) с з элементами, пока (з — 1)2 (или з(з — 1) ) не станет строго :больше М,',.
Это может значительно увеличить длительность .поиска, особенно если в матрице много строк/столбцов с оди.наковым (малым) числом элементов. Сравнение двух стратегий приводит, таким образом, к вы.Воду, что наша стратегия (из У12М) требует меньше времени .На поиск главного элемента (потому что просматривается .меньшее числО строк, и просматриВаются тОлькО строки), меньше памяти (потому что не нужны массивы для слежения За столбцами) и, Возм02кно, приВодит к более устОйчивым вычислениям (потому что используется 10МЯ). С другой стороны, заполнение может быть ббльшим, так как исследуется очень малое число (2 — 3) строк; следовательно, может не быть выбран элемент с минимальной'> ценой Марковица. Проведенные эксперименты показывают, однако, что увеличение числа СОШЧТ обычно бывает незначительно и не отражается на общей эффективности нашей схемы.
В различных реализациях разных вариантов стратегии Марковица большая часть работы (т. е. времени) и дополнительной памяти уходит на просмотр, переупорядочение и слежение за строками и столбцами. Поэтому имеет смысл Описать еще одну стратегию выбора, в которой подобная работа минимальна. Зта стратегия такова: Упорядочиваем столбцы матрицы А по возрастанию числа ненулевых элементов, На 1-м шаге гауссова исключения выбираем в качестве главного элемент 1-го столбца, удовлетворяющий условию устойчивости и принадлежащий строке с минимальным числом ненулевых элементов. Так как мы рассчитываем, что в столбце мало элементов, то можно проверять их все и не заботиться об упорядочении строк.
Эта процедура поиска много проще, чем рассматривавшиеся до сих пор; к тому же при исключении пронзводятся тОлькО перестанОвки СТРОК. Численные результаты, приведенные в 1201 (см. также (18~, с. 12О), показыВают, что методы, осноВЯнные на этой стратегии, имеют недостатки. Заполнение часто будет большим; вероятная причина в том„что столбцы, поначалу содержавшие мало элементов, быстро заполняются, но тем не менее используются как ведущие. Поэтому такая стратегия должна применяться осторожно и/или для специальных классов матриц. Интерес представляет предположение, что разреженность, может быть, сохраняется лучше, если комбинировать эту стратегию с отсечением по большому барьеру (и итерационным уточнением; см.
гл. 4). Для некоторых классов матриц можно сохранить и устойчивость, и разреженность, выбирая главные элементы только на главной диагонали, а в некоторых случаях они могут даже браться в естественном порядке, что позволяет вовсе избавиться от перестановок.
Многа вещественной и индексной ~р~фм~т~~и ~танови~ся в этом случае не~ужн~Й; поз~~му разумно вводить в программу для разреженных матриц в каче- стВО Возможных ВЯриантоВ и стратегии, эффективно обраба" тывающие такие специальные, но часто Встречающиеся случаи. Два класса матриц, для которых не нужен Выбор глаВного Элемента по устоЙчи~ости, — это матрицы с диагонал~ным преобладанием и положительно определенные матрицы.
Тем не менее в ряде случаев выбор главного элемента может помочь сохранению разреженности. В этой связи стоит отметить, что использование большого барьера (и итерационного уточнения) часто позволяет уменьшить размер заполнения, вследствие чего с выгодой могут быть применены более простые стратегии выбора; см. 197, 1О21. Некоторые другие стратегии выбора обсуждаются в 12О1; см.
также 118) и 1711. 4.1, Сходимость итераиионного уточн8нин Напомним (см. гл. 1), что для матрицы коэффициентов ли~еЙ~~Й с~с~~~ы ЛХ=Ь (1.1) строится треугольное разло~кение 1 1.3 = РА~ + Е, после чего прибли2кение х| к х — так называемое шение (08) — вычисляется по формуле х, =Я13 '1. 'РЬ. следующий Итерационным уточнением (1К) называется процесс (см. [110, 75, 81, 107~ ): г =Ь вЂ” Ах 1 р д,.=Я13 11. 'Ргр 1 —.1, ~,, „,, (~ х,„,=х+~„ Он заканчивается при значении ц, для которого ~1Х,— х, ~~1" 81~Х,Ь либо Здесь е обозначает машинную точность, ~~ Й вЂ” произвольную векторную норму, а МАХ1Т вЂ” заданное пользователем максимальное число ~терациЙ.
Относительно сходимости итерационного уточнения справедливы следующие теоремы. 1'еорема 4.1* Персть х — точнОВ РВш8ни8 сист8мы (1,1)'. ПРВдположим, чтО ВсВ Вычисл8ниЯ В (1.4) — (1,6) Выполняются б83 Ошибок. Если 1' — 1~-1~ -1Е (1.10) ТО ~~Рот~ ~ 01;+1от Доказательство проводится по индукции и предоставляется читателю как упражнение, (Заметим, что Р = 1— — 13-'1.-' РАЯ.) И Теорема 4.2. Обозначим через Х», (1 = 1(1) п) собственные значения Р, занямероеанные так, чтобы ~ Х» ~.:» ~ Х», ~, К = 2 (1) и. (1.13) ! Х, ~ < 1.
Доказательство легко следует из теоремы 4.1. В Следствие 4,3. Соотношения (1.14), (1.16) и (1.17) остаются в силе„если заменить (1,15) на ~~Р~~ < 1, (1.18) где ~~ ~~ — матричная норма, порожденная выбранной векторной ~орм~й. Я Замечание 4А. Согласно (1.13), ~Х» ~ есть спектральный радиус матрицы Р. Мы будем пользоваться обозначением р(Р) =1~» ~ (1.19) Замечание 4.5. Число И йЕ1.ЕЯТ=~~»1, »1~ ~~х,11 (1.2О) называется оценкой относительной погрешности.
И Теперь в свете сформулированных теорем рассмотрим внимательней три критерия остановки (1.7) — (1.9). Если р(Р) << 1, то итерационный процесс (1.4) — (1.6) будет сх» диться быстр» ~ и2 как пра~~ило3 будет» ~становлен усл~ ~ вием (1.7) или, быть может, если начнут преобладать ошибки округлений, условием (1,8). В этом случае КЕ1.ЕБТ дает правильное представление об относительной ошибке вычисленного решения хч (если Ь Ф О). Если р(Г) хотя и меньше единицы, но близок к ней, то сходимость может быть очень медленной, и в типичном случае итерации будут остановлены условием (1.9). КЕ1 ЕЯТ будет хорошей оценкой ошибки.
Если р(Р) ="= 1, то 1Й, скорей всего, расходится, и соотношение (1.17) не выполняется. Зто будет обнаружено при проверке условия (1.8), обычно при ц = 3, и значение КЕ- 1.ЕЯТ покажет, что случилось, Нужно подчеркнуть, что теоремы справедливы при предположении, что 1К выполняется без ошибок (анализ метода, в котором учитываются ошибки при вычислениях по формулам (1.3) — (1.6), проведен в 156~ и 162~ „см. также 11101).
Конечно, это предположение нереалистично. Невязки г~ (см. (1.4) ) обычно вычисляются с увеличенной разрядностью, и имеются убедительные экспериментальные свидетельства, что этого достаточно для сходимости итерационного процесса в пределах машинной точности (при условии (1.15)), В этой связи можно упомянуть„что вычислительные погрешности при подстановках (1.5) обычно много меньше, чем ошибки разложения (см, 175, 81, 104, 1071).
При сравнении итерационного уточнения (1К) с прямым решением (08) сразу видно, что 1К требует больше памяти (потому что нужно хранить копию А) и времени (для процесса (1,4) — (1.6)). Зтой ценой достигаются ббльшая точность решения (если 1К сходится) и оценка ошибки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
