Вычислительные методы алгебры и оценивания. И.В. Семушкин (2011) (Вычислительные методы алгебры и оценивания. И.В. Семушкин (2011).pdf), страница 7

Нужно воспользоваться определениями элементарных матриц специального вида [10] и их свойствами. Приведем эти определения и свойства и затем продолжим доказательство.Определение 2.4. Элементарная матрица E есть любая матрицавида E = I + B, где rank B = 1.Упражнение 2.4.векторы.Определение 2.5.матрицы:Докажите, что E = I + xy T , где x и y — некоторыеВведем следующие специальные элементарныеDk — диагональная k-матрица. Имеет единичную диагональ, кроме k-гоэлемента, который не тривиален, т. е. не равен нулю или единице.LCk — столбцово-элементарная нижняя треугольная k-матрица. Имеет единичную диагональ и нетривиальные элементы только в k-м столбце.LRk — строчно-элементарная нижняя треугольная k-матрица. Имеет единичную диагональ и нетривиальные элементы только в k-й строке.UkC — столбцово-элементарная верхняя треугольная k-матрица. Имеет единичную диагональ и нетривиальные элементы только в k-м столбце.372 Стандартные алгоритмы LU-разложенияТаблица 2.1.

Свойства специальных элементарных матрицКоммутативность в операции умноженияCLCi Dj = Dj Li ,i>jUiC Dj = Dj UiC ,i<jRLRi Dj = Dj Li ,i<jUiR Dj = Dj UiR ,i>jRR RLRi Uj = Uj Li ,i≤jCC CLCi Uj = Uj Li ,i≥jCC CCLCi Ui = Ui Li = TiRR RRLRi Ui = Ui Li = TiОперация обращения матрицDi−1получается из Di заменой нетривиального элемента dii на d−1ii с сохранениемзнака этого элементаRCRCRE −1 , где E ∈ {LCk , Lk , Uk , Uk , Tk , Tk } получается из E заменой знаков нетривиальных элементов на противоположныеПрименимость правила суперпозиции вместо перемножения матрицC CLCi Lj Lk ,UiC UjC UkC ,i<j<ki>j>kCCCL = D1 LC1 D2 L2 · · · Dn−1 Ln−1 Dn LnCU = Dn UnC Dn−1 Un−1· · · D2 U2C D1 U1CR RLRi Lj Lk ,UiR UjR UkR ,i<j<ki>j>kRRRL = LR1 D1 L2 D2 · · · Ln−1 Dn−1 Ln DnRU = UnR Dn Un−1Dn−1 · · · U2R D2 U1R D1UkR — строчно-элементарная верхняя треугольная k-матрица.

Имеет единичную диагональ и нетривиальные элементы только в k-й строке.TkC — полно-столбцово-элементарная верхняя треугольная k-матрица. Содержит единичную диагональ и нетривиальные элементы только в k-мстолбце.TkR — полно-строчно-элементарная верхняя треугольная k-матрица.

Имеетединичную диагональ и нетривиальные элементы только в k-й строке.Упражнение 2.5.Докажите свойства этих элементарных матриц,приведенные в табл. 2.1.Продолжим доказательство теоремы 2.3, прерванное на стр. 37.Приведение данной матрицы A к единичной матрицы, составляющее сутьисключения по методу Гаусса-Жордана, запишем в терминах операций свведенными специальными элементарными матрицами:A(n+1) = (TnC)−1Dn−1 · · · (T2C )−1D2−1 (T1C )−1D1−1 A = I.38(2.12)2.4 Алгоритмы метода ЖорданаК результату (2.12) приводит следующий алгоритм Гаусса-Жордана:Начальное значение: A(1) = A.Для k = 1 до n выполнятьA(k+1) = (TkC)−1Dk−1 A(k) ,где элементыDk−1 (k, k) = 1/A(k) (k, k),TkC (i, k) = A(k) (k, k)(i, k), i = 1, 2, .

. . , n, i 6= kсуть множители для нормировки и вычитаний, соответственно.Множители, возникающие в этом алгоритме, образуют так называемуютаблицу множителей. По существу, это матрица, которая займет местоисходной матрицы A по окончании всего алгоритма: −1CCD1 (1, 1)T1 (1, 2)T1 (1, 3)··· C−1C T1 (2, 1)D(2,2)T(2,3)···11(2.13). C−1C T1 (3, 1)T1 (3, 2)D1 (3, 3)··· ............CВоспользуемся свойством в четвертой строке табл.

