Содержание к диссертации
Введение
ГЛАВА 1. Особенности обработки функциональных зависимостей в экономических и социальных системах 13
1.1. Функциональная зависимость как предмет исследования в экономических и социальных системах 14
1.2. Измерения и погрешность при обработке временных рядов в эконометрике 19
1.3. Особенности данных и закономерностей в социологии 23
1.4. Обзор и анализ алгоритмов приближения таблично заданных функциональных зависимостей 26
1.4.1. Обзор и анализ способов глобальной и локальной аппроксимации 26
1.4.2. Обзор и анализ результатов использования степенных рядов при аппроксимации для уменьшения вычислительной погрешности 30
1.4.3. Обзор и анализ методов построения эмпирических формул 32
1.5. Обзор известных методов сжатия информации 34
1.6. Анализ алгоритмов численного интегрирования 37
1.7. Сущность предлагаемого подхода к обработке таблично заданных функций одной переменной 38
Выводы 43
ГЛАВА 2. Исследование свойств детерминированных хаотических рядов. описание методов обработки таблично заданных функций одной переменной 45
2.1. Основы теории хаотических систем 45
2.2. Математическое описание алгоритмов приближения таблично заданных функций одной переменной 53
2.2.1. Математическое описание методов глобальной интерполяции 54
2.2.2. Методы локальной интерполяции 59
2.2.3. Использование степенных рядов при аппроксимации для уменьшения вычислительной погрешности 60
2.2.4. Построение эмпирических формул 62
2.3. Математическое описание алгоритмов численного интегрирования 64
Выводы 66
ГЛАВА 3. Алгоритмизация предлагаемых методов аппроксимации и интегрирования и построение моделей сжатия и восстановления числового ряда 68
3.1. Алгоритмизация метода аппроксимации числового ряда 68
3.2. Алгоритмизация метода интегрирования числового ряда 85
3.3. Описание разработанного программного обеспечения 89
3.3.1. Используемые данные и процедуры обработки 90
3.3.2. Описание работы модулей программы 91
Выводы 102
ГЛАВА 4. Практическая реализация и сопоставительный анализ методов аппроксимации и интегрирования функций одной переменной 104
4.1. Результаты сокращения затрат памяти таблично заданных функций одной переменной при использовании разработанной модели сжатия метода аппроксимации 104
4.2. Сопоставительный анализ результатов реализаций известных и разработанного метода аппроксимации 116
4.2.1. Сравнение показателей погрешности и затрат памяти 116
4.2.2. Сравнительный анализ скоростных характеристик и оценка вычислительной сложности 119
4.3. Сопоставительный анализ результатов реализаций известных и разработанного методов интегрирования 126
4.3.1. Сравнение показателей погрешности и затрат памяти 126
4.3.2. Сравнительный анализ скоростных характеристик... 129
Выводы 136
Заключение 138
Список использованных источников 141
Приложение 1 149
- Обзор и анализ результатов использования степенных рядов при аппроксимации для уменьшения вычислительной погрешности
- Использование степенных рядов при аппроксимации для уменьшения вычислительной погрешности
- Алгоритмизация метода интегрирования числового ряда
- Сравнительный анализ скоростных характеристик и оценка вычислительной сложности
Введение к работе
Актуальность. Управление в социально-экономических системах основывается на необходимости обработки больших объемов информации, значительная часть из которой является результатом использования эконометрики и социометрии и представляет собой функции одной переменной, отражающие поведение объектов управления, в том числе во времени. При этом накапливаются огромные массивы эконометрических и социометрических данных, требующих адекватной и своевременной обработки в компьютерных системах поддержки принятия управленческих решений. В связи с этим возникает проблемная ситуация, сущность которой заключается в отсутствии таких практически пригодных форм представления функций, средств их интегрирования и алгоритмов, которые обеспечивают высокую скорость обработки данных при приемлемой погрешности и допустимом минимуме затрат памяти. Для разрешения названной проблемной ситуации возникает потребность в поиске новых подходов, методов и алгоритмов, а также соответствующих программных средств.
Основная решаемая задача данной диссертационной работы заключается в разработке программных и алгоритмических средств аппроксимации функций одной переменной и их интегрирования на основе положений теории хаотических систем.
Для решения основной решаемой задачи имеются необходимые предпосылки. Над проблемами аппроксимации и интегрирования функций работали известные отечественные и зарубежные исследователи. Вопросам изучения хаотических систем посвящены работы А. Пуанкаре, Э. Лоренца, М. Хенона, Дж. Томпсона, Г. Биркгофа, Н. С. Крылова, А.Н. Гапоно-ва-Грехова и других известных ученых.
Теоретическая часть диссертационной работы включает в себя разработку методов и алгоритмических средств аппроксимации и интегрирования функций на основе положений хаотических систем путем использования генераторов хаотических процессов в виде дискретных отображений особого типа. Практическая часть содержит описание программных средств, пригодных для практического использования в контурах систем управления социально-экономическими объектами.
Исследование реализации аппроксимации и интегрирования функций одной переменной на основе достижений современной теории хаотических систем является актуальным и перспективным научным направлением.
Работа выполнялась в рамках гранта Минобразования Г00-4.5-15 «Разработка и исследование методов, алгоритмических, программных и технических средств организации быстрых символьных вычислений» при непосредственном участии автора.
Цель работы заключается в разработке методов, алгоритмических средств и программной реализации процедур аппроксимации и интегрирования функций одной переменной на основе использования дискретных хаотических отображений для снижения вычислительной и емкостной сложности, и также регулирования погрешности при использовании программных продуктов в контурах систем управления социально-экономическими объектами.
Задачи исследования заключаются в следующих положениях:
Определить особенности объекта исследования и существующих методов обработки (аппроксимация, сжатие и интегрирование) функций одной переменной, а также исследовать свойства дискретных хаотических отображений.
Разработать методы и алгоритмические средства аппроксимации и интегрирования функций одной переменной на основе генераторов числовых хаотических рядов в виде специальных дискретных отображений.
Создать программные средства аппроксимации и интегрирования функций одной переменной, являющихся пригодными для практического использования в современных системах управления социально-экономическими объектами.
Выполнить сопоставительный анализ разработанных методов функциональных преобразований с известными способами аппроксимации и интегрирования.
Объектом исследования являются процессы обработки таблично заданных форм представления информации в социально-экономических системах.
Предметом исследования является организация и реализация процедур аппроксимации и интегрирования функций одной переменной.
Методы исследования основываются на положениях теории проектирования сложных информационных систем, функционального математического анализа, теории алгоритмов, теоретического программирования и теории хаотических систем.
Достоверность и обоснованность результатов исследования подтверждается: согласованностью теоретических и экспериментальных результатов, проведенными программными экспериментами по функциональному преобразованию таблично заданных функций одной переменной, полученных в результате использования эконометрики и социометрии; корректным использованием законов и положений современной теории хаотических (случайно-подобных) систем и теории аппроксимации, а также рецензированием печатных работ, их обсуждением на научно-технических конференциях, семинарах кафедры ПО ВТ и экспертизой разработанного программного продукта Федеральной службой по интеллектуальной собственности, патентам и товарным знакам.
Научная новизна работы состоит в решении важной научно-технической задачи по созданию нового класса методов, алгоритмических и программных средств аппроксимации и интегрирования функций одной переменной для использования в контурах управления социально-экономических объектов. Впервые получены следующие результаты:
1. Разработан метод аппроксимации функций одной переменной на основе генераторов числовых хаотических рядов в виде специальных дискретных отображений, что позволяет сокращать число хранящихся узлов в исходной последовательности и обеспечивать регулируемую погрешность
Л расчетов. Созданный алгоритм аппроксимации по затратам времени имеет преимущество до 7 раз по отношению к алгоритму, реализующему метод наименьших квадратов, по числу выполняемых операций - до 6 раз.
2. Созданы алгоритмические модели сжатия и восстановления таблично заданных функциональных зависимостей одной переменной по результатам измерений, позволяющие после разработки алгоритмов и программ достигнуть сокращения затрат памяти на периодических и гладких возрастающих или ц* убывающих функциях по сравнению с методами сжатия и округления в 10 раз.
3. Разработан метод интегрирования таблично заданных функцио нальных зависимостей на основе хаотической аппроксимации со скорост ными преимуществами и открывающий возможности создать алгоритми ческие и программные средства, обеспечивающие вычисление определен ных интегралов с погрешностью до 1-10". Скорость вычислений возрастает по сравнению с методами трапеций и прямоугольников в 1,3 раза.
4. Осуществлена алгоритмизация методов аппроксимации и интег- рирования при создании программных средств для конкретных практиче ских приложений, которая отличается упрощенной схемой взаимодействия модулей и унификацией состава основных блоков обработки таблично за данных функций одной переменной.
Практическая ценность работы заключается в создании пригодных для практического использования в системах управления социаль но-экономическими объектами программных средств аппроксимации и интегрирования функций одной переменной. Алгоритмизация и про- граммная реализация методов аппроксимации и интегрирования позволили получить показатели погрешности от 10"1 до 1-Ю'9, что является приемле мым для применения в социально-экономических системах. Разработанные методы, алгоритмы и программные средства открывают пути создания аппаратных средств для быстротекущих процессов, возникающих в кон турах систем управления (обработка результатов биржевых торгов, опросов, ^ анкет, демографических данных и т.д.), а также для аппроксимации и ин- тегрирования функций от многих переменных и для приложений в других ^ предметных областях.
На защиту выносятся:
Метод аппроксимации функций одной переменной на основе числовых хаотических рядов в виде дискретных отображений.
Алгоритмические модели сжатия и восстановления таблично заданных функциональных зависимостей.
3. Метод интегрирования таблично заданных функциональных зави- {А" симостей по результатам измерений на основе хаотической аппроксимации.
4. Результаты сопоставительного анализа разработанных и известных средств аппроксимации и интегрирования функций одной переменной.
Апробация результатов работы. Результаты диссертационной ра боты обсуждались и получили положительную оценку на VI научной кон ференции "Вибрация-2003", г. Курск, 2003 г.; XI Российской науч но-технической конференции «Материалы и упрочняющие техноло- гии-2004», г. Курск, 2004 г. (2 доклада); VIII Международной науч- * но-технической конференции «Медико-экологические информационные технологии - 2005», г. Курск, 2005 г.; VI Всероссийской научно-технической конференции «Теоретические и прикладные вопросы современных информационных технологий», г. Улан-Уде, 2005 г.; XII Российской научно-технической конференции «Материалы и упрочняющие технологии-2005», г. Курск.
Реализация результатов работы. Основные результаты диссертационного исследования в виде программных продуктов функционального преобразования таблично заданных функций внедрены в отделе автоматизированной системы управления производством (АСУП) ОАО «Геомаш», г. Щигры Курской области и используются в учебном процессе Курского государственного технического университета.
Публикации. По результатам выполненных разработок и исследо ваний опубликовано 9 печатных работ, в том числе 1 по перечню цен- V*1 тральных рецензируемых журналов и изданий, рекомендуемых ВАК Ми- нистерства образования и науки РФ, получено свидетельство об офици- ^ альной регистрации программы для ЭВМ.
В работах, написанных в соавторстве, лично автором диссертацииразработаны и описаны методы аппроксимации и интегрирования функций одной переменной с использованием детерминированных хаотических ото бражений [2,3,4,5]; выполнено сравнение затрат характеристик разработанных и известных методов аппроксимации и интегрирования [6,7]; исследовано их применение к обработке временных рядов в социально-экономических систе- (41 мах [1,8] и созданы программные средства обработки функций одной пере- менной [9].
Структура и объем работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 140 страницах машинописного текста, содержит 51 рисунок, 7 таблиц, список литературы из 82 наименований и 8 приложений объемом 72 страницы. Общий объем 221 страница.
Во введении выполнено обоснование темы, сформулированы цель и задачи диссертационного исследования, научная новизна, практическая 1 ценность, апробация и реализация результатов работы, публикации по теме диссертации, структура и объем диссертации.
В первой главе выполнен обзор используемых в экономических и социальных системах методов обработки таблично заданных функций одной переменной (в дальнейшем ФОП), в том числе в рамках эконометрики и математической социологии. Определены источники информации для эконометрических и социологических исследований. Приводятся особенности измерений, погрешности и форм закономерностей при обработке временных рядов.
Рассмотрены и проанализированы известные способы обработки таб лично заданных ФОП: методы глобальной и локальной аппроксимации, построение эмпирических формул и алгоритмы численного интегрирования. Поскольку выявленные в процессе научного исследования закономерности являются определенного рода сжатием информации об изучаемых объектах, V*' в главе содержатся характеристики методов сжатия информации. заданных ФОП с использованием положений хаотической динамики. За счет строгой повторяемости ряда, порождаемого дискретным хаотическим отображением при одинаковых стартовых условиях, открывается возмож ность заменять часть узлов исходной последовательности данных на по следовательность значений отображения, промасшабированную с коэф фициентом, значение которого зависит от выбранной погрешности вычис- ^ лений. Поэтому математическое выражение хаотического процесса (ото- бражение) можно использовать как память. Это позволяет уменьшить погрешность результатов по сравнению с локальной интерполяцией, которая была взята за основу в реализованном методе, и расширить интервалы интерполяции для сокращения памяти, требуемой для хранения всех значений таблично заданной функции.
Предлагаемый подход может быть использован при численном вы числении интегралов, если заменить интегрируемую ФОП обработанной Ч разработанным методом приближения последовательностью.
Вторая глава содержит положения хаотической динамики, используемые в предлагаемых методах аппроксимации и интегрирования таблично заданной ФОП, и анализ предметной области.
Выбор средств хаотической динамики в виде дискретных отображений для реализации метода аппроксимации определяется такими характеристиками: строгой повторяемостью генерируемых числовых последовательностей при задании равных стартовых значений и низким уровнем вычислительной сложности реализации отображений.
В главе приведены математические выражения методов обработки таблично заданных ФОП и способы расчета их погрешностей. Рассмотрены методы глобальной и локальной интерполяции, приводятся способы упрощения этих методов.
В главе также рассматриваются широко используемые для числен ую' ного интегрирования квадратурные формулы и приводится расчет по грешностей при их применении.
В третьей главе выполнено поэтапное построение алгоритмических моделей сжатия и восстановления исходных зависимостей в рамках созданного метода аппроксимации и алгоритмизация разработанных методов аппроксимации и интегрирования таблично заданной ФОП с использованием положений хаотической динамики. Приведены блок-схемы созданных методов и описание их программной реализации.
Разработанные методы позволяют производить вычисления с регулируемой погрешностью и расширять интервалы обработки для сокращения памяти, требуемой для хранения всех значений таблично заданной функции.
При интегрировании с использованием разработанного подхода исходная таблично заданная зависимость заменяется на полученную с помощью числового детерминированного хаотического ряда, и производится вычисление определенного интеграла как суммы элементарных площадей, ограниченных сверху найденной последовательностью.
В главе приведено описание, назначение и взаимодействие модулей разработанной на основе предлагаемого метода программы. Описаны входные и выходные данные, рассмотрены процедуры обработки программного продукта.
Программа позволяет: работать с таблично и аналитически заданными функциями; обрабатывать ФОП с использованием методов хаотической динамики на основе линейного приближения; подсчитывать коэффициент сжатия данных; сохранять обработанные данные и восстанавливать приближаемые функции с указанной погрешностью из файла результатов; выполнять расчет и построение графиков зависимости объемов памяти от погрешности обработки для предлагаемых алгоритмов и традиционных методов приближения и интегрирования.
В четвертой главе выполнен сравнительный анализ показателей работы реализаций известных и разработанных методов по вычислительной сложности, затратам памяти, погрешности и времени обработки.
Для оценки вычислительной сложности были выполнены сравнения характеристик разработанных и известных методов интерполирования и интегрирования. Опыты на основе разработанного программного обеспечения показали, что созданный алгоритм аппроксимации по числу выполняемых операций имеет преимущество по отношению к алгоритму, реализующему метод наименьших квадратов, до 6 раз, а по затратам времени - до 7 раз. Алгоритм интегрирования превосходит по скорости в 1,3 раза известные методы нахождения определенных интегралов (прямоугольников и трапеций).
Рассчитана память, необходимая для хранения исходной числовой последовательности, и выполнено ее сравнение с памятью, затрачиваемой для хранения преобразованной с помощью предлагаемого метода приближений числовой последовательности с погрешностью метода s.
Произведено сравнение погрешности, получаемой с помощью линейной интерполяции и предлагаемого метода аппроксимации. Как показали эксперименты, при одинаковых затратах памяти у предлагаемого метода меньшая погрешность по сравнению с локальной интерполяцией.
Сравнение характеристик методов интегрирования проводилось с известными методами численного нахождения интегралов. На основании проведенных экспериментов можно сделать вывод о том, что при одинаковых затратах памяти на хранение подынтегральной таблично заданной функции погрешность расчета интеграла ниже в случае, если подынтегральная функция обработана предлагаемым методом.
В главе рассмотрены примеры на сжатие, интерполирование и интегрирование данных, использующие эконометрические и социологические информацию.
В заключении приводятся основные результаты диссертационного исследования.
В приложениях приводятся результаты сопоставительного анализа созданных и известных методов и листинги разработанного программного продукта.
Обзор и анализ результатов использования степенных рядов при аппроксимации для уменьшения вычислительной погрешности
В ряде случаев сложные теоретические зависимости аппроксимируют относительно простой эмпирической формулой, позволяющей быстро, но приближенно, производить необходимые вычисления.
Задача построения эмпирической формулы отлична от задачи интерполирования тем, что не требуется совпадения значений измеряемой зависимости и полученной эмпирической формулы в узлах. Достаточно, чтобы их разность не превышала выбранной погрешности [40, 42]. Поэтому при прочих равных условиях сложность эмпирической зависимости будет ниже, чем у аппроксимирующей, так как первая не обязана точно попадать в узловые точки. Иногда это бывает оправдано, так как исходные данные, как правило, являются приближенными и содержат ошибки. Экспериментальные данные в некоторой і степени сглаживаются, а интерполяционная формула повторила бы все ошибки, имеющиеся в экспериментальных данных.
Приближение данных эмпирическими формулами состоит из двух этапов. Первым является определение типа формулы. Если неизвестен характер зависимости между величинами х и у, то вид эмпирической формулы является произвольным. Предпочтение отдается простым формулам с низкой погрешностью. Если отсутствуют сведения о промежуточных данных, то обычно предполагается, что эмпирическая функция не имеет точек разрыва и график ее - плавная кривая. Нет общего метода для нахождения наилучшего типа формулы, соответствующей приближаемым данным. Результат в значительной мере определяется опытом и интуицией исследователя, что следует отнести к недостаткам указанного метода. В некоторых случаях выбор типа эмпирической формулы может быть произведен на основе теоретических представлений о характере изучаемой зависимости [48].
Вторым этапом построения эмпирической формулы является определение ее параметров на основе минимизации расстояний между реальными и приближаемыми значениями во всех узлах, исходя из чего строятся системы уравнений и находятся искомые параметры. На этом основаны метод выбранных точек [40, 48] и метод средних [35, 36]. Для уточнения эмпирической формулы вводят постоянную величину так, чтобы сумма квадратов новых уклонений была минимальной. Это увеличивает количе ство вычислений, а, следовательно, и погрешность [40, 43]. Если число параметров эмпирической формулы превышает число уравнений, из которых их можно найти, рассчитывают грубые значения искомых параметров и вводят для них поправки невязки. Это усложняет вычисления и, следовательно, увеличивает погрешность результата. С Рассмотренные методы определения параметров эмпирической фор мулы являются сравнительно простыми, но получаемые с их помощью fa аппроксимации не обеспечивают требуемой погрешности и не является однозначно определенными [40]. Эти алгоритмы используют в тех случаях, когда точность исходных данных относительно невелика [35, 43]. Выявленные в процессе научного исследования закономерности яв ІУ ляются определенного рода сжатием информации об изучаемых объектах, имеющейся в распоряжении исследователя. Виды такого сжатия весьма разнообразны [1, 54, 55]. Сжатие информации является одним из самых динамически развивающихся направлений и используется в различных областях науки и техники, где требуется хранение и передача информации. Во-первых, это связано со все еще достаточно высокой стоимостью носителей информации (магнитные и оптические диски, ПЗУ, ОЗУ и т.д.), во-вторых, с необходи-мостью передачи больших потоков информации по перегруженным линиям связи (радио- и оптическая связь, телефония, сети). Универсального алгоритма сжатия данных не существует и для каждой конкретной задачи имеется свой наиболее эффективный метод. Применение нерационально выбранного алгоритма может привести к противоположному результату в виде увеличения потока информации [23,27, 56]. Традиционными методами сжатия являются перекодировка и упа-ковка информации [54, 55]. Под перекодировкой понимают любое представление исходной информации, при котором ее можно восстановить и которое занимает меньший физический объем на носителе. Примером перекодировки являются общепринятые условные обозначения, такие как я (вместо 3,1415...); 1/3 (вместо 0,3333....); оператор математического ожидания М; обозначения для единичных, диагональных, нулевых и прочих матриц; сокращения: MS-DOS, FAT, модем и т.д. Запись программы в исходных текстах тоже может рассматриваться как способ архивации: если программа написана на языке высокого уровня, то ее текст обычно меньше размера исполняемого файла и поэтому несколько килобайт кода могут быть представлены одной строкой [55-58]. Если путем изменения местоположения и взаимного расположения носителей информации удается сократить ее объем, то такой процесс считают упаковкой. Это один из самых старых и популярных способов сжатия информации. Он отличается простотой и высокой скоростью работы. Такую процедуру выполняет архиватор RAR при создании так называемых 5Ы//-архивов, выигрывая на этом несколько процентов в степени сжатия [59-62]. Существуют методы сжатия информации без потерь и с потерями. Сравнительные характеристики методов сжатия без потерь приведены в таблице 1.1 [55, 56, 63-65]. Одним из видов информации являются числовые данные. Особое положение среди числовых данных занимают одномерные массивы, представляющие собой временную последовательность значений какого-нибудь процесса [55, 60-62], т.к. любой динамический процесс, в т.ч. в социально-экономических системах, характеризуется большим количеством исследуемых характеристик. Это делает особо актуальным способы обработки хранимой и передаваемой информации.
Использование степенных рядов при аппроксимации для уменьшения вычислительной погрешности
За счет замены части исходных узлов на сгенерированный детерминированными отображениями ряд объем аппроксимированной последовательности имеет обратную зависимость от рабочей погрешности метода s.
Разработанный подход использования свойств детерминированных отображений может быть использован для расчета определенного интеграла таблично заданной ФОП.
Таким образом, была решена задача по разработке метода аппроксимации ФОП со следующими свойствами: возможностью сжатия исходной последовательности; процесс аппроксимации может быть начат до получения всей таблично заданной ФОП; для приближения не требуется расчет производной исходной функции; количество рассчитываемых коэффициентов равно количеству баз аппроксимации; обеспечивается регулируемая погрешность вычислений; не требуется дополнительных операций по перераспределению узлов; ошибочные точки незначительно влияют на результат приближения.
Предлагаемый подход использования свойств детерминированных хаотических отображений может быть применен к вычислению определенного интеграла таблично заданной ФОП.
В случае, когда вид подынтегральной функции не допускает непосредственного интегрирования, т.е. первообразную нельзя выразить в элементарных функциях, используются методы численного интегрирования [43, 50]. Универсальными методами являются методы численного интегрирования, основанные на аппроксимации подынтегральной функции с помощью интерполяционных многочленов. Рассмотрим использование кусочной (локальной) интерполяции. В этом случае определенный интеграл заменяют интегральной суммой:
Причем, длина наибольшего из элементарных отрезков Ах стремится к нулю. Это приводит к требованию увеличения числа узлов исходной по-следовательности, что увеличивает затраты памяти на их хранение. Простое уменьшение числа узлов с целью сокращения требуемой для их хранения памяти приводит к увеличению шага Ах и, следовательно, к росту погрешности вычислений.
При оценке эффективности квадратурных формул наиболее трудоемкой операцией часто является нахождение значения подынтегральной функции f. Поэтому предпочтительней является формула, в которой ис-пользуется меньшее число узлов [43,44].
Предлагаемый подход использования свойств детерминированных хаотических отображений может быть применен при интегрировании следующим образом. Поскольку геометрически определенный интеграл на отрезке [а, Ь] - это площадь, ограниченная прямыми у=0, х=а, х=Ь и подынтегральной функцией (выражение 3.16)), исходная таблично заданная ФОП заменяется на полученную с помощью числового детерминирован-ного хаотического ряда согласно выражению (3.14) и методу, описанному в разделе 3.1 (рис. 3.13). Применение предлагаемого метода позволяет сократить число узлов исходной последовательности, необходимых для обеспечения требуемой погрешности расчета определенного интеграла.
Ниже приведена методика сравнения расчета определенного интеграла с помощью разработанного метода интегрирования и известных методов (прямоугольников и трапеций). Исходная (подынтегральная) функция может быть задана аналитически или таблично. Если она задана аналитически, разработанный алгоритм может быть использован как численный.
В опыте вначале с использованием рабочей погрешности є на основе исходной функции рассчитывались базы (раздел 3.1) (см. рис. 3.2). После этого искомый определенный интеграл может быть представлен как сумма площадей, ограниченных снизу осью х, справа и слева вершинами базы, сверху - исходной последовательностью. Затем рассчитывалось значение площади (интеграла) каждой базы с максимально низкой погрешностью, которое принималось за эталонное. Если исходная функция задана таблично, то площадь может быть найдена традиционными квадратурными методами (прямоугольников, трапеций, Симпсона). Если функция задана аналитически, то интеграл может быть найден точно с помощью формулы Ньютона-Лейбница. Следующим действием находились элементарные площади, ограниченные снизу осью х, справа и слева вершинами базы, сверху - последовательностью, полученной с помощью детерминированного хаотического ряда, которые сравнивались с полученными ранее эталонными значениями на тех же участках (рис. 3.14).
С эталонными значениями площадей сравнивались значения площадей на участке каждой базы, ограниченные снизу осью х, справа и слева вершинами базы, сверху отрезком, проходящим через узлы рассматриваемой базы, если проводился расчет по методу трапеций, или прямой, проходящей через точку с абсциссой x=Xk-xt, рассматриваемой базы и лежащей на отрезке, соединяющей начало и конец базы, если сравнение производилось по методу прямоугольников (рис. 3.15).
Следовательно, при расчете элементарных площадей, как в случае использования разработанного метода интегрирования, так и в случае применения для расчетов известных методов прямоугольников и трапеций, использовалось равное количество узлов.
Алгоритмизация метода интегрирования числового ряда
Аппроксимация таблично заданной ФОП может быть рассмотрена как способ сжатия числового ряда, что очень важно при исследовании и анализе информации управления [16,23].
Обработка последовательности цифровых данных в дискретные промежутки времени в разработанном методе аппроксимации включает сжатие и восстановление первоначальной информации с выбранной погрешностью. Рассмотрим, во сколько раз возможно сокращение затрат памяти для хранения исходной и преобразованной с помощью предлагаемого метода аппроксимации таблично заданной ФОП.
Для наилучшего отображения результатов эксперимента и возможности выбора произвольного количества узлов в таблично заданной ФОП предложен следующий подход. Был выбран ряд функций с различными участками возрастания и убывания на области значений. Среди выбранных зависимостей были рассмотрены наиболее часто используемые в социально-экономических системах согласно [1]. Затем определялась погрешность метода для аппроксимации. После этого значения аргумента и функции рассчитывались с некоторым выбранным шагом на произвольных отрезках из области определения аппроксимируемой последовательности. Такой подход позволяет промоделировать таблично заданную ФОП с любым количеством элементов и постоянным шагом.
Были выбраны функции, имеющие практически гладкие участки на некоторых отрезках областей значений (например, у=1/(х+1), y=ln(x+JJ) и периодические с отрезками резкого возрастания и убывания (например, y=sin(x)/(100ln(x)), y=4sin{x)cos{x)). В процессе проведения экспериментов на затраты памяти изменялось значение рабочей погрешности аппроксимации є промоделированной таблично заданной ФОП. Расчеты производились для значений рабочей погрешности от 0,01 до 0,000000001. Часть результатов экспериментов по показателям сжатия, рассчитанных по формуле (3.16), приведена в таблице 4.1. На заданном отрезке изменений аргумента функции выбирался шаг задания ее значений. Для эксперимента были выбраны значения шага, равные 1/500; 1/3000; 1/6000, то есть на выбранном отрезке аппроксимации исходная цифровая последовательность состояла из 500; 3000 и 6000 узлов. Было выполнено исследование последовательностей с постоянным шагом, потому что для экономических приложений наиболее типична ситуация, когда моменты времени, в которые производится регистрация значений анализируемых признаков, являются равноотстоящими [27]. Параметры сжатия рассчитывались при использовании отображений Хенона, «Иллюстрации Лоренца» и TentMap.
В таблице 4.1 для сравнения приведены значения сжатия для хранения аналогичной информации при использовании округления и для применения метода Хаффмана, сравнение с которым выполнялось потому, что для сжатия числовых последовательностей традиционно используются методы сжатия без потерь, каким является метод Хаффмана. Сжатие при округлении рассчитывалось следующим образом: объем памяти, требуемый для хранения исходной последовательности с погрешностью 0,000000001, делился последовательно на затраты памяти на хранение последовательности с погрешностью, равной 0,00000001; 0,0000001; 0,000001; 0,00001; 0,0001; 0,001 и 0,01. Результаты исследования других функций проведены в Приложении 1.
Показатели сжатия при реализации разработанного метода аппроксимации и созданной в его рамках модели сжатия увеличиваются при уменьшении требований к погрешности метода и увеличении числа узлов внутри исследуемого интервала, что объясняется большим количеством узлов, заключаемых в каждую из баз при обработке.
В случаях, если функция возрастает или убывает резко (ордината каждого последующего узла значительно отличается от ординаты предыдущего узла), коэффициент сжатия ухудшается и может дать значение меньше единицы, т.е. файл, хранящий обработанную последовательность, будет занимать больше места в памяти, чем файл с исходным числовым рядом.
При обработке гладких возрастающих или убывающих (в т.ч. и периодических) функций при погрешности больше 0,00001 предложенная обработка превосходит результаты сжатия метода Хаффмана, при погрешности больше 0,000001 - округление. Сокращение затрат памяти наибольшее, чем менее резко возрастает или убывает изучаемая зависимость, т.е. чем меньше ордината каждого последующего узла отличается от ординаты предыдущего.
Проведенные опыты показали, что коэффициент сжатия предложенного метода аппроксимации растет при увеличении количества узлов исходной последовательности внутри рассматриваемого интервала, причем этот вывод не зависит от использованного для аппроксимации отображения. Это важно при исследовании больших динамических систем.
Из таблицы 4.1 видно, что рассчитанные по формуле (3.16) коэффициенты сжатия исходной числовой последовательности напрямую зависят от погрешности метода є. Например, на рис. 4.1 изображен этап работы про Ill
граммной реализации предлагаемого метода аппроксимации при следующих исходных данных: исследуемая функция 1п(1+х); рабочая погрешность е=0,01; отрезок из области определения [3; 10]; узлы функции рассчитывались с шагом 1/500, при обработке использовалось отображение TentMap, по осям отложены значения функции и аргумента исследуемой ФОП: С помощью подобной функции могут быть промоделированы явления в социальных и экономических системах, имеющие тенденции к росту, например, рост биржевых котировок в течение торговой сессии.
Сравнительный анализ скоростных характеристик и оценка вычислительной сложности
Разработанная программа позволяет строить зависимость затрат памяти, необходимых для хранения подынтегральной функции (исходной и обработанной предлагаемым алгоритмом интегрирования), от погрешности.
Сравнение проводилось с реализациями известных методов численного интегрирования - прямоугольников и трапеций.
Для проведения эксперимента и моделирования числового ряда произвольной длины выбиралась функция, например, у=1/(х+1); отрезок из области ее определения, например, [3; 10]; диапазон изменения шага, с которым рассчитывались узлы исходной числовой последовательности, например, от 100 до 500; приращение, с которым изменялся шаг при построении графика, например, 5; а также рабочая погрешность, например, 0,001; хаотическое отображение, например, «Иллюстрация Лоренца». Изменяя с помощью приращения количество узлов исходного ряда, рассчитывалась память, требуемая для хранения каждой из получаемых последовательностей. По результатам расчетов в программной реализации возможно построение графика зависимости погрешности вычислений от затрат памяти (в байтах) (рис. 4.15). На рис. 4.15 отображен график для вышеприведенных данных.
На рис. 4.16 отображены результаты эксперимента при следующих исходных данных: выбранная функция y=sin(x)/(100exp(x))\ отрезок из области ее определения [3;10]; диапазон изменения шага от 100 до 500; приращение изменения шага 5, погрешность метода 0,001.
Другие опыты по сопоставительному анализу зависимости погрешности от затрат памяти на хранение подынтегральной функции представлены в Приложении 6.
На основании проведенных экспериментов можно сделать вывод о том, что при одинаковых затратах памяти на хранение подынтегральной таблично заданной ФОП погрешность расчета интеграла была ниже в случае, если подынтегральная функция обработана реализацией предлагаемого метода. Погрешность выше, если к узлам начала и конца баз, рассчитанных с учетом погрешности є, применялись известные численные методы интегрирования - прямоугольников и трапеций.
Коэффициент сжатия исходной подынтегральной таблично заданной ФОП, получаемый с помощью выражения (3.15) для случая интегрирования, аналогичен соответствующему коэффициенту, рассчитываемому при интерполяции.
С помощью разработанного программного обеспечения возможно выполнять сравнение зависимостей времени интегрирования от погрешности для разработанного алгоритма и реализацией методов трапеций и прямоугольников. На рис. 4.17 приведен пример такого анализа для следующих исходных данных: функция 29-х15+78-х10+11ос5+90-х; начало отрезка интегрирования х0 10; шаг изменения аргумента ir=0,001; число узлов ряда N=500; правило изменения погрешности Cj+i=Sj+0,00001; М=10.
Для выполнения сравнения изменялись значения погрешности вычислений, рассчитывалось время нахождения определенного интеграла. Шире результаты экспериментов по сравнению временных характеристик приведены в Приложении 7. Анализ показал, что некоторые значения погрешности, которые обеспечивает предложенный алгоритм интегрирования, недостижимы при использовании алгоритмов прямоугольников и трапеций, что можно отнести к достоинствам созданного метода. Он превосходит по скорости в 1,3 раза известные методы нахождения определенных интегралов (прямоугольников и трапеций). С помощью интегрирования в экономике и социологии можно находить различные показатели. В частности, это позволяет делать прогнозы в промежутках между измерениями.
Для иллюстрации применения разработанного метода интегрирования с использованием социометрической информации рассмотрим пример с социологическими данными. В таблице 4.3 представлена динамика рождаемости в одном из роддомов г. Москвы по годам и месяцам (источник информации сайт http://www.mariamm.ru).
