Главная Промышленная автоматика.

Лемма 6.6. Если А - невырожденная верхняя (нижняя) треугольная матрица, то матрицы Ац и А из леммы 6.5 обратимы и являются верхними (нижними) треугольными.

Доказательство. Допустим, что А - верхняя треугольная матрица. Для случая нижней треугольной матрицы доказательство аналогично. Очевидно, что Лц- невырожденная верхняя треугольная матрица и, значит, Ai существует. Далее заметим, что А 21=0. Поэтому Д=Л 22-Л 21 ЛЛj2=/4 22-невырожденная верхняя треугольная матрица. □

Теорема 6.2. Пусть М (п) - время, требуемое для умножения двух (пХп)-матриц. Если 8М{т)М(2m)iM(т) для всех т, то найдется такая постоянная с, что обращение любой невырожденной верхней (нижней) треугольной {пХп)-матрицы А можно вычислить за время сМ (п).

Доказательство. Докажем теорему для случая, когда п - степень числа 2. Очевидно, что в противном случае можно вложить Л в матрицу вида

Л О .0 L

где m+n«2n) является степенью числа 2. Тем самым, увеличив постоянную с не более чем в 8 раз, мы установим наш результат для произвольного п ).

Если п - степень числа 2, можно разбить Л на четыре ((п/2)х Х(/г/2))-подматрицы и рекурсивно применить формулу (6.3). Заметим, что Л 21=0, так что А=Л22- Следовательно, для обращения треугольных матриц Лц и Д требуется 2Т(п/2) времени, для двух нетривиальных умножений еще 2М {п/2) времени и, для того чтобы поставить минус в правом верхнем углу, еще nV4 операций. Из условия теоремы и неравенства М(\)\ выводим, что n/iM {п/2). Таким образом,

Г(1) = 1,

Г(/г)<2г(у) + ЗЛ1(-) для п>2. (6.4)

Легко доказать, что из (6.4) следует Т {п)ЗМ {п)/2. □

6.4. НВП-РАЗЛОЖЕНИЕ МАТРИЦЫ

Один из эффективных методов решения системы линейных уравнений состоит в применении так называемого НВП-разложения.

1) И опять более тщательный анализ дает для произвольного п постоянную с, несильно отличающуюся от наилучшей известной постоянной для случая, когда п - степень числа 2.



Определение. НВ-разложением ) (/пхп)-матрицы Л, пгп, называется представление ее в виде А =LU, где L - нормированная нижняя треугольная (тхт)-матрица, а U - верхняя треугольная (тХ/г)-матрица.

Уравнение Лх=Ь, где А - это (пХп)-матрица, х - п-мерный вектор-столбец неизвестных, а Ь - п-мерный вектор-столбец, можно решить, сначала НВ-разложив А в произведение LU в предположении, что это возможно. Затем представим Лх=Ьввиде Lt/x=b. Чтобы получить решение х, решим сначала ty=b относительно у, а затем U\=y относительно х.

Трудность применения этого метода заключается в том, что у матрицы А может не быть НВ-разложения, даже если она невырожденна. Например, матрица

"О Г

невырожденна, ноу нее нет НВ-разложения. Однако если матрица А невырожденна, то найдется такая матрица перестановки Р, что АР- имеет НВ-разложение. Изложим алгоритм, который по любой невырожденной матрице А находит такие матрицы L, U и Р, что А =L[/P.Матрицы L,UviP образуют НВП-разложение *) матрицыЛ.

Алгоритм 6.1. НВП-разложение

Вход. Невырожденная (/гХ/г)-матрица М, п - степень числа 2.

Выход. Матрицы L, U и Р, для которых M=LUP, причем L - нормированная нижняя треугольная матрица, U - верхняя треугольная и Я - матрица перестановки.

Метод. Вызываем процедуру МНОЖИТЕЛЬ(Ж, п, п), где МНОЖИТЕЛЬ - рекурсивная процедура, показанная на рис. 6.4. При описании этой процедуры используются диаграммы на рис. 6.1- 6.3, где затемненная область матрицы представляет ту ее часть, о которой известно, что она состоит из одних нулей.

Каждый рекурсивный вызов процедуры МНОЖИТЕЛЬ происходит на (/пХр)-подматрице А (п Х/г)-матрицы М. При каждом вызове т есть степень числа 2 и трп. Выходом этой процедуры являются три матрицы L, U и Р, показанные на рис. 6.1. □

Пример 6.3. Найдем НВП-разложение матрицы

ГО О О 4

О О 3 О

перев.

По первым буквам слов «нижняя» и «верхняя».- Прим. перев.

По первым буквам слов «нижняя», «верхняя» и «перестановка».- Прим.




Рис. 6.1. Выход процедуры МНОЖИТЕЛЬ.


т/2 т/2




Рис. 6.2. Шаги процедуры МНОЖИТЕЛЬ: а - начальное разбиение матрицы А; 6 - разложение матрицы А после первого вызова процедуры; в - разбиение матриц i/i и D; г - обнуление нижнего левого угла матрицы D. (Отметим, что . можно рассматривать как нормированную нижнюю (или верхнюю) треугольную

матрицу.)





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 [84] 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.002