У меня есть небольшой запрос относительно дискретных преобразований Фурье. Если я правильно понимаю, то мы делаем преобразование полинома в его представление точечного значения, причем n точек для многочлена, который поднимается до степени n-1. Но почему мы должны оценивать его на n-ом корнях единства? Разве никакие другие n точек однозначно не идентифицировали бы этот многочлен И были бы намного проще?Понимание дискретного преобразования Фурье
Не могли бы другие точки n однозначно идентифицировать этот многочлен И было бы намного проще?
Нет для обоих. 1) Нет никакой гарантии, что будут выполняться n произвольных точек и 2) это будет не проще. Поверните вопрос: почему вы возражаете против корней единства?
Главные аппликативные причины
У вас не было бы ни одного из них со случайными точками - интуитивно говоря, потому что они не образуют группу. Существует еще много теоретических причин (а также еще несколько применимых)
@Dave Lehavi - Что случилось с этим? Вы отправляете ответ, который, будучи более технически сформулированным, находится в существенном согласии с моим, меня поменяет, а затем переходите к другому несвязанному вопросу? Рассматривали ли вы переход на декаф? – MarkusQ
Нет, не совсем. Это не имеет ничего общего с полиномами. Речь идет о разложении вектора (начальная последовательность чисел) на другую основу . Просто эта основа имеет ряд очень полезных свойств:
(1) Это ортогонально - векторы не смешиваются, и определение преобразования обратно к исходной основе чрезвычайно просто.
(2) Базисные векторы Фурье представляют собой собственные векторы операции сдвига (или кругового сдвига для дискретного случая) - базисная функция Фурье , после сдвига векторных индексов, по-прежнему остается той же функцией (раз число). Именно это делает свертки и решение большого класса дифференциальных уравнений очень простыми в пространстве Фурье.
(3) И, наконец, записи являются корнями единства - это дает повышение до F FT, один из самых изящных алгоритмов, когда-либо обнаруженных, уменьшая операции N^2, необходимые для смены основы на N log N.
Вот два «интуитивных» объяснения дискретного преобразования Фурье. Они не прыгают в уравнения непосредственно, но вы пройдете через в желание, кто-сказал-мне-это-прежде, чем способ
Это вниз прямо и плоский НЕТ (я бы хотел кричать). предположим, что f, g - различные полиномы n-1 степени и одинаковы на n точках, то их разность F равна 0 на n точек. Хурай! вы только что нашли полином n-1 степени с n корнями. –
Отвечая на ваши замечания на мой пост: никакие другие моменты не будут работать, но не по той причине, о которых он упоминает. Я считаю, что ваш ответ вводит в заблуждение, потому что вы говорите более или менее «это может сработать, но зачем беспокоиться» (это не так). Я не знаю, о каком другом вопросе вы говорите, и я ненавижу декаф. –
@David Lehavi - Вы можете заставить его работать для других (тщательно подобранных) наборов точек (подумайте о до-ином изменении представления или использовании альтернативного набора орто-нормальных базисных функций), но _in_general_ он не сработает , – MarkusQ