Вычислительная математика и теория алгоритмов Преобразование фурье.

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

Быстрое пф.

43. (4 задачи) (БПФ)Вычислить быстрое преобразование Фурье на степенях от

5. . Проверить обратным преобразованием(проверку сделать для только для Фурье образа четного полинома, см. пример)

6. (решатьa) этот запасной).

Пример проверки – расчёт обратного преобразование Фурье к преобразованному четному полином

Имитация алгоритма Шеханге-Штрассена

Перемножение полиномов и чисел с помощью преобразования Фурье ()

44. (1 задача, действ.Фурье2)ипредставить в виде вектора значений на точках. Перемножить значения, восстановить полином 4й степени по значениям, перевести в число с помощью поразрядного сдвига.

Схема решения:

Подставим наши аргументы, чтобы найти четыре уравнения на четыре (не известные нам пока) коэффициента:

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

45. (1,5 задачи, комп. Фурье, Ш.Ш.) Перемножить алгоритмом типа Шеханге-Штрассена и. Использовать корни четвертой степени из 1:. (- они образуют геометрическую прогрессию с коэффициентом) Пусть

46. (0,5 задачи, действ.Фурье - начало) иперемножить как полиномы. Восстановить с помощью поразрядного сдвига. Сопоставить результат с прямым перемножением чисел. Пример

Подставляем 10 вместо х, чтобы найти результат перемножения

Проверка прямым перемножением

(т.е. решение верно).

//Пример2: ,

Простейшее битовое преобразование Фурье.

47. битовое преобразование Фурье. перемножить с помощью дискретного битового преобразования Фурье по модулю простого числа (7) (по желанию Можно взять больший простой модуль, например 11,17 и т.д.). два числа cиd. если их произведение оказывается больше 63. одно из них разделить пополам, взять целую часть. желательно, чтобы при этом не получилось число 5 - чтобы этого избежать поделите другое число (ибо пример с числом 5 разобран нами ниже).

обратная матрицаили , что тоже, потому что.

пример перемножим число 5 и 5 (у нас слишком мало примеров ограниченной сложности, поэтому не будем показывать два разных числа)

, второе число совпадает с первым поэтому результат тот же

=

Восстановим результат перемножения полиномов с помощью поразрядного сдвига

.

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

, где - примитивный кореньn+1 степени из 1. Обычно корни бывают в комплексной плоскости вида над полем комплексных чисел, - обычно берётся кореньn+1 степени из 1:(для удобства проведения быстрого преобразования Фурье важно, чтобы,), либо корни по модулю натурального числа. здесь тоже бывает важно, чтобы это был корень степени.

пример .

идея основана на

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

1, ,,,..,,.

с учетом равенства

вычисление обратного преобразования Фурье основано на вычислении полинома с коэффициентами полученными на предыдущем этапе в точках обратным предыдущим

1, ,,,..,,.

и делении итогового результата на число точек.

Пример

Уточним корни

прямое преобразование ,обратное преобразование

проверим, что данные преобразования и их матрицы при перемножении дают единичную матрицу

.

Задача. Вычислить по схеме Горнера полином , вычислить в точкаx=1, х=-1,x=2,x=i, х=-i

общий подход

Теория Быстрого преобразования Фурье - продолжение предыдущего раздела:

Вычисления преобразования Фурье с помощью схемы Горнера во всех точках займет n²действий, что много и представляет проблему если вектор большой. при частоте 48 килогерц принятой при аудиозаписи в час мы имеемn=50 000c^-1*4000c=200 000 000 компонент (читатель привыкший считать независимо от обстоятельств точно, наверное убеждён в НАШЕМ часе 60*60=3600 секунд, что примерно 4000). квадрат этого числа 4 10¹⁶

Быстрое преобразование Фурье позволяет вычислить за , что как минимум в миллион раз быстрее. Быстрое преобразование Фурье делается на корнях степении интегрирует идеи быстрого возведения в степень и схемы Горнера быстрого вычисления полиномов в одной точке.

Всё основано на равенстве.

. Мы последовательно разлагаем полином на четный и нечетный. из нечетного полинома выносимx, в результате имеем два полинома от