Алгоритмы оптимизации временной сложности кусочно-полиномиальной аппроксимации функций в применении к быстрому преобразованию Фурье на основе параллельного вычисления элементов базиса

• Автор: Фирсова, Светлана Александровна
• Шифр специальности: 05.13.17, 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Таганрог
• Количество страниц: 168 с.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ.
ГЛАВА 1. АЛГОРИТМИЧЕСКОЕ ПОСТРОЕНИЕ И ОПТИМИЗАЦИЯ ВРЕМЕННОЙ СЛОЖНОСТИ ОБОБЩЕННОЙ КУСОЧНОПОЛИНОМИАЛЬНОЙ СХЕМЫ АППРОКСИМАЦИИ ФУНКЦИЙ ОДНОЙ ДЕЙСТВИТЕЛЬНОЙ ПЕРЕМЕННОЙ.
1.1. Обобщенная схема кусочнополиномиальной аппроксимации функций на основе полинома Лагранжа
1.2. Алгоритм и программное моделирование минимизации временнойсложности обобщенной схемы кусочнополиномиальной аппроксимации функций на основе полинома Лагранжа
1.3. Алгоритм кусочнополиномиальной аппроксимации на основе ряда Тейлора в средах i и в среде i
1.4. Обобщенная матричная схема параллельного восстановления коэффициентов полинома по его корням.
1.5. Представление неветвящихся вычислительных алгоритмов в форме параллельной программы с детерминированными значениями управляющих индексов.

1.6. Выводы.

ГЛАВА 2. АЛГОРИТМЫ КУСОЧНОПОЛИНОМИАЛЬНОЙ АППРОКСИМАЦИИ ФУНКЦИЙ В ПРИМЕНЕНИИ К БПФ НА ОСНОВЕ

ПАРАЛЛЕЛЬНОГО ВЫЧИСЛЕНИЯ ЭЛЕМЕНТОВ БАЗИСА.

2.1. Алгоритм аппроксимации суммы ряда Фурье алгебраическими полиномами.
2.2. Параллельные схемы аппроксимации суммы ряда Фурье алгебраическими полиномами.
2.3. Схема параллельного суммирования ряда Фурье, совмещенная с параллельным вычислением элементов базиса на основе полиномов Чебышева
2.4. Параллельные схемы вычисления коэффициентов ряда Фурье
2.5. Разновидность схемы параллельного суммирования ряда Фурье, совмещенной с вычислением элементов базиса
2.6. Схема последовательного суммирования ряда Фурье, совмещенная с параллельным вычислением элементов базиса.
2.7. Схема параллельного выполнения дискретного преобразования Фурье, совмещенная с параллельным вычислением коэффициентов и элементов базиса
2.8. Совмещение схемы быстрого преобразования Фурье с параллельным вычислением элементов тригонометрического базиса
2.9. Обобщенные параллельные схемы суммирования разложений по ортогональным полиномам.
2 Преобразование ДПФ в форму алгебраического полинома и в кусочнополиномиальную форму с параллельной схемой выполнения
2 Выводы.
ГЛАВА 3. ЧИСЛЕННЫЙ ЭКСПЕРИМЕНТ ПО ОБОБЩЕННОЙ КУСОЧНОПОЛИНОМИАЛЬНОЙ АППРОКСИМАЦИИ ФУНКЦИЙ И ЭЛЕМЕНТОВ БАЗИСА ТРИГОНОМЕТРИЧЕСКИХ ПРЕОБРАЗОВАНИЙ.
3.1. Специфика программной реализации разложения элементарных функций в ряд Фурье с использованием его преобразования к виду алгебраического полинома
3.2. Численный эксперимент по переводу частичной суммы ряда Фурье в форму алгебраического полинома
3.3. Устойчивость вычисления базисных функций преобразования Фурье на основе кусочнополиномиальной аппроксимации.
3.4. Вычисление коэффициентов кусочнополиномиальной аппроксимации на основе схем, оптимизирующих временную сложность
3.5. Выводы
ЗАКЛЮЧЕНИЕ.
ЛИТЕРАТУРА


