Прямые методы для разреженных матриц. О. Эстербю, З.Златев (984134), страница 2
Текст из файла (страница 2)
5 имеет номер 5.3; формула 15 $ 3 гл. 5 нумеруется как (3.15); из другой главы ссылаемся на нее как на формулу (5.3.15). Для таблиц и рисунков своя нумерация в каждой главе. Например, табл. 7 или рис. 7 гл. 1 нумеруем как 1.7. Аналогичная система нумерации используется для теорем, - следствиЙ, замечаний и т, д. Мы хо~ели бы выразитн свою благодарноств Ангелике Пайсен, с болыной тгцател~ностню и мастерством печатавшеЙ РУКОПИСЬ. ВВЕДЕНИЕ Многие практические задачи приводят к бОльшим систе" мам линейных алгебраических уравнений Ах= Ь, где п~К, Ае=й""" и Ь«ы Р""' заданы; гап1А=п, и нужно вычислить вектор х е:- Р" ~ '. В этой книге мы обсудим решение системы (1.1) при помощи так называемых прямых методов, Мь«начнем с хорошо известного гауссова исключения.
Процесс исключения состоит из и — 1 шагов, А'"'" = 1.®А®, ~ =1% п — 1, и начинается с матрицы А««« =А. Нижняя угловая подматрица порядка п — 1+ 1 в матрице А«"«обозначается через А«„ а ее элементы — через а® 0,1= ~(1) и).
Злементь«подматрицы А~с+«находятся по формуле а(~+и а(~~«а~«1а(««~а® «1 1, + 1 ~1) и ~1 З» 1«««'=1, 1=1(1)п; Й= — айай, «=1+1(1)п; прочие элементы 1."> равны нулю. Конечным результатом исключения является верхняя треугольная матрица 13=А<"«, а весь процесс эквивалентен вычислению треугольного разложения А= 1Л5, Где Устройство матриц 1.
и 13 показывают следующие две формулы1 (1) а(1) а(1) а(1) 11 12 13 а(2) а(2) 22 23 1й а(2) 2п Чтобы разложение (1,5) удалось вычислить, необходимо, .чтобы все знаменатели аф в формулах (1.3) были отличны от нуля. Кроме того, для обеспечения приемлемой устойчивости вычислений желательно, чтобы поправочные члены афана/аф в этих формулах были не слишком велики. Обычно это достигается перестановкой строк и/или столбцов с тем, чтобы гарантировать неравенство ~ 1()') ~ =:1 либо ~ а(фа~и~~ -:1. Мы вернемся к атому вопросу в ~ 3.1, а пока просто подГотовимся к необходимости ввести в процесс перестановки строк и столбцов, которые преобразуют (1.1) в РАЯ Ятх) = РЬ, (1.9) Здесь Р, Я вЂ” матрицы перестановок.
Разложение (1,5) переходит теперь в соотношение 1ЛЗ = РА( ) + Е, (1.10) Где 1, «-1 Обознача1ОТ сеЙчас реально вычисленные треуголь ные матрицы, а Š— матрица возмущения, учитывающая помимо друГих факторОв Ошибки вычислений. Приближение х к точному решению х вычисляется подстановкой х(=Я1.1 Ч. 'Рь, после чего мы полаГаем Определение 1.1. Вектор х из (1.11) — ~1.12) называется прямым решение ~ВБ)'> системы.
Замечание 1.2. Даже если вычисления в ~1.11) выполняются без ошибок, все же возможно, что х Ф х из-за того, что в ~1.10) матрица Е ненулевая. Мы вправе ожидать, что процесс исключения и подстановки дает «харошееэ решеиие, если элементы Е малы. Гак часто и бывает, Однако заранее эта нельзя гарантировать, как и нельзя гарантировать, что элементы Е будут малы, если используются лишь перестановки строк.
Поэтому может быть пОлезен следующий процесс «уточнения». Вычислить для 1 = 1, 2„..., Ц вЂ” 1 г~ = Ь вЂ” Ахь (1.13) А =~Ь' '1. 'Ргь (1.14) х~+ ~ — х$ + (.1~ (1.15) И ПОЛОЖИТЬ х = хч. (1.16) Определение 1.3. Процесс, Описываемый формулами (1.13) — (1.15), называется итерационным уточнением, Вектор х из (1,16) называется итерационно дточненнь~м решением (1В)т~. Замечание 1.4.
При некоторых условиях процесс (1.13)— (1.15) сходится и х; -+ х ~1-+ со) . В этом случае х = х, + ~ Й; и 4-+ О. Если ряд сходится быстро, то ~~с1;~! можно использовать как приближенную оценку для погрешности ~~х — хД, Будучи сходящимся, итерационное уточнение дает решение лучшего качества и правдоподобную оценку погрешности. платить за это, — дополнительная Таблица 1,1. Сравнение памяти и времени для 08 и Щ н случае нлотных матриц.
Время счета измеряется числом умножений Время — и'+ н'+ О(п) 3 ') 08 — дгес1 зо1Ш1оп, — Прим. перев. ~) 1К вЂ” ЫегаИче геййипен1. — Прим. перев. 13 память (потому что нужно хранить копию А) и добавочное время (для процесса (1.1З) — (1,15) ).
Е) табл. 1.1 указаны требованиЯ к памЯти и время счета длЯ обоих процессоВ 08 и 1Й. До сих пор мы неявно предполагали, что память и время требуются для обработки всех п2 элементов матрицы А (т. е., что А — плотная матрица). Таблица 1.1 показывает, что в этом случае память и время быстро растут с ростом и и что И в обоих отношениях всегда оказывается более дорогостоя- щим, чем ВЬ.
Однако ВО мнОГих приложениях А разрежена, т, е. боль- шая часть ее элементов состоит из нулей, В этой книге мы опишем специальные приемы, позволяющие использовать раз- Реженность А. Граница между плотными и разреженными матрицами до- вольно зыбкая. Мы можем назвать матрицу разреженной, если применение к ней методов, описываемых в книге, эконо- мит память и/или Время. Рассмотрим основную формулу процесса факторизации (1.2) а() +ц — а())) ай)ай)7чй) ~ай) ~ь Р .(2.1) 1, ) = К + 1 (1) и, 1 = 1 (1) и — 1. Ясно, что вычисления упростятся, если одна или более из величин, входящих в правую часть (кроме а))',))„Равны нулю. Методы для разреженных матриц основаны на следую- щих Главных принципах: а) хранятся только ненулевые элементы матрицы А; б) стараются выполнять лишь те преобразования, кото- рые действительно что-то изменяют; иными словами„форму- лой (2,1) пользуются, лишь если аф Ф О и аф Ф О; в) число «новых элементов» (составляющих заполнение) стараются по возможности уменьшить.
Новый элемент воз- никает, если аЖ=О, а ап'+') ~ь О. и ' н Прежде чем продолжить, введем некоторые обозначения и те Р м инолОГи ю. Под элементом матрицы А мы подразумеваем ненулевой элемент. Прочие элементы А называются нулями и обрабатываются как таковые, И Обозначает число неизвестных (число столбцов). И) обозначает число уравнений (число строк). (Случай, когда гп Ф п, рассматривается только в главе 5). 14 ХХ обозначает число элементов матрицы А.
ХИ вЂ” д~~~а одномерного массива А, используемого для хранения элементов (ХЫ~ ХУ). СОПИТ вЂ” максимальное число элементов (включая заполнение), хранимых в массиве А в процессе исключения (ХХ= СОБСТ). — барьер (см. конец $ 1.4). Мы увидим, что применение методов для разреженных матриц полностью изменит содержимое табл.
1.1. Конкретней, время счета и память не будут расти так быстро с ростом и; память, необходимая для 1К, не всегда будет больше, чем для ВБ (поскольку мы вводим отсечение по барьеру); наконец, время счета для 1К будет зачастую меньше, чем для ВЗ, благодаря методам, которые мы собираемся описать в последующих главах. Чаще всего утверждения или предположения о методах для разреженных матриц не удается доказать математически.
Чтобы показать, что один метод лучше другого, или выяснить, при каких обстоятельствах он лучше, нам нередко придется опираться на практические эксперименты. По этой причине были построены несколько классов тестовых матриц. Они представляют собой либо типовые примеры, либо обобщения встречающихся на практ~~е матр~ц, либо «гнусные~ примеры, призванные усложнить жизнь для разреженных матричных программ. В этом параграфе будут определены некоторые из тестовых матриц, которые мы планируем использовать в дальнейшем тексте. Тестовые матрицы класса 0 (п, с) — это и К п матрицы с единицами на главной диагонали, с тремя диагоналями выше главной на расстоянии с от нее, циклически продолжаемыми внизу, и треугольником элементов с катетами 10Х 1О в верхнем правом углу. Точнее, для любого п ~ 14 и целого с„1:" с ~ и — 13: а;,~ = 1, 1 = 1 (1) п; а,, =1+ 1, 1= 1 (1) и — с; а,, „, =1+ 1„1=п — с+1(1)п; а.
= — 1, 1= 1(1) п — с — 1; 1, 1+с+1 а,, „,,= — 1, 1=п — с(1)п; (3.1) а,,+,+ — — 16, 1 = 1 (1) и — с — 2; КООООХХХООХХХХХХХХХ О Х О О О О Х Х Х О О Х Х Х Х Х Х Х Х О О Х О О О О К Х Х О О Х Х Х Х Х Х Х Х о о о х О о о о х х х о о х х х х х х х ООООХООООХХХООХХХХХХ о о о о о х о о о о х х х о о х х х х х о о о о о о х о о о о х х х о о х х к х о о о о о о о х о о о о х х х о о х х х О О О О О О О О Х О О О О Х Х Х О О Х Х О О О О О О О О О Х О О О О Х Х Х О О Х' ООООООООООХООООХХХОО о о о о о о о о о о о х о о о о х х х о о о о о о о о о о о о о х о о о о х х х Х О О О О О О О О О О О О Х О О О О Х Х Х Х О О О О О О О О О О О О Х О О О О Х Х Х Х О О О О О О О О О О О О Х О О О О О К Х Х О О О О О О О О О О О О Х О О О ООХХКООООООООООООХОО о о о х х х о о о о о о о о о о о о х о о о о о х х х о о о о о о о о о о о о х а,, „=16, 1 =п — с — 1(1)п; а =1ОО1, 1=1(1)11 — ~, ) =1(1)1О. Меняя и и с, можно получить матрицы с различными разме- рами и структурой разр~~енности.
На рис. 1.2 изображена матрица В (20,5), тестааыг матрицы класса е(п,с) — это симметричные по- ложительно Определенные и ~ и матрицы, у котОрых на глав- ной диагонали стоит число 4, а на двух диагоналях, соседних с главной, и еще на двух на расстоянии с от нее — число — 1. Эти матрицы Очень схожи с матрицами, получаемыми при дискретизации эллиптических уравнений с частными произ- Водными посредством пятиточечной разностной Формулы. Итак, для и ==. 3 и целого с, 2 ~ с ~~ и — 1: а,, =4, 1=1(1) и; а, =а, = — 1, 1=1(1)п — 1; (3.2) а,,+, —— а... = — 1, 1 = 1 (1) п — с. Ка рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
