Самарский А.А. Гулин А.В. - Численные методы (1078412), страница 14
Текст из файла (страница 14)
В большинстве существующих стандартных программ одновременно с решением системы линейных алгебраических уравнений (1) вычисляется определитель матрицы А. Пусть в процессе исключения найдено разложение (22), т. е. построены матрицы Е н (г'. Тогда бе1(РА) =((е1 1. ()е1 У=()е1 1.=1„(м...1 „„ т. е. произведеяие диагональных элементов матрицы Е равно определителю матрицы РА. Поскольку матрицы РА и А отличаются только перестановкой строк, определитель матрицы РА может отличаться от определителя матрицы А только знаком.
А именно, бе1(РА) =де(А, если число перестановок четно, н ()е1(РА) = = — ()е1А, если число перестановок нечетно. Таким образом, для вычисления определителя необходимо знать, сколько перестановок было осуществлено в процессе исключения. Если матрица А вырождена, то при использовании метода Гаусса с выбором главного элемента по столбцу на некотором шаге исключения й все элементы )(-го столбца, находящиеся ниже главной диагонали и на ней, окажутся равными нулю. Действительно, рассмотрим укороченную систему (см. (11) из 5 1), которая получается на й-м шаге исключения: (й-1) («-1) («-1) айй хй+ ...
+ ай,„х~ =)« (й-')х ай„л «+... +ай„, х (24) («-1) (й — Ц ()г — 1) а й хй+ ... + аг„х,„=),„ При решении системы (24) могут возникнуть два случая". 1) хотя бы один из коэффициентов айй',а~„'й,...,а(й" отличен от (й-1) (й-1) ()г-1) нуля; 2) айй =ай„,й=... =а й =О. Если для всех 6=1, 2, ... ..., а( реализуется первый случай, то систему (1) можно решить методом Гаусса с выбором главного элемента по столбцу, н, следовательно, ()е1А~О.
Если же ()е1 А =О, то при некотором й реализуется второй случай. Прн этом дальнейшее исключение становится невозможным и программа должна выдать информацию о том, что определитель матрицы равен нулю. зя ат $4. Обращение матрицы Нахождение матрицы, обратной матрице А, эквивалентно решению матричного уравнения АХ=Е, (1) где Š— единичная матрица и Х вЂ” искомая квадратная матрица, Пусть А= [ао), Х= [хо[. Уравнение (1) можно записать в виде системы гпз уравнений ~ амхгу=бу, в з 51=1,2,...,т, (2) где бе=1 при 1=1 и бн — — 0 при (Ф1. Для дальнейшего важно заметить, что система (2) распадается на лз независимых систем уравнений с одной и той же матрицей А, но с различными правыми частями.
Эти системы имеют внд Ах'п=бо', 1=1, 2, ..., гн, (3) где х"'= (хо, х„, ..., х,)', У вектоРа бо' Равна единице 1'-Я компонента и равны нулю остальные компоненты. Например, для матрицы второго порядка система (2) распадается нв две независимые системы амхо+ а,злз1 — — 1, апх,з+ а,зхзз = О, и амлм + аззлм — О амлм + амкзз = ! .
Для решения систем (3) используется метод Гаусса (обычный или с выбором гланного элемента). Рассмотрим применение метода Гаусса без выбора главного элемента. Поскольку все системы (3) имеют одну и ту же матрицу А, достаточно один раз совершить прямой ход метода Гаусса, т. с. получить разложение А =ЕУ и запомнить матрицы Е и 1Е Для этого, как мы знаем (см. 3 1), требуется сделать лг(пг' — 1)/3 действий умножения и деления.
Обратный ход осуществляется путем решения систем уравнений ЕУ б У (Уы Уз/ ° 'У иг) (4) Егхот = ун>, ! = 1, 2, ..., и, (5) яв с треугольными матрицами Е и Ег. Решение системы (5) при каждом 1 требует 0,5 т(пз — 1) действий, Для решения системы (4) надо еще добавить т делений на диагональные элементы матрицы Е, так что здесь потребуется 0,5гп(па+1) умножений и делений. Всего при каждом 1' на обратный ход затрачивается 0,5(т — 1)пз+ +0,5(пг+ 1)гп=гп* действий, а для всех 1 требуется лз' действий. Можно сократить число действий, принимая во внимание специальный вид правых частей системы (4).
Запишем подробнее пер- вые ) — 1 уравнений системы (4): 1ыУы=й )му„+ 1, дм= О, 1; кау„+ 1;, „д„+ ... + 1; ь; „у... = 6. Учитывая невырожденность матрицы Е, отсюда получим до=ум= ° ° .=у!-в=6. При этом оставшиеся уравнения системы (4) имеют вид )УУУ =1 ! гУьч+ !6)тУ)~-ь) + ° ° + (нУУ =() 1=1+1, 1+2,..., т. Отсюда последовательно находятся неизвестные дк по формулам Г-1 )мам уу= — =~, 1=1+1,1+ 2,...,т, (6) !и Уд= !/(ьь (7) Подсчитаем число умножений н делений, необходимое для проведения вычислений по формулам (6). При фиксированном ! для вычислений по формуле (6) требуется 1 деление и 1 — ) умножений. Вычисления по формулам (6), (7) при фиксированном ! потребуют !+ т ..+ ) (и — )-)-2) (т — )+!) 2 ! /1 действий.
Наконец, решение указанным способом систем (4) при всех 1= 1, 2, ..., т потребует — '~" (т — 1' + 2) (т — у + 1) = — '~„"А (А + 1) = 2 2 6 )=з А — — ! действий. Общее число действий умножения и деления, необходимое для обращения матрицы указанным способом, и (тз — !) т' (т — !) ! т(т+ !) (и+ 2) а 3 2 6 Тем самым обращение матрицы требует не намного больше времени, чем решение системы уравнений. 5 5. Метод квадратного корня 1. факторизация эрмитовой матрицы.
Метод предназначен для решения систем уравнений Ах=) (1) с симметричной (в комплексном случае — эрмитовой) матрицей. Он основан на разложении матрицы А в произведение А = 5'()5, (2) где 5 — верхняя треугольная матрица с положительными элементами на главной диагонали, 5' — трапспонированная к ней (или комплексно сопряженная) матрица,  †диагональн матрица, на диагонали которой находятся числа, равные ч-!. Возможность представления (2) можно получить хан следствие теоремы об 5и-разложении (см. $2). Пусть все угловые миноры матриды А отличны от нуля.
Тогда справедливо разложение А=Ли, где 5 — нижняя треугольная матрица, имеющан обратную, и и — верхняя треугольная с единичной диагональю. Представим матрицу 5 в виде произведения 5=МК, где М вЂ” нижняя треугольная матрица с единичной главной диагональю н К вЂ” диагональная матрица, главная диагональ которой совпздает с главной диагональю матрицы )., т. е. К=а!аа](п, (еь .... ! -]. (3) По условию диагональные элементы матрицы !. отлнчны от нуля, и, следовательно, разложение 5=МК существует.
Тогда А=мки, (4) где М и и — треугольные матрицы с единичной главной диагональю н К вЂ” диагональная матрица, имеющая обратную. Иэ условия А =А получаем и'К М'= мки» к- м-'и.к =им*- . (5) Матрица, находящаяся в левой час~и равенства (5), является нижней треугольной, а в правой части — верхней треуголыюй. Поэтому иэ равенства (5) следует, что обе матрицы иМ* †' и К-'М-'и'К* являются диагональными.
Лалее, поснольку матрица иМ -' имеет единичную главную диагональ, она является единичной мвтрвней, иМ' — ~ К, т. е. и=М'. Отсюда и из (4) получаем разложение А МКМ'. (б) Представим матрицу К, определенную согласно (3) в виде произведения трех диагональных матриц; К !К!'ь)У]к]', где обозначено !К]~*=5!аа!У]! 1, У]! ],".,)"]! 11 0 б)ад]з)пп(н, мкп(зз,..., з)яп! ]. Тогда из (6) получим разложение (2), где Я=]К] "М* — верхняя треугольная матрица с положительными элементами на главной диагонали.
2. Пример. Если разложение (2) получено, то решение системы (!) сводится к последовательному решению двух систем уравнений с треугольными матрицами 5Ву=.(, (7) 5х=у. (8) Покажем на примере матриц второго порядка как можно получить разложение (2). Пусть А — действительная симметричная матрица А= ~"' 70 Будем искать 5 и 0 в виде 5 [512 212~ 11 [а11 О 1 где каждое из чисел 1/„, 1/„мпжЕт быть либо + 1, либо — 1. Тогда 5 /15 11 11 11 12 11 5 а 1 2 й 111112211 5 011 + 5 »2 и из условия (2) получаем трн уравнения: яп2/11 = ам, 5115121211 = амь 5122/11 + 5212/22 = а22. Из первого уравнения находим 2/„=51дн а„, 5„=У(~а„[.
Далее, если а„чьб, то 5,1=а„/(5„1/„), н, наконец, 2.У 12 5221122 а22 512'2111 т. е. (п5) 1= Х г/»5» = 2/»5» Кроме того, 5"= [5„), поэтому 21 (5*О5)» =" ,5»2/»521, 1--1 где я„ — число, комплексно сопряженное я„. Из условия ( 2 ) полу- чаем уравнения ~ я11415» = а»Ч 1, /= 1, 2, ..., т, 1=1 ,'(9) Так как матрица А эрмнтова, можно, не ограничивая общности, считать, что в системе (9) выполняется неравенство 1(/.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
