Разряженные матрицы. Р. Тьюарсон (984138), страница 19
Текст из файла (страница 19)
Вычисление матрицы У-' в форразложения на множители (которое, как мы пока- „, м, является тем же, что и вычисление матрицы У-' в явном виде) сочетается с прямым гауссовым исклю- чением. Мы увидим, что в методе 63Е исключение лементов над диагональю эквивалентно вычислению „атрицы У-' в соответствии с приведенным выше вторым методом. Этот метод для вычисления матрицы, обратной к верхней треугольной матрице У с единичной диагональю, может быть в математической форме описан следующим образом.
Пусть И<» "п=бД<»', й =1, 2, ..., и, (5.3.1) причем ио'=(у, (ум'и = ~„ (5.3.2) б»=1„+ в~ е», (5.3.3) » где элементы вектора-столбца $~ даются в виде Ц»~=0 ! ) й, и Цм — и!е»»!, ! ( й (5.3.4) (и!»' — (1,!)-й элемент матрицы У<»>). Принимая во внимание формулы (5.3.3) и (5.3.4), имеем О, = У„, и поэтому из формул (5.3.1) и (5.3.2) следует, что (5.3.5) Для установления связи между методами ПЕ и ИЕ нам потребуются следующие результаты (Брей. то" и др, (1969) ). Пусть матрицы Т.», Т» и !!» определяются соответственно формулами (2.2.3), (5.2.2) и .(531). Тогда имеем следующие леммы.
126 Гл. Д Исключение Гаусса — Жордана Лемма 5.3.6. Последние и — й+1 строк матра С» ... Е»Е»А и Т» ... Т»Т»А идентичны при й — ! 2, ..., п. Доказательство. Лемма, несомненно, верна дле й = 1, так как в каждом из двух методов СЕ и ИЕ первый столбец матрицы А приводится к вектору е, идентичными преобразованиями строк, при которых в качестве главного взят элемент а»»»»>. Допустим, что лемма справедлива для некоторого й. Тогда не (к+ 1)-м шаге, в каждом из двух методов ПЕ и»»зЕ, в (3+1)-м столбце (3+ 1)-й элемент делается рав. ным единице, а все элементы, расположенные ниже, обращаются в нули.
Другими словами, над послед. ними и — й строками производятся идентичные пре. образования. Поэтому последние п — я строк матриц Е»».» ... Е»Е»А и Т»+» ... Т,Т,А тоже идентичны. До. казательство леммы завершается по индукции. Лемма 5.3.7. Последние и — й+ 1 строк матриц 1.» и Т» идентичны при й = 1, 2, ..., и. Доказательство. Принимая во внимание формулы (2.2А) и (5.2.3), мы находим, что последние п — й+! строк обеих матриц Е» и Т» образуются из последних п — й+ 1 элементов й-го столбца соответственно иат. риц Е»» ...
Е»Е»А и Т» 1 ... Т»Т»А. Поэтому, учнты. вая лемму 5.3.6, последние и — к+! строк матриц 1» и Т» идентичны. Лемма 5.3.8. Если матрицы У<»! и А<»> определяются соответственно формулами (5.3.1) и (5.2.1), те первые к — 1 строк обеих матриц совпадают при й=2 3, ..., и. Доказательство. Так как еК»А=е»У, то, учитывая лемму 5.3,6 и равенство 0,=1„, имеем е',Ага== =е»Т»А =е(Е»А =е10=е»0»(1 =е(Р". Таким образом, лемма справедлива при й = 2. Предположим, что леы ма справедлива при некотором й. Тогда из формулы (5.2.1) на основании леммы 5.3.6 и учитывая, что в конце й-го шага прямого гауссова исключения ДЗ.
Связь между формами РР1 и ЕР< 121 ... Е»Е<А=е»У, имеем » ° е'А<»+'<=е»Т» . ° . Т»Т<А=еК» ... Е»Е<А= е'„у — е»у<»+ н Орее — — (1„+$"'ер)ее=ее, равд, бве =е +$ <р< и бД"= (Т„+ ~'фе,) $<р'=в<в', д > р, так как еД<о'= О. Поэтому имеем ...О~,=О„...й бе = ... 0»+<(е,+5 )=е»+в =О»еы -<»и -<и О е»=Ц„ =У л что завершает доказательство.
1 „ерь из формул (5.2.1), (5.2.2), (5.2.3), (5.3.1), (53,3) и (5.3.4) следует, что на и-ом шаге над первыми <е — 1 строками обеих матриц Аан и У<ю производятся идентичные преобразования. Поэтому не только ь.е строки, но также и первые Й вЂ” 1 строк матриц А<»+«и О<»< н являются идентичными. Методом индукции по Й доказательство леммы завершается.
Лемма 5.3.9. Первь<е й — 1 строк матриц О» и Т» совпадают, Доказательство. Принимая во внимание формулы (53.3), (5.3.4), (5.2.2) и (5.2.3), находим, что нетривиальные элементы первых 1< — 1 строк в обеих матрицах Ол и Тл образуются из первых д — 1 элементов (<-х столбцов соответственно матриц О<»< и А<л>. Поэтому из леммы 5.3.8 заключаем, что первые й — 1 строк матриц Ол и Тл идентичны.
Лемма 5.3.10. Если матрицы У» и У-< даютсл соответственно формулами (5.3.3) и (5.3.5), то й-е столбць< этих матриц идентичны. Доказательство. Из формул (5.3.3) и (5.3.4) имеем 1йа Гл. д Исключение Таисса — Жердина На основании лемм 5.3.7, 5.3.9 и 5.3.10 имеем сле. дующие два уравнения, которые показывают связь между формами РН и ЕР1: е',Т„е„= е',(7де = е,У е„, ! ( А, (5.3.11) е',Т„е в',Еде, г » )й. (5,3.12) Из формулы (5.3.11) ясно, что нетривиальные эле. менты РГ1, расположенные над ведущей диагональю, являются элементами матрицы 0-', выраженной в явной форме, где У является верхней треугольной мат. рицей с единичной диагональю, полученной в конце процесса прямого гауссова исключения. С другой стороны, из формулы (5.3.12) следует, что нетривиальные элементы в обоих формах РН и ЕН, распо. ложенные на диагонали и под ней, являются идентичными.
Таким образом, структура распределения нулей и ненулевых элементов в обеих формах РН и ЕН одинакова для элементов, расположенных на диагонали и под ней. Над диагональю структура распределения нулей и ненулевых элементов у формы РГ! такая же, как и у матрицы (7 — ', в то время как у формы ЕН она такая, как у матрицы (7. Вообще говоря, матрица У-' содержит больше ненулевых эле. ментов, чем матрица (/, и поэтому форма РН обычно не так разрежена, как форма ЕР1, 5.4.
Минимизация общего числа ненулевых элементов в форме РН Ввиду тесной связи, существующей между фор мами РН и ЕН, все сказанное в разд. 2.3 относи. тельно ошибок округления и выбора главного эле. мента остается в силе и в случае формы РН. Методы минимизации общего числа ненулевых элементоз в форме РН по существу подобны тем, что приве. дены а разд. 2.5 (Маркович (1957); Ларсон (1962); Смит н Орчард-Хейс (1963); Вулф н Катлер (!963)' Диксон (1965); Тьюарсон (1966), (1967, Ь); Орчард бд тнинимиэация числа ненулевые элементов в форме РИ 199 уейс (1968)). Мы сейчас вкратце рассмотрим те нз„еиения, которые нужно внести в методы, приведенные в разд. 2.5, с тем чтобы они могли быть использованы в случае формы РГ[. На й-м шаге метода Сь)Е й-я строка матрицы А~») умножается на различные коэффициенты и складывается со всеми другими строками.
Вследствие этого имеет место заполнение ненулевыми элементами не только области ниже диагонали (как в методе С»Е), но также и области, расположенной над диагональю. для минимизации этого заполнения нам потребуются следующие результаты, Если к началу й-го шага метода Сь)Е переставить в.ю и й-ю строки и 1-й н й-й столбцы, то вместо элемента а<", в качестве главного элемента будет взят элемент а~»>. Конечно, ) а',»т'! должно быть больше допустимого значения главного элемента е.
При таком выборе главного элемента мы получим следующее. Если Р» н Я» есть матрицы, полученные перестановкой соответственно з-й и й-й строк и 1-го и й-го столбцов единичной матрицы !„, то матрица Айо = Р»А~»~0» (5А.! ) имеет элемент а',»т> в (й, й)-й позиции. Тогда вместо формул (5.2.1) и (5.2.3) имеем А~»эп=Т»А~~', й=1, 2, ..., и, (5.4.2) и л(») ! — — (чь й и ~<»'= — (5.4.3) 1 м») > » ~й) в кз формул (5.4.1) и (5.4.2) имеем А '=ЯД» ...
Я„Т„Р„... Т,Р,Т,Рн (5.4.4) Пусть В» есть матрица, полученная из последних "— 9+1 столбцов матрицы А(»~ путем замены в них ненулевых элементов единицами. (Заметим, что матРицы А(») и В» не идентичны соответствующим матРицам разд. 2.5.) Теперь имеем следующую теоРему (Тьюарсон (19766) ), которая подобна теоРеме 2,5,5, б Р. теюарсои 18о Гл. 5. Исключенье Гаусса — Жордака Теорема 5.4.5. Если элемент а®„+ь и где 1)й выбран в качестве главного элемента на й-м шаге метода б)Е, то локальное заполнение дается (51)-м элементом матрицы бю равной О =ВВ'В, (5.4.5) где „— матрица, полученная из матрицгя Вь путем заменьс всех ее нулей единицами, а всех единиц нулями.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
