1626435697-9d9ede204f9baad60159c2d6531787c7 (844297), страница 100
Текст из файла (страница 100)
Заметим, что каждая из теорем 12.1 и 12.2 в отдельности не достаточно сильна для этого. Пример 12,10. Рассмотрим задачу умножения двух комплексных чисел а+1Ь и с+Ы, а именно вычисления М -[; ~~Я. Пусть 5 — сама матрица М, а Р— поле вещественных чисел и ~р„'], -О, фч.-Π— векторы из Ра. допустим, что ''~~' 'П::1 Гл. Рк нижние опенки числА АРНФметнческих опеРАций — элемент поля Р. Это произведение равно у,г,а+у,г,Ь+у,г,а— — у,г,Ь. Если оно принадлежит полю Р, то коэффициенты при а и Ь должны равняться нулю.
Поэтому у,г, +у,г, 0 (12.10) у,г,— у,г,=О. (12.11) Допустим, что у,чьО. Тогда из (12.11) получаем ге=у г1/ун Подставив это в (!2.10) и умножив на у„находим, что (у,'+у,')г,=О. Поскольку у,~О, то у',+уечьО и, значит, г,=О '). Тогда в силу (12.11) г,=О. Но равенства г,=г,=О противоречат условию ~,"1 ~0.
Теперь допустим, что у,=О. Если у,=О, то противоречие возникает сразу. Если уе~:О, то, поменяв ролями у, и у, в рассуждении, приведенном выше, получаем, что г,=г,=О; снова противоречие. Таким образом, теорема !2.3 применима к Мх при у=с=2, так что три вещественных умножения необходимы. Программа в примере 12.3 показывает, что три умножения и достаточны. П Теоремы 12.1 — 12.3 можно обобщить на случай, когда в вычислении допускаются деления.
В этом случае надо допускать такие шаги в вычислении, которые при некоторых значениях входов приводят к делению на О. Следовательно, теория, рассматривающая мультипликативные операции (т. е. умножение и деление), предполагает, что поле Р бесконечно. Если бы оно было конечным, то мы могли бы столкнуться с вычислениями, не работакыцими ни для каких входов из-за того, что любой возможный вход приводит к делению на О. С учетом этих изменений каждую из теорем 12.1 — 12.3 можно перенести на случай обеих мультнпликативных операций вместо одного умножения.
В теореме 12.2 определение активной мулылилликативной операции г ч-уей или г ~-у/Ь должно быть следующим: или значение одной из переменных у н Ь включает в себя одну из формальных переменных хн а другой операнд не принадлежит Р, или д принадлежит Р, Ь включает в себя одну иа формальных переменных х, и операцией является деление. вл.у. ПРЕДВАРИТЕЛЬНАЯ ОБРАБОТКА В примере 12.9 мы показали, что вычисление значения полинома л-й степени в одной точке требует п умножений. Однако мы исходили из предположения, что полинам представлен своимн коэффи. ') Здесь существевыо предположевве о том, что Р— поле вмкествеыыых чисел. ыт пппдвлпитвльная овплвоткл циентами. Сейчас изучим задачу минимизации числа умножений.
необходимых для вычисления одного полинома, когда разрешается представлять полином любым множеством параметров, вычисляемых по коэффициентам. Если бы нам было нужно вычислять данный полинам несколько раз, то разумно было бы потратить некоторое время на вычисление другого представления полинома, при условии что новое представление даст более быстрое вычисление. Такое изменение представления называется предварительной обработкой (коэффициентов) '). В примере 12.9 умножение было активным, если один из сомножителей включал в себя коэффициенты а„а„..., а„, а другой не принадлежал г", Таким образом, умножение, в котором оба сомножителя включали коэффициенты и не включали переменную х, считалось за умножение. В случае предварительной обработки мы получаем "даром" все умножения, в которых ни один сомножитель не включает в себя переменную.
Определение. Степенью полинома от нескольких переменных называют наибольшую степень переменных этого полинома. Например, степень полинома р(х, у)=х'+х'уз равна 3. Следующая лемма утверждает, что для любых о+1 полиномов от о переменных существует нетривиальный полинам от и+1 переменных, тождественно равный нулю на данных полиномах. Например, пусть р,=х' и р,=х+х'. Тогда р,+2р",+р",— р',=О для всех х. Лемма 12.2. Пусть р (хы..., х„), 1<!<и,— полиномы. Если п >г, то существует полипом д(уь..., у„), не все коэффициенты которого равны нулю, но для которого у(р„..., р„) как функция от х„..., х„равна тождественно нулю. Д о к а з а т е л ь о т в о. ! 1усть Зл — множество всех полиномов вида р~,'р,'...рД где 0<14<0 для всех!.
Заметим, что (Щ= =(д+1)". Пусть т — наибольшая из степеней полиномов рь Тогда каждый полинам д Е Ял — это полинам от х„х„..., х, степени, не большей дтп. Любой полинам степени с(тп от г переменных можно представить вектором длины (Фин+1)г. Компонентами этого вектора служат коэффициенты при описанных выше членах, расположенных в фиксированном порядке. Поэтому можно говорить о линейной независимости полиномов и, в частности, утверждать, что (по основной теореме линейной алгебры) любое множество, состоящее из (с(тип+1)г+ +! полиномов из 54, должно быть линейно зависимо, т. е. некоторая их нетривиальная сумма должна равняться нулю.
'1 Следуег отметить различие между этой ситуацией и ситуацией из равд. 8.8, где были известиы все точки. в которых нужно вычислять значения полииома. Здесь же перед зычпслеиием значений мы можем работать только с козффициеитамп, а вычисления значений производятся по одному за раз, т. е. в префиксцом, а ие в свободном режиме. 49! гл. ~з. нижние опенки числа аоиьмптических опнплции В частности, если т, и и г фиксированы и и >г, то нетрудно показать, что (й+1)")(йтп+1)' для достаточно большого й, поскольку (й+1)" — полипом более высокой степени по й, чем (йтп+1)'.
Поэтому найдется такое й, что нетривиальная сумма полиномон из Зл будет тождественно равна нулю как функция от х„..., х„. Эта сумма и будет искомым полиномом д. [3 С помощью леммы 12.2 покажем, что любое множество параметров полинома, через которое его коэффициенты выражаются в виде полиномиальных функций, должно содержать и+1 параметров, чтобы представлять произвольный полинам и-й степени.
Лемма 12.3. Пусть М вЂ” взаимно однозначное отображение и- мерного векторного пространства С" коэффициентов на г-мерное векторное пространство 0" параметров. Если М-' таково, что каждая компонента вектора в С" является полиномиольной функцией компонент соответствующего вектора в 0', то г)п. Д о к а з а т е л ь с т в о. Пусть г(п и М ' задается равенствами с,=р~(йь..., й,), где р~ — полиномы, й — параметры и с~— коэффициенты.
В силу леммы 12.2 найдется такой нетривиальный полинам д, что д(см..., с„) — тождественный нуль для всех йь !(1(г '). Но так как сам полипом у не равен тождественно нулю, то найдутся такие полиномы с коэффициентами с„..., с„, что у(с„..., с„)чьО. Этн полиномы нельзя представить в терминах параметров й;, получили противоречие. С) Теперь покажем, что вычисление значения полинома и-й степени в одной точке даже при наличии предварительной обработки требует не менее и/2 умножений. Теорема 12,4.
Вычисление значения произвольного полинома и-й степени в одной точке требует не менее п/2 умножений, даже если не считать входящие в него умножения, которые включают в себя толью коэффициенты полинома. До к аз а тел ь с та о. Допустим, что существует вычисление с т умножениями, включающими в себя неизвестную х. Пусть РезУльтаты этих Умножений — выРажениЯ гм Г„..., 1„. ТогДа каждое выражение (1 можно записать в виде 1!=из!-1(11 "' 6-т, х)+айаг-11н[Узгд, " )г-1. х)+1211, 1(1(т, где каждая функция Е~ линейна по ~у и х, а каждая функция р; полиномиальна по коэффициентам. Полинам р(х), который вычисляется, можно записать в виде Р(х) =Ез „()'„..., 1, х)+Рз„,.
'1 Заметим, что е — полипом по с~ и, значит, по еь поскольку сг — полн- номы по параметрам ЫЬ 493 УПРАЖНЕНИЯ Следовательно, р(х) можно представить новым множеством из 2т+! параметров, а именно множеством функций ][ь Более того, коэф. фициенты полинома р(х) — полиномиальные функции параметров ~ь По лемме !2.3 2т+!)а+1. Таким образом, и-эп/2. П Теорема 12.4 дает нижнюю оценку числа умножений, необходимых для вычисления значения полинома в одной точке, когда проводится предварительная обработка (коэффициеитов).
Значительный интерес вызывает проблема представления полинома, при котором его можно вычислить за и/2 умножений, Но надо не только находить параметры для такого представления полннома, при котором легко вычисляются его значения, но н уметь быстро вычислять эти параметры по коэффициентам полииома. Поэтому хотелось бы, чтобы параметры были рациональными функциями коэффициентов. Техника нахождения таких параметров приведена в упражнениях. УПРАЖНЕНИЯ 12.1.
Пусть Р— поле и х — формальная переменная. Покажите, что множество полиномов от х с коэффициентами из Р образует коммутативное кольцо Р [х] и единица в Р является единицей в Р [х]. 12.2 Покажите, что любое вычисление для выражений ас+ Ы, ас — Ы, Ьс+ Ы, Ьс — аЫ требует не менее четырех умножений, где а, 6, с, б — элементы поля Р. 12.3. Покажите, что любое вычисление произведения вектор- столбца на вектор-строку Га а, [Ьи Ьм Ь А! требует не менее глп умножений. 12.4. Полинам и-й степени от двух переменных х и у имеет в об- л Р гнем случае вид ~ч; 2з ~ацх'у/.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
