Джордж, Лю - Численное решение больших разреженных систем уравнений (947498), страница 4
Текст из файла (страница 4)
ния элементов множителя Е могут быть различными. В этом Доказательство единственности множителя Ь представляется читателю. 26 Гл. 2. Вводные сведения образом: „т Ао=ов= Р, О~ всР; с, у,„'(7, 1 0 1н- ~ О гн ъ% (1 О! (2.1.2) ! О 0 О сгз уя 0 в~ Н~ 1 О 1 О О 1 О 0 О „Я„ ' О ! 0 „ГЕ~ вl~чтйУ "зги 7' оон —— и2 лн-з = ЕтАтАя > параграфе мы исследуем некоторые возможные методы вычисления Е,. Наличие разных вариантов дает необходимую гибкость при выборе схемы хранения разреженного матричного множителя Е Констр! ктивное доказательство теоремы 2.!.! подсказывает вычислительную схему для построения множителя Е.
Это алгоритм в так называемой форме внешних произведений Схему можно описать на матричном языке шаг за шагом следующим В 2ли Алгоритм разлоагенил 27 Здесь для значений 1 от 1 до М г1, есть положительный скаляр, о, — вектор длины Л' — г, а Н, — положительно определенная симметричная матрица порядка Ж вЂ” й После Ж шагов алгоритма имеем А = й~г ... $ мгй...
Ьгге ~ = тг тг Можно показать (см. упр. 2.1.6), что 6 = 2., + 1„+... + Е, — (тУ вЂ” ! ) У„ (2.1.3) Таким образом, Рй столбец 2. есть в точности г-й столбец Ц. В этой схеме вычисляются один за другим столбцы Ь. В то же время каждый шаг требует модификации подматрицы Й, посРедством внешнего пРоизведениЯ !т',.1)гг/г(,. РезУльтатом Является Н„т. е. как раз та матрица, которую остается разложить.
Порядок обращения к элементам А в процессе разложения изображен на рисунке. Яжиейагаг ейиаагеиии ие треаеетеи .'::;:. Ртемеииемеи таите П Рееаагаемага етеиаеи Другая формулировка процесса разложения — это метод окаймлеяия. Пусть матрица А представлена в виде А=(, ), А=(" )(" ). (2.!А) где ит =г.м'и и ~ = (з — нггнг)вь (Почему число з — - готте положительное) (2.1.5) причем уже получено симметричное разложение Ь„Лги ведущей главной подматрицы М порядка М вЂ” 1.
(Почему М положительно определена?) Тогда разложением А будет яв Гл. 2. Вводные сведения Заметим, что разложение ЕмЕм подматрицы М также можно получить приемом окаймления. Поэтому схема может быть описана следующим образом; для 1 = 1, 2, ..., И решить систему Егл де, А-ь. де 1и вычоелиепь 4„= а,, — ~я~ 8,т ~ В этой схеме поочередно вычисляются строки Е; к еще не- разложенной части матрицы обращение не производится до тех пор, пока не будет вычисляться соответствующая часть Е.
Последовательность вычислений изображена на рисунке. Вычиспеннап часть 1Е матрицы; Всстип к ний иткрыт П~ /Г атей части айргщснис пака не прсазуаринась П ;.::...властии аткрьет; праидксаит персстрийка Последняя схема вычисления коэффициентов Š— это алгоритм в форме скалярных произведений. Его можно описать так. Для 1 = 1, 2, ..., Ж вычислить /-1 в 'ъ)Н к„=("и — Еч 1 . Ф-1 Для 1 = 1+ 1, 1+ 2, ..., й вычислить 1-1 =(ц х~ я рь. е-~ Эти формулы можно вывестн непосредственно, приравнивая элементы А соответствующим элементам произведения ЕЕт, Как и в варианте с внешними произведениями, вычисляются один за другим столбцы Е, но к той части матрицы, которая на Е 2.1.
Алгоритм разложения 29 данном шаге еще не разложена, обращения не происходит. По- следовательность вычислений и характер обращений к элемен- там А указаны на рисунке. Юрпиьскпк кс ппсискИиьт Япге часпгь «ьтчиспскп," Йчптсп л псы спгкрат .:,:.:. Дссауп сгпкрькп; П .:,:),: аюисхИппт :::::: псссспгйспкп Две последние формулировки можно изложить на языке одних скалярных произведений. Это можно использовать для уменьшения погрешности численного разложения, накапливая с двойной точностью скалярные произведения.
На некоторых вычислительных машинах такое накопление требует лишь небольших дополнительных затрат. 2.1.3. Разложение разреженных матриц Как было показано в главе 1, при разложении разреженной матрицы она обычно претерпевает некоторое заполнение, т. е. нижний треугольный множитель 1. имеет ненулевые элементы в тех позициях, где в исходной матрице стояли нули. Вспомним разложение матрицы 4 1 2 -' 2 1 —,' 0 О 0 2 0 3 0 0 О 0 — 0 2 0 0 0 16 нз й 1,1.
Ее треугольный множитель | выглядит так: 2 0 0 0.5 0.5 0 1 -1 1 0.25 -0.25 -0.5 1 — 1 -2 0 0 0 0 0 0 0.5 0 -3 1 ЗО Гл л Вводные сведения 1 2 О 0 0 0 3 0 0 О -' 0 0 0 0 16 Модификация на 1-м шаге дает (с точностью до трех значащих цифр) . 25 †. 5 —. 125 (! г 2)= —.125 —.25 .563 —.5 — 1 —.25 — 1 — 25 15 Если при решении разреженной системы используется наличие нулей, то от заполнения зависят и требования к памяти, и количество вычислительной работы.
Напомним, что п(С1) обозначает число ненулевых элеменгов в С1, где П может быть вектором или матрицей. Из (2.!.2) и (2.1.3) видно, что число ненулевых элементов в С выражается формнлой и — $ ч(х)= и+ Х Ч(п) (2.!.6) В нижеследующей теореме, а затем на протяжении всей книги мы измеряем количество арифметической работы числом мультипликативных операций (умножений и делений), называемых в дальнейшем просто «операциями». Большая часть арифметики, выполняемой в матричных расчетах, образует последовательность пар «умножить — сложить», поэтому число следовательно, матрица А заполнилась в позициях (3,2), (4,2), (4,3), (5,2), (5,3) и (5,4), Это явление заполнения, которое обычно игнорируют при решении плотных систем, играет критическую роль в разреженном исключении.
Причину появления ненулевых элементов можно понять лучше, если использовать формулировку процесса факгоризации, связанную с внешними произведениями. На 1-м шаге подматрица Й, модифицируется посредством матрицы п,вт/е(, и получается Н,. В результате подматрица Н, может иметь ненулевые элементы в позициях, которые были нулями в Н,. В приведенном выше примере 6 2лх Алгоритм разложения 3! аддитивных операций приблизительно равно числу мультипли- кативных.
Теорема 2.1.2. Число операций, необходимых для вычисления треугольного множителя Ь матрицы А, равно и-! н-! — з! (о!) [т1(о !) + 3] = — ~ [т!(Т„!) — 1] [з! (Ь„!) + 2]. (2.1.7) г-! Доказательство. Три формулировки разложения различаются лишь порядком выполнения операций. Для подсчета числа операций воспользуемся алгоритмам в форме внешних произведений (2.!.2). На !'-и шаге требуется т!(о,) операций для вычнсле— 1 ния ог/1/о! и — т1(о,) [т)(ог) + 1] операций для формирования симметричной матрицы Результат получается суммированием по всем шагам. Для плотного случая число ненулевых элементов в Ь есть — У(У+ 1), (2.1.8) а арифметическая работа— Л' — ! ! ч ! ! з 2 — Л г(г+ 3) = — Уз+ — Уз — — У. 2 аи 6 2 3 (2.1.9) а арифметическая рабата при вычислении Е— и-! — 1 (4) = 2 (У вЂ” 1). г-! Сравнивая эти результаты с подсчетами для плотного случая, видим огромное различие в требованиях к памяти н вычислительной работе.
Стоимость решения эквивалентных разреженных систем с разными упорядочениями также может быть весьма различной Рассмотрим еще в качестве примера разреженной матрицы разложение Холесского для симметричной положительно определенной трсхдиаганальной матрицы.
й!ажно показать (см. главу 5), чта если Š— мнал<итель такой матрицы, та з!(Ь„) = 2 для г = 1, ..., У в 1. В этом случае число ненулевых элементов в г есть з!(Е) =2У вЂ” 1, 32 Гл. 2. Вводные сведения Как показано в $1.1, матрицу А, приведенную в начале этого раздела, можно упорядочить так, что она вообще ие испытывает заполнения! Нужная для этого матрица перестановки есть О О О О 1 О О 0 1 0 0 О 1 О О О 1 О 0 0 1 О О О О При применении к А она обращает ее упорядочение.
В резуль- тате получается матрица 16 0 0 0 2 0 0 0 РАРт 0 0 3 0 2 0 0 0 — ' 1 2 -' 2 1 4 Этот простой пример демонстрирует, что разумный выбор Р может повести к громадному сокрашению заполнения и арифметической работы. Поэтому при решении линейной системы Ал=Ь общий подход состоит в том, чтобы сначала найти перестановку, нли упорядочение Р данной задачи. Затем система записывается в виде (РАР )(,Рх) =РЬ, и метод Холесского применяется к симметричной положительно определенной матрице РАРг, что приводит к треугольнойу раз. ложению ЕЬг. Решая эквивалентную переупорядочеиную систему, часто можно достичь уменьшения запросов к машинной памяти и времени исполнения Упражнения 2лл Повязать что разложение колесового симметричной положительно определенноА матрипы единственно 2А.2 Пусть А — симметричная положительно определенная матрнна порядка яг.
Показать, что: а) всякая главная подматрина А положительно определена; б) А вевырождена и А-' также положительно определена; в) глах аи птах ) а 1ж1жн " ~жь гс.н 2.1.3 Пусть А — симметричная положительно определенная матрица. По. казать, по а) ВгАВ положительно определена тогда и только тогда, когда В невы. рождена, б) окаймленная матрица положительно определена тогда и только тогда, ногда з ) я'А-'и. 2.1А.
Записать равенства, аналогичные равенствам (2 1.2), (2 !.3), ноторые данали бы разложение ПЮг, где Е теперь — ннжния треугольная матрица с единицами на диагонали, а  — диагональная матрица с положительными диагональными элементами 2.1.6. Пусть Е и Р— нижние треугольные матрицы порядка М, которые при некотором й (1 < а ( д!) удовлетворяют условиям: ел = ! для ( ) /г; ел = 0 для ! ) ! и 1 ) а; (л 1 для ( ~ й; (о О для 1 ) / и ! < й. Случай М = 6, й = 3 изображен на рисунке.
1 0 1 О 001 Ооо. Ооо.. 000««« Показать, что ЕР Е+Р— У, и тем самым установить справедливость (2.1.3). 2.1.6 Привести пример симметричной матрицы, которая бы не имела треугольного разложении Ы,т, и такой, котораи бы допускала более, чем одно разложение. 3 2.2. Решение треугольных систем 2.2.г'. Вычисление решения После того как вычислено разложение, нужно ре1пить треугольные системы д.у = Ь н атх= у. В этом параграфе будет рассмотрено численное решение треугольных систем. Пусть мы имеем линейную систему Тх=Ь порядка М, где Т вЂ” невырожденная треугольная матрица. Без потери общности можно предположить, что Т вЂ” нижняя треугольная.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
