AOP_Tom2 (1021737), страница 150
Текст из файла (страница 150)
Вопросы, связанные с точностью, конечно, не возникают при работе с целыми числами по модулю т, а не с действительными числами. Схема (9) работает при а = 4, когда т и 2и4 — взаимно простые числа, а (16) работает при п = 6, когда т — взаимно простое число с биг н знаменателем (17). В упр. 44 показано, что и/2+ 0(!ой и) умножений и 0(п) сложений достаточно для любого нормированного полинома и-й степени по любому модулю т. оЦепочкн полнномов (полиномиальные цепочки). Рассмотрим вопросы оптимальности.
Каковы наилучшие схемы вычисления полиномов различных степеней, выраженные в терминах минимального возможного числа арифметических операций? Этот вопрос впервые проанализировали А. М. Островский для случая, когда коэффициенты предварительно не адаптируются (опубликовано в В!об!еэ ш Л!айетапнн апб МесЬал!сэ Ргевепсеб го Я, гоп МВеэ (Кеи 1'ог)с Асабеш!с Ргеээ, 1954), 40 — 48), и Т. С. Мацкин (Т. В. МосхЫп) — для адаптированных коэффициентов [см. Ви!!.
Ашег. Магй. Яос. 61 (1955), 163[. Для исследования этого вопроса, можно распространить понятие аддитивной цепочки из раздела 4.6.3 на понятие цепочки полиномое. Цепочка полиномов — это последовательность вида (24) х=Ло, Л,, ..., Л,=и(х), где и(х) — некоторый полинам от х и для 1 < г < г либо Л, = (~Л!) о Лы О < 1,6 < 1, (25) либо Л; = о о Лы 0 < 6 < !. Здесь символ "оо означает какую-либо из трех операций ("+", "—" или "х'), а о — так называемый параметр. Шаги первого вида называются шагами цепочки, а шаги второго вида — шагами параметра. Будем предполагать, что на каждом шаге параметра о! используются разные параметры; если существует г шагов параметра, то они должны включать оы ог, ..., о, в таком порядке.
Следовательно, полинам и(х) в конце цепочки имеет вид (26) и(х) = ч х" + .. + 91х + 90, где 9„, ..., ум да — полиномы от ам аг, ..., о, с целыми коэффициентами. Будем интерпретировать параметры ом ог, ..., аоо как действительные числа, и, следо- вательно, будем ограничиваться вычислением полиномов с действительными коэффициентами.
Множестеа результатов В полиномиальной цепочки определяется, как множество всех возможных векторов (д„,..., йм ао) действительных чисел, когда ам аз,..., а, независимо принимают все возможные действительные значения. Если для каждого выбора г+ 1 различного целого чигта уа...., А с (О, 1,..., и) существует ненулевой полинам от многих переменных 7 ., с целыми коэффициентами, такой, что Д, „(дм,..., дл) = О для всех (оа,..., йг, до), принадлежащих 77, то мы говорим, что множество результатов В имеет максимум ! степеней свободы и что цепочка (24) имеет максимум г степеней свободы.
Мы также говорим, что цепочка (24) вычисляет данный полинам и(х) = и„ха+ +и|х+из, если (и„,..., им ио) принадлежит 77. Значит, цепочка полиномов, число степеней свободы которой не больше и, не может вычислять все полиномы и-й степени (см. упр. 27). Как пример цепочки полиномов рассмотрим следующую цепочку, соответствующую теореме Е, где и нечетное: л Лг л Лз л, Лг+з! л,+„ а +Л Лг х Лг аг х Лг (27) а, г,+Л; агч.г1+ Лг 1 < г < и/2. Лг+з' х Лг+з. Теорема М (Т. С.
Мацкин. 1954). Полияомиальная цепочка с числом умножений т > О имеет максимум 2т степеней свободы. Доказательство. Пусть дм цг,..., р — это Л,-цепочки, которые являются операцией умножения. Тогда дг=Яг, гх5г; для 1<1<т и и(х)=ог ем (28) Здесь (и!'2) + 2 умножений и и сложений, (и/2) + 1 шагов цепочки и и + 1 шагов параметра. По теореме Е множество результатов Н включает множество всех (и„,...,им из) при и„э4 О, так что (27) вычисляет все полиномы степени и. Доказать, что множество А имеет максимум и степеней свободы, невозможно, поскольку множество результатов имеет и + 1 независимую компоненту. Полнномязльная цепочка с з шагамя параметра имеет максимум з степеней свободы.
В известной мере это очевидно: нельзя вычислить функцию с 1 степенями свободы, используя меньше чем г произвольных параметров. Однако этот интуитивно понятный факт нелегко доказать формально; например, существуют непрерывные функции ("заполняющие пространство кривые"), отображающие действительные прямые на плоскость, которые отображают один параметр на два независимых параметра. Для наших целей необходимо проверить, что нет полиномиальных функций с целыми коэффициентами, которые обладают таким свойством; доказательство можно найти в упр. 28. Если этот факт имеет место, можно продолжить доказательство требуемых утверждений. где каждое 5 равно некоторой сумме ро х, и оо Запишем 51 = Т, + )гу, где Т,— сумма р, и х„тогда как бз равно сумме о,.
Сейчас и(х) выражен в виде полинома от х, Д, ..., Дг„,~1 с целыми коэффициентами. Поскольку )г, можно выразить как линейные функции от ам..., о„множество значений, представленных всеми действительными значениями Д,...., рг содержит множество результатов цепочки. Следовательно, существует максимум 2т + 1 степеней свободы; как показано в упр.
50, этот результат можно улучшить, получив 2т, когда гя > О. э В упр. 25 приведен пример построения согласно теореме М. Подобный результат можно доказать для сложения. Теорема А (Э. Г. Велага, 1955). Цепочка лолллома, содержащая д операций сло- жения л вычитания, имеет максимум д + 1 степеней свободы. Докизательстоо. (Проблемы кибернетики 5 (1961), 7-15.) Пусть км ..., кг — это Лг-цепочки, которые соответствуют операциям сложения или вычитания. Тогда к, =+Тг, г+Тгг для 1 <1 < 4 и и(х) = Тггч.ы (29) где каждое Т, -- произведение к;, х; и оо Можно записать Т = А-Вм где А— произведение о, и Вг -" произведение к; и хл Следующее преобразование можно последовательно произвести по отношению к цепочке для г = 1, 2, ..., д: пусть,9, = Аг,/Аг,-м тогда к; = Аг; г(*Вг1 г хДВг;).
Затем заменим к; на хВгг г ~,В,Вг; и каждое появившееся к; в формулах Тг,,ы Тг,.ьг, ..., Тгр~ы на Аг, |к,. (Эта замена может изменить значения Аг,+ы .4м+г,, Агг-~1 ) После того как преобразование проделано для всех г, положим Др.ьг — — Аггч.ы тогда и(х) можно выразить в виде полинома от 9ы ..., )Ур„г и х с целыми коэффициентами.
Доказательство почти завершено, однако следует быть осторожными, потому что полиномы, полученные, как Оы ..., Д,+„и определенные для всех действительных значений, могут не включать все полиномы, представленные первоначальной цепочкой (см. упр. 26); возможно получение Аг; г — — О для некоторых значений о э но это делает неопределенным )гь Чтобы закончить доказательство, заметим, что множество результатов ?? первоначальной цепочки можно записать в виде В = Нг 0 Йг 0 . 0 Йр 0 В', где В;— множество результатов возможных векторов, когда Аг, г — — О, и ??' — множество результатов возможных векторов, когда все сп не равны нулю. Выше было доказано, что ??' имеет максимум д+ 1 степень свободы.
Если Аг, г = О, то Тг;, = О. Таким образом, числа шагов сложения к, может быть уменьшено, чтобы получить другие цепочки вычисляемого множества результатов Щ. По индукции можно доказать, что каждое множество Н, имеет максимум д степеней свободы. Следовательно, согласна упр. 29 В имеет максимум д+ 1 степень свободы. 1 Теорема С. Ясли цепочка лолянома (24) вычисляет все паллномы и-й степени и(х) = и„х" + + ио для некоторого и > 2, то ола включает по крайней мере (и/2г + 1 операций умножения л ло крайней мере и операций сложения-вычитаняя. Доказательство.
Пусть существует т шагов умножения. По теореме М цепочка имеет максимум 2тп степеней свободы; таким образом, 2т > и + 1. Аналогично по теореме А существует > и сложений-вычитаний. ! Теорема утверждает, что не существует ни одного метода, имеющего меньше (и/2) +1 умножений или меньше п сложений, с помощью которого можно вычислить все возможные полиномы степени п. Результат упр. 29 позволяет нам усилить это утверждение и сказать, что не существует ограниченной совокупности таких цепочек полиномов, которые достаточны для всех полиномов заданной степени.
Конечно, некоторые специальные полиномы можно вычислить более эффективно; мы действительно полностью доказали, что полиномы с алгебраически независимыми коэффициентами в том смысле, что они не удовлетворяют нетривиальному полиномнальному уравнению, требуют (и/2) +1 умножений и и сложений. К несчастью, коэффициенты, с которыми мы имеем дело на компьютере, — всегда рациональные числа, так что приведенные выше теоремы не имеют реального применения. На самом деле, в упр. 42 показана, что всегда можно достичь О(ч/и ) умножений (и, скорее всего, огромного числа сложений). С практической точки зрения ограничения теоремы С относятся к "почти всем" коэффициентам, и они, оказывается, применимы ко всем разумным схемам вычисления.
Более того, можно получить нижние грани, соответствующие теореме С, даже в рациональном случае. Согласно приведенному выше усиленному. доказательству У. Штрассен (У. Бтгаззеп) показал, например, что полипом и(х) = ~~~ 2з х" (30) нельзя вычистить любой полиномнальной цепочкой длины < пз/1бп, если цепочка не имеет хотя бы -'и — 2 умножений и и — 4 сложений (БТСОМР 3 (1974), 128-149]. Коэффициенты (30) очень велики; однако можно найти такие полиномы, коэффициенты которых равны только нулям и единицам и каждая вычисляющая их цепочка полиномов включает по крайней мере.,/и((4 18п) умножений в цепочке лля всех достаточно болыпих и, даже когда параметры о могут быть произвольными комплексными числами.
(См. Н..!. Бцэ1оп, ЯСОМР 7 (1978), 61 — 69; С.-Р. БсЬпо1т, Ьес1пге ХоСеэ 1п Сошр. Яс!. 53 (1977), 135 — 147.) Жан-Поль Ван де Виль (Зеап-Рап1 тал бе %1е1е) показал, что оценки определенных 0 — 1 полиномов требуют, в общем, сп/1обп арифметических операций для некоторого с > 0 (КОСЯ 19 (1978), 159.-165). Все еще существующее расхождение между нижней гранью теоремы С и действительным числом операций, как известно, достигается во всех ситуациях, кроме тривиального случая, когда и = 2. Теорема К дает (и/2) + 2 умножений, а не '01/2) + 1, хотя она доводит до минимума количество сложений. Наши специальные методы для п = 4 и и = 6 имеют минимальное число умножений, но одно дополнительное сложение. Когда п нечетное, то несложно доказать, что нижних граней теоремы С нельзя одновременно достичь для умножений н для сложений (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
