AOP_Tom2 (1021737), страница 151
Текст из файла (страница 151)
упр. 33). Для и = 3, 5 и 7 можно показать, что необходимо по крайней мере (и/2) + 2 умножений. В упр. 35 и 36 показано, что обе нижние грани теоремы С не могут быть достигнуты одновременно при п = 4 или п = 6; таким образом, обсуждаемые методы будут наилучшими для и ( 8. Для четного и Моцкин (МотгЫп) доказал, что достаточно ~п/2) + 1 умножений, но его конструкция включает неопределенное количество сложений (см. упр. 39). Оптимальную схему для и = 8 нашел В. Я, Пан, доказавший, что в этом случае необходимо и достаточно и + 1 сложений, когда существует (и/2) + 1 умножений; он также показал, что (и/2) + 1 умножений и и + 2 счожений достаточно для всех четных и > 10. В работе Пана (БТОС 10 (1978), 162 — 172] также установлено необходимое точное минимальное количество у.множений и сложений, когда вычисления производятся полностью с комплексными числами, а не с действительными для всех степеней и, В упр.
40 обсуждается интересная ситуация, возникающая при нечетных значениях и > 9. х" + +х+1. Поскольку этот полинол! можно записать в виде (х"+' — 1)/(х — 1), его можно вычислить, выполнив((п+ 1) операций умножения (см. раздел 4.6.3), две операции вычитания н одно деление, в то время как технический прием во избежание деления, кажется, требует приблизительно втрое больше операций (см. упр. 43). Специальные полнномы от нескольких переменных.
Определитель матрицы размера п х и можно рассматривать как полипом от пз переменных хо, 1 < 1,1 < и. Если х!1 ф О, то Х11 Х12 ... Х! Х21 222 ° 22 221 222 ХЗ» 821 Х22 — (Х21/Х11)212 . Х2» (Х21/211)Х! хзз — (хз!/х!!)хп " хз — (хз1/хп)*! = х11ПЫ Х 2 (Х 1/Х11)Х12» Х» (Х»1/Х11)Х! (31) 1 Х 2 . Х»» Поэтому определитель матрицы размера п х и можно найти, вычислив определитель матрицы размера (и — 1) х (и — 1) и выполнив дополнительно (п — 1)2+ 1 умножений, (и — 1)2 сложений и п — 1 делений.
Поскольку определитель размера 2 х 2 можно вычислить с помощью двух операций умножения и одной операции сложения, определитель почти всех матриц (т. е, матриц, для которых нет необходимости в делении на нуль) можно вычислить, выполнив максимум (2пз — Зпз + 7п — 6)/6 операций умножения, (2пз — Зпз+ и)/6 операций сложения и (пз — п — 2)/2 делений. Ясно, что результаты, полученные для цепочек полиномов с одной переменной, можно без труда применить к полиномал1 с многими переменными. Например, если нужно найти оптимальную схему вычисления полинома без адаптации коэффициентов, можно рассматривать полипом и(х) как полипом от и+ 2 переменных х,и„,...,иг,ие) в упр. 38 показано, что в этом случае необходимо и умножений и и сложений.
В самом деле, А. Бородин (ТЛеогу оИХасй!пеэ ап!( Сошригаз!опз, егйтег( Ьу 2. КоЬа14!] и А. Паз (А. Рах) [влезь Ъог)г: Асадеш!с Ргеээ. 1971, 45-58] доказали, что правило Горнера (2) является, по существу, только методом вычисления и(х) за 2п операций без предварительных условий. С незначительными изменениями приведенные выше к!вгоды могут быть так же хорошо обобщены для цепочек, включающих деление, т.
е. для рациональных функций, как и для полиномов. Любопытно, что цепные дроби, аналогичные правилу Горнера, оказались оптимальными с точки зрения вычислительных операций, если скорости выполнения операций умножения и деления одинаковы, даже при дополнительных условиях (см. упр. 37). Иногда деление полезно во время вычисления полиномов! даже если полиномы определены только в терминах умножения и сложения (соответствующие примеры приводятся в алгоритмах Шо-Трауба для производных полинома). Другим примером является Определитель даже легче вычислить, когда появляется нуль.
Например, если хы —— О, но хьй ~ О, получим Хь, ... *, Хг! Х22 ХЗЗ 422 хзь хзг . хз ° х хьг Хь„ 232 (ХЗ1/221)Х22 -. ХЗ ' (ХЗ1/Х21)Х2 = хгь ьЬеь хзг (х„ь/хм)хм ... Хзз (хзь/хм)хг (32) Х11Х 2 Перманентном матрицы называется полипом, который очень похож на определитель, но все его коэффициенты при произведениях членов матрицы равны +1. Таким образом, ХЬЬ ... Хь„ рег .; = ~ хььзх21,...Х„З„, Хьм ° ХЗЗ (33) где сумма берется по всем перестановкам уьуг...уп от (1,2,...,п). Казалось бы, эту функцию даже легче вычислить, чем ее более сложную с виду сестру, но не существует метода вычисления перманента матрицы, такого же эффективного, как известные методы для определителя.
В упр. 9 и 10 показано, что достаточно существенно меньшего количества операций и) для больших п, но врелья счета всех известных методов все еше возчастает по экспоненте с ростом размера матрицы. На самом деле Лесли Г. Велиант Еев!!е О. За!!апс) показал, что вычислить заданную 0-1-матрицу так же трудно, как подсчитать число допустимых вычислений машины Тьюринга с недетерминированным полиномиэльным временем, если игнорировать полиномиальный характер времени вычислений. Следовательно, проблемы, связанные с полинольиальным временем вычисления перманента, должны включать множество других хорошо известных проблем, сопротивляющихся эффективному решению за полиномиальное время.
С другой стороны, Велиант доказал, что пер- Здесь сокращение размера определителя до (и — 1) х (и — 1) приводит к зкономии и — 1 умножений и и — 1 сложений, используемых в (31): это компенсация за дополнительную информацию, необходимую для того, чтобы отличать данный случай.
Таким образом, любой определитель можно вычислить, выполнив приблизительно -и арифметических операций (включая деление). Это замечательно, поскольку это поливом с и! членами и и переменными в каждом члене. Для вычисления определителя матрицы с цслммн элементами процедуры (31) и (32) кажутся непривлекательными, так как они требуют рациональной арифметики. Однако можно воспользоваться методом вычигления определителя по ьпоь( р для любого простого числа р, поскольку возможно деление по ьыоь) р (упр. 4.5.2 — 1б). Если это проделать для достаточного количества простых чисел, то точное значение определителя можно найти так, как объясняется в разделе 4.3.2, поскольку неравенство Адамара 4.б.1 (25) дает верхнюю грань. Коэффициенты харакшериспьическозо полинома ь)е!(ХТ вЂ” Х) матрицы Х размерап х и также можно вычислить за 0(пз) шагов; см.
3, Н. Зз'!!)ыпзоп, ТЪе А!яеЪгшс Е!лепта!не РгоЫеш (Ох!огф С!агеп11оп Ргезз, 1965), 353-355, 410-411. В упр. 70 обсуждается интересный свободный от деления метод, не используюпьий операции деления н включающий 0(пз) шагов. манент целочисленной матрицы размера и х и можно вычислить по модулю 21 эа 0(пвв в) шагов для всех !с ) 2. [См. Т!2еагев!са1 Сотр.
Яс!. 8 (1979)., 189 — 20Ц Другой связанной с матрицами фундаментальной операцией, конечно, является умножение матрац: если х = (х; ) -- матрица размера т х п, 2' = (у!1) — матрица размера и х в и Х = (211) — матрица размера т х в, то формула Я = Х!' означает, что Хо,—— ~~1 х, ул, 1<1<т, 1<!2<в. (34) Это равенство можно рассматривать как вычисление одновременно тв палиномов от ти+ ив переменных; каждый полинам — "скалярное произведение" двух и-мернь1х векторов. Непосредственно вычисление включает тив умножений и тв(и — 1) сложений, но Ш.
Виноград (Б. %!пойгас1) в 1967 году обнаружил, что можно зал1енить акала половины умножений сложениями: хль = ~ (х121' + у21-12)(х121-1 + уел) а! — 51 + х1иуил[11 061(]; 1<у<и/2 а1 — ~Х~ х621хьэу-1! 1<1<и/2 (35) В этой схеме используется [и/2]тв + [и/2](ги + в) умножений и (и + 2)тв + ([и/2) — 1)(тв+ т+ в) сложений или вычитаний: общее число операций возрастает незначительно, но число умножений сокращается приблизительно вдвое.
[См. 1ЕЕЕ Тгвпв. С-17 (1968), 693-694.] Поразительная конструкция Винограда побудила многих ученых более внимательно взглянуть на проблему умножения матрицы, что привело к широко распространенному предположению о том, что и /2 умножений, возможно, необходимо выполнить для умножения матриц размера и х и, потому что довольно похожая нижняя грань, как известно, имеет место для полиномов с одной переменной. Еще луч1пую схему для больших и открыл в 1968 году Уолкер Штрассеи (Но1кег Йгаввеп); он нашел способ вычисления произведения матриц размера 2 х 2 с помощью всего семи операций умножения, без коммутативности умножения, как в (35). Так как матрицы размера 2и х 2и можно разбить на четыре матрицы размера и х и, его идею можно использовать рекурсивно для получения произведения матриц размера 21 х 22 только с 7" умножениями вместо (2л)в = 82. Порядок роста числа сложений равен 7л.
Первоначально в методе Штрассена умножения матриц размера 2 х 2 [!1!пшег, Мав)2. 13 (1969), 354 — 356] использовалось 7 умножений и 18 сложений; Ш. Виноград позже обнаружил следующую более экономную формулу: с А В Р ш+и+Ы(В+С вЂ” А-Р) 2о+и+с где и = (с-а)(С вЂ” Р), а = (с+И)(С вЂ” А), 1о = аА+(с+11-а)(А+Р— С). Если соответствующие промежуточные результаты сохранены, то используется 7 умножений и только 15 сложений; индукцией по (с легко показать, чта можно умножать матрицы размера 22 х 2" с помощью 71 операций умножения и 5(7" — 41) операций сложения.
Общее число операций, необходил1ЫХ ДЛЯ уМНОжения матриц Размера и х и, следовательно, можно сократить ат порядка ив до 0(и12") = 0(ив воы). Подобное сокращение применяется также к вычислению определителей и обратной матрицы; см. 3. В.. ВппсЬ апб 3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
