Преобразование фурье

Автор: Пользователь скрыл имя, 18 Ноября 2011 в 10:48, реферат

Описание работы

Быстрое преобразование Фурье (БПФ, FFT) — это алгоритм быстрого вычисления дискретного преобразования Фурье (ДПФ). То есть, алгоритм вычисления за количество действий, меньшее чем O(N2), требуемых для прямого (по формуле) вычисления ДПФ. Иногда под БПФ понимается один из быстрых алгоритмов, называемый алгоритмом прореживания по частоте/времени или алгоритмом по основанию 2, имеющего сложность O(Nlog(N))

Работа содержит 1 файл

Преобразование Фурье.doc

— 320.00 Кб (Скачать)

Преобразование Фурье вычисляется всякий раз, когда мы слышим звук. Ухо автоматически выполняет вычисление, проделать которое наш сознательный ум способен лишь после нескольких лет обучения математике. Наш орган слуха строит преобразование, представляя звук — колебательное движение частиц упругой среды, распространяющееся в виде волн в газообразной, жидкой или твёрдых средах — в виде спектра последовательных значений громкости для тонов различной высоты. Мозг превращает эту информацию в воспринимаемый звук.

Аналогичные операции можно производить с помощью  математических методов над звуковыми  волнами или практически над  любыми другими колебательными процессами — от световых волн и океанских  приливов до циклов солнечной активности. Пользуясь этими математическими приёмами, можно раскладывать функции, представляя колебательные процессы в виде набора синусоидальных составляющих — волнообразных кривых, переходящих от максимума к минимуму, затем опять к максимуму, подобно океанской волне. Преобразование Фурье — это функция, описывающая амплитуду и фазу каждой синусоиды, соответствующей определённой частоте. (Амплитуда представляет высоту кривой, а фаза — начальную точку синусоиды.)

Преобразование  Фурье стало мощным инструментом, применяемым в различных научных  областях. В некоторых случаях его можно использовать как средство решения сложных уравнений, описывающих динамические процессы, которые возникают под воздействием электрической, тепловой или световой энергии. В других случаях оно позволяет выделять регулярные составляющие в сложном колебательном сигнале, благодаря чему можно правильно интерпретировать экспериментальные наблюдения в астрономии, медицине и химии.

Первым человеком, поведавшим миру об этом методе, был французский математик Жан Батист Жозеф Фурье, именем которого и было названо преобразование. Сказать, что Фурье интересовался теплотой, слишком мало, — он был просто помешан на тепле. Люди, посещавшие его дом в Гренобле, часто жаловались на царившую там невыносимую жару. Одевался он также всегда очень тепло. Возможно, именно жаркий климат привлёк Фурье, когда в 1798 году он присоединился к свите Наполеона, состоявшей из 165 учёных, которая сопровождала его в египетском военном походе.

Пока Наполеон сражался с сирийцами в Палестине, изгонял турок из Египта и преследовал предводителя мамлюков Мурад-бея, французские учёные занимались крупными научными исследованиями в географии, археологии, медицине, земледелии и истории. Фурье был назначен секретарём научной организации, известной под названием Египетского института. Он весьма успешно справлялся со своими административными обязанностями, поэтому ему часто стали поручать и задания дипломатического характера. Несмотря на свою занятость, он всё же успевал интенсивно заниматься изучением египетских древностей и размышлять о математической теории нахождения корней алгебраических уравнений.

Незадолго до того, как в 1801 году французы были изгнаны из Египта, Фурье и его коллеги отплыли во Францию. Командующий британским военным флотом адмирал Сидней Смит захватил их корабль вместе с грузом — древними египетскими рукописями и другими находками. Следуя благородному духу той эпохи, Смит высадил учёных целыми и невредимыми в Александрии. Впоследствии представитель британского командования был направлен в Париж, чтобы вернуть конфискованные материалы, за исключением Розеттского камня (являющегося ключом к расшифровке египетских иероглифов), который и по сей день стоит в Британском музее как памятник военного поражения Наполеона и напоминание о том вкладе, который он внёс в египтологию.

Вернувшись во Францию, Фурье сосредоточился на математических исследованиях, став профессором анализа  в Политехнической школе, но в 1802 году вернулся на службу к Наполеону. Фурье был назначен префектом департамента Изер. Пытаясь устранить руины, оставшиеся после революционных событий 1789 года, он возглавил строительство французского участка дороги на Турин и осушил 80 000 км2 малярийных болот. В этот же период он вывел уравнение, описывающее распространение тепла в твёрдом теле. К 1807 году Фурье изобрёл и метод решения этого уравнения: преобразование Фурье.

Фурье применил свой математический метод для объяснения механизма теплопроводности. Удобным примером, в котором не возникает вычислительных трудностей, является распространение тепла по якорному кольцу (железному кольцу, к которому крепится якорь), погружаемому на некоторое время наполовину в огонь. Когда погружённая в огонь часть кольца раскаляется докрасна, его вынимают из огня. Чтобы тепло не успело уйти в воздух, кольцо сразу закапывают в мелкий песок, а затем измеряют температуру на той его части, которая непосредственно огнём не нагревалась.

