Разряженные матрицы. Р. Тьюарсон (984138), страница 21
Текст из файла (страница 21)
6.3. Минимизация ненулевых элементов в методе К6$ Из формулы (6.2.4) видно, что во всех столбцах, для которых сушествует отличное от нуля скалярное произведение со столбцом а<"', может иметь место некоторое заполнение. Позтому для минимизации локального заполнения из последних л — й+1 столбцов выбирается столбец а'»', который привел бы к наименьшему заполнению, если перед й-м шагом метода й<з3 сделать его й-м столбцом. Это осушествляется перестановкой й-го и з-го столбцов матрицы А<и; А'»' = Ам~Я», (6.3. Ц где <,/» получается перестановкой й-го и а-го столбцов единичной матрицы 1„, Тогда вместо формулы (6.2.1) Матрица /7» является единичной матрицей, в которой /г.я строка заменена вектором-строкой ь<»Е Из формул (6.2.1), (6.2.2) и (6.2.3) следует, что 138 Га б. Методы ортогоиализации применяем А(»+')=А~~В», й=1, 2...
и. (6.3.2) Если й(4) и й(с»с) обозначают соответственно 1-й стол. бец и (с, !)-элемент матрицы А, то матрица 0» дается (4) формулой (6.2.2), но элементы векторов э даются "(4) формулами 64)=0, ! <й, -(4) б» 'а/ (М -(4) и $с = —,),(, б» 'б»' Г= ! > й, (6.3.3) ~б(4)'Е(»)) г вместо формул (6.2.3). Для определения столбца, который приводит к наименьшему локальному запоянению, можно воспользоваться следующей теоремой, в которой через Ь',4' обозначен 1-й столбец матрицы Вы полученной из по.
следних и — й+1 столбцов матрицы А(") путем замены всех ненулевых элементов единицами. Теорема 63.4. Есси (1+й — 1)-й и й-й столбцы матрицы А(4) переставлена и затем выполняется я-й исаг метода Р65, то максимальное заполнение дается 1-м диагональным элементом матрицы 6», где 04 = (В» и В») В»ВМ (6.3.5) причем и обозначает булево умножение, а матрица В» получается иэ матрицьс В» путем замены всех ее нулей единицами, а всех единиц нулями. Доказательство. Если (1+ й — 1) -й столбец матрицы Аби сделан ортогональным к ее (!+й — !)-му столбцу, то максимальное число дополнительных ненулевых элементов, созданных в 1-м столбце, равно Ь(14'Ь(с), где Ь(С вЂ” !ьй столбец матрицы В». С другой стороны, если Ьс * Ьс = 6, то ни один ненулевой эле(»и м) = мент не создается.
Таким образом, в обоих случаях общее заполнение для !пго столбца может быть дано в виде (Ь( ' Ь'4)ГЬ(4~ Ь' '. с ° дд д(инимизацил ненулеввсх элементов в методе йтсз 139 П внимая во внимание то обстоятельство, что с(д 'Ь(сд) = О, общее заполнение длЯ всех столбцов имеет и" с вид и — д.! ) дс(сдс).= Х (Ьс ) ' Ь!' )) Ьс(' ) Ьс(д)* (6 36) !-! или и-д+) Я= ~~', (е)Вд * Вде;) е(ВдВдес, с ) где е является )ьм столбцом матрицы !„д+(, или н-дд! д(сдс) = е',(Вд в Вд) 2, е е'В'Вде,= д / = ес (Вд в Вд) ВдВде! = есбдес, н-д+) так как ~ е(ес=7„д+), что и завершает доказа!! тельство теоремы.
Заметим, что условие Ь вЬ, =1 не обязательно (д) (м озяачает, что скалярное произведение соответствующих столбцов матрицы А(") не равно нулю. Также заполнение в столбце Ь(см может быть меньше, чем Ьс Ьс, так как в действительном методе К63 может м)' м) иметь место взаимное уничтожение слагаемых. Этим обьаспаетсЯ, почемУ л(сдс) дает максимальное, а не действительное заполнение. На)п опыт учит, что такие случаи ') редки и когда они имеют место, то составляют лишь небольшой процент от обшего объема вычислений. Поэтому действительное заполнение очень близко к И(с~с~ Как бы там ни было, из приведенной выше теоремы следует, что для того, чтобы минимизировать заполнение, мы определяем дэ(дэ) = ппп я(сдс) = т)п )е,'Оде(1 (6.3.7) с в начале й-го шага метода )с05, затем полагаем з = рч-с — ! р ю ф р р (рз!), (632), Ч (!веется в виду — взаимного уничтожения слагаемых.— С)Рим.
РеО. Гл. В. Методы ортогонолозоции (6.2.2) и (6.3.3.) для вычисления матрицы А(»+'> с по. мощью матрицы А(">. Заметим, что для определения 4 на каждом шаге й должны вычисляться только диагональные элементы произведения матриц В»» В, я / »». Даже это требует больших затрат труда на каждом шаге.
Поэтому, прежде чем применить метод »((л$, мы можем априорно упорядочить столбцы матрицы А по возрастающим значениям диагональных элементов матрицы (В) о В,) В)В(. Можно также, используя теорему 6.3.4, производить изменения порядка столбцов матрицы А(»> через определенные ии. тервалы, а не на каждом шаге й. Это, вообще говоря, приводит к дальнейшему уменьшению заполнения, Для определения столбцов, которые приводят к нуле. вому заполнению в других столбцах, полезно исполь. зовать приводимые ниже следствия из теоремы 6.3.4. Следствие 8,3.8. Если всякий раз, когда Ь((»' » Ь()»>=1, имеем Ь) Ьс =Ь) Ь), то ди =О.
(»)' (ц (»к (ы (и Доказательство. Пусть )) является и)-мерным вектором, все элементы которого единицы. Тогда О=Ь( Ь) — Ь) Ь) = 1' Ь) — Ь) Ь( (и (и и> но (и (и (»> =(р' — Ь)(ы') Ь(ы = =.Ь; Ь -(») (») и следствие вытекает из формулы (6.3.6). Следствие 6.3,9. Если Ь)(»)'Ь((»> = 1, то 8)(»)> =О. Доказательство. Если Ь)"'Ь((~>=1, то Ь((»' »Ь)(."=! означает, что Ь) Ь) =1, и на основании следствия (»> (м 6.3.8 имеем 8((»(>=0. Таким образом, из этого следствия видно, что все столбцы, содержащие всего один ненулевой элемент, должны быть ортонормированы в первую очередь Следующая теорема показывает, что в действительно. сти столбец с единственным ненулевым элементом приводит к уменьшению общего числа ненулевых элементов в столбцах, с которыми он взаимодействует.
дд, Минимивиция ненилеамхехементов в методе мОБ 141 Теорема 6.3.10. Если а1йй1 = 1, но а1йй1=0 для всех ы: р, то а~" йн= 0 для всех ! > й. Доказательство. Из формулы (6,2.4) для / > й имеем ам й н = а" 1 — гаова1й1,т ~~а1й1)') а1й1 = И И ~ ий И I ( ий/ ) ий = а'й1 — а<й1 = О И И что и завершает доказательство теоремы. Пусть У и Уй — соответственно пт-мерный и (и— Ь+1)-мерный векторы-столбцы, все элементы ко торых единицы, а е; и е; обозначают 1-е столбцы матриц 1„и 1„йы соответственно. Тогда, подобно формулам (5.4.11), определим т)"' = -;ВйУ и с'й1 = У'В е .
(6.3,11) Теперь можем описать алгоритм априорного упорядочения столбцов матрицы А для минимизации заполнения. Алгоритм 6.3.12. Определить матрицу В, по матрице А. Пусть В~ обозначает вектор-строку, составленную нз и натуральных чисел так, что ее /-й элемент равен 1: Положить й = 1. !. Вычислить ст~м по формуле (6.3.11). Найти с'," = пцп с1й1. В случае совпадения значений минимума для нескольких 1 выбрать с~ с наименьшим ин(й1 дексом. Если с<и' > 1, перейти к шагу 2, В противном случае положить все Ье1~'=О, если Ьр~~=1, заменить бй столбец матрицы Вй ее первым столбцом н исключить первый столбец из дальнейшего рассмотрения. Переставить (1+ А — 1)-й и й-й элементы вектора Кй.
Положить й равным А+ 1. Если й = и, то перейти к шагу 3, в противном случае вернуться к началу на. стоящего шага. 2. Вычислить бй согласно формуле (6.3.5). Упорядочить последние и — я + 1 элементов Яй соответственно возрастающим значениям диагональных элементов матрицы бй н обозначить результирующий веки тор через В ы Гл. д. Методы ортогоиалиеации 142 6.4. Метод триангуляризации Хаусхолдера Этот метод состоит из и шагов. Для й-го шага А~ +и= НлА' ~, я=1, 2, ..., и, (6.4.1) где -1*(ы. (м Ни=!,„— ал Ч т) (6.4.2) 3. Упорядочить столбцы матрицы А согласно зна. чениям элементов вектора Я„э, так, чтобы новая пози. ция 1-го столбца матрицы А соответствовала значению /-го элемента вектора гт' +ь Замечания. На первом шаге изложенного алгорит.
ма мы определим все столбцы матрицы А, которые содержат всего один ненулевой элемент. После того как такие столбцы делаются ортогональными к остальным столбцам матрицы, могут появиться еще столбцы с одним ненулевым элементом (согласно теореме 6.3.10), и они также определяются на первом шаге. На втором шаге оставшиеся столбцы матрицы А упорядочиваются соответственно величинам заполнения, которое каждый столбец создавал бы, если бы его выбрали в конце первого шага алгоритма. Заметим, что в существующей практике выполнения алгоритма перестановка столбцов матрицы Апо только запоминается, а не производится фактически. Информация о перестановках используется в дальнейшем при осуществлении ортогонализации по методу К л3.
Матрицы перестановок Р и Я, при которых матрица А =РАЯ имеет форму, подходящую для метода КОЗ, могут быть найдены способами, описанными в гл. 3. Если матрица А имеет одну из форм: ВОР, ВТР, В14ТР, ЗВВ(лР, 0ВВ(лР, ВВТР или ВВ(2ТР, то область, в которой может иметь место заполнение, огра. ничивается заштрихованными частями этих форм. В следующем разделе мы рассмотрим метод ортогональной триангуляризации Хаусхолдера (1959). В нем используются элементарные эрмитовы матрицы для преобразования матрицы А к верхней треугольной форме. 6.4. Метод трааыгуляраэацаа Хауехолдера 143 а зг элементы вектора-столбца т<<й> даются формулами т1',.й'=О, 1(й, (6.4.3) й<йй< = а<й' ~ р, Ч<й' = а<ей>, с' > й, т<й йй й' « йе причем ра = 2, (а<<ййт)а а =6' -~ 6 а<й' (6.4.4) й и для устойчивости рй берется с тем же знаком, что и а<а<, Мы начинаем с матрицы А<'< = — А.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
