Разряженные матрицы. Р. Тьюарсон (984138), страница 6
Текст из файла (страница 6)
Общее число всех таких элементов, которые были нулями в матрице Ацо и приняли ненулевые значения в матрице Асьэ'>, называется локальньсм заполнением. Если вместо элемента а<~' в качестве главного на й-м шаге мы выбираем другой ненулевой элемент а~у~, з ) К 1) К необходимо переставить й-ю н з-ю строки так же, как й-й и с-й столбцы в матрице А~"', прежде чем вычислять Ам+и по формуле (2.2.2). Тогда дц Минимизации числа ненулевые элементов в ЕГ! ЗЭ вместо формулы (2.2.2) имеем А~»+н=(»А~»', й= 1, 2, ..., п, (2.5.2) где Аин = Р»А'М» (2.5.3) а матрица Р» и матрица Я» получены из единичной матрицы ! путем перестановки соответственно ее й-й и з-й строк и Ф-го и 1-го столбцов.
Все матрицы е.» также выражаются формулой (2.2.3), но элементы векторов-столбцов т1<»~ имеют теперь вид »11»>=0, 1(п, ~(й! т(») = —— й'»~ и»» (2.5.4) 1> Ф, Ч'~~ = 1 » =~~~ »» Следующая теорема (Тьюарсон (1967 б) ) может быть использована для определения главного элемента„обеспечивающего наименьшее заполнение. Теорема 2.5.5. Если а<~>», „, выбран главным элементом й-го шага прямого гауссова исключения, то локальное заполнение дается (1, 1) -м элементол1 матрицы че», равной а = »»», (2.5.6) где аф — (1, 1)-й элемент матрицы А'»'. Принимая во внимание последний абзац равд.
2.3, вспомним, что ~а)»,'~ > е, где е — допустимое значение главного элемента. Следовательно, из всех наличных кандидатов на роль главного элемента, а именно для всех элементов, для которых ~ аф ~ > а при 1 > й, 1 > й, необходимо выбрать такой, который обеспечил бы наименьшее локальное заполнение. Это может быть сделано следующим образом. Определение. Обозначим через В» матрицу, полученную из последних и — й+ 1 строк и столбцов матрицы Аао путем замены ненулевых элементов единицами. Гл. р.
Метод исключения Гаусса где В» — транспонированная к матрице, полученной из матрицы В путем замены всех ее нулевых элемен- тов единицами, а всех единиц нулями. Доказательство. Если в матрице А'») (р+ й — 1, у+й — 1)-й элемент равен нулю, но и (с+й — 1, (7+Й вЂ” 1)-й элемент и (р+Й вЂ” 1, 1'+Й вЂ” 1)-й эле- мент ненулевые, то из соотношений (2.5.2), (2.2.3), (2.5.3) и (2.5А) следует, что (р+ й — 1, д+ й — 1)-й элемент в А(»+') будет ненулевым.
Это равносильно утверждению, что если Ь(» =О , Ь(е = Ьр)~= 1, (») где Ь„есть (р,с))-й элемент матрицы В», то соз. (») дается новый ненулевой элемент. Если через ун обо(») значить общее число таких вновь созданных ненуле- вых элементов (локальное заполнение) на й-м шаге гауссова исключения, то у)»()= ЕЕ Ь',",)(1 — Ьр")')Ьр')), р ~ 1, у ~ 1. е Или у((»))= Е ~л' е',В е (1 — е'В е)е'В е„(2.5.7) р а где ограничения р час', (7Ф( опущены, так как для р=1 или Ьы =О, или 1 — Ь,е =О и для д=) или (Ги ' м) 1 — Ьр)= О, или Ь'( = О.
Теперь, если М является ма(») трицей (п — й+ 1)-го порядка со всеми элементами, равными единице, то 1 — е'В е =е'Ме — е'В е =е' (М вЂ” В ) е р»ерер»е ») (2.5.8) где последний знак равенства следует из того, что величина е'В»е является скалярной, Из выражений р» е (2.5.7) и (2.5.8) имеем =е',В ~е е'В'„),е е'В ет=е',В»В'В е,, 2.д Минимиэация числа ненулевых элементов в ЕР1 41 так как ~~< ее' ~ ее'=1 ь <.
Этим завершается е е е р р р н-ь+< доказательство теоремы. Теперь мы, наконец, в состоянии выбрать главный элемент, который обеспечит наименьшее локальное заполнение. Это может быть осуществлено на основании приводимого ниже следствия, доказательство которого мы опускаем, так как оно непосредственно вытекает из теоремы 2.5.5.
Следствие 2.5.9. Локальное заполнение будет минимальным, если на й-м шаге гауссова исключения в качестве главного вь<брагь элемент а<в<<, где з = = а+ й — 1, 1= р+ й — 1 и а, р даны формулой уф= ш(пе,'6 е для всех (а<<в+<в < +„,~) а (2.5.10) <,/ (е — некоторое подходящим образом вь<бранное допустимое значение главного элемента).
Принимая во внимание формулу (2.2.11), получим все ненулевые элементы 5<ем путем изменения знаков у ненулевых наддиагональных элементов матрицы У. Поэтому из формул (2.2.9) и (2.2.10) следует, что обратная подстановка в методе Гаусса не порождает новых ненулевых элементов.
Таким образом, новые ненулевые элементы создаются только при прямом исключении. В конце й-го шага последние и — й строк и столбцов матрицы А<"+П содержат, вообще говоря, некоторое число ненулевых элементов там, где в матрице А<м соответствующие элементы были нулями. Так как такие строки и столбцы используются на последующих шагах для вычисления векторов т<<ь< и 5<в<, то минимизация локального заполнения будет минимизировать и число ненулевых элементов векторов э<<м и 5<в< при условии, что достижение локальных минимумов приводит к глобальному минимуму. Это условие может и выполняться для некоторых матриц, но не является обязательным для произвольных разреженных матриц. Во всяком случае, минимизация локального роста таких ненулевых элементов с помощью следствия 2.5.9 все же приводит Гл. 2.
Метод исключения Гаусса к существенному уменьшению числа ненулевых элементов во всех векторах ~М> и Чмц Выбор главных элементов а<~' для обеспечения минимума локального заполнения не влечет за собой особых сложностей. Необходимые изменения в формулах могут быть описаны следующим образом. Из формул (2.5.2) и (2.5.3) имеем АЫ'о = Еара ° ЕгРгЕ,РгА(Ыг Оаь (2.5.11) и если положить Е=Е„Р„...
ЕгРгЕ,Рь ЩЯг ... (;1а=Я и А"'+н =У, (2,5.12) получим А '= ЯО 'Х. (2.5.13) Матрицы перестановок Я и Ря в совокупности требуют для своего хранения объем памяти порядка п ячеек (а не пг), так как в каждом случае необходимо запомнить только позиции нетривиальных элементов. Более простой, хотя и менее точный метод нахождения главного элемента, при котором локальное заполнение было бы малым, основан на следующей теореме (Маркович (1957) ). Теорема 2Л.14, Если ни й-м шаге гауссова исключения в качестве главного выбран элемент и~>г, „то максимальное возможное заполнение (не обязательно совпадающее с действительным заполнением) дается (1, /)-м элементом матрицы Ом причем 6г — — (Вг — 1„я+г) М (Вд — 1„я м), (2.5.15) где М вЂ” матрица, все элементся которой единицы.
Доказательство. Если обозначить через д~~с~' максимальное возможное заполнение на й-м шаге, то так же, как и при доказательстве теоремы 2.5.5, имеем И3'= ЕХ б)еС РФс и учь/ с лс. Минимиэацив числа ненулевых элементов в ЕГ! 43 Или в Р = (е„б~тв~ — 11 (~ Ьвт' — 1), так как Ьт4~ = 1, Отсюда дтв1 = (етВ, ~„,е, — 1) (Х е'В е, — 1) = Р =(е',В, ׄ— е,'7э) (7'Вне, — Ге ), (2.5.!6) где Ун — (и — й+!)-мерный вектор-столбец с еди- ничными элементами. Таким образом, дф = е,' ( — 1„н+ т) 1' У' ( — 1 е ы) е = = е',.
( — 1„н+,) М ( — Г„д т) е, где, как и прежде, а+ Й вЂ” 1 = з и 6+ й — 1 = й Заметим, что выбор главного элемента аф в соответствии с формулой (2.5.17) не обязательно приводит к наименьшему локальному заполнению. Интересно применение изложенного выше метода выбора главного элемента в случае, когда Вн =Вн и только диагональные элементы выбираются в качестве главных. Из формулы (2.5.16) в этом случае следует, что Ьятнт> =(е',.В,7х — 1) ()т' В,е,.
— 1) = =(е',Вн!т — 1)', так как В' =В . так как !тн)тв=М. Этим завершается доказательство теоремы. Для того чтобы воспользоваться приведенной выше теоремой, будем выбирать на й-м шаге главный элемент по следуюшей формуле (вместо формулы 2.5.10): фф=пппдф длЯ всех ~и,"тн т +„,~> е, (2.5.17) н! Гл 2. Метод искаокения Гаусса Поэтому ~~~'= т(п(е,'Ве7 — 1)'. Но индекс а бу7тет тем же для т(п(е,'.„Р— 1), что и для пппе,'В Уи, так как е,'ВиРе) 1.
Другими словами, для выбора главного среди диагональных элементов применяется формула (2.5. И) т т е,'Ви(ти = еиВ„)т ~а<'+>. ь.+я, ~) в. при Заметим, что есВе)се есть общее число ненУлевых элементов (с + й — 1)-й строки матрицы Ам>. Таким образом, на каждом шаге выбирается строка (и соответствующий столбец), которая содержит наименьшее число ненулевых элементов. Это относительно просто сделать и поэтому рекомендуется во многих практических приложениях (Тиннн и Уокер (1967), Спиллерс и Хикерсон (1968), Черчилл (197!)). Одно из главных оснований для выбора главного элемента только среди диагональных элементов заключается в следующем. Если матрица А симметричная, то очень часто хранится в памяти только ее верхняя треугольная часть вместе с главной диагональю, и выбор главного среди диагональных элементов при прямом гауссовом исключении не нарушает симметрии.
Кроме того, все векторы ЧМ1 могут быть легко полученыиз верхней треугольной матрицы в конце прямого исключения. Формулируем эти положения в виде теоремы. Теорема 2.5.19. Если матрица А — симметричная и только диагональные элементы выбираются в качестве главньсх, то а) матрица, состоящая из последних и — й строк и столбцов матрицы Ам+в в формуле (2.5.2) при й = 1, 2...,, л — 1, тоже симметричная, 2.5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
