Например, необходимо вычислить 1.5! по значениям О!, 1!, 2! и 3!, используя кубический полином. Отношения разностей равны

О 1 2 3

У у у" у"

3 3 2

Таким образом, U]o]{x) = иц{х) = 1, И[2](а;) = \х{х-\) + \,ищ{х) = \х{х-1){х-2)-\-а;(а;-1) + 1. Подставляя а; = 1.5 в ищ{х), получаем -.125+.375+1 = 1.25; требуемое "правильное" значение равно Г(2.5) = \ и 1.33. (Но существует, конечно, много других последовательностей, которые начинаются с чисел 1, 1, 2 и 6.)

Чтобы интерполировать несколько полиномов, имеющих те же точки интерполирования Хо, Хх, Хп, но разные значения уо, yi, уп, желательно переписать (41) в виде, предложенном В. Дж. Тейлором (W. J. Taylor) [J. Research Nat. Bur. Standards 35 (1945), 151-155]:

"HW = (f -i)/(j -)

и a; {a;o,a;i,...,a;„}, где

Wk = l/iXk -Xo)... (Xk - Xk-l){Xk - Xk+l) -..{xk- Xn)- (46)

Такой вид (41) также рекомендуется в связи с численной устойчивостью [см. работу Р. Henrici, Essentials of Numerical Analysis (New York: Wiley, 1982), 237-243]. Знаменатель (45) равен частичным отношениям дроби 1/(а; - Хо){х - Xi)... {х - а;„).

Важное и в некоторой степени неожиданное применение полиномиальной интерполяции открыто Ади Шамиром (Adi Shamir) [САСМ 22 (1979), 612-613], который заметил, что полиномы по модулю р можно использовать для "засекречивания". Иначе говоря, существует возможность разработки системы скрытых ключей или паролей, такой, что, зная любые п -Н 1 ключей, можно эффективно вычислить магическое число Л, допустим, открывающее дверь, но, зная любые п ключей, получить какую-либо информацию о N невозможно. Поразительно простое решение

Шамира этой проблемы состоит в выборе случайного полинома и{х) = и„а;" -I-----h

uiX + Uo, где О < Uj < р и р -большие простые числа. Каждая часть секрета является целым числом х из интервала О < а; < р вместе со значением и{х) modp, а сверхсекретное число Л равно постоянному члену ио- Задав п -I-1 значение u{Xi), можно получить N путем интерполирования. Однако, если только п значений u{xi) заданы, всегда существует единственный полином и{х), имеющий заданный постоянный член, но такие же значения в точках Xi, а;„, следовательно, п значений не делают одно определенное N более вероятным, чем любое другое.

Полезно заметить, что интерполирование полинома - только частный случай китайской теоремы об остатках из раздела 4.3.2 и упр. 4.6.2-3, так как нам известны значения Ы[„](а;) по модулю взаимно простых полиномов а; - а;о, • • •, х - Хп- (Как видно из раздела 4.6.2 и обсуждения, следующего за (3), f{x) по модулю [х - Хо) = f{xo)-) В такой интерпретации формула Ньютона (42) точно равна "представлению

со смешанным основанием" формулы 4.3.2-(25), а 4.3.2-(24) дает другой способ вычисления ао, ..., а„ с помощью такого же числа операций, как и (44).

Используя быстрое преобразование Фурье, можно уменьшить время счета при интерполировании до 0(п (log п)). Подобное сокращение можно сделать и для таких родственных алгоритмов, как решение китайской теоремы об остатках и вычисление полиномов п-й степени в п различных точках. [См. Е. Horowitz, Inf. Ргос. Letters 1 (1972), 157-163; А. Borodin and R. Моепск, J. Сотр. Syst. Sci. 8 (1974), 336-385; A. Borodin, Complexity of Sequential and Parallel Numerical Algorithms, edited by J. F. Traub (New York: Academic Press, 1973), 149-180; D. Bini and V. Pan, Poiynomiai and Matrix Computations 1 (Boston: Birkhauser, 1994), гл. 1.] Однако эти исследования представляют, главным образом, теоретический интерес, поскольку известные алгоритмы требуют достаточно больших затрат времени на другие операции, что делает их непривлекательными, если п не слишком велико.

Замечательное расширение метода разностных отношений, который так же хорошо применим к отношению полиномов, как и к самим полиномам, введено в 1909 году Т. Н. Тьеле (Т. N. Thiele). Метод Тьеле "обратных разностей" обсуждается в книге Л. М. Милна-Томпсона (L. М. Milne-Thompson, Calculus of Finite Differences (London: MacMillan, 1933), гл. 5; см. также работу R. W. Floyd, CACM 3 (1960), 508).

*Билинейные формы. Некоторые из пробле.м, рассмотренных в данном разделе,- это частные случаи общей проблемы вычисления множества билинейных форм

т п

