Файл: В. П. Кандидов и др. Москва физический факультет мгу.pdf

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. Ломоносова имени М.В. Ломоносова имени М.В. Ломоносова имени М.В. Ломоносова
Физический факультет
Физический факультет
Физический факультет
Физический факультет
В.П. Кандидов, С.С. Чесноков, С.А. Шленов
В.П. Кандидов, С.С. Чесноков, С.А. Шленов
В.П. Кандидов, С.С. Чесноков, С.А. Шленов
В.П. Кандидов, С.С. Чесноков, С.А. Шленов
ДИСКРЕТНОЕ
ПРЕОБРАЗОВАНИЕ
ФУРЬЕ
Москва 2019
Москва 2019
Москва 2019
Москва 2019

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М.В. Ломоносова
Физический факультет
В.П. Кандидов, С.С. Чесноков, С.А. Шленов
ДИСКРЕТНОЕ
ПРЕОБРАЗОВАНИЕ
ФУРЬЕ
Учебно-методическое пособие
Москва 2019

УДК 519.6
ББК 22.19
К19
Кандидов В.П., Чесноков С.С., Шленов С.А.
К19
Дискретное
преобразование Фурье. Учебное пособие
/В.П. Кандидов и др. – Москва: физический факультет МГУ,
2019. – 88 с, : ил.
ISBN 978-5-8279-0179-2
Рецензенты: дф-мн профессор В.А.Трофимов, дф-мн доцент В.А.Хохлова
Печатается по рекомендации Ученого Совета физического факультета МГУ имени М.В.Ломоносова
В пособии систематически изложены теоретические основы и сформулированы рекомендации по практическому применению преобразования Фурье в численных исследованиях. Рассмотрены особенности преобразования Фурье для функции дискретного аргумента, задаваемой числовым массивом конечной размерности. Приведена теорема
Котельникова–Шеннона и ее связь с дискретным преобразованием Фурье. Значительное внимание уделено вопросам ширины спектральной полосы и спектрального разрешения образа
Фурье сеточной функции. Кратко представлены алгоритм быстрого преобразования
Фурье и библиотеки стандартных программ преобразования Фурье, используемые в численных исследованиях.
Рассмотрены возможные артефакты при дискретном преобразовании
Фурье и даны практические рекомендации по его использованию.
Изложенный материал проиллюстрирован конкретными примерами.
Пособие может быть полезным при изучении курсов по численным методам, радиофизике, оптике и спецкурсам на физическом факультете и других естественных факультетах МГУ, а также в классических и технических университетах страны.
Ключевые
слова: вычислительный эксперимент, дискретное преобразование Фурье, теорема Котельникова-Шеннона, частота
Найквиста, быстрое преобразование Фурье.
УДК 519.6
ББК 22.19
ISBN 978-5-8279-0179-2
© Физический факультет МГУ
© В.П. Кандидов, С.С. Чесноков, С.А. Шленов

Глава__2._Функция_дискретного_аргумента'>Глава__1._Преобразование_Фурье_и_его_свойства'>Оглавление
3
Оглавление
Предисловие
4
Введение
5
Глава
1. Преобразование Фурье и его свойства
8
§1.1. Ряд Фурье
8
§1.2. Интеграл Фурье
12
§1.3. Свойства преобразования Фурье
13
Глава
2. Функция дискретного аргумента
20
§2.1. Дискретность и конечность области определения сеточной функции
20
§2.2. Спектр функции дискретного аргумента
21
§2.3. Теорема Котельникова – Шеннона
27
§2.4. Осцилляции Гиббса
31
§2.5. Взаимосвязь функции и спектра при дискретизации аргумента
35
§2.6 Вычисление производных с использованием спектров
38
Глава
3. Дискретное преобразование Фурье (ДПФ)
44
§3.1. Анализ Фурье. Ортогональность гармоник в дискретном пространстве. Синтез Фурье
44
§3.2. Свойства ДПФ. Формулы запаздывания, смещения и свертки
47
§3.3. Двумерное преобразование Фурье
48
Глава
4. Практика дискретного преобразования Фурье
50 50 53 58
§4.1. Выбор шага дискретизации на сетке
∆
x
§4.2. Выбор области периодизации функции L
§4.3. Частотное разрешение
∆
f
§4.4. Заключительная иллюстрация влияния шага дискретизации и периода функции на спектр при ДПФ
61
Глава
5. Быстрое преобразование Фурье (БПФ)
63 63 66 67
§5.1. Алгоритм БПФ
§5.2. Оценка эффективности
§5.3. Двоичная инверсия
§5.4. Простой пример. Графическая схема БПФ
68
Глава
6. Компьютерные библиотеки ДПФ
71
§6.1. Свободно распространяемая библиотека FFTW
71
§6.2. ДПФ в пакете Wolfram Mathematica
81
§6.3. ДПФ на языке Python
82
Литература
87

