Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 9
Текст из файла (страница 9)
Использование разреженности основано на соотношении Вапй (А) = Вапс((Е + аг), которое будет доказано в $4.2, где рассматривается профиль- ный метод. ') Некоторые авторы называют шириной ленты А число 2й(А) + 1. Ва Гл 4. Ленточного 0 орофильньзе методы — Ом 021 4222 а,з Ом 022 Ситчнетрично О О Ом 04~ О О 044 О 052 05 ° Оп 062 О О 066 О 025 026 ап МаозРОЦО А О О Озз 04> О О О, О Озз оьз О 4254 055 О 066 О 02, ом 0.22 Маесио хранение Ркс.
4Л.2. Диагональная схема хранення. Это показано иа рис. 4.1.2. Такая схема хранения очень проста и вполне эффективна, если бз(А) не слишком меняется с изме- НЕНИЕМ 2. Теорема 4.1.1. Число операций, необходимых для разложения матрицы А с шириной ленты р, в предположении, что лента Вапб(1, + 1.2) заполнена, равно 1 йв х 2 2й(й+З)М- з -~'-.Ъ.й. Доказательство. Утверждение следует из теоремы 2.1.2 и формул р+1, если 1(«1- М вЂ” р, Ч (х..з) = М вЂ” 2+1, если М вЂ” и<1«М. Теорема 4,1.2. 17усть А га же, что и в теореме 4.1.1.
Число операций, необходимых для решения системы Ах = Ь при известном множителе Холесского 1, матрицы А, равно 2(р+ 1) М вЂ” (19+ 1). Доказательство. Утверждение следует из теоремы 2.1.2 и формул для 21(1„2), приведенных в доказательстве теоремы 4.1.1.
Как отмечалось выше, достоинство этого подхода — в его простоте. Однако у него есть н некоторые потенциально серьезные слабости, Прежде всего, если рз(А) сильно меняется при изменении 1, то диагональная схема хранения, показанная на рнс. 4.1,2, будет неэффективна. Кроме того, мы увидим позднее, Обычным методом хранения симметричной ленточной матрицы А является так называемая диагональная схема хранения (Маг((п 1971).
Подднагонали нижнего треугольника А, составляющие Вапб(А), вместе с главной диагональю хранятся по столбцам в прямоугольном массиве с размерами МХ(р(А)+ 1). В 4.2. Профильный метод что имеются некоторые очень разреженные задачи, которые могут быть решены весьма эффективно; однако их нельзя упорядочить так, чтобы они имели малую ширину ленты (см. рис. 4.2.3).
Таким образом, существуют задачи, для которых ленточные методы просто непригодны. Возможно, самая убедительная причина, почему не стоит быть энтузиастом ленточных схем, та, что профильные методы, обсуждаемые в следующем параграфе, имеют те же достоинства простоты, что и ленточные, и лишь немногие из их недостатков. упражнения 4,!.1, Пусть А — симметричная положительно определенная Ж Х Н матрица с шириной ленты р. У вас имеются два набора подпрограмм для решения системы Ах = 0.
В обоих случаях в процессе разложения Ь записывается на место А. В первом случае А хранится как заполненная нижняя треугольная матрица; при этом строки нижней треугольной части хранятся одна за другой в одномерном массиве в последовательности ап, изь аеь о»ь ... ..., о„ „ ,, а„,. Во втором случае А хранится по диагональной схеме, описанной в этом параграфе. Если () и Н заданы, то какую схему вы выбрали бы, пытаясь минимизировать запросы к памяти? 4.!.2.
Рассмотрите звездный граф с Н узлами, показанный на рис. 4.2.3а. Докажите, что при любом упорядочении этого графа ширина ленты соответствуюшей матрицы не будет меньше, чем 1 (Н вЂ” 1)/21 . й 4.2. Профильный метод 4.2.1.Матричная формулировка Несколько более сложной схемой использования разреженности является так называемый оболочечный, или профильнэги, метод, в котором удается извлечь выгоду из изменения ();(А) как функции от 1. Оболочка А, обозначаемая через Епч(А), определяется как Епч(А) =((1, 1) )О < 1' —,( -Дг(А)).
То же самое можно записать посредством столбцовых индексов уг (А): Епч(А) = Иг', !)(~г(А) ~~У < 1). Величина )Епч(А) ! называется профилем или размером оболочки А. Справедлива формула ) Епи (А) ) = ~ и, (А). Лемма 4.2.1. Епч(А) =Епч(Ь+Е~)'). ') Читатель должен помнить, что там, где это им удобно, авторы считают пары (4 А в определении Епт(А) неупорядоченнымн; тогда оболочка кудванвается». — Прим. перев.
60 Гл е. Ленточные и профильная методы Доказательство. Докажем лемму индукцией по размерности )ч. Предположим, что утверждение справедливо для матриц порядка )т' — 1. Пусть А — ЖХФ симметричная матрица, представленная в виде А=(, ), где в — скаляр, и — вектор длины л( — 1, а М вЂ” невырождеииая матрица порядка М вЂ” 1, разложенная в произведение Х,,Т, т Епт(А ) Рне. 4.2Л. Иллюстрации н определению оболочки 4. Элементы наполненна н ь обведены нружкамн.
По предположению индукции, Епч(М)=Епч(д,,+а.мг). Если ЬЬт — симметричное разложение А, то треугольный множитель ,(, можно записать как где т — скаляр, а то — вектор длины М вЂ” 1. Теперь достаточно показать, что 1н(А) = 1н(Е+ Ьт). Согласно (2.1.5), векторы м и та связаны соотношением армен = и.
Но и, = О для 1 ~1()н(А), а элемент и~лье не равен нулю. Как следует из лемм 22.3 и 2.2,4, ы, = О для 1 (1< 1н(А) и тв1,„<а~ Ф О. Поэтому 1н(А) = 1н(Ь+ ьт), откуда Епч(А) = Епч(Т + 1Г). Теорема 4.2.2. Епч(А)с= Вано(А). Доказательство. Это следует из определений множеств Ване) и Епч, 4 4 2. Профильный истое 61 На результате леммы 4 2.1 основана возможность использования нулей вне области, занятой оболочкой или лентой.
Предполагая, что используются лишь нули, лежащие вне Епч(А), определим арифметическую работу при численном решении системы. Для подсчета числа операций полезно понятие ширины Ф Ис ® ья в Иь Ис ь»®а иььа а Ф нь ьа®ьй а11)ж И, ь1ь Иь ьа Аю Рнс. 4.2.2. Илляьстрапня н определениям шарипы ленты н ширины фронта Теорема 4.2.4. Если используются лишь нули, находящиеся вне оболочки, то число операций, необходимых при разложении А в произведение И.т, выражается формулой — ш, (А)(ш, (А) + 3), фронта, которое мы сейчас введем. Для матрицы А 1-я ширина фронта определяется как ш,(А)=((й!й> ю' и аы ФО для некоторого 1~(1) !. Заметим, что е,(А) есть число «активнык» строк на 1-м шаге разложения, т.
е. число строк оболочки А, которые пересекают 1-й столбец. Величину нт (А) = тп а х (ш, (А) ! 1 ( 1 ( У) обычно называют шириной фронта, или волновым фронтом А (!гопз 1970, Ме!оз(т 1969). Рис. 4.2.2 иллюстрирует зтн определения. Полезность понятия ширины фронта в анализе профильного метода демонстрирует следующее утверждение.
Лемма 4.2.3. 63 Гл 4. Ленточные и профильные методы Рис. 4.3.3а. Звездный граф е М узлами. йлоряйочеиие, йнотором центрольньтИ узел помечен лоолейним Улоряйочение о минимольнай шириной ленты Рис. 4.2.36. Упорядочение с минимальным профилем н упорядочение с мини- мальной шириной ленты для звездного графа с Гт' узлами при Гт' = 9. Хотя переход от ленточных схем к профильным связан лишь с очень небольшим усложнением, он может подчас дать весьма впечатляющий выигрыш. Чтобы убедиться в этом, рассмотрим пример на рис.
4.2.3, где показаны два упорядочения одной матрицы. Нетрудно проверить, что число операций, необходимых при разложении матрицы, упорядоченной так, чтобы профиль был минимален, и число ненулевых элементов в соответствующем треугольном множителе суть величины порядка 0(Ж). Такой же порядок имеет ширина ленты. В то же время упорядочение с минимальной шириной ленты требует 0(й(з) операций, а ь' имеет 0(тчв) ненулевых элементов. а число операций, необходимых для решения системы Ах = Ь при известном разложении А = Ы,т, равно 2 ~ (ш,(А)+ 1). Доказательство, Если считать оболочку А заполненной, то число ненулевых элементов в Ем равно ш,(А)+ 1.
Теперь нужное утверждение вытекает из теоремы 2А.2 и леммы 2,2А. в 4.2, профильный иегов вз Хотя этот пример сконструирован искусственно, есть много практических задач, где профильные схемы много эффективней ленточных. Некоторые примеры приведены в работе (1)п, ЬЬегтап !975). 4.2.2. Интерпретация на языке графов Пусть симметричной 7ч'Р,7ч' матрице А сопоставлен неориентированный г аф Р Ол (Л4 Е) узлы которого помечены в соответствии с нумерацией строк А: л =(х„..., хн). Чтобы лучше понять комбинаторную прирпду профильного метода, полезно дать интерпретацию в терминах теории графов тех матричных понятий, которые введены в предыдущем разделе.
Теорема 4.2.5. Если ( <1, то включения (1, () я Епч(А) и х~ я Аб)((хь ... ..., х,)) равносильны. Доказательство. Если х~ ~АеЦ((хь ..., х;)), то агь чь 0 для некоторого К й = 1, так что )~(А) «ь и (), () ~ Епч(А). Обратно, если )~(А) «1«1, это означает, что х~я Аб) (Х1 <л>), Ц'"' ' откуда х~ ен Ад) ((хь ..., Хе) ). Следствие 4.2.6.
44ля 1 = 1, ..., 4ч' справедливы равенства гь~(А)=!Аб) ((хь ..., Х4))1. Доказательство. Согласно определению еь,(А), имеем го,(А) =~(1) 4'1(1, 1) ~ епч(А))1. Теперь нужное утверждение вытекает из теоремы 4.2.5. Рассмотрим матрицу и соответствующий ей помеченный граф на рис. 4.2.4. Смежными множествами здесь будут: А4(х,) (Хьхе), 4((хьхх)) 4((хьх2,хэ)) ьь (х4 х5 хь) А4((хьхьхьх4)) = (х, хь) ь А4((хь..., Хх)) (хд,х7), А4((хь..., хь)) = (х,), А4((хь ..,, Хе)) 15, 64 Гл 4 Ленточные и профильные суетоды Сравните их со строчными иидексамн элементов оболочки в каждом столбце. Рнс. 4,24. Матрица и соответствующий ей помеченный граф Множество Ас() ((хс, ..., х!)) будет именоваться с-м фронтом помеченного графа, а число элементов этого множества (как и раньше) — с-й шириной фронта.
Унраъснения 4.2.1. Довязать, что 1 1 2 Х вс (А) (ю с (А) + 3) чч 2 Е (Зс (А) (Рс (А) + 3). с-! 4.2.2. Говорят, что симметричная матрица А имеет монотонный профиль, если СС(А) ( А(А) при С ( С. Показать, что для матрицы А с монотонным профи!ем и и 1 1 т~ юс (А)(шс (А)+3) 2 ~ ))с (А) (Рс (А) + 3). с 1 2 ~и 4,2.3. Доиазать зивлзалентность следующих условий; а) для ! ( с ( А! подграфы О((хь, хс)) связны; б) для 2 ~ С» »СУ справедливо А(А) ( Ь 4.2.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
