IX Власова Е.А. Ряды (1081388), страница 40
Текст из файла (страница 40)
Дискретное преоорллование Фурье 327 соответствие сеточную функцию у Е В„ч, для которой координаты вектора с являются дискретными коэффициентами Фурье функции у'. Отображение У' 1 называют обратпным дискретпным преобразованием Фурье. Оно определяется формулами (3.59), которые эквивалентны следующему матричному равенству: у" = Р 1с. Матрицу Р 1 называгот матприцеб обратного дискретпного преобразования Фурье. Из формул (3.59) следует, что матрица обратного дискретного преобразования имеет вид 1 1 Р 1 Я -1 Ч -2 1 1) -2 9 -4 1 Я -(Ж-1) д 21~ 1) (3.64) 9 -1Д1-1) е -(1у-1) -г(лт- 1) Ч Ч 'Под арифметической операцией понимается умножение двух комплексных чисел с последующим сложением.
Обратимся теперь к вычислительным аспектам осуществления прямого и обратного дискретных преобразований Фурье. Выполняя прямое или обратное преобразование Фурье, нам приходится умножать квадратную матрицу Р или Р 1 порядка й)' на столбец из Ж чисел. При этом для определения всех дискретных коэффициентов Фурье сеточной функции у иэ унитарного пространства 1)1т требуется порядка )ч'г арифметических операций' (матрицы Р и Р 1 считаются вычисленными заранее).
Однако если )т' является составным числом, то количество выполняемых арифметических операций можно значительно сократить. Существует алгоритм вычисления дискретных коэффициентов Фурье сеточных функций, называемый быстпрым дискретным преобразованием Фурье, который позволяет уменьшить число производимых арифметических операций до порядка дт(Ф1 +)тг+ ... + )11 ), где дт = = Ф1 )ч'г...
111щ — разложение числа )т' на простые сомножители. 328 3. РЯДЫ ФУРЬЕ Рассмотрим идею быстрого преобразования Фурье на примере вычисления прямого преобразования Фурье функции 7 из унитарного пространства Во7 в случае, когда 117 = Д71Д72. Перепишем формулы (3.62) для вычисления дискретных коэффициентов Фурье в следующем виде: О1-1 с1 = — ~~> 1(х )д1, 7171~г . г=о 1= 0, М-1, 17 1(71Д72+70) = 171Д72+170 = (11Д71+ 10)71Д72+170 = = 11711'711'72+ 1071 г72+ 170 = 11ЭЛ+ 1071 1172+ 170~ и, следовательно, 11 11ЯЖ 1031№ 110 1031№ 1м Отсюда для любого 1 = О, М вЂ” 1 получаем № — 1№ — 1 д71 юг у,=о у,=о №-1х 1 №-1 № = — ~~, ~ —,~, У(хй№+1.) ч"" ')д1м = — ~1, с(10,7ОИ17', ,~о=о Я=О го=о где д = е г"'7~ Обратим внимание на то, что д ~ = 1 для всех 7П Е Ж. Отметим, что любой номер 1 = О, Ж вЂ” 1 можно представить в виде 1= 11 М1+10, где 11 < Мг и 1о < 1111 — неотрицательные целые числа.
Также любой номер 7' = О, М вЂ” 1 можно представить в виде 7' =,7'1 Мг + 70, где 71 < Д71 и 70 < Д12 — нЕотрицатольные целые числа. С учетом этих представлений для любых 1, 7' = О, Д7-1, имеем 329 ЗЛ2. Дискретное преоорввоввние Фурье где введено обозначение: №-1 с(1о уо) = ~~) У(ху №+1 )д~~~№, уз =О, 1112 — 1, 1с =О, 11'1 — 1. Ф1 и=в При известной матрице Г дискретного преобразования Фурье, т.е. при известных значениях д'о~'№/Ф1, для вычисления каждого коэффициента с(1е, 1с) требуется М1 арифметических операций. Общее число таких коэффициентов 1т'"11вэ = 1"в'. Таким образом, для вычисления всех коэффициентов с((е,ус) необходимо порядка М11в' арифметических операций. Далее, при известных коэффициентах с(1о, 1а), 1а = О, Фг — 1, и величинах дбо/Мэ для вычисления каждого коэффициента с1 требуется осуществить порядка 1в2 операций.
Всего таких коэффициентов М, значит, следует добавить еще 1вэМ операций. Следовательно, для вычисления всех коэффициентов дискретного преобразования Фурье необходимо ММ2+ 1в'11т' операций. Так как М(М1 + Мэ) (1в'2 при 19' ) 4, то получаем более выгодный способ вычисления дискретного преобразования Фурье. Экономия в количестве вычислений стала возможной благодаря выделению коэффициентов с(1о,уе), котоРые использУютсЯ Дла вычисления нескольких различных коэффициентов с1. В общем случае, когда Ж = Ф11в2...Фо„удается аналогичным образом выполнить дискретное преобразование Фурье всего за Ф(1в1 + Фэ+... + Ж,„) операций. Более подробно остановимся на случае, когда Ж является степенью числа 2, т.е.
И=2~, тих% Разложим числа 1 = О, 1в'-1 и 1' = О, Ф-1 по степеням числа 2, т.е. представим их в виде т — 1 2 — у кЗт2 т=а т-1 1= 2 1ь2ь, к=а (3.65) где все коэффициенты 1ь и 2, принимают одно из двух значений: О или 1. Для произвольной сеточной функции у Е Р11 положим 33О 3. РЯДЫ ФУРЬЕ 1 М-1 с1 = — ~~» У(х )611 = д(, 1=О 1 1 1 = —,.Е Е У ,=О3 ,=О у(~»ЦО,...1ут 1))6~1.
(3.66) 1,=О Заметим, что д = е ~"11~ Поэтому для любого целого р верно равенство да»а = 1. Рассмотрим теперь произведение целых чисел (у. С учетом представления (3,65) имеем ц= (й ат')(1 т',2') = 1 1 йт',2' т-1т-т — 1 т-1 т-1 »йут2~~" + ~~» ~ »йут2~~" = » — — О т-1т-т-1 т-1 т-1 1й3т2й+т+ 2т '~» ~~» (й)т2й-(т-т) г=а й=та-г 1=0 т-1 т-т — 1 т — 1 ут2т ~~» 1й2" +2тв= ~ ~'„2тат+1»»в, т=а г=а где т-1 т-1 та-т-1 вт ~~» ~~», 1йу,2" ( ат =а(»О,...,1т т 1) = Р 1й2, й г=а й=та-т Учитывал, что д~' = (д1»»)' = 1, получаем т-1 та-1 11 Ц 1 Ота„на П батата„ =О Я(1О,...,ут 1) = у(х ), где у' имеет разложение (3.65).
Коэф- фициент Фурье с1 с произвольным номером 1 равен 3.12. Дискретное преобразоеаиие Фурье Тогда, используя (3.66), имеем та-1 =яЕп*у)~'= —,. Е Е~(") П~""= 3=о 3п>->=О го=0 >'=0 1 1 п>-1 =ГЕ Е И*3) П~""= уо 0 гп ->=О т=о 1 1 >7" — ~ 13' ' 'У~ )(30 " 3 — 1) (3 67) го=о 3>ь — > =0 Если ввести следующие обозначения: с (30>31»" ° 3та-1) =~ (30>" ° >Зтп-1) =1(Я3)> 1 С (10>30»3п>-2) = 7 О> С (30>31»".3п>-1)> 11) ° ° % ' '„, >2 >ат)о) 10) 3, >=О 1 с (то>11 30 ",3 -з)= — ~~ чт ' с (1о уо>" уп> — 2)> <г) 1 т,г -'а11о,)>) 11) 2 ~-' гтп а=о 1 2~ то процесс вычисления дискретных коэффициентов Фурье с1 по формуле (3.67) сведется к быстрому алгоритму вычислений с использованием следующих рекуррентных формул: с (10»... 10 м3о»...
3 ь 1) = 1 Е т)>: с(~ Ц (>О >ь-2 30 3 -)т) (3 68) 2, „=о где т=1>-1 -г> /ж > тс = 1, т. 332 3. РЯДЫ ФУРЬЕ Начальными значениями (й = 0) для этих формул являются значения функции 7" Е Р77 В уалах СЕтхи я1 — — УТ(Х, 7' = О, Д7 — 1: с О0,.71~",.7т-1) = 1(х1), 7' = р .7;2", (0) О=О а конечными значениями (й = га) — искомые дискретные коэф- фициенты Фурье функции у: с(~) (1ш1~,...,1 1) = с1, 1 = ~~~ 1~2" 7с=О (10~ !1ь — 1~.70~ ° ).7йй-Й-1) = (ь) 1 9 ~ ~ С (10, ° ° ° ~1ь-з~,70~ ~2т-й)~ (3.69) ь'„а =0 где Ь-1 а„, я =а(10 11 ",1ь-1) =~ 1,2", д=е ~у, Й=1,171.
т=О Определим количество арифметических операций, необходимых для вычисления дискретных коэффициентов Фурье с использованием описанного алгоритма. На каждом й-м шаге для вычисления одного коэффициента с (10, ",1ь-1,,70," .7' -ь-1) (ь) при известных коэффициентах с(~ 1) требуется выполнить две арифметические операции (как и выше, считаем, что значения 91 -"з О -172 известны заранее). Таких коэффициентов насчитывается 2'". Поэтому на й-м шаге совершается 2 2 арифметических операций, а всего эа 7п шагов нужно выпал- нить 2'" 27а = 2Д(1060 % операций.
Рассуждая аналогично, приходим к рекуррентным формулам быстрого алгоритма обратного преобразования Фурье: 3.12. Дискретное иреооразоваиие Фурье Начальными значениями (Й = 0) для этих формул являются значения дискретных коэффициентов Фурье сеточной функции 1" Е Ри'. с=т — 1 с (уе,,)'1,...,у 1) = с;, )' = ~у у„2, (О) . — Х ~ с а конечными значениями (Й = т) — значения функции У Е Рм в узлах сетки х~ =1Т(М, 1 = О, Д( — 1: с(~)(1е,11,".,1, 1) = у(х~), 1= у 1ь2" Итак, вместо необходимьпс )т'2 операций при использовании обычного алгоритма преобразования Фурье, приведенный алгоритм быстрого (прямого и обратного) преобразования Фурье тРебУет выполнениЯ всего поРЯдка 2Д(1обзМ аРифметических операций, давая тем самым не только существенный выигрьпп в затратах машинного времени (при реализации этого метода на компьютере), но и увеличивая надежность вычислений.
Отметим, что процедура последовательного вычисления величин с(~)(11,...,1а 1,уе,...,ун, я 1) по рекуррентным формулам (3.68) эквивалентна процедуре последовательного вычисления 2'"-мерных комплексных векторов с(") 0,0,0,..., ( 0) с(")(1,0,0,...,0) с(")(О, 1, О,..., 0) )с = О, п1, с(")(О, 1, 1,..., 1) с(~)(1, 1, 1,..., 1) с помощью линейных отображений с(1) Р с(е) с00 ть с(1) с(™в) Р с(н~-1) 334 3. РЯДЫ ФУРЬЕ Таким образом, матрицу г (прямого или обратного) дискретного преобразования Фурье (см.
(3.63)) можно представить в виде произведения гп квадратных матриц порядка 2~Я: гпь~тл-1 ° ~2~1. Матрицы г"1, г"я, ..., г' замечательны тем, что каждая из них имеет лишь по два ненулевых элемента в каждой строке (и каждом столбце). За счет отбрасывания (не выполнения) операций умножения на нули этих матриц и достигается выигрьпп в необходимом числе операций при выполнении дискретного преобразования Фурье по быстрому алгоритму. Можно показать, что элементы каждой матрицы Р;, = (( ~ ), (и) о=1,т,имеютследующийвид. ПустьО<я<2 ",О<о<2" 1, параметр н имеет значение 0 при вычислении прямого дискретного преобразования Фурье, и значение 1 при вычислении обратного дискретного преобразования Фурье. Тогда: ~ " = 1 при у = й2" + е+ 1, 1= й2" '+ о+ 1 или у = й2" + + 2н-1+ е+ 1 1 й2~-1+ е+ 1.
~(")=д( О "з при1=й2" +о+1 1=2 1+Ь2" 1+с+1 ,у,[ 7 у(",1 = — д( О "з при у = я2" + 2" ' + е + 1, 1 = 2 1+ Ь1 + Ь 2 Я 1 ( е + у"~ ~ = 0 в остальных случаях. Численную реализацию прямого и обратного дискретных преобразований Фурье можно проводить в соответствии со следующим алгоритмом. Алгоритм быстрого прямого (обратного) дискретного преобразования Фурье 1. Входные данные: М = 2 — количество узлов; А(Ф), В(д() — Ж-мерные массивы действительных и мнимых частей комплексного М-мерного вектора Х(Ж).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
