Вычисление функций на сетках в контексте символьно-численно-графического интерфейса

• Автор: Кисленков, Владимир Валерьевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 87 с. : ил

Введение.

1 Вычисление функций на сетках с переменным шагом

1.1 Настройка на интервал значений аргумента .

1.1.1 Идея подхода.

1.1.2 Настройка на интервал при вычислении

значений функции с помощью асимптотического ряда.

1.2 Использование базовых точек

1.2.1 Идея подхода.

1.2.2 Вычисление значений некоторых элементарных функций.

1.3 Настройка на значение параметра

1.3.1 Идея подхода.

1.3.2 Модифицированные функции Бесселя . .
1.3.3 Исходные алгоритмы.
1.3.4 Сеточноориентированные алгоритмы . .
2 Программные средства поддержки сеточноориентированных вычислений
2.1 Архитектура.
2.2 Программный интерфейс библиотеки.
2.2.1 Схемы работы с библиотекой.
2.2.2 Программный интерфейс
2.3 Модуль символьной обработки
2.4 Численная библиотека
2.4.1 Описание
2.4.2 Интерфейс
2.5 Модуль рекурренций
2.5.1 Описание
2.5.2 Интерфейс
2.6 Интерфейсный модуль .
2.7 Дополнительные реализации.
2.7.1
2.7.2 Система .
2.7.3 Пакет i
2.8 Дальнейшее развитие.
3 Дополнение. Вычисление произведений с помощью сеточноориентированных алгоритмов
3.1 Постановка задачи вычисления произведений . .
3.2 Основные алгоритмы
3.3 Применение развертки и цепочек рекурренций .
3.4 Реализация
Заключение.
Введение


При этом в ряде таких задач подобные вычисления требуют больших временных затрат. Поэтому разработка программных средств, позволяющих ускорять вычисление функций на сетках, является актуальной проблемой. На практике вычисление значений заданной функции на сетке часто производится наивным методом, путем независимого вычисления в каждой точке сетки. Однако, вычисляя значение этой функции в очередной точке сетки, можно попытаться использовать часть ранее проделанной работы по вычислению функции в предыдущих точках, сокращая таким образом число операций и ускоряя процесс вычислений. Основанные на этой идее методы вычисления функций мы будем называть сеточноориентированными. Сеточноориентированные методы позволяют достичь большей скорости вычислений путем преобразования методов независимых вычислений функций к виду, позволяющему сохранить некоторую часть промежуточных результатов вычислений в уже пройденных точках сетки, и последующего использования этих результатов для вычисления значений функции в новых точках. Кроме того, частое обращение к сохраненным данным требует высокой скорости обмена процессора с памятью. На прежних компьютерах часто оказывалось так, что вычисление некоторой величины производилось быстрее, чем выборка этой величины из оперативной памяти. Современные же компьютеры, обладающие большими объемами как оперативной, так и быстрой кэшпамяти, делают возможными хранение и быструю обработку большого объема промежуточных результатов. Для некоторых классов функций хорошо известны алгоритмы, позволяющие экономить операции при вычислениях на сетках с помощью предварительной обработки. Например, если для вычисления полиномов общего вида Рпх аоХп 4в1 . ХОп водной точке наиболее быстрой является схема Горнера п умножений и п сложений, то для вычислений таких полиномов на сетке можно применить более экономные вычислительные алгоритмы, позволяющие сократить число операций по сравнению с применением схемы Горнера независимо в каждой точке сетки. Применение таких алгоритмов осуществляется в два этапа на первом этапе исходный полином преобразуется к специальному виду на втором этаг пе производится вычисление значений исходного полинома с помощью нового представления в точках заданной сетки. При этом число операций на втором этапе меньше числа операций при вычислении полиномов по схеме Горнера независимо в каждой точке. К таким вычислительным схемам относятся схемы Дж. Тодта, Ю. Л. Кеткова, В. Я. Пана 1. Таким образом, достигается небольшая экономия по сравнению со схемой Горнера, согласно которой в данном случае потребовалось бы пять умножений и шесть сложений. Болес общая схема Кеткова требует для произвольного полинома пй степени для п 6 выполнения п 2 п4 умножений и п 1 сложений. В работе Э. Белаги 2 дается строгое доказательство невозможности построения схемы вычислений произвольных полиномов й степени, использующей на втором этапе менее 1 умножений и п сложений. Схемы Пана 3 позволяют достичь количества действий, близких к этой оценке. Однако, если рассматривать вычисление полиномов на равномерной сетке, что является часто встречающейся задачей, то можно достичь гораздо большей экономии числа операций с помощью известного метода конечных разностей. Идея этого метода состоит в следующем если первая разность интересующей нас функции рх я1 х может быть вычислена посредством меньшего числа операций, чем гг 1, то для вычисления значения функции в новой точке сетки можно использовать функцию рх и значение в предыдущей точке сетки. Если, например, функция является полиномом степени п, то ее первой разностью будет полином степени п 1. Для вычисления 1рх можно снова использовать первую разность, и т. В результате для вычисления заданного полинома в новой точке потребуется всего лишь п сложений. Заметим, что метод конечных разностей отличается от ранее упомянутых методов тем, что подразумевает некоторую перенастройку вычислительной схемы в каждой новой точке, т. А вычисления с предварительной обработкой после ее проведения осуществляются в каждой точке сетки независимо.