Введение

Класс методов, используемых в численном анализе и научных вычислениях для решения ОДУ/УЧП. Спектральные методы – это класс техник, применяемых в прикладной математике и научных вычислениях для численного решения определенных дифференциальных уравнений. Идея заключается в представлении решения дифференциального уравнения в виде суммы определенных "базисных функций" (например, ряда Фурье, представляющего собой сумму синусоид), а затем в выборе коэффициентов в этой сумме таким образом, чтобы максимально точно удовлетворить дифференциальное уравнение. Спектральные методы и методы конечных элементов тесно связаны и основаны на одних и тех же принципах; основное различие состоит в том, что спектральные методы используют базисные функции, которые, как правило, отличны от нуля во всей области определения, в то время как методы конечных элементов используют базисные функции, отличные от нуля только на небольших подмножествах (компактном носителе). Следовательно, спектральные методы связывают переменные глобально, а методы конечных элементов – локально. Отчасти по этой причине спектральные методы обладают превосходными свойствами сходимости, при этом так называемая "экспоненциальная сходимость" является максимально достижимой, когда решение гладкое. Однако известных трехмерных результатов захвата ударных волн в единой области с использованием спектральных методов не существует (ударные волны не являются гладкими). В сообществе методов конечных элементов метод, в котором степень элементов очень высока или возрастает с увеличением параметра сетки h, иногда называют методом спектральных элементов. Спектральные методы могут применяться для решения дифференциальных уравнений (УЧП, ОДУ, собственные значения и т.д.) и задач оптимизации. При применении спектральных методов к УЧП, зависящим от времени, решение обычно представляется в виде суммы базисных функций с коэффициентами, зависящими от времени; подстановка этого выражения в УЧП приводит к системе ОДУ относительно коэффициентов, которую можно решить любым численным методом для ОДУ. Задачи на собственные значения для ОДУ аналогичным образом преобразуются в матричные задачи на собственные значения. Спектральные методы были разработаны в серии работ Стивена Орсага, начиная с 1969 года, и включают, помимо прочего, методы рядов Фурье для задач с периодической геометрией, полиномиальные спектральные методы для задач с конечной и неограниченной геометрией, псевдоспектральные методы для сильно нелинейных задач и спектральные итерационные методы для быстрого решения стационарных задач. Реализация спектрального метода обычно осуществляется с использованием коллокации, подхода Галеркина или метода Тау. Для очень небольших задач спектральный метод уникален тем, что решения могут быть записаны символически, предоставляя практическую альтернативу рядовым решениям дифференциальных уравнений. Спектральные методы могут быть менее затратными в вычислительном отношении и проще в реализации, чем методы конечных элементов; они наиболее эффективны при стремлении к высокой точности в простых областях с гладкими решениями. Однако из-за их глобального характера матрицы, связанные с шагом вычислений, являются плотными, и вычислительная эффективность быстро снижается при большом количестве степеней свободы (за некоторыми исключениями, например, если матричные операции могут быть представлены в виде преобразований Фурье). Для больших задач и негладких решений методы конечных элементов, как правило, работают лучше благодаря разреженным матрицам и более эффективному моделированию разрывов и резких изгибов.

Алгоритм

Вычислите преобразование Фурье (bj,k) функции g.
Вычислите преобразование Фурье (aj,k) функции f по формуле.
Вычислите f, взяв обратное преобразование Фурье (aj,k). Поскольку нас интересует только конечное окно частот (размера n, например), это можно сделать с помощью алгоритма быстрого преобразования Фурье. Следовательно, в общем случае алгоритм выполняется за время O(n log n).

Связь с методом спектральных элементов

Можно показать, что если функция бесконечно дифференцируема, то численный алгоритм с использованием быстрых преобразований Фурье будет сходиться быстрее, чем любой полином от размера сетки h. То есть, для любого n > 0 существует такое δ, что ошибка меньше, чем δ для всех достаточно малых значений h. Мы говорим, что спектральный метод имеет порядок точности n для любого n > 0. Поскольку метод спектральных элементов является методом конечных элементов очень высокого порядка, существует сходство в свойствах сходимости. Однако, в то время как спектральный метод основан на спектральном разложении конкретной краевой задачи, метод конечных элементов не использует эту информацию и применим к произвольным эллиптическим краевым задачам.