Переход от коэффициентов многочлена А(х) к его значениям требует времени ©(га2), если мы вычисляем отдельно значение в каждой из га точек по схеме Горнера за в (га) шагов. В дальнейшем мы увидим, что время можно сократить - при подходящем выборе точек достаточно О (га lgra) операций.

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

Теорема 32.1 (Однозначность интерполяции)

Для любого множества {(ж0, у0), (жь yt),..., (жп ь yn-i)} пар аргумент-значение (все жг- различны) существует единственный многочлен А(х) степени ниже га, для которого ук = А(хк) для к = 0,1,..., га - 1.

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

Теорема утверждает, что некоторая матрица обратима. В самом деле, уравнение (32.3) можно записать в матричном виде:

/ 1

1

ж0

Х\

еп-1

п - 1

1 \

„п-1 Jn-1

(

а0

\

J \ an i J

( Уо \

У1

V Уп-i J

(32.4)

Левая матрица называется матрицей Вандермонда (Vandermonde matrix) и обозначается V(xo, х\,..., xn i). Как утверждает упражнение 31.1-10, определитель этой матрицы равен

]<к

Хк

и по теореме 31.5 эта матрица является обратимой (невырожденной), если хк различны. Поэтому коэффициенты многочлена aj однозначно определяются по формуле

а = V(x0, xi,

У-

Это доказательство сводит задачу интерполяции к решению системы линейных уравнений (32.4). Если делать это по общим правилам решения систем линейных уравнений, описанным в главе 31 (LU-разложение), потребуется время О (га3). Более быстрый алгоритм интерполяции основывается на формуле Лагранжа:

п-1

Е

к=0

Ук

П(

Зфк

П {Хк

Зфк

(32.5)

Убедитесь, что правая часть (32.5) представляет собой многочлен степени меньше га и что А(х]Л = Ук Для всех к. В упражнении 32.1-4 предлагается показать, что с помощью формулы Лагранжа можно вычислить коэффициенты многочлена А за время ©(га2).

Таким образом, мы можем переходить от набора га коэффициентов к набору значений в га точках и обратно за О (га2) операций. (Интерполяция является вычислительно неустойчивой операцией. Хотя описанный здесь подход математически корректен, надо понимать, что небольшое изменение входных значений или ошибки округления во время вычислений могут вызвать сильное изменение результата.)

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

{(ж0,у0), (xi,yi), •.., (sn i,yn i)},

а многочлен В - набором

{(х0,у0), {хъу[),..., (хп-у1)},

(заметьте, что значения А и В заданы в одних и тех же га точках), то многочлен С(ж) задается парами

{(х0,Уо + Уо), (xi,yi + yi), •.., (жп 1,уп 1 + уп)}.

Подобным образом можно поступать и с умножением, перемножая значения в каждой точке по отдельности. Надо иметь в виду, однако, что при умножении степени многочленов складываются, и произведение двух многочленов степени меньше га может иметь степень больше га. Она заведомо меньше 2га (даже 2га - 1), так что для восстановления произведения достаточно 2га точек (теорема 32.1). Таким образом, умножая два многочлена Ап В степени меньше га, полезно с самого начала иметь значения многочленов А и В не в га, а в 2га точках (одних и тех для для А ж В). После этого эти значения можно перемножить за за время ©(га) и получить представление произведения С = АВ в виде набора пар аргумент-значение. (Сравните это время с 0(га2) при вычислении коэффициентов произведения по формуле (32.2).)

Осталось обсудить такой вопрос: мы знаем значения многочлена в заданных точках; как найти его значение в точке, которой нет среди них? По-видимому, нет более простого способа сделать это, чем сначала найти коэффициенты многочлена, а затем вычислить его значение в нужной точке.

Быстрое умножение многочленов, заданных вектором коэффициентов

Надписи на самой картинке на стрелках:

Обычное умножение, время ©(га2) Вычисление значений, время ©(ralgra) Интерполяция, время ©(ralgra) Поточечное умножение, время 0(га) в правом столбце:

Представление набором коэффициентов Представление набором значений

Рис. 31.2 32.1 Схема быстрого алгоритма умножения многочленов. В верхней части рисунка многочлены заданы векторами коэффициентов, в нижней - значениями. Стрелки, идущие слева направо, соответствуют умножению. Символы и>2„ обозначают комплексные корни из единицы степени 2п.

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

При этом можно использовать любой набор из га различных точек, но выбрав их удобным образом, можно сократить время преобразования в ту и другую сторону до ©(ralgra). Как мы увидим в разделе 32.2, удобно взять в качестве точек комплексные корни из единицы, в этом случае оба перехода сведутся к так называемому дискретному преобразованию Фурье (Discrete Fourier Transform, DFT) и обратному к нему преобразованию, которые выполняются за ©(ralgra) операций.

Этот план действий изображен на рис. 32.1. Как мы уже говорили, при умножении двух многочленов степени меньше га получается многочлен степени меньше 2га, поэтому для начала мы дополняем многочлены-сомножители нулевыми коэффициентами старших степеней. После этого мы имеем дело с многочленами степени меньше 2га, и потому используем «комплексные корни степени 2га из единицы», обозначаемые иг2п при г = 0,1,... , 2га - 1.

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

1.Удвоение количества коэффициентов. Дополнить вектора коэффициентов, задающие многочлены А(х) и В(х), нулевыми коэффициентами старших степеней так, чтобы в векторах коэффициентов стало по 2га элементов.

2.Вычисление значений. При помощи быстрого преобразования Фурье (применяемого дважды - для А и для В) вычислить значе-