Прямые методы для разреженных матриц. О. Эстербю, З.Златев (984134), страница 12
Текст из файла (страница 12)
Таблица 4.14, результаты, полученные и экспериментах с питью матрицами харуэллской коллекции. При факторизации этих матриц не происходит заполнении Бремя счета 'Уиеличе ние нрсмени. ': Матрица У12М вЂ” 1и о ЗН1. 200 ЗН1. 400 зтк о Вт 0 0.97 0.93 124 Нужно помнить, что для «дорогих» задач применение 1К с бол~ш~м Т сущ~с~~е~но ~~~р~щае~ пам~~~ и вре~я счета, а именно для этого сорта задач вопросы памяти и времени важны по-настоящему (сравни табл. 4.8 и 4.9).
Для практической реализации итерационного уточнения были предложены три стратегии. А. Классический, или английский способ. Невязки в формуле (1.4) накапливаются с увеличенным числом разрядов, а за~ем окру~ляю~ся до обычной ра~рядно~~и. Все остальные вычисления проводятся с обычной точностью. Эта стратегия анализируется в 18Ц и 1107~; см.
также 175~, Она реализована в У12М. Б. Революционный, или польский, способ. В недавней работе 152] показано, что при некоторых условиях повышенная разрядность не нужна даже для вычисления невязок. Этот результат важен для машин/ компиляторов, не имеющих возможности увеличивать разрядность. Полная машинная точность решения не будет достигнута, но сам процесс будет численно устойчивым (см, также 173~). В.
Осторожный, или скандинавский, способ. Векторы гь дь х~ хранЯтсЯ с уВеличенным числОм разрЯдов, и Все скалЯР . Ные произведения в (1.4) — (1.6) накапливаются с повышен. ной разрядностью. Все остальное выполняется с обычной точностью, Если в обычном числе п| разрядов, а в числе с повышенной точностью пр разрядов и п2.» 2п1, то при сходи- мости итерационного процесса можно получить дополнительно . п1 верных разрядов решения по сравнению со стратегией А, ' Этот факт был доказан в ~3, 51 для алгоритма, предложен.:=.
ного В 19~. Наши эксперименты указывают, что он справед- :лиВ и для гауссОВЗ исключения. Плата за это — дополнительная память для массивов Гь 4ь хь увеличение времени на каждую итерацию и несколько ,. (обычно 3 — 4) дополнительных итераций для получения добавочной точности. Кроме того, мы получаем более достоверные :;.: Оценки ошибки, а Возможно, и бо~~е робастный алгори~м, ,'; который может сходиться и тогда, когда не сходится страте'- гия А, Ах =Ь, (7 ) где Л е=- Р " и о е- =Р""' заданы, а х ~ Р" — искомый :- вектор, такой, что евклидова длина вектора г=Ь вЂ” Ах (7.2) ';::.' 4,7.
Итерационное уточнение и задача наименьших квадратов Общие методы для линейных задач наименьших квадра';: тов рассматриваются в гл, 5. Однако если такая задача ре:::: шается методом расширения„то к получающейся линейной ::..системе могут быть применены методы, описанные в гл, 2 — 4. Рассмотрим линейную задачу наименьших квадратов Таблица 4.15.
Необходимая память (измеряемая параметром СОПИТ) при решении задачи (7,3) для А ° Г2(1500, и, 125, 6, 100.0), и = 500 (100) 1400 ПРЙЧОю Решение Итеоацнонно уточненное решение 1. не хранится т 10-' т-10 ' т=и-' т~=в10 т~10' 101610 88077 69227 66526 63872 62712 63175 64716 65606 64180 255889 294191 300395 270602 260079 239894 204261 217605 181777 175433 111192 136040 140801 136181 138383 126535 96729 106094 84174 79005 32129 26915 23930 23432 19771 19772 19812 19910 20585 21529 минимальна. Расширенной называется система Ву= с, Где А~ е1 Л Многие эксперименты 190, 97, 101, 103~ показали, что применение большого барьера Т вместе с итерационным уточнением очень эффективно при решении систем вида (7.3)'. В этом параграфе представлены некоторые численные резульэ~с~еримент~ с 10 тестовыми матрицам~ класса Р2 (1500, и, 125, 6, 100.0), и =500(100)1400.
Заметим, что при таком выборе параметров гп, с, г расширенные матрицы, хотя и имеют различные размерности (п+гп= — 2000(100)2900), содержат одно и то же количество ненулевых элементов (ХХ = 2(ггп+ 100)+ гп = 19720). Режим ВЯ использовался с Т = 10-1а и считался дважды соответственно с хранимой и сбр~~ы~ае~оЙ ~~жнеЙ тр~у~о~~ной матрицеЙ 1.. Режим 1К использовался с Т = 10-", 1 = О(1)4. Правая часть бралась таким образом, чтобы первые гп компонент вектора у были равны О, а последние п компонент — 1.
Б табл. 4.15 — 4.17 мы приводим данные соответственно о необходимой памяти (измеряемой параметром СОКОЛЯТ), времени счета и полученной точности. Эксперимент был проведен в ХЕ11СС; машина 1ВМ 3033; компилятор РОКТН. Табл. 4.15 ясно показывает, что требования к памяти уменьшаются„если не хранить 1.
(режим 1)8); однако еще большее сокращение памяти достигается при (хранении Е и) использовании большого барьера — чем больше барьер, тем больше сокращение. Из табл. 4.16 следует, что время счета для режима 1:)8 мало чувствительно к тому, хранится 1. или нет; однако 1К и большой барьер обеспечивают значительное уменьшение времени, Оптимальным значением барьера является, видимо, Т = О.1, хотя в некоторых случаях при Т = 1 время еще меньше.
Таблица 4.16. Время счета (в сехундах; машина ! ВМ 3033) при решении задачи (7.3) для А = Г2(1500, п„125, 6„100.0), и = 500 (100) 1400, Число итераций дли нтерационно уточненных ре1пений укавано в скобках Итерацнонно уточненное решение т== 1О-' т=ш — ' т в 10 Х .10-' т=10-' Согласно табл.
4.17, для режима ВЯ точность довольно хорошая, хотя для 1К она значительно лучше (и часто близка Таблица 4.П. Погрешность при решении вадачи (7.3) дли А= Г2 (1500„п, 125, 6„100,0), и = 500(100) 1400 Прямое решение Итерацнонно уточненное решение н анитея Ь не тадж 10 т-10-' 500 600 700 800 900 1000 1100 1200 1300 1400 130.15 178.38 108.55 75,88 82.68 57,55 51.39 18,74 (4) 16.48 (3) 12.10 (3) 11.16 (3) 10.41 (3) 9.55 (3) 9.48 (3) 9.58 (3) 9.91 (4) 9.25 (3) 12.68 (4) 11.12 (4) 9.03 (4) 7.67 (4) 7.49 (4) 7,06 (4) 6.99 (4) 7.20 (4) 7.07 (4) 7,17 (4) 8.11 (9) 6.87 (9) 5.63 (9) 5.27 (8) 5.13 (8) 4 99 (9) 5.13 (8) 4.98 (7) 4.91 (8) 5.17 (8) 1,ОŠ— 6 1.3 Š— 6 4.3 Š— 6 1.2 Š— 7 6.0 Š— 8 6.0 Е-8 6.0 Š— 8 6.0 Š— 8 6.0 Š— 8 6.0 Š— 8 3.30 (3) 2.57 (3) 2.65 (6) 4.73 (24) 5.15 (37) 2.89 (14) 3 10(15) 7,28 (50) 5,45 (33) 4,24 (21) к машинной точности), пока Т меньше единицы, Ясно, что значение Т = 1 с~~ш~ом ~ел~ко, как показывают ность и число итераций (табл.
4.16). Критерий остановки есть комбинация условий (1.7) — (1.9), причем МАХ1Т = 50. При Т = 1 расходимость очевидна для и = 500 и 600, но и для других значений и более внимательное изучение величин Ода показало бы„что итерационный процесс ведет себя слишком нерегулярно, чтобы его результату можно было доверя~~. Разумеется, это всего лишь один эксперимент, показывающий превосходство 1К с большим Т. Мы не можем дать доказательство или гарантию, что этот вариант всякий раз лучше; но многие другие эксперименты подтверждают, что он всегда работает Очень эффективно.
Мы пробовали решить те же задачи посредством МА28. Результаты для А = Р2 (1500, 500, 125, 6, 100,0) приведены в табл. 4.18. При и = 600 для решения (7,3) не хватило часа,, процессорного времени; другие значения и мы не испы- ':-'-: тывали. Таблица 4,И. Некоторые данные относительно задачи (7.3) с А = Г2 (1500, 500, 123, О, 100.0). Задача решалась в МЕЛИСС на машине 1ВМ 3033 посредством программы МА23 Погрешность Время счета Память С011ХТ То обстоятельство, что МА28 терпит катастрофу на матрицах вида (7.4), требует объяснения, Оказывается, что такие матрицы особенно трудны для МА28, и результаты для них не типичны для ее обычной производительности.
В матрице-',::. Г2 (1500, и, с, г, к) из 1500 строк 1480 содержат г ненулевых::, элементов (а остальные 20 строк — от г+ 1 до г+ 10 нену- -: левых элементов). Следовательно, число ненулевых элементов в 1480 строках Б из 1500+и равно г+1 (а в остальных строках больше, если и <.
750). Аналогично для столбцов, поскольку  — симметричная. Таким образом, минимальная цена Марковица есть г г; она достигается на 1480 диагональных элементах, которые, однако, все должны быть отвергнуты как кандидаты в главные элементы согласно критерию устойчивости (см. (3.1.2) и (3,3.4) ) . На первом шаге гауссова исключения приходится просмотреть 1480 строк и 1480 столбцов„пока программа, использующая СЕМЯ, не Осознает, чтО минимальная цена Марковица для элемента, удОвлетВоряющего критерию устойчивости, не может быть . (при и ~ 750) меньше г(2г — 1).
На многих последующих шагах дело Обстоит сходным ОбразОМ. ПреимуществО прО- : смотра только нескольких строк (как в У12М) очевидно. Нужно отметить„что Возможность ограничить поиск несколь: кими строками введена теперь и В МА28 (см. Нагже11 $пЬгоц11пе 11Ьгагу БИ11е11п, 1983, № 16, р. 2). 4.8. Оценка числа ооусловленносхи ЧислО ОбуслоВленности м(А) = 1~А~1~~А — Ч матрицы коэф:.--' фициентов является довольно важной характеристикой не только для сходимости процесса итерационного уточнения, но "и при Выяснении чувствительности решения задачи к ошибкам ,:- (округлений).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
