Разряженные матрицы. Р. Тьюарсон (984138), страница 25
Текст из файла (страница 25)
<о4. 162 Г*. 7. Собственные аноченин и собственныв векторы Доказательство. Из соотношений (7.4.3) и (7.4,4) ! из определений йю» и В» и из условия, что в матрице 41»1 (д+ й — 1)-й и (р+ и — 1)-й столбцы становятся с . ответственно й-м- и (й+ 1)-м столбцами, имеем где Ьд, — (ю', ю))-й элемент матрицы В» и 2 означаег юы булеву сумму столбцов.
Теперь что завершает доказательство теоремы. Принимая во внимание теоремы 7.4.5 и 7.4.6 и то, что (ю, 1)-й элемент матрицы В» такой же, как н (1+ '+ 1, 1)-й элемент матрицы Нм мы можем, очевидно, выбрать главныи элемент аю»+1» ю+» ю следующим обри. зом: дю»ю'+ ую»ю,,=ш(п(Я>+ уюю»11 ), 1Ф1+ 1, (7.4.8) где дюю»11 — (ю, 1)-й элемент матрицы 6 '). Это должно, вообще говоря, минимизировать заполнение. Более простой, хюття и менее точный, путь для вы.
бора главного элемента, основан на зависимости заполнения от общего числа ненулевых элементов а з-й строке и 1-м столбце. Поэтому мы выбираем з и( следующим образом. Пусть В» определено так, ка" это сделано для теоремы 7.4.5, а )т» так, как. для фоР' мулы (3.2.2), но (т» — (л — й)-мерный вектор. строка все элементы которого равны единице.
Тогда с Уче том формул (3.2.2) и (3.2.3) уравнение ю ~1 — 1, (7,4.9) йю»1 = пинаю»1, ю,ю ы цт может быть использовано для определения з и й ') См, примечание иа стр. 164. 7.б. Библиография и комментарии 7.5. Собственные векторы Собственный вектор х, соответствующий известно- „„собственному значению л, может быть легко поен потому, что уравнение Ах = йх означает, что (А — лг') х = О. (7.5.1) 5аметнм, что А — 57 — особенная матрица, так как ~ О, и поэтому мы могли бы опустить одно из уравнений системы (7.5.1) ') и решить оставшуюся систему неоднородных уравнений для и — 1 отношений компонент вектора х.
Ошибки округления и другие вопросы вычислений для этого случая упоминаются у Фокса (1965). Прн решении неоднородной системы уравнений могут быть использованы различные способы минимизации заполнения и (или) вычислительных затрат, приведенные в предыдущих глфвах. 7.6. Библиография н комментарии Различные прямые методы вычисления собственных значений и собственных векторов полных матриц н анализ ошибок даны у Фокса (1965) и Уилкинсона (1965).
Вращения Якоби для ленточных матриц описаны у Рутисхаузера (1963) и Шварпа (1968). Заполнение для методов Гивенса и Хаусхолдера рассматри.вается Тьюарсоном (1970а). Также у Тьаюрсона (!970с) излагаются некоторые способы минимизации заполнения при приведении заданной матрицы к форне Хессенберга. '! Зяесь автор ошибается: можно опустить лишь то иа ураваеиий (7БЛ), которое является линейной комбинацией прочих!— гграм, ред.
Глава В ИЗМЕНЕНИЕ бАЗИСА И РАЗНЫЕ ВОПРОСь4 8.1. Введение В некоторых приложениях необходимо вносить не. которые изменения в матрипу А после того, как обрат. ная к ней матрица (в форме РН или ЕГ!) определена, Это имеет место, например, в линейном программировании, где на каждом шаге симплексного метода один столбец «базнса» заменяется «небазисным» столбцом,' и обратная матрица базиса изменяется так, чтобы стать обратной к измененному базису (Орчард-Хейс (1968) ).
Другим примером, из области электрических цепей, является метод, известный под названием ме. тода разбиения Крона (Крон (1963)), где изменение в матрице А задается матрицей малого ранга. В этой главе мы рассмотрим некоторые методы включения результатов изменения матрицы А в обратную к нея матрицу (Данциг (!963б); Бартельс и Голуб (1969); Брейтон и др. (1969),; )Форрест и Томлин (1972)), В равд. 8.2 мы опишем различные методы изменения форм ЕН и РН, если изменен один столбец в заданной матрице (изменения в строках матрицы А могут быть учтены путем рассмотрения изменений соответ.
ствующих столбцов матрицы А'). Метод разбиения Крона для разреженных матриц описан в разд. 8.3. Разложение на множители матрицы, обратной к А, дается в равд. 8.4. Оно получается, если обращение матрицы У производится способом, отличным от того. который приведен в разд. 2.2. 8.2. Изменение обратной матрицы А-' при изменениях в столбце матрицы А Предположим, что имеется ЕГ1, РГ! или одна нэ других форм обратной к А матрицы. Формы ЕН " РГ! заданы соответственно формулами (2.4.1) я В.2. Изменение обратной матрицы 165 где д» = А йз. Поэтому (а+ н А =(1и+(й~,"+и — ед)йД А '=ТРА ', (8.2.2) где, принимая во внимание разд.
5.2, Т =1„+ фа) — е )е'„, (8.2.3) прячем й(лео ~(а)— ю й(ими и *«)= ! ~а й(и+И ' зз (8.2,4) Гаким образом, А-' имеет на один множитель больше, ми разложение на множители матрицы А-'. Напомнам, что только ненулевые элементы вектора ь(а) долж. ны храниться для вычисления матрицы Т . Другие столбцы матрицы А могут быть заменены подобным же способом. Конечно, каждая такая занена добавляет еще один множитель (подобный маттнце Та) к обратной матрице. Если требуется изменить )плько небольшое число столбцов, то разумно пользоннться изложенным здесь методом. С другой стороны, нези заменяется ряд столбцов матрицы А, как в лимпйном программировании, то было бы желательным забавиться от тех множителей матрицы А-', которые (пответствуют замененным столбцам исходной мат'тнцы А.
Каждый из этих столбцов можно представить (82.4). Пусть А обозначает матрицу, полученную из „атриды А путем замены ее (1-го столбца новым столб„ом, скажем а . 14ы опишем несколько возможных путей решения вопроса построения матрицы А-' по нзнестной матрице А-'. Первый метод Если А-' обозначает какую-либо форму обратной н А матрицы, то каждый столбец матрицы А — 'А совпазет с соответствующим столбцом единичной матрицы за исключением (1-го столбца. Действительно, няесм А 'А=1„+(А йз — е)е,=! +(йз"~~~ — ез)ез, (8.2А) !Еб Гл.
8. Изменение базиса и разные заарасьт себе удаленным из «бтазиса», а новый столбец (кото рым заменяется исходный) — вставленным на его ме, сто, В следующих двух методах, пригодных только дл„ формы ЕГ1, исключается множите.ть, соответствунотцин удаляемому из базиса столбцу.
Второй метод Мы покажем, что замена аа на йа приводит к заме, щению матрицы Ет» в формуле (2.4.1) матрицей Т„ определяемой формулой (8.2.3), причем вектор ~й дается соотношениями б(т) 1 й(е> = — — и Ф д, и ~'«1 = —,, (8,2,5) ш ' ш ' б~~ где Очевидно, матрица Е, ЕнА, за исключением д-и столбца, совпадает с' вейхней треугольной матрице! А<а+'н, определяемой формулой (2.2.5). Обозначим д-! столбец матрицы Е„... Е,А через й~"+". Как н н равд.
2.2, разложение на множители матрицы, об ратной к матрице Е ... ЕнА, получится, если главньк элементы брать на ведущей диагонали. Так как мат рицы Е„... ЕнА и Е„... Еьй отличаются только и-н столбцом, то ввиду соотношений (2.2.9), (2.2.10) (2.2.11) матРицы Ете„.н ... (тнЕп ° ° ° ЕнА и Уа+н .. ... Ет„Е„... Е,А будут совпадать, за исключениен и-го столбца. Столбец д для первой из этих двух мат риц выражается формулой (8.2.6). Из формул (8.2.3) (8.2.5) и (8.2.6) видно, что матрица Та преобразуе' е1-й столбец матрицы Уе+н ...У„Е ... Енй в вектор столбец еа и не повлияет на Другие столбцы. Друпон словами, матрица Т Ет т, ... Ен„Е„...
Е,А и матриж 13 11 и, Ет„Е„... Е,А совпадают. Поэтому Е«=Етн ... Ет„Е„... ЕнА=— — = Ет ... и~,т (т~~, ... Ет„Е„... Е,А А '=Етн ... Ц,Т«Ц,т (1„Е„... Еп (8.2.Т В2. Изменение обратной матрицы !67 Чтобы изменить другой, д,-й столбец, после того „нк д-й столбец был заменен, необходимо учесть две возможности: 1. Если д,~(е), то Т, замещает У и а,"",=(7»еы "(7»-~ »(7».ь " (Тн и" Т,й», ° 2, Если д,) а, то Т, вставляется непосредственно после Т„причем н матрица У», не замещается.
Из приведенных двух случаев ясно, что столбцы следует, если можно, замещать в порядке, уменьшения нх индексов (Брейтон и др. (1969)). Третий метод Этот метод особенно'пбдходит для программ ли. нейного программирования (Брейтон и др. (1969); Форрест и Томлин (1972)). Как и ранее, пусть а, Фй столбец матрицы А, замещается столбцом й» н А обозначает измененную матрицу. Если Аы+н= =(.„... Р,А и 0=й„... Л,А, то только д-е столбцы натрнц А~"+и и У различны.
Теперь определяются элементарные матрицы О, и Т„такие, что последние н — д элементов а-й строки матрицы (т»А'"~'! равны нулю и е» является д-м столбцом матрицы У»~= -Т»ЦА'"+ '. Очевидно, матрица 0~»~ легко обращается, так как она получается из матрицы у путем замены ее д-й строки и е)-го столбца соответственно на е' и е .
узким образом, принимая во внимание формулй (22.9), (2.2.10) и (2.2.11), У!»' ' получается из матрацы уе ... у„, если исключить матрицу у и понежить в формуле (2.2.11) каждое й!е! = О, й > д. Ясно, что А '=0'»~ Т 0 й„... У, (8.2.8) 1бз Гл. 8. Изменение базиса и разные вопросы Чтобы воспользоваться этой формулой для зычно лениЯ А — ', нам нУжно опРеделить матРицы Оа и Г Это может быть осуществлено следующим образок, Я Если 0а =1„+ еД", (8.2 9) приЧем е' + яма' = е'у ... у а а+1 ''' и' то, принимая во внимание условие А "+'е; = Уеь 1 Ф !), имеем л<О О1 1л (8.2АО) Так как а',О„А!и+о=А!!!е',, исключение Гаусса — Жор дана, произведенное для а-го столбца матрицы О,А!""'! не окажет влияния на другие столбцы, и матрица г! будет определяться той же формулой (8.2.3), в кото.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
