1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 51

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 51)

а+ ( — а)=( — а)+а=О. Заметим, что последнее свойство — существование обратного элемента относительно сложения — в замкнутом полукольце может не выполняться (равд. 5.6). А свойство 4 замкнутого полукольца — существование и единственность бесконечных сумм — не обя. зательно выполняется в кольце. Кольцо, в которпм операция ° коммутативна, называется коммутативным. Если в коммутативном кольце для каждого элемента а, отличного от О, существует элемент а-', обратный относительно умножения, т.

е. а а-' а-' а 1, то кольцо называется полем. Пример 6.1. Вещественные числа образуют кольцо, если взять в качестве + и ° обычные сложение и умножение. Вещественные числа, однако, не образуют замкнутого полукольца. Система ((О, 1), +, , О, 1), где + — сложение по модулю 2 и ° — обычное умножение, образует кольцо, но не замкнутое полукольцо, поскольку значение 1+1+... не определено. Но если нереопределить + так, что а+Ь=О, если а=Ь=О, и а+Ь=! в прочих случаях, то получится замкнутое полукольцо 5, из упр. 5.1.

5, не является кольцом, поскольку 1 не имеет обратного. С[ Введем важный класс колец матриц. Определение. Пусть 1т=(5, +... О, 1) — кольцо и М вЂ” множество (лхл)-матриц, элементы которых принадлежат Я. Пусть Ои обозначает (пхп)-матрицу, все элементы которой равны О, и 1„— сдиничную (лХл)-матрицу, у которой на главной диагонали стоят 1, а на остальных местах О. Для А и В из М„обозначим через А+„В такую (пхл)-матрицу С, что С [1, ![=А [1, ![+В [1, Л '), а через А „ — такую (лхл)-матрицу О, что !1 [1, 1[=Д А [1, й[ ° ° В [й, 1]. 1) М[6 !1 — алемент, стоящий в матрице М иа пересечении Ьй строки и Ьто столбца. кь основныв понятия Лемма 6А. (М„, +„, „, 0„, /„) — кольцо. Д о к а з а тел ь ст в о.

Элементарное упражнение. (З Заметим, что определенная выше операция умножения матриц „не коммутативна при л~(, даже если умножение в исходном кольце В коммутативно. Мы будем писать + и ° вместо +„и „, если это не будет вызывать путаницы со сложением и умножением в исходном кольце Я. Кроме того, мы будем часто опускать знак умножения, если он восстанавливается очевидным образом.

Пусть Я вЂ” кольцо и ̄— кольцо (лхл)-матриц с элементами из Я. Допустим, что п четно. Тогда (лХл)-матрицу М„можно разбить на четыре ((л/2)Х(л/2))-матрицы. Пусть Яв ыз — кольцо (2Х2)-матриц с элементами из Мыг. Непосредственно проверяется, что умножение и сложение (лХл)-матриц в М„эквивалентно умно.

жению и сложению соответствующих (2 х 2)-матриц в Яз,„д, элементами которых служат ((л/2) Х (л/2))-матрицы. Лемма 6.2. //усть 1 — такое отображение из М в йз,ыы что /(А) — матрица А„ А„ из акты где А„— левый верхний квадрант матрицы А, А„— ее правый верхний квадрант, А„— левый нижний, А „— правый нижний. Тогда /(А+ В) =/(А)+/(В), /(АВ) =/(А)./(В). Д о к аз а тел ь ство, Доказательство состоит в подстановке определяющих равенств для + и в Мыр в определяющие равенства для + н ° в Я, „и, а это элементарное упражнение. П Лемма 6.2 важна тем, что указывает возможность построения алгоритма умножения (лхл)-матриц из алгоритмов умножения (2Х2)-матриц и ((и/2)Х(п/2))-матриц, Мы воспользуемся ею в следующем разделе и построим асимптотически быстрый алгоритм умножения матриц. Здесь же подчеркнем тот факт, что алгоритм умножения (2Х2)-матриц будет не произвольным, а специально ориентированным на работу с йк,~ь Так как кольцо /('к„д не коммутативно, даже если таково кольцо Я, то этот алгоритм умножения (2Х2)-матриц не может предполагать коммутативностн умножения ((л/2) Х (л/2))-матриц.

Но он может, разумеется, использовать любое из свойств кольца. Определение. Пусть А будет (л Х и)-матрицей с элементами из некоторого поля. Матрицей А-', обратной к А, называется такая (пхл)-матрица, что АА-г=/„. 9 А. Ахо, дж. Хопкро4е, дж. ульмав гл. к гмножвнив мхтгиц Легко показать, что если матрица А -' существует, то она единственна и АА-'=А-'А=(„. Кроме того, (АВ)-'=В-'А-'. Определение. Пусть А будет (пхп)-матрицей, Определителем йе1(А) матрицы А называется сумма, взятая по всем перестановкам р= (1„(м..., 1„) целых чисел от 1 до н, произведений а ( — 1)ье Д А[1, (], где и« вЂ” — О, если перестановка р чепиитя (т. е. ее можно получить из (1, 2,..., и) четным числом транспозиций), и й =1, если перестановка р нечетная (получается нечетным числом транспозиций).

Легко показать, что каждая перестановка либо четна, либо нечетна (но не то и другое одновременно). Пример 6.2. Пусть а„ а„ а„ а„ а„ а„ Шесть перестановок чисел 1, 2, 3 таковы: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, !), (3, 1, 2), (3, 2, 1). Очевидно, перестановка (1, 2, 3) четна, ибо получается из себя с помощью 0 транспозиций. Перестановка (2, 3, 1) четна, поскольку, переставляя 2 и 3 в (1, 2, 3), получаем (1, 3, 2), затем переставляем 1 и 2 и получаем (2, 3, 1).

Аналогично (3, 1, 2) — четная перестановка, а остальные три — нечетные. Таким обРазом, йе1(А)=амаьзйьь — ама„а,ь — а„а„а„+а„а„а„+ +а,, а„а„— а„а„ахь П Пусть (нхп)-матрица А образована элементами из некоторого поля, Можно показать, что А-' существует тогда и только тогда, когда йе1 (А)ФО, и что йе1 (АВ) =йе1 (А) йе1 (В). В случае йе1(А)чьО матрицу А называют невырожденнои. Определение. (т хи)-матрица А называется верхней треугольной, если А [1, 1[=0 при 1<1<1<т, и нижней треугольной, если А!1, 1)=0 при 1<1<1<я.

Умножение двух верхних треугольных матриц дает верхнюю треугольную матрицу. Аналогичное утверждение верно и для нижних треугольных матриц. Лемма 6.3. Если А — «еадратная верхняя или нижняя треугольная матрица, то (а) де1(А) равняется произведению элементов, стоящих на главной диагонали (т. е. ПА [1, П), вл, ллгогитм штэлссяил для гмножения млтянц Определение. Нодматрицей матрицы А называется матрица, получаемая вычеркиванием некоторых сгрок и столбцов матрицы А. Главной подматрицей (и х и)-матрицы А называется квадратная подматрица матрицы А, состоящая из первых й строк первых 6 столбцов матрицы А, 1(М:и, Рангом гапк(А) матрицы А называется размер ее наибольшей квадратной невырожденной подматрицы.

Например, ранг (пхп)- матрицы перестановки равен и. Заметим, что если А =ВС, то гапк (А)(М![ч (гапк (В), гап[г (С)). Кроме того, если А имеет т строк и ранг т, то любые ее й строк образуют матрицу ранга й. Определение. Матрицей Аг, транспонированной к А„называют матрицу, получаемую перестановкой А [1, 11 и А [1, 1[ для всех 1 и /. 6.2. АЛГОРИТМ ШТРАССЕНА ДЛЯ УМНОЖЕНИЯ МАТРИЦ Пусть А и  — две (п ха)-матрицы, причем и — степень числа 2.

По лемме 6.2 можно разбить каждую матрицу А и В на четыре ((и/2)х(п/2))-матрицы и через них выразить произведение матриц АнВ: А„ А„ В„ В„ С„ С„ где С» = А»В»+ А»В» С„= А»В„+ А„В„, С» =А»В»+АэзВз1 С„=. А„В,, ~- А„Внг (6.1) ДИ (б) А невырожденна тогда и только тогда, когда все элементы на главной диагонали отличны от нуля. /(о к а з а тел ь с т во. (а) Всякая перестановка (1» 1ь... ..., 1„), кроме (1, 2, ..., и), содержит такую компоненту 1м что 1/С/, и такую компоненту 1, что 1л)й. Поэтому в сумме, определяющей йе1(А), все слагаемые, кроме того, которое соответствует перестановке (1, 2,..., и), равны О. (б) непосредственно следует из (а).

(л Определение. Нормированной называется матрица, у которой на главной диагонали стоят 1 (элементы вне главной диагонали произвольны). Заметим, что определитель нормированной верхней треугольной или нижней треугольной матрицы равен 1. Определение. Матрицей перестановки называется такая матрица из О и 1, что в каждой строке и каждом столбце стоит ровно одна единица. гл, а гмножание мызин Если рассматривать А и В как (2Х2)-матрицы, элементами каждой из которых служат ((и/2) Х(п/2))-матрицы, то нх произведение можно выразить через суммы и произведения ((и/2) х (и/2))-матриц (формулы (6.1)), Допустим, что С» вычисляются с помощью т умножений и а сложений (или вычитаний) ((и/2)Х(п/2))-матриц.

Рекурсивно применяя этот алгоритм, можно вычислить произведение двух (пХп)- матриц за время Т(п), удовлетворяющее неравенству Т(п)(тТ®+ 4, п>2, (6.2) Л о к аз а тел ь от в о. Чтобы вычислить произведение ма- триц сначала вычислим произведения (а„— а„) (Ь„+ Ь„), (ам+а„) (Ь„+Ь„), (а„— ам) (Ь„+ Ь„), (а„+а„) Ьги аи (Ь1в Ьм)~ а„(Ьм- Ь„), (а„+ а„) Ьпо т,= те~= /ич = т~= тБ те= тг= если и — степень числа 2. Первое слагаемое в правой части неравенства (6.2) — зто сложность умножения т пар ((и/2) х (и/2))-матриц, а второе — сложность выполнения а сложений при условии, что каждое сложение или вычитание двух ((и/2) х (и/2))-матриц требует пЧ4 времени.

Рассуждения, аналогичные проведенным в теореме 2.1 для с=2, показывают, что прн т)4 решение неравенства (6.2) ограничено сверху величиной йп' е '", где й — некоторая постоянная. Вид этого решения не зависит ото, т. е. от числа сложений. Таким образом, если т 8, то мы получаем метод, асимптотически лучший обычного метода сложности 0(пэ). Штрассен изобрел искусный метод умножения двух (2Х2)-матриц с элементами из произвольного кольца, в котором достаточно семи умножений. Рекурсивно применяя свой метод, он смог умножить две (п Х и)-матрицы за время О (и "е '), что по порядку примерно равно и"'. Лемма 6.4. Лроизведение двух (2х2)-матриц с элементами из произвозьноео «озьца можно вычислить, выполнив 7 умножений и 18 сложений (вычитаний). а.я АлГОРитм штРАссенА для умнОжения мАтРиц Затем вычисляем сы по формулам Сн = та + та — та+ та, с„=т, +т„ с =та+т С„= та — та + та — т,.

Число операций подсчитывается тривиально. Доказательство того, что в результате получаются требуемые величины см, представляет собой простое алгебраическое упражнение на использование аксиом кольца. П В упр. 6.5 приведен способ вычисления произведения двух (2х2) матриц за 7 умножений и 15 сложений. Теорема 6.1. Две (пхп)-матрицы с элементами иэ произвольного кольца можно перемножигпь эа 0(п"а') арифметических операций.

Д о к а з а т е л ь с т в о. Сначала рассмотрим случай И=2". Пусть Т(п) — число арифметических операций, необходимых для умножения двух (пхп)-матриц. По лемме 6.4 Т(п)=7Т ( — ")+18( — ) для п)2. Следовательно, в силу простой модификации теоремы 2.! Т (и) составляет 0(7"а"), или 0(п"а'). Если и не является степенью числа 2, то каждую матрицу вложим в матрицу, порядок которой равен наименьшей степени числа 2, большей и.

Характеристики

Список файлов книги