8.7. КИТАЙСКАЯ ТЕОРЕМА ОБ ОСТАТКАХ И ИНТЕРПОЛЯЦИЯ ПОЛИНОМОВ

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

Теорема 8.13. Пусть полиномы степени не больше число арифметических операций, необходимых для умножения двух полиномов степени Пусть такие полиномы, что степень полинома меньше степени полинома существует алгоритм с предварительной обработкой данных, вычисляющий за время тот единственный полином степени, меньшей степени полинома для которого

Доказательство. Применяется аналог алгоритма 8.5 и доказательство следует доказательству теоремы 8.12.

Следствие. Существует алгоритм восстановления полиномов по остаткам (согласно китайской теореме) с временной сложностью

Рассмотрим один важный частный случай: все модули имеют степень 1. Если то вычеты (числа постоянны, т. е. являются полиномами степени 0. Если и то значит, Таким образом, единственным полиномом и степени, меньшей для которого и будет тот единственный полином степени, меньшей для которого для каждого Другими словами, -это полином, интерполируемый по значениям в точках

Поскольку при работе с полиномами интерполяция очень важна, мы с удовольствием отметим, что интерполяцию по значениям в точках можно выполнить за время даже если нет предварительной обработки данных. Это объясняется тем, что здесь, как мы увидим из следующей леммы, легко найти значения коэффициентов из

Лемма 8.3. Пусть для где все различны (т. е. все взаимно просты). Пусть постоянный полином, причем Тогда где

Доказательство. Запишем так что

Далее, поэтому

Заметим, что обладает тем свойством, что значит, при некотором Таким образом, Теперь лемма немедленно следует из (8.22), поскольку постоянная.

Теорема 8.14. Интерполяцию полинома по значениям в точках можно выполнить за время без предварительной обработки данных.

Доказательство. В силу леммы 8.3 вычисление полиномов эквивалентно вычислению значений производной некоторого

полинома степени точках. Полином можно получить за время если сначала вычислить затем Производную полинома можно найти за шагов. Вычисление значений производной занимает времени в силу следствия 2 теоремы 8.10. Теорема вытекает теперь из следствия теоремы 8.13 при

Пример 8.7. Проинтерполируем полином по следующим парам (точка, значение): Здесь для Тогда а полином равен Далее, и в точках 1, 2, 3, 4 этот полином принимает соответственно значения —6, 2, —2, 6. Таким образом, равны соответственно . С помощью быстрого китайского алгоритма 8.5, переделанного для полиномов, получаем

и затем

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

Метод БПФ именно это и делает в случае, когда в качестве точек берутся числа Здесь алгоритмы вычисления значений и интерполяции оказались особенно простыми благодаря ствойствам степеней числа и специального упорядочения их. Однако стоит заметить, что вместо степеней числа можно было бы взять любой набор точек. Тогда у нас было бы такое

"преобразование", что на всю задачу (преобразование, вычисления и обратное преобразование) потребовалось бы а не времени.