Предисловие
4
Предисловие
Учебное пособие
“Дискретное преобразование
Фурье” знакомит студентов и аспирантов с аппаратом и физическими представлениями преобразования Фурье в численном исследовании. В нем кратко изложены теоретические основы и даны рекомендаций по практическому применению прямого и обратного преобразования
Фурье для функции дискретного аргумента, задаваемой числовым массивом конечной размерности. На основе формализма построения функции дискретного аргумента на однородной сетке рассмотрены особенности образа и оригинала Фурье, связанные с их периодизацией, ограничением спектральной полосы частотой Найквиста, эффектом наложения частот, вычислением производных.
С позиций вычислительного эксперимента изложена теорема Котельникова -
Шеннона и ее связь с дискретным преобразованием Фурье в задаче восстановления непрерывных функций по дискретным отсчетам.
Значительное внимание уделено вопросам ширины спектральной полосы и спектрального разрешения образа Фурье для сеточной функции. Кратко рассмотрены алгоритм Быстрого преобразования
Фурье и его эффективность. В конце пособия представлены библиотеки стандартных программ преобразования
Фурье и некоторые рекомендации по их использованию.
В пособии наглядно представлена структура числовых массивов и возможные артефакты при дискретном преобразовании
Фурье, даны практические рекомендации по его использованию для анализа реальных функциональных зависимостей.
Изложенный материал наглядно иллюстрирован конкретными примерами.
Пособие подготовлено на основе многолетнего опыта преподавания общего курса «Численные методы в физике» на радиофизическом отделении физического факультета Московского государственного университета имени М.В.Ломоносова.
Учебное пособие “Дискретное преобразование Фурье” может быть полезным при изучении общих курсов по численным методам, радиофизике, оптике и спецкурсам на физическом факультете и других естественных факультетах МГУ, а также в классических и технических университетах страны.
В.П. Кандидов, С.С. Чесноков, С.А. Шленов
Москва, 2019 г.

Введение
5
Введение
В численных исследованиях дискретное преобразование Фурье является эффективным методом, с помощью которого осуществляется взаимно однозначное соответствие сеточной функции и ее образа в спектральном пространстве. Спектральная обработка результатов вычислительного и физического эксперимента с помощью преобразования Фурье существенно расширяет возможности анализа в научных исследованиях. В методах расщепления решения многомерных задач математической физики дискретное преобразование Фурье стало мощным средством построения экономичных вычислительных схем.
Возможность прямого и обратного перехода от сеточной функции к ее спектру позволяет решать в спектральном пространстве отдельные компоненты расщепленной задачи, что значительно повышает эффективность числительной схемы. Дискретное преобразование Фурье является ключевой составляющей программного обеспечения в спектроскопии, томографии, в обработке сигналов и изображений.
Дискретное преобразование Фурье представляет собой численный алгоритм представления функций разложением в ряд по тригонометрическим функциям. Метод разложения функций в тригонометрический ряд принадлежит Жан–Бати́сту Жозе́фу Фурье́. В
1807 году его доклад в Парижской академии наук «О распространении тепла в твёрдом теле» с решением задачи теплопроводности разложением в тригонометрический ряд не получил одобрения, а уже в
1812 году Фурье был удостоен Большой премии академии за труд
«Аналитическая теория тепла», в котором его метод получил дальнейшее развитие. Переход в спектральное пространство гармоник
Фурье особенно эффективно при фундаментальных и прикладных исследованиях аналитическими и численными методами волновых процессов в оптике, акустике, электронике, радиофизике и других научных областях. Метод гармоник Фурье, получивший начало как математический аппарат для решения задачи теплопроводности, в настоящее время стал мощным средством спектрального анализа в физических исследованиях.
С дискретным преобразованием Фурье тесно связана теорема отсчетов, впервые сформулированная в 1933 году В.А.Котельниковым в статье “О пропускной способности “эфира” и проволоки в электросвязи”. Независимо от него в 1949 году К. Шенноном также получена ее формулировка. Эта теорема, связанная с цифровой

