Вычисления результанта 2-ч полиномов

Министерство образования и науки РФ 
ФБГОУ ВПО «Сочинский государственный университет»

Факультет экономики и процессов управления

Кафедра общей математики и информатики

 

 

 

                                        КУРСОВАЯ РАБОТА 

 

По дисциплине: элементы абстрактной и компьютерной алгебры

Тема: вычисление результата 2-х полиномов

 

 

 

 

 

 

                                                         Руководитель: Иванова Милена Николаевна

         Группа:12-ИНФ

                                       Ф.И.О. студента: Лесовская А.Ю.

 

                                    

                                     Сочи 2013

 

Содержание

 

1.    Введение                                                                                                          3

2.    Полиномиальные  алгоритмы                                                                         5

2.1   Алгоритм вычисления ad mod m                                                                   5

2.2   Дихотомический  алгоритм возведения в степень                                       6

2.3   Алгоритм Евклида                                                                                          7

2.4   Алгоритм решения  уравнения ax + by = 1                                                   9

2.5   Полиномы Чебышева                                                                                     9

3.    Полиномиальная  арифметика                                                                       12

3.1. Алгоритм нахождения делителей многочлена f(x) в кольце Fp[x]           13

3.2. Произведение и возведение в степень многочленов, заданных

       массивами                                                                                                        14

3.3. Небольшие оптимизации для произведения многочленов                         17

Список литературы

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Введение

 
     В математике, многочлены или полиномы от одной переменной — функции вида  , где c фиксированные коэффициенты, а x — переменная. Многочлены составляют один из важнейших классов элементарных функций. 
     Изучение полиномиальных уравнений и их решений составляло едва ли не главный объект «классической алгебры». С изучением многочленов связан целый ряд преобразований в математике: введение в рассмотрение нуля, отрицательных, а затем и комплексных чисел, а также появление теории групп как раздела математики и выделение классов специальных функций в анализе. Техническая простота вычислений, связанных с многочленами, по сравнению с более сложными классами функций, а также тот факт, что множество многочленов плотно в пространстве непрерывных функций на компактных подмножествах евклидова пространства (см. аппроксимационная теорема Вейерштрасса), способствовали развитию методов разложения в ряды и полиномиальной интерполяции в математическом анализе. Многочлены также играют ключевую роль в алгебраической геометрии, объектом которой являются множества, определённые как решения систем многочленов. Особые свойства преобразования коэффициентов при умножении многочленов используются в алгебраической геометрии, алгебре, теории узлов и других разделах математики для кодирования, или выражения многочленами свойств различных объектов.  Весьма удобным является представление двоичных чисел в виде полиномов степени n -1, где n – количество разрядов числа. 
    Идея представления числа в виде полинома состоит в следующем – основание системы счисления заменяется некоторой фиктивной переменной, например x. Степень этой переменной будет соответствовать номеру разряда числа, а коэффициент значению самого разряда. Рассмотрим пример: Запишем двоичное число и его разложение в виде степеней двойки (аналогично переводу в десятичную систему счисления):

  . Теперь, заменим двойку на фиктивную переменную x, при этом получим выражение:

  
Исключив элементы с нулевым коэффициентом, получим полиномиальное представление числа: .

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Полиномиальные алгоритмы

 

     Четыре приведённых ниже алгоритма относятся к разряду так называемых

полиномиальных алгоритмов. Это название носят алгоритмы, сложность которых оценивается сверху степенным образом в зависимости от длины записи входящих чисел. Если наибольшее из чисел, подаваемых на вход алгоритма, не превосходит m, то сложность алгоритмов этого типа оценивается величиной O(ln cm), где c – некоторая абсолютная постоянная. Во всех приведённых примерах с =1.Следующий алгоритм вычисляет admod m. При этом, конечно, предполагается, что натуральные числа a и d не превосходят по величине m.

 

 

2.1 Алгоритм вычисления ad mod m

 

1.  Представим d в двоичной системе счисления d = d0

     2r+.+dr-12+dr, где di, цифры в двоичном представлении, равны 0 или 1,

     d0 = 1.

2.     Положим a0 = a и затем для i = 1,.,r вычислим ai  º a2i-1adi (mod m).

3.     ar есть искомый вычет admod m.

    

Справедливость этого алгоритма вытекает из сравнения

 

ai

º a2i-1ad02^i+.+di

(mod m), легко доказываемого индукцией по i.

Так как каждое вычисление на шаге 2 требует не более трёх умножений по модулю m и этот шаг выполняется r £ log2 m раз, то

сложность алгоритма может быть оценена величиной O(ln m).

           

 

 

