Фаддеев, Фаддеева - Вычислительные методы линейной алгебры (947503), страница 31
Текст из файла (страница 31)
После аннулирования всех строк в левом нижнем углу за счет добавления подходящих линейных комбинаций первых л строк, мы получим в правом нижнем углу матрицу А Схема (6) может быть видояэменена следующим образом. Очевидно, что аннулирование матрицы — Е, находящейся в левом нижнем углу схемы (6), требует такого же линейного комбинирования первых л срок схемы, как при получении единичной матрицы Е Очевидно, что такой же прием может, быть применен для вычисления линейной неоднородной формы с,х,+ ...
+с„х„+с[. Разница ' будет только в том, что в правом нижнем углу нужно записать вместо 0 свободный член а, так что исходная схема имеет вид: 175 э 22[ ЗАДАЧА ИСКЛЮЧЕНИЯ в левом верхнем 'углу вместо матрицы А. Поэтому вычисления можно проводить так. Составим матрицу [А, Е[. Посредством деления первой строки на ап сделаем первый элемент первой строки равным единице. Затеи получим нуль в первом столбце за счет добавления ко всем строкам первой, умноженной на подходящие множители. Дзлее получим единицу на месте второго элемента второй строки, посредством деления, и нуль на месте всех остальных элементов второго столбца, за счет добавления второй строки к остальным (в частное~и к первой).
Через л шагов мы получим на месте матрицы А единичную матрицу, а тогда на месте Е окажется матрица А По ходу процесса можно как угодно переставлять строки, что позволяет избегать деления на числа, близкие к нулю, если матрица не очень плохо обусловлена. Описанному процессу можно дать другое толкование, Вспомним, что линейное комбинирование строк равносильно умножению слева на некоторую матрицу. Обозначим череа В,, В,, ..., В„ последовательные матрицы, умножение на которые соответствует окончани:о 1-го, 2-го, ..., и-го шагов процесса, Ясно, что матрицы, получа)ощнеся по ходу процесса, будут [А, Е[, [В,А, В,[, [ВЯА, Ва[, ...
..., [В„А, В„]. У матрицы В,А первый столбец совпадает с первым столбцом единичзой матрицы, у матрицы В,А уже первые два столбца совпадают со столбцами единичной матрицы и т. д. Обозначим через (г( ' вектор, компоненты которого равны элементам 1-й строки матрицы В„, через А 1-й столбец матрицы А. Из сказанного выше ясно, что [А), (г; )=йа пРи /. )г. Сам процесс построения векторов г') ) в точности совпадает с описанным в Э 9 процессом построения двойственного базиса.
Двойственный базис здесь строится к базису, состоящему из столбцов матрицы А, исходя из системы координатных векторов. Выпишем формулы, соответствующие описанному процессу. (г[ = (1, 0 , О) Ь з = (О. 1, О) Ъ'~~ = (О, О, , 1) „,)ьа) ) „,)А-Ц (АА.))г- ) ФА)=Ъ("-') — (А, Ъ(а-т,У'). ) = 1 — ) А А Г Вместо единичных векторов можно брать любую другую систему линейно-независимых векторов.
Однако при неудачном выборе начальной системы векторов может случиться, что одно из скалярных произведений [Аь, (г)," ')) окажется равным нулю нли станет близким к нулю, В частности, для 176 точные методы вешания систем липвйных кялвнвний [гл. и координатной системы векторов это будет иметь место, если один нз главных миноров матрицы А равен нулю илн близок к нулю. Следует отметить, что если взять в качестве системы векторов Ъ'> , И,, ..., Р ь столбцы Ав матрицы А, то, как легко видеть м> ю> .,в> (А„, г'1" '~) ~ О. Это следует из того Я 12), что матрица (А,, А,) (А,, Ая)...
(А,, А„) (Аа, А,) (А,„А>)... (Аю А„) (А>н А,) (А>н А>) ... (Агн А„) положительно определена, и, следова>ельно, все ее главные миноры положнтелы>ы. Отметим также, что процесс проходит хорошо, если за векторы Ь'Г>, ..., '>>~~> ваяешь строки матрицы, близкой к обратной. В работе Хестннса [4[ рекомендуется для обращения плохо обусловленных матриц пользоваться описанным процессом, проводя его сначала исходя из столбцов матрицы А, а затем, с целью уточнения (возможно несколько раз), исходя из полученного приближения к обратной матрице.
Результату исключения можно придать матричную форму. Это дает возможность получить некоторые обобщения. Именно, решение системы х,, ..., х„ в матричном виде можно записать как столбец ==А 'Г, а значение линейной формы с,х,+ ... +с„х„— как число СА 'В. Такое представление указывает путь для вычисления более сложного выра>кения СА >В, где С н В некоторые прямоугольные матрицы, иа которых С состоит из п столбцов, а В из а строк, причем число столбцов В и число строк С безразлично. Действительно, элемент 1-й строки н >г-го столбца матрицы СА ' В есть число с;А (>а, где с; есть Г-я строка матрицы С, а (>ь к-и столбец матрицы В.
Поэтому вычисление элементов матрицы СА 'В можно производить методом исключения. примененным к схеме А [В (7) — с~Го )77 9 221 ЗАДАЧА ИСКЛЮЧЗНИЯ После аннулирования элементов, находящихся в левом нижнем углу, за счет добавлении линейной комбинации первых л строк мы получим в правом нижнем углу матрицу СА ' В. Очевидно, что при одновременном изменении знаков всех элементов матриц В и С результат не меняется, так что схема (7) равносильна схеме л~ — в С~~ О (7') Вычисление обратной матрицы для матрицы А можно осуществлять при помощи схемы вл(~ в (8) в которой в качестве матрицы В моакет быть взята произвольная незырожденная л~атрица.
Применение схемы (8) по существу равносильно применению описанного выше процесса биортогонализации исходя из системы векторов, компоненты которых образуют строки матрицы В. В частности, процесс при В = А' равносилен процессу биортогонализации столбцов матрицы А. Для вычисления произведения СА 4 В можно кроме схемы (7) пользоваться транспонированной (с точностью до знаков В и С) схемой (9) — В ~~Π— В (!О (9') где А' — матрица, транспонированная с матрицей коэффициентов системы, С' — столбец, составленный из коэффициентов вычисляемой линейной формы, Р' — строка из свободных членов. Справедливость этого построения легко обосновывается непосредственно, без ссылки на приведенные результаты. Действительно, если мы умножим первые а стРок схемы (9') на кг, ха...., ли и добавим к последней, 12 Заа.
Яти Д. К. Фаддеев а В. Н. Фаддеева При вычислении по этой схеме мы получим в правом нижнем углу матрицу (СА ' В), так как (СА ' В) = В'(А') ~С'. В частности, для вычисления значения линейной формы с,х, + + саха+ ... + свхв можно также пользоваться схемой 178 точныг. методы ввшвния систвм линвйных твхвнаний [гл, и мы получим нуль в левом нижнем углу и с,х,+саха+ ... +с„х„ в правом нижнем углу. Аналогично, для решения системы АХ= Р мы можем пользоваться схемой А' ((Е (10) Схемы (7) и (9) могут быть применены для вычисления А 'В.
Дчя этого достаточно положить С=Е в этих схемах. Для обращения матрицы наряду со схемой (6) можно пользоваться схемой АДЕ $ (! 1) Прн этом после окончания процесса мы получим в правом нижнем углу матрицу, транспонированную с А '. Таким образом, для каждой из разобранных задач мы имеем две схемы, определяемые или матрицей А или ее транспоннрованной. Отметим, что целесообразно пользоваться той схемой, которая в ниж- нем левом углу содержит наименьшее число строк. Так, в задаче решения линейной системы без обратного хода целесообразно поль- зоваться схемой с транспоннрованной матрнцей, в задаче вычисления произведения А В в схемой с транспоннроваиной матрицей, в слу- чае, если число столбцов в В меньше л, и схемой с данной матрицей, если число столбцов в В больше и.
В табл. П. 11 дается обращение матрицы методом биортогонализации столбцов. В графах 1, П, !П, !Ч записываются компоненты столбцов матрицы А и компоненты последовательно вычисляемых векторов Рг !ю В графе Ч, для контроля, выписываются (Аю Ъф), в графе ч'! числа с;в=(АюР, ), в графе ЧП числа с;= —.
В последних четырех !а — цт 1 см строках граф ! — Гт' получается А '. Контрольное умножение обратной матрицы на матрицу А показало, чтомаксимальныйэлементŠ— А 'А по модулю не больше 0.0000>. В табл. П. 12 мы приводим решение системы, проведенное по схеме (10). Как обычно, последний столбец является контрольным. Его эле- ментами являются строчные суммы. Отметим, что прн решении системы по схеме (10) число операций немного превосходит число операций по способу Гаусса.
Однако однообразие процесса, именно в отсутствие обратного хода, нередко делает этот способ более удобным, 180 точные методы вешания систем лянейных хвавненнй [гл. и а в качестве  — матрица 0.25 0.30 0.15 0.20 ОА5 0.50 0.30 0.40 О 65 О 70 0 45 О 60 0.85 0.90 0.60 0.80 Вычисление А 'В произведено по схеме 19) при С' = Е. В результате вычислений — 1.2З753 — 1.25780 — 0.94295 — 1.25728 0.01847 0.04348 — 0.00491 -- 0.00655 !.00394 1.03916 0.72652 0,96871 А 'В = 1А5096 1.48240 1.06466 1 А!957 таллина п,г2 Решение системы линейных уравнений методом исключения з.ш ЗЛЗ з.оз ЗЛ2 — 2,40 1 0.42 О.МЗаа 0.09320 цигзо -0.37400 3.62 1.65960 1.12520 0.93080 — 1,ЗМОΠ— О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
