Д. Кнут - Искусство программирования том 2 (3-е издание) - 2001 (Часть 2) (1119454), страница 44
Текст из файла (страница 44)
К тому же будет сэкономлено всего 7% времени счета, когда и = 100. Для комплексной арифметики ситуация отчасти иная; схема (35) становится благоприятной для и > 20, и эконоьштся 18% времени при и = 100, Брент оценил, что схема Штрассена (36) не превосходит (35) до тех пор, пока и и 250. Такие огромные матрицы на практике встречаются нечасто, позтому применяются другие технические приемы. Кроме того, известные методы порядка п"', где ы с 2,7, имеют такую большую константу пропорциональности, что потребуется более 10ш умножений, прежде чем они превзойдут (36). По контрасту следующие методы, которые мы обсудим, очень практичны и находят широкое применение.
Дискретвное преобразование Фурье ~ комплекснозначной функции Г от и переменных по соответствующей области тпы ..., гп„ злементов определяется равенством для О < йа,.... й„< 1, и этот метод можно рассматривать, как одновременное вычисление 2" линейных полиномов от 2" переменных Г(8!,....1н). Общеизвестный технический прием, предложенный Ф. Ятсом (Г. Тасей) [ТЬе Пеайп ап!! Апа!уь4з оГ Еэсгогаа! Ехрстипепгй (Нйгрепбвп! 1гпреНа! Впгеап о( Бо!! Вс!евсей, 1937)], можно испольювать лля уменьшения числа сложений в (38) от 2" (2" — 1) до п2".
Метод Ятса можно цокать, РассмотРев слУчай, когда и = 3! пУсть хо,!ато — — е(!! ! гз, гз). Задано третей айаг аооа+аыи+аои+аа11+т1ао+т1о1+вне+а!и аоао-аао!+ного-ао1!+а1оо-а1о1+тио-аи! оооо+нов!-ао!о-аои+а1ао+тао1-а!1о-а1и тооо-том -*о!о+то! 1 +аио-т !о! -тио+ааи аооо етом +а ма+ тон -т1оо-а!о! -а!!о-а!и а оаа аоа! *о!о таи твоа-нам+во!о-тои -а!ао+т ив -ти о+о!и *ооо+аео1-тои-та!1-аио-а!о!+а!и+ни! и!о! аио аом-аам -ао!о+ааи -а 1 от+а !в!+а и о-аи! ти1 Для вычисления от колонки "Задано" к колонке "Первый шага требуется четыре сложения и четыре вычитания; интересной особенностью метода Ятса является то.
что точно такое же преобразование, которое действует от колонки "Задано" к колонке "Первый шаг", будет действовать от колонки "Первый шаг" к колонке аВторой шага н от колонки "Второй шаг" к колонке "Третий шаг". В каждом случае выполняется четыре сложения и затем четыре вычитания, а после трех шагов магически получается требуемое преобразование Фурье 7"(йа,зги аз) на месте, первоначально занимаемом Р(й!, йю йз). Этот особый случай часто называют преобрйзованиеда Уолша 2" данных элементов, поскольку соответствующая модель знаков изучена Дж. Л. ЪЪлшем (д.
1,. %а!э!!) [Ашег. 7. Ма!7!. 45 (1923), 5-24!. Заметим, что число перемен знаков слева направо в колонке "Третий шага принимает соответствующие значения О, 7, 3, 4, 1, 6, 2, 5. Это перестановки чисел (6,1,2,3,4,5,6,7). Уолш заметил! что будет точно О, 1,..., 2" -1 изменений знаков в общем случае, если соответствующим образом переставить преобразованные элементы, Прн этом коэффициенты обеспечивают дискретную аппроксимацию синусоидами с различными частотами. (См. работу Н. Г.
НвгшпНц )ЕЕЕ Зресггнш 6, 11 (Нореш!тег, 1969), 62-91, в которой речь идет об использовании этого свойства; дополнительно коэффициенты Уолша обсуждаются в разделе 7.2. Ц Метод Уолша можно обобщить дйя оценки любого дискретного преобразования Фурье н фактически для оценки любого числа сумм, которые можно записать в обшем виде 7" (йь, йт,..., йн) = С;- д,(й„йю„,й„,!!)дй(й„...,йн,1,)...рн(й.,1.)Е(!!,!Зг " ! ) (39) 0<а! <!н! О<1„<га Первый иаг аааа+ааа1 аа!о гто!1 *ио+а1о1 юи !-а!и тово ном амо-*ои а1ю т1о1 тио-аги Второй иог таоо+аан+аои+аои ааоо+а!о!+а!и+а!и ааао аоо1.~-хаи аои аио -а 1м+ а!!о -а! и аооо+аоа1-таи-таи аио+а1о1-аиа-аи! оооо-аоо! -*о!о+еои т!оо-ти!-а!!о+ни! для 0 < 01 < тз и виданных функций 9~(вз,...,зи,г,).
Иы поступим следующим образом: 10(21~32 13 ° . ° зги) = Р(31~32,33>» ° ~ ги)ю 11(30~21,22, ° ° °,ги-1) = ~ йи(ви,ги)70(ГЬ32, ° °,ги)~ 0<1 <~и 12(З -1~3,11, °,1 -2) = ~ йи 1(ви-мзи,ги 1)11(зи,с1,...,1 1); 0<1 1 <10 1 У ( 3 Зи) — ~ 91(31,...,30,31)У -1(32 33: ° .
3 ~1)~ 0<11<ш1 у(з„зз,зз,....,в„) =~„(01,32,03 " в ). (40) для метода Етса, как покззаио выше, 91(ззч..., 3 31) = ( 1) ' ' Ь("1 32' 3) пРел СтаапяЕт КОЛОНКУ "ЗадаНО", 71(В3,31,12) — КОЛОНКУ иПЕРВЫй Шати И т. д. ВСяКИй раз, когда множество сумм можно представить в виде (39) для умеренно простых функций 91(31,..., в, 11), схема (40) будет уменьшать количество вычислеиий от порядка )1'2 до порядка 13'108 10* или около того, где Ю = п11...
1п„— количество данных точек, К тому же даииая схема идеально подходит для параллельного вычисления. Важный особый случай одномерного преобразования Фурье обсуждается в уир. 14 и 53; одиомерный случай также приводится в разделе 4.3.3С. Рассмотрим более частный случай вычисления полинома. Иитзрполлциомимй полипом Лавраи0100 порядка и, которь|й мы запишем в вице (Х-Х1)(Х-Х2)...(Х-Хи) (Х-Х0)(Х-Х2)...(Х-Х„) и(„)( ) — 9 +91 (Хо-Х1)(Х0-Хз) ° ° (Хо-Хи) (Х1-Хо)(Х1 -Хз)...
(Х1-Хи) (х хе)(х х1) (х х 1) (4ц + '''+ри (Хи-Хз)(яи- )... (Хи-Хи 1) является только полииомом от х степени < и, который принимает соответствующие зиачеиия 90, 91, ..., 90 в и+ 1 различной точке х = хе, х1,..., х . (Из (41) очевидно, *1то и(и)(хз) = 90 для 0 < й < и. если 7(х) — любой такой полипом степени < и, то У(х) ии У(х) — и(и)(х) имеет степень < и и 9(х) Равно нУлю Дли х = хо,хм ..., хи; следовательно, 9(х) должен быть кратен полиному (х-хе)(х-х1)... (х-хи). Степень последнего полинома больше и, поэтому 9(х) = 0,) Если предположить, что значении функции табулироваиы и хорошо аппроксимируются полииомом, то формулу (41) можно использовать для "интерполирования" значений функции в точках х, ие занесенных в таблицу.
Лагранж предложил (41) своим учеиикам в Раг13 Есо1е 74огша)е в 1795 году [см. (Еиггев 7 (Рзпз, 1877), 386), однако Эдвард Уоринг (Ебивгб Жаг1пй) из Кембриджского университета к тому времени уже представил такую же формулу, совершенно точно и ясно сформулированную в Рл13озорл1са! згелвасг1опв 69 (1779), 59-67. На первый взгляд кажется, что в формулах Уоринга и Лагранжа совсем немного сложений, вычитаний, умножений и делений; иа самом деле — точио и сложений, 2нз + 2п вычитаний, 2пз+ и — 1 умножений и и+ 1 делений, Но, к счастью (как мы подозревали), возможно улучшение. Основная идея упрощения (41) учитывает тот факт, что и1„)(х) — и(„й(х) = 0 для х хе~ ° ..
~х»-1~ таким образом~ и1»)(х) и1» 1)(х) полинам степени и нли меньше, кратный (х — хе)... (х — х„,). Можно сделать вывод, что Уй( ) = .( — )" (х - - )+ (.-И( ). гле а„— константа Это приводит к интерполлционной 1/юрмуле Ньютона иуй(х) = а„(х — хе)(х — х1)... (х — х„1) + + аз(х — хо)(х — х1) + а1(х — хе) + ао. (42) и(»)(х) = ((... (а„(х — х 1) + а„1)(х — х„р) + ° )(х-хе) + ае). (43) Это потребует и умножений и 2п сложений. Иначе можно вычислить каждый отдельный член (42) справа налево; выполнив 2п — 1 умножений и 2п сложений, мы вычислим все значения и(о) (х), и(,) (х), ..., и(„) (х), что во всяком случае покажет, будет ли сходиться интерполяционный процесс.
Коэффициенты аз в формуле Ньютона можно найти, вычисляя отношения разностео по следующей таблице (показано для и = 3). уо (у1 — уо)/(х1 — хо) = У1 (Уз -У1)/(хз - 1) = Уз (уз-уз)/(хз-хз) = уз У,-у1)/(хз-хо) = уз' (уз уз)/(хз х1) уз У1 (уз - у~з')/(хз - хе) = уз" МожЗЮ доКазать, что ао — — Уо, а1 = У'„аз = Уз и т, д., н показать, что отношеНИя Раз- ностей имеют тесную связь с производными интерполируемой функцки (см. упр. 15).
Значит, следующие вычисления (соответствующие (44)) можно яспользовать, чтобы получить аз. На 1ап с (ае, а1,..., а») +- (уо, у1, ° - °, у») 1 затем для й = 1, 2,...,п (в таком порядке) присвоить а,<- (а1-ау 1)/(х -х. з) для 1 = п,п — 1,...,/з (в таком порядке). Для этого процесса требуется 11(из + и) делений и аз + и вычитаний, и экономится около трех четвертей работы по сравнению с (41).
где аз — коэффициенты, которые необходимо определить по заданным числам хо, х1,, х», ую ум у„. Заметим, что зта формула имеет место для всех и; коэффициент аз не зависит от хе+1,..., х„или от уз+1,..., у„. Когда аз известны, интерполяционнвя формула Ньютона удобна для вычисления, так как можно снова обобщить правило Горнера н записать Например, необходимо вычислить 1.5! по значениям О(, 1!, 2'.
и 3(, используя кубический полипом. Отношения разностей равны У У У У 1 О э 3 э 4 6 Таким образом, и(е)(х) = ищ(х) = 1, п(з)(х) = фх(х-1)+1, и(з)(х? = зх(х-1)(х 2)+ ~1х(х-1)+1. Подставляя х = 1.5 в и(з)(х), получаем —.125+.375+1 = 1.25; требуемое 'правильное" значение равно Г(2.5) = 7э,/я 1.33.
(Но существует, конечно, много других последовательностей, которые начинаются с чисел 1, 1, 2 и 6.) Чтобы интерполировать несколько полнномов, имеющих те же точки интерполирования хе, х~, ... „х„, но разные значения уо, ум ..., у„, желательно переписать (41) в виде, предложенном В. Дж. Тейлором (%'. 3. Тау1ог) (,Х. Везеагсй Май Внг.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