2.2 Дихотомический  алгоритм возведения в степень.

     В общем виде дихотомический алгоритм позволяет вычислить n–ю степень в моноиде. Будучи применён к множеству целых чисел с операцией сложения, этот метод позволяет умножать два целых числа и более известен как египетское умножение. Классический алгоритм возведения в степень посредством последовательного умножения характерен, главным образом, своей неэффективностью в обычных обстоятельствах – его время работы линейным образом зависит от показателя степени.

Возьмём моноид М с операцией умножения и рассмотрим некоторый элемент x0 из М, а также произвольное натуральное число n0. Для того, чтобы вычислит, представим n0 в двоичной системе счисления:

 n0 = bt2t + bt – 12t – 1 + . + b121 + b020, предполагая, что n0 содержит (t +1) двоичных цифр (т.е. что bt ¹ 0 и bt + 1 = 0). В этих условиях вычисляемое выражение может быть записано:

Или же

     Если задана последовательность (xi)0 £ i £ t, первый элемент которой есть     x0 и xi для iÎ [1,t] определено соотношением   xi = xi – 12, то можно записать        = P{xi | 0£ i £ t, bi ¹ 0}. Чтобы завершить построение алгоритма и иметь возможность получить значение предыдущего произведения, необходимо вычислить биты bi числа n0. Для последовательности (ni) 0 £ i £ t+1                    (с начальным элементом n0), определённой соотношением ni = [ni–1/2] для любого i Î [1, t + 1], бит bi равен нулю, если ni чётно, и равен единице в противном случае. Первое значение индекса i, для которого ni равно нулю, есть t + 1. Ясно, что число итераций, необходимых для выполнения алгоритма, зависит толькоот показателя n.

2t £ n £ 2t + 1  или   t £ log2n < t + 1.

Первая часть этого свойства может быть выражена следующим образом: [ + 1] = 0 и [n/2t]¹ 0, что позволяет точно определить число совершаемых делений n, равное числу итераций алгоритма при заданном значении n. Очевидно, нужно совершить t + 1 итераций, чтобы выполнить алгоритм, т. е. [log2n] + 1 итераций. Следовательно, трудоёмкость алгоритма есть O (log n). Третий алгоритм – это классический алгоритм Евклида вычисления наибольшего общего делителя целых чисел. Мы предполагаем заданными два натуральных числа  a и b и вычисляем их наибольший общий делитель (a,b).

 

 

 

3. Алгоритм Евклида

 

1.     Вычислим  r – остаток от деления числа a на b, a = bq+r, 0 £ r < b.

2.     Если r = 0, то b есть искомое число.

3.     Если r ¹ 0, то заменим пару чисел (a,b) парой (b,r) и перейдём к шагу 1.

 

     Не останавливаясь на объяснении, почему алгоритм действительно находит (a,b), докажем некоторую оценку его сложности.

     Теорема 1. При вычислении наибольшего общего делителя (a,b) с помощью алгоритма Евклида будет выполнено не более 5p операций деления с остатком, где p есть количество цифр в десятичной записи меньшего из чисел a и b.

     Доказательство. Положим r0 = a > b и определим r1,r2,.,rn -последовательность делителей, появляющихся в процессе выполнения шага 1

алгоритма Евклида. Тогда r1 = b,., 0 £ ri+1 < ri,  i = 0,1,.,n - 1.

Пусть также u0 = 1, u1 = 1, uk+1 = uk+uk-1, k ³ 1, - последовательность Фибоначчи. Индукцией по i от i = n - 1 до i = 0 легко доказывается неравенство ri+1 ³ un-i. А так как un ³ 10(n-1)/5, то имеем неравенства 10p > b = r1 ³

un ³ 10(n-1)/5 и n < 5p+1.

     Немного подправив алгоритм Евклида, можно достаточно быстро решать сравнения ax º 1 (mod m) при условии, что (a,b) = 1. Эта задача равносильна поиску целых решений уравнения ax + by = 1.

 

 

 

 

2.4 Алгоритм решения  уравнения ax + by = 1

     Определим  матрицу E =

1. Вычислим r – остаток от деления числа a на b, a = bq + r, 0 £ r < b.
2. Если r = 0, то второй столбец матрицы Е даёт вектор (x y)   решений уравнения.
3. Если r ¹ 0, то заменим матрицу Е матрицей
4. Заменим пару чисел (a,b) парой (b,r) и перейдём к шагу 1.

     Если обозначить через Еk матрицу Е, возникающую в процессе работы алгоритма перед шагом 2 после k делений с остатком (шаг 1), то в обозначениях из доказательства теоремы 1 в этот момент выполняется векторное равенство (a,b)*Ek = (rk-1,rk). Его легко доказать индукцией по k. Поскольку числа a и b взаимно просты, имеем rn = 1, и это доказывает, что алгоритм действительно даёт решение уравнения ax + by = 1. Буквой n мы