Аппроксимация функции одним полиномом на большом промежутке может повлечь для достижения заданной точности значительного увеличения степени полинома, что пропорционально степени повышает объем вычислений. При ограничении степени аппроксимирующего полинома увеличивается погрешность. Отсюда возникает задача разработки метода аппроксимации функций на такой основе, которая при малой степени полинома могла бы обеспечивать требуемую точность аппроксимации. Разложение функций по невязкам. При этом необходимо выполнение условия i 0 0. Один из способов получения разложения функций по невязкам состоит В ТОМ, ЧТО из уравнения невязки 4 определяется0 0,0 а из этого уравнения находится искомая функция xфСуо Д наиболее часто употребляемых элементарных функций допускается представление суперпозиции функций. ЯВНОМ виде. В качестве примера разложения функции в ряд невязок можно привести разложение функции д1плг. Д0 абсолютная погрешность начального приближения у0. Разложения функций по невязкам имеют достаточно широкое распространение в качестве метода аппроксимации функций. Однако, необходимая точность вычисления функции достигается лишь при условии правильного выбора начального приближения, алгоритм нахождения которого может быть достаточно сложным и не обладает универсальностью. Данный метод не может быть реализован по единой программе в общем случае. Метод невязок не гарантирует вычисления функции с заданной точностью при заданном количестве операций за заданное время. Для данного метода в периодической литературе не предлагаются параллельные алгоритмы реализации. Дробнорациональные приближения. ЛхТа,х кь,х
Общее количество операций для достижения заданной точности при рациональном приближении обычно меньше, чем при многочленном, однако при использовании дробнорациональных приближений появляется операция деления. Следует иметь в виду, что во многих ЭВМ само деление организуется как приближенное вычисление функции хх для которой требуется алгоритм, сопоставимый по числу операций с вычислением Як, х . В тех случаях, когда скорость выполнения операции деления близка к скорости умножения, эффективность использования рациональной аппроксимации возрастает. В последовательных арифметических устройствах иногда применяют переход от дробнорационального приближения к вычислению соответствующей цепной дроби. Общее количество операций при вычислении цепной дроби меньше, чем при вычислении рациональной дроби, образуемой по схеме подходящей дроби . Поэтому с помощью цепных дробей вычисляют значения тех функций, для которых разложение в степенной ряд сходится недостаточно быстро или даже расходится. Помимо того аппроксимация функций в виде цепных дробей используется как источник получения рациональных приближений. Иногда цепная дробь используется как средство уменьшения количества операций при счете на ЭВМ. При определенных условиях использование аппарата цепных дробей способствует уменьшению накопления погрешностей округления , . В частности, для цепной дроби с единичными частными числителями и положительными частными знаменателями относительная погрешность ее значения асимптотически с точностью до бесконечно малых первого порядка не превышает максимальной из относительных погрешностей ее компонентов независимо от числа звеньев дроби. Практическое использование цепных дробей ограничивается некоторыми их особенностями. Так, например, при вычислении цепных дробей в режиме с плавающей запятой погрешности округления могут накапливаться быстрее, чем при счете дробнорациональной функции . Для приближения функции цепной дробью требуется выполнить ряд априорных расчетов искомой функции, на конкретной ЭВМ с целью оценки фактических погрешностей и определения необходимого числа разрядов в машинном представлении числа в отличие от степенного ряда цепная дробь не имеет общей формулы остаточного члена приближения. Помимо отмеченных известных затруднений, цепная дробь сама по себе, непосредственно по построению, не допускает эквивалентной записи в параллельной форме. Однако необходимо оговориться, что алгоритмическая структура цепной дроби адекватна архитектуре конвейерного типа.