3.1.3. Интерполяция надполем

Пусть теперь J — поле, и рассмотрим совокупность «пробных» точек , различны. Тогда задача интерполяции над J состоит в том, чтобы найти полином такой, что

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

Начнем с интерполяции Лагранжа.

Теорема 3.1.7. Пусть — поле, различны. Тогда существует единственный полином степени , такой, что .

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

где

Проверкой убеждаемся, что для благодаря сомножителю в числителе в то время как следовательно, что и требовалось. Более того, по построению .

(Единственность.) Предположим, что существует другой полином такой, что Тогда полином имеет, очевидно, корней, но его степень . Из теоремы 3.1.4 видно, что это может быть только в случае, когда Следовательно,

Пример. Рассмотрим «пробные» точки и пусть Заметим, что значения не обязаны быть все различными, и в примере встречаются одинаковые. Пользуясь формулой Лагранжа и выполняя вычисления в мы получаем следующий полином

Проверка:

Пример. Вычислим такой, что . Работая с множеством неотрицательных целых чисел, получаем

Проверка: над .

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

Из следствия 3.1.3 мы знаем, что если разделить на , то в остатке получим , т.е.

Поэтому , а следовательно,

Если рассматривать как полином-константу, то видно, что мы ввели в отношение сравнимости по модулю полинома. Сравнимость по модулю полинома обладает свойствами, аналогичными свойствам сравнимости для целых чисел, и все факты относительно сравнимости, полученные для целых чисел, остаются справедливыми для сравнимости по модулю . Учитывая, что мы хотим найти такой, что

легко убеждаемся, что задача интерполяции — это частный случай греко-китайской задачи об остатках над

Теперь, конечно, модули — это линейные полиномы, но поскольку все различны, то различны и полиномы следовательно, они удовлетворяют ограничению быть попарно взаимно простыми. (См. теорему 6.2.12 и окружающий ее текст для формального распространения греко-китайской теоремы об остатках на полиномы. Также аналогично случаю целых чисел два полинома взаимно просты, если любой их наибольший общий делитель — константа; см. также следующий раздел.)

Следующая теорема покажет нам, как приспособить к нашим потребностям греко-китайский алгоритм, представленный в гл. 2.

Теорема 3.1.8. Пусть дано поле тогда

Доказательство.

а. Доказательство вытекает из следствия 3.1.3, согласно которому, чтобы найти остаток от деления на достаточно просто вычислить значение в точке

b. По определению мультипликативного обратного нам нужен единственный полином степени такой, что

Поскольку — константа; эта константа равна потому что

Представляем теперь греко-китайский алгоритм, приспособленный к задаче интерполяции.

GCRAn-Interpolation. Интерполяция на основе греко-китайского алгоритма

Вход: значения - различны и J — поле.

Выход: такой, что

1. [Инициализация]

2. [Основной цикл] Для i от 1 до выполнять .

3. [Выход] Вернуть

Анализ времени работы алгоритма GCRAn-Interpolation. Поскольку упомянутый алгоритм используется исключительно над (конечными) полями, сложение и умножение коэффициентов выполняется за время более того, в этом случае расширенный алгоритм Евклида для целых чисел вычисляет мультипликативный обратный данного числа за время

Мы ясно видим, что шаг 2 доминирует над временем выполнения нашего алгоритма. Более того, при итерации шага 2 мы имеем следующие четыре операции:

1. . После этого умножения полином имеет степень i; очевидно, это умножение выполняется за время

Как мы знаем, вычисление над полем значения полинома степени i в данной точке требует времени поскольку обращение выполняется за время ясно, что с вычисляется за время

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

Это выполняется за время

Из приведенных рассуждений мы видим, что итерация шага 2 выполняется за время поэтому итераций шага 2 выполняются за время

что является временем выполнения алгоритма GCRAn-Interpolation.

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

Таким образом, — решение данной задачи интерполяции. Проверка:

Однако если бы последняя «пробная» точка была вместо , то на шаге 2 мы бы получили , что и было бы решением нашей задачи. Проверка:

Читателю следует обратить внимание на то, что точно так же, как в случае алгоритма GCRAk, решение для -точечной задачи интерполяции строится следующим образом:

где вычисляется на итерации описанного алгоритма. С другой стороны, интерполяционная формула Лагранжа дает

Сравнивая две различные формы полинома замечаем, что только первая форма расширяема в том смысле, что присоединить новую «пробную» точку можно, выполнив еще одну итерацию алгоритма GCRAn-Interpolation. С другой стороны, с добавлением новой пробной точки все коэффициенты полинома Лагранжа должны быть вычислены заново.