Вначале распределение  температуры нерегулярно: часть  кольца равномерно холодная, другая часть  равномерно горячая, а между этими  зонами наблюдается резкий градиент температуры. Однако, по мере того как тепло распространяется от горячей зоны к холодной, распределение температуры становится всё более равномерным. Вскоре распределение приобретает форму синусоиды: график изменения температуры плавно нарастает и убывает в виде буквы S, точно по такому же закону, по которому изменяется функция синуса или косинуса. Синусоида постепенно выравнивается и в конце концов температура по всему кольцу становится одинаковой.

Фурье предположил, что первоначальное нерегулярное распределение можно разложить на множество простых синусоид, каждая из которых имеет свой максимум температуры и свою фазу, т.е. начальное положение на кольце. При этом каждая синусоидальная компонента должна изменяться от максимума к минимуму и обратно целое число раз на одном полном обороте по кольцу. Составляющая, которая имеет ровно один период на кольце, была названа главной гармоникой, а составляющие с двумя, тремя и более периодами — соответственно второй, третьей и т.д. гармоникой. Математическая функция, описывающая максимум температуры и позицию, или фазу, каждой из гармоник, называется преобразованием Фурье от функции распределения температуры. Фурье свёл единую функцию распределения, трудно поддающуюся математическому описанию, к более удобным в обращении рядам периодических функций синуса и косинуса, которые в сумме дают исходное распределение.

Солнечный луч, разложенный на спектр, является физическим аналогом математических преобразований (вверху). Интенсивность солнечного луча, входящего в призму, постоянно меняется во времени (внизу). Свет, выходящий из призмы, разделён в пространстве на отдельные «чистые» цвета, или частоты. В этом спектре имеется средняя амплитуда на каждой частоте. Таким образом, функция интенсивности от времени трансформировалась в функцию амплитуды в зависимости от частоты. Преобразование Фурье может представить сигнал, изменяющийся во времени, в виде зависимости частоты и амплитуды, но оно даёт также информацию о фазе.
 

Применяя этот анализ к процессу распространения  тепла по кольцу, Фурье рассудил, что чем больше число периодов у синусоидальной компоненты, тем быстрее она должна затухать. Эту мысль можно проиллюстрировать, проследив за отношениями, наблюдающимися между главной и второй гармониками температурного распределения. Во второй гармонике температура дважды меняется от максимума к минимуму на одном проходе вдоль кольца, в то время как в главной гармонике это изменение наблюдается лишь один раз. Следовательно, расстояние, которое нужно преодолеть теплу от максимума температуры к минимуму, во второй гармонике вдвое меньше, чем в первой, главной. Более того, температурный градиент во второй гармонике также вдвое круче, чем в первой. Таким образом, поскольку вдвое более интенсивный поток тепла проходит вдвое меньшее расстояние, вторая гармоника должна затухать вчетверо быстрее, по сравнению с первой, как функция времени.

Гармоники более  высокого порядка будут затухать ещё быстрее. Поэтому лишь одно синусоидальное распределение, соответствующее главной  составляющей, останется при приближении  температуры кольца к равновесию. Фурье считал, что с помощью этого метода можно рассчитать, как любое начальное распределение температуры изменяется во времени.

Распределение температуры в железном кольце было одним из первых физических явлений, анализировавшихся методом Фурье. Вверху (a) показано распределение температуры в различных точках кольца: более горячие области окрашены ярче. Чтобы провести анализ, кольцо «разгибают» и измеряют температуру в каждой точке (b), на основании полученных данных строят график распределения температуры вдоль окружности (c). Затем эту графическую функцию раскладывают на множество синусоидальных кривых различной частоты и амплитуды (d). При простом суммировании 16 кривых (сплошная линия, e) получается хорошая аппроксимация исходного распределения температуры (пунктирная линия, e). 
 
Теплопроводность  железного кольца определяет изменение температурного распределения во времени (слева). Так же, как температурное распределение можно описать в любой момент времени рядом синусоидальных кривых, изменение распределения во времени может быть описано через изменения характера самих синусоид. Здесь показаны распределения с одним периодом, или первая гармоника (в центре), и распределение с двумя периодами, или вторая гармоника (справа). Фурье установил, что вторая гармоника затухает в 4 раза быстрее, чем первая, а гармоники более высоких порядков затухают с ещё большей скоростью. Поскольку первая гармоника изменяется медленнее других, общее температурное распределение стремится к синусоидальной форме первой гармоники.
 

