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

Из условия теоремы вытекает, что 4Л1 (/и/2)(1/2*)Л1 (т). Поэтому

<=1

Так как сумма в правой части сходится и М{т)т, существует такая постоянная к, что Т (т) {knim) М (т). Для алгоритма 6.1 п=т и, значит, Т {n)kM(n). □

Следствие. НВП-разложение любой невырожденной {пХп)-мат-рицы можно найти за О ишгов.

Доказательство. В силу теорем 6.1, 6.3 и 6.4. □

6.5. ПРИЛОЖЕНИЯ НВП-РАЗЛОЖЕНИЯ

В этом разделе мы покажем, как использовать НВП-разложение для нахождения обратных матриц, вычисления определителей и решения систем линейных уравнений. Мы увидим, что каждая из этих задач сводится к задаче умножения двух матриц и, следовательно, любое улучшение асимптотической временной сложности умножения матриц приводит к улучшению асимптотической временной сложности этих задач. Обратно, умножение матриц, как мы покажем, сводится к обращению матриц и, следовательно, задачи умножения матриц и обращения их эквивалентны с вычислительной точки зрения.

Теорема 6.5. Пусть г>0 и а\. Пусть М (п) - время, требуемое для умножения двух матриц, и М (2т)22+е М (т) для некоторого е>0. Тогда матрицу, обратную к данной невырожденной матрице, можно найти за время О (Ж (п)).

Доказательство. Пусть А - невырожденная (пXп)-матрица. В силу теорем 6.3 и 6.4 можно найти НВП-разложение A=LUP за время 0(М(п)). Тогда A--=P--U-L-. Матрицу P-i можно вычислить за 0(п) шагов. Матрицы 1/- и существуют, и их можно вычислить за 0{М(п)) шагов в силу теоремы 6.2. Аналогично за 0(М{п)) шагов можно вычислить произведение P-W-L-K □

Следствие. Обращение {пХп)-матрицы можно найти за 0(n") uiaeoe.

Теорема 6.6. Если функция М (п) та же, что и в теореме 6.5, и А есть (пхп)-матрица, то dtt {А) можно вычислить за 0{М{п)) ишгов.

Доказательство. Применим алгоритм 6.1, чтобы найти НВП-разложение матрицы А. Если он не срабатывает из-за того,



e.S. ПРИЛОЖЕНИЯ НВП-РАЗЛОЖЕНИЯ

что В строке 2 не удалось найти ненулевой столбец или в строке 9 не существует то матрица А вырожденна, и det(/4)=0. В противном случае пусть А-LUP. Тогда det(/l)=det(L) det([/) det(P). Найдем det(L) и det([/), вычислив произведения их диагональных элементов. Так как L - нормированная нижняя треугольная матрица, то det(L)=l. Так как U - верхняя треугольная, то можно вычислить det(t/) за 0(п) шагов. Поскольку Р - матрица перестановки, то det{Л)=dЬl в зависимости от того, представляет Р четную или нечетную перестановку. Вопрос о четности или нечетности перестановки можно выяснить, построив ее из (1, 2, . . ., п) с помощью транспозиций. Потребуется не более п-1 транспозиций, и их число можно сосчитать во время выполнения. □

Следствие. Определитель {пХпуматрицы можно вычислить за 0(n*") шагов.

Пример 6.4. Вычислим определитель матрицы М из примера 6.3. Там мы нашли НВП-разложение

Определители первого и второго сомножителей равны произведениям диагональных элементов, т. е. соответственно 1 и 24. Осталось установить, какую перестановку - четную или нечетную - представляет третья матрица Р. Так как Р представляет перестановку (4, 3, 2, 1) и ее можно получить двумя транспозициями (1, 2, 3, 4): =>(4, 2, 3, 1)=>(4, 3, 2, 1), заключаем, что она четна и det(P) = l. Таким образом, det(M)=24. □

Теорема 6.7. Пусть функция М (п) та же, что и в теореме 6.5, А - невырожденная (пхп)-матрица и Ь - вектор-столбец разжрности п. Пусть \=[хи х2, XnV - вектор-столбец неизвестных. Тогда систему линейных уравнений Лх=Ь можно решить за 0{М{п)) шагов.

Доказательство. С помощью алгоритма 6.1 построим НВП-разложение А=ШР. Тогда система LUPx=b решается в два шага. Сначала решаем систему Ly= b относительно у, а затем - систему UPx=y относительно х. Каждую из этих подзадач можно решить за 0{п) шагов, применив метод исключения, т. е. сначала найти значение уи подставить его вместо переменной уг, затем найти значение у2 и т. д. НВП-разложение можно построить за 0{М(п)) шагов в силу теоремы 6.4, а систему LUP\=b можно решить за 0(п) шагов. □



Следствие. Систему из п уравнений с п неиавестньши можно решить за О ишгов.

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

Теорема 6.8. Пусть для умножения двух {пхп)-матриц и об-раш,ения (пХп)-матрицы требуется соответственно М{п) и I(п) времени. Предположим, что 8M (т)>Л1 (2т)>22+е М(т) при некотором г>0 и аналогичные неравенства верны для I (п). Тогда М (п) и I (и) совпадают с точностью до постоянного множителя.

Доказательство. Теорема 6.5 показывает, что / CiM (п) для некоторой постоянной Ci. Чтобы установить неравенство М (n)C2l [п) для некоторой постоянной с, рассмотрим произвольные (/гХ/г)-матрицы Л и S. Так как

7 -А АВ

О / -В

lO О / .

то можно вычислить произведение АВ, обращая (ЗпхЗп)-матрицу. Следовательно, М (п)1 (ЗпХ/ (4пХ64 / («). □

6.6. УМНОЖЕНИЕ БУЛЕВЫХ МАТРИЦ

В разд. 5.9 изучалась задача умножения двух булевых матриц с элементами из замкнутого полукольца {О, 1}, в котором сложение и умножение определяются таблицами

1 1

Было показано, что умножение двух булевых матриц эквивалентно вычислению транзитивного замыкания графа. К сожалению, замкнутое полукольцо {О, 1} не является кольцом, и поэтому к умножению булевых матриц неприменимы ни алгоритм Штрассена для умножения матриц, ни другие результаты, изложенные ранее в этой главе.

Очевидно, что обычный алгоритм умножения матриц требует О (п) шагов 1). Тем не менее известно по крайней мере два способа

) Если почти все элементы матрицы-произведения равны 1, то можно перемножить две булевы матрицы в среднем за время 0(п), вычисляя каждую сумму





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.0035