Документ взят из кэша поисковой машины. Адрес оригинального документа : http://num-anal.srcc.msu.su/lib_na/cat/ft_htm_p/ftfcr_p.htm
Дата изменения: Thu Nov 5 12:31:57 2015
Дата индексирования: Sun Apr 10 02:28:46 2016
Кодировка: Windows-1251
БЧА НИВЦ МГУ. FTFCR_P. Ускоренные дискретные преобразования Фурье
Текст подпрограммы и версий
ftfcr_p.zip 		Тексты тестовых примеров
tftfcr_p.zip

Подпрограмма:  FTFCR (модуль FTFCR_p)

Назначение

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

Математическое описание

Пусть длина  N преобразуемого вещественного ряда  X удовлетворяет условию:  N = 2 M + 1. Ряд  X преобразуется в вещественный ряд  A по формуле (прямое преобразование): 

                                    N-2             
     A r  =  1/2 * X0 +    ∑    X n * cos (π r * n/(N - 1) ) + 1/2 * (- 1)r * XN-1  ,
                                    n=1
      r = 0, 1, ..., N - 1

Так как система функций  cos (π r x),  r = 0, ..., N ортогональна на сетке  Xn = n / N с весами (1/2, 1, 1, ..., 1, 1/2), но не ортонормирована, обратное преобразование совпадает с прямым с точностью до постоянного множителя.

B вычислениях используется метод быстрого преобразования Фурье [1]. Ряд коэффициентов Фурье  A получается на месте исходного ряда  X без использования дополнительной рабочей памяти. При больших  N число операций пропорционально  N * log2N.

1.  В.А.Морозов, Н.Н.Кирсанова, А.Ф.Сысоев. Комплекс алгоритмов быстрого преобразования Фурье дискретных рядов. Сб. "Численный анализ на ФОРТРАНе", вып. 15, Изд. МГУ, 1976.

Использование 

procedure FTFCR(var X :Array of Real; N :Integer);


   Параметры
X - вещественный вектоp длины  N; перед началом работы подпрограммы содержит преобразуемый ряд  X; по окончании работы подпрограммы содержит преобразованный ряд  A;
N - заданная длина массива  X (тип: целый). 
   Версии:  нет 
   Вызываемые подпрограммы
FTF1C - вычисление дискретного или обратного дискретного преобразования Фурье комплексного ряда длины, равной степени двух, методом быстрого преобразования Фурье. 
   Замечания по использованию
  Длина  N преобразуемого ряда должна удовлетворять условию  N = 2 M + 1,  M > 2, целое. B противном случае pезультат работы подпрограммы не определен.

Пример использования 

Unit TFTFCR_p;
interface
uses
SysUtils, Math, { Delphi }
LStruct, Lfunc, UtRes_p, FTFCR_p;

function TFTFCR: String;

implementation

function TFTFCR: String;
var
N,_i :Integer;
const
X :Array [0..8] of Real = ( 1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0 );
begin
Result := '';
N := 9;
FTFCR(X,N);
Result := Result + #$0D#$0A;
for _i:=0 to 8 do
 begin
  Result := Result + Format('%20.16f ',[X[_i]]);
  if ( ((_i+1) mod 3)=0 )
   then Result := Result + #$0D#$0A;
 end;
Result := Result + #$0D#$0A;
UtRes('TFTFCR',Result);  { вывод результатов в файл TFTFCR.res }
exit;
end;

end.

Результаты:

   X = ( 40.,  -13.13707,  0.,  -1.6199,  0.,  -0.723231,  0., -0.519783065,  0. )