Разряженные матрицы. Р. Тьюарсон (984138), страница 24
Текст из файла (страница 24)
Так как матрицы А'»',, А14 и А'4+и все симметричньре, то операции для достижения минимума заполнения строк приведут, вообще говоря, также и к минимизации заполнения столбцов. Если В4 — матрица, полученная из последних и — й строк и п — й+! столбцов матрицы Айо путем замены каждого ненулевого элемента едияицей, то или с помощью формул (6.6,8) и (6.6.9), или применяя формулу (6.6.11) можно определить з и 1, причем з Ф ( — 1 (так как диагональный элемент матрицы А<41 не может быть сделан (й+ 1, й)-м элементом симметричными перестановками строк и столбцов).
Интересная модификация метода СтМ для ленточных матриц дана Шварцем (!968). В этом методе для приведения симметричной ленточной матрицы к трех- диагональной форме применяется соответствующая последовательность вращений, аналогичных вращению, представленному формулой (7.2.1). В течение всего процесса преобразований сохраняется свойство ленточности заданной матрицы (см. рис. 7.2.1). Исключение двух симметричных элементов внутри ленты создает, вообще говоря, два одинаковых ненулевых элемента в симметричных позициях вне ленты. Эти элементы исключаются последовательностью вращений, которые 'б * Г р Х б (бр+!— 4- иент, стоящий в позипии (й.
й — 1), займет позицию (Г+ й — 1, — 1), где ранее стоял нуль. Таким образом, первые й — 1 строк " столбнов утратят тот вид, который был поедположен в ниязле раздела — Мрялр рео. 156 Гл. 7. Собственные значения и собственные векторы ширина ленты заданной матрицы) и в конечном счет за границы матрицы.
На рис. 7.2.1 показан весь пр,„ цесс исключения элемента ам при п = 1О и Х причем ввиду симметрии матрицы А рассматриваютси' только элементы, лежащие на главной диагонали и Х Х -и — — к---к О--- 1 к — -Х вЂ” --к- — -к х х х х --х- — -Ф- — -х — — х -О-,— - + --4- — -х---х---к х х х х х Рис. 7.2.1. Вращения иля ленточной матрицы. под ней. Пусть вращение Я определяется так же, как в формуле (6.6.1), и т и со выбраны из условии преобразования данного, элемента в нуль.
Например на рис. 7.2.1 сначала применяется вращение 1чзч дл" того, чтобы сделать ам равным нулю. Это создает не нулевой элемент в (7,3)-й позиции и используетс" )свт для обращения его в нуль. В свою очередь это создает (1О, 6)-й ненулевой элемент. Тогда с помощь 1св, щ обращается в нуль (10, 6)-й элемент. Подобным же образом с помощью вращения есп (которое оставляет (4, 1)-й элемент без изменении) 7.З. Метод Харслолдера 157 „ючается (3, 1)-й элемент. Лва дополнительных искл вра ,цения сдвинут ненулевые элементы, созданные в втес той строке и втором столбце, вниз и за границу иат Рицы.
Продолжение этого процесса для других ок и столбцов преобразует матрицу А к трехдиаго„льиой форме. 7.3. Метод Хаусхолдера Этот метод приводит матрицу А к трехднагональаой форме с помощью элементарных эрмитовых ортогоиальных матриц (Уилкинсои (1965)). В начале й-го мага матрица А~»> имеет трехдиагоиальную форму для своих первых й — 1 строк и столбцов.
На а-м шаге вводятся нули в и-ю строку и й-й столбец, причем сохраняются нули, введенные иа предыдущих шагах. другимн словами, все элементы в позициях А+2, «+3, ..., и й-й строки и й-го столбца обращаются в нуль. Метод подобен тому, что описан в равд. 6.4. Ов состоит из и — 2 шагов, таких, что А'»+о= Н«А'"Нм Й=1, 2, ..., и — 2 (7.3.1) (Ап~ — = А и А'" "— трехдиагональная матрица), где Н«=7„— а«т! (7.
3,2) в элементы вектора-столбца т!<«> заданы соотношениями "1«! =6 '~~ ь, (7.3.3) т!ф, =а'«„', « ~ Р«, т11«!=а!т»«>, Е) й+ 1, причем л 6«« = ~ (а!««г)', а« = 6«« ~ Ца!««тт . (7.3.4) для устойчивости знак р«должен быть выбран таким же, как и знак а!«т »«ь « Пусть В» — матрица, полученная из, последних и-Ф строк и и — й+ 1 столбцов матрицы Апо путем замены каждого ненулевого элемента единицей, Тогда аналогично теореме 6.4.8 имеем следующую теорему. 158 Га 7.
Собственные значения и собственные векторы Теорема 7.3.6. Если 51~~'=1 и Ам~ = Н»А'ы, (7.3.6) гдг матрица Н» определяется соотношениями (7.3,2) (7.3.3) и (7.3.4), то максимальное значение заполне. ния дается (1, 1)-м элементом матриц»и 6», опреде. ленной по формуле (6.3.5). Доказательство. Если мы сравним формулы (7,3.6), (7.3.2), (7.3.3) и (7.3.4) соответственно с формуламн (6.4.1), (6.4.2), (6.4.3) и (6.4.4), то увидим, что отан.
чие между ними заключается в том, что в первой группе формул не используется й-я строка матрицы А~»1 Это отличие учитывается в этом разделе тем, что мат. рипа В» составляется из последних и — й строк, а не из последних и — и+ 1 строк, как в теореме 6А,3, Исходя из сказанного, дальнейший ход доказатель.
ства настоящей теоремы такой же, как и для теоремы 6.4.8, и мы его здесь повторять не будем. Из определения 6» видно, что теорема 6.4.9 применима также и к матрице Вм определенной в этои параграфе. Поэтому если мы воспользуемся формулой (6.3.7) для выбора й и затем возьмем такое з = э — 1, при котором о,"»~=1, и переместим (э+й, й+Я- — 1)-й элемент матрицы Аро на (а+ 1, й)-ю позицию перед применением преобразования (7.3.6), то занол.
некие будет минимизировано'). Так как в формуле (7.3.1) и матрица А(»44~, и матрица Ари симметричные, то описанный выше выбор з и й для минимизации за полнения в случае когда матрица Або умножается слева на матрицу тт», будет, вообще говоря, мннимн. зировать также заполнение в случае, когда матрица Н»А(»~ умножается справа на матрицу Н».
Можно вы числить действительное заполнение для преобразова ния (7.3.1), но так как это связано со слишком боль шими вычислениями, то никакого преимущества дл" практики такое вычисление не дает. ') Сы, ориыечааие аа стр. 154. 159 7.4. Приведение к форме Хессенберга В свете изложенного, прежде чем выполнить й-й „метода НМ, мы перемешаем (а+й, 3+й — 1)-й М„мент матрицы Аио в (й+ 1, й)-ю позицию симметэлем Р""" „„иымн перестановками строк и столбцов.
Этим достиг нгается то, что заполнение будет небольшим. Волее простым путем нахождения й является выбор олбца матрицы Вд, который взаимодействует с небольшим числом других столбцов. Другими словами, акой столбец дает минимиальное число ненулевых булевых скалярных произведений с другими столбцами: ее(Ве в Ве) (7 = пцп е) (Ве е Ве) )г, (7.3,7) l ((онечно, это является, вообще говоря, менее точной оценкой заполнения„чем использование формулы (6,3. 7) . До снх пор в этой главе мы рассмотрели метод Гивеяса н метод Хаусхолдера для симметричных разреженных матриц.
В следующем разделе мы покажем, как с помощью элементарных преобразований подобия можно привести несимметричную матрицу к верхяей форме Хессенберга. 7.4. Приведение к форме Хессенберга Пусть Аии — матрица, у которой первые й — 1 столбцов имеют форму Хессенберга, т.
е. аф=О для всех г' ) 1+ 1 и 1 ( й. Тогда на й-м шаге применяются элементарные преобразования подобия (которые очень похожи на матрицы Вх разд. 2.2) для обращения в нуль элементов й-го столбца в позициях Ф + 2, й+3, ..., п. Это осуществляется для й = 1, 2, ... ..., и — 2, в результате чего матрица А~"-'~ имеет ф~р~у Хессенберга. Таким образом, имеем А =Ьк„,А 1.ее, й= 1, 2, ..., и — 2, (7.4,1) Й-~-н м) -1 где 1.э+, — — 1„+ Чм+неемь (7.4.2) !60 Гл. 7. Собственные значения и собственные векторы причем элементы вектора-столбца т)(а) даются в ви) иде т)((а+"=О, !~(Й+1, (7.4.3) (м п(а+!) ')~;),~,+ ! м) ак+(,я Из формул (7.4.2) и (7.4.3) следует, что Еа+( — — 7 — т! ее+!.
-! (а+ н (7.4.4) Приведенные выше уравнения означают, что для по. лучения матрицы А("+') из матрицы А(ь) необходимо вначале добавить ко всем строкам с элементами а((аа) Ф О, ! ) й+ 1, УмноженнУю на соответствУющин коэффициент (й+!)-ю строку и затем добавить к (Й+1)-му столбцу умноженные на соответствующие коэффициенты столбцы результирующей матрицы, отвечающие элементам а)(аа) чьО, 1) й+ 1. Таким обра.
зом, заполнение имеет место во всем (й+ 1)-м столб. це и в последних и — й — 1 строках и столбцах мат. рицы А(Я). В последних и — й — 1 компонентах (й+ + 1)-го столбца заполнение имеет место дважды: один раз при умножении слева на матрицу Еае! и один рзз при умножении справа на матрицу Ея+!~. Конечно, в первых й+ 1 компонентах (й+1)-го столбца запал. нение имеет место только в результате умножения справа на матрицу Ьа+!. С другой стороны, для по. следних и — й — 1 строк и столбцов заполнение имеет место только при умножении слева на Ея+ь Пусть На обозначает матрицу, полученную из последних п-й строк и и — у+1 столбцов матрицы А(ь) путем за.
мены каждого ненулевого элемента единицей. Тогда имеем следующую теорему. Теорема 7 4 б. Если (э+ й, 1+ й — 1)-й элемент матрицы А(") перемещается в (й + 1, й) -ю позиция) симмегричнь(ми перестановками строк и столбцов' ) причем з чы ! — 1, и результирующая матрица умно кается слева на матрицу Ья+(, то максимальное эа ') См, примечание на стр. 154. 7ХХ Приведение и форме Хессенберга 1В1 „„ение дается (з,1)-м элементом матрицы <гь определенной формУлой (2.5.6) .
77оказательство. Ограничение з ~1 — 1 требуется тому, что диагональный элемент матрицы Або не „ожет быть перемещен в (й+ 1, й)-ю позицию с по„ошью симметричных перестановок строк и столбцов. с учетом того, что (1,1)-й элемент матрицы Вь соответствует (< + й, 1+ й — 1) -му элементу матрицы А<">, доказательство такое же, как и для теоремы 2.5.5, и агт нужды его здесь повторять.
Так как матрица Еь+< изменяет< только (й + 1)-й столбец матрицы А<а>, то, если пренебречь заполне'паеч, которое при этом создается, можно использовать теорему 7.4.5, чтобы выбрать главный элемент для кнннмизации заполнения на каждом шаге. Можно выпнслнть заполнение для (й+1)-го столбца, вызванное умножением на матрицу Ьа+<, но это слишком трудоемкий процесс, чтобы его использовать на практике. Теперь мы опишем, каким образом заполнение (е+1).го столбца может быть минимизировано при умножении матрицы А<М только справа на матрицу Ьг<'.<. Пусть йх обозначает матрицу, полученную из последних и — й+ 1 столбцов матрицы А<ю путем заиены каждого ненулевого элемента единицей. Пусть На обозначает матрицу, состоящую только из последних и — у+ 1 строк матрицы 5<а.
Кроме того, пусть Рв обозначает матрицу, полученную из единичной катрицы (и — й+ 1)-го порядка путем замены ее д-го диагонального элемента нулем. Тогда имеем следуюа<ую теорему. Теорема 7.4.6.Если (р+и — 1, а+юг — 1)ой эле'мент матрицы А<и< перемещается в (й+1, й)-ю позиЦию путем симл<етричных перестановок строк и столбцов') и результирующая матрица умножается справа иа л<атрицу Еа<'.<, то л<аксимальное заполнение (й+ +1)-го столбца дается в виде У<ь>=е'Я' (<т' а 7<с<Ва)е,. (7.4.7) ') См, примечаапе па стр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
