Разложение Фурье

[xyz]

Если перевести всю справку, то получится намного больше! До сих пор под энциклопедией я понимал совершенно иное. Хотя вас понимаю, одно дело делать пересказ готового, другое отвечать на вопросы, пусть даже и не очень сложные. Первое определяет технические возможности, второе творческие. Или я не прав?!

[Break]

Antic, тема мне интересна, т.к. часто приходится работать с Фурье. Я, просто из Ваших постов сделал вывод, что эта тема вам близка, потому рассчитывал на подсказку. Как всегда, буду делать сам.

[Antic]

Break, еще раз желаю успеха. Тема мне действительно близка, но времени сейчас нет!

[uni]

Уважаемый Break, по вашему вопросу

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

и по поводу (Antic)

то можно сформировать ряд Фурье с подстановкой полученных из FFT данных для вычисленных амплитуд и фаз гармоник

я могу сказать следующее. Сразу извиняюся за пример без использования Maple, но вы я вижу многоплатформенный товарищ и вам не составит труда "портировать" документ в Maple. Мне быстрее и легче было это сделать в Mathcad. Если будут вопросы, то я отвечу на любой.
Я кстати не знаю какой Maple считается новым, в ядре, которое используется в Mathcad функция FFT уже была, а это Maple V R4.

[uni]

Похоже, что коэффициент равен двойке. Её надо вставить под знак суммы в левой формуле, т.е. скобку под знаком суммы умножить на 2. Тогда вроде красиво, за исключением того, что восстановление на основе ряда немножко по-моему смещено вниз. Не претендую на абсолютную правильность, но в том, что касается БПФ я думаю теперь можно быть уверенным. Как из разложения в ряд Фурье получается левая формула? Фокус очень прост. Берём обратное Фурье преобразование в виде формулы с суммой и экспонентой внутри. Раскладываем экспоненту по формуле Эйлера на синус и косинус. Умножаем комплексные числа покомпонентно, т.е. спект умножаем на cos + i*sin, получится комплексное число под суммой. Смотрим на разложение в ряд Фурье и сравниваем, видим, что если взять реальную часть от полученной в результате преобразования формулы, то получим то же разложение в ряд по гармоническим функциям, но в качестве коэф-тов уже выступают алгербраическое представление спектральных составляющих. В общем, вот и всё, тот кто понял молодец, а не понял - я нарисую картинки, если хотите. Тут по-моему есть ещё одна тонкость, которую "чистмат" может от неопытности не заметить с первого раза. А именно, нужно подобрать дискретизацию сигнала таким образом, чтобы дельта по частоте в спектре совпадала с элементарной частотой в ряде Фурье. Гармоники, на которые мы разбиваем сигнал должны быть одними и теми же, то в методе БПФ, что в разложении в ряд. Это возможно не сразу ясно.

P.S. В приведённой выше картинке нужно при вычислении коэффициента a(0) удвоить значение интеграла. Иначе сигнал выглядит ниже чем есть на самом деле - постоянная составляющая не правильно посчитана. Если исправить все будет правильно. И совпадет со вторым вариантом - где коэффициенты вычисляются через FFT. Признаю неточность.

[Antic]

Уважаемый uni! К сожалению в Вашем ответе очень много принципиальных неточностей. Прямое и обратное БПФ относятся к сугубо численным методам и потому вспоминать символьный Maple в связи с этим не стоит - он тут совсем не к чему. В Mathcad, как в изначально численной системе, реализация БПФ и довольно мощная была задолго до ее появления в Maple. Кстати она с множеством примеров описана в моей книге Дьяконов В. В. "Энциклопедия Mathcad 2001i/11" (М.: СОЛОН-Пресс, 2004). Никаких сдвигов восстановленной зависимости там нет, и если Вы посмотрите книгу, то разберетесь, что у Вас неточно. Кроме того, в ней Вы можете найти очень интересные и оригинальные (вовсе не из справки, как постоянно хамит xyz) примеры точного восстановления сложных зависимостей по модифицированному методу Филона (дискретизация по любому числу отсчетов с линейной интерполяцией между точками), примеры приближения рядами Фурье с подавлением эффекта Гиббса (он у вас виден даже с "закрытыми глазами") и многое другое. Все это можно применить и в Maple, но сейчас у меня просто нет времени повторяться. К тому же задавший тему спрашивал совсем не об этом - он хотел, что бы кто то сделал Maple-процедуру из его программного модуля, написанного непонятно на каком языке.