Введение
6 обработкой сигнала, определяет оптимальный интервал дискретизации непрерывной функции, при котором по дискретным отсчетам полностью восстанавливается исходная функция. Теорема отсчетов имеет фундаментальное значение в области коммуникационных технологий и вместе с этим является средством обработки и представления результатов вычислительного эксперимента.
В настоящем пособии теорема отсчетов Котельникова–Шеннона включена как составная часть дискретного преобразования Фурье в численном исследовании.
Дискретное преобразование Фурье получило широкое распространение после разработки алгоритмов быстрого преобразования, позволивших значительно сократить вычислительные затраты особенно для массивов большой размерности. В настоящее время алгоритмы быстрого преобразования Фурье хорошо известны и широко используются в спектральном анализе. Хотя в современной литературе излагается ряд различных подходов к разработке алгоритмов
БПФ, в пособии представлен один из них, а именно, так называемый алгоритм Кули–Тьюки, впервые описанный в статье J. W. Cooley and
J. W. Tukey, "An algorithm for the machine calculation of complex Fourier series", Math. Comput. 19, 297–301 (1965). Алгоритм БПФ и его аппаратная реализация позволило в реальном времени осуществлять спектральную обработку больших массивов, что существенно повысило быстродействие в численном исследовании, криптографии, анализе сигналов и изображений.
В пособии основное внимание уделено анализу погрешностей, связанных с дискретизацией функций, полей при выполнении операций с массивами конечных размерностей.
Несмотря на то, что вычислительные мощности современных кластеров стремительно увеличиваются, исследователь сталкивается с проблемой аппроксимации полей и процессов на вычислительных сетках. исследования динамический полей с широким диапазоном масштабов проблема сеточной аппроксимации является особенно острой в многомерных нестационарных задачах нелинейной волновой оптики, нелинейной акустики, физики плазмы, нано оптики, распространения волн в случайно-неоднородных средах и других областях физики.
Пособие состоит из шести глав. В первой главе кратко изложены основные свойства и формализм преобразования Фурье, которые используются в последующем изложении. Во второй главе рассмотрены функция дискретного аргумента, особенности ее спектра и

Введение
7 эффект наложения частот. Введено понятие частоты Найквиста, получена формула для восстановление непрерывной функции в соответствии с теоремой Котельникова – Шеннона, дан анализ возникновения осцилляций Гиббса и приведена процедура вычисления спектров производных. В третьей главе построены формулы анализа и синтеза дискретного преобразования Фурье и приведены его свойства.
Значительное внимание уделено возникновению ошибок при наложении частот, подавлению осцилляций Гиббса, улучшению спектрального разрешения в дискретном образе Фурье. Кратко приведен аппарат дискретного преобразования Фурье двумерных функций в декартовой системе координат. Четвертая глава посвящена рекомендациям по практическому использованию дискретного преобразования Фурье, в частности, вопросам выбора шага сетки, периода регистрации и частотного разрешения. В пятой главе представлен алгоритм быстрого преобразования Фурье (БПФ) и дана оценка его эффективности.
Рассмотрен порядок последовательного представления элементов массива исходной сеточной функции и ее дискретного образа, а также приведен в качестве примера граф алгоритма БПФ. Шестая глава посвящена использованию свободно распространяемой библиотеки
FFTW, эффективно осуществляющей БПФ. Подробно описана ее установка на компьютер в среде GNU/Linux и проиллюстрирована ее работа на конкретных примерах для действительных и комплексных массивов. Далее изложено применение БПФ в пакете Wolfram
Mathematica. В конце главы рассмотрено использование для БПФ программ, написанных на языке Python, проведено сравнение их быстродействия.

