Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 45
Текст из файла (страница 45)
багаж(агсЬ 35 (1945), 151-155): ( уегге у ую )(( 'о юь и х ф (хо, х~,..., х„), где иъ = 1!(хь — хо) (хь — хь-ь)(хь — хь+~) (хэ — хв). (46) Такой внд (41) также рекомендуется в связи с численной устойчивостью (см. работу Р. Непйс(, Елзепг1аЬ оГ Юшпег1са) Ала)уз)з (Хеп Ъогк: байеу, 1982), 237-243]. Знаменатель (45) равен частичным отношениям дроби 1/(х — хо)(х — х~)... (х -х„). Важное и в некоторой степени неожиданное применение полиномиальной интерполяции открыто Адн Шамиром (Агй Ябапиг) [САСМ 22 (1979), 612-613), который заметил, что полиномы по модулю р можно использовать для "засекречивания".
Иначе говоря, существует возможность разработки системы скрытых ключей или паролей, такой, что, зная любые и + 1 ключей, можно эффективно вычислить магическое число Ю, допустим, открывающее дверь, но, зная любые и ключей, получить какую-либо информацию о Х невозможно. Поразительно простое решение Шамира этой проблемы состоит в выборе случайного полинома и(х) = н„х" + . " + игх + ие, где О с и; < р и р — большие простые числа.
Наждак часть секрета является целым числом х из интервала О < х с р вместе со значением и(х) шог( р, а сверхсекретное число дг равно постоянному члену ие. Задав и + 1 значение и(х;), можно получить Х путем интерполирования. Однако, если только и значений и(х;) заданы, всегда существует единственный поливом и(х), имеющий заданный постоянный член, но такие же значения в точках хм ..., х„, следовательно, и значений не делают одно определенное )т' более вероятным, чем любое другое. Полезно заметить, что интерполирование полннома — только частный случай китайской теоремы об остатках из раздела 4.3.2 и упр. 4.6.2 — 3, так как нам известны значениЯ н(„)(х) по модУлю взаимно пРостых полиномов х — хе, ..., х — х„.
(Как видно из раздела 4.6.2 и обсуждения, следующего за (3), 7'(х) по модулю (х — хо) = ,7(хо).) В такой интерпретации формула Ньютона (42) точно равна "представлению со смешанным основанием" формулы 4,3,2-(25), а 4.3.2 — (24) дает другой способ вычисления ао, ..., а„с помощью такого же числа операций, как и (44). Используя быстрое преобразование Фурье, можно уменьшить время счета при интерполировании до 0(п(!обп)т). Подобное сокращение можно сделать и для таких родственных алгоритмов, как решение китайской теоремы об остатках и вычисление полиномов и-й степени в и различных точках. !См. Е. Ноток!гх, ЬК Ргос.
1,ее!его 1 (1972), 157-163; А. Вогогйп апд К, ЫоепсЬ, Х Сошр. Яуза Яа. 8 (1974), 336-385; А. Вогоб!и, Сошр!ех!гу ог" Вепиеппа) апН Рага)!е! Хшпег!са! А!бог!гйгпз, еб!!еб Ьу 3. Г. ТгаиЬ (Хенч Уотерс Асадеш!с Ргезз, 1973)., 149-180; 1). В1п! ап6 У. Рап, Ро!упош!а! апс! Ма!Их Сшпрпгабопз 1 (Воз!оп: В!гЬЬацзег, 1994), гл. 1.) Однако зти исследования представляют, главным образом, теоретический интерес, поскольку известные алгоритмы требуют достаточно больших затрат времени на другие операции, что делает их непривлекательными, если и не слишком велико.
Замечательное расширение метода разностных отношений, который так же хорошо применим к отношению полиномов, как и к самим полиномам, введено в 1909 году Т. Н. Тьеле (Т. Х. ТЫе!е). Метод Тьеле "обратных разностей" обсуждаегся в книге Л. М, Милна-Томпсона (Ь. М. М!!пе-ТЬошрзоп, Са!сц)из о1 Г!шГе 12!!Уегепсез (1 опбоп: МасМ!!!ап, 1933), гл. 5; см. также работу В. %. Г!оуб, САСМ 3 (1960), 508). зь — — ~ ~~~ !Вьхйуу для 1 < Й < а, (47) где !Вь — определенные козффициенты, принадлежащие некоторому заданному полю. Трехмерная матрица (!ма) называется тензором размера т х их а.
Его можно изобразить, записывая з матриц размера т х и по одной для каждого значения /с. Например, проблема умножения комплексных чисел, т. е, вычисления х! + 132 — (х1 + !хз)(у1 + !уз) = (Ж191 хзу2) + !(х!уз+хзу1) (48) является проблемой вычисления билинейной формы, точно определенной тензором размера2х2х2: 0-1 1 0 Умножение матриц, как зто определено в (34), — зто проблема вычисления семейства билинейных форм, соответствующих особому тензору размера пгп х пв х та.
Преобразования Фурье (37) также можно отнести к втой проблеме, несмотря на то что они не билинейны, а линейны, если допустить, что хь — зто постоянные, а не переменные. Вычисление билинейных форм легче всего изучать, если ограничиться тем, что можно назвать нормальными вычислительными схемами, в которых все умножения в цепочке происходят между линейными комбинациями х-в и линейными комбинациями у-в. Таким образом, мы строим г произведений ш! =(пня~+" +а„,~х,„)(бпуг+ ° ° +Ь„уу„) для 1 < !< с (49) вБилинейные формы. Некоторые из проблем, рассмотренных в данном разделе,— зто частные случаи общей проблемы вычисления множества билинейных я5орм и получаем хь в виде линейных комбинаций этих произведений: хь = еюю1 + + сь„ю„дли 1 с б с ю Здесь все пю б» и сь, принюглежат заданному полю коэффициентов. Сравнив (50) с (47), получаем, что нормальные вычислительные схемы корректны для тензора (1~ ь) тогда и только тогда, когда (51) 10ь = апб;зсы + ° + а;,б,„сь, для 1 < 1 ( гл, 1 С 7' < и н 1 с б с э.
Ненулевой тензор (1; ь) называют тензором ранга "единица", если существуют три таких вектора (аы ..,,а ), (бы...,И„), (сы..., с,), что Ц в = а,б сь для всех 1, 7, я. Это определение можно распространить на все тензоры, утверждая, что рангом тензора (г;.ь) является такое минимальное число г, что (Ц ь) выражается в виде суммы г тензоров единичного ранга над заданным полем. Сравнив это определение с равенством (51), покажем, что ранг тензора есть минимальное число умножений в цепочке при нормальном вычислении соответствующих билинейных форм. Между прочим, когда э = 1, тензор (1; ь) — всего лишь обычная матрица и ранг тензора (10~) равен рангу матрипы (см.
упр. 49), Понятие ранга тензора введено Ф. Л. Хичкоком (Г, Ь. Н1гсбсос(г,,у. Магб. алИ Рбуэ1сэ 6 (1927), 164-189); его применение к проблеме сложности вычисления полинома приведено в важной статье У. Богаээеп, СгеИе 264 (1973), 184 — 202. Схема Винограда (35) для умножения матриц является "анормальной", так как она смешивает значения х и у до их умножения. С другой стороны, схема Штрассена-Винограда (36) не опирается на коммутатнвность умножения, поэтому она нормальна.
На самом деле (36) соответствует следующему способу представления тензора размера 4 х 4 х 4 для умножения матриц размера 2 х 2 в виде суммы семи тензоров единичного ранга: оооо 1ооо оооо оо1о оооо оооо оооо оооо + о 1оо оооо оооо оооо + оооо оооо оооо оооо + оооо оооо оооо оооо + оооо оооо оооо оооо + оооо оооо ооо~ оооо + (Здесь 1 обозначает -1.) Тот факт, что (51) симметрично по 1, 7', б и инвариантно относительно множества преобразований, делает изучение рангов тензоров простым с математической точки зрения н приводит к некоторым удивительным выводам о билинейных формах.
Можно, изменяя порядок индексов 1, 7, /с, получить "транспонированные" билинейные формы, и транспонированный тензор, понятно, имеет такой же ранг, но соответствующие билинейные формы являются, в принципе, совершенно иными. Например, нормальная схема вычисления произведения матрицы размера (гп х и) на матрицу размера (и х е) предусматривает существование нормальной схемы вычисления произведения матрицы размера (и х «) и матрицы размера (» х ш), если используется такое же число умножений по цепочке.
В терминах матриц зги две проблемы едва ли кажутся как-то связанными — онн включают различное число умножений на векторы различной размерности, но в тензорной терминологии онн эквивалентны. (См. В, Я. Пан, 5Ьюехп мат. наук 27,5 (сентябрь-октябрь 1972), 249-250; д. Е. Норсгой апб Л. Мившзй, ЯСОЛХР 2 (1973), 159-173.) если тензор (гоя) можно представить в виде суммы (51) г одноранговых тензорови А, В, С вЂ” матрицы (аи), (69), (см) ссютветствуюшего размера тхг, ихг, эхг, то мы говорим, что (А, В, С) — реа ииэацил тензора (г, ь).
Например, реализация умножения матриц размера 2 х 2 в (52) может быть точно определена матрицами 1010011 1001101 1100000 0100010 В 0101000 С 1011001 (53) 0010111 0011101 1000111 0001111 0011011 1010101 Тензор (10ь) размера т х п х е также можно представить в виде матрицы, объединив ее индексы. Обозначим (103ь) для матрицы размера гпе х гч строки которой указаны парами индексов (1,Я, а столбцы имеют индекс 1ь Аналогично (ге~о~ ) станет матрицей размера в х тп, содержащей Ф,„.е в строке 6 и в столбце (1, 7): (гбьВ) является матрицей размера гпя х и и т.
д. Индексы матрицы.— необязательно целые числа, и здесь упорядоченные пары используются как индексы. С помощью этих обозначений можно получить следующую простую, но полезную нижнюю грань ранга тензора. Лемма Т. Пусть (А, В, С) — реализация телзора (Фив) размера т х и х ж Тогда гапй(А) > гап1Щь>), гагй(В) > гапЩОц) и гшй(С) > гшй(1ь~;О); шшловательно, гапк(1ие) > шак(гагй(110ы), гапк(гдпо), гап)с(гьбг3)). Декезагпельсшее. Из соображений симметрии достаточно показать,что г > гапк(А) > га~й(ги чй). так как матрица А имеет размер т х г, то.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