Zk = YliJkXiVj для 1 < fc < s, (47)

.=1 j=i

где tijk - определенные коэффициенты, принадлежащие некоторому заданному полю. Трехмерная матрица (tjj*.) называется тензором размератхпхв. Его можно изобразить, записывая s матриц размера m х п по одной для каждого значения fc. Например, проблема умножения комплексных чисел, т. е. вычисления

zi + iz2 = (xi + iX2){yi + гу2) = {Х1У1-Х2У2) + i{xiy2+X2yi), (48)

является проблемой вычисления билинейной формы, точно определенной тензором размера 2x2x2:

Умножение матриц, как это определено в (34), - это проблема вычисления семейства билинейных форм, соответствующих особому тензору размера тп х ns х ms. Преобразования Фурье (37) также можно отнести к этой проблеме, несмотря на то что они не билинейны, а линейны, если допустить, что Хк - это постоянные, а не переменные.

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

Щ = {аиХ1 + --- + ат1Хт){ЬиУ1 + --- + Ьп1Уп) для1</<г (49)

и получаем Zk в виде линейных комбинаций этих произведений:

Zk = CklWi +----1- CkrWr ДЛЯ 1 < fc < s. (50)

Здесь все а, 6 и Ci-r принадлежат заданному полю коэффициентов. Сравнив (50) с (47), получаем, что нормальные вычислительные схемы корректны для тензора [tijk) тогда и только тогда, когда

Ujk = anbjlCkl Н-----h QirbjrCkr

(51)

для l<i<m, l<j<nHl<fc<s.

Ненулевой тензор (tijk) называют тензором ранга "единица", если существуют три таких вектора (oi,...,Om), (6i,...,6„), (ci,...,Cg), что Ujk = aibjCk для всех i, j, к. Это определение можно распространить на все тензоры, утверждая, что рангом тензора (tijk) является такое минимальное число г, что (tijk) выражается в виде суммы г тензоров единичного ранга над заданным полем. Сравнив это определение с равенством (51), покажем, что ранг тензора есть минимальное число умножений в цепочке при нормальном вычислении соответствующих билинейных форм. Между прочим, когда s = 1, тензор (tijk)-всего лишь обычная матрица и ранг тензора (tiji) равен рангу матрицы (см. упр. 49). Понятие ранга тензора введено Ф. Л. Хичкоком (F. L. Hitchcock, J. Math, and Physics 6 (1927), 164-189); его применение к проблеме сложности вычисления полинома приведено в важной статье V. Strassen, Creiie 264 (1973), 184-202.

Схема Винограда (35) для умножения матриц является "анормальной", так как она смешивает значения а; и у до их умножения. С другой стороны, схема Штрассена-Винограда (36) не опирается на коммутативность умножения, поэтому она нормальна. На самом деле (36) соответствует следующему способу представления тензора размера 4x4x4 для умножения матриц размера 2 х 2 в виде суммы семи тензоров единичного ранга:

/1ооо\

0100 0000

Voooo/

/0000\ 0000 1000

Vo100/

/0010\ 000 1 0000

\oooo/

/0000\ 0000 00 10

Vooo 1/

/1000\/1000\/100 0\/1000\ 0000 1/ 0000 / 0000 / 0000

0000 ; 0000 /I 0000 /I 0000 Voooo/ Voooo/ Voooo/ Voooo/

/0000\ 0 100 0000

Voooo/

/ООООч 0000 0000

Voooo/

/ООООч 0000 0000

\0000/

/ООООч 0000 0000

Villi/

/ООООч 0000 0000

voooo/

/ООООч 0000 0000

\0000/

/ООООч 0000 0000

\0000/

/ООООч 0000 0000

\0000/

/ООООч /ООООч /ООО 1ч /ООООч 0000 / 0000 \/ 000 1 \/ 0000 0000 lloOOoil 0001 /1 0000

Voooo/Voooo/ \oooi/Voooo/

/0000\ 0000 0000

Voooo/

/ООООч 0000 0000

Voooo

/0000\ 0000 0000

Voooo/

/001 l\ 0000 ООН,

\0000/

/ООООч 0000 0000

Voooo/

/ООООч 0000 0000

Voooo/

/ooi л

0000 ООН, \0000/

/ООООч /ООООч

0000

iolo Vi 010/

/ioii\ /ioli

0000 0000

1 О 11 I 10 11

Vioi 1/ Vioi ь

0000

i о 1 о Vi о 1 о/

/i о 11\

0000

1 о i 1 \ioi 1/

(52)

(Здесь i обозначает -1.)

Тот факт, что (51) симметрично по i, j, к и инвариантно относительно множества преобразований, делает изучение рангов тензоров простым с математической точки зрения и приводит к некоторым удивительным выводам о билинейных формах. Можно, изменяя порядок индексов i, j, fc, получить "транспонированные"