AOP_Tom2 (1021737), страница 152
Текст из файла (страница 152)
Е. Норсго11, Магй. Сошр. 28 (1974), 231 — 236. До 1978 года несмотря на многочисленные попытки никому не удавалось уменьшить показатель степени Штрассена 187, пока Виктор Пан не обнаружил, что он может быть уменьшен до 1ой„е 143640 ю 2.795 (см. упр. 60). Этот новый прорыв привел к дальнейшему интенсивному исследованию проблемы, и совместные усилия Д.
Бини (П. В1ш), М. Каповани (М. Сарогаш), Д. Копперсмнта (П. Соррегзпи0~), Г. Летти (С. Босг1), Ф. Романи (Р. Ношап1), А. Шенхаге (А. БсЬопЬайе), В. Пана и Ш. Винограда привели к драматическому уменьшению асимптотики времени счета. В упр. 60 — 67 обсуждаются интересные технические приемы, благодаря которым установлены такие верхние грани; в частности, в упр. 66 приведено достаточно простое доказательство того, что достаточно 0(паз') операций. Известная до 1997 года лучшая верхняя грань, равная 0(пз згв), предложена в работе Копперсмита и Винограда [Х.
5ушЬобс Сошр. 9 (1990), 251 — 280). По контрасту лучшая находящаяся в обращении нижняя грань равна 2пз — 1 (см. упр. 12). Эти теоретические результаты совершенно поразительны, но с практической точки зрения они редко используются, так как и должно быть очень большим для того, чтобы можно было преодолеть влияние добавочных факторов. Ричард Брент (ВйсЬагд Вгепг) (81ап(огп Сошрпсег 8с1епсе герогС С8157 (МагсЬ, 1970), см.
также Хпшег. Май. 16 (1970), 145-156) нашел, что аккуратное выполнение схемы Винограда (35) с соответствующим масштабированием численной устойчивости будет лучше традиционного метода только при и > 40. К тому же будет сэкономлено всего 7% времени счета, когда и = 100. Для комплексной арифметики ситуация отчасти иная; схема (35) становится благоприятной для и > 20, и экономится 18% времени прн и = 100. Брент оценил, что схема Штрассена (36) не превосходит (35) до тех пор, пока и ш 250, Такие огромные матрицы на практике встречаются нечасто, поэтому применяются другие технические приемы.
Кроме того, известные методы порядка и"', где ы < 2.7, имеют такую большую константу пропорциональности, что потребуется более 10зз умножений, прежде чем они превзойдут (Зб). По контрасту следующие методы, которые мы обсудим, очень практичны и находят широкое применение. Дискретное преобразование Фурье ~ комплекснозначной функции Е от и переменных по соответствующей области тм ..., т„ элементов определяется равенством для 0 < з~ < ты ..., О < з„< т„.
Слово "преобразование" оправдано, так как можно восстановить значения Е(г„..., г„) по значениям ~(зм..., з„), как показано в у.пр. 13. В особо важном случае, когда все т = 2, получаем (38) обп,...з. <а для 0 < а1,...,а„< 1., и этот метод можно рассматриватгп как одновременное вычисление 2" линейных полиномов от 2" переменных Е(»„..., »и). Общеизвестный технический прием, предложенный Ф. Ятсом (Е. Уа»ез) (Тйе Вез»дп апг» Апа!усбз о» Еас»ог!а! Ехребшеп»э (Нагрепг1еп: 1парепа! Вцгеац о! Бог! Бсаепсей, 1937)], можно использовать для уменьшения числа сложений в (36) от 2" (2п — 1) до п2". Метод Ятеа МОЖНО ПОНятЬ, раССМОтрЕВ СЛуЧай, КОГда П = 3: ПуСтЬ Хг,г,гв — — Е(»Г., »ГИ»З). Задано Г!ервый шаг тово тааг тога таи тгоо тао1 т11о ты 1 Для вычисления от колонки "Задано" к колонке "Первый шага требуется четыре сложения и четыре вычитания; интересной особенностью метода Ятса является то, что точно такое же преобразование, которое действует от колонки "Задано" к колонке "Первый шаг", будет действовать от колонки "Первый шага к колонке "Второй шага и от колонки "Второй шаге к колонке "Третий шаг".
В каждом случае выполняется четыре сложения и затем четыре вычитания, а после трех шагов магически получается требуемое преобразование Фурье »(в1, ври аз) на месте, пеРвоначально занимаемом Е(а1, зю вз). Этот особый случай часто называют преобразованием Уолша 2" данных элементов, поскольку соответствующая модель знаков изучена Дж. Л, Уолшем (,!. Ь. %а!з!1) (Ашег. Ь Ма»»ь 45 (1923), 5 — 24). Заметим, что число перемен знаков »лева направо в колонке "Третий шага принимает соответствующие значения О, 7, 3, 4, 1, 6, 2, 5. Это перестановки чисел (О, 1,2,.3,.4,5,6, 7). Уолш заметил, что будет точно О, 1,..., 2" — 1 изменений знаков в общем случае, если соответствующим образом переставить преобразованные элементы. При этом коэффициенты обеспечивают дискретную аппроксимацию синусоидами с различными частотами.
(См, работу Н. г. Нагшц»Ъ, 1ЕЕЕ прес»гцпа 6, 11 (НорешЪег, 1969), 82- 91, в которой речь идет об использовании этого свойства; дополнительно коэффициенты Уолша обсуждаются в разделе 7.2.1.) Метод Уолша можно обобщить для оценки любого дискретного преобразования Фурье и фактически для оценки любого числа сумм„которые можно записать в общем виде 7 (а1, зг,..., ап ) = д»(ам йю..., вп. »Г)дз(йа,..., йп~ »з) ° ° дп(вп~ »п)Е(»»1»з ° ° ~ »п) (39) 0<11<ш1 а<». < тово-1-тао1 таы+то11 т1оо+тго1 тио+ти, тооо-тоо1 тога — то11 тгаа — тго1 тио — гиг Второй швг тооа+тоо11тога+топ тгао+тгог+тиоэт111 тово-тана.раааа — тои тгао-тго1+тгы — тги тоаоэтоог-тога — то11 тыарт,ш -т,ы-ти, тово — тоог — того-1-та11 тгоа — тго1 — т11о.~-т111 Третий шаг тооаэтоо1+Го1оето11 1 тгоо 1 тенг+Гага~.там тооа -тоо1.ааааа-тои Раааа-тго1+тио-тиг таво+ тоог — того — то~ г а.тгоо.ртгог-т ив-т и 1 твоа-тоа1 — та1артои 1-тгоо — т1а1-тио+тиг оооытоогттоготтогг — т1оо-тао1-тио-т111 тооо-тоог+тоао — тои -*1оо+тгоа — тгырт1и таао+тоо1 — того-тои -тын-тгаиртгга +т111 тово-тоа1 — та1оетои — тгао 1-т1а1+т1ы тиг для 0 < в < пг и заданных функций д (»,..., Вп, ! ).
Мы поступим следующим образом: го(!1122 23~ ° ° ° ~ гп) — г (21~ 22, ЗЗ ° 1сп)! !!(»а|с!~!2~ ° ~гп-1) ~Х' дп(8 мгп)20(21~ 22 ° ° ° гп)! О<1„<п1„ 22(8 — 1 8 !11. ! -2) Е д — 1(в -1 в ! — 1)21(8 21 .. ! — 1) О<1„, <юп„ гп(81~ Вгз ВЗ~ ° °; Вп) = ~' д!(81~ ° ° ° ~ Вп121) гп — 1(82~ ЗЗ, ° ° » Яп~ 21)! о<1, <., (40) 1(81~82182~ " ~88) гп(81 82~88~ 18п). ДлЯ метоДа Ятса, как показано выше, д (в,, зп, ! ) = (-1)' "; Уо(21, 22, 22) пРеДСтаапяЕт КОЛОНКУ "ЗадаНО", /1(82,21,сг) — КОЛОНКУ "ПЕрВЫй Шатп И т.
д. ВСяКИй раз, когда множество сумм можно представить в виде (39) для умеренно простых функций д,(81,..., Яп, сз), схема (40) будет уменьшать количество вычислений от ПОрядКа Хг дО ПОрядна гУ!О8Ю ИЛИ ОКОЛО ТОГО, ГдЕ !!! = П21... 1нп — КОЛИЧЕСТВО данных точек. К тому же данная схема идеально подходит для параллельного вычисления. Важный особый случай одномерного преобразования Фурье обсуждается в упр.
14 и 53; одномерный случай также приводится в разделе 4.3.3С. Рассмотрим более частный случай вычисления полинома. Интерполяционный полипом Лагранжа порядка и, который мы запишем в виде (Х-Х1)(Х вЂ” Хг)... (Х-Хп) (Х вЂ” ХО)(Х-Хг) .. (Х вЂ” Хп) и(п)(х) = уо +У1 (хо — х1)(хо — хг)... (хо — х ) (х1 — хо)(х! — хг)... (х1 — х ) (Х -ХО)(Х - Х1)... (Х - Хп 1) + ° + уп и, (41) (Хп-ХО)(яп-Х1)" (Хп-Хп-1) является только полиномом от х степени < и, который принимает соответствующие значениЯ Уо, У1,, Уп в и+1 Различной точке х = хо, х1,..., хп. (Из (41) очевиДно, что и(п)(хв) = Ув ДлЯ О < В < и. Если У(х) — любой такой полинам степени < и, то д(х) = г (х) — и(п)(х) имеет степень < и и д(х) равно нулю для х = хо,х1,... ...,хп; следовательно, д(х) должен быть кратен поливому (х-хо)(х — х!)...
(х — хп). Степень последнего полинома больше и, поэтому д(х) = 0.) Если предположить, что значения функции табулированы и хорошо аппроксимируются полиномом, то формулу (41) можно использовать для "интерполирования" значений функции в точках х, не занесенных в таблицу. Лагранж предложил (41) своим ученикам в Рапв Есо!е !4огша!е в 1795 году [см. (Еиггев 7 (Рапв, 1877), 286), однако Эдвард Уоринг (Ебггаг1! %аг!пй) из Кембриджского университета к тому времени уже представил такую же формулу, совершенно точно и ясно сформулированную в Р)г!!оворЫсв! 2гапвасс!опв 69 (1779), 59-67. На первый взгляд кажется, что в формулах Уоринга и Лагранжа совсем немного сложений, вычитаний, умножений и делений; на самом деле — точно и сложений, 2п'+ 2п вычитаний, 2пг+ и — 1 улэножений и и+ 1 делений.
Но, к счастью (как мы подозревали), возможно улучшение. Основная идея упрощения (41) учитывает тот факт, что и(„1(х) — и~„э) (х) = О лля х = хо,...,х„ы таким образом, и~ы(х) — иы Н(х) — полипом степени и или меньше, кратный (х — хо)... (х — х„,). Можно сделать вывод, что иьй(х) = а„(х — хо)...(х — х„-э) + ш„-й(х), где а„— константа. Это приводит к интерполяционной формуле Ньютона и~„1(х) = а„(х — хо)(х — хз)... (х — х„1) +. + аг(х — хо)(х — хэ) + аэ(х — хо) + ао, (42) где ае — коэффициенты, которые необходимо определить по заданным числам хо, хе, уо, уэ, ..., у„.
Заметим, что эта формула имеет место для всех и; коэффициент ае не зависит от хеэ,, х„или от уееэ,..., у„, Когда ае известны, интерполяционная формула 11ьютона удобна для вычислении, так как можно снова обобщить правило Горээера и записать ищ1(х) = ((... (а„(х — х„э) + а„э)(х — х„г) + )(х — хо) + ао). (43) Это потребует и умножений и 2п сложений. Иначе можно вычислить каждый отдельный член (42) справа налево,.
выполнив 2п — 1 умножений и 2п сложений, мы вычислим все значения и(о)(х), и(Н(х), ..., и(„)(х), что во всяком случае покажет, будет ли сходиться интерполяционный процесс. Коэффициенты ае в формуле Ньютона можно найти, вычисляя ошношенил разностей по следующей таблице (показано для и = 3). (у~ уо)/(хэ хо) = уэ (Уг У1)/(Х2 Х1) У2 (УЗ У2)/(ХЗ Х2) УЗ (Уг — Уэ)/(хг хо) = Уг (УЗ У2)/(ХЗ Хэ) УЗ Уэ (УЗ вЂ” Уге)/(ХЗ-ХО) = Узе У2 (44) Начать с (ао,аэ,...,ае) +- (уо, ум ° , уе); затем для к = 1, 2,...,п (в таком порядке) присвоить аз < †(а .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
