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

6.1. ОСНОВНЫЕ понятия

Лемма 6Л. +п, 0„, /„) - кольцо. Доказательство. Элементарное упражнение. □

Заметим, что определенная выше операция умножения матриц •„ не коммутативна при п>>1, даже если умножение в исходном кольце R коммутативно. Мы будем писать + и • вместо +п и •„, если это не будет вызывать путаницы со сложением и умножением в исходном кольце R. Кроме того, мы будем часто опускать знак умножения, если он восстанавливается очевидным образом.

Пусть R - кольцо и Л1„- кольцо (п X п)-матриц с элементами из R. Допустим, что п четно. Тогда (п X п)-матрицу Л1„ можно разбить на четыре ((п/2)Х(п/2))-матрицы. Пусть 7?2.л/2 - кольцо (2х2)-матриц с элементами из Мп/2. Непосредственно проверяется, что умножение и сложение (п X п)-матриц в M„ эквивалентно умножению и сложению соответствующих (2 х 2)-матриц в 7?2,л/2, элементами которых служат ((п/2) X (п/2))-матрицы.

Лемма 6.2. Пусть f-тлкое отобрашние из Л1„ в 7?2,л/2» что f (А) - матрица

Ail 22j

из R2,n/2, где Ац-левый верхний квадрант матрицы А, Л12- ее правый верхний квадрант, А ai- левый нижний, А ц- правый нижний. Тогда

f(A + B) = f(A} + f{B), f(AB)==f(A).f{B).

Доказательство. Доказательство состоит в подстановке определяющих равенств для -f и • в Мп/2 в определяющие равенства для + и • в 7?2,п/2. а это элементарное упражнение. □

Лемма 6.2 важна тем, что указывает возможность построения алгоритма умножения (пХп)-матриц из алгоритмов умножения (2х2)-матриц и ((п/2)Х(п/2))-матриц. Мы воспользуемся ею в следующем разделе и построим асимптотически быстрый алгоритм умножения матриц. Здесь же подчеркнем тот факт, что алгоритм умножения (2х2)-матриц будет не произвольным, а специально ориентированным на работу с 7?2,п/2- Так как кольцо 7?2,л/2 не коммутативно, даже если таково кольцо R, то этот алгоритм умножения (2х2)-матриц не может предполагать коммутативности умножения ((п/2)Х (п/2))-матриц. Но он может, разумеется, использовать любое из свойств кольца.

Определение. Пусть А будет (пХп)-матрицей с элементами из некоторого поля. Матрицей А-, обратной к А, называется такая (пХп)-матрица, что Л/1-*=/„.



Легко показать, что если матрица А - существует, то она единственна и АА-=А-А = 1п- Кроме того, (ЛB)-l=fi-M-.

Определение. Пусть А будет (пХп)-матрицей. Определителем ut\{A) матрицы А называется сумма, взятая по всем перестановкам P=(i, lit • • -у in) целых чисел от 1 до п, произведений

(-DpjlAiJ, ij],

где kp=0, если перестановка р четная (т. е. ее можно получить из (1,2,..., п) четным числом транспозиций), и /г,= 1, если перестановка р нечетная (получается нечетным числом транспозиций).

Легко показать, что каждая перестановка либо четна, либо нечетна (но не то и другое одновременно).

Пример 6.2. Пусть

Шесть перестановок чисел 1, 2, 3 таковы: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). Очевидно, перестановка (1, 2, 3) четна, ибо получается из себя с помощью О транспозиций. Перестановка (2, 3, 1) четна, поскольку, переставляя 2 и 3 в (1, 2, 3), получаем (1, 3, 2), затем переставляем 1 и 2 и получаем (2, 3, 1). Аналогично (3, 1,2) - четная перестановка, а остальные три - нечетные. Таким образом, det (Л)=а11а22азз - аийгззг - аиагхазз+ахгагзазгЧ-

+U13 flai аз2- «13 Саг «зг. □

Пусть (п X п)-матрица А образована элементами из некоторого поля. Можно показать, что А- существует тогда и только тогда, когда det ЩфО, и что det (/lfi)=det (Л) det (В). В случае det {А)фО матрицу Л называют невырожденной.

Определение. (тХп)-матрица Л называется верхней треугольной, если A[i, /1=0 при l}<iim, и нижней треугольной, если Л It, /]=0 при l<i</<n.

Умножение двух верхних треугольных матриц дает верхнюю треугольную матрицу. Аналогичное утверждение верно и для нижних треугольных матриц.

Лемма 6.3. Если А - квадратная верхняя или нижняя треугольная матрица, то

(а) det (Л) равняется произведению элементов, стоящих на главной диагонали (т. е. ПЛ [i, iJ), t



6.2. АЛГОРИТМ ШТРАССЕНА ДЛЯ УМНОЖЕНИЯ МАТРИЦ

(б) А невырожденна тогда и только тогда, когда все элементы на главной диагонали отличны от нуля.

Доказательство, (а) Всякая перестановка (tl, ta, . . . ..., /„), кроме (1, 2, .... п), содержит такую компоненту ij, что ij<.}, и такую компоненту г, что ift>ft. Поэтому в сумме, определяющей det(), все слагаемые, кроме того, которое соответствует перестановке (1, 2, . . ., п), равны 0. (б) непосредственно следует из (а). □

Определение. Нормированной называется матрица, у которой на главной диагонали стоят 1 (элементы вне главной диагонали произвольны).

Заметим, что определитель нормированной верхней треугольной или нижней треугольной матрицы равен 1.

Определение. Матрицей перестановки называется такая матрица из О и 1, что в каждой строке и каждом столбце стоит ровно одна единица.

Определение. Подматрицей матрицы А называется матрица, получаемая вычеркиванием некоторых строк и столбцов матрицы А. Главной подматрицей (пХп)-матрицы А называется квадратная подматрица матрицы Л, состоящая из первых й строк первых столбцов матрицы Л, 1<<п.

Рангом rank (Л) матрицы Л называется размер ее наибольшей квадратной невырожденной подматрицы. Например, ранг (пхп)-матрицы перестановки равен п.

Заметим, что если А=ВС, то rank (ЛХМШ (rank (В), rank (С)). Кроме того, если Л имеет т строк и ранг т, то любые ее k строк образуют матрицу ранга к.

Определение. Матрицей Л, транспонированной к Л, называют матрицу, получаемую перестановкой Л И, j] и Л [/, i] для всех i и /.

6.2. АЛГОРИТ.М ШТРАССЕНА ДЛЯ УМНОЖЕНИЯ МАТРИЦ

Пусть Л и fi - две (пХп)-матрицы, причем п - степень числа 2. По лемме 6.2 можно разбить каждую матрицу Л и fi на четыре ((п/2) X (п/2))-матрицы и через них выразить произведение матриц Л и fi:

fll2l

"Си

Cj, = Л2fil + Л22fi2l.

С22 = 2lfil2

А R

•22"22

(6.1)





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