Мы детально обсуждаем случаи степеней n = 4, 5, 6, поскольку такие значения п ча1це встречаются в приложениях. Сейчас рассмотрим общую схему вычисления полиномов п-й степени, метод, включающий максимум [n/2j -I- 2 умножений и п сложений.

Теорема Е. Каждый полином п-й степени (1) с действительными коэффициентами, п > 3, можно вычислить по схеме

у = :, + с, w = y; ,= ИпУ + ао)у + Ро, п четное,

{и„у-\-Ро, п нечетное,

и{х) ={... {{z{w - ai) + Pi)iw - аг) + •) - am) + (20)

при подходящих вещественных параметрах с, а и Pk, где m = "п/2] - 1. На самом деле можно выбрать эти параметры таким образом, что /Зт = 0.

Доказательство. Сначала рассмотрим условия, при которых Oj и /3j могут быть выбраны в (20) при фиксированном с. Пусть

р{х) = и{х - с) = ОпХ" + Un-ix"" Н-----h flil -Ь По. (21)

Покажем, что р{х) имеет вид pi{х){х- - am) + /Зщ для некоторого полинома pi (х) и некоторых констант am, Рт- Если разделить р{х) на х" - am, то остаток Рт будет константой только в том случае, если вспомогательный полином

q{x) = агт+и" + 02„-l.т"- + • • + fli, (22)

сформированный из нечетных коэффициентов р{х), кратен х - am- Наоборот, если q{x) имеет множитель х - am, то р{х) = pi{x){x - am) + Рт при определенных константах Рт, которые можно определить посредством деления.

Также необходимо, чтобыpi(a;) имел вшдр2{х){х -am-i)-Pm~i, и это эквивалентно тому, что q{x)/{x - am) является кратным х - am-i; если qi{x) -полином, соответствующий р\{х), как q{x) соответствует р{х), то qi{x) - q{x)/{x - ат)-Продолжая в том же духе, найдем, что параметры ai. Pi, ..., а„, Рт существуют тогда и только тогда, когда

q{x) =a.2m+i{x-ai)-.-{x-am)- (23)

Другими словами, каждый полином q{x) тождественно равен нулю (и это возможно, только когда п четное) или же q{x) -полином степени т, имеющий все вещественные корни.

Поразительный факт был обнаружен Дж. Ином (J. Eve) [JVumer. Math. 6 (1964), 17-21]: еслир{х) имеет по крайней мере n-l комплексный корень, все вещественные части которых не отрицательны или не положительны, то соответствующий полином q{x) тождественно равен нулю или имеет все вещественные корни (см. упр. 23). Поскольку и{х) - О тогда и только тогда, когда р{х -Ь с) =0, необходимо просто выбрать параметр с достаточно большим, чтобы по крайней мере п - 1 корень и{х) = о имел вещественные части > -с, и (20) будет применяться всякий раз, как только а„ 1 = Un-i - ncUn ф 0.

Можно определить с таким образом, чтобы эти условия выполнялись, а также чтобы Рт - 0. Первые п корней уравнения и{х) = О определены. Если а-\-Ы - корень, имеющий наибольшую или наименьшую вещественную часть, и если b ф О,

то положим с = -а и ащ = -Ь; тогда х" - am является множителем и{х - с). Если корень с наименьшей или наибольшей вещественной частью вещественный, но корень со второй наименьшей (или второй наибольшей) вещественной частью не вещественный, то применяется такое же преобразование. Если два корня с наименьшими (или наибольшими) вещественными частями вещественны, то их можно выразить в виде а-6 и а-ьЬ соответственно. Пусть с = -а и а„ = 6; сноваж-ат - множитель и{х - с). (Однако часто возможны другие значения с; см. упр. 24.) Коэффициент а„ 1 будет ненулевым для хотя бы одного из этих вариантов, если только q{x) не будет тождественно равным нулю.

Заметим, что этот метод доказательства обычно дает по крайней мере два значения с, переставлять ai, am~i можно (m - 1)! способом. Некоторые из этих вариантов, вероятно, дают большую точность, чем остальные.

Вопросы, связанные с точностью, конечно, не возникают при работе с целыми числами по модулю т, а не с действительными числами. Схема (9) работает при n = 4, когда m и 2u4 - взаимно простые числа, а (16) работает при n = 6, когда m - взаимно простое число с бие и знаменателем (17). В упр. 44 показано, что n/2-l- O(logn) умножений и 0{п) сложений достаточно для любого нормированного полинома п-й степени по любому модулю т.

