2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Ряд Фурье
Сообщение28.04.2014, 16:27 


28/04/14
1
Описание
Горячий участок одной программы расчета течения жидкости вычисляет сумму ряда
$$\sum_{i=0}^{N}\sum_{j=0}^{N} a_{ij}\cos(ix)\cos(jy)$$для набора из M точек $(x,y)$, принадлежащих области течения $[-\pi/2;\pi/2]^2$. Запрограммируйте как можно более быстрый алгоритм расчета данной суммы. Коэффициенты $a_i_j$ задайте формулой
$$a_{ij} = \frac {1} {1+i+j+\frac{1}{\sqrt{1+ij}}}.$$Помогите, люди добрые. Не получается ничего :(

 Профиль  
                  
 
 Re: Ряд Фурье
Сообщение11.09.2015, 11:31 


11/09/15
2
Метод схлопывания пополам.
Область i,j бьётся на четвертинки, над каждой вызывается рекурсия.
Пока четвертинки не станут достаточно маленькими, чтобы напрямую сложить - 4 или 16 например.

 Профиль  
                  
 
 Re: Ряд Фурье
Сообщение11.09.2015, 17:54 
Заслуженный участник


25/02/11
1786
Не знаю, какое олимпиадное решение подразумевается, но по-нормальному, раз "горячий участок", то много раз считается, и, вероятно, пределы для возможных значений $N$ известны. Так что имеет смысл заранее посчитать значения коэффициентов и хранить в массиве. Сгруппируем слагаемые, вынося $\cos i x$ и получим алгоритм с $N(N+1)$ умножениями и $2N$ вычислениями косинусов. Поскольку вычисление косинусов медленнее, чем умножение, можно вычислять их рекуррентно по формулам приведения. В общем, получится $O(N^2)$ умножений плюс вычисление $\cos x$, $\sin x$, $\cos y$, $\sin y$.

 Профиль  
                  
 
 Re: Ряд Фурье
Сообщение11.09.2015, 18:11 


18/05/15
679
Это же дискретное преобразование Фурье массива $a_{ij}$. Для него написаны быстрые алгоритмы. Например, "Численные методы" Кобельков, Жидков.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group