Прямые методы для разреженных матриц. О. Эстербю, З.Златев (984134), страница 13
Текст из файла (страница 13)
Мы не станем вычислять х(А) в соответствии "*~' определением, поскольку это весьма дорого, а точнее зна;: 'чение его не требуется. Надежные и недорогие оценки числа обусловленности .'„'можно получить посредством алгоритмов, описанных в 112, :;-:-13, 57, 1091. Все Они выведены для плотных матриц (относйтельно лентОчных матриц см. 147~), но в равной мере при",= менимы и к разреженнОму случаю, Подпрограмма, основанная на алгоритме из 1109~, ; Включена В пакет У12М и при обращении к ней Вычисляет оценку СОХО числа обуслоьленности матрицы коэффициентов. Заметим, что для обращения к этой подпрограмме необходимо сохранять нижнюю треугольную матрицу 1..
Из обсуждения, проведенного в ~ 4.2, следует, что для ' сходимостн процесса итерационного уточнения барьер Т не -" -должен превышать числа, обратного к СОХО. Поэтому вы„-числение СОХ0 полезно при подыскании хорошего значе;,,',:ййя для Т. Если СОЫ1) имеет порядок числа, обратного к машинной ' точности, то нельзя рассчитывать на сходимость итерацион' ' ного уточнении ни при каком Т.
Для решения задачи нужно .' перейти на вычисления с повышенной разрядностью. 4.У. Робастность и надежность До сих пор мы обсуждали главным образом алгоритмы :: для разреженных матриц. Чтобы превратить алгоритм в эле- мент программного обеспечения, нужно требовать робастности и надежности, а если мы хотим, чтобы этим программ,ным обеспечением пользовались, то и определенной эффек- ТИВНОСТИ.
ПОД робастность|О мы подразумеваем, что (а) программа должна отказывать лишь в том случае, если задача действительно трудная, и (б) если программа, в самом деле, отказывает, она должна ВыдаВать ясную информацию, вызВана ли ее неудача (61) плохой обусловленностью задачи, (62) неустойчивостью исключения, (63) недостатком памяти, (64) расходимостью итерационного процесса (65) или чем-то еще. Под надежностью мы подразумеваем, что (в) программа никогда не должна выдавать плохой ре- зультат за хороший и (г) прОгр~мма Дол~на дават~ оценку Ошибки.
Чтобы позволить пользователю поддерживать эффектив- ность последующих вычислений, программа должна сохра- нять важные детали успешно закончившегося процесса, та- кие, как (д1) сколько памяти было использовано фактически; (д2) сколько было итераций и (дЗ) соотношение времени для факторизации и для ите- рационной части. В свою очередь пользователю должны быть предостав- лены рычаги для управления в соответствии с информацией типа (б) или (д) такими параметрами, как (е1) коэффициент устойчивости (п), (е2) барьер (1'), (еЗ) число просматриваемых строк (р), (е4) длины основных массивов (ХМ„ХХ1), (е5) и т.
д. Но без надобности не-следует обременять пользователи Всеми этими параметрами, позтому программа должна преду- сматриВать (ж) значения для параметров по умолчанию. Чтобы извлекать Выгоду из специальных ситуаций, в про- грамме Должны быть (3) ВетВН для специальных матриц нли задач. Наш опыт показывает, что гауссово исключение со стра- тегией 16МЯ, соединенное с итерапионным уточнением и от- сечением по большому барьеру, дает хорошую основу при составлении робастной, надежной и эффективной программы для разреженных матриц.
Как следует из обсуждения в пре- дыдущих параграфах пункты (а) „(в) ) (г) н (е) били учтены должным образом, Пункты (б), (д1 и (з) нужно и~е~ь В виду при реализации алгОрнтма. Что касается зна- чений по умолчанию, мы можем рекомендовать п~ 14, 10~, Т ~ 10,001, 0.011, р -=(2, Ч, ХМ = ЗХЕ, ХЫ1 = 0.6ХМ. Конечно, эти рекомендации нужно воспринимать доста- точно критично, так как все очень сильно зависит от конкрет- ной задачи и режима. Мы ввели пункты (б) и (д) как раз для того, чтобы при необходимости, решая родственную за- дачу, можно было сделать правильный выбор. Нужно помнить о классификации задач, предложенной В $ 2.7, к кот~рой можно добави~ь, что при ~спол~з~~ании ,':.итерационного уточнения категории (1) переходит в (2), : а категория (3) — в (4).
Однако мы могли бы предусмотреть : возможность отключить 1К и вычислять прямое решение, не храня матрицу 1. (см. $ 2.6). Плохая обусловленность задачи (см. (61)) часто, но не := всеГда прояВляется через ~алость гл~вных элементОВ.
С дру- Гой стороны, пр~чиной для малых ~ла~ных элементов мож~т .'::..быть и плохое масштабирование. Неустойчивость исключения (см. (62) ) можно обнаружить, вычисляя числа Ь~ (см. :::: (3.1.4)); ей можно противодействовать, уменьшая коэффи- циент устойчивости и. О недостатке памяти (см. (63)) долж- ::: но быть выдано явное сообщение с указанием, какой массив " (или массивы) требует расширения и на каком шаге исключения, Процесс итерационного уточнения (см. (64)) может схо- '"-,- диться медленно или расходиться, и оба случая идентифици- ' руются посредством значения параметра КЕ1.ЕЗТ и числа .:::: итераций. Расходимость. может быть Вызвана слишком боль- :..шим Т или плохой обусловленностью матрицы коэффициен- тов.
Для задач категорий (3) и (4) при отыскании оптималь- .::.:;:ного Т может быть очень полезна описанная в $ 4,5 «стра- теГиЯ переменноГО Тъ. Мы уже указали (В ~ 3.4) некОторые классы матриц, для которых с успехом могут быть применены специальные стратегии выбора главного элемента. Мы рекомендуем включать В проГрамму для разреженных матриц, Во-первых, ВетВи, позВоляющие эффективно ОбрабатыВать такие специальные случаи, и, во-вторых„возможность отказа от 1К. 4.1О.
Заключительные замечания об итераиионном уточнении и барьерах Процесс вычисления грубого, но дешевого разложения матрицы А посредством отсечения по большому барьеру можно рассматривать как апредварительную подготовкуз 1) А. Ш-разложение, полученное этим способом, иногда называют неполным, или частичным. Предварительная подготовка путем неполного разложения успешно применялась для симметричных положительно определенных матриц в сочетании с каким"либо итерациОнным методом, например методОМ последовательной верхней релаксации или методом сопряженных градиентов (см. 12, 26, 32, 34, 53, 55, 60, 781).
Эти ите-. рационные методы не могут быть пр~менены к Матрицам общего вида, но вместо иих (как в '1'12М) можно использовать итерационное уточнение. С этой точки зрения нашу книгу можно было бы назвать и так: сНеполное 1Л3-разложение в качестве предварительной подготовки к итерационному уточнению». Наши зксперименты п~~азали, что зтот подход ~асто бывает очень эффективен (см.
190, 101, 1031). Нужно подчеркнуть, однако, что существуют задачи, для которых прямое решение конкурентоспособно. Поэтому процесс итерационного уточнения должен быть лишь одним из возможных вариантов в пакете для разреженных линейных систем, Заметим еще, что если матрица А очень плохо обусловлена, то 1К может не сходиться даже при Т= О, В то же время режим 08 с двойной точностью вычислений ~может давать ответ приемлемой (но неизвестной) точностиэ (см.
146), стр. 143). Здесь следует сказать о том, что, пользуясь некоторыми машинно- зависимыми возможностями (листование, мультибанкирование и т. д.), можно так модифицировать режим итерационного уточнения, что он никогда не потребует больше памяти, чем прямое решение. Плата за это — умеренное увеличение времени счета. В РЕСКИН для машины 1ЛЧ1ЧАС 1100/32. разработана модификация режима 1Й программы 712М, использующая мультибанкирование, , $,1.
Линейные задачи метода наименьших квадратов Пусть ~п, и — натуральные числа; Ь ~ С ' — вектор; .''А е= С вЂ” матрица. Через А Обозначаем матрицу, сОпря" мынную с А. Определение 5 1. (Единственная) матрица А+ е= ~".~"' удовлетворяющая услоВиям А+ЛЛ+=А+, (1.1) ЛА А=А, (1 Л) (Л+А)" = А+А, (1.3) (АЛ+)" = ЛА+, (1.4> .,: Называется обобщенной обратной Мура — Пенроуза, или ' йсевдообратной для матрицы А. И Замечание 5,2. По-видимому, Мур 1581 первым ввел понятие обобщенной обратной матрицы. Условия (1.1) — (1,4) -,были сформулированы Пенроузом 163~ значительно позднее. В Замечание 5.3.
Если гп = и и гапКА = п, то А-' удовлетворяет условиям (1.Ц вЂ” (1.4). Этот факт оправдывает те~. 'мин ~0606щенная Обратнаяэ В применении к А+. Определение 5.4. Линейная задача наименьших квадра;:,.'ТО — ЭТО ЗЗДЗЧа ОТЫСКЗНИЯ ВЕКТора Х Е= (~ т МИНИМИЗируЮ- пХ1 ':;:щего евклидову длину вектора г=Ь вЂ” Лх, г~С (1.5) : х называется псевдорешением '~. В Теорема 5.5. Все решения айдйчи (1,5) Вьфйжйк)тся формулой х = Л+Ь + (1 — А+А) к, (1.6) ' еде й Я"= С вЂ” произвольный Вектор.
Доказательство, См. 1771. И Следствие 5.6. Псевдорешение задачи (1.5), имеющее минимальнуго евклидову длину, единственно и равно Атгг. ° " Н срагеааае — 1еааГ вааагеа ао!аГгсс.— Пргггг, гггрге. Следствие 5.7. Если гап~А = п, то псевдорешение задачи (1,5) единственно и равно А+Ь. В этой главе мы рассмотрим прямые методы для вегцественных разреженных задач наименьших квадратов, у которых матрица А имеет полный столбцовый ранг. Таким образом, предполаГается: Рп~хй 1 1~~йх1 гийА=п, А — большая и разреженная. Замечание 5.8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