*Цепочки полиномов (полиномиальные цепочки). Рассмотрим вопросы оптимальности. Каковы наилучшие схемы вычисления полиномов различных степеней, выраженные в терминах минимального возможного числа арифметических операций? Этот вопрос впервые проанализировали А. М. Островский для случая, когда коэффициенты предварительно не адаптируются (опубликовано в Studies in Matliematics and Mechanics Presented to R. von Mises (New York: Academic Press, 1954), 40-48), и Т. С. Моцкин (Т. S. Motzkin) -для адаптированных коэффициентов [см. Bull. Amer. Math. Soc. 61 (1955), 163].

Для исследования этого вопроса можно распространить понятие аддитивной цепочки из раздела 4.6.3 на понятие цепочки полиномов. Цепочка полиномов -это последовательность вида

а; = Ао, Al, Хг = и{х), (24)

где и{х) - некоторый полином от а; и для 1 < г < г

либо Ai = (±Aj) о Аус, 0<j,k<i,

либо Xi = aj о Хк, О < к < i.

Здесь символ "о" означает какую-либо из трех операций ("-I-", "-" или "х), а aj -так называемый параметр. Шаги первого вида называются шагами цепочки, а шаги второго вида- шагами параметра. Будем предполагать, что на каждом шаге параметра aj используются разные параметры; если существует s шагов параметра, то они должны включать ai, аг, ..., а« в таком порядке. Следовательно, полином и{х) в конце цепочки имеет вид

и{х) = QnX" + + qix + до, (26)

где qn, ..., qi, qo - полиномы от ai, ог, .., а« с целыми коэффициентами. Будем интерпретировать параметры ai, аг, а, как действительные числа, и, следо-

вательно, будем ограничиваться вычислением полиномов с действительными коэффициентами. Множество результатов R полиномиальной цепочки определяется, как множество всех возможных векторов (д„,... ,qi,qo) действительных чисел, когда ai,a2,... ,as независимо принимают все возможные действительные значения.

Если для каждого выбора t +1 различного целого числа о, , jt G {0,1,..., n} существует ненулевой полином от многих переменных fjo...j, с целыми коэффициентами, такой, что fjo...j,{qjo,- ,qjt) =0 для всех ... ,gi,go), принадлежащих R, то мы говорим, что множество результатов R имеет максимум t степеней свободы и что цепочка (24) имеет максимум t степеней свободы. Мы также говорим, что цепочка (24) вычисляет данный полином и{х) = и„а;" -I-----l-Uii-1-uo, если (и„,..., Ui, uq)

принадлежит R. Значит, цепочка полиномов, число степеней свободы которой не больше п, не может вычислять все полиномы п-й степени (см. упр. 27).

Как пример цепочки полиномов рассмотрим следующую цепочку, соответствующую теореме Е, где п нечетное:

(27)

1 < г < n/2.

Здесь [n/2J + 2 умножений и n сложений, [n/2\ + 1 шагов цепочки и n + 1 шагов параметра. По теореме Е множество результатов R включает множество всех (и„,... ,ui,uo) при Un Ф О, так что (27) вычисляет все полиномы степени п. Доказать, что множество R имеет максимум п степеней свободы, невозможно, поскольку множество результатов имеет п + 1 независимую компоненту.

Полиномиальная цепочка с s шагами параметра имеет максимум s степеней свободы. В известной мере это очевидно: нельзя вычислить функцию с t степенями свободы, используя меньше чем t произвольных параметров. Однако этот интуитивно понятный факт нелегко доказать формально; например, существуют непрерывные функции ("заполняющие пространство кривые"), отображающие действительные прямые на плоскость, которые отображают один параметр на два независимых параметра. Для наших целей необходимо проверить, что нет полиномиальных функций с целыми коэффициентами, которые обладают таким свойством; доказательство можно найти в упр. 28.

Если этот факт имеет место, можно продолжить доказательство требуемых утверждений.

Теорема М (Т. С. Моцкин, 1954). Полиномиальная цепочка с числом умножений т> О имеет максимум 2т степеней свободы.

Доказательство. Пусть pi, р2, Рт -это А;-цепочки, которые являются операцией умножения. Тогда

Pi = S2i-ixS2i для 1<г<т и и{х) = S2m+i, (28)