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

6.4. нвп-разложение матрицы

1 0-

1 0 0 0"

0 1

0 2 0 0

P = PsPi

Таким образом, МНОЖИТЕЛЬ ( 0020 •) дает

ГО О О П 0 0 10 0 10 0 L1 О О 0J

Теперь возвращаемся к вызову МНОЖИТЕЛЬ (Ж, 4,4) в строке 6, причем роль Li, Ui и Pi играют соответственно L, [/ и Р. В строке 7 вычисляем

-О О О П

п гр-.-Г° 3 О 01 О О 1 О 1У иг1 -[4 о О Oj О 1 О О

Li О О 0.

в строке 8

так что после выполнения строки 9

0 0 3 0

0 0 3 0 0 0 0 4

"1 0"

"0

0"

и в строке 10

0 0 0 4

3 О О 4

Предлагаем читателю проверить, что МНОЖИТЕЛЬ (G, 2, 2) выдает

1 0

3 0"

1 0"

0 1

. /2 =

0 1.

Таким образом, в строке 12 Рз~1ц, а в строке 13

Г1 О О О H = U,P, = Ui = [ 2 О О

Следовательно, в строках 14-16 вычисляем

-10 0

-1 0

П 1 П

П 9.

О О О И

П П 1 п



Теперь приступим к доказательству корректности алгоритма 6.1.

Теорема 6.3. Для любой невырожденной матрицы А алгоритм 6.1 вычисляет такие матрицы L, U и Р, что А=Ы)Р.

Доказательство. Детали, необходимые для доказательства того, что различные разложения, изображенные на рис. 6.2 и 6.3, корректны, оставляем в качестве упражнения. Покажем лишь, что

1) в строке 2 процедуры МНОЖИТЕЛЬ всегда можно найти ненулевой столбец и

2) в строке 9 всегда существует

Пусть А будет (тХ/г)-матрицей. Покажем индукцией по т, где т - степень числа 2, что если А имеет ранг т, то МНОЖИТЕЛЬ вычислит такие L, U и Р, что А = ШР н L, U, Р - нижняя треугольная матрица,.верхняя треугольная матрица и матрица перестановки рангов т, т, п соответственно. Кроме того, первые т столбцов матрицы U образуют подматрицу ранга т. Если /п=1, то в А должен быть ненулевой элемент, так что базис индукции выполняется. Допустим, что т=2*, k\. Так как А имеет т столбцов и ранг т, то каждая из матриц В тл С, появляющихся в строке 5, имеет т/2 столбцов и ранг т/2. По предположению индукции вызов процедуры МНОЖИТЕЛЬ в строке 6 выдает требуемые матрицы Li, UiH Pi, причем первые m/2 столбцов матрицы Ui образуют матрицу ранга т/2. Поэтому матрица необходимая в строке 9, существует.

Из рис. 6.2,2 видно, что матрица А равна произведению трех матриц, у одной из которых в верхней части стоит t/i, а в нижней G. Ранг этой матрицы должен быть т, ибо матрица А имеет ранг т. Поэтому G имеет ранг т/2. Поскольку первые т/2 столбцов матрицы G состоят из нулей, а G получается из G вычеркиванием ее первых т/2 столбцов, то ранг матрицы G также равен т/2. Следовательно, по предположению индукции вызов процедуры МНОЖИТЕЛЬ в строке 11 дает нужные L, t/j, Р. Отсюда непосредственно вытекает доказываемое утверждение. □

Прежде чем переходить к анализу времени работы, заметим, что матрицу перестановки можно представить в виде такого массива Р, что Р тогда и только тогда, когда 1 в столбце i стоит в строке /. Поэтому две (п X п)-матрицы перестановок можно перемножить за время 0(п), положив PiP [i]=Pi IP г li]]. При таком представлении можно вычислить за время О (п) также и обращение матрицы перестановки.

Теорема 6.4. Пусть для каждого п можно умножить две (п х п)-матрицы за такое время М (п), что при некотором е>0 неравенство



М (2т)2+М (т) выполняется для всех т Тогда найдется такая постоянная k, что алгоритм 6.1 тратит не более кМ (п) времени для любой невырожденной матрицы.

Доказательство. Применим алгоритм 6.1 к (пХ/г)-ма-трице. Пусть Т {т) - время, требуемое для выполнения процедуры МНОЖИТЕЛЬ (Л, т, р), где А -это (тХр)-матрица, трп. В силу строк 1-4 этой процедуры Т(1)=Ьп для некоторой постоянной Ь. Рекурсивные вызовы в строках 6 и 11 занимают Т (т/2) времени каждый. В каждой из строк 7 и 13 вычисляется матрица, обратная к матрице перестановки (что занимает 0(п) времени), и произвольная матрица умножается на матрицу перестановки. Это умножение просто переставляет столбцы первой матрицы. Представляя матрицу перестановки в виде массива Р, видим, что Р[1]-й столбец первой матрицы становится i-м столбцом произведения. Таким образом, произведение можно найти за время 0(тп), и тем самым строки 7 и 13 выполняются за время 0(тп).

Строка 9 тратит 0(М(т/2)) времени на вычисление Е- (в силу теоремы 6.2); такое же время требуется для вычисления FE-. Так как матрица Ui имеет не более (т/2) строк и не более п столбцов, то произведение (FE-)Ui можно вычислить за время 0((п/т)М (т/2)).

Заметим, что п делится на т, так как тип являются степенями числа 2 и тп. Легко видеть, что остальные шаги занимают 0(тп) времени в худшем случае. Таким образом, получили рекуррентные соотношения

Г(т)<(2(т) + ()+-«. ->1. (6.5)

[bn, если т=\,

где Ь, end - постоянные.

В силу условия теоремы и равенствам(1)=1 справедливо неравенство М (т/2)(т/2у. Поэтому можно объединить второе и третье слагаемые в (6.5). Для некоторой постоянной е

T(mK(2(f)+(f) \bn.

если m > 1, если т=\.

(6.6)

Из (6.6) выводим

Г(/п)<

4M(j-f42M(9-j-f .. . -f4i°g"M(l)J-f Ь/гт<

log m

en 4m

£ iiM{Z) + bnm. 1=1

Неформально: здесь требуется, чтобы значение М (п) было заключено между «2+8 и „з Может оказаться, например, M(n)=kn4ogn для некоторой постоянной к; тогда условие теоремы не удовлетворяется.





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