Понимание дискретного преобразования Фурье

Question

У меня небольшой запрос по поводу дискретных преобразований Фурье. Если я правильно понимаю, то, что мы делаем, это преобразовываем многочлен в его представление значения точки с n точками для многочлена, который идет в степень n-1. Но почему мы должны оценивать это по n-м корням единства? Разве другие n точек не могли бы однозначно идентифицировать этот многочлен И были бы намного проще?

Answer 1

Шеф Аппликатив Причины

• Волны становятся мономами.
• Произведение на пространстве времени - это свертка на фазовом пространстве и наоборот (так что вы можете умножить два полинома степени n в O (n log n)).
• Производная по пространству времени - произведение x на фазовое пространство и наоборот.

У вас не было бы ни одного из них со случайными точками - интуитивно говоря, потому что они не образуют группу. Есть еще много теоретических причин (а также несколько более прикладных)

Answer 2

Разве другие n точек не могли бы однозначно идентифицировать этот многочлен И были бы намного проще?

Нет обоим. 1) Нет гарантии, что n произвольных точек сработают и 2) это не будет проще. Переверните вопрос: почему вы возражаете против корней единства?

Answer 3

Вот два «интуитивных» объяснения дискретного преобразования Фурье. Они не переходят непосредственно к уравнениям, а проводят вас по пути «кто-то сказал мне-это-до»

1. http://betterexplained.com/articles/an-interactive-guide-to-the-fourier-transform/

2. http://www.altdevblogaday.com/2011/05/17/understanding-the-fourier-transform/

Answer 4

Нет, не совсем. Это не имеет ничего общего с полиномами. Речь идет о разложении вектора (начальная последовательность чисел) на другой основа. Просто у этой базы есть ряд очень полезных свойств:

(1) Оно ортогонально - векторы не смешиваются, и определить преобразование обратно в исходный базис чрезвычайно просто.

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

(3) И, наконец, записи являются корнями единства - это дает повышение к F FT, одному из самых элегантных когда-либо обнаруженных алгоритмов, сокращая N ^ 2 операций, необходимых для изменения базы к н лог б.