2.1, TiC = LCi Ui в его−1инверсной форме (TiC )−1 = (UiC)−1(LCi ) , и подставим его в (2.12), а такжесвойствами коммутативности из этой таблицы. Это дает возможность перегруппировать сомножители в (2.12) следующим образом: C −1−1 −1C −1 −1C −1 −1)D···(L)D(L)DA = I.(Un ) · · · (U2C)−1(U1C )−1 · (LCnn2121Второй сомножитель в квадратных скобках совпадает с матрицей L−1 дляLŪ -разложения матрицы A. Первый сомножитель в квадратных скобкахесть матрица U −1 для этого разложения.

Правило суперпозиции, согласнотабл. 2.1, действует для первого сомножителя (в нем индексы матриц убывают слева-направо) и не действует для второго сомножителя. Однако дляCCCL = D1 LC1 D2 L2 · · · Dn−1 Ln−1 Dn Ln правило суперпозиции действует. Суперпозиция, т. е. постановка элементов матриц на принадлежащие им позиции,реализуется автоматически по ходу алгоритма. Поэтому в нижней треугольной части матрицы (2.13) (кроме диагонали) образуется матрица L, диагональные элементы матрицы L представлены на диагонали, но в инверсномвиде (там — обратные значения этих элементов), а выше диагонали расположены элементы той матрицы, для которой действует правило суперпозиции,т. е.

элементы матрицы U −1 . В работе алгоритма перемены знаков у этих392 Стандартные алгоритмы LU-разложенияэлементов не совершались (что надо делать при обращении элементарныхматриц E, согласно табл. 2.1), поэтому эти знаки — неверные.2Чтобы выполнить разложение по методу Жордана, надо воспользоватьсяследующим алгоритмом. На первом шаге в активной подматрице A0 = Aвыбирается главный элемент.

Затем первая строка нормируется, домножается на ai1 и вычитается из i-й строки, i = 2, 3, . . . , n. На втором шагеглавный элемент определяется среди элементов активной подматрицы A(1) .Потом вторая строка нормируется и после домножения на ai2 вычитаетсяиз i-й, где i = 1, 3, . . . , n. В общем случае на k-м шаге в подматрице A(k−1)выбирается главный элемент.

Затем k-я строка нормируется, домножаетсяна aik и вычитается из i-й, где i = 1, . . . , k − 1, k + 1, . . . , n. В результате,чтобы получить требуемое разложение, остается поменять знак на противоположный у всех элементов, лежащих выше главной диагонали.Алгоритм 7. «LŪ −1-разложение» A = LŪ по методу ЖорданаДля k = 1 до nВыбираем главный элемент в A(k−1).Нормируем первую строку матрицы A(k−1) .Для i = 1 до k − 1Вычитаем первую строку матрицы A(k−1) ,(k−1)умноженную на aik , из i-й строки.Для i = k + 1 до nВычитаем первую строку матрицы A(k−1) ,(k−1)умноженную на aik , из i-й строки.Для i = 1 до nДля j = i + 1 до naij = −aijЗамечание 2.6.

Термин «LŪ −1-разложение», который мы используем здесь для краткости в применении к методу Жордана, не должен вводить в заблуждение. Он самом деле отыскивает LŪ -разложение матрицы A,но при его выполнении в одном и том же массиве дает вместо матрицы Ūобратную матрицу Ū −1, причем в следующем виде: единицы главной диагонали матрицы Ū −1 не хранятся, а все другие элементы этой матрицы получаются с противоположными знаками.402.5 Вычисление обратной матрицыУпражнение 2.6.Объясните, как следует понимать словосочетание−1«L̄ U -разложение» Жордана. Докажите, что в этом случае выполняетсяразложение A = L̄U , но матрица L̄ получается в виде обратной матрицы снеправильными знаками ее внедиагональных элементов.Замечание 2.7.Чтобы сэкономить процессорное время, целесообразно везде пользоваться обратными величинами ведущих элементов, какэто сделано на диагонали в таблице множителей (2.13).2.5Вычисление обратной матрицыЕсть два способа вычисления обратной матрицы A−1: через решение системы Ax = f с различными правыми частями f и непосредственно черезразложение матрицы A в произведение треугольных матриц.

В первом способе правая часть f последовательно пробегает значения столбцов ei единичной матрицы I, при этом для каждой из них найденное решение x системыAx = f образует i-й столбец искомой матрицы A−1. Это, очевидно, соответствует решению матричного уравнения AX = I, так как X = A−1.Второй способ основан на том, что если A = LŪ, то A−1 = Ū −1 L−1. Этоназывают элиминативной формой обратной матрицы [10], так как здесьA−1 находят непосредственно по разложению A = LŪ, которое само посебе эквивалентно процедуре гауссова исключения (elimination) неизвестных. Рассмотрим этот способ и характеризуем особенности его программной реализации более подробно. Для численной иллюстрации рассмотримследующий пример.Пример21A=322.1. Пусть для данной матрицы A найдено A = LŪ :4 −4 621 2 −2 34 2 11 2 −1 , L =  1 2 , Ū = .8 1 13 2 31 −2 5 0 52 1 2 41Известная особенность реализации такого разложения заключается в том,что результат разложения замещает исходную матрицу, т.

е. имеемисходный массив ⇒ результирующий массив 2 4 −4 62 2 −23 2 −1 1 4 2 1. ⇒ 1 23 8 1 13 23 −2 2 1242 5 0 5(2.14)412 Стандартные алгоритмы LU-разложенияСледовательно, до начала вычисления обратной матрицы A−1 в наличииимеем две матрицы: матрицу L — в нижней треугольной части массива вместе с диагональю, матрицу Ū — в верхней треугольной части массива безединичной (известной по умолчанию) диагонали. Запишем A−1 = Ū −1 ×L−1,где символ × обозначает процедуру перемножения треугольных матриц Ū −1и L−1 в указанном порядке. Тем самым отмечаем, что это должна быть специальная, а не общая процедура, экономящая время вычислений за счетисключения операций умножения на заведомо нулевые элементы сомножителей Ū −1 и L−1.Сомножители Ū −1 и L−1 нужно вычислять также по специальным процедурам, для которых исходные данные Ū и L берутся из массива, названного в выражении (2.14) результирующим массивом после факторизацииA = LŪ .

Результаты Ū −1 и L−1 работы этих процедур записываются в этотже результирующий массив.Вывод алгоритмов процедур для L−1 и для Ū −1 основан на свойствахэлементарных треугольных матриц, в частности, на свойстве «суперпозиции вместо перемножения». Для L это свойство означает, что произведениеL = L1 L2L3L4 может быть получено не перемножением элементарных матриц L1 , L2, L3, L4, а суперпозицией (постановкой на свои позиции) нетривиальных столбцов элементарных матриц-сомножителей:LL1 L2L3L4221111 2 1 1211=.3 2 3 312 1312 1 2 421112 14Согласно правилу обращения произведения матриц, L−1 найдем как результат перемножения следующих обратных матриц:L−14−11114 × L−131132 1−1 × L−121−1L−11−122 × 1 1 .32 111121Так как индексы у элементарных нижнетреугольных матриц здесь слеванаправо уже не возрастают, а убывают, операция перемножения × матрицне может быть заменена суперпозицией.

В программной реализации этот422.5 Вычисление обратной матрицысимвол × должен соответствовать некоторой специальной вычислительнойпроцедуре. Все исходные данные для этой процедуры уже предоставленыполученным разложением (2.14). Действительно, инверсию элементарныхматриц, показанных в последнем выражении, получают в самой процедуреприменением простых операций: сначала диагональный элемент из нетривиального столбца каждой элементарной матрицы заменяют на обратный повеличине; затем полученное число берут с противоположным знаком и умножают на каждый поддиагональный элемент. Эти действия соответствуютуказанному выражению, представленному в следующем виде:L−141111/4 × L−13111/3−2/31 × L−1211/2−2/2−1/211 × L−111/2−1/21−3/2−2/211.В действительности это означает, что сначала — на этапе ❶ — результирующий массив из (2.14) пересчитывают по указанным правилам, чтобынайти L−1, приводя этот массив к следующему стартовому виду:1/2 2 −232 2 −23 1 2 2 −1 1/2 2 −1  =⇒  −1/2.3 23 −2  ❶  −3/2 −2/21/3 −2 2 124−2/2 −1/2 −2/3 1/4 (2.15)Чтобы понять, как в этом массиве должна работать процедура вычисления матрицы L−1, рассмотрим произведение матриц перед выражением−1−1−1(2.15) и формально будем перемножать матрицы L−14 , L3 , L2 , L1 справа−1−1 −1налево, т.

е. вычислим L−14 (L3 (L2 L1 )). Процесс такого поэтапного перемножения отразим в табл. 2.2.Из табл. 2.2 видно, что после получения (2.15), т. е. на этапе ❷, пересчитывают только элементы a21 , a31 и a41. В данном случае имеем1/2 2 −231/2 2 −23 −1/21/2 1/2 2 −1 2 −1  =⇒  −1/4. −3/2 −2/21/3 −2  ❷  −1−11/3 −2 −2/2 −1/2 −2/3 1/4 −3/4 −1/2 −2/3 1/4 432 Стандартные алгоритмы LU-разложения−1−1 −1Таблица 2.2. Поэтапное перемножение L−14 (L3 (L2 L1 ))L−14 1111/41/3−2/31111/41L−1311/31/2−2/2−1/3−1/31/3−1/121/6−2/3−1 −1−1−1 L4 (L3 (L2 L1 )) 11/21/21/21 × −1(L−12 L1 )−3/4−1/41−1/2−1 −1(L−13 (L2 L1 )) × 1 1  −1/4×  −11−2/3L−12 × 1L−14 1 × L−131/2−1 1−1/21L−111/2−1/2−3/211−2/21⇐= ❷⇐= ❸1/2−1/41/2−1/3−1/31/3−1/481/24−1/61/4⇐= ❹Далее видно, что на этапе ❸ пересчитывают только a31 , a41, a32 и a42, т.