[uni]

Да нет, не может быть у меня много, тем более принципиальных, неточностей. Первую часть своего примера я взял из книги А.Б. Сергиенко "Цифровая обработка сигналов" - см. тему "Ряд Фурье", я лишь немного украсил картинками приведённые там фурмулы (формулы от туда, как и замечание).
Слово символьный я даже не упоминал. Maple имеет (имел) функции для численного выполнения одно и двумерного БПФ, это я и указал, они не новы, о чем я узнал просмотрев не так давно книжку В. П. Дьяконова "Математическая система Maple V R3/R4/R5" там есть список функций в конце, где есть FFT. Так что символьный Maple не упоминал . Другую книжку Вашу посмотрю, просто у меня картинки не совсем совпали, чуть-чуть. А должны. Что касается второй части моего примера, то придумал я его сам. Вроде ничего там страшного нету - складываем синусоиды и косинусоиды - вроде ничего необычного. И преобразования вроде бы я сделал верно (я их правда в уме делал, но ведь работает).

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

P.S. Смотрите P.S. выше, нашел ошибку, посмотрев книжку уважаемого Antic'а.

[uni]

Уважаемый Antic! Да похоже 2 замечания я приму как значительные - это неправильно посчитанная постоянная составляющая и похоже знак внутри суммы должен быть "минус", т.е. мнимые части спектральных составляющих (имеется в виду алгебраическое представление) надо брать отрицательными. Надо все-таки на бумаге сначала выкладки делать.

Вот попробовал сделать вновь, уже исправленный вариант.

[Antic]

Добрый вечер, uni! По главному замечанию Вы меня просто не совсем поняли. Я имел ввиду лишь то, что БПФ в Mathcad реализовано без какого либо обращения к ядру Maple. Оно было даже в DOS-кой версии Mathcad, когда он был чисто численной системой. И реализовано в Mathcad БПФ и ныне получше чем в Maple, поскольку ориентировано на решение инженерных задач. Что касается ядра Maple, то оно было включено в Mathcad с одной единственной, хотя и важной целью - выполнением символьных операций. С двумя другими замечаниями Вы согласились, так что,думаю, "конфликт" улажен. А вообще эта тема очень интересная, но уже имеет альтернативу - вейвлет-преобразования. В моих книгах они, кстати, описаны впервые применительно к Mathcad- реализации и намного полнее, чем в справке.

Добавляю в порядке редактирования - уже утром! Uni, не стоит говорить о Mathcad на форуме по Maple. Лучше, если это вам интересно, откройте тему на форуме по Mathcad. Я готов в ней поучаствовать в меру сил - увы пока их хватает на текущие дела с описанием MATLAB.

[uni]

Не стоит, так не стоит. Будем делать в Maple. Вот третий пример выполненный в 9.01. Я хотел лишь показать как возможно использовать результаты БПФ. Всё ведь крутиться вокруг одного и того же - есть базисы, коэффициенты - проекции на гармонические базисы. То, как они находятся, важно с вычислительной точки зрения (с БПФ получается быстрее), формулы сами для вычисления проекций просто показательны.

В файле документа использованы гостовские шрифты из комплекта Компаса, скорее всего у вас их нет, но я думаю это не страшно.

[Antic]

Uni, теперь это в тему - Maple. Но, смею заметить, что у Вас БПФ оказалось побоку. Поскольку синтезируете Вы сигнал прямо по полученным гармоникам, не используя просто висящий FFT(10,x,y). И обратное БПФ Вы тоже не используете (и даже его просто не сделали).

