Белашов В.Ю., Чернова Н.М . Эффективные алгоритмы и программы вычислительной математики
Подождите немного. Документ загружается.
§ 2. Спектральный анализ временных рядов
Рис. 9.5. Нормированная автокорреляционная функция
экспоненциально убывающего сигнала
БПФ
БПФ
(
)
{
}
Ck
z
ОБПФ
()
{}
Zm
{
Y
(
l
)}
{C
Y
(
k
)}
{C
X
(
k
)}{
X
(
l
)}
Рис. 9.6. Схема алгоритма вычислениясвертки двух
последовательностей {
Z
(
m
)}
157
§ 2. Спектральный анализ временных рядов
Согласно теореме о свертке [Корн, Корн, 1978], в
этом случае справедливо равенство C
z
(k) = C
x
(k)C
Y
(k), k =
0, 1, ..., N - 1, из которого следует, что свертка Z(m) может
быть вычислена с помощью БПФ в соответствии со
схемой, изображенной на рис. 9.6. На БПФ рис. 9.7. по-
казана в качестве примера свертка экспоненциально
убывающей последовательности x(t) = e
-t
с самой собой,
полученная с использованием процедуры fft.
2.4. СИНТЕЗ СИГНАЛОВ С ПОМОЩЬЮ БПФ
Алгоритм БПФ, изложенный выше, может быть
использован для синтеза L-периодического продолжения
дискретизированного сигнала x(t) по его амплитудному и
фазовому спектрам [Ахмед, Рао, 1980]. Пусть дис-
кретизированный сигнал представляет собой последо-
вательность {X(m)}, m = 0, 1, ..., N при X(0)=X(N), которая
отвечает непрерывному сигналу x(t), измеренному на
промежутке времени длиной L. Пусть также заданы |F
x
(kw
0
)| и
ψ
x
(kw
0
) при k = 0, 1, ..., N/2 и N=2
n
, w
0
=2
π
/L.
Тогда сигнал X(m) может быть восстановлен (син-
тезирован) в соответствии со следующим алгоритмом:
1) находим F
x
(kw
0
) = |F
x
(kw
0
)|
(
)
e
ikw
x
ψ
0
, k = 0, 1, ...,
N/2;
2) определяем C
x
(k) = (1/L) F
x
(kw
0
), k = 0, 1, ..., N-1,
где, в соответствии с теоремой о комплексной сопряжен-
ности [Ахмед, Рао, 1980], C
x
(N/2 + l) =
C
x
(N/2 - l), l= 1, 2,
..., N/2 - 1;
3) с помощью алгоритма
БПФ производим обратное пре-
образование Фурье и находим
.
() ()
Xm C k W
mN
x
km
k
N
=⋅
−
=
−
∑
0
1
,
= 0, 1, ..., - 1
Данный алгоритм тестиро-
вался с использованием проце-
дуры FFT, пример полученных
результатов для N = 8, в сравне-
нии с контрольными, представ-
лен в табл. 9.2.
Таблица 9.2
Рис. 9.7. Свертка экспоненциалдьно убывающего
сигнала (нормированное значение)
k |F
x
(kw
0
)|
ψ
x
(kw
0
)
0 3.5 0 0
1 1.306563 -1.178097 1
2 0.707107 -0.785398
2
3 0.541196 -0.392699 3
4 0.5 -
4
5 - -
5
6 - -
6
7 - -
7
153
Айвазян С.А., Бежаева З.И., Староверов О.В. Классификация многомерных наблюдений. М.: Статистика, 1974.
Айвазян С.А., Енюков И.С., Мешалкин Л.Д. Прикладная статистика. Основы моделирования и первичная обработка
данных. М.: Финансы и статистика, 1983.
Абрамович М., Стиган И. Справочник по специальным функциям. М.: Наука, 1979.
Агеев М.И., Алик В.П., Малюк Л.В., Марков Ю.И. Алгоритмы (51-100). М.: ВЦ АН СССР, 1966.
Агеев М.И., Алик В.П., Марков Ю.И. Библиотека алгоритмов 51б-100б. (Справочное пособие.). Bып. 2. М.: Сов. радио, 1976,
Алберг Дж., Нильсон Э., Уолш Дж. Теория сплайнов и ее приложения / Пер. с англ.: М.: Мир, 1972.
Ашкрофт Дж., Элдридж Р., Полсон Р. и др. Программирование на ФОРТРАНЕ 77 / Пер. с англ. Н.А.Геодакова, Д.П.
Матюшина. М.: Радио и связь, 1990.
Бахвалов Н.С. Численные методы (анализ, алгебра, обыкновенные дифференциальные уравнения). Т. 1. М.: Наука, 1973а.
Бахвалов Н.С. Численные методы. М.: Наука, 1973б.
Белашова А.А. Тестирование информации на стационарность в системе регистрации и обработки радиокосмических
данных в реальном масштабе времени // Исследование явлений в ионосфере и магнитосфере Земли. Владивосток: ДВО
АН СССР, 1990. С. 92 - 97.
Белашова А.А., Белашов В.Ю. Реализация алгоритма Кули - Тьюки вычисления БПФ в системе регистрации и обра-
ботки радиокосмофизических данных в реальном масштабе времени // Исследование явлений в ионосфере и магни-
тосфере Земли. Владивосток: ДВО АН СССР, 1990. С. 87 - 91.
Белашов В.Ю. О численных методах решения эволюционных уравнений типа уравнения Кадомцева-Петвиашвили:
Препринт ИКИР. Магадан, 1989. 21 с.
Белашов В.Ю. Численное исследование динамики неодномерных нелинейных волн в слабодиспергирующих средах:
Дис... канд. физ.-мат. наук. М.: ИЗМИРАН, 1991.
Белашов В.Ю. Специальные функции и алгоритмы их вычисления. М.: Магадан, 1997.
Белашов В.Ю. Уравнение КП и его обобщения. Теория, приложения. Магадан: СВКНИИ ДВО РАН, 1997.
Белецкий Я. Турбо Паскаль с графикой для персональных компьютеров / Пер. с польск. Д.И.Юренкова. М.: Ма-
шиностроение. 1991.
Беляков В.М., Кравцова Р.И., Раппопорт М.Г. Таблицы эллиптических интегралов. Т. 1, 2. М.: 1962.
Березин И.С., Жидков Н.П. Методы вычислений. Т. 2. М.: Физматгиз, 1962.
Библиотека алгоритмов 1б-50б: Справочное пособие. Вып. 1. М.: Советское радио, 1975.
Библиотека алгоритмов 151б-200б: Справочное пособие. М.: Радио и связь, 1981.
Брич З.С., Капилевич Д.В., Котик С.Ю. и др. Фортран ЕС ЭВМ. М.: Статистика, 1978.
Бронштейн И.Н., Семендяев К.А. Справочник по математике для инженеров и учащихся втузов / Пер. с нем. под ред.
Г.Гроше и В.Циглера. М.: Наука, 1981.
Вазов В.Р., Форсайт Дж. Разностные методы решения дифференциальных уравнений в частных производных / Пер. с
англ. М.: Мир, 1969.
Ван дер Варден Б.Л. Математическая статистика. М.: ИЛ, 1960.
Виноградов И.М. Основы теории чисел. М.: Гостехиздат, 1953.
Воробьева Г.Н., Данилова А.Н. Практикум по вычислительной математике. Изд. 2. М.: Высшая школа, 1990.
Гольцман Ф.М. Статистические методы интерпретации. М.: Наука, 1971.
Гринчишин Я.Т., Ефимов В.И., Ломакович А.Н. Алгоритмы и программы на Бейсике. М.: Просвещение, 1988.
Данциг Дж. Б. Линейное программирование, его применение и обобщения / Пер. с англ. М.: Прогресс, 1966.
Демидович В.М., Марон Б.В. Численные методы вычислительной математики. М.: Высшая школа, 1962
Дорот В.Л., Троицкий В.А., Шелест В.Д. Элементы вычислительной математики. Л.: Изд-во ЛПИ им. Калинина, 1977.
Дорот Л.И., Пименов И.А., Сацук В.В. Математическое обеспечение исследований геофизических закономерностей на
примере космических лучей. М.: Наука, 1978.
Дяконов В.П. Справочник по алгоритмам и программам на языке Бейсик. М.: Наука, 1981.
Иберла К. Факторный анализ. М.: Статистика, 1980.
Калиткин В.Г. Численные методы. М.: Наука, 1978.
Касаткин В.И. Лекции по методам вычислений. М.: Наука, 1978.
Кнут Д.Е. Искусство программирования. Т. 2. Получисленные алгоритмы / Пер. с англ. М.: Мир, 1977.
Корн Г., Корн Т. Справочник по математике для научных работников и инженеров / Пер. с англ. под ред. И.Г. Ара-
мановича. М.: Наука, 1978.
Курош А.Г. Курс высшей алгебры. М.: Физматгиз, 1962 .
158
Крылов В.И., Бобков В.В., Монастырный П.И. Вычислительные методы высшей математики. Т. 1. Минск: Вышэйшая
школа, 1972.
Лаврентьев М.А., Шабат Б.В. Методы теории функций комплексного переменного. М.: Физматгиз, 1965.
Люк Ю. Специальные функции и их аппроксимации / Пер. с англ. под ред. К.И.Бабенко. М.: Мир, 1980.
Мизрохи С.В. TURBO PASCAL и объектно-ориентированное программирование. М.: Фин. и стат., 1992.
Ортега Дж., Рейнболд В. Итерационные методы решения нелинейных уравнений со многими неизвестными / Пер. с
англ. М.: Мир, 1975.
Островский А.М. Решение уравнений и систем уравнений/Пер. с англ. М.: ИЛ, 1963.
Поляков Д.Б., Круглов И.Ю. Программирование в среде Турбо Паскаль (версия 5.5) / Справочно-методическое посо-
бие. М.: Изд-во МАИ, 1992.
Плис А.И., Сливина Н.А. Лабораторный практикум по высшей математике. М.: Высшая школа, 1983.
Самарский А.А., Гулин А.В. Численные методы: Учебное пособие для вузов. М.: Наука, 1989.
Справочник по специальным функциям / Под ред. М. Абрамовича, И.Стиган. М.: Наука, 1979.
Теория вероятностей и математическая статистика/Под. ред. Колемаева В.А.: Учебное пособие для эконом. спец. ву-
зов. М.: Высшая школа, 1992.
Троицкий В.А., Иванова И.М. Методы вычислительной математики. Ч. 1. Л.: Изд-во ЛПИ им. Калинина, 1975.
Уилкинсон Дж. Алгебраическая проблема собственных значений / Пер. с англ.М.: Наука, 1970.
Уилкинсон Дж. Райнш. Справочник алгоритмов на языке АЛГОЛ. Линейная алгебра / Пер. с англ. М.: Машино-
строение, 1976.
Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. М.: Физматгиз, 1963.
Фишер Р.А. Статистические методы для исследования. М.: Госстатиздат, 1958.
Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений / Пер. с англ. Х.Д. Ик-
рамова. М.: Мир, 1980.
Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений / Пер. с англ. М.: Мир, 1969.
Хемминг Р.В. Численные методы для научных работников и инженеров / Пер. с англ. М., Наука, 1972.
Численные методы. Учебник для техникумов. / Под ред. Данилина Н.И., Дубровской Н.С., Кваши О.П. и др. М.: Выс-
шая школа, 1976.
Янке Е., Эмде Ф., Леш Ф. Специальные функции. М.: Наука, 1968.
Bartlett M.S. The use of transformatioms. Biometrics, 3, 39, 1947.
Belashov V.Yu. The methods for numerical integration of nonlinear evolutional KP-class equations // XX Int. Conf. on
Phenomena in Ionized Gases, Italy, Pisa, July 8-12, 1991. Contributed papers. V. 6. P. 1241-1242.
Brent R.P. Algorithms for minimization without derivatives. Englewood Cliffs, N. J.: Prenctice-Hall. 1973.
Caffrey J. Communications of the ACM. Algorithms, 1962, N 6.
Clark Eva S. Communications of the ACM // Algorithms, 1963, N 3.
Cjjley J.W., Tukey J.W. An Algorithm for Machine Computation of Complex Fourier Series // Mathematics of Computation,
1965. V. 19. P. 297 - 301.
Dekker T.J. Finding a zero by means of successive linear interpolation, in B. Dejon and P. Henrici (eds.), Constructive aspects
of the fundamental thejrem of algebra. New York: Wiley-Interscoence. 1969.
Fisher J.R. Fortran Program for Fast Fourier Transform // Naval Research Laboratory Report. N 1074, Washington, D.C., 1970.
Floyd R.W. Communications of the ACM // Algorithms, 1962, N 6.
Georg R. Communications of the ACM // Algorithms, 1962, N 7.
Goerzel G. Mathematical Methods for Digital Computers / A.Ralston and H.S.Wilf, eds., 1961.
Giammo T.P. Communications of the ACM // Algorithms, 1962, N 2.
Greenstadt J. The determination of the characteristic roots of a matrix by the Jacobi method//Mathemetical methods for Digital
Computers/A.Ralston and H.S.Wilf, eds., 1961.
Gulinsky O.V., Belashov V.Yu., Dorman L.I. e.a. Analysis of the Small-scale Cosmic Ray Fluctuations Spectrum Inferred From
Ground-based Cosmic Ray Observation Data // Geofisica International, Mexico, D.F., Io, de enero de 1988. V. 27. N 1. P. 3 - 36.
Halstead M.H. Communications of the ACM // Algorithms, 1962, N 3.
Hennion P.E. Communications of the ACM // Algorithms, 1962, N 2.
Herndon J.R. Communications of the ACM // Algorithms, 1961, N 4.
Mifsud C.J. Communications of the ACM // Algorithms, 1961, N 11.
Nestor C.W. Communications of the ACM // Algorithms, 1961, N 7.
Peck J.E.L. Polynomial curve fitting with constraint // Soc. Indust. Appl. Math. Rev., 1961.
Perry C. Communications of the ACM // Algorithms, 1962, N 2.
Pfaltz J.L. Communications of the ACM // Algorithms, 1962, N 6.
Randell B., Broyden C.G. Communications of the ACM // Algorithms, 1962, N 1.
Relph A.P. Communications of the ACM // Algorithms, 1962, N 7.
Roek D.J. Communications of the ACM // Algorithms, 1962, N 5.
159
Romberg W. Vereinfachte numerische Integration. Det. Konglinge Norske Videnskaber Selskab Forhandlinger, 1955. N 28. P. 30-36.
Satterthwaite F.E. An approximate distribution of estimates of variance components. Biometrics. 2, 10, 1946.
Thacher H.C. Communications of the ACM // Algorithms, 1962, N 3.
Thacher H.C. Communications of the ACM // Algorithms, 1963, N 3.
Thacher H.C. Communications of the ACM // Algorithms, 1964, N 7.
Welch B.L. On linear combinations of several variances // J. Amer. Statist. Assoc., 51, 132, 1956.
Wilkinson J.H. Rounding errors in algebraic processes. Englewood Cliffs, N.J.:Prentice-Hall. 1967.
160