Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 42
Текст из файла (страница 42)
По теореме Е множество результатов В включает множество всех (и,..., ив вас) при вг„~ О, так что (27) вычисляет все полиномы степени п. Доказать, что множество В имеет максимум и степеней свободы, невозможно, поскольку множество результатов имеет п + 1 независимую компоненту. Полиномиальная пеночка с з шагамн параметра имеет макшвчум з степеней свободы. В известной мере это очевидно: нельзя вычислить функцию с в степенями свободы, используя меньше чем З произвольных параметров. Однако этот интуитивно понятный факт нелегко доказать формально; например, существуют непрерывные функции ("заполняющие пространство кривые"), отображающие действительные прямые на плоскость, которые отображают один параметр на два независимых параметра.
Для наших целей необходимо проверить„что нет пслиномиальных функций с целыми коэффициентами, которые обладают таким свойством; доказательство можно найти в упр. 28. Если этот факт имеет место, можно продолжить доказательство требуемых утверждений. Теорема М (Т. С. Мацкин, 1954). Полиномиальная цепочка с числом умножений пг ) О имеет максимум 2пг степеней свободы. Даказавпельсшаа. Пусть рм дг, ..., р — это Л;-цепочки, которые являются опера- цией умножения. Тогда гв; =Язв г х Яг; для 1< а <гп н и(х) =бгм+м (28) вательно, будем ограничиваться вычислением полиномов с действительными коэффициентами. Мнамсеспмва резраыаашаа В полнномиальной цепочки определяется, как множество всех возможных векторов (д„,...
в ам вза) действительных чисел, когда аг, аг,..., о, независимо принимают все возможные действительные значения. Если для каждого выбора в+ 1 различного целого числа уа, ..., 7г с (Ов 1,, и) существует ненулевой полинам от многих переменных Д,; с целыми коэффициентами, такой, что /гэ Л(в7 „..., й,) = О для всех (в7„,...,ймв7а), принадлежащих В, то мы говорим, что множество результатов В имеет максимум З сагспеней свободы и что цепочка (24) имеет максимум в степеней свободы. Мы также говорим, что цепочка (24) вмчасллепг данный полинам а(х) = и„х" + + игх+па, если (и„,...,ав,иа) принадлежит В, Значит, цепочка полиномов, число степеней свободы которой не болыпе и, не может вычислять все полиномы и-й степени (см.
упр. 27). Как пример цепочки полиномов рассмотрим следующую цепочку; соответствующую теореме Е, где п нечетное: где каждое Я» равно некоторой сумме ро х, и а,, Запишем Я, = Т» + 1»»ч где һ— сумма р, и х;, тогда как й» равно сумме ао Сейчас и(х) выражен в виде полиномаот х, бы ..., йэ е» с целыми коэффициентами. Поскольку В» можно выразить как линейные функции от аы..., им множество значений, представленных всеми действительнымн значениями»»ы.
° °, рэ +ы содержит множество результатов цепочки. Следовательно, существует максимум 2ш + 1 степеней свободы; как показано в упр. ЗО, этот результат можно улучшить, получив 2п», когда гл > О. 3 В упр. 25 приведен пример построения согласно теореме М. Подобный результат можно доказать для сложения.
Теорема А (Э. Г. Белвга, 1958). Цепочка полннома, содержащая д операций сло- жения н вычитания, имеет максимум в + 1 степеней свободы. Доказательство. (Проблемы кибернетики 5 (1961), 7-15.) Пусть к„..., кч — это А»-цепочки, которые соответствуют операциям сложения илн вычитания. Тогда к; = хТм» хТм для 1 <1< и и и(х) =Ттч+ы (29) где каждое Т вЂ” произведение к;, х; и ао Можно записать Т» = А» В», где А»вЂ” произведение си и  — произведение к, и хь Следующее преобразование можно последовательно произвести по отношению к цепочке для 1 = 1, 2,..., е: пусть 1»» = Аэ»»»Ам-», тогда к; = Ам»(хВэ»» х )»» Вгн).
Затем заменим к, на хВм-» х)1»Вм и каждое появившееся к, в формулах Тм„.», Тм+м ..., Тэч+» на Аэ, » к,. (Эта замена может изменить значения .4м+ы Ам+э; °, Аэю+» ) После того как преобразование проделано для всех 1, положим ()чч.» = Аэгь», тогда и(х) можно выразить в виде полинома от йы..., Д,.~» и х с целыми коэффициентами. Доказательство почти завершено, однако следует быть осторожными, потому что полиномы, напученные, как»»ы ..., Вч+», и определенные для всех действительных значений, могут не включать все поэиномы, представленные первоначальной цепочкой (см.
упр. 26); возможно получение Ам» = О для некоторых значений а., но это делает неопределенным йь Чтобы закончить доказательство, заметим, что множество результатов В первоначальной цепочки можно записать в виде В = В» 0 Вэ 0 ° ° 0 Вч О В', где В— множество результатов возможных векторов, когда Ам» = О, и В' — множество результатов возможных векторов, когда все си не равны нулю. Выше было доказано, что В' имеет максимум 9+1 степень свободы. Если Ам» = О, то Тм» = О. Таким образом, число шагов сложения к; может быть уменьшено, чтобы получить другие цепочки вычисляемого множества результатов В;.
По индукции можно доказать, что каждое множество В, имеет максимум и степеней свободы, Следовательно, согласно упр. 29 В имеет максимум и + 1 степень свободы. 3 Теорема С. Есчн цепочка полннома (24) вычисляет все полнномы и-й степени и(х) = и„х" + ° + ио для некоторого и > 2, то она включает по крайней мере (п)2) + 1 операций умножения и по крайней мере и операций сложения-вычитания. Доказав»ельсп»ео. Пусть существует т шагов умножения. По теореме М цепочка имеет максимум 2»п степеней свободы; таким образом, 2т > и+ 1, Аналогично по теореме А существует > и сложений-вычитаний.
Теорема утверждает, что не существует ии одного метода, имеющего меньше ?и/2)+1 умножений или меньше и сложений, с помощью которого можно вычислить все возможные полиномы степени и. Результат упр. 29 позволяет нам усилить зто утверждение и сказать, что не су<цествует ограниченной совокупности таких цепочек полиномов, которые достаточны для всех полнномов заданной степени. Конечно, некоторые специальные полиномы можно вычислить более эффективно; мы действительно полностью доказали, что полиномы с алгебраически незаеиси<ни.ии коэффициентами в том смысле, что они не удовлетворяют нетривиальному полиномиальному уравнению, требуют ?п/2) + 1 умножений и и сложений. К несчастью, коэффициенты, с которыми мы имеем дело на компьютере, — всегда рациональные числа, так что приведенные выше теоремы не имеют реального применения. На самом деле, в упр.
42 показано, что всегда можно достичь О(~/й) умножений (и, скорее всего, огромного числа <ложений). С практической точки зрения ограничения теоремы С относятся к "почти всем" коэффициентам, и они, оказывается, применимы ко всем разумным схемам вычисления. Более того, можно получить нижние грани, соответствующие теореме С, даже в рациональном случае. Согласно приведенному выше усиленному доказательству У.
Штрассен (Ъ', 8<гаээеп) показал, например, что полипом я п(х) = ~ 2~ х" (30) нельзя вычислить любой полиномиельной цепочкой длины с пэ/1йп, если цепочка не имеет хотя бы -'и — 2 умножений и и — 4 сложений (о?СОМР 3 (1974), 128-149]. Коэффициенты (30) очень велики; однако можно найти такие полиномы, коэффициенты которых равны только нулям и единицам и каждая вычисляющая нх цепочка полиномов включает по крайней мере ~~й/(4 18 п) умножений в цепочке для всех достаточно больших и, даже когда параметры а могут быть произвольными комплексными числами. (См. Н, Л,?,!р<оп, 8?СОМР 7 (1978), 61-69; С.-Р. Бс?<погг, ? ее<иге Хо<ее ш Сошр. Бс? 53 (1977), 135 — 147.) Жан-Поль Ван де Виль (Леап-Рац1 тап <?е %1е!е) показал, что оценки определенных 0 — 1 полиномов требуют, в общем, сп/?ой п арифметических операций для некоторого с > 0 (ГОСБ 19 (1978), 159-165).
Все еще существующее расхождение между нижней гранью теоремы С и действительным числом операций, как известно, достигается во всех ситуациях, кроме тривиального случая, когда и = 2. Теорема Е дает ?и/2) + 2 умножений, а не ) и/2) + 1, хотя она доводит до минимума количество сложений. Наши специальные методы для и = 4 и п = 6 имеют минимальное число умножений, но одно дополнительное сложение. Когда п нечетное, то несложно доказать, что нижних граней теоремы С нельзя одновременно достичь для умножений и для сложений (см.
упр. 33). Для и = 3, 5 и 7 можно показать, что необходимо по крайней мере ?и/2) + 2 умножений. В упр. 35 и 36 показано, что обе нижние грани теоремы С не могут быть достигнуты одновременно при и = 4 или и = 6; таким образом, обсуждаемые методы будут наилучшими для п < 8. Для четного и Моцкин (Мосх?оп) доказал, что достаточно ?и/21 + 1 умножений, но его конструкция включает неопределенное количество сложений (см. упр. 39). Оптимальную схему для и = 8 нашел В.
Я. Пан, доказавший, что в этом случае необходимо и достаточно и + 1 сложений, когда существует ?п/2) + 1 умножений; он также показал, что ?и/2) + 1 умножений и х + ' +я+1. Поскольку этот полипом можно записать в виде (х"+1 — 1)/(х — 1), его можно вычислить, выполнив ((и+ 1) операций умножения (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
