Бабенко - Основы численного анализа (947491), страница 11
Текст из файла (страница 11)
Поэтому введем еще операцию разбавления, состоящую в том, что вектор а е С" будет отождоствляты:я с вектором й е С ": а = — (ав, ..., ап...1, О...., О)'. Приняв это определение, мы получим, что с = й * Ь. Введем операцию поколепонентного умножения векторов: а ЕО Ь =.- (поЬо,, ип 1Ьп. 1)'. (Не следует операцию !и путать с операцией З умножением чисел в ег.) Теорема 4 (о свертке). Ь"с = (Га) " (Л~). Доказатйльство. Пусть Гс .= (Д, ..., у и 1)', имеем цепочку очевидных соотношений 2л — 1 2л — 1 2л — 1 ыз' ~ а!Ьь 1= 1=О о=в 2п — 1 2п — 1 2п — 1 2п — 1 ~ "Ь,,— 1=О п — ! а!ыз 1=а ~ ~' а!ыз' ~~ ' 11" ОЬь 1=о 2п — 1 п — 1 ~, 3!1 ОЬ 1.—:О ! = ~ а!озз! ~ Ьь 1::о 1=о л22 — 1 п22- 1 зз = ~~ агн(щ ) з -'ыз ~~ агье1(!о ) ', 1' = О, 1....,. и,— 1.
(2о) 1=о 1..О Поскольку озг = ехр(2хет/(и,!2)), то мы представили преобразование Фурье последовательности (аь) через преобразования Фурье последовательностей (а 21 ), (агом 1) половинной длины. Преобразование Фурье каждой из этих последовательностей является функцией на Х"!~,и тем самым сразу видна выгода такого представления. С каждой из полученных сумм правой части равенства (25) поступим аналогично: проделаем такое прообразоваиио г раз. Читая полученные формулы в обратном порядке, получим следующие соотношения.
Пусть двоичное представление индексов й !' имеет вид! = (1г 1...1о)2, ! = (зв...1г 1)2, гче 11, зь = О, 1. (напомним, что ы первообразпый корень степени 2н). Посмотрим. как можно более экономно вычислить преобразование Фурье вектора и. Если это делать по формуле (19), то потребуется =- пг арифметических операций при условии, что будут предварительно вычислены величины ш, ..., ззп 1. Если 0 = 2", го можно существенным образом уменьшить шоно арифметических операций.
Занишеа! форе!улу (19) в следую!цем виде: 45 З 4. Примеры аагоригамоо; аиа иэ авгоригамоо Положим ас = Ао))(„м ..., 10) и введем величины Ас)Зг — л 1).— 2,,1о =-Ао)0, 1е — 2, ..., 10.'+0)0" ' '" ~'Ао)1, 1, 2, ..., 1о), (26) Аа)3,. М ° ) 3е- а, 1е — а- л 10) =- Аа-2)3'-и ) 3,-а:л, 0: 1:-а-и ", 1о,'' '- — — гАа л)3' л) "-,.3, „г,1, 1„.,) ..., 1,), 1(в<с. О' — . г' — )О-0)г С другой стороны, при в — -- г получим соотношение (27) А„)3„-г) . " ° 3о. = Хгч которое следуегг из более обшей с(гормулы А )3 — г,:3 —,1е — -и, 1о) = с)Π—.. "2 -г1гСС вЂ” !..Л,—,0„,0)го (28) — Е ) легко доказываемой по индукции.
Очевидно, что зто соотношение выполняется при в = 1; допустим его справедливость на в — 1-лс шаге. Тогда на в-м шаге получим Аа).3„„..., 3е „1е „,, „,, 10)— ис+ )О' — — '! ' 'о — ! )г 0 — 1 ° л — а)0 . ° 0)г Е С. „...,С.,).)=ОД Ог)г — -!.-г — )1гц — !. Л; —,-)0..0)г, Сг,—, и. )О ..02г аи 6 „...,С.
)а,=о,л (29) причем во второй сумме 1 = (1,. с...1,, ! 11„а !...1о)2, а в первой сумме единицу нужно заменить нулем. Заметим, чго выполняется соотношение (3а — а-~-1 3е — Л)2(1е — ! ° ° 1г — а 10... 0)2 = = и — 3 — 2)2(1 — ю ..1,-,тсО ... 0)2 (спос1 2), и как следствие (3е — аг-1 ° ° 3е — 1)2(1е — С ° ° 1е — а — ЛО...О)2 0г — а ° 3е — !0...0) (3е — а 3е — 2)2(1~ — л 1,—,<-20... 0)2 (плос1 2). Тем самым правая часть (29) совпадает с правой частью (28). Для каждого в козффициент Аа)3).— с . °,3 — а) 1.— а — !) .... 1о) имеет и значений, Глава 1. Постановка задач численного анализа так как величины дзп (ь принимают значения О, 1.
Поэтому для подсчета Ла по формуле (26) требуется п сложений и и умножений, а чтобы определить Л, нужно пг сложений и пг умножений, т. е. 2п 1ояз и арифметических операций. Изложенный способ называется бмшпрым преобразованием Фурье (БПФ). Возможно, что величина 2п1обяп являотся нижней границей числа арифметических операций, требуемых для вычисления преобразования Фурье любого вектора а.
Алгоритм БПФ сначала был описан в 1924 г. К, Рунге и Д. Кенигом [143[, а затем переоткрыт Дж. Кгши и Дж. Тычки в 1966 г. [132[. Он имеет огромное значение при решении некоторых прикладных задач, в частности при решении задачи расшифровки фотоинформации, получаемой с искусственных спутников. гМы релобрали вопрос о вычислении дискретного преобразования Фурье в случае п †-- 2". А что будет в случае, осли и простое число? Этот вопрос будет рассмотрен ниже. 3 а д а ч и. Можно определять кратное дискретное преобразование Фурье.
Пусть 1, ), и хгультиивдексы: 1 = (!г, .... !г), ) = Ог, ...., У ), и = (ггг,, п,), и — 1 = (ггг — 1, ..., гг, — 1). Положим агг-' = юг'г' ... го,-*г', гдг ыь =- охр(йяг)пь) (й — -- 1, 2...., о). Преобразование Фурье опреде шм формулой Л = ~ ои ~, 3 '— ' (21...., у,), О < гь < пь, й — —. 1, 2,..., и. '1 г=о 7. Выведите формулу обратного преобразования Фурье и формулу, аналогичную форлгуле (23), 8. Считая, что пь = 2" (Л = 1, 2,, о), получите аналог соотношений (26), (27) и на их основании онигиите метод БПФ и многомерном случае. 9. Считая, что па = 2"" (й = 1, 2, ..., о), покажите, что для того, чтобы вычислить кратное дискретное преобразование Фурье, достаточно выполнить йпг... пг х!ой (пг...
и,) арифметических операций, Подробнее о кратном БПФ см. (11. 164 — 156[ 8. Алгоритмы арифметики многочленов. Алгоритм БПФ позволяет построить экономные алгоритмы арифметики многочленов от одной переменной. Задача сложения многочленов абсолютно ясна, имеет векторный характер и легко поддается распараллеливанию.
Поэтому мы прежде всего обсудим алгоритмы умножения и деления многочленов. Пусть р(х), !)(х) — многочлены степеней не больше и — 1: п — 1 и — 1 11(х) = ~г агх, г?(х) = ~ ~Ььх~. Будем считать, что ггь = (гь = О, если й < О или й аз и. Из коэффициентов многочленов р(х). 11(х) образуем векторы а = (ао, ..., аа 1)', Ь 4, Примерл1 алгоритмов; анализ алгоритмов Ь = (Ьо, ..., Ь„л)'. Их свертка с = а а Ь определяет коэффициенты мно- гочлена 1(х) = р(х) о(х).
В салгом деле, переллножая многочлены р(х) и о(х), получим га — 1 га — 2 Л Р(х)Я(х) = ~ т ~ ~ЩЬл 1 = ~ сьх . 11апомним, что по определениго с2„1 = О. Для вычисления вектора с с помощью формулы (24) потребуется = п2 арифметических операций. Однако на основании теоремы о свертке существует более экономный способ вычисленлы коэффициентов много- члена Е(х).
р(т) =. о(х) з(х) + г(х Ь где г(х) многочлен степени не больпге и —. 2. Рассматривая последнее соотношение в окрестности точки х = оо, его можно записать в виде р(х) о(х) — г(х) '1 ~ 1лх В кольце формальных рядов Лорана 1 2 пухл введем обозначение целой части по аналогии с кольцом вещественных чисел: ! П1,т ~= 2 плх . л= — ж л=о Теорема 5. Произведение двух лгногочленов степеней не болыие и — 1 можно вычислить, исиользул не более 24п1оязп+ б2п операций слоз1сенил и умножения и 4п — 1 операций сдвига порядка на (1оаа и', + 1 единиц.
Доклзлтвльозво. Пусть 2' ' < и < 2" = т; степени многочле; нов р(х) и у(х) будем считать равными т — 1. Тогда по теореме о свертке с = Г 1((Ха)1и(ГЬ)). Воспользуемся алгоритмом БПФ для подсчета преобразований Фурье. Для этого нам потребуется 3(4т 1оя22и) операций сложения и умножения; дзя вы шсления покомпонентного произведения векторов потребуется 2т. умножений, а для вычисления обратного преобразования Фурье необхолплю йт делений на 2т = 2'тл, т. е. 2т операций сдвига порядка на г —, 1 = (1ояз и) + 1 единиц.
Замечая, что т < 2п, получим оценку, указанную в формулировке теоремы. П Рассмотренный спогюб вычисления произведегшя двух многочленов будем называть быстрым умножением многочленов, Быстрое умножение позволяет организовать алгоритм быстрого деления многочленов. Для двух многочленов р(х) и о(х) соответственно степеней т — 1 и и — 1 рассмотрилл процедуру деления с остатком; Глава 1. Постановка задач численного ассализа Тогда з(х) = ''.р(х)с1(.
)). Чтобы определить з(х), нужно найти разложение 1Сс1(х) по степеням х и — з Если й(х) = 2 Ььх", то наложим од = Ь„с з(Ь, г (з' = 1, 2....., и — 1) ыо и с1(х) = 1 -'. осх ~ +... + аа дх "'~; тогда 1/с1(х) —. Ь„х "+'Я(х). Построим последовательность (Уа(х)) многочлеиов сгг х по следующим формулам: Ус(х) = 1 — осх ~) Уьчч(х) = 21ь(х) — 4[х)У~~(х), 1с = 1, 2,... (30) Заметим, что 1 — ссУь с = (1 — с1Уь)з, и если с1Уа = 0(х '), то 1 — ссУЬ = 0(х ~"). В силу выбора начальных данных 1 — оУа = 0(х а") (й =- = 2, 3,...). Мы несколько модифицируем последовательность 1ь(х).
Если оо(х) = СЮ и — 1 — Зьх ", то положим (у)„.— — 2 Дх ь. Построим послеловательа=о а=о ность (Яа(х)) с помощью соотношений Ус(х) = Ус(х), Хь с(х) = 2Яь(х) — ((сс(сг))з - Хь(х))з,, й = 2, 3,... (31) Покажем, что ха = Уь+0(х з ) ()с .=- 2, 3,...). Доказательство проведем по индукции. Предположим, что это соотношение выполняется на Ь-м шаге. Положим ха =. Уь + И'ь, И'~ — — 0(х з ). Из соотношения (30) получаем вот' откуда Яь г .— — Уа с + 0(х - ). Чтобы найти в(х) и г(х), нам нужно сделать и шагов, где и определяется из неравенств 2' "' < ги — и д 1 < 2 . т -п Найдя Я (х) = 2, йьх а, образуем миогочлеи хт " 2, йьх ь = и(х). а=о а=о Тогда с1 Ь„ ,ха-гсс Ь„ ,х"-' ' ' Ь„ сх 2 г„о, = г,— дга =2Уь - ЬУЯ = 2Уь — Д вЂ”. 2Уь — с1'У,а —,0(х ~ )= -'2Игь --2ссУьИ'и —.
1И'~в -С- 0(х ~ ) =- —, 2И'а(1 — с1Уь) ч- 0(х ~ ) = 0( — хм') '«4, Пример»«лгоритпмов; аналит алгоритпмов и, спедоватечьно, в(х) = ~ ~. г(х) = р(х) — 0(х) в(х). Подсчитаем число операций, необходимых для вычисления в(х) и г(х) . Вычисление по формуле (30) требует 48 2в «(й+1)+0(2") операций, а всего двя вычисления У потребуется 2 (48 2" к + 0(2ь)) =. 48(и— й<» — 1)2» "«+0(2 ) операций сложения и умножения. Вычисление г(х) и г(х) требует 24т!ойз т+ 24п1ойг и+ 0(т, + и) операций, и, таким образом, потребуется 0(т !ойг т) арифметических операций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
