Главная Промышленная автоматика.

циентами. Сейчас изучим задачу минимизации числа умножений, необходимых для вычисления одного полинома, когда разрешается представлять полином любым множеством параметров, вычисляемых по коэффициентам. Если бы нам было нужно вычислять данный полином несколько раз, то разумно было бы потратить некоторое время на вычисление другого представления полинома, при условии что новое представление даст более быстрое вычисление. Такое изменение представления называется предварительной обработкой (коэффициентов) ). В примере 12.9 умножение было активным, если один из сомножителей включал в себя коэффициенты а о. а.х, . . ., а„, а другой не принадлежал F. Таким образом, умножение, в котором оба сомножителя включали коэффициенты и не включали переменную X, считалось за умножение. В случае предварительной обработки мы получаем "даром" все умножения, в которых ни один сомножитель не включает в себя переменную.

Определение. Степенью полинома от нескольких переменных называют наибольшую степень переменных этого полинома. Например, степень полинома р(х, у)=х-{-ху равна 3.

Следующая лемма утверждает, что для любых и+1 полиномов от V переменных существует нетривиальный полином от и+1 переменных, тождественно равный нулю на данных полиномах. Например, пусть pi=x и Pt-x-\-:. Тогда pi-\-2p\-\-p\-pl=Q для всех х.

Лемма 12.2. Пусть Pi(Xi, . . . , Хг), 1<»<п,- полиномы. Если п>г, то существует полином g{yu , Уп), все коэффициенты которого равны нулю, но для которого g{pu • • • , Рп) кал функция от Хи . . . , Хг равна тождественно нулю.

Доказательство. Пусть - множество всех полиномов вида PiPt. . .рп", где 0<t;<d для всех /. Заметим, что 5 = =(d+\)". Пусть т - наибольшая из степеней полиномов pi. Тогда каждый полином qS - это полином от Хи Ха, . . . , Хг степени, не большей dmn.

Любой полином степени dmn от г переменных можно представить вектором длины {dmn+iy. Компонентами этого вектора служат коэффициенты при описанных выше членах, расположенных в фиксированном порядке. Поэтому можно говорить о линейной независимости полиномов и, в частности, утверждать, что (по основной теореме линейной алгебры) любое множество, состоящее из (dmrt+l)4--Ь1 полиномов из Sa, должно быть линейно зависимо, т. е. некоторая их нетривиальная сумма должна равняться нулю.

) Следуег отметить различие между этой ситуацией и ситуацией из разд. 8.5. где были известны все точки, в которых нужно вычислять значения полинома. Здесь же перед вычислением значений мы можем работать только с коэффициентами, а вычисления значений производятся по одному за раз, т. е. в префиксном, а не в свободном режиме.



В частности, если т, п я г фиксированы и п>г, то нетрудно показать, что (d+l)"Xdmrt+l)" для достаточно большого d, поскольку (d+\)"- полином более высокой степени по d, чем [dmn+iy. Поэтому найдется такое d, что нетривиальная сумма полиномов из Sa будет тождественно равна нулю как функция от л:,, . . . , х. Эта сумма и будет искомым полиномом g. □

С помощью леммы 12.2 покажем, что любое множество параметров полинома, через которое его коэффициенты выражаются в виде полиномиальных функций, должно содержать п+1 параметров, чтобы представлять произвольный полином /г-й степени.

Лемма 12.3. Пусть М - взаимно однозначное отобраокение п-мерного векторного пространства С" коэффициентов на г-мерное векторное пространство D параметров. Если М таково, что каждая компонента вектора в С" является полиномиальной функцией компонент соответствующего вектора в D, то гп.

Доказательство. Пусть r<rt и Л!"* задается равенствами Ci-=pi(du . , dr), где Pi - полиномы, di - параметры и Сг - коэффициенты. В силу леммы 12.2 найдется такой нетривиальный полином g, что g{Ci, . . . , с„) - тождественный нуль для всех di, lir ). Но так как сам полином g не равен тождественно нулю, то найдутся такие полиномы с коэффициентами Ci, . . . , с„, чтоg{Cu . . . , Сп)фО. Эти полиномы нельзя представить в терминах параметров dj, получили противоречие. □

Теперь покажем, что вычисление значения полинома п-й степени в одной точке даже при наличии предварительной обработки требует не менее п12 умножений.

Теорема 12.4. Вычисление значения произвольного полинома п-й степени в одной точке требует не менее п/2 умножений, даже если не считать входящие в него умножения, которые включают в себя только коэффициенты полинома.

Доказательство. Допустим, что существует вычисление с т умножениями, включающими в себя неизвестную х. Пусть результаты этих умножений - выражения Д, . . . , f„. Тогда каждое выражение fi можно записать в виде

fi-lLai-Afl.....fi-i. x)+p,i.,]*[L,i{f„ x)+,i],

lim, где каждая функция Li линейна по fj я х, а каждая функция Pi полиномиальна по коэффициентам. Полином р(х), который вычисляется, можно записать в виде

/W=2«+i(/l.....L.

1) Заметим, что g - полином по с/ и, значит, по d,-, поскольку С( - полиномы по параметрам d,-.



Следовательно, р(х) можно представить новым множеством из 2т+1 параметров, а именно множеством функций pj. Более того, коэффициенты полинома р (х) - полиномиальные функции параметров Pi. По лемме 12.3 2m-j-l«4-l. Таким образом, тп/2. □

Теорема 12.4 дает нижнюю оценку числа умножений, необходимых для вычисления значения полинома в одной точке, когда проводится предварительная обработка (коэффициентов). Значительный интерес вызывает проблема представления полинома, при котором его можно вычислить за п/2 умножений. Но надо не только находить параметры для такого представления полинома, при котором легко вычисляются его значения, но и уметь быстро вычислять эти параметры по коэффициентам полинома. Поэтому хотелось бы, чтобы параметры были рациональными функциями коэффициентов. Техника нахождения таких параметров приведена в упражнениях.

УПРАЖНЕНИЯ

12.1. Пусть F - поле их - формальная переменная. Покажите, что множество полиномов от х с коэффициентами из F образует коммутативное кольцо F [х] и единица в F является единицей в F [х].

12.2 Покажите, что любое вычисление для выражений

ac + hd, ас-bd, bc + ad, be-ad

требует не менее четырех умножений, где а, Ь, с, d - элементы поля F.

12.3. Покажите, что любое вычисление произведения вектор-столбца на вектор-строку

[К Ьз.....6„]

требует не менее тп умножений.

12.4. Полином п-й степени от двух переменных хиу имеет в об-

щем случае вид

aijxyi. Покажите, что для вычисления значе-

ния этого полинома с предварительной обработкой коэффициентов необходимо и достаточно (п--1)(п+2)/2-1 умножений.





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 [160] 161 162 163 164 165 166 167 168 169 170 171 172 173 174

0.0021