Глава 1. Преобразование Фурье и его свойства
8
Глава
1. Преобразование Фурье и его свойства
§1.1. Ряд Фурье
Периодическую функцию
)
(
)
(
nL
x
u
x
u
±
=
(
L
,
2
,
1
=
n
), которая имеет конечное число разрывов на периоде и абсолютно интегрируема, т.е. удовлетворяет условию
∞
<

−
2
/
2
/
)
(
L
L
dx
x
u
, можно представить в виде суммы гармонических составляющих (ряда Фурье):

∞
=
π
+
π
+
=
1 0
)]
2
sin(
)
2
cos(
[
2 1
)
(
k
k
k
k
k
x
f
b
x
f
a
a
x
u
,
(1.1) где
k
L
f
k
1
=
– частота k-ой гармонической компоненты. Если функция
)
(x
u
зависит от времени, то частота
k
f
имеет размерность
1
с
Гц
−
=
, если она зависит от пространственной координаты, то
k
f
измеряется в
1
м
−
. Гармонические функции
)
2
cos(
x
f
k
π
и
)
2
sin(
x
f
k
π
, образующие базис разложения, ортогональны на периоде:












=
π
⋅
π



=
≠
=
π
⋅
π



=
≠
=
π
⋅
π



−
−
−
и всех при
0
)
2
sin(
)
2
cos(
,
при
2
/
,
при
0
)
2
sin(
)
2
sin(
,
при
2
/
,
при
0
)
2
cos(
)
2
cos(
2
/
2
/
2
/
2
/
2
/
2
/
m
k
dx
x
f
x
f
m
k
L
m
k
dx
x
f
x
f
m
k
L
m
k
dx
x
f
x
f
L
L
m
k
L
L
m
k
L
L
m
k
(1.2)
Используя свойство ортогональности базисных функций, нетрудно показать, что амплитуды косинус и синус компонент гармоник Фурье вычисляются по формулам:

Глава 1. Преобразование Фурье и его свойства
9
L
,
2
,
1
,
0
,
)
2
sin(
)
(
2
,
)
2
cos(
)
(
2 2
/
2
/
2
/
2
/
=
π
=
π
=


−
−
k
dx
x
f
x
u
L
b
dx
x
f
x
u
L
a
L
L
k
k
L
L
k
k
(1.3)
Наряду с (1.1) разложение периодической функции можно представить в виде:

∞
=
ϕ
−
π
+
=
1 0
)
2
cos(
2 1
)
(
k
k
k
k
x
f
C
a
x
u
,
(1.4) где
2 2
k
k
k
b
a
C
+
=
– амплитуда и
k
k
k
a
b
arctg
=
ϕ
– фаза гармоники на частоте
k
f
Поскольку гармонические функции
)
2
cos(
x
f
k
π
и
)
2
sin(
x
f
k
π
выражаются через экспоненты с мнимым аргументом следующим образом:
(
)
2
)
2
cos(
2 2
x
f
i
x
f
i
k
k
k
e
e
x
f
π
−
π
+
=
π
и
(
)
i
e
e
x
f
x
f
i
x
f
i
k
k
k
2
)
2
sin(
2 2
π
−
π
−
=
π
, из (1.1) следует комплексное представление ряда Фурье, которое более удобно в вычислениях:

∞
−∞
=
π
=
k
x
f
i
k
k
e
d
x
u
2
)
(
, где

−
π
−
=
2
/
2
/
2
)
(
1
L
L
x
f
i
k
dx
e
x
u
L
d
k
(1.5)
Отрицательные частоты при
0
<
k
в выражении (1.5) введены математически формально. Физически реально существуют гармоники
)
2
cos(
k
k
x
f
ϕ
−
π
и их компоненты
)
2
cos(
x
f
k
π
и
)
2
sin(
x
f
k
π
с положительными частотами
k
f , которые можно зарегистрировать экспериментально. Амплитуда
k
C и фаза
k
ϕ
гармоник, амплитуды косинус и синус их компонент
k
a и
k
b связаны с комплексными коэффициентами разложения
k
d простыми соотношениями:

Глава 1. Преобразование Фурье и его свойства
10
[ ]
[ ]
).
(
,
,
Re
Im arctg
,
2
k
k
k
k
k
k
k
k
k
k
k
d
d
i
b
d
d
a
d
d
d
C
−
−
−
=
+
=






=
ϕ
=
(1.6)
Множества
{
}
,...
3
,
2
,
1
,
,
=
ϕ
k
C
k
k
являются соответственно амплитудным и фазовым спектром функции
)
(x
u
Если функция
)
(x
u
вещественная, то амплитуды синус и косинус компонент
k
a и
k
b действительны и коэффициенты разложения разных знаков являются комплексно сопряженными числами:
∗
−
=
k
k
d
d
. В этом случае амплитуды компонент
k
a
и
k
b
равны:
[ ]
[ ]
k
k
k
k
d
b
d
a
Im
2
,
Re
2
−
=
=
(1.7)
Качественный вид косинус
k
a
и синус
k
b
компонент в спектре вещественной функции представлен на рис. 1.1:
Рис.1.1. Схематическое изображение комплексно сопряженных коэффициентов разложения
*
k
k
d
d
−
=
вещественной функции.
В случае симметричной функции
)
(
)
(
x
u
x
u
−
=
коэффициенты разложения
k
d
являются действительными (
0
]
Im[
2
=
−
=
k
k
d
b
) и, следовательно, фаза
0
=
ϕ
k
, что соответствует разложению по косинусоидальным гармоникам
)
2
cos(
x
f
k
π
Бесконечное множество амплитуд и фаз
{
}
L
,
3
,
2
,
1
,
,
=
ϕ
k
C
k
k
или коэффициентов разложения
{
}
+∞
−∞
=
,
,
0
,
,
,
L
L
k
d
k
является