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