Разряженные матрицы. Р. Тьюарсон (984138), страница 22
Текст из файла (страница 22)
После и шагов И' метода триангуляризации Хиусхолдера (НТ) первые п строк матрицы А<а+«представляют собой верхнюю треугольную матрицу, которую обозначим через О, а последние тн — и строк матрицы А<"+« содержат одни нуди (напомним, что и< ) и). Заметим, что только и†1 шагов требуется для метода НТ, если л< = и. Пусть Н„Н„, ... Н,=Н, а матрицу, составленную из первых и строк матрицы Н, обозначим через Н, Тогда из формулы (6.4.1) и из того, что Н вЂ” ортогональная матрица, следует А'"+" = НА А= Й'О и, наконец, АО <=Й'.
(6А.6) Так как (т-< — верхняя треугольная матрица и столбцы матрицы Н' ортонормированы, то из формулы (6.4.6) следует, что метод НТ является другим возможным путем ортонормирования столбцов матрицы А. Высокая точность метода НТ делает его привлекательным для вычислений (Уилкинсон (1965) ). Конечно, он требует ббльших затрат труда, чем метод ЙПЗ. Матрица Н хранится в факторизованной форме (64.5); фактически требуется хранить только ненулевые элементы векторов т)<й< и все значения ай (Тьюарсон (1968а)).
144 Гл. 6. Методы ортогонолизоции Для рассмотрения вопроса о заполнении для ма. тода НТ нам потребуется следующая лемма. Лемма 6.4.7. Если й-й шае метода НТ задан фор. мулами от (6.4.!) до (6.4.4), то а) первые й — ! строк и столбцов матриц А<»+» и А<»> одинаковы, б) аий+н = =>- (! и а<»+'> = О, !' > й. Доказательство. Из формул (6.4.2) и (6.4.3) видно, что первые й — ! строк и столбцов матрицы Н» такие же, как и соответствующие столбцы и строки едннич: ной матрицы 7 . Отсюда, принимая во внимание формулу (6.4.!), следует справедливость первой части леммы..Теперь из формул (6.4.3) и (6.4.4) имеем >><»>а<»>=Га<й> ~ () ха'»'+ ~ Га<.'>х'— е =(йй й/ йй ! й+1 !й/ = ~ ~ а<»йй> + рйй = ай, откуда, учитывая формулы (6.4.!) и (6.4.2), вытекает, что а'й+'> = а<»> — ой <(>!<й>'аЮ) т><й> = а<й' — т1<»> или а<»+ '> = <- () йй й а" +" = О, !' > Й.
и Этим завершается доказательство леммы. Из приведенной леммы ясно, что единственно возможным на й-м шаге метода НТ является заполнение в последних и — й+ ! строках н и — й столбцах матрицы А<">. Для минимизации этого заполнения воспользуемся приведенными ниже теоремами (6.4.8) н (6.4.9). Пусть В» — матрица, полученная путем замены ненулевых элементов единицами в последних и — й+ ! строках и столбцах матрицы А<»>. Обозначим !чй столбец этой матрицы через д/~>, а (<,!) н эле- б.а. Метод трианеулярикации Хаусколдера 14о .„ит — через Ьи, так что |м Ь! = Вке), Ьи =е|Вке), |и - |я) е,.— !'-й столбец единичной матрицы 7„к+), Тогда имеем следующую теорему.
Теорема 6.4.8. Если Ь!)к)) =1, то максимальное значение заполнения на й-м шаге метода НТ дается перил диагональным элементом л|атрицы бь определенной формулой (6.3.5). Доказательство. Из формул (6.4.1), (6.4.2), (6.4.3) а (6,4.4) имеем а|'+') = а|к' — а ' ()1|м'а|к)) )1|к), д ) й. так~а) Но т||м'а|к) = ~, а|ма|к) ~ 6 а|к), а и |а к ка' и так как равенство Ь|))' — — 1 гарантирует выполнение неравенства а|к) Ф О, то условие Ь)')'. Ь'," = О, где )=д — й+1, влечет за собой ~, а!)ьк)а|!'*)=О и | к т)л)к)аа = О.
Следовательно, в д-м столбце матрицы А| ) ° |и' |к) Ф не будет заполнения, если равенство Ь|") а Ь)|') =1 не имеет места. Если Ь)к' а Ь!))о 1, то заполнение не может превышать величины (Ь)~к а Ь)|")) Ь! )'Ь|) ), где вектор Ь! получен из вектора Ь) путем замены в нем -и) 'к) всех единиц нулями, а всех нулей — единицами. (Ваметим, что равенство Ь!)к) а Ь)~)=1 не означает, что *и) и) Ч 'а|,"' М О, так как может иметь место взаимное Уничтожение слагаемых скалярного произведения.) Учитывая равенство Ь)|к'Ь|к'=О, можно выразить макс"мум заполнения всех столбцов матрицы А|к) в виде я-Ф+) Е= Х (Ь)к)'.Ь!)'))Ь!)))Ь)к), |-) 146 Гл ц Методы ортогоиилиэоции что соответствует формуле (6.3.6) при 1= 1.
Подай, ным же образом мы заключаем, что дм!=е'0 е . г! ! и !' Этим завершается доказательство теоремы. Заметим, что если а!и»и!=О, то может существовать столбец т,,для которого тг!и!'а!и! Ф О, но а!лика!М=О поэтому будет иметь место излишнее заполнение в т-» столбце. Этого можно избежать перестановкой й.» и э-й строк матрицы Ам! перед й-м шагом метода НТ причем з определяется из условия а!ли! чь О. Для учет» перестановок строк и столбцов имеется следующая теорема. Теорема 6.4.9.
При перестановке двух сголбцое матрицы Ви должны быть пересгаелены также соот. аетстеующие диагональные элементы матрицы Си. Пе. рестановка же двух строк матрицы В» никакого элия. 'нин на матрицу би не оказывает. Доказательство.
Пусть матриць! Р, и Яи получена из единичной матрицы 1„»+! путем перестановки двуя строк и двух столбцов соответственно. Теперь если ин замещаем матрицу Ви матрицей Р»ВЯ», то правая часть уравнения (6.3.5) будет равна Д»~ВйРй и Р»ВД») ЩВйРйР»ВД» = =Ой(В,'* В,) Вйв»О,=Ола,д„ так как Рй*Р» — — ЯДй — — ф, и Щ=РйР» — — Ти я+!. Этим завершается доказательство.
Из теорем (6.4.8) и (6.4.9) следует, что для мини' мизации заполнения в методе НТ мы определяем к я» чалу й-го шага индекс й согласно формуле (6.3.7) Я дРУгой индекс з ) й, такой, что а!и!.т.. ~ О, ЗатеМ переставляем Й-й- и (э+й — у)-й столбцы и й-ую я з-ую строки матрицы А!"!.
Очевидно, столбцы матряцм Вд, содержащие всего один ненулевой элемент, не пр"' водят к какому-либо заполнению и должны рассмат' д и Сопоставление пополнения в методах 11хеэ и НТ 147 ваться первыми. Это эквивалентно предварительной пвать перес становке строк и столбцов матрицы А, которая поэзо олина бы получить наибольшую верхнюю тре угол ольную матрицу в верхнем левом углу, прежде чем прим именнть метод НТ к оставшейся матрице, 6.5. Сопоставление заполнений в методах К6$ и НТ 8 предыдущем разделе мы отметили, что метод НТ может бь|ть применен к заданной матрице А для получения матрицы В' с ортонормированными столбцаии, Соотношение между матрицами А и В' дается фориулой (6.4,6). Если мы вспомним, что В' обозначает матрицу, составленную из первых и столбцов матрицы Н(Не ..
Н'„, и будем ее хранить в факторизованной форме, то потребуются только ненулевые элементы всех векторов трн) и все ан. Хранение матрицы Я' в факторизованной форме не влечет за собой никаких осложяений, так как матрица В' в дальнейшем обычно используется для умножения на вектор (или матрицу).
Мы сейчас покажем, что матрица В' в факторизованной форме является более разреженной, чем матрица с ортонормированными столбцами, полученная в методе К63. Принимая во внимание теоремы 6.3.4, 6.4.8 н 6.4.9, можно утверждать, что максимально возможное заполнение на й-м шаге и в методе КСе8, и в методе НТ дается минимальными диагональными элементами соответствующих матриц Он. Из уравнения (6.3.5) и из того, что матрица Вн имеет размеры тп Х (и — 1+ 1) для метода КСЬ и (и — й+!) Х (п — й + 1) для метода НТ, ясно, что на й-м шаге в методе КПЬ создаетса, вообще говоря, большее число новых ненулевых элементов, чем на соответствующем шаге в методе НТ.
5олее того, из формулы (6.4.3) следует, что только "оследние и — й+! ненулевых элементов й-го столбца матрицы Аео хранятся для вектора ~<н! в методе 11Т в противоположность эквивалентному хранению "енулевых элементов еп-мерного вектора, я-го столбца матрицы А1н>, в методе КСЬ. Поэтому является оче- Гл. Е. Методы оргоеоааеизацьи видным, что факторизованная форма матрицы 19', а, обще говоря, значительно более разрежена, чем орт,„ нормированные столбцы, полученные в методе К~6' 6.6. Метод Якоби Вращения Якоби, являющиеся элементарными еь. тогональными преобразованиями (Уилкнисон (1966)) могут также использоваться для преобразования за. данной матрицы в матрицу А~"+и, которая аналогичнь матрице, полученной в методе НТ.
Метод Якоби (Щ состоит из и — 1 основных шагов, каждый нз которнх в свою очередь состоит из нескольких промежуточянэ шагов. Если Аоо обозначает матрицу в начале й-го ос. новного шага, то первые й — 1 столбцов матрицы Аа) уже имеют форму верхней треугольной матрицы. Еслн (й /)-й элемент матрицы А<М обозначить через а)ь', то в течение й-го основного шага все а)ьь1 Ф О, 1> е, обращаются в нули. На каждом промежуточном шагг с помощью плоского вращения преобразуется в нуль один из элементов а)ьь' чь О, 1> й. Таким образом, об. шее число промежуточных шагов на Ьм основнов шаге равно числу ненулевых элементов аф, 1> Ф.
Рассмотрим первый промежуточный шаг й-го основ. ного шага, Если аф является первым ненулевым эле ментом й-го столбца, который лежит под диагональю матрицы А(Ы, то мы определяем ортогональную мат. рину Р„ь следующим образом: й ь = 1„+ (т — 1) (еьеь + ерер) + га (еье~ — ереь), (6.6 1) где (6,6,21 и) рь (ад,~~~ + а~"')'1 Таким образом, матрица )1рь получена из единичной матрицы путем замены ее элементов (й, й), (й р)' б.б. Метод Якоби 149 ) „(р, р) соответственно величинами т, в, — в и (р)»(ы сейчас покажем, что все строки матриц Аво и А~в одинаковы, за исключением «-й и р-й строк, рые взаимодействуют друг с другом, причем (р, «).й элемент матрицы )кр»А<д~ обращается в нуль. для 1, не равного «или р, из формулы (6.6.1) и того, что е~е; = О, 1 чь 1, имеем е(14р»А'»> = е';А~»~.
(6.6.3) 6 другой стороны, ее Вр» А »1 = (ед + ( г — 1) е» + вер) А»> = = те»А<д>+ верА<д~. (6.6.4) Аналогично ЬВр»А' '=(е', +(т — 1)е,' — ь ',) Атее = тер А< в — ве'„Ае) (6,6,5) Таким обРазом, Р-Я и «-Я стРоки матРицы )кр»А<д> Яв. лаются линейными комбинациями соответствующих строк матрицы А<дд Наконец, из формул (6.6.5) и (6.6,2) следует, что е'11 Ав'е = та'»1 — ва~д~ = О. р р» » р» д» (6.6.6) Из формул (6.6.4) и (6.6.5) видно, что заполнение имеет место не только в р-й строке, но также и в «-й строке матрицы АЖ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