обозначили количество делений с остатком, которое в точности такое же, как и в алгоритме Евклида.

    Полиномиальные алгоритмы в теории чисел – большая редкость. Да и оценки сложности алгоритмов чаще всего опираются на какие-либо не доказанные, но правдоподобные гипотезы, обычно относящиеся к аналитической теории чисел. Для некоторых задач эффективные алгоритмы вообще не известны. Иногда в таких случаях всё же можно предложить последовательность действий, которая, «если повезёт», быстро приводит к требуемому результату. Существует класс так называемых вероятностных алгоритмов, которые дают правильный результат, но имеют вероятностную оценку времени работы. Обычно работа этих алгоритмов зависит от одного или нескольких параметров. В худшем случае они работают достаточно долго. Но удачный выбор параметра определяет быстрое завершение работы. Такие алгоритмы, если множество «хороших» значений параметров велико,

на практике работают достаточно эффективно, хотя и не имеют хороших оценок сложности.

2.5 Полиномы Чебышева

 
     Допустим, задана  функция y(x), это означает, что любому допустимому значению х сопоставлено значение у. Но иногда оказывается, что найти это значение очень трудно. Например, у(х) может быть определено как решение сложной задачи, в которой х играет роль параметра или у(х) измеряется в дорогостоящем эксперименте. В этом случае можно вычислить небольшую таблицу значений функции, но прямое нахождение этой функции при большом числе значений аргумента будет практически невозможно. Функция у(х) может существовать в каких-нибудь физико-технических или математических расчётах, где её необходимо будет многократно вычислять. В этой ситуации удобно заменить функцию у(х) приближённой формулой, то есть подобрать некоторую функцию j(х), которая приближается   в некотором смысле к у(х) и просто вычисляется. Затем при всех значениях аргумента полагать, что у(х) j(х). Основная часть классического численного анализа основывается на приближении многочленами, потому как с ними легче работать. Однако для большинства целей используются другие классы функций. Выбрав значимые точки и класс приближающих функций, нам необходимо ещё выбрать одну определённую функцию из этого класса посредством какого-то критерия — некоторой меры приближения или «равенства». До того как начать вычисления, мы должны решить также, какую точность нам надо в ответе и какой критерий мы выбираем для измерения этой точности.

 
Всё изложенное выше можно сформулировать в виде четырёх вопросов:

1. Какие значимые точки мы будем использовать?
2. Какой класс приближающих функций будет нами использован?
3. Какой критерий согласия «равенства» мы применим?
4. Какая точность нам необходима?

     Существуют три группы функций, которые широко применяемых в численном анализе. Первая группа включает в себя линейные комбинации функций 1, х , х 2 , …, х n , что совпадает с классом всех многочленов степени n (или меньше). Второй класс - включает в себя функции cos a i x , sin a i x . Этот класс имеет непосредственное отношение к рядам Фурье и интегралу Фурье. Третья группа образована функциями e - az . Эти функции часто встречаются в реальных ситуациях, к ним, например, часто приводят задачи накопления и распада.

    Что касается критерия согласия или «равенства», то классическим критерием согласия является «точное совпадение в значимых - узловых точках». Этот критерий обладает преимуществами простоты теории и выполнения вычислений, но он также имеет неудобство из-за игнорирования шума (погрешности, возникающей при измерении или вычислении значений в значимых (узловых) точках). Другой достаточно хороший критерий — есть «наименьшие квадраты». Это означает, что сумма квадратов отклонений в узловых точках должна быть наименьшей возможной или, другими словами, приведена к минимуму. Этот критерий использует неточную информацию, чтобы получить наименьшее количество шума. Третий критерий напрямую связан с именем Чебышева. Основная идея его заключается в том, чтобы привести максимальное отклонение к минимуму. Конечно, могут быть возможны и другие критерии. Более точно ответить на поставленные нами четыре вопроса можно лишь исходя из условий и цели каждой задачи в отдельности. 
     Критерии согласия данного метода — минимизация максимальной ошибки Полиномы Чебышева определяются следующим образом:

T n ( x )= cos ( n Ч arccos ( x ))

Например: 

T 0 ( x )= cos (0)=1,

T 1 ( x )= cos ( q )= x ,

T 2 (x)= cos (2 q )=cos 2 ( q )-sin 2 ( q )=2x 2 -1

    Можно было бы и дальше использовать тригонометрические соотношения для нахождения полиномов Чебышева любого порядка, но будет лучше установить для них рекуррентное соотношение, связывающее

T n +1 ( x ), T n ( x ) и T n -1 ( x ):

T n+1 (x)= cos (n q + q )= cos (n q ) cos ( q )-sin(n q )sin( q ),               

T n-1 (x)= cos (n q - q )= cos (n q ) cos ( q )-sin(n q )sin( q )

Складывая эти неравенства, получим: