Составители:
Рубрика:
рантов и всех лиц, заинтересованных в использовании имеющихся
или в создании новых систем аналитических вычислений.
§1. Быстрое дискретное преобразование
Фурье (БПФ)
1. О понятии многочлена в кольце K
Пусть K – коммутативное, ассоциативное кольцо с единицей, и
пусть буква x – посторонняя для кольца K.
Кратко напомним, как вводится понятие многочлена в кольце K.
Рассмотрим выражение ax
m
(здесь m – неотрицательное целое чис-
ло, а a ∈ K), назовем его одночленом в кольце K и введем (обычные
для комплексных многочленов) действия умножения и приведения
одночленов. Степенью этого одночлена называется число m. Да-
лее введем понятие многочлена как формальной суммы одночле-
нов, где порядок безразличен. Канонической формой многочлена
называется многочлен с приведенными подобными членами, рас-
положенными по убыванию степеней,
P (x) = a
0
x
n
+ . . . + a
n
.
Два многочлена называются равными, если их канонические фор-
мы совпадают.
Сумму и произведение двух многочленов можно определить со-
вершенно формально, написав для них соответствующие равенства
(подробно на этих очевидных вещах останавливаться не будем).
Степенью deg(P ) ненулевого многочлена называется старшая
степень его одночленов. За степень нулевого многочлена O при-
нимают число degO = −∞.
Высшим (старшим) членом ненулевого многочлена называется
первое слагаемое его канонической формы. Считается, что нулевой
многочлен не имеет высшего (старшего) члена.
Нетрудно видеть, что буква x фактически играет роль раздели-
теля: ее безболезненно можно убрать, и упомянутые выше действия
совершать лишь над коэффициентами, помещая их на места, зану-
мерованные показателем степени убранной буквы x.
Предположим, что кольцо K – область целостности, т.е. что про-
изведение двух элементов из K равно нулю только если хотя бы
4
