Содержание к диссертации
Введение
ГЛАВА I. Алгоритмическое построение и оптимизация временной сложности обобщенной кусочно-полиномиальной схемы аппроксимации функций одной действительной переменной 30
1.1. Обобщенная схема кусочно-полиномиальной аппроксимации функций на основе полинома Лагранжа. 31
1.2. Алгоритм и программное моделирование минимизации временной -сложности обобщенной схемы кусочно-полиномиальной аппроксимации функций на основе полинома Лагранжа 41
1.3. Алгоритм кусочно-полиномиальной аппроксимации на основе ряда Тейлора в средах Turbo-Basic и Object Pascal в среде Delphi. 47
1.4. Обобщенная матричная схема параллельного восстановления коэффициентов полинома по его корням. 64
1.5. Представление неветвящихся вычислительных алгоритмов в форме параллельной программы с детерминированными значениями управляющих индексов 71
1.6. Выводы 78
ГЛАВА II. Алгоритмы кусочно-полиномиальной аппроксимации функций в применении к бпф на основе параллельного вычисления элементов базиса 80
2.1. Алгоритм аппроксимации суммы ряда Фурье алгебраическими полиномами. 81
2.2. Параллельные схемы аппроксимации суммы ряда Фурье алгебраическими полиномами 91
2.3. Схема параллельного суммирования.ряда Фурье, совмещенная с параллельным вычислением элементов базиса на основе полиномов Чебышева 98
2.4. Параллельные схемы вычисления коэффициентов ряда Фурье 101
2.5. Разновидность схемы параллельного суммирования ряда Фурье, совмещенной с вычислением элементов базиса 103
2.6. Схема последовательного суммирования ряда Фурье, совмещенная с параллельным вычислением элементов базиса 105
2.7. Схема параллельного выполнения дискретного преобразования Фурье, совмещенная с параллельным вычислением коэффициентов и элементов базиса 106
2.8. Совмещение схемы быстрого преобразования Фурье с параллельным вычислением элементов тригонометрического базиса 109
2.9. Обобщенные параллельные схемы суммирования разложений по ортогональным полиномам 113
2.10. Преобразование ДПФ в форму алгебраического полинома и в кусочно-полиномиальную форму с параллельной схемой выполнения... 115
2.11. Выводы 119
ГЛАВА 3. Численный эксперимент по обобщенной кусочно- полиномиальной аппроксимации функций и элементов базиса тригонометрических преобразований . 121
3.1. Специфика программной реализации разложения элементарных функций в ряд Фурье с использованием его преобразования к виду алгебраического полинома 121
3.2. Численный эксперимент по переводу частичной суммы ряда Фурье в форму алгебраического полинома 125
3.3. Устойчивость вычисления базисных функций преобразования Фурье на основе кусочно-полиномиальной аппроксимации 129
3.4. Вычисление коэффициентов кусочно-полиномиальной аппроксимации на основе схем, оптимизирующих временную сложность 134
3.5. Выводы. 136
Заключение 138
Литература. 142
Приложение 1 150
- Алгоритм и программное моделирование минимизации временной -сложности обобщенной схемы кусочно-полиномиальной аппроксимации функций на основе полинома Лагранжа
- Представление неветвящихся вычислительных алгоритмов в форме параллельной программы с детерминированными значениями управляющих индексов
- Схема параллельного выполнения дискретного преобразования Фурье, совмещенная с параллельным вычислением коэффициентов и элементов базиса
- Устойчивость вычисления базисных функций преобразования Фурье на основе кусочно-полиномиальной аппроксимации
Введение к работе
Актуальность проблемы. Существует широкий круг задач, решаемых на ЭВМ; в которых используется вычисление функций. При этом в практических приложениях, как правило, от методов вычисления функций требуется:
высокое быстродействие,
высокая точность их аппроксимации,
вычислительная устойчивость,
- минимальные затраты объема оперативной памяти и вычислительных ресурсов,
- универсальность схемы вычисления.
Например, сложные многомерные задачи моделирования, которые необходимо решить в течение строго ограниченного времени, в алгоритмах решения содержат большие наборы разнообразных схем вычисления функций. Компьютерная реализация таких схем в целом и вычисления в них функций в частности требует обеспечения высокого быстродействия и высокой точности вычисления. Один из характерных примеров - задачи обработки метеонаблюдений и прогноза погоды. Область решения (пространственно-временной участок атмосферы) разбивается на отдельные пространственные ячейки, временные изменения в каждой ячейке представляются сложной функцией. Требуется точно и с наименьшими затратами времени для каждой ячейки вычислить изменение функции. Например, требование службы погоды Германии, состоит в том, чтобы расчет прогноза на день по локальной модели с заданным пространственным и временным разрешением занимал не более получаса машинного времени. Очевидно, чтобы прогнозировать погоду на большей территории требуется больший объем вычислений при тех же ограничениях по времени.
Эта ситуация усугубляется экстремальными изменениями погоды. Например, перемещение тайфуна над сравнительно небольшой территорией
Японии или Сахалина требует быстро и точно прогнозировать параметры движения тайфуна с целью принятия своевременных оперативных решений.
К категории задач, требующих большого объема оперативной памяти; относятся, задачи, гидро- и аэродинамики і по расчету течений в условиях сложной пространственно-временной структуры с учетом влияния различных физических и химических процессов..Такие задачи являются, как правило, многомерными, и расчет по каждому направлению хотя бы для нескольких точек требует оперативной памяти, превышающей 10 Гбайт. В квантовой, химии неэмпирические расчеты электронной структуры молекул требуют вычислительных затрат, пропорциональных N 4 илиN5, где N условно характеризует число молекул. По этой причине многие молекулярные системы вынужденно исследуются в,упрощенном модельном представлении в виду нехватки вычислительных ресурсов. Программные модели данных процессов включают разнообразный набор функциональных зависимостей.
Время машинной реализации і последних и затраты на их реализацию ресурсов памяти существенно влияют на значения этих параметров для модели в целом. Это приводит к вопросу об оптимизации временной сложности вычисления функций при ограничениях на объем памяти и вычислительные ресурсы.
Сложная взаимозависимость аргументов и> значений функций при длительности вычислений влечет накопление погрешности. Отсюда возникает требование устойчивости схемы вычисления каждой функции.
В аналогичных ситуациях в моделях гидро- и аэродинамики, в задачах управления,, в частности, летательными и космическими аппаратами имеет место особый аспект - аспект параллельных вычислений, где помимо естественных требований точности и быстродействия возникает специфическое требование синхронизации параллельных процессов вычисления функций.
Следует особо выделить аспект, вычисления тех функций, которые представляются посредством разложения в ряд Фурье. При каждом конкрет-
ном количестве отсчетов и конкретном числе элементов базиса как функцию можно рассматривать любую разновидность преобразования Фурье.
Аппаратом преобразований Фурье пользуются во многих областях фундаментальной и прикладной науки, техники. При этом возникают задачи, связанные со скоростью выполнения преобразований Фурье, с сокращением объема вычислений, с повышением точности и вычислительной устойчивости этих преобразований.
Отдельно следует рассматривать аспект, связанный с динамически изменяющимися параметрами выполнения данных преобразований. Сюда следует отнести переменное число элементов дискретного преобразования Фурье (ДПФ) и быстрого преобразования Фурье (БПФ), задание переменного шага отсчета, переменное количество точек отсчета-и, наконец, задание переменной точности вычисления.
Ряды Фурье и ДПФ с динамически изменяющимися параметрами используются, в частности, для представления многочастотной функции в задачах небесной механики, в задачах цифровой обработки изображений или многомерных сигналов, биометрических сигналов и др.
Во всех таких задачах неизменно сохраняется требование высокого быстродействия данных преобразований.
На этой основе актуален синтез эффективных параллельных алгоритмов преобразований Фурье с динамически изменяющимися; параметрами при сохранении требования вычислительной устойчивости и высокой точности этих преобразований.
Такую постановку вопроса ^ можно рассматривать как важную часть общей постановки вопроса о построении методов аппроксимации функций, обладающих одновременно высокой точностью, устойчивостью и быстродействием. В контексте преобразований Фурье проблема построения таких методов непосредственно относится к быстрому вычислению элементов базиса с динамически меняющимися отсчетами.
При этом как самостоятельная: может рассматриваться проблема параллельного вычисления всех элементов базиса тригонометрических и общего вида ортогональных преобразований с динамически изменяющимися отсчетами, а также проблема синхронизации соответственных параллельных процессов;
Вычисление функций, непосредственно представимых рядом Фурье, возникает при построении математических моделей объектов управления, при этом большое внимание уделяется определению их динамических и вероятностных характеристик /1 /. Такие модели широко используются при решении краевых задач для уравнений в частных производных; задач механики деформируемого твердого тела, цифровой обработке сигналов и цифровой фильтрации / 2, 3/, моделирования оптических систем и синтезированных голограмм, распознавания образов и др. /47,
Помимо отмеченных выше областей применения, цифровая обработка сигналов применяется в таких различных областях / 2 /, как акустика, звуковая локация, радиолокация, сейсмология, связь, системы передачи данных, ядерная техника и др. При этом выделяются характерные параметры сигнала, отделяются шумовые помехи, выполняется приведение сигнала к виду,.который наиболее удобен для пользователя.
Области применения цифровой обработки сигналов постоянно расширяются.
Ряды и преобразования Фурье, помимо отмеченного, непосредственно используются в теории электрических цепей, теории механических и колебательных систем, лазерной оптике и термодинамике. Нетрадиционные аспекты применения рассматриваемых преобразований освещены в/ 5, 67.
Теория и практика исследований в > области цифровой обработки продолжает активно развиваться / 7 - 20 /.
Существующие схемы вычисления функций, включая схемы вычисления элементов тригонометрического и ортогонального базисов схем цифро-
вой обработки, в рассматриваемых аспектах можно неформально классифицировать следующим образом / 21,22 /.
Многочленные приближения.
Разложение функций по невязкам.
Дробно-рациональные приближения.
Итеративные процессы.
Сегментная, властности, кусочно-полиномиальная аппроксимация.
Приближение тригонометрическими полиномами.
Выбор метода аппроксимации функций зависит от постановки задачи в конкретной предметной области.
Ниже приводится сравнительная характеристика наиболее часто применяемых методов. Для определенности эта характеристика дана для случая приближенного вычисления действительной функции одной действительной переменной на конечном промежутке.
Случай, когда вычисляется базис для комплексных ДПФ и БПФ, сводится к рассматриваемому отделением действительной и,мнимой части элементов базиса.
1. Многочленные приближения.
В случае функции одной переменной одним из источников многочленных приближений является разложение функции в степенной ряд Маклорена
Ъкхк (1)
или в ряд Тейлора
^ак(х-х0)к,
где х 0 - постоянная величина, являющаяся центром сходимости ряда.
Если функция f(x) дифференцируема п + \ раз при хе(х0—г,х0 +г), г &0, то для всех хе(х0-г,х0 + г) имеет место формула Тейлора
/М=^(*-*У+*M" (2)
с остаточным членом
. * о
Необходимым и достаточным условием сходимости ряда (2) к функции f{x), хє(х0 -r,x0 +г), является выполнение условия lim Rn (х) = 0.
л-»оо
При счете на ЭВМ используют не только сходящиеся, но и «полусходящиеся» ряды, которые сходятся при малом количестве членов, обеспечивая необходимую точность, и расходятся при увеличении числа членов. При суммировании большого числа членов степенного ряда накапливаются погрешности от входных данных и погрешности, получаемые за счет ограниченной разрядности представления чисел в ЭВМ.
Наиболее часто вычисление приближения производится по схеме Гор-нера, а также по схемам Винограда, Мотцкина - Белаги - Пана / 23 — 29 /.
Схема Горнера для вычисления значения полинома степени и в заданной точке в общем случае требует п операций сложения (вычитания) и п операций умножения. Эта схема широко используется на практике, однако в случае, когда требуется вычислять один и тот же полином многократно и время выполнения операции умножения значительно больше времени выполнения операции сложения, более экономно применять методы Мотцкина - Белаги - Пана.
С целью ускоренного вычисления функций активно развиваются параллельные вычисления полиномов.
Ускорение в этом случае достигается не за счет сокращения количества последовательных операций, а за счет параллельного выполнения взаимно независимых частей аппроксимирующего функцию алгоритма при условии готовности значений данных.
В качестве примера можно привести обобщенную схему Горнера для вычисления значения полинома (алгоритм Дорна / 30, 31 /):
Рп(х) = ах" + а х"-т + — + я г , х^"* + а х"а +
п\ / п п-т пиП
+ апАхпА + ап_х_тхпА'т + + а г__,л jc L " J + a. jc"1 +
где [or ]- целая часть «; и, — целочисленный остаток от деления п — 1 на т.
Алгоритм заключается в синхронном вычислении всех строк этой записи, преобразованных к виду
Ш [-1-
г-о
После вычисления всех /^ (х) m полученных значений суммируются по схеме сдваивания.
Временная сложность выполнения алгоритма на т процессорах в асимптотике составит
п т
Т(т) = \
+ |>g2m| }{t,+te)+ty,
где t , tc - соответственно время бинарного умножения и сложения. В частности, при т=п,-
T(n) = 0(\og2n),
В дальнейшем эта схема будет рассмотрена детально (раздел 2.2).
Достаточно многочисленные примеры аналогичных схем можно найти в/28, 29, 31-34/.
Кусочно-полиномиальные варианты многочленных приближений рассматриваются в/35-37/. Как правило, они не основаны на рядах Тейлора и для них не строятся параллельные схемы вычисления.
Кусочно-полиномиальные многочленные приближения отдельно рассматриваются ниже.
Аппроксимация функции одним полиномом на большом промежутке может повлечь для достижения заданной точности значительного увеличения степени полинома, что пропорционально степени повышает объем вычислений. При ограничении степени аппроксимирующего полинома увеличивается погрешность.
Отсюда возникает задача разработки метода аппроксимации функций на такой основе, которая при малой степени полинома могла бы обеспечивать требуемую точность аппроксимации.
2. Разложение функций по невязкам.
Пусть функция у = f{x) задана уравнением
F(x,y) = 0. (3)
В качестве невязки уравнения (3) можно рассмотреть / 21/ значение функции
z0=F{x,y0), (4)-
получающееся при замене точного значения у на у0, которое является приближением функции у=/(х) на заданном отрезке [a, b]. При этом необходимо выполнение условия lim z0 = 0.
У-*Уо
Один из способов получения разложения функций по невязкам состоит в»том, что из уравнения невязки (4) определяется' д;0 = ф (у0, z0), а из этого уравнения находится искомая функция /(х)=/(ф(у0,г0))- Для наиболее часто употребляемых элементарных функций допускается представление суперпозиции функций /(ф(у0,г0)) в явном виде.
В качестве примера разложения функции в ряд невязок можно привести разложение функции у=\п(х).
Положив
х-еУо
z„=-
, У а
х+е-
где у 0 - приближенное значение у = \п(х) для хє[а, b], получим
l-z«
l+z0
х=еУа
Тогда
In x= In
ґеу. l + O
V l~zoJ
= y0.+ ln—- ^
l-zn
Разложив In в ряд Тейлора, получим
In х= ^0+2 2^7^^0^1 *=i 2 л:—1
Если оставить т членов этого ряда, то абсолютная погрешность приближения оценивается из равенства / 21 /
Л 2m_1
2^--)(2^-1)5 где А0 - абсолютная погрешность начального приближения у0.
Разложения функций по невязкам имеют достаточно широкое распространение в качестве метода аппроксимации функций. Однако, необходимая точность вычисления функции достигается лишь при условии правильного выбора начального приближения, алгоритм нахождения которого может быть достаточно сложным и не обладает универсальностью.
Данный метод не может быть реализован по единой программе в общем случае.
Метод невязок не гарантирует вычисления функции с заданной точностью при заданном количестве операций (за заданное время).
Для данного метода в периодической литературе не предлагаются параллельные алгоритмы реализации.
Отсюда не представляется целесообразным использовать метод для вычисления элементов базиса преобразований Фурье с динамически меняю-
щимся количеством отсчетов.
3. Дробно-рациональные приближения.
Под дробно-рациональным приближением функции обычно понимается ее приближение вида/217
Общее количество операций для достижения заданной точности при рациональном приближении обычно меньше, чем при многочленном, однако при использовании дробно-рациональных приближений появляется операция деления. Следует иметь в виду, что во многих ЭВМ само деление организуется как приближенное вычисление функции / (jc)=х "', для которой требуется алгоритм, сопоставимый по числу операций с вычислением Rk, (х).
В тех случаях, когда скорость выполнения операции деления близка к скорости умножения, эффективность использования рациональной аппроксимации возрастает. В последовательных арифметических устройствах иногда применяют переход от дробно-рационального приближения к вычислению соответствующей цепной дроби. Общее количество операций при вычислении цепной дроби меньше, чем при вычислении рациональной дроби, образуемой по схеме подходящей дроби / 38 /.
Цепную или непрерывную дробь определяют как выражение
bl+ 2-
і ак
Ьк+..
где -* - к-е звено цепной дроби; Ь0 — нулевое звено; а, - частные делители; К
Ъ t - частные знаменатели (/=1, 2,...).
Область и условия сходимости цепной дроби отличается от области - и
условий сходимости степенного ряда при разложении одной и той же
функции. Поэтому с помощью цепных дробей вычисляют значения' тех функций, для которых разложение в степенной ряд сходится недостаточно быстро или даже расходится. Помимо того аппроксимация функций в виде цепных дробей используется как, источник получения рациональных приближений. Иногда цепная дробь используется как средство уменьшения количества операций при счете на ЭВМ. При определенных условиях использование аппарата цепных дробей способствует уменьшению накопления погрешностей округления / 39, 40'/.. В частности, для. цепной дроби с единичными частными числителями и положительными частными-знаменателями относительная погрешность ее значения асимптотически (с точностью до бесконечно малых первого порядка) не превышает максимальной из относительных погрешностей' ее компонентов независимо от числа звеньев дроби.
Практическое использование цепных дробей ограничивается некоторыми их особенностями. Так, например, при вычислении цепных дробей в режиме с плавающей запятой погрешности округления могут накапливаться быстрее, чем при счете дробно-рациональной функции 1211.
Для приближения функции цепной: дробью - требуется выполнить ряд априорных расчетов искомой функции, на конкретной ЭВМ с целью оценки фактических* погрешностей и определения необходимого числа разрядов в машинном представлении числа (в отличие от степенного ряда цепная дробь не имеет общей формулы остаточного члена приближения).
Помимо отмеченных известных затруднений, цепная дробь сама по себе, непосредственно по построению, не допускает эквивалентной записи в параллельной форме. Отсюда вытекает существенное несоответствие тенденции распараллеливания' вычислений и несоответствие архитектуре программного обеспечения параллельных суперкомпьютеров..
Однако необходимо оговориться, что алгоритмическая структура цепной дроби адекватна архитектуре конвейерного типа.
В контексте темы диссертационной работы не просматривается возможность оптимизации временной сложности аппроксимации функций цепными и рациональными дробями на основе средств одной только информатики. Для этой цели требуются специальные математические приемы / 22, 25, 27 - 29 /.
Отсюда проблематично использовать метод для параллельного вычисления элементов базиса преобразований Фурье с динамически меняющимися параметрами.
4. Итеративные процессы.
Примером итеративного процесса является метод «цифра за цифрой».
В алгоритмах вычисления функций, основанные на методах «цифра за цифрой», используются итеративные процессы, позволяющие последовательно определять цифровое значение / -го разряда af искомого значения
функции /(х), заданной в позиционной системе счисления.
Большинство алгоритмов рассматриваемого вида разработано для двоичной системы счисления, хотя имеются алгоритмы для десятичной и произвольной систем счисления / 21 /.
Принцип построения алгоритмов «цифра за цифрой» удобно проиллюстрировать на примере.
Пусть требуется вычислить функцию у=log 2 X ДЛЯ X є [ 1,2).
Значения функции, лежащие вне этого интервала, могут быть вычислены с помощью формул
(2*х, xe(-co,l),k<0,
log,z=k+\og7x, z=< . r ч
При х є [1,2) значение функции у є (0,1).
Для функции y=\og2x последовательно вычисляются двоичные раз-
ряды результата аі (у = Уа,2~', а, = 0 или а, =1) на основе следующих
/=0
формул:
ai = 0, если х] <2 и xi+l =лгf ,
а1 = 0 если х] >2 и jc/+l=2_1jcf , /=1,2,...,/1, х0=*. Процесс позволяет получать последовательно х,,л:2,...,хп и одновременно с этим цифры результата aita2,...,an.
Таким образом, данный метод состоит из последовательного по разрядам выполнения операций, которые включают в свой состав арифметику, логические операции и условные переходы по значениям сложных выражений отношения. Длительность работы алгоритма пропорциональна числу разрядов с достаточно большим значением коэффициента пропорции. Схема «цифра за цифрой» по этим причинам не соответствует архитектуре суперкомпьютеров, число разрядов мантиссы- в которых достигает 256 и более цифр /41-47/. Трудности усугубляются тем, что в описаниях метода, как правило, не указывается зависимость точности,аппроксимации функции от диапазона изменения независимой переменной.
С другой стороны, методы типа «цифра за цифрой» успешно применяются в специализированных устройствах, где упрощается обработка текущего разряда /48, 49/. Кроме того, очевидной является возможность аппаратной конвейеризации метода в общем случае.
Очевидна трудность использования методов типа «цифра за цифрой» в условиях динамически меняющегося диапазона изменения аргумента функции. В частности, это можно отнести к переменному количеству элементов базиса ДПФ и БПФ с переменным числом отсчетов и переменным, шагом дискретизации.
5. Сегментная аппроксимация.
Сегментная аппроксимация включает в себя методы кусочной аппроксимации, основанные на разбиении исходного промежутка задания функции
на подынтервалы /217. Широко применяются методы сплайновой интерполяции.
Пусть отрезок [a, b] разбит HaJV равных частичных отрезков [хп xl+, j,
где xt=a+ih, i=0,\,—,N-l,xN=b, h=(b-a)/N.
Функцию Sm(x) называют сплайном степени т дефекта к, если S'm(x)~ полином степени т на частичном отрезке l'*j,*<+,J и SMeCM_k[a,b].
На практике наиболее широкое распространение получили сплайны третьей степени, имеющие на [а, Ь] непрерывную, по крайней мере, первую производную / 50,51 /.
Однако при условии высокой точности резко возрастает количество частичных отрезков, и, как следствие, время вычисления.
Следует заметить, что с возрастанием степени сплайна возрастает число уравнений. системы, по которым согласуются значения производных, поэтому на практике ограничиваются сплайнами невысокой степени.
Неизбежным следствием такого построения является потеря математических характеристик аппроксимируемой функции, связанных со значениями; производных высшего порядка.
Сегментный метод наиболее близок к методу, конструируемому в диссертационной работе. Главное отличие предложенного метода от известных будет заключаться в том, что его конструкция основана на обобщенном алгоритме, включающем произвольную степень аппроксимирующего полинома; аппроксимацию произвольной функции на произвольном промежутке при произвольном задании границы абсолютной погрешности приближения.
Предложенный метод главным образом ориентирован на параллельные вычисления, хотя обладает существенно высоким быстродействием при последовательной реализации.
В контексте связи сегментной аппроксимации с ДПФ и БПФ можно отметить риск потери гармонических свойств аппроксимируемых элементов
базиса. По крайней мере, это очевидно при сплайновой аппроксимации. В более общем случае затруднительно выполнять динамическую оптимизацию временной сложности метода.
6. Приближение тригонометрическими полиномами.
Рассматриваемый способ приближения функций наиболее близок к теме диссертационного исследования - непосредственные примеры такой аппроксимации представляют собой ряды Фурье, ДПФ, БПФ.
Приближения тригонометрическими полиномами используются, как правило, для характеристики качеств аппроксимируемой функции, выражаемых периодическими свойствами /52-54/. Это делается с тем, чтобы получить по возможности адекватное представление о физическом процессе, который выражается посредством аппроксимируемой функции.
В качестве одного из источников приближения функций тригонометрическими полиномами используется интерполяция на основе полиномов Чебышева.
Полиномы Чебышева I и II рода традиционно / 55, 56/ обозначаются Т'п(х) и Un(x). При этом для цели аппроксимации функций тригонометрическими полиномами используются следующие соотношения:
Тп (х) = cos(n в), х = cos в,
^(8^^)=(-1)^08(2^^), (5)
Г2„+1(8т^) = (-1)"8т((2« + 1)^, (6)
Un(x) = cosec(#) shi((h + l)#), JC = COS0 ,
U2^ne)J-^C<2" + l)e), (7).
COS0
cose' На этой основе конструируется полином, интерполирующий функцию /(х),
следующего вида
/M=Z«(x). (9)
/-0
Чаще встречаются разложения по ортогональным полиномам / 57 / вида
Рп (*)=*„ +сх Тх (х)+с2 Т2 {х)+...+сп Тп (х), co=-)f(cos0)de, ck = --)f(cose)coskede,(k>l),
Л о Л о
(10)
где Тк (х) — алгебраические полиномы. Такие приближения используются в
качестве наилучших среднеквадратичных приближений. С другой стороны приближения (5) — (9) используются как среднеквадратичные приближения функций непосредственно тригонометрическими полиномами, в частности, для приближения функций заданных таблицей по методу наименьших квадратов.
В последнем случае тригонометрические полиномы образуют ряд Фурье/57/.
Обе формы интерполяционных полиномов тесно связаны между собой, допуская преобразование одной формы в другую. Эти преобразования основаны на известных рекуррентных зависимостях / 55, 56 /
Tm^{x)=2xTm(x)-Tm_x(x) |
Т0(х)=\, Тх(х) = х У
Um+l(x)=2xUm{x)-Um_l{x) ^
U0(x) = \, Ux(x) = 2x J'
которые существенно используются в диссертационной работе с целью преобразования не только тригонометрического полинома, но и отрезка ряда Фурье общего вида, а также ДПФ к виду алгебраического полинома по степеням одной независимой переменной.
В качестве другого источника приближения функции тригонометрическими полиномами используется непосредственно разложение функции
f(x) в ряд Фурье:
Ах)=^ + %(ансо*(пх) + Ья&ш(пх)), (13)
где а0,ап,Ьп, (п = 1,2,...) - постоянные числовые коэффициенты. Из (13) получается приближение
а. м
/М* І + Zfe cos(rar) + Ьп sin (га:)). (14)
В приложениях наряду с (13) широко используются интегральное преобразование Фурье / 1 /
X{a>)=]f(x)e-,a" dx, (15)
— QO
и ДПФ
Х(к)=^х{пТ)е^"к , (16)
и = 0
а также БПФ.
Известная конструкция последнего заключается в следующем / 58 /.
Предположим, что нужно вычислить ДПФ {-A^(&)}, к=0,..., N-\ последовательности {*(«)}, п=0,..., N-1, где N четно. Последовательность (х(и)} можно разделить на две подпоследовательности {g(n)} и {h(n)}
следующим образом:
g(n)=x(2n), h(n) = x{2n + l), и=0,..., #/2-1. (17).
ДПФ двух последовательностей {g(n)} и {h(п)} можно записать в виде
N12-1 4"пк
G(k)= S g{n)e'J " , (18)
ЛГ/2-1 4»я*
#(*) = X А(и)е" " , (19)
тогда как (х(А:)} можно выразить через эти четную и нечетную составляющие следующим образом:
NI2-X
n=0
4япк
X(k) = И")*"' * + *M*
-j
2rrk(2n+\)\
Airnk
2"k N/2-l
Аяпк
X(k) = s(«)e~7 " + e~' " /г(и)е~У " ,k=0,...,N-l. (20) Из сравнения (20) с (18) и (19) видно, что
X{k)=G(k) + e'J N Н(к), 0
(21)
xik+N)=G(k)-e'J' *N Н(к), 0 <<--!.
(22)
Следовательно, ДПФ последовательности х(п) из N выборок можно получить с помощью ДПФ двух соответствующих подпоследовательностей длиной N/2 выборок g(n) и h(n), используя N дополнительных комплексных
умножений.
ОХ4(0)
Рис. 1.
Рис. 2. На рис. 1 представлен граф для одного отсчета 4-точечного БПФ. Формульная запись в этом случае выглядит следующим образом ХМ = [х(0М2)^4]+^4 [x(l)+x(3)w:].
На рис. 1 символ «О» обозначает множитель W.
На рис. 2 представлен полный граф 4-точечного БПФ, формульная запись которого записывается в виде
Xi(k) = [x{0)+x(2)W2k]+W,k[x{\)+x(3)W2k], = 0,1,2,3.
Время, необходимое для вычисления ДПФ, пропорционально числу
произведений, и при непосредственной реализации это число пропорцио
нально N2. Во втором случае, т. е. при*использовании (21) и (22), время вы
числении пропорционально + N&N2 /2 при больших
N. Отметим, что, если число N12 снова четно, можно повторить процедуру,
и если N является степенью числа2, ее можно повторять до тех пор, пока не будет получено преобразование одной точки, которое, очевидно, совпадает с самой точкой. Отсюда полное число комплексных умножений, необходимых для выполнения ДПФ, пропорционально (N12) log 2 N.
Сохраняет актуальность проблема сокращения времени вычисления ряда Фурье, БПФ и ДПФ. Такая проблема имеет место как в случае последовательных, так и параллельных вычислений для компьютеров с различной архитектурой /59-63 /.
В периодической литературе для і всех представленных приближений функции тригонометрическими полиномами, включая (10), (13) - (16), а также (21) - (22), как правило, не рассматривается перевод преобразований Фурье на основе (5) - (8) в полиномиальную форму.
Иными словами, остается не изученной возможность перевода частичной суммы ряда Фурье, ДПФ и БПФ в форму алгебраического полинома по степеням одной переменной; на основе соотношений Чебышева (5) - (12). Преимущество такого перевода заключалось бы в том, что все вычислительные схемы частичной суммы ряда и преобразований Фурье можно было бы перевести в хорошо изученную область аппроксимации функций полиномами вида (1). В частности, сюда- можно было применить сегментную аппрок-
симацию / 21, 36 / и хорошо разработанные / 23, 28, 29, 32 - 34 / параллельные схемы вычисления значений полиномов.
Более того, рассматривая частичную сумму ряда Фурье, ДПФ и БПФ как функцию, можно ставить вопрос о свертке этих преобразований в целом посредством; кусочно-полиномиальной аппроксимации в форму полинома фиксировано малой степени.
На основании изложенного актуальной является задача построения обобщенного метода вычисления элементарных функций и их суперпозиций, в схему которого включались бы преобразования Фурье, и который отличался бы высокой вычислительной устойчивостью и быстродействием. Более точно, речь идет о вычислении произвольной функции одной действительной переменной с априори заданной границей: абсолютной погрешности на произвольном промежутке. При,этом целесообразна постановка вопроса об оптимизации временной сложности вычисления функций рассматриваемого вида при заданных ограничений на объем памяти и вычислительные ресурсы.
Применительно к ДПФ и БПФ метод должен сохранять точностные ш сложностные характеристики при параллельном вычислении всех элементов базиса в случае динамически меняющихся параметров.
Цель диссертационной работы состоит в разработке и і исследовании эффективных методов вычисления элементарных функций, их суперпозиций, а также функций одной действительной переменной более общего вида. Сюда включаются тригонометрические полиномы, используемые в качестве базиса ряда Фурье и преобразований Фурье, властности, ДПФ и БПФ. От конструируемых методов требуется, чтобы функции рассматриваемого вида могли быть вычислены с априори заданной границей абсолютной.погрешности на произвольном промежутке. При этом должен быть синтезирован: и программно реализован алгоритм оптимизации временной сложности вычисления функций рассматриваемого вида при условии заданных ограничений на объем памяти и вычислительные ресурсы. Методы должны отличаться.ре-
гулярностью, единством конструкции, вычислительной устойчивостью, обладать параллелизмом и простотой синхронизации.
Для достижения поставленной цели в диссертационной работе решаются следующие задачи:
выполнить синтез и анализ метода и построить на его основе алгоритмы устойчивого вычисления функций одной;действительной переменной с априори заданной границей абсолютной погрешности на произвольном промежутке с оптимизацией временной сложности. при заданных ограничениях на объем памяти и вычислительные ресурсы;
в качестве частных случаев общей схемы должны получаться, с одной стороны, классические аппроксимации на основе интерполяционных полиномов Лагранжа, Чебышева и тейлоровских разложений, с другой стороны, - схемы кусочно-полиномиальной аппроксимации, сегментной фрагментации, а также известные параллельные схемы вычисления полиномов;
сконструировать и программно реализовать алгоритм оптимизации временной сложности1 вычисления произвольных функций рассматриваемого вида на произвольном промежутке;
разработать схему параллельного вычисления сложной суперпозиции элементарных функций, которая позволяет конечную последовательность ярусов ярусно-параллельной формы вычисления суперпозиции заменить одним единственным ярусом без изменения точности аппроксимации; как результат должна достигаться естественная синхронизация параллельных процессов вычисления функций данного вида;
выполнить перенос метода на случай функций, аппроксимируемых тригонометрическими полиномами, включая частные суммы ряда Фурье, ДПФ, БПФ и преобразования на основе ортогональных полиномов; исследовать специфику устойчивости, и параллелизма выполнения преобразований Фурье данным методом;
6) разработать алгоритмы параллельного вычисления всех элементов триго
нометрического базиса преобразований Фурье и элементов базиса ортого
нальных полиномов; синтезировать параллельные алгоритмы суммирова
ния ряда Фурье, ДПФ; БПФ, которые позволяют совмещать выполнение:
этих преобразований с одновременным вычислением; всех элементов три
гонометрического базиса и всех коэффициентов разложений в данном ба
зисе; :
7) дать формальное описание предложенных алгоритмов вычисления функ-
цийи разработать программные модели с целью отладки, проверки рабо
тоспособности; оценок временной сложности и вычислительной устойчи
вости сконструированных методов вычисления функций;
8) провести численный эксперимент по оценке устойчивости и корректности
алгоритма оптимизации временной сложности схем вычисления функций.
Методы исследования опираются на использование теоретических основ информатики, численного анализа; теории сложности, прикладной информатики и алгоритмов цифровой обработки сигналов.
Научная новизна диссертационной работы г заключается в построении обобщенного метода* приближенного-- вычисления элементарных, функций; их суперпозиций, а также функций одной действительной переменной более общего вида, включая тригонометрические полиномы, используемые в качестве элементов базиса преобразований Фурье, в том числе ДПФ и БПФ. Метод обладает параллелизмом, вычислительной устойчивостью и в широком диапазоне точности приближения функций достигает единичной оценки временной сложности их вычисления: Синтезирован алгоритм оптимизации временной сложности;вычисления, функций рассматриваемого вида при условии заданных ограничений на объем памяти и вычислительные ресурсы.
Конкретно, научная новизна результатов может быть охарактеризована следующим образом:
1) предложен метод и сконструированы алгоритмы устойчивого вычисления і функций одной действительной переменной и их суперпозиций с априори
заданной границей абсолютной погрешности на произвольном промежутке с оптимизацией временной сложности при заданных ограничениях на объем памяти и вычислительные ресурсы;
предложенные методы и; схемы характеризуются регулярностью, единством конструкции, эффективно распараллеливаются, обладают- естественной синхронизацией и вычислительной устойчивостью; сочетание двух последних качеств с оптимизированной временной сложностью и быстродействием в целом отличают данные методы от известных;
предложена алгоритмическая схема параллельного вычисления сложной суперпозиции элементарных функций, которая позволяет конечную последовательность ярусов ярусно-параллельной формы вычисления суперпозиции заменить одним единственным ярусом без изменения точности аппроксимации; существенно при этом, что ярус произвольно заданных функций с готовыми значениями аргументов і приобретает естественную синхронизацию по шагам схемы Горнера вычисления значения аппроксимирующего такие функции полинома;
разработаны параллельные схемы суммирования ряда Фурье, ДПФ и БПФ, которые формально достигают логарифмических оценок временной сложности при совмещении их выполнения с параллельным вычислением всех элементов-тригонометрического базиса, а также коэффициентов^ данных тригонометрических разложений; такое совмещение отличает схемы от известных и позволяет выполнять рассматриваемые преобразования при!динамически меняющемся количестве отсчетов и динамически меняющихся коэффициентах разложений; отличительным качеством полученных схем является их инвариантность относительно количества: элементов базиса и относительно выбора шага дискретизации преобразований Фурье; в частности, шаг дискретизации может быть переменным;
разработанные схемы преобразований = Фурье базируются на переводе этих преобразований в форму полинома; что отличает эти схемы от известных по построению и- позволяет применить.для выполнения данных
преобразований методы параллельного вычисления полиномов, а также методы кусочно-полиномиальной аппроксимации; 6) разработанные параллельные схемы преобразований Фурье переносятся на случай разложения по ортогональным полиномам с сохранением отли-. чительных динамических характеристик.
Отличительной особенностью предложенной обобщенной схемы от известных схем приближенного вычисления функций является то,.что оптимизация временной сложности достигается алгоритмическими и программными; средствами, в то время как в известных схемах такая оптимизация, как правило, достигается средствами математического анализа. Основные положения, выносимые на защиту:
1) обобщенная схема устойчивого вычисления функций одной действитель
ной переменной и их суперпозиций с априори заданной границей абсо-
. лютной погрешности- на произвольном промежутке с оптимизацией временной сложности при заданных ограничениях на объем памяти и вычислительные ресурсы;
алгоритмическая схема параллельного вычисления сложной суперпозиции элементарных функций, которая позволяет конечную последовательность . ярусов ярусно-параллельной формы вычисления? суперпозиции заменить единственным ярусом без изменения точности аппроксимации;
параллельные алгоритмы приближенного вычисления функций; аппроксимируемых тригонометрическими полиномами; включая частные суммы
. ряда Фурье на основе перевода этих сумм в форму алгебраического полинома;
алгоритмы параллельного вычисления ДПФ и БПФ, совмещенные с параллельным вычислением коэффициентов и всех элементов тригонометрического базиса в условиях динамически; меняющихся параметров,, включая меняющееся число отсчетов и переменный шаг дискретизации;
схема, согласно которой при условии дополнительного времени на априорный перевод ДПФ в форму алгебраического полинома дальнейшее вы-
числение N -точечного ДПФ может выполняться г параллельно на N процессорах за время 0(І).
Практическая ценность диссертационного исследования!заключается в прикладном характере предложенных методов и алгоритмов. В частности, методы кусочно-полиномиальной аппроксимации могут составлять библиотеку стандартных и встроенных компьютерных программ устойчивого вычисления функций с единичной оценкой времени. Эти методы пригодны для. бортовых вычислителей, их целесообразно применять для синхронизации параллельных процессов вычисления функций; вместе с тем их можно использовать в персональных компьютерах со стандартной: архитектурой. Практически ценны качества минимизации времени вычислений при заданных ограничениях на объем памяти и вычислительные ресурсы, регулярность и общность предложенных схем..Важной для практики цифровой фильтрации.является применимость предложенных методов для параллельного вычисления; всех элементов базиса ортогональных преобразований, включая ДПФ и БПФ. Практическую направленность имеют представленные в диссертации методы; параллельного выполнения ДПФ за логарифмическое число шагов при переменном шаге дискретизации, переменном количестве отсчетов и переменном * числе элементов базиса.
Внедрение и использование результатов работы. Полученные в работе результаты использованы в госбюджетной НИР «Математические методы устойчивой параллельной обработки, поиска и распознавания», код ВНТИЦ 02 0318 206 0355, регистрационный номер 01.2.00 106436; при разработке изделия «Заря-СК» на ФГУП «Таганрогский завод «Прибой»; в учебном процессе кафедры информационных систем и технологий управления Таганрогского государственного педагогического института, что подтверждено соответствующими актами1 об использовании, приведенными в приложении к диссертационной работе.
Апробация работы. Основные результаты работы докладывались на:
Всероссийской научно-технической конференции с международным участием «Компьютерные технологии в инженерной и управленческой деятельности» (Таганрог, 1999 г.);
6-й Международной конференции «Математические модели физических процессов и их свойства» (Таганрог, 2000 г.);
международной научно-практической конференции «Проблемы образования студентов гуманитарных вузов в свете развития современных информационных технологий» (Таганрог, 2001 г.);
Международной научно-технической конференции «Интеллектуальные САПР» (Таганрог, 2002 г.);
научно-технических конференциях профессорско-преподавательского состава и аспирантов ТГПИ (Таганрог, 2000 - 2003 гг.);
семинаре «Теоретическая и прикладная информатика» кафедры информатики ТГПИ (Таганрог, 2004 г.).
Публикации. По материалам работы опубликовано 8 печатных работ, включая монографию, с общим объемом 14 печатных листов.
Структура и объем работы. Диссертационная работа состоит из введения, 3 глав основного раздела, заключения, списка литературы и 4 приложений. Основное содержание работы изложено на 149 страницах, включая 23 таблицы, 6 рисунков и список литературы из 85 наименований.
Алгоритм и программное моделирование минимизации временной -сложности обобщенной схемы кусочно-полиномиальной аппроксимации функций на основе полинома Лагранжа
Время, необходимое для вычисления ДПФ, пропорционально числу произведений, и при непосредственной реализации это число пропорцио нально N2. Во втором случае, т. е. при использовании (21) и (22), время вы числении пропорционально + N&N2 /2 при больших N. Отметим, что, если число N12 снова четно, можно повторить процедуру, и если N является степенью числа2, ее можно повторять до тех пор, пока не будет получено преобразование одной точки, которое, очевидно, совпадает с самой точкой. Отсюда полное число комплексных умножений, необходимых для выполнения ДПФ, пропорционально (N12) log 2 N. Сохраняет актуальность проблема сокращения времени вычисления ряда Фурье, БПФ и ДПФ. Такая проблема имеет место как в случае последовательных, так и параллельных вычислений для компьютеров с различной архитектурой /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) дать формальное описание предложенных алгоритмов вычисления функ цийи разработать программные модели с целью отладки, проверки рабо тоспособности; оценок временной сложности и вычислительной устойчи вости сконструированных методов вычисления функций.
Представление неветвящихся вычислительных алгоритмов в форме параллельной программы с детерминированными значениями управляющих индексов
Наконец, следует учесть, что (1.66) отражает сложность одного шага; если в результате его выполнения не достигается точность (1.6), процесс воспроизводится на 2 +I подынтервалах заново и т.д. Отсюда оценка (1.66) требует оговорки как в отношении к в левой части, - оно зависит от є, - так и в отношении значения правой части, - ее надлежит умножить на число повторных воспроизведений процесса вычислений, необходимых для достижения оценки точности (1.6).
На основании изложенного можно заключить, что программная реализация обобщенной матричной схемы аппроксимации функций рассматриваемого класса полиномами: произвольно заданной степени обладает вычислительной устойчивостью (в силу возможности выбора минимальной степени аппроксимирующего полинома) и минимальной, временной сложностью порядка О (і) (согласно оценке замечания 1.4).
Следует заметить, что предложенные обобщенные последовательные и параллельные схемы приближенного вычисления функций отличаются от известных тем, что,в качестве частных случаев они включают аппроксимации на основе интерполяционных полиномов Лагранжа, Чебышева и тейлоровских разложений. Такой вывод следует из того, что если наперед задана точность аппроксимации и по предложенной схеме выбрана степень аппроксимирующего полинома, этот полином во всех случаях может быть приведен к каноническому виду полиномах заданными коэффициентами. Вместе с тем предложенная схема непосредственно по построению включает как частный случай схемы кусочно-полиномиальной аппроксимации и сегментной фрагментации. В дальнейшем будет показано, что рассматриваемая схема включает также известные схемы параллельного вычисления полиномов, — на том основании, что каждый аппроксимирующий функцию полином может быть вычислен по такой параллельной, схеме как на основном интервале, так и на каждом подынтервале в отдельности.
Представление неветвящихся вычислительных алгоритмов в форме параллельной программы с детерминированными значениями управляющих индексов. Под арифметическим выражением (АВ) будет пониматься вычислительная формула из конечного числа констант, переменных и функций, связанных знаками арифметических операций/ 31 /. При этом для определенности предполагается, что значения констант, переменных; функций и их аргументов могут быть только действительными. В данном определении допускаются только такие функции, которые включают конечное число суперпозиций над стандартными функциями; к числу стандартных относятся все функции одной переменной из списка встроенных и внешних функций языка ФОРТРАН / 71 /. Наиболее существенной частью излагаемого определения является то, что в АВ все операции, отличающиеся от сложения и умножения, должны быть выражены через функции. В частности, ах интерпретируется как функция при любом дг Г, включая х натуральное. Деление Ь/х интерпретируется как Ьх х. где -«:=» обозначает оператор присваивания; каждая Frik) является стандартной функцией, значение аргумента bkr которой либо задано исходно как константа, либо задано как значение переменной: а{(к,), либо как значение переменной f{ 2), где кх к к2\ а] ])() определяется совершенно аналогично bkr, - либо как исходная константа, либо как значение а или / 2) с той разницей, что &, к к2. Пусть также предполагается, что при каждом к = const все значения переменных Ьь выражены записью, непосредственно предшествующей записи (1.67), а все значения переменных сг{к 1)() - записью, заключенной между (1.67) и (1.68). Если притом задание этих значений произведено в соответствии с принципом,единственного присваивания / 72/, то набор АВ (1.67), (1.68) называется F-ЕП-программой. Названный принцип понимается в том смысле, что любой из переменных bkr, а(к 1)(), во всей
Замечание 1.5. Данный принцип в / 721 представлен как «второе определение однократного присваивания» (переменная может получить значение в программе только один раз). В дальнейшем по ходу изложения станет очевидно, что данную формулировку можно заменить на «первое определение однократного присваивания» (переменной можно присвоить значение только в одном операторе программы) без существенных изменений предложенной в I 31, 65 / архитектуры MB С, на которую наиболее ориентирован излагаемый метод. При этом оператор программы будет представлять собой укрупненный оператор циклического шага («оператор F-ЕП -ранга Ь ), что оговаривается ниже в соответствующем конкретном контексте.
Схема параллельного выполнения дискретного преобразования Фурье, совмещенная с параллельным вычислением коэффициентов и элементов базиса
Поэтому вся такая сложная суперпозиция элементарных функций в данной ярусно-параллельной форме может быть заменена на один единственный ярус из полинома первой; степени, причем ярус будет содержать только умножение и сложение.
В результате число последовательных ярусов ярусно-параллельной формы сокращается с 6 до 1. Время параллельной.реализации такой функции ускоряется в 6 раз.
Данный пример иллюстрирует сущность применения изложенной таблично-алгоритмической; схемы для параллельного вычисления сложной суперпозиции элементарных функций: метод позволяет конечную последовательность ярусов ярусно-параллельной формы вычисления суперпозиции заменить одним единственным ярусом без изменения точности аппроксимации.
Иными словами, метод позволяет выполнить вычисление суперпозиции по максимально параллельной форме программы. Изложенный метод существенно упрощает ярусно-параллельную форму. В (1.67) на месте элементарной функции можно поставить суперпозицию функций, например, вида (1.26). В этом случае ярус (1.67) приобретает вид суммы,произведений (после преобразований транслятора).
Замечание 1.6. Как отмечалось, предложенная! кусочно-полиномиальная схема позволяет по всем подынтервалам параллельно приближенно вычислять суперпозицию функций как полином заданной степени от одного заданного аргумента. В частности, это можно сделать при помощи полинома первой степени. Именно данное качество обобщает и усовершенствует представленный в /31,65/ прототип описанной выше ярусно-параллельной формы.
Существенно при этом, что ярус произвольно заданных функций с готовыми значениями аргументов; приобретает естественную синхронизацию по шагам схемы Горнера вычисления значения, аппроксимирующего такие функции полинома. 1. Предложен метод, на основе которого конструируются алгоритмы приближенного вычисления функций одной действительной переменной с априори заданной границей абсолютной погрешности на: произвольном промежутке с минимальным значением временной сложности при условии заданных ограничений на объем памяти и вычислительные ресурсы. Метод отличается обобщенностью, включая в себя алгоритмическое построение и программную реализацию кусочно-полиномиальной схемы аппроксимации функций одной действительной переменной, а также аппроксимации такой функции полиномом произвольно заданной степени при отмеченных ограничениях. Частью конструкции метода является обобщенная- параллельная схема восстановления коэффициентов полинома по его корням: 2 . Метод отличается оптимизированным значением временной сложности. Оптимизация временной сложности понимается как нахождение ее минимального значения при условии заданных ограничений на объем памяти и вычислительные ресурсы. Минимальная временная сложность порядка О (і) достигается как в последовательном, так и в параллельном вариантах предложенного метода. В условиях минимальной временной; сложности метод отличается вычислительнойустойчивостью. 4. Конструкция метода вносит существенное упрощение в ярусно-параллельную форму вычислительного алгоритма, внося естественную синхронизацию в ярус функций по, фиксированной для всех функций одной переменной степени аппроксимирующего полинома. При этом аппроксимируемая в ярусе функция может иметь вид произвольной суперпозиции элементарных функций. 5. Предложенный метод можно трактовать как общего вида алгоритмическую схему вычисления функций одной действительной переменной, которая как частный случай включает известные аппроксимации функций на основе интерполяционного полинома Лагранжа и ряда Тейлора. 6. Обобщенность схемы и минимизация временной сложности достигаются техническими (программными), а не математическими средствами. 7. Метод промоделирован на языках Фортран, Turbo Basic, Pascal 7.0 и Object Pascal в среде Delphi. Результаты моделирования и численный эксперимент подтверждают высокую точность и минимальную временную сложность аппроксимации функций при заданных ограничениях на объем памяти и вычислительные ресурсы.
Устойчивость вычисления базисных функций преобразования Фурье на основе кусочно-полиномиальной аппроксимации
ДПФ в форме (2.52) является функцией при дискретно задаваемом значении аргумента: В диапазоне изменения этого аргумента функцию (2.52) можно преобразовать к кусочно-полиномиальной форме, как это было сделано в примере 2.1 для случая преобразования в форму полинома частичной суммы ряда Фурье. Тогда всю эту функцию можно для одного значения отсчета вычислить за время- 0(l) на одном процессоре. Параллельное вычисление всего ДПФ для N отсчетов потребует того же времени на -N процессорах.
Предложение 2.7. ДПФ может быть преобразовано в форму алгебраического полинома. При этом время выполнения ДПФ в максимально параллельной форме варьируется от оценки (2.55) до оценки для: случая ./V отсчетов в зависимости от охарактеризованных непосредственно выше условий относительно характера изменения числа отсчетов и шага дискретизации. В частности, оценка (2.56) достигается при условии наличия дополнительного времени на предварительное преобразование ДПФ в форму полинома (2.52).
Таким образом, ДПФ может выполняться по параллельным схемам, идентичным представленным для случая вычисления частичной суммы ряда Фурье. Следует заметить, что кусочно-полиномиальные схемы, разработанные в главе 1 для функций сравнительно общего вида, в частности, могут быть эффективно использованы, как показывает оценка (2.56), для параллельного выполнения ДПФ. Очевидно, что если в качестве базиса ортогональных преобразований взамен тригонометрического рассматривать базис ортогональных полиномов, то еще более просто, чем в рассмотренном случае, получается перевод ортогонального преобразования в форму полинома (2.52). На основании замечания 2.14 на случай базиса ортогональных полиномов переносятся все рассуждения, схемы и оценки, проделанные для случая ДПФ с тригонометрическим базисом. 1. Изложены схемы вычисления функций, аппроксимируемых тригонометрическими полиномами, включая частные суммы ряда Фурье, ДПФ, БПФ; а также ортогональные преобразования общего вида. 2. В отличие от известных, первая из предложенных схем позволяет производить устойчивое параллельное вычисление тригонометрического полинома произвольной степени с временной сложностью 0(l). Эта. схема применяется при существенном ограничении, которое заключается в том, что тригонометрический полином аппроксимирует часто используемую функцию. 3. Вторая из предложенных схем основана на переводе тригонометрического полинома в форму алгебраического полинома с заданными коэффициентами. Значение последнего можно вычислить по одной из известных параллельных схем с оценкой временной сложности О (log2 п). Ограничение для данного случая составляет необходимость предварительного преобразования тригонометрического полинома в форму алгебраического. Преобразование можно выполнить по предложенному в данной главе алгоритму, отличающемуся от известных преобразований ряда Фурье. 4. Третья из предложенных схем отличается от известных по построе нию, а также тем, что без дополнительных ограничений позволяет парал лельно вычислять приближенное значение суммы ряда Фурье, значение ДПФ одновременно со всеми элементами тригонометрического базиса и коэффициентами с временной сложностью 0(log2 п). 5. Данная схема имеет вид регулярного распараллеливаемого алгоритма и обобщается на разложение по произвольным ортогональным полиномам. Эта схема инвариантна относительно числа элементов базиса, количества точек отсчета ДПФ и переменного шага дискретизации. При этом логарифмическая оценка временной сложности параллельного выполнения ДПФ достигается в условиях динамически изменяющихся параметров. 6. При наличии дополнительного времени на априорный перевод ДПФ в форму алгебраического полинома дальнейшее вычисление N-точечного ДПФ может выполняться параллельно на N процессорах за время. В главе приводятся программные модели сконструированных методов вычисления функций с целью отладки, проверки работоспособности, точности, оценок временной сложности и анализа вычислительной устойчивости. Программная реализация включает обобщенную кусочно-полиномиальную схему аппроксимации функций рассмотренных в двух предыдущих главах классов полиномами произвольно заданной степени при условии вычислительной устойчивости и минимальной временной сложности.
Численный эксперимент проведен на различных языках программирования, включая Object Pascal в среде Delphi. Проверке на точность, устойчивость и временную сложность подвергались, в частности, предложенные схемы выполнения преобразований Фурье.
