Актуальность проблемы. Существует широкий круг задач, решаемых на ЭВМв которых используется вычисление функций. При этом в практических приложениях, как правило, от методов вычисления функций требуется:
— высокое быстродействие,
— высокая точность их аппроксимации,
— вычислительная устойчивость,
— минимальные затраты объема оперативной памяти и вычислительных ресурсов,
— универсальность схемы вычисления.
Например, сложные многомерные задачи моделирования, которые необходимо решить в течение строго ограниченного времени, в алгоритмах решения содержат большие наборы разнообразных схем вычисления функций. Компьютерная реализация таких схем в целом и вычисления в них функций в частности требует обеспечения высокого быстродействия и высокой точности вычисления. Один из характерных примеров — задачи обработки метеонаблюдений и прогноза погоды. Область решения (пространственно-временной участок атмосферы) разбивается на отдельные пространственные ячейки, временные изменения в каждой ячейке представляются сложной функцией. Требуется точно и с наименьшими затратами времени для каждой ячейки вычислить изменение функции. Например, требование службы погоды Германии, состоит в том, чтобы расчет прогноза на день по локальной модели с заданным пространственным и временным разрешением занимал не более получаса машинного времени. Очевидно, чтобы прогнозировать погоду на большей территории требуется больший объем вычислений при тех же ограничениях по времени.
Эта ситуация усугубляется экстремальными изменениями погоды. Например, перемещение тайфуна над сравнительно небольшой территорией
Японии или Сахалина требует быстро и точно прогнозировать параметры движения тайфуна с целью принятия своевременных оперативных решений.
К категории задач, требующих большого объема оперативной памятиотносятся, задачи, гидрои аэродинамики^ по расчету течений в условиях сложной пространственно-временной структуры с учетом влияния различных физических и химических процессов. Такие задачи являются, как правило, многомерными, и расчет по каждому направлению хотя бы для нескольких точек требует оперативной памяти, превышающей 10 Гбайт. В квантовой, химии неэмпирические расчеты электронной структуры молекул требуют вычислительных затрат, пропорциональных N 4 или N5, где N условно характеризует число молекул. По этой причине многие молекулярные системы вынужденно исследуются в, упрощенном модельном представлении в виду нехватки вычислительных ресурсов. Программные модели данных процессов включают разнообразный набор функциональных зависимостей.
Время машинной реализациипоследних и затраты на их реализацию ресурсов 1 памяти существенно влияют на значения этих параметров для модели в целом. Это приводит к вопросу об оптимизации временной сложности вычисления функций при ограничениях на объем памяти и вычислительные ресурсы.
Сложная взаимозависимость аргументов и1 значений функций при длительности вычислений влечет накопление погрешности. Отсюда возникает требование устойчивости схемы вычисления каждой функции.
В аналогичных ситуациях в моделях гидрои аэродинамики, в задачах управления, в частности, летательными и космическими аппаратами имеет место особый аспект — аспект параллельных вычислений, где помимо естественных требований точности и быстродействия возникает специфическое требование синхронизации параллельных процессов вычисления функций.
Следует особо выделить аспект, вычисления тех функций, которые представляются посредством разложения в ряд Фурье. При каждом конкретном количестве отсчетов и конкретном числе элементов базиса как функцию можно рассматривать любую разновидность преобразования Фурье.
Аппаратом преобразований Фурье пользуются во многих областях фундаментальной и прикладной науки, техники. При этом возникают задачи, связанные со скоростью выполнения преобразований Фурье, с сокращением объема вычислений, с повышением точности и вычислительной устойчивости этих преобразований.
Отдельно следует рассматривать аспект, связанный с динамически изменяющимися параметрами выполнения данных преобразований. Сюда следует отнести переменное число элементов дискретного преобразования Фурье (ДПФ) и быстрого преобразования Фурье (БПФ), задание переменного шага отсчета, переменное количество точек отсчета-и, наконец, задание переменной точности вычисления.
Ряды Фурье и ДПФ с динамически изменяющимися параметрами используются, в частности, для представления многочастотной функции в задачах небесной механики, в задачах цифровой обработки изображений или многомерных сигналов, биометрических сигналов и др.
Во всех таких задачах неизменно сохраняется требование высокого быстродействия данных преобразований.
На этой основе актуален синтез эффективных параллельных алгоритмов преобразований Фурье с динамически изменяющимисяпараметрами при • сохранении требования вычислительной устойчивости и высокой точности этих преобразований.
Такую постановку вопроса ^ можно рассматривать как важную часть общей постановки вопроса о построении методов аппроксимации функций, обладающих одновременно высокой точностью, устойчивостью и быстродействием. В контексте преобразований Фурье проблема построения таких методов непосредственно относится к быстрому вычислению элементов базиса с динамически меняющимися отсчетами.
При этом как самостоятельная: может рассматриваться проблема параллельного вычисления всех элементов базиса тригонометрических и общего вида ортогональных преобразований с динамически изменяющимися отсчетами, а также проблема синхронизации соответственных параллельных процессов;
Вычисление функций, непосредственно представимых рядом Фурье, возникает при построении математических моделей объектов управления, при этом большое внимание уделяется определению их динамических и вероятностных характеристик /1 /. Такие модели широко используются при решении краевых задач для уравнений в частных производныхзадач механики деформируемого твердого тела, цифровой обработке сигналов и цифровой фильтрации / 2, 3/, моделирования оптических систем и синтезированных голограмм, распознавания образов и др. / 4 /,
Помимо отмеченных выше областей применения, цифровая обработка сигналов применяется в таких различных областях / 2 /, как акустика, звуковая локация, радиолокация, сейсмология, связь, системы передачи данных, ядерная техника и др. При этом выделяются характерные параметры сигнала, отделяются шумовые помехи, выполняется приведение сигнала к виду,, который наиболее удобен для пользователя.
Области применения цифровой обработки сигналов постоянно расширяются.
Ряды и преобразования Фурье, помимо отмеченного, непосредственно используются в теории электрических цепей, теории механических и колебательных систем, лазерной оптике и термодинамике. Нетрадиционные аспекты применения рассматриваемых преобразований освещены в / 5, 6 /.
Теория и практика исследований в > области цифровой обработки продолжает активно развиваться / 7 — 20 /.
Существующие схемы вычисления функций, включая схемы вычисления элементов тригонометрического и ортогонального базисов схем цифровой обработки, в рассматриваемых аспектах можно неформально классифицировать следующим образом / 21,22 /.
1. Многочленные приближения.
2. Разложение функций по невязкам.
3. Дробно-рациональные приближения.
4. Итеративные процессы.
5. Сегментная, в ластности, кусочно-полиномиальная аппроксимация.
6. Приближение тригонометрическими полиномами.
Выбор метода аппроксимации функций зависит от постановки задачи в конкретной предметной области.
Ниже приводится сравнительная характеристика наиболее часто применяемых методов. Для определенности эта характеристика дана для случая приближенного вычисления действительной функции одной действительной переменной на конечном промежутке.
Случай, когда вычисляется базис для комплексных ДПФ и БПФ, сводится к рассматриваемому отделением действительной и, мнимой части элементов базиса.
1. Многочленные приближения.
В случае функции одной переменной одним из источников многочленных приближений является разложение функции в степенной ряд Маклорена
Ъкхк (1) 0 или в ряд Тейлора
00 *=0 где х 0 — постоянная величина, являющаяся центром сходимости ряда.
Если функция /(.х) дифференцируема п +1 раз при хе (х0 —г, х0+ г), г =?0, то для всехсе (-с0 -г, х0 + г) имеет место формула Тейлора о к с остаточным членом
А о
Необходимым и достаточным условием сходимости ряда (2) к функции f (x), xg (x0-г, х0 +г), является выполнение условия lim Rn (х) =0. оо
При счете на ЭВМ используют не только сходящиеся, но и «полусходящиеся» ряды, которые сходятся при малом количестве членов, обеспечивая необходимую точность, и расходятся при увеличении числа членов. При суммировании большого числа членов степенного ряда накапливаются погрешности от входных данных и погрешности, получаемые за счет ограниченной разрядности представления чисел в ЭВМ.
Наиболее часто вычисление приближения производится по схеме Гор-нера, а также по схемам Винограда, Мотцкина — Белаги — Пана / 23 — 29 /.
Схема Горнера для вычисления значения полинома степени и в заданной точке в общем случае требует п операций сложения (вычитания) и п операций умножения. Эта схема широко используется на практике, однако в случае, когда требуется вычислять один и тот же полином многократно и время выполнения операции умножения значительно больше времени выполнения операции сложения, более экономно применять методы Мотцкина — Белаги — Пана.
С целью ускоренного вычисления функций активно развиваются параллельные вычисления полиномов.
Ускорение в этом случае достигается не за счет сокращения количества последовательных операций, а за счет параллельного выполнения взаимно независимых частей аппроксимирующего функцию алгоритма при условии готовности значений данных.
В качестве примера можно привести обобщенную схему Горнера для вычисления значения полинома (алгоритм Дорна / 30, 31/):
Рп (х) = ах" + а х" ~т ±¦ +а г, х" ^ + а х" «+ п / «п-т ип апАх» А + ап^тхпА~т +•¦• +а г., л х +ахп,+ где [а] - целая часть апе — целочисленный остаток от деления п — 1 на т.
Алгоритм заключается в синхронном вычислении всех строк этой записи, преобразованных к виду
После вычисления всех Рпк (х) т полученных значений суммируются по схеме сдваивания.
Временная сложность выполнения алгоритма на т процессорах в асимптотике составит
Т{т) = п т где *, гс — соответственно время бинарного умножения и сложения. В частности, при т=п,
Т (п) = 0(о%2п),
В дальнейшем эта схема будет рассмотрена детально (раздел 2.2).
Достаточно многочисленные примеры аналогичных схем можно найти в/28, 29,31−34/.
Кусочно-полиномиальные варианты многочленных приближений рассматриваются в/35−37/. Как правило, они не основаны на рядах Тейлора и для них не строятся параллельные схемы вычисления.
Кусочно-полиномиальные многочленные приближения отдельно рассматриваются ниже.
Аппроксимация функции одним полиномом на большом промежутке может повлечь для достижения заданной точности значительного увеличения степени полинома, что пропорционально степени повышает объем вычислений. При ограничении степени аппроксимирующего полинома увеличивается погрешность.
Отсюда возникает задача разработки метода аппроксимации функций на такой основе, которая при малой степени полинома могла бы обеспечивать требуемую точность аппроксимации.
2. Разложение функций по невязкам.
Пусть функция у = /(х) задана уравнением
F (x, y) = 0. (3)
В качестве невязки уравнения (3) можно рассмотреть / 21/ значение функции z0=F{x, y0), (4) получающееся при замене точного значения у на у0, которое является приближением функции у=/(х) на заданном отрезке [а, b. При этом необходимо выполнение условия lim z0 = 0.
У~*Уо
Один из способов получения разложения функций по невязкам состоит в"том, что из уравнения невязки (4) определяется' х0 =O (y0,z0), а из этого уравнения находится искомая функция /(х)=/(ф (у0,г0))• Для наиболее часто употребляемых элементарных функций допускается представление суперпозиции функций f (o (y0,z0)) в явном виде.
В качестве примера разложения функции в ряд невязок можно привести разложение функции у=
Положив
Х-в'' где у о — приближенное значение д> = 1п (х) для хе[а, б], получим
Разложив 1п —— в ряд Тейлора, получим
1-г
Если оставить т членов этого ряда, то абсолютная погрешность приближения оценивается из равенства / 21 / где Л0 — абсолютная погрешность начального приближения у0.
Разложения функций по невязкам имеют достаточно широкое распространение в качестве метода аппроксимации функций. Однако, необходимая точность вычисления функции достигается лишь при условии правильного вьлбора начального приближения, алгоритм нахождения которого может быть достаточно сложным и не обладает универсальностью.
Данный метод не может быть реализован по единой программе в общем случае.
Метод невязок не гарантирует вычисления функции с заданной точностью при заданном количестве операций (за заданное время).
Для данного метода в периодической литературе не предлагаются параллельные алгоритмы реализации.
Отсюда не представляется целесообразным использовать метод для вьшисления элементов базиса преобразований Фурье с динамически меняюд (-)
АГ
2л1н-1)(2т-1)' щимся количеством отсчетов.
3. Дробно-рациональные приближения.
Под дробно-рациональным приближением функции обычно понимается ее приближение вида / 21'/
0 /=0
Общее количество операций для достижения заданной точности при рациональном приближении обычно меньше, чем при многочленном, однако при использовании дробно-рациональных приближений появляется операция деления. Следует иметь в виду, что во многих ЭВМ само деление организуется как приближенное вычисление функции /{х)=х~ для которой требуется алгоритм, сопоставимый по числу операций с вычислением Як, (х) .
В тех случаях, когда скорость выполнения операции деления близка к скорости умножения, эффективность использования рациональной аппроксимации возрастает. В последовательных арифметических устройствах иногда применяют переход от дробно-рационального приближения к вычислению соответствующей цепной дроби. Общее количество операций при вычислении цепной дроби меньше, чем при вычислении рациональной дроби, образуемой по схеме подходящей дроби / 38 /.
Цепную или непрерывную дробь определяют как выражение, а Ь" а2
I ак где — к-е звено цепной дробиЬ0 — нулевое звеноа , — частные делителиК
Ь1 — частные знаменатели (/=1, 2,.).
Область и условия сходимости цепной дроби отличается от области — и условий сходимости степенного ряда при разложении одной и той же функции. Поэтому с помощью цепных дробей вычисляют значения1 тех функций, для которых разложение в степенной ряд сходится недостаточно быстро или даже расходится. Помимо того аппроксимация функций в виде цепных дробей используется как, источник получения рациональных приближений. Иногда цепная дробь используется как средство уменьшения количества операций при счете на ЭВМ. При определенных условиях использование аппарата цепных дробей способствует уменьшению накопления погрешностей округления / 39, 40 /. В частности, для. цепной дроби с единичными частными числителями и положительными частными-знаменателями относительная погрешность ее значения асимптотически (с точностью до бесконечно малых первого порядка) не превышает максимальной из относительных погрешностей' ее компонентов независимо от числа звеньев дроби.
Практическое использование цепных дробей ограничивается некоторыми их особенностями. Так, например, при вычислении цепных дробей в режиме с плавающей запятой погрешности округления могут накапливаться быстрее, чем при счете дробно-рациональной функции / 27 /.
Для приближения функции цепной: дробью — требуется выполнить ряд априорных расчетов искомой функции, на конкретной ЭВМ с целью оценки фактических' погрешностей и определения необходимого числа разрядов в машинном представлении числа (в отличие от степенного ряда цепная дробь не имеет общей формулы остаточного члена приближения).
Помимо отмеченных известных затруднений, цепная дробь сама по себе, непосредственно по построению, не допускает эквивалентной записи в параллельной форме. Отсюда вытекает существенное несоответствие тенденции распараллеливания' вычислений и несоответствие архитектуре программного обеспечения параллельных суперкомпьютеров.
Однако необходимо оговориться, что алгоритмическая структура цепной дроби адекватна архитектуре конвейерного типа.
В контексте темы диссертационной работы не просматривается возможность оптимизации временной сложности аппроксимации функций цепными и рациональными дробями на основе средств одной только информатики. Для этой цели требуются специальные математические приемы / 22, 25,
Отсюда проблематично использовать метод для параллельного вычисления элементов базиса преобразований Фурье с динамически меняющимися параметрами.
4. Итеративные процессы.
Примером итеративного процесса является метод «цифра за цифрой».
В алгоритмах вычисления функций, основанные на методах «цифра за цифрой», используются итеративные процессы, позволяющие последовательно определять цифровое значение / -го разряда af искомого значения функции /(х), заданной в позиционной системе счисления.
Большинство алгоритмов рассматриваемого вида разработано для двоичной системы счисления, хотя имеются алгоритмы для десятичной и произвольной систем счисления / 21 /.
Принцип построения алгоритмов «цифра за цифрой» удобно проиллюстрировать на примере.
Пусть требуется вычислить функцию у=log 2 х для х е[1,2). Значения функции, лежащие вне этого интервала, могут быть вычислены с помощью формул
При х е[1,2) значение функции у е (0,1).
Для функции ^=1о§- 2х последовательно вычисляются двоичные разряды результата ai (у =а, 2 ', ai = 0 или at =1) на основе следующих
27 — 29 /. п формул:
0, если * ] <2 и 1 =дг ], а1 =0 если х ] >2 и х1+1=2~1х ], /=1,2,.,", х0=*.
Процесс позволяет получать последовательно х1, х2,., хп и одновременно с этим цифры результата а1, а2,., ап.
Таким образом, данный метод состоит из последовательного по разрядам выполнения операций, которые включают в свой состав арифметику, логические операции и условные переходы по значениям сложных выражений отношения. Длительность работы алгоритма пропорциональна числу разрядов с достаточно большим значением коэффициента пропорции. Схема «цифра за цифрой» по этим причинам не соответствует архитектуре суперкомпьютеров, число разрядов мантиссыв которых достигает 256 и более цифр / 41 — 47 /. Трудности усугубляются тем, что в описаниях метода, как правило, не указывается зависимость точности, аппроксимации функции от диапазона изменения независимой переменной.
С другой стороны, методы типа «цифра за цифрой» успешно применяются в специализированных устройствах, где упрощается обработка текущего разряда / 48, 49/. Кроме того, очевидной является возможность аппаратной конвейеризации метода в общем случае.
Очевидна трудность использования методов типа «цифра за цифрой» в условиях динамически меняющегося диапазона изменения аргумента функции. В частности, это можно отнести к переменному количеству элементов базиса ДПФ и БПФ с переменным числом отсчетов и переменным, шагом дискретизации.
5. Сегментная аппроксимация.
Сегментная аппроксимация включает в себя методы кусочной аппроксимации, основанные на разбиении исходного промежутка задания функции на подынтервалы /217. Широко применяются методы сплайновой интерполяции.
Пусть отрезока, b] разбит uaN равных. частичных отрезков [хп х1+, j, где х)=a+ih, /=0,l,., iV-l, xN=b, h=(b-a)/N.
Функцию Sm (x) называют сплайном степени т дефекта к если S’m (x)~ полином степени т на частичном отрезке и
SH{x)eCKk[a, b].
На практике наиболее широкое распространение получили сплайны третьей степени, имеющие на [а, b] непрерывную, по крайней мере, первую производную / 50,51 /.
Однако при условии высокой точности резко возрастает количество частичных отрезков, и, как следствие, время вычисления.
Следует заметить, что с возрастанием степени сплайна возрастает число уравнений. системы, по которым согласуются значения производных, поэтому на практике ограничиваются сплайнами невысокой степени.
Неизбежным следствием такого построения является потеря математических характеристик аппроксимируемой функции, связанных со значениями — производных высшего порядка.
Сегментный метод наиболее близок к методу, конструируемому в диссертационной работе. Главное отличие предложенного метода от известных будет заключаться в том, что его конструкция основана на обобщенном алгоритме, включающем произвольную степень аппроксимирующего полиномааппроксимацию произвольной функции на произвольном промежутке при произвольном задании границы абсолютной погрешности приближения.
Предложенный метод главным образом ориентирован на параллельные вычисления, хотя обладает существенно высоким быстродействием при последовательной реализации.
В контексте связи сегментной аппроксимации с ДПФ и БПФ можно отметить риск потери гармонических свойств аппроксимируемых элементов базиса. По крайней мере, это очевидно при сплайновой аппроксимации. В более общем случае затруднительно выполнять динамическую оптимизацию временной сложности метода.
6. Приближение тригонометрическими полиномами.
Рассматриваемый способ приближения функций наиболее близок к теме диссертационного исследования — непосредственные примеры такой аппроксимации представляют собой ряды Фурье, ДПФ, БПФ.
Приближения тригонометрическими полиномами используются, как правило, для характеристики качеств аппроксимируемой функции, выражаемых периодическими свойствами / 52 -54 /. Это делается с тем, чтобы получить по возможности адекватное представление о физическом процессе, который выражается посредством аппроксимируемой функции.
В качестве одного из источников приближения функций тригонометрическими полиномами используется интерполяция на основе полиномов Чебышева.
Полиномы Чебышева I и II рода традиционно / 55, 56 / обозначаются Т’п (jc) и Un (x). При этом для цели аппроксимации функций тригонометрическими полиномами используются следующие соотношения:
Тп (х) = cos{п в), х = cos в, rJsin0) = (-l)icos (2/!0),. (5)
T2n+l (sin в) = (-1)" sin ((2 п + 1)0) i (6)
С/п (х) = cosec (0) sin ((и +jc = cos0, sjny)=(-lNc!((2^j (?) cos0
8) cos 0
На этой основе конструируется полином, интерполирующий функцию /(х), следующего вида т
М=1 ЬкТк (х). (9)
— 0
Чаще встречаются разложения по ортогональным полиномам / 57 / вида
Рп Тх (х)+с2 Т2 (х)+.+сп Тп (.X),
С0=- {/(соэ в) <19, ск = -~ {/(соэ 9) соб к9с19, (к> 1), Л о л о
10) где Тк (х) — алгебраические полиномы. Такие приближения используются в качестве наилучших среднеквадратичных приближений. С другой стороны приближения (5) — (9) используются как среднеквадратичные приближения функций непосредственно тригонометрическими полиномами, в частности, для приближения функций заданных таблицей по методу наименьших квадратов.
В последнем случае тригонометрические полиномы образуют ряд Фурье / 57 /.
Обе формы интерполяционных полиномов тесно связаны между собой, допуская преобразование одной формы в другую. Эти преобразования основаны на известных рекуррентных зависимостях / 55, 56 /
Тт^х)=2хТт (х)-Ттх (х) | Г0(х)=1, Тх (х) = х)
С/0(*) = 1, их{х) = 2×1' которые существенно используются в диссертационной работе с целью преобразования не только тригонометрического полинома, но и отрезка ряда Фурье общего вида, а также ДПФ к виду алгебраического полинома по степеням одной независимой переменной.
В качестве другого источника приближения функции тригонометрическими полиномами используется непосредственно разложение функции f (x) в ряд Фурье:
M=^ + ?kcos (m-) + 6"sin (ra:)), (13)
2 л=1 где a0, an, bn, (п = 1,2,.) — постоянные числовые коэффициенты. Из (13) получается приближение, а м
М* ~ + zk cos (rar) + Ьп sin (га:)). (14)
Z и=1
В приложениях наряду с (13) широко используются интегральное преобразование Фурье / 1 / }/(*)"?-, вя (15) 00 и ДПФ (16) и = 0 а также БПФ.
Известная конструкция последнего заключается в следующем / 58 /. Предположим, что нужно вычислить ДПФ {Х{к)}, к=0,., N — последовательности {*(«)}, п=0,., N-1, где N четно. Последовательность (х (и)} можно разделить на две подпоследовательности (g (w)} и {h (n)} следующим образом: g (n)=x (2n), h{n) = x{2n + i), п=0,., IV/2−1. (17)
ДПФ двух последовательностей {g (я)} и {h (n)} можно записать в виде
N12−1
G (k)=? g{n)e'J ", (18) л=0
N12-}.. j
Н (к)= X Ь{п)е~ «, (19) и=0 тогда как (х (А:)} можно выразить через эти четную и нечетную составляющие следующим образом:
N/2−1 4япк
X{k)=? g (n)e'J «+ h (n)e J
2лк (2п+) n=0 или
N/2-l
4япк
Аяпк. 2xк yy/2—1
Z, k=0,., N-l. (20)
Из сравнения (20) с (18) и (19) видно, что 2як N
X (k)=G (k) + e N Н (к), 0<�к<�—-1, 2
Хк + N
2 як N G{k)-e~ N Н (к), 0<�к< —1.
21)
22)
Следовательно, ДПФ последовательности х{п) из N выборок можно получить с помощью ДПФ двух соответствующих подпоследовательностей длиной N/2 выборок g (n) и h{n), используя N дополнительных комплексных умножений. ох4(р)
Рис. 1. х<�о) а
Рис. 2.
На рис. 1 представлен граф для одного отсчета 4-точечного БПФ. Формульная запись в этом случае выглядит следующим образом ХМ = [х (0)+х (2)?:]+?: [х (1)+х (3)^4°].
На рис. 1 символ «О» обозначает множитель .
На рис. 2 представлен полный граф 4-точечного БПФ, формульная запись которого записывается в виде
X:4(*) = [х{0)+х{2)1У2к]+ И? [х{)+х (з)1Г2к ], к = 0,1,2,3.
Время, необходимое для вычисления ДПФ, пропорционально числу произведений, и при непосредственной реализации это число пропорционально Л2. Во втором случае, т. е. при*использовании (21) и (22), время вычислений пропорционально 2 (N/2)2 + Ы= (л2 /2) + ЫыИ1 /2 при больших N. Отметим, что, если число N12 снова четно, можно повторить процедуру, и если N является степенью числа 2, ее можно повторять до тех пор, пока не будет получено преобразование одной точки, которое, очевидно, совпадает с самой точкой. Отсюда полное число комплексных умножений, необходимых для выполнения ДПФ, пропорционально
Сохраняет актуальность проблема сокращения времени вычисления ряда Фурье, БПФ и ДПФ. Такая проблема имеет место как в случае последовательных, так и параллельных вычислений для компьютеров с различной архитектурой /59−63 /.
В периодической литературе дляч всех представленных приближений функции тригонометрическими полиномами, включая (10), (13) — (16), а также (21) — (22), как правило, не рассматривается перевод преобразований Фурье на основе (5) — (8) в полиномиальную форму.
Иными словами, остается не изученной возможность перевода частичной суммы ряда Фурье, ДПФ и БПФ в форму алгебраического полинома по степеням одной переменнойна основе соотношений Чебышева (5) — (12). Преимущество такого перевода заключалось бы: в том, что все вычислительные схемы частичной суммы ряда и преобразований Фурье можно было бы перевести в хорошо изученную область аппроксимации функций полиномами вида (1). В частности, сюдаможно было применить сегментную аппроксимацию / 21, 36 / и хорошо разработанные / 23, 28, 29, 32 — 34 / параллельные схемы вычисления значений полиномов.
Более того, рассматривая частичную сумму ряда Фурье, ДПФ и БПФ ¦ как функцию, можно ставить вопрос о свертке этих преобразований в целом посредствомкусочно-полиномиальной аппроксимации в форму полинома фиксировано малой степени.
На основании изложенного актуальной является задача построения обобщенного метода вычисления элементарных функций и их суперпозиций, в схему которого включались бы преобразования Фурье, и который отличался бы высокой вычислительной устойчивостью и быстродействием. Более точно, речь идет о вычислении произвольной функции одной действительной переменной с априори заданной границей: абсолютной погрешности на произвольном промежутке. При, этом целесообразна постановка вопроса об оптимизации временной сложности вычисления функций рассматриваемого вида при заданных ограничений на объем памяти и вычислительные ресурсы.
Применительно к ДПФ и БПФ метод должен сохранять точностные ш сложностные характеристики при параллельном вычислении всех элементов базиса в случае динамически меняющихся параметров.
Цель диссертационной работы состоит в разработке иисследовании эффективных методов вычисления элементарных функций, их суперпозиций, а также функций одной действительной переменной более общего вида. Сюда включаются тригонометрические полиномы, используемые в качестве базиса ряда Фурье и преобразований Фурье, в. частности, ДПФ и БПФ. От конструируемых методов требуется, чтобы функции рассматриваемого вида могли быть вычислены с априори заданной границей абсолютной-погрешности на произвольном промежутке. При этом должен быть синтезирован: и программно реализован алгоритм оптимизации временной сложности вычисления функций рассматриваемого вида при условии заданных ограничений на объем памяти и вычислительные ресурсы. Методы должны отличаться, регулярностью, единством конструкции, вычислительной устойчивостью, обладать параллелизмом и простотой синхронизации.
Для достижения поставленной цели в диссертационной работе решаются следующие задачи:
1) выполнить синтез и анализ метода и построить на его основе алгоритмы устойчивого вычисления функций однойдействительной переменной с априори заданной границей абсолютной погрешности на произвольном промежутке с оптимизацией временной сложности. при заданных ограничениях на объем памяти и вычислительные ресурсы;
2) в качестве частных случаев общей схемы должны получаться, с одной стороны, классические аппроксимации на основе интерполяционных полиномов Лагранжа, Чебышева и тейлоровских разложений, с другой стороны, — схемы кусочно-полиномиальной аппроксимации, сегментной фрагментации, а также известные параллельные схемы вычисления полиномов;
3) сконструировать и программно реализовать алгоритм оптимизации временной сложности1 вычисления произвольных функций рассматриваемого вида на произвольном промежутке;
4) разработать схему параллельного вычисления сложной суперпозиции элементарных функций, которая позволяет конечную последовательность ярусов ярусно-параллельной формы вычисления суперпозиции заменить одним единственным ярусом без изменения точности аппроксимациикак результат должна достигаться естественная синхронизация параллельных процессов вычисления функций данного вида;
5) выполнить перенос метода на случай функций, аппроксимируемых тригонометрическими полиномами, включая частные суммы ряда Фурье, ДПФ, БПФ и преобразования на основе ортогональных полиномовисследовать специфику устойчивости, и параллелизма выполнения преобразований Фурье данным методом;
6) разработать алгоритмы параллельного вычисления всех элементов тригонометрического базиса преобразований Фурье и элементов базиса ортогональных полиномовсинтезировать параллельные алгоритмы суммирования ряда Фурье, ДПФ, БПФ, которые позволяют совмещать выполнение: этих преобразований с одновременным вычислениемвсех элементов тригонометрического базиса и всех коэффициентов разложений в данном базисе- :
7) дать формальное описание предложенных алгоритмов вычисления функ-• ций и разработать программные модели с целью отладки, проверки работоспособностиоценок временной сложности и вычислительной устойчивости сконструированных методов вычисления функций;
8) провести численный эксперимент по оценке устойчивости и корректности алгоритма оптимизации временной сложности схем вычисления функций.
Методы исследования опираются на использование теоретических основ информатики, численного анализатеории сложности, прикладной информатики и алгоритмов цифровой обработки сигналов.
Научная новизна диссертационной работы г заключается в построении обобщенного метода* приближенного— вычисления элементарных, функцийих суперпозиций, а также функций одной действительной переменной более общего вида, включая тригонометрические полиномы, используемые в качестве элементов базиса преобразований Фурье, в том-числе ДПФ и БПФ. Метод обладает параллелизмом, вычислительной устойчивостью и в широком диапазоне точности приближения функций достигает единичной оценки временной сложности их вычисления: Синтезирован алгоритм оптимизации временной сложностивычисления, функций рассматриваемого вида при условии заданных ограничений на объем памяти и вычислительные ресурсы.
Конкретно, научная новизна результатов может быть охарактеризована следующим образом:
1) предложен метод и сконструированы алгоритмы устойчивого вычисления < функций одной действительной переменной и их суперпозиций с априори заданной границей абсолютной-погрешности на произвольном промежутке с оптимизацией временной сложности при заданных ограничениях на объем памяти и вычислительные ресурсы;
2) предложенные методы исхемы характеризуются регулярностью, единством конструкции, эффективно распараллеливаются, обладаютестественной синхронизацией и вычислительной устойчивостьюсочетание двух последних качеств с оптимизированной временной сложностью и быстродействием в целом отличают данные методы от известных;
3) предложена алгоритмическая схема параллельного вычисления сложной суперпозиции элементарных функций, которая позволяет конечную последовательность ярусов ярусно-параллельной формы вычисления суперпозиции заменить одним единственным ярусом без изменения точности аппроксимациисущественно при этом, что ярус произвольно заданных функций с готовыми значениями аргументовприобретает естественную синхронизацию по шагам схемы Горнера вычисления значения аппроксимирующего такие функции полинома;
4) разработаны параллельные схемы суммирования ряда Фурье, ДПФ и БПФ, которые формально достигают логарифмических оценок временной сложности при совмещении их выполнения с параллельным вычислением всех элементов-тригонометрического базиса, а также коэффициентов^ данных тригонометрических разложенийтакое совмещение отличает схемы от известных и позволяет выполнять рассматриваемые преобразования при-динамически меняющемся количестве отсчетов и динамически меняющихся коэффициентах разложенийотличительным качеством полученных схем является их инвариантность относительно количества: элементов базиса и относительно выбора шага дискретизации преобразований Фурьев частности, шаг дискретизации может быть переменным;
5) разработанные схемы преобразований^ Фурье базируются на переводе этих преобразований в форму полиномачто отличает эти схемы от известных по построению ипозволяет применить. для выполнения данных преобразований методы параллельного вычисления полиномов, а также методы кусочно-полиномиальной аппроксимации- 6) разработанные параллельные схемы преобразований Фурье переносятся на случай разложения по ортогональным полиномам с сохранением отли-. чительных динамических характеристик.
Отличительной особенностью предложенной обобщенной схемы от известных схем приближенного вычисления функций является то, что оптимизация временной сложности достигается алгоритмическими и программнымисредствами, в то время как в известных схемах такая оптимизация, как правило, достигается средствами математического анализа.
Основные положения, выносимые на защиту:
1) обобщенная схема устойчивого вычисления функций одной действительной переменной и их суперпозиций с априори заданной границей абсо лютной погрешностина произвольном промежутке с оптимизацией временной сложности при заданных ограничениях на объем памяти и вычислительные ресурсы;
2) алгоритмическая схема параллельного вычисления сложной суперпозиции элементарных функций, которая позволяет конечную последовательность ^ ярусов ярусно-параллельной формы вычисления? суперпозиции заменить единственным ярусом без изменения точности аппроксимации;
3) параллельные алгоритмы приближенного вычисления функцийаппроксимируемых тригонометрическими полиномамивключая частные суммы ряда Фурье на основе перевода этих сумм в форму алгебраического полинома;
4) алгоритмы параллельного вычисления ДПФ и БПФ, совмещенные с параллельным вычислением коэффициентов и всех элементов тригонометрического базиса в условиях динамическименяющихся параметров, включая меняющееся число отсчетов и переменный шаг дискретизации;
5) схема, согласно которой при условии дополнительного времени на априорный перевод ДПФ в форму алгебраического полинома дальнейшее вычисление Nточечного ДПФ может выполняться г параллельно на N процессорах за время 0(1).
Практическая ценность диссертационного исследования заключается в прикладном характере предложенных методов и алгоритмов. В частности, методы кусочно-полиномиальной аппроксимации могут составлять библиотеку стандартных и встроенных компьютерных программ устойчивого вычисления функций с единичной оценкой времени. Эти методы пригодны для. бортовых вычислителей, их целесообразно применять для синхронизации параллельных процессов вычисления функцийвместе с тем их можно использовать в персональных компьютерах со стандартной: архитектурой. Практически ценны качества минимизации времени вычислений при заданных ограничениях на объем памяти и вычислительные ресурсы, регулярность и общность предложенных схем. Важной для практики цифровой фильтрации. является применимость предложенных методов для параллельного вычислениявсех элементов базиса ортогональных преобразований, включая ДПФ и БПФ. Практическую направленность имеют представленные в диссертации методыпараллельного выполнения ДПФ за логарифмическое число шагов при переменном шаге дискретизации, переменном количестве отсчетов и переменном* числе элементов базиса.
Внедрение и использование результатов работы. Полученные в работе результаты использованы в госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания», код ВНТИЦ 02 0318 206 0355, регистрационный номер 01.2.00 106 436- при разработке изделия «Заря-СК» на ФГУП «Таганрогский завод «Прибой" — в учебном процессе кафедры информационных систем и технологий управления Таганрогского государственного педагогического института, что подтверждено соответствующими актами1 об использовании, приведенными в приложении к диссертационной работе.
Апробация работы. Основные результаты работы докладывались на:
— Всероссийской научно-технической конференции с международным участием «Компьютерные технологии в инженерной и управленческой деятельности» (Таганрог, 1999 г.);
— 6-й Международной конференции «Математические модели физических процессов и их свойства» (Таганрог, 2000 г.);
— международной научно-практической конференции «Проблемы образования студентов гуманитарных вузов в свете развития современных информационных технологий» (Таганрог, 2001 г.);
— Международной научно-технической конференции «Интеллектуальные САПР» (Таганрог, 2002 г.);
— научно-технических конференциях профессорско-преподавательского состава и аспирантов ТГПИ (Таганрог, 2000 — 2003 гг.);
— семинаре «Теоретическая и прикладная информатика» кафедры информатики ТГПИ (Таганрог, 2004 г.).
Публикации. По материалам работы опубликовано 8 печатных работ, включая монографию, с общим объемом 14 печатных листов.
Структура и объем работы. Диссертационная работа состоит из введения, 3 глав основного раздела, заключения, списка литературы и 4 приложений. Основное содержание работы изложено на 149 страницах, включая 23 таблицы, 6 рисунков и список литературы из 85 наименований.
Основные результаты диссертационной работы заключаются в следующем.
1. Разработаны обобщенные алгоритмы устойчивого вычисления функций одной действительной переменной и их суперпозиций с априори заданной границей абсолютной погрешности на произвольном промежутке. В основе предложенных алгоритмов лежит кусочно-полиномиальная аппроксимация функций рассматриваемого вида. При этом аппроксимация построена таким образом, что временная сложность вычисления функций минимизируется для любой наперед заданной точности приближения.
2. Обобщенный алгоритм включает аппроксимации на основе интерполяционных полиномов Лагранжа, Чебышева и тейлоровских разложений, а также схемы кусочно-полиномиальной аппроксимации, сегментной фрагментации. Каждая из данных разновидностей полиномиальной аппроксимации преобразуется в форму параллельного алгоритма с логарифмической оценкой временной сложности.
3. Сконструирован и программно реализован алгоритм оптимизации временной сложности вычисления произвольных функций рассматриваемого вида на произвольном промежутке. Оптимизация временной сложности достигается на выходе алгоритма, определяющего минимальное значение времени при условии заданных ограничений на объем памяти и вычислительные ресурсы. При этом в широком диапазоне точности достигается оценка^ временной сложности приближенного вычисления функций порядка 0(1).
4. Представлена алгоритмическая схема параллельного вычисления сложной суперпозиции элементарных функций, которая позволяет конечную последовательность ярусов ярусно-параллельной формы вычисления суперпозиции заменить одним единственным ярусом без изменения точности аппроксимации. В результате достигается естественная синхронизация параллельных процессов вычисления функций данного вида.
5. Разработаны схемы параллельного вычисления функций, аппроксимируемых тригонометрическими полиномами. Данные схемы включают устойчивое параллельное вычисление тригонометрического полинома произвольной степени с единичной оценкой временной сложности в том случае, если аппроксимируемая функция является часто повторяющейся.
6. На основе предложенных схем аппроксимации функций разработаны алгоритмы параллельного вычисления всех элементов тригонометрического базиса преобразований Фурье и элементов базиса ортогональных полиномов.
7. Синтезированы параллельные алгоритмы суммирования ряда Фурье, ДПФ,! БПФ, которые позволяют достигать логарифмических оценок временной сложности при совмещении выполнения этих преобразований с: одновременным, вычислением всех элементов тригонометрического базиса и всех коэффициентов разложений в данном базисе.
8. Предложенные алгоритмы параллельныхпреобразований Фурье обобщаются на случай разложения по 1 произвольным ортогональным полиномам, в общем случае не зависят от временного интервала снятия отсчетов, инвариантны относительно количества отсчетов и числа членов разложения.
9. Разработанные алгоритмы параллельного вычисления функций, включая элементы тригонометрического базиса, по построению обеспечивают вычислительную устойчивость. Результаты численного эксперимента, представленные в диссертационной работе, иллюстрируют это свойство алгоритмов и подтверждают их математическую корректность.
Научная новизна результатов диссертационной работы заключается в следующем.
1. Предложенная оптимизация временной сложности кусочно-полиномиальных схем приближенного вычисления функцийотличается от известных тем, что достигается алгоритмическими средствами информатики, в то время как известные схемы оптимизации, как правило, используют средства математического анализа.
2. Предложенные методы и схемы характеризуются регулярностью, единством конструкции, эффективно распараллеливаются, обладают естественной синхронизацией и вычислительной устойчивостьюсочетание двух последних качеств с оптимизированной временной сложностью и быстродействием в целом отличают данные методы от известных.
3. Разработанные параллельные схемы суммирования ряда Фурье, ДПФ и БПФ формально достигают логарифмических оценок временной сложности в условиях совмещения их выполнения с параллельным вычислением всех элементов тригонометрического базиса, а также коэффициентов данных тригонометрических разложений. Такое совмещение отличает схемы от известных и позволяет выполнять рассматриваемые преобразования при динамически, меняющемся количестве отсчетов и динамическименяющихся коэффициентах разложений. Отличительной чертой представленных схем является их инвариантность относительно количества элементов базиса и относительно выбора шага дискретизации преобразований Фурье. В частности, шаг дискретизации может быть переменным.
4. Представленные схемы преобразований Фурье базируются на переводе этих преобразований в форму полинома, что отличает эти схемы от известных по построению и позволяет применить для выполнения данных преобразований методы параллельного вычисления полиномов, а также методы кусочно-полиномиальной аппроксимации.
Практическая ценность диссертационного исследования заключается в прикладном* характере1 предложенных методов и алгоритмов. В частности, методы кусочно-полиномиальной аппроксимации могут составлять библиотеку стандартных и встроенных компьютерных программ устойчивого вычисления функций с единичной оценкой времени. Эти методы пригодны для бортовых вычислителей, их целесообразно применять для синхронизации параллельных процессов вычисления функций, вместе с тем их можно использовать в персональных компьютерах со стандартной архитектурой. Практически ценны качества минимизации времени вычислений при заданных ограничениях на объем памяти и вычислительные ресурсы, регулярность и общность предложенных схем. Важной для практики цифровой фильтрации является применимость предложенных методов для параллельного вычисления всех элементов базиса ортогональных преобразований, включая ДПФ и БПФ. Практическую направленность имеют представленные в диссертации методы параллельного выполнения ДПФ за логарифмическое число шагов при переменном шаге дискретизации, переменном количестве отсчетов и переменном числе элементов базиса.
Практическое использование результатов работы.
1. В НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания», код ВНТИЦ 02 0318 206 0355, регистрационный номер 01.2.00 106 436.
2. При разработке изделия «Заря-СК» на ФГУП «Таганрогский завод «Прибой».
3. В учебном процессе кафедры информационных систем и технологий управления Таганрогского государственного педагогического института.
ЗАКЛЮЧЕНИЕ
