Разряженные матрицы. Р. Тьюарсон (984138), страница 17
Текст из файла (страница 17)
Имеем Ам = (Ам — ЕРа)/даа, (4.2.6) причем им 1+а — — А,аап Для полного определения матриц Е и У необходимо применить следующий порядок вычислений: первый столбец матрицы Е, первая строка матрицы У, второй столбец матрицы Е, вторая строка матрицы У и так далее. Как только матрицы Е и 0 становятся известными, легко перейти к формулам (4.1.3) и (4.1.4) для вычисления у и х следующим образом: а-1 Ьа- ~ 1а,д, Уа= 1, й=1, 2, ..., а (4.2.7) н ха =Уа х'., паехе й=п, и — 1, ..., 1, (4.2.8) р а+~ причем суммы ~(...) и Е (...) полагаются рав- Р ! Р о+1 нымн нулю. !!2 Гл. 4. Прямое треугольное разложение Так как формулы (4.2.7) и (4.2.2) по существу одинаковы, можно элементы вектора-столбца у получать при вычислении элементов и»! по методу Краута, применяя формулу (4.2.2) к расширенной матрице (А)Ь) вместо матрицы А и полагая а»,„+1 =Ь» и и„,„+, =у„.
Точность метода Краута может быть повышена применением частичного упорядочения при выборе . главного элемента следующим образом (Уилкинсон (1965)). Вычисляем 1ы согласно формуле (4.2.1), затем определяем 11» 1= птах)(ы 1, 1 > й, (4 2.9) и переставляем з-ю и й-ю строки матриц Е и А. Затем применяем формулы (4.2.1) для ! ) й (для вычисления остальных элементов й-го столбца матрицы Е ')) и (4.2.2). Каждая такая перестановка строк записывается, и в результате получается матрица перестановок Р, такая, что (где Š— нижняя треугольная матрица, а 0 — верхняя треугольная матрипа с единичной диагональю). Из по.
следнего уравнения следует, что А ~ = О ' 1. ~Р. (4.2,10) Из сравнения формул (4.2.10) и (4.1.2) очевидно, что, какие бы перестановки строк матрипы А ни производились в процессе треугольного разложения, для получения обратной матрицы А-' требуется произвести такие же перестановки столбпов матрипы О 'Е '. Уилкинсон (1965) доказал, что треугольное разложение с частичным упорядочением является исключительно точным, если скалярные произведения в формулах (4.2.1) и (4.2.2) могут вычисляться с накоплением. ') Онн уме вычислены Ллл выбора а по формуле (4.2,9).— Прим.
ред. 4д Минимизация занолнения для метода Краута 113 Заметим, что если 1нн =О, то вычисления по формуле (4.2.2) производить нельзя Но если применять формулу (4.2.9), то этого не будет. В этом случае 1ея ие может быть нулем, так как это означало бы, что Ь.й столбеп нижней треугольной матрицы в треугольном разложении матрицы А равен нулю и матрица А особенная. Между гауссовым исключением и прямым треугольным разложением Краута существует следующая связь (Уилкинсон '(1965)).
Для неособенной матрицы А матрицы Е и (7 являются единственными, если они существуют и одна из ннх является треугольной матрицей с единичной диагональю. Поэтому из уравнений (2.2.7) и (4.1.1) следует, что ь = Т," и матрицы (7 в обоих этих уравнениях идентичны. Если при применении гауссова исключения и метода Краута производятся одни и те же перестановки строк н столбцов, то между этими методами опять же существует вышеупомянутая зависимость. 4.3. Минимизация заполнения для метода Краута В начале Ь-го шага метода Краута можно выбрать ненулевой элемент из последних и — й + 1 строк и столбцов матрнпы А и переместить его в (й, й)-ю познпию так, чтобы заполнение было минимальным.
Для определения такого элемента требуется следующее (Тьюарсон (1969а)). Пусть Вд обозначает матрицу, которая получается, если все ненулевые элементы матрицы, представленной на рис. 4.2.1, заменить единицами. Обозначим через Ь)1~' (1, 1)-й элемент матрицы В» и пусть Ян, Тн и 7тя обозначают подматрицы Ь~тт',1) >Ь,1<Ь;Ь!1', 1< й, 1)й и Ь!туг~, 1,1-~Ь. Определим Л =З ят, (4.3.1) где -.
означает булево умножение матриц нли, другими словами, обычное умножение матриц с дополнительным условием, что 1+ 1 = 1. Пусть Ан есть матРика, полученная из матрицы Л» заменой каждого ее 114 Гл. т. Прямое треугольное разлоягенае ненулевого элемента нулем, а нулей — единицами, ь пусть Л,=Л,ЕЛ<„ (4.3.21 где Я означает булево суммирование матриц (1 <хт! = = 1). Если У есть (и — 1+1)-мерный вектор-стол. бец, все элементы которого единицы, то определим с'»1 = У'Л» (4.3.3) г<»1=Л У (4.3.4) Если г«о и сй»1 обозначают а-й и б-й элементы соответственно векторов г<»1 и с<»1, то имеем следующую теорему.
Теорема 4.3.б. Если гав+ с<»<=<пах(г<ю+ с<»1) и е < а З пренебречь воэможностью полного взаимного уничто. жения слагаемых при вычислении скалярных произведений в формулах (4.2.1) и (4.2.2), то перемен(ение элемента а,+» «+» < в (й, й)-ю пози«ию в начале й-го шага метода Краута приводит к наименьшему локальному заполнению. Доказательство. Если е„'Л еь — — 1, то из формулы (4.3.2) следует, что е',Л»еа и е',У ез не могут одновременно быть равны нулю. Принимая во внимание, что матрица Л» была получена из матрицы Л» заменой ее ненулевых элементов нулями, а нулей — единицами, и учитывая уравнение (4,3.1), находим, что уравнения е',(Я ьТ»)ез — — 1 и е,'Л' е =О не могут быть одновременно верны, если е„'Л е = 1. Если перед й-м шагом метода Краута переставить й-й и (р+ + й — 1) -й столбцы матрицы, представленной нз рис. 4.2.1, то на основании определения 5», Т» н Л<» я того обстоятельства, что мы пренебрегаем возможностью взаимного уничтожения слагаемых при вычисленни скалярных произведений, имеем »-< ~, 1, и» чь О И е,', (3» ь Т») е„= 1, о~< 4,3 Минимизация эалоянения для метода Краута 116 прн" н„ем се+ й — 1=1 н элемент в (1, й)-й позиции „атрнцы, в которой произведена перестановка, будет авен нулю тогда и только тогда, когда е,'л(ееа = О, ! А-1 2нл ~~>' э Р Р (4.3.6) 1) Прим 2) Прая, Имеется в виду в первоначальном столбце Р+ й — 1.— ред.
Имеется в виду в первоначальной строке а + й — 1,— ред, Если равенства е'Меев — — О и е,'(5яе Те)еа — — 1 одно. временно удовлетворяются, то, согласно формуле (4 2,1), имеет место заполнение, так как нуль в (1, А)-й позиции станет ненулевым элементом. Таким образом, мы видим, что если е,'Леев=1 и (р+я — 1)-й и й-й столбцы переставлены перед А-м шагом метода Краута, то в (й й)-й позиции заполнения нет. Общее число таких позиций, в которых не может быть заполнения '), равно )г'Льеа или с'"', если учесть формулу (4.3.3). Точно таким же способом можно показать, что г~м представляет собой общее число позиций'), в которых не будет заполнения, если перед й-и шагом метода Краута будут представлены Ья и (а+ й — 1)-я строки.
Поэтому наименьшее локальное заполнение будет иметь место, если перед А-м шагом метода Краута переставить й-ю и (э+ А — 1)-ю строки и й-й и (1+1 — 1)-й столбцы, причем г)"1+с',е>= =щах(гче)+ с)е)). этим завершается доказательство а) теоремы. Существенно, чтобы выбранный согласно изложенной теореме элемент аэ), где д з+ Й вЂ” 1, = 1+ й — 1, после того как его значение будет изменено по формуле (4.2.1), не стал меньше е — допустимого значения главного элемента, т. е. чтобы выполнялось условие 116 Гл. 4. При.ное треугольное разложение Выбор е уже рассматривался в равд.
2.3. Обычно нельзя проверить выполнимость условия (4.3.6) преж. де, чем применять теорему 4.3.5, так как это потребо вало бы больших вычислений и было бы аналогично «полному упорядочению» в методе Краута, что не ре. комендуется (Унлкинсон (1965)). На практике сперва выбирают небольшое число элементов, приводящих к минимуму заполнения или к заполнению, близкому к минимуму, и затем проверяют выполнимость уело. вия (4.3.6), прежде чем выбрать один из этих элемен. тов в качестве главного на й-м шаге. Можно применить теорему 4.3.5 при моделирова. нии метода Краута, если начать с матрицы В, (матрицы, полученной из матрицы А путем замены всех ее ненулевых элементов единицами) и использовать булевы умножения и сложение в формулах (4.2.!) и (4.2.2) для регистрации заполнения.
Таким образом, для всех шагов могут быть «априорно» выбраны главные элементы и в матрице А выполнены перестановки, в результате которых эти главные элементы располагались бы на главной диагонали, прежде чем действительный метод Краута был бы применен. Это может быть осуществлено, если ни один из вычисленных главных элементов не меньше, чем е. Если матрица А положительно-определенная, то главные элементы мо. гут быть выбраны указанным выше способом ') (Тннни и Уолкер (1967); Густавсон и др.
(1970)). Поло. жительно-определенные матрицы и симметричные .матрицы, которые могут и не быть положительно-определенными, рассматриваются в равд. 4.5. 4.4. Метод Дулитла (Блэка) Этот метод является вариантом метода Краута, в котором на й-м шаге вычисляются только й-е строки матриц Е и (7 (Уэстлейк (!968); Тинни и Уокер (!967)). Это является преимуществом, если матрица А хранится по строкам. В этом методе элементы й-й строки матрицы 5 вычисляются слева направо с пв') Среди диагональных элемента», — Пряли ред, 4 д Метод Хохецкого (квадратных корнев, Бакахевика) 117 мощью формулы / — ~ !Ы= пег Х 1ирир4 1=1 2, ° ° °, й, (4.4 1) р а элементы Й-й строки матрицы У вычисляются, как и в методе Краута, по формуле (4.2.2).
Порядок вычислений таков: первая строка матрицы Е, первая строка матрицы У, вторая строка матрицы Е, вторая строка матрицы И и так далее. В этом методе для минимизации локального заполнения нельзя пользоваться теоремой 4.3.5, так как к нзчалу и-го шага известна только первая строка подматрицы 5е'). Возможно, лучше всего моделировать сначала метод Краута, а затем ' априорно выбрать главные элементы, как об этом упоминалось в предыдушем параграфе, Можно также получать матрицы Е и У не по строкам, а по столбцам, вычислив г-1 аеи — ~ 1,.
и < ~ = ~, 2, ..., й — 1, (4. 4. 2) и затем применив формулу (4.2.1) для определения 1ии 1) й. Этот вариант метода Краута полезен тогда, когда ненулевые элементы матрицы А хранятся по столбцам. В следующем разделе рассмотрим Ш-разложение для симметричных матриц. 4.5. Метод Холецкого (квадратных корней, Банахевича) Хорошо известно, что если матрица А неособенная и симметричная, то она может быть представлена в виде А = Ы' или А = Г11, При этом матрица А должна быть упорядочена так, чтобы ни одна из ее северо-западных главных подматриц не была особенпой.
Матрица Š— это единственная нижняя треуголь- '1 Так же, как и подматрппм У» — Прим, ред. ПВ ! л. 4. Прямое треуголвное разложение ная матрица '), а матрица с! — это единственная верх. няя треугольная матрица. Если А = 0'гг', то ~, и яи ! — — авн й(). (4.5А) р ! Поэтому для элементов и-й строки матрицы 5т имеем ! в-! аяв = ваяя — лх:, и,в! 2 р (4.5.2) я — ! ав — ~ и и !)Й. (4л.з) ии я-! В этих формулах принято, что ~'( ) () для ь р Для вычисления строк матрицы У формулы применяются поочередно. Если матрица А не положительно- определенная, то диагональные элементы идя могут быть комплексными числами. Если А — положительно-определенная симметрич. ная матрица, то метод Холецкого является наилучшим для треугольного разложения (Уилкинсон (1965) ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