Анализ Фурье был вызовом математическим теориям, которых твёрдо придерживались его современники. В начале XIX века многие выдающиеся парижские математики, в том числе такие как Лагранж, Лаплас, Лежандр, Био и Пуассон, не могли принять утверждение Фурье о том, что любое исходное распределение температуры можно разложить на составляющие в виде главной гармоники и гармоник более высоких частот. Леонард Эйлер также считал идеи Фурье ошибочными, хотя к тому времени сам пришёл к выводу, что некоторые функции можно представить суммой синусоид. И когда Фурье огласил своё утверждение на одном из заседаний Французской академии наук, Лагранж заявил, что это невозможно.

Тем не менее  академия не могла игнорировать значение результатов, полученных Фурье, и удостоила  его премии за математическую теорию законов теплопроводности и сравнение  результатов его теории с точными физическими экспериментами. Однако награда была присуждена со следующей оговоркой: «Исходя из новизны предмета исследований и его важности, мы решили присудить премию, отмечая в то же время, что путь, которым автор приходит к своим уравнениям, не свободен от затруднений, и что анализ, проведённый им при их интегрировании, оставляет желать несколько большей общности, равно как и строгости».

Сомнения, с которыми коллеги Фурье встретили его  работу, явились причиной того, что  её публикация была отложена до 1815 года. На самом деле она так и не была полностью напечатана вплоть до 1822 года, когда вышла его книга «Аналитическая теория тепла».

В подходе Фурье  основное возражение вызывало утверждение  о том, что по существу разрывная  функция может быть представлена суммой синусоидальных функций, являющихся непрерывными. Разрывные функции описывают разрывающиеся кривые или прямые линии. В качестве примера можно привести функцию, называемую ступенькой Хевисайда, значение которой равно 0 слева от разрыва и 1 справа. (Такая функция описывает, например, зависимость электрического тока от времени при замыкании цепи.) Современники Фурье никогда не сталкивались с такой ситуацией, когда разрывная функция описывалась бы комбинацией обычных, непрерывных функций, таких как линейная, квадратичная, экспонента или синусоида. Однако если Фурье был прав в своих предположениях, то сумма бесконечного ряда тригонометрических функций должна сходиться к точному представлению ступенчатой функции, даже тогда, когда у функции много таких ступенек. В то время это утверждение казалось совершенно абсурдным.

Тем не менее, несмотря на все эти сомнения, многие исследователи, в том числе математик Софи Жермен и инженер Клод Навье, начали расширять сферу исследований Фурье, выведя их за пределы анализа теплопроводности. А математиков тем временем продолжал мучить вопрос о том, может ли сумма синусоидальных функций сходиться к точному представлению разрывной функции.

Вопрос о сходимости возникает всякий раз при суммировании бесконечного ряда чисел. Рассмотрим классический пример: достигнете ли вы когда-нибудь стены, если с каждым шагом будете проходить половину оставшегося расстояния? Первый же шаг приведёт вас к отметке на половине пути, второй — к отметке на трёх его четвертях, а после пятого шага вы преодолеете уже почти 97% пути. Вы почти дошли до цели, однако сколько бы ещё шагов ни сделали, вы никогда не достигнете её в строгом математическом смысле. Можно лишь доказать математически, что в конце концов вы сможете приблизиться на любое заданное, сколько угодно малое расстояние. (Доказательство будет эквивалентно демонстрации того, что сумма одной второй, одной четвертой, одной восьмой, одной шестнадцатой и т.д. стремится к единице.)

Вопрос о сходимости рядов Фурье снова возник в конце XIX века в связи с попытками предсказания интенсивности приливов и отливов. Лорд Кельвин изобрёл аналоговое вычислительное устройство, позволяющее морякам торгового и военного флота узнавать о приливах и отливах. Аналоговый вычислитель механически определял наборы амплитуд и фаз по таблице приливных высот и соответствующих моментов времени, тщательно замеренных на протяжении года в данной гавани.

Каждая амплитуда  и фаза представляли синусоидальную компоненту функции высоты прилива  и были одной из периодических составляющих. Результаты вводились в вычислительное устройство лорда Кельвина, которое синтезировало кривую, предсказывающую высоту прилива как функцию времени на следующий год. Вскоре подобные кривые приливов были составлены для всех портов мира.

  
Предсказатель приливов Феррела, аналоговое вычислительное устройство, построенное в конце XIX века, производил анализ Фурье для прогнозирования высоты приливов. По данным о высоте приливов, собранным в данной гавани, другая машина вычисляла так называемые коэффициенты Фурье, каждый из которых отражал влияние на периодичность высоты прилива отдельных факторов, таких как гравитационное притяжение Луны. Таблицы коэффициентов Фурье публиковались для всех портов мира. Коэффициенты для данного порта вводились в специальные машины, такие как предсказатель приливов Феррела, путём соответствующих поворотов ручек на задней панели машины (слева). Установив затем интересующее время на передней панели (справа), на циферблате автоматически выставлялась предсказываемая высота.

Информация о работе Преобразование фурье