Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 173
Текст из файла (страница 173)
Так же, как и в случае прямой подстановки, время работы составляет О (и2). Поскольку матрица У верхне-треугольная, мы можем переписать (28.21) в следующем виде: иых1+ и12х2+ + и1,„2х„з+ и1,„1х„1+ и1„х„= У1, и22х2 + + и2,„2х„2 + и2,„1х„1 + из„х„= уз, и -2, -2Х -2+ и -2, -1Х -1 + и -з,дХв и»-1,>>-1х»-1 + и»-1,»х» Ул-2 > = Ул-1 > и„,„х„= у„ Таким образом мы можем последовательно найти х„, х„1,..., х1. х„= у„/и„,„, х„1 — — (у„1 — и„1 „х„)/и„ Х»-2 1уп-2 1и»-2,п-1Х» — 1 + ип-2,»Х»))/и»-2,п-2 или, в общем виде, и х1= у,— ~ и;х /ии. У=>+1 Процедура ШР ЯО~.УИ для данных Р, 2,, У и 6 находит х путем комбинирования прямой и обратной подстановки. В псевдокоде предполагается, что размерность и хранится в атрибуте тои>а ~.Ц и что матрица перестановки Р представлена массивом к. Часть Чй.
Избранные темы ШР 8оьун(т:,У,я, Ь) 1 и - гоим[Х] 2 $ог1 -1топ 3 йоУ; — Ь„щ — Я 1, Уу 4 1ог г — п йоттпто 1 5 до кя - (у; — ~ ";+з и~х ) (Пт 6 гетигп х Процедура ШР Бсн.чн находит у в строках 2-3 с помощью прямой подстановки, а затем вычисляет х при помощи обратной подстановки в строках 4-5. Наличие внутри каждого цикла неявного цикла суммирования приводит ко времени работы данной процедуры, равному 9 (пз). В качестве примера данного метода рассмотрим систему линейных уравнений 1 2 0 3 3 4 4 х= 7 5 6 3 8 Здесь 1 2 0 3 А= 3 4 4, Ь= 7 5 6 3 8 и мы хотим найти неизвестный вектор х. 1ЛЗР-разложение матрицы А имеет вил 1 0 0 5 6 3 0 0 1 7 = 0.2 1 0 , У = 0 0.8 -0.6 , Р = 1 0 0 0.6 0.5 1 0 0 2.5 0 1 0 (Читатель может самостоятельно убедиться в корректности разложения, проверив выполнение равенства Р А = Ь У.) Используя прямую подстановку, мы находим у из уравнения Ь у = Р Ь: 1 0 0 0.2 1 0 0.6 0.5 1 ут 8 Уг = 3 Уз 7 что дает нам путем вычисления сначала ум затем уз и уз окончательное решение 8 1.4 1.5 Глава 28.
Работа с матрицами Используя обратную подстановку, мы решаем уравнение У х = у относительно х: 5 6 3 0 08 -06 0 0 25 х| 8 хз = 14 хз 1.5 что дает нам требуемое решение исходной системы линейных уравнений — 1.4 х = 2.2 0.6 путем вычисления сначала хз, затем хз и хп Вычисление ЬЮ-разложения Мы показали, что если можно вычислить 1Л)Р-разложение невырожденной матрицы А, то для решения системы линейных уравнений А х = Ь можно воспользоваться простыми прямой и обратной подстановками.
Нам осталось показать, как эффективно найти (Л)Р-разложение матрицы А. Мы начнем наше рассмотрение со случая невырожденной матрицы А размера и х и и отсутствия матрицы Р (или, что эквивалентно, Р = 1„). В этом случае мы должны найти разложение А = 1, У. Назовем матрицы 1 и У Ш-разложением (Ш бесогпроайюп) матрицы А. Наш процесс построения ?Л1-разложения называется метнодам исключения Гаусса (Оапзз е1ппшайоп) Мы начнем с удаления первой переменной из всех уравнений, кроме первого, путем вычитания из этих уравнений первого, умноженного на соответствующий коэффициент.
Затем та же операция будет проделана со вторым уравнением, чтобы в третьем и последующих уравнениях отсутспювали первая и вторая переменные. Процесс будет продолжаться до тех пор, пока мы не получим верхне-треугольную матрицу — это и будет искомая матрица У. Матрица 1, составляется из коэффициентов, участвовавших в процессе исключения переменных. Мы реализуем описанную стратегию при помощи рекурсивного алгоритма. Итак, мы хотим построить Ш-разложение невырожденной матрицы А размером и х и.
Если и = 1, задача решена, поскольку мы можем выбрать 1 = 11 и (1 = А. При и ) 1 разобьем А на четыре части: Часть Чй. Избранные темы 846 где с — вектор-столбец размером и — 1, и — вектор-строка размером и — 1, т а А' — матрица размером (и — 1) х (и — 1). Используя матричную алгебру (проверить полученный результат можно при помощи умножения), разложим матрицу А следующим образом: о А' и/аы 1„д О А' — идат/адд Нули в первой и второй матрицах разложения представляют собой вектор-строку и вектор-столбец размера и — 1 с нулевыми элементами. Матрица ого /ап, т получающаяся тензорным произведением векторов с и гл и делением каждого элемента получившейся в результате умножения матрицы на аы, представляет собой матрицу размером (и — 1) х (и — 1) (тот же размер имеет и матрица А', из которой оиа вычитается).
Получающаяся в результате матрица размером (и — 1) х (и — 1) А' — ого /аы (28.23) называется дополнением Шура (Бспнг сошр1егпепд) элемента адд в матрице А. Из требования невырожденности А вытекает невырожденность дополнения Шура. Почему Предположим, что дополнение Шура представляет собой вырожденную матрицу размером (и — 1) х (и — 1). Тогда по теореме 28.1 она имеет ранг, строго меньший и — 1. Поскольку нижние и — 1 элементов в первом столбце матрицы < ам шт О А' — сиР/ам равны О, нижние и — 1 строк должны иметь ранг, строго меньше и — 1.
Таким образом, ранг всей матрицы строго меньше и. Применяя результат упражнения 28.1-10 к уравнению (28.22), находим, что ранг матрицы А строго меньше и, так что согласно теореме 28.1 мы получаем противоречие с начальным условием невырожденности А. Поскольку дополнение Шура невырождено, мы можем рекурсивно найти его 1Л3-разложение А' — дд иР/адд = Ь' У', где Ь' — нижне-треугольная, а à — верхне- треугольная матрицы. Используя матричную алгебру, получим: < 1 О с/ам 1„ < 1 О дд/ам 1„д (':) )( О А' — ~! ) О Ь'У' (».;)=., Глава 28. Работа с матрицами 1Л.1 РЕСОМРОБ!Т1ОХ(А) 1 и +- гоии1А] 2 $огй — 11ои 3 йо иьь +- аьь 4 1ог 1 — /с+ 1 1о и 5 бо 1св — а;ь/иьь 6 иы — агя 7 1ог г' — /с + 1 1о и 8 аоТо 5 ~+11о 9 бо аб +- ау 10 ге1пгп Ь и У с (сь содержит ьч с им содержит сот и — 1сьиь5 что дает нам искомое 1Л)-разложение.
(Заметим, что поскольку матрица Ь' — единичная нижне-треугольная, таковой же является и матрица Ь; поскольку матрица à — верхне-треугольная, таковой же является и матрица У.) Конечно, если аы = О, этот метод не работает, поскольку при этом должно быть выполнено деление на О. Он также не работает, если верхний левый элемент дополнения Шура А' — тлот/аы равен нулю, поскольку в этом случае деление на ноль возникнет на следующем шаге рекурсии. Элементы, на которые в процессе 1Л-разложения выполняется деление, называются ведущими (р1чо1з), и они располагаются на диагонали матрицы У.
Причина, по которой в 11)Р-разложение включается матрица перестановок Р, состоит в том, чтобы избежать деления на нулевые элементы. Использование матрицы перестановки для того, чтобы избежать деления на ноль (или на малые величины), называется выбором ведущего элемента (р1чо11пй). Важным классом матриц, для которых Ы~-разложение всегда работает корректно, является класс симметричных положительно определенных матриц. Такие матрицы не требуют выбора ведущего элемента, и описанная стратегия может быть применена без опасения столкнуться с делением на ноль.
Мы докажем это в разделе 28.5. Наш код для 1ЛЛ-разложения матрицы А следует рекурсивной стратегии, хотя рекурсия в нем и заменена итеративным циклом (такое преобразование является стандартной оптимизацией процедуры с оконечной рекурсией, когда последней операцией процедуры является рекурсивный вызов ее самой). В коде предполагается, что размерность матрицы А хранится в атрибуте гоша 1А]. Поскольку мы знаем, что в вычисляемой матрице У все элементы ниже диагонали равны О и процедура ШР Богачи к ним не обращается, наш код не заполняет их никакими значениями. Аналогично, поскольку в матрице Ь диагональные элементы равны 1, а элементы выше диагонали — нулевые, код процедуры не заполняет их, ограничиваясь только "значащими" элементами матриц У и Х,. Часть Ч11. Избранные темы Э.3::! 9, '3 4 " 4 .1 !6 9 10 -2 4 9 '!! 3 1 5 ~36 2.'4:.
114:;! 2 2.,1 7 в! 2 3 1 5 4 19 3-' .7. 3 2 3 1 5 6 13 5 !9 !О 23 4 10 !1 31 2 3 ! 5~ ! О О О Р 3 ! 51 6 !3 5 !9 3 1 0 0 10 4 2 4 ! !2 19 10 23 ! 4 1 О 0 О 1 2 4 10 11 31 12 1 7 ! ! 0 О О 3 1. л! Рис. 28.1. Работа процедуры ПИэесомгоз!т!Ох Вычисление 1Л)Р-разложения В общем случае при решении системы линейных уравнений А х = Ь мы можем оказаться должны выбирать ведущие элементы среди недиагональных элементов Внешний цикл 1ог, начинающийся в строке 2, выполняет каждый шаг рекурсии по одному разу. В теле этого цикла в строке 3 ведущим элементом полагается элемент аьы В цикле 1ог в строках 4-6 (который не выполняется, когда 70 равно и) для обновления матриц У и 2" используются векторы и и и7т.
Элементы вектора и определяются в строке 5 и сохраняются в 14ы а элементы и7т определяются в строке 6, после чего каждый элемент и7т сохраняется в иы. И наконец, элементы дополнения Шура вычисляются в строках 7-9 и сохраняются в матрице А (в строке 9 нам не требуется деление на аьы так как оно уже выполнено в строке 5 при вычислении 1!я). В связи с тройной вложенностью в циклы строки 9 время работы процедуры 1Л3 1)есомРОз!т!Оы равно с3 (72 ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
