Быстрое преобразование Фурье с использованием матрицы Вандермонда - оценка коэффициентов?

Question

Скажите, что я пытаюсь оценить полином:

x^2 + 1

Использование метода быстрого преобразования Фурье для оценки коэффициентов. Теперь я могу изменить это в матрицу / векторную форму, используя коэффициент в качестве входных данных для быстрого преобразования Фурье:

так:

x^2 + 1 = <1, 0, 1, 0>

Это делается с использованием значения коэффициента, например, 1 = 1, 0x ^ 1 = 0, X ^ 2 = 1 и т. Д.

Теперь мы подошли к тому моменту, когда я полностью запутался. Я имею в виду использовать матрицу Вандермонда: Матрица Вандермонда ~ Wiki , чтобы вычислить эти значения в форме FFT с использованием матрицы:

1 1 1 1  
1 i-1-i
1-1 1-i
1-i 1 i

Выход

fft(1,0,1,0)

есть

(2,0,2,0)

Теперь это шаг, который я не совсем понимаю, как мы использовали эту матрицу для получения (2,0,2,0)?

Answer 1

Во-первых, ваша матрица Вандермонда неверна. Запись (4,3) должна быть -1, а не 1, поскольку четвертая строка должна быть (-i) ⁰ , (-i) ¹ , (-i) ² , (-i) ³ . Обратите внимание, в частности, что

(- i) * (- i) = (-1) ² * i ² = i ² = -1.

С этой поправкой результат следует из умножения матрицы Вандермонда на вектор столбца (1,0,1,0).

Answer 2

Может быть, вы могли бы объяснить, какова ваша общая цель здесь. Я никогда не слышал об использовании БПФ для оценки полиномов. Они используются для умножения полиномов или для свертки сигналов (эквивалентная задача), но я не стал бы беспокоиться, если бы у полиномов / сигналов не было большого числа членов. x ² + 1 не большой. 16 терминов невелики, и даже 64 или 256 терминов, вероятно, лучше сделать с помощью простых методов O (N ² ).

Дискретные преобразования Фурье использовать матрицу M _ij = & omega; ^ij где & omega; это N-й комплексный корень из 1, а нумерация столбцов / строк изменяется от 0 до N-1.

Быстрые преобразования Фурье никогда не используют эту матрицу напрямую, они сильно оптимизированы для использования метода «разделяй и властвуй» ( алгоритм Кули-Тьюки ) для вычисления конечного результата на этапах 2x2 DFT последовательно и параллельны друг другу.

Если вы напишите свой вектор как [0,1,0,1] вместо [1,0,1,0], я думаю, вы увидите, что если вы умножите это на матрицу, которую вы дали, вы получите [0,2,0,2]. (Хотя у вас есть ошибка, это

1 1 1 1  
1 i-1-i
1-1 1-1
1-i-1 i

) В используемой программе должно быть какое-то соглашение, которое изменяет порядок коэффициентов вектора.