[uni]

Уважаемый Antic. Закомментируйте строку с БПФ и оцените разницу. При реализации БПФ можно пользоваться теми же массивами, в которых находится сам сигнал - это два массива - реальные и мнимые части. Это используется скорее всего везде, т.к. это разумно с точки зрения ресурсов (накой чёрт выделять память под массивы результата, когда алгоритм позволяет выводить результат прямо в область памяти с исходными данными?). Это используется по-видимому в реализации FFT() в Maple.

Вопрос Break'а, если его глубоко не понимать, а на уровне дословного и заключался в том, как найти коэффициенты (проекции) разложения по базису Фурье (sin, cos), без использования явных формул с интегралами. Я думаю, я в точности показал возможный вариант решения. Я бы сделал ещё одно уточнение - примеры, которые я показал выше, ищут эти самые коэффициенты в количестве N/2 штук сразу. Это означает что найдено будет столько спектральных составляющих. Конечно обратным БПФ можно синтезировать гораздо легче, но это уже продолжение разговора. Так мы и до идеальной фильтрации дойдем, потом будем фильтры синтезировать ... и т.д. Давай те уж на чём-нить остановимся, т.к. не видно заинтересованного лица.

[Antic]

Добрый вечер, uni! По первому вопросу признаю Вашу правоту - действительно я забыл, что массив x это исходный сигнал, а y - результаты БПФ. Насчет того, что это всегда так (повидимому), то это не совсем так - к примеру MATLAB при FFT позволяет втащить его результаты в указанный массив и это более естественно. Видимо Вам просто стоило поместить после функции FFT короткий комментарий о том, что она делает. Тогда подобные моему замечания были бы излишни.

Насчет обратного FFT Вы вроде согласились? Кстати при Вашем огромном (для такой простой функции, как трекгольная пила) числе отсчетов, еще не известно что будет быстрее - ваш прямой синтез по нескольким n гармоникам или проведение обратного БФП при N=1024. Но это уже мелочи - задачу Вы решили и я вовсе не против прекращения дискуссии на эту интересную тему.

[uni]

Чтобы расставить точки над i дам ещё пару комментариев.

действительно я забыл, что массив x это исходный сигнал, а y - результаты БПФ

Не совсем так, я использовал обозначение переменных их справки, где кстати и написано, что x и y - это входной комплексный сигнал в виде x+y*I и результат записывается также в x и y одновременно, т.е. надо понимать, что входной сигнал затирается выходным (это чтоб путаницы небыло для тех кто эту тему когда посмотрит). На рисунке я сделал комментарий
Я вообще рассматриваю мои тут манипуляции только как иллюстрацию для обучения кого-то этим вопросам. Другого практического применения не вижу. Количество отсчётов можно взять любое степени двойки (см. картинку). При этом постоянную составляющаю тоже считают гармоникой - нулевой. В предыдущей картинке это не полагалось, а теперь i=1..n-1 при восстановлении и n показывает правильное число гармоник. Т.е. постоянную составляющую и ещё 2. Но это вовсе не означает, что на картинке кривая должна выгибаться обязательно при большем количестве гармоник. Тут всё ещё зависит от коэффициентов, они могут быть нулевыми - нужно смотреть их распределение.
Я тут выше где-то боялся, а получается, что можно использовать произвольное число отсчётов, только надо помнить некоторые "минусы" метода БПФ - наложение спектров, например, то что в результате БПФ в векторе содержится и зеркальный спектр и количество гармоник в 2 раза меньше числа отсчетов. Это всё из-за вещественности сигнала. В радиотехнике как правило это всегда нужно помнить, т.к. сигналы все вещественные. Но бывают приложения, где сигналы комплексные и там уже мыслить надо по-другому.

P.S. Что-то у меня глюк какой-то случился - plot() поменял местами функции для отрисовки.