Разряженные матрицы. Р. Тьюарсон (984138), страница 23
Текст из файла (страница 23)
Так как «-я строка матрицы йр»А~»~ используется снова на следующем промежуточном шаге для преобразования некоторого элемента а~~~', д) р, в нуль, то ненулевые элементы, созданные в «-й строке на первом шаге, могут также создавать ненулевые элементы в д-й строке. Это случится всякий раз, когда а<дт1 О, а~'1 ~ О и а~~>=О. Мы назовем это ет' взаимодействием второго порядка между р-й и д-й строками. Аналогично имеем взаимодействие третьего и высшего порядка между строками. Таким образом, важно минимизировать заполнение Й-й строки на каждом промежуточном шаге. Так же, как и 'в методах ИТ н КС5, мы рассмотрим матрицу Вд, полученную "з последних п — «-1-1 строк и столбцов матрицы А<д~ ПУтем замены каждого ненулевого элемента едини- Гл.
з. методы ортогоналнзачии цей. Если (э+й — 1, 1+й — 1)-й элемент матриц„ Апо перемещен в (К й)-ю позицию в начале й-го ос, новного шага метода Якоби, то заполнение меже~ быть определено с помощью матрицы Вм если пре, небречь взаимным уничтожением слагаемых в пре. цессе вычислений. Во всяком случае, если принят, в расчет взаимное уничтожение слагаемых при вычнс. лениях, то фактическое заполнение будет меньшии чем заполнение, вычисленное с помощью матрицы В, Из формул (6.6А) и (6.6.5) видно, что общее запоя. пение на й-м шаге зависит не только от з-й строкз матрицы Вм но также и от каждой бой строки мат, рицы Вы для которой Ьй~=!, Ь';~'=е,Вье~ 3аполне ние будет тем меньше, чем меньше строк, для которых Ьп —— 1, и чем меньше в этих строках содержитсз пи ненулевых элементов.
Общее число единиц во всех строках, для которьп ЬД' =1, дается формулой (3.2.6): А' =2. г) ~ где суммирование производится для всех 1, для кото рых Ь)|~ =1. Используя формулу (3.2.2), имеем ез х Ьеп ( т' А = ~7, Ьп е;ВьГя = 7„е~Вье;е(ВДь или с()м = есВьВь $~ы (6,6,7) Таким образом, для минимизации заполнения мы вы бираем столбец 1 следующим образом.
Определяем с()" = пип с()"' (6,6.8) ! и затем, чтобы минимизировать заполнение, вызван ное взаимодействием второго и высшего порядков располагаем строки, для которых Ьп — — 1, в порядке ~ы возрастания значений всех г)м и выбираем з из уело вия г',ы = пп'пг® (6.6.9) гм 1, где минимум ищется по всем 1, для которых Ьп =1 б.7. Библиография и комментарии Можно выбрать з и 1, используя общее заполнение „й строки на соответствугощем основном шаге.
Кроме того, ~ожет быть определено заполнение и для других стро, рок по это требует затраты слишком большого труда, и я потому не удобно для практического использования. Б матрице Вд (з, 1)-й элемент будет ненулевым в „ице Ьго шага в том случае, если е1В'„и В е =1. 1)оэтому общее число новых ненулевых элементов в строке з будет равно яля, если воспользоваться формулой (3.2.2), уф=и',(Ва * В„) 17 — е,'ВдЪ' . (6.6.10) Таким образом, мы можем выбрать з и 1 из условия ум' = ппп у'я1, (6.6.1) гг Нг где минимум берется по всем значениям 1 и 1, прн ко~м торых Ьн = 1. 6.7. Библиография и комментарии Метод триангуляризации Хаусхолдера и метод Якоби с анализом ошибок округления изложены у Уилкинсона (1965).
На основании экспериментальных вычислений Райс (1966) показал, что модифицированаый метод Грама — Шмидта приводит к лучшим результатам, чем обычный метод Грама — Шмидта. Анализ ошибок округления для метода ййо дается бьерком (1967). Применение программ ортонормирования в численном анализе рассматривается дэвисом (!962), Глава 7 СОБСТВЕННЫЕ ЗНАЧЕНИЯ И СОБСТВЕННЫЕ ВЕКТОРЫ 7.1. Введение Имеются два хорошо известных прямых метода длз вычисления собственных значений и собственных век. торов симметричных матриц: метод Гивенса (бМ) в метод Хаусхолдера (НМ). По существу они эквивз. лентны методам триангуляризации Якоби и Хаусхол.
дера, описанным в гл. 6. В обоих методах прнменяетсх ряд ортогональных преобразований подобия для прв. ведения заданной матрицы к, трехдиагональной фор. ме, так как собственные значения и собственные век. торы трехдиагональной матрицы легко определяются (Уилкинсон (1965); Фокс (1965)). В следующих двух разделах мы дадим краткое описание этих методов в обрисуем некоторые приемы минимизации заполнении в случае, когда заданная матрица преобразуется х трехднагональной форме (Тьюарсон (1970а) ). В случае несимметричных матриц применяется мо.
дификация гауссова исключения для приведения зз. данной матрицы к форме Хессенберга, в которой все а;; = 0 при 1) 1+ 1 (Уилкинсон (1965)). Собствев. ные значения матрицы Хессенберга легко находятся (Фокс (1965)). В разд. 7А вслед за кратким аписа. нием этого метода приводятся способы миннмизацкв заполнения (Тьюарсон (1970с)). Если заданная матрица А симметричная, то во мне. гих случаях можно произвести такую перестановку при которой верхний левый угол результирующей мат рицы будет иметь трехдиагональную форму. Это меж' но осуществить, если удастся найти строку, в которо" не больше одного внедиагональиого элемента, ВтУ строку (и соответствуюший столбец) перемешаем та"' чтобы она стала первой строкой (первым столбцом) 7.2.
Метод Гееенса 153 Затем мы исключаем первую строку и первый столбец аз дальнейшего рассмотрения и повторяем описанную выше процедуру для оставшихся строк и столбцов. поли на каком-либо шаге нельзя будет найти строку с одним внедиагональным элементом, то процесс пре«рашается. Ясно, что на этом шаге левый верхний угол преобразованной матрицы будет иметь трехдиагональиую форму. Теперь нам остается только преобразовать квадратную матрицу в нижнем правом углу к трехдиагональиой форме, применив один из методов Г1М или НМ. Поэтому в остальной части настоящей главы эту подматрицу без потери общности будем обозначать через А. 7.2. Метод Гивенса Этот метод приводит матрицу А к трехдиагональной форме с помощью вращений Якоби (Уилкинсон (1965)).
К началу й-го основвого шага первые й — 1 строк и столбцов матрицы Аич имеют трехднагональную форму. Основной й-й шаг состоит не больше чем нз п — Й вЂ” 1 промежуточных шагов, в процессе которых последовательно вводятся нули в позиции й + 2, й+ 3, ..., и й-й строки и й-го столбца. Применяя обозначения, подобные тем, что были в равд, 6.6, определим Гг э=1„+(т — 1) (ее+,е'+, + е е')+ где ஠— первый нейулевой элемент после (1+1)-й строкй в й-м столбце.
Тогда первый промежуточный шаг в основном й-м шаге может быть представлен в виде (7.2.2) Теперь е,'Й =е,', если 1 чь й + 1, р. Поэтому все строки и столбцы матриц А) ' и А'»', имеющие индексы, отличные от й+ 1 и р, будут одинаковыми и е, 'э, Гг „А по = (е' „, + (т — 1) е,', + ве') Аеи = = те'+,Ам'+ ве„'Ав>. (7.2.3) И4 Гл.
7. Собственные значения и собственные векторы Аналогично имеем е')с Аеб = те'А'а' — оте' Ам>. р рь р яч( (7.2 4) Таким образом, (Ф+ 1)-я и р-я строки матрицы ДраА(а( являются линейными комбинациями соответствующв„ строк матрицы А(л). Подобным же образом можно убедиться, что е матрице(т ьА(еМ' (й+ 1)-й и р-й столбцы явля(отсе линейными комбинациями соответствующих столбцов матрицы )(рлА(л), Более того, если положить (и аз+( ((а(~д) + (а(аье(( а) )з (ь( арь ((а ь() + (а, +(( а) ) а то е'А(ь'е =е')т А(ы(с' е = р( ь р рь раь = (те'А(Я( — ие' А(а') е = ) ь = та(а( — ота(м = О. рь я-(-(, ь Так же можно показать, что е'А(ме = О. Таким обра.
ь ( р зом, (р, й)-й и (й, р)-й элементы матрицы А',и равны нулю. Повторным применением формулы (7.2.2) преобразуются в нуль все элементы, расположенные в позициях А+2, А+3, ..., и й-й строки и й-го столбца матрицы А(ю. Результирующая матрица обозначается через А(а+(( и й-й основной шаг завершен. Нам было бы желательно определить такой элемент а("> (еь (Ф ФО, зэьг — 1,что если с помощью симметричной пере. становки строк и столбцов его сделать (й+ 1, й) и элементом, то заполнение будет минимальным '). Это ') Автор не учитывает, что выбор главного элемента в столб' пе ( + й — (, Г ) 2, и связанная с этим перестановка й.го в (( + й — !).го столбиов влекут за собой симметричную переста' новку й-й и (( + й — ))-й строк. В результате неиулевоп эле' 7.2.
Метод Гиввяса 155 „ая ксмбинаторная задача, и ее решение не могло „быть полезным для практики из-за чрезмерно больИзого го объема вычислений, которого оно потребовало Поэтому обычно предпочитают методы, близкие к оп оптимальным, ие связанные с большой затратой тру да Анализ, приведенный в разд. 6.6, с минималь„„„и изменениями может быть применен также и сь. Отличие заключается в том, что в равд. 6.6 й-я рока взаимодействует с другими строками, в то время как здесь (й+ 1)-я строка взаимодействует с другими строками, а затем (й+1)-й столбец взаимодейтвует с другими столбцами.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
