AOP_Tom2 (1021737), страница 157
Текст из файла (страница 157)
Обобщение теоремы М показывает, что первое умножение в цепочке и каждое умножение параметров мажет, по существу, вводить толька один новый параметр в множество результатов.! 31. (Мйу] Докажите, что цепочка полиномов, допускающая вычисление всех нормиро- ванных полиномов степени и, имеет по крайней мере (и/2] умножений и и сложений- вычитаний. 32. )М25] Найдите цепочку полиномов минимальной возможной длины, которая может вычислить все полиномы вида иох~ + иэх' + ио.
Докажите, чта эта цепочка минимальна. ь ЗЗ. (М35) Пусть и > 3 нечетное. Докажите, чта цепочка палиномав с (и/2) т 1 шагами умножений не может вычислить все полиномы степени и, если она не имеет хотя бы и, + 2 шага сложения-умножения. )Указанию См. упр. 30.) 34. (Мйб) Пусть Ло, Лп ., Л, цепочка полиномаи, в которой все взаги сложений и вычитаний шаги параметра и среди которых имеется по крайней мере один параметр умножения Предположим, что эта схема имеет ш умножений и й = г — т сложений- вычитаний и что вычисление полинома по цепочке имеет максимальную степень и.
Докажите, что все полиномы, вычисляемые па этой цепочке, коэффициенты которых при х"' не равны нулю, могут быть вычислены па другой цепочке, которая имеет максимум тл умножений, максимум 1. сложений и не имеет волчитаний. Кроме того, последний шаг новой пепочки должен быть только умножением параметра. ь Зб. )МЯ5) Покажите, что любая цепочка полиномов, которая вычисляет полинам общего нида четвертой степени, используя три умножения, должна иметь по крайней мере пять сложений-вычитаний.,'Указание. Предположите, что сув1ествует талька четыре сложения- вычитания, и покажите, чта применимо упр. 34, поэтому схема должна быть частного вида, который не представляет все палиномы четвертой степени.] Зб. (МЯ7) Продолжая предылущее упражнение, покажите, что любая цепочка полиномав.
которая вычисляет обычный полинам седьмой степени и использует только четыре умножения, должна иметь по крайней мере семь сложений-вычитаний. 37. (М31) (Т. С. Мацкин (Т. Б. Мосх)г(п).) Покажите, что "почти всех рациональные функции нида (и х" + и„-ухл"' + + и1х+ ио)/(х + е ~х" ' -г -~- о~х-~-оо) с коэффициентами из поля В можно вычислить, воспользовавшись схемой о1 + бй/(х+ Й2 + Вз/(х+ ' + д /(я+а +1) . )) для соответствующих а„у3з из Я. (Эта схема цепных дробей имеет и делений и 2п сложений, под "почти всеми" рациональными функциями понимаются все функции, за исключением тех, коэффициенты которых удовлетворяют некоторым нетривиальным паэиномиальным уравнениям) Определите аз и 31 для рациональной функции (х +10х+29)/(х + г 2 Яо:+ 19). ь 38.
)ВМ32] (В. Я. Пан, 19б2.) Назначение данного упражнения — доказать, что правило Горпера действительно оптимально, если предварительно не адаптировать коэффициент. Необходимо произвести и. умножений и и сложений для вычисления и х" + +и~х+ио. если заданы переменные и„,..., иы ио, х и произвольные постоянные. Рассмотрим цепочки, такие, как раньше, ио так, что и„,..., иы ио, х являются переменными. Например, можно сказать, что Л з ~ = и, Ло = х, Чтобы показать, что правило Горнера наилучшее, удобно доказать более общую теорему. Пусть А = (а; ), О < 1 < ац 0 < у < и, — действительная матрица размера (го+ 1) х (и+ 1) и ранга и+ 1 и пусть В = (Ьо,, бм) — действительный вектор.
Докажите, что любая цепочка полииомав, которая вычисляет Р(х;ио,...,ио) = ~(поио.(- +о,„и„+6,)х', =о включает по крайней мере и умножений в цепочке. (Заметим, что это не только означает, что рассматривается несколько фиксированных цепочек, параметры а, которых— определенные значения, зависящие от А и В. Это означает, что и цепочка, и значения ов могут зависеть от заданных матрицы А и вектора В.
Не важно, как выбраны А, В и значения о1„невозможно вычислить Р(х;ие,, и„), не выполнив и "умножений в цепочке".) Из предположения, что ранг матрицы А равен и+ 1, вытекает, что т > и. [Ухазаиое. Покажите, что из любой такой схемы можно вывести другую схему, которая имеет меньше умножений в цепочке и и уменьшено на единицу.] 3й. [М22] (Т. С. Мацкин, 1954.) Покажите, что схему вида ш« = х(х+ а«) + бм ш« = н«,(ьп + у«х + о«) + б«х + б«для 1 < Ь < т; где о«, 1㫠— действительные числа и у«, 6« — целые числа, можно использовать для вычисления всех нормированн«вх палиномов степени 2тп над полем действительных чисел. (Для различных полиномов можно по-разному выбирать о«, 2«, у«и Б«) Попытайтесь, когда возможно, предположит«э что б« = О.
40. [М41] Можно ли нижнюю грань количества операций умножения в теореме С поднять от [п/2] + 1 до [и/2] + 1 (см. упр, 33)? 41. [22] Покажите, что действительную и мнимую части (а+ Ьг)(с+ 4«) можно получить с помощью трех умножений и пяти сложений действительных чисел, где два сложения включают только а и Ь. 42. [Яб] (М. Патерсон (М. Рагегвоп) н Л, Штокмейер (П бгос)апеуег).) (а) Докажите, что цепочка полнномов с т > 2 умножениями имеет максимум г гпг + 1 степеней свободы. (Ь) Покажите, что для всех и. > 2 существуют такие палиномы степени и, все коэффициенты которых — нули нли единицы, которые не могут быть вычислены любой цепочкой полиномов с менее чем [т/й] умножениями, если все параметры аг дотжньв быть целымн числами.
(с) Покажите, что любой полинам степени и с целыми коэффициентами можно вычислить при помощи полностью целочисленного алгоритма, который выполняет максимум 2[«/й] умножений, если количество цронзведенных сложений не имеет значения. 43. [22] Объясните, как вычислить х" 4- + х+ 1, выполнив 21(п+ 1) — 2 операций умножения и 1(п + 1) сложения (не операций деления или вычитания), где 1(и) — функция, рассматриваемая в разделе 4.6.3. ь 44. [М25] Покажите, что любой нормированный полинам и(х) = х" +и„-«х" '+ . тво можно вычислить, выполнив -'и+ 0(1об и) умножений и < -'п сложений и использовав параметры и«, ог, .. — палиномм от и, и и„г,... с целымн коэффициентами.
[Указание. Сначала рассмотрите случай, когда и = 2~.] ь 45. [НМ22] Пусть (Ьб«) — тензар размера т х и х в и пусть Р, О, Н вЂ” невырожденные матрицы соответственно размера т х т, и х и и в х в. Если тб, = 5:,",, '5:,",, ~".;,, Ро 011 Н„П1, для всех г, 1, Ь, докажите, что теизор (То«) имеет такай же ранг, как и (гб«). [Указание. Рассмотрите, что произойдет, когда Р «, С «, Н ' применить таким же способом к (Т, «).] 46. [М22] Докажите, что все пары (зы зг) билинейных форм от (х«, хг) н (ум уг) можно вычислить с максимум тремя умножениями в цепочке. Другими словами, покажите, что каждый тензор размера 2 х 2 х 2 имеет ранг < 3.
47. [М25] Докажите, что для всех т, и и в существует тензар размера т х г«х в, ранг которого равен по крайней мере [тпв/(т+ и+ «Я. Обратно, покажите, что каждый тензор размера т х и х в имеет ранг, не превышающий тив/шах(т, п, в). 43. [М21] Если (Гу«) и (Г'; «) — тенэоры размера т х и х в и т' х п' х в' соответственно, то их прямая сумма (й «)Ю(1„«) = (Г' «) является тензором размера (т+т ) х(и+и ) х(в+в ), определенным как Г" ,„= 1; «, если г < т, 1 < п, Ь < з, или как зо« вЂ” — Г, если 1 > т, У > пэ й > в; в остальных слУчаЯх Г'; „= О. Их пРЯмое пРоизведение (Гоь)З(счь) = (са'„) — этотензор размера ттхпп хвв', определенный как си, >11 >Ои> = Гцвс(, ь . Получите верхние грани гапЦС,~в) < гапй(сцв) + гапЩ в) и гапЩ,"в) < гап>с(сбв) гапк(Г';зв).
э 49. (НМЯЯ] Покажите, что ранг тензора (Сов) размера т х и х 1 такой же, как его ранг, когда он записан в виде матрицы (Геп) размера т х и, соответствующий традиционному определению ранга матрицы как максимального числа линейно независимых строк. 50. (НМЯО] (Ш. Виноград.) Пусть (Саь) — тензор размера тп х и х т, соответствующий умножению матрицы размера т х и на вектор-столбец размерности и х 1. Докажите, что ранг тензора (сць) равен глп. 51.
(МЯД (Ш. Виноград,) Придумайте алгоритм для циклической свертки степени 2, который использует 2 умножения и 4 сложения, не считая операций с хь Подобно этому придумайте алгоритм для степени 3, используя 4 умножения н 11 сложений. (См. соотношение (б9), которое позволяет решить аналогичную задачу для степени 4.) 52. (МЯЯ] (Ш. Виноград.) Пусть и = и'п", где и' .1.
и". Пусть заданы нормальные схемы для циклических сверток степени и' и о", использующие соответственно (гп', гп") умножений в цепочке, (р',рл) умножений параметров и (о~,а ~) сложений. Покажите, как построить нормальную схему для циклической свертки степени п, используя >и тл умножений в цепочке, р и + т'р умножений параметроа и о'пл + т'ол сложений. 53. (НМ40] (Ш.
Виноград ) Пусть ы — т-й комплексный корень из единицы. Рассмотрим одномерное дискретное преобразование Фурье Дв) = ~ Г(1)ы", для 1 < в < т. с=> а) Когда т = р' — степень нечетного простого числа, покажите, что эффективные нормальные схемы вычисления циклических сверток степеней (р — 1)р~ для О < Я < е приводят к эффективным алгоритмам вычисления преобразования Фурье т комплексных чисел. Предложите подобную конструкцию для случая, когда р = 2. ») Когда гл = гп'т" н т' .1 т", покажите, что алгоритмы преобразования Фурье для т' и тл можно скомпоновать так, чтобы получить алгоритм преобразования Фурье для гл элементов. 54.
(МЯЯ] Теорема Ч~ доказана для бесконечных палей. Сколько элементов должно содержаться в конечном пале, чтобы доказательства теоремы Чг оставалось справедливым7 55. [НМЯЯ] Определите ранг тензора (74), когда Р— проиввввьнов матрица размера и хи. 56. [МЗЯ] (У. Штрассен (У. 5>гавэеп).) Покажите, что любая цепочка палнномов, которая вычисляет множество квадратичных форм 2,", 2 "., гцвх>хв для 1 < >с < в, должна использовать, в целом, по крайней мере -', гапк(го в + гцв) умножений в цепочке (Указание.
Покажите, что минимальное число умножений в цепочке равно минимальному рангу (Гнв), взЯтомУ по всем тензоРам (Гбь), таким, чта Гав + Г,>в - -ге ь + г>ы ДлЯ всех 1, >, >с.] Воспользуйтесь этим для доказательства того, что любая цепочка полиномав, вычисляющая множество билинейных форм вида (47) и соответствующая тензору (гб*), нормален он или анормален, должна использовать хотя бы -'гап>г(гтв) умножений в цепочке. 57. (МЯ>>] Покажите, что быстрое преобразование Фурье можно использовать для вычисления коэффициентов произведения двух заданных полиномов степени и х(н)я(в), произведя 0(п1об и) операций (точно) сложений и умножений комплексных чисел.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
