Содержание к диссертации
Введение
ГЛАВА 1. Обзор и анализ методов сплайн-функций, математических сплайновых моделей и программныхкомплексов, содержащих сплайны 14
1.1. Сплайны как универсальный метод моделирования числовых данных 14
1.2. САПР и ГИС как основные применения сплайнов в вычислительных приложениях
1.2.1. САПР как прикладная сфера использования интерполяционных сплайнов 36
1.2.2. ГИС как прикладная сфера использования интерполяционных сплайнов 39
1.3. Объектно-ориентированная реализация общей задачи сплайновой интерполяции 43
Выводы по главе 1 44
ГЛАВА 2. Основные задачи, решаемые при разработке методических основ обобщённой объектно-ориентированной технологии построения сплайн-функций 46
2.1. Унифицированный подход к моделированию интерполяционными сплайн-функциями, заданными на линейных оболочках 46
2.2. Построение сетки узлов склеивания как задача моделирования, решаемая на предварительном этапе сплайновой интерполяции 52
2.3. Построение биортогонального базиса как основной методический этап технологии моделирования обобщёнными сплайнами 59
2.4. Построение и решение систем линейных уравнений как основной методический этап технологии моделирования обобщёнными сплайнами 68
2.5. Интерполяция при решении практических задач и L-сплайны как обобщённый метод моделирования 2.5.1. Интерполяция данных об изменении свойств титана при нагревании 76
2.5.2. Интерполяция данных о режиме биений при вынужденных колебаниях вблизи резонанса и при резонансе 77
2.5.3. Интерполяция образующей сечения замкнутой ёмкости цилиндрической
формы с эллиптическими днищами 78
Выводы по главе 2 80
ГЛАВА 3. Алгоритмы, численные методы и их модификации, используемые при реализации основных методических блоков обобщённой объектно-ориентированной технологии построения сплайн-функций 82
3.1. Методы решения задачи построения сетки узлов склеивания, не совпадающих с точками исходных данных 82
3.1.1. Решение задачи построения сетки узлов склеивания с помощью генетического алгоритма 83
3.1.2. Решение задачи построения сетки узлов склеивания с помощью аналитического метода з
3.2. Модификации алгоритма вычисления производных высоких порядков в условиях объектно-ориентированного подхода 101
3.3. Методы объектно-ориентированной реализации основных этапов технологии построения обобщённого одномерного сплайна. Качественные тесты 109
3.4. Метод последовательных L-сплайновых приближений 115
3.5. Адаптация классов для работы с большими числами к выполнению расчётов сплайновых моделей с экспоненциальными функциональными
составляющими 123
Выводы по главе 3 130
ГЛАВА 4. Реализация основных структурных компонент программного комплекса «моделирование и обработка числовых данных с помощью интерполяционных сплайнов» 132
4.1. Архитектура программного комплекса «Моделирование и обработка данных с помощью интерполяционных сплайнов» 132
4.2. Реализация технологии построения интерполяционных сплайнов, заданных на линейных оболочках
4.2.1. Класс производных высших порядков сложных функций 137
4.2.2. Классы, реализующие построение интервальных представлений сплайновых моделей 142
4.3. Реализация методов расчёта сетки узлов склеивания для построения сплайн функций 147
4.3.1. Классы для поддержки процедур случайного выбора в схеме генетического алгоритма 148
4.3.2. Модуль, реализующий аналитический метод построения сеток узлов склеивания сплайн-функций
4.4. Класс больших рациональных чисел 156
4.5. Основные компоненты интерфейса программного комплекса 159
Выводы по главе 4 168
Заключение 171
Список сокращений 175
Список использованной литературы
- САПР как прикладная сфера использования интерполяционных сплайнов
- Построение сетки узлов склеивания как задача моделирования, решаемая на предварительном этапе сплайновой интерполяции
- Решение задачи построения сетки узлов склеивания с помощью генетического алгоритма
- Модуль, реализующий аналитический метод построения сеток узлов склеивания сплайн-функций
Введение к работе
Актуальность темы диссертации. Задача выбора математического метода является типичной проблемой, с которой периодически сталкиваются все пользователи прикладных пакетов моделирования. Это объясняет существование огромного количества работ по тематике математического моделирования, разработке новых методов, вариаций и модификаций существующих, а также неослабевающий интерес исследователей к этой задаче, и к настоящему времени предложены различные методы и алгоритмы построения сплайнов и разработаны многочисленные подсистемы машинной графики и геометрического моделирования, занимающие центральное место в машиностроительных САПР. Актуальность задачи поиска эффективных методов моделирования сплайн-функциями и разработки соответствующих алгоритмов подтверждается фактом проведения с 1998 г. российских и международных конференций по методам сплайн-функций, в том числе конференция «Методы сплайн-функций», посвя-щнная 80-летию со дня рождения Ю.С. Завьялова (31 января – 2 февраля 2011 г.), на которой было представлено 54 доклада.
Существует огромное количество работ по тематике математического моделирования, разработке новых методов, вариаций и модификаций существующих, а также неослабевающий интерес исследователей к этой задаче. Можно констатировать, что на сегодняшний день отсутствуют общепризнанные и неоспоримые критерии выбора того или иного метода моделирования для решения конкретной прикладной задачи, и продолжение исследований в этом направлении по-прежнему стоит в повестке дня.
Проблеме практического использования сплайновых методов интерполяции посвящены сотни фундаментальных монографий и учебных пособий (Дж. Алберг, В. Нильсон, Дж. Уолш, К. де Бор, Завьялов Ю.С., Квасов Б.И., Мирошниченко В.Л., Василенко В.А. и др.), а также диссертационных исследований в России (Иванченко А.Н., Романовский Л.М., Мирошниченко П.В., Орлов С.Е., Богданов В.В., Крымова Е.А., Плавник А.Г., Ромакина О.М., Макаров А.А. и др.) и за рубежом (G. Muntingh, B.T.T. Yeo, A.P. Sibileau и др.). Для решения прикладных задач моделирования предлагают использовать как классические методы (кубические, полиномиальные сплайны и различные их модификации), так и специализированные для решения того или иного типа задач (локально-аппроксимационные сплайны, нелокальная сплайновая интерполяция, минимальные сплайны лагранжева типа и т.д.).
Отсутствие универсальных критериев выбора того или иного сплайново-го метода для решения каждой конкретной прикладной задачи, имеющих высокую степень математической строгости и учитывающих последующую компьютерную реализацию, делает актуальной задачу разработки системы с максимальным охватом теоретически возможных конструкций, получаемых в результате моделирования методами сплайн-функций, а также реализующей максимально унифицированный подход к построению сплайн-функций с учтом се-
годняшних реалий их применения на практике – объектно-ориентированные языки программирования, использование шаблонных конструкций.
Заслуживает внимания идея обобщения различных методов и алгоритмов при построении общей схемы моделирования сплайн-функциями. Как показал обзор публикаций, наиболее естественным способом обобщения является выделение трх основных стадий, являющихся общими при построении различных сплайн-функций: подготовка исходных данных для моделирования – задание недостающих условий, построение интерполяционной сетки; выбор базиса – набора линейно независимых функций для построения линейной оболочки; непосредственное построение сплайновой модели – вычисление значений коэффициентов для отрезков, получение расчтных формул сплайн-функции.
В постоянном развитии находится рынок систем автоматизированного проектирования и геоинформационных систем. Верхние строчки мировых рейтингов занимают такие отечественные и зарубежные разработки в области САПР, как ArchiCAD (Graphisoft, Nemetschek, Германия), ArCon «Архитектура и дизайн» (Еврософт, Россия), и ГИС – ArcGIS (ESRI, США), GRASS GIS (U.S. Army Corps of Engineers, США) и другие.
Вс это свидетельствует об актуальности проведения теоретических и прикладных исследований по тематике сплайновых методов моделирования, а также построению эффективных компьютерных реализаций разрабатываемых методов и алгоритмов.
Диссертационная работа выполнена в рамках научного направления ЮР-ГПУ (НПИ) «Теория, принципы и технологии построения информационно-вычислительных и измерительных систем» (утверждено решением ученого совета университета от 20.09.2011 г.).
Целью диссертационной работы является разработка и исследование математических моделей, а также методов, алгоритмов, программных модулей и комплексов для моделирования и обработки числовых данных с помощью унифицированной технологии построения интерполяционных сплайнов.
Задачи диссертационной работы:
-
Выполнить содержательный анализ и систематизацию методов сплайн-функций; выявить методические особенности и свойства, являющиеся общими для существующего многообразия сплайновых методов. Разработать унифицированную методику, учитывающую смысловую общность основных алгоритмических этапов, выполняемых при построении сплайн-функций.
-
Выполнить формализацию основных алгоритмических этапов, составляющих процесс построения сплайн-функций; для каждого этапа определить арсенал используемых математических методов, реализующих этот этап, и обосновать необходимость разработки или модификации используемых методов для обеспечения корректности работы технологии, основанной на унифицированной методике построения сплайн-функций.
-
Реализовать математические методы, выполняемые на каждом из этапов унифицированной технологии построения сплайн-функций, с использова-
нием основных принципов объектно-ориентированного программирования. С помощью качественных тестов показать корректность работы программных модулей, реализующих последовательные этапы моделирования.
-
Реализовать методы построения параметрических сплайновых конструкций с использованием ручного управления параметрами для реализации возможности расчта сплайновых моделей, а также корректировки числовых и функциональных параметров пользователем в интерактивном режиме, и автоматического управления параметрами для реализации возможности решения задач построения гладких сплайновых приближений с заданной точностью средствами унифицированной технологии построения сплайн-функций с программным расчтом значений числовых параметров.
-
Разработать общую структуру вычислительного ядра программного комплекса моделирования интерполяционными сплайнами – иерархию классов, реализующих основные этапы технологии построения сплайн-функций, а также ряд вспомогательных классов для обеспечения работоспособности вычислительного ядра, и реализовать с использованием парадигм обобщнного и объектно-ориентированного программирования.
-
Разработать и реализовать интерфейс программного комплекса моделирования интерполяционными сплайнами, позволяющий организовать интерактивное взаимодействие с пользователем посредством формирования списков для выбора значений числовых и функциональных параметров сплайнов из списка возможных значений, а также визуализации результатов выполнения последовательных этапов построения сплайн-функций, позволяющей выполнять пользовательскую оценку и планировать дальнейшие манипуляции с параметрами сплайн-функций с целью улучшения качественных свойств модели.
7. Разработать общую структуру программного комплекса моделирования
интерполяционными сплайнами с организацией взаимодействия вычислитель
ного ядра и интерфейса и реализовать посредством написания системных про
цедур, выполняющих обмен параметрами с проверкой корректности построе
ния передаваемого набора.
Методология и методы исследования. Для решения поставленных в работе задач использованы методы математического и компьютерного моделирования, линейной алгебры, вычислительной математики и компьютерной графики, реализующие различные стадии многоэтапного процесса построения интерполяционных сплайнов: обобщнные методы вычисления производных высоких порядков на основе формул Фаа-ди-Бруно для построения биортогонально-го базиса сплайна; алгоритмы решения СЛУ специального вида с привлечением соответствующих численных методов для расчта биортогональных базисных коэффициентов сплайна; модификация генетического алгоритма с репродукцией со случайной маской для вычисления положения узлов склеивания; корреляционный анализ отклонений параметрических сплайнов для прогнозирования оптимального значения параметра при построении сплайновых моделей, удовлетворяющих заданным критериям точности и гладкости; метод БВЕ для быст-
рого вычисления экспоненциальных функций с большими значениями показателя; язык C++ как средство реализации вычислительного ядра программного комплекса с организацией иерархической структуры классов на основе концепции обобщнного программирования. Визуализация результатов моделирования выполняется посредством парсинга формульных представлений базисных функций и организации межязыкового обмена численной информацией между вычислительным ядром и графическим Java-редактором.
Достоверность научных результатов и выводов подтверждается корректностью постановок задач, обоснованностью принятых допущений, корректным применением известных теоретических положений, методов и алгоритмов, устойчивой работой разработанного программного обеспечения и результатами численных экспериментов на модельных примерах.
Объектом исследования диссертационной работы являются методы сплайн-функций, их применение для обработки числовых данных.
Предметом исследования являются математические модели, методы и алгоритмы построения сплайн-функций, а также программные комплексы, использующие методы сплайн-функций для построения математических моделей.
Тематика работы соответствует п.2 «Развитие качественных и приближенных аналитических методов исследования математических моделей», п.3 «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий» и п.4 «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента» паспорта специальности 05.13.18 – «Математическое моделирование, численные методы и комплексы программ».
Научная новизна. В диссертации получены следующие новые научные и практические результаты:
в области математического моделирования:
предложен новый общий конструктивный подход к построению интерполяционных сплайнов, отличающийся от существующих использованием формы разложения сплайна по функциям, образующим биортогональный базис, что позволяет непосредственно использовать интерполяционные условия в качестве коэффициентов сплайна;
предложен способ выбора узлов склеивания сплайн-функций, отличающийся от известных способов систематическим подходом, обеспечивающим принадлежность узлов склеивания соответствующим интервалам и одинаковость относительного расположения узлов склеивания, что позволяет упростить задачу интерполяции за счет сохранения единства биортогонального базиса;
в области численных методов:
- предложен метод одновременного вычисления производных высоких
порядков от сложных функций и выбран эффективный алгоритм для объектно-
ориентированной программной реализации метода, отличающийся от сущест
вующих использованием общих формул вычисления производных высоких по-
рядков от сложных функций;
- впервые предложен метод построения гладкого сплайнового приближе
ния с заданной точностью на основе автоматического управления параметрами
базисных функций L-сплайнов с использованием корреляционной зависимости
между набором специальным образом конструируемых контрольных функций
и величиной максимального отклонения анализируемой модели от исходной,
что позволило исключить необходимость ручного подбора параметров;
в области комплексов программ:
- предложена оригинальная структура инструментального программного
комплекса «Моделирование и обработка числовых данных с помощью интер
поляционных сплайнов», позволяющая проводить научные исследования с со
держательным анализом различных сплайновых методов.
Основные положения, выносимые на защиту.
1. Общий конструктивный подход к построению интерполяционных
сплайнов с использованием формы разложения сплайна по функциям биорто-
гонального базиса (соответствует п.2 паспорта специальности – Развитие каче
ственных и приближнных аналитических методов исследования математиче
ских моделей).
-
Систематический подход к выбору узлов склеивания сплайн-функций, упрощающий задачу интерполяции за счт сохранения единства биортогональ-ного базиса (соответствует п.2 паспорта специальности – Развитие качественных и приближнных аналитических методов исследования математических моделей).
-
Реализация обобщнного метода одновременного вычисления производных высоких порядков от сложных функций в виде шаблонного класса, позволяющего одновременно возвращать значения функции и производных до заданного порядка в виде числового массива (соответствует п.3 паспорта специальности – Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий).
-
Метод последовательных L-сплайновых приближений с возможностью автоматического поиска параметров сплайна (соответствует п.3 паспорта специальности – Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий).
-
Реализация вычислительного ядра программного комплекса с использованием парадигм обобщнного и объектно-ориентированного программирования (соответствует п.4 паспорта специальности – Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента).
Теоретическая ценность работы.
Ценность научных работ состоит в том, что предложен, научно обоснован и практически реализован комплекс математических моделей, а также методов, алгоритмов и программных модулей для моделирования и обработки числовых данных с помощью интерполяционных сплайнов. Предложен и программно
реализован набор алгоритмов обработки числовых данных с использованием унифицированной технологии построения интерполяционных сплайнов, базирующейся на использовании оптимальных алгоритмов реализации основных вычислительных этапов, общих для существующего многообразия сплайн-функций.
Практическая ценность работы.
Практическая значимость исследования заключается в том, что на основе
разработанных методов и алгоритмов создано специальное программное
обеспечение – оригинальное вычислительное ядро программного комплекса
«Моделирование и обработка числовых данных с помощью интерполяционных
сплайнов», базирующееся на парадигмах обобщенного и объектно-
ориентированного программирования и обеспечивающее высокую надежность
и производительность в создании прикладных программных приложений за
счет повторного использования кода. Разработан инструментальный
программный комплекс «Моделирование и обработка числовых данных с
помощью интерполяционных сплайнов», позволяющий проводить научные
исследования с содержательным анализом различных сплайновых методов, в
том числе традиционно не используемых для решения определнного типа
практических задач моделирования; входящие в комплекс программы
зарегистрированы в Реестре программ для ЭВМ – «Набор классов для вычисле
ния производных высших порядков сложных функций» (свидетельство №
2014616948) и «Инструментальный программный комплекс исследования
свойств биортогональных базисов интерполяционных сплайнов»
(свидетельство № 2014660876).
Реализация результатов работы. Результаты диссертационной работы нашли практическое применение в АО ВНИГРИуголь при разработке структуры и содержания цифровых геологических моделей угольных объектов и программных средств моделирования, в ООО МИП «Композитспецмаш» при решении задач интерполирования профилей днищ оболочек наматывания и в учебном процессе ЮРГПУ (НПИ) имени М.И. Платова при реализации магистерских и бакалаврских программ по направлениям подготовки «Информатика и вычислительная техника» (09.03.01, 09.04.01), «Программная инженерия» (09.04.04, 09.03.04) и «Математическое обеспечение и администрирование информационных систем» (02.03.03).
Апробация работы. Основные положения и результаты
диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах:
1. IV конференция молодых учных «Геоинформационные технологии и
космический мониторинг» (НИИ механики и прикладной математики ЮФУ им.
И.И. Воровича, Ростов-на-Дону, 2011).
2. Международная молоджная конференция «Академические
фундаментальные исследования молодых учных России и Германии в
условиях глобального мира и новой культуры научных публикаций» (ЮРГТУ (НПИ), Новочеркасск, 2012).
3. II Международная научная конференция преподавателей, аспирантов,
магистров и студентов вузов «Наука. Образование. Культура. Вклад молодых
исследователей» (ЮРГТУ (НПИ), Новочеркасск, 2013).
4. VII Международная научная конференция «Вулканизм, биосфера и
экологические проблемы» (Институт вулканологии и сейсмологии ДВО РАН,
Майкоп-Туапсе, 2013).
-
XIII Всероссийское угольное совещание «Основные направления геологоразведочных и научно-исследовательских работ на тврдые горючие ископаемые в современных экономических условиях» (ВНИГРИуголь, Ростов-на-Дону, 2014).
-
XV Международная научно-практическая конференция «Теория, методы и средства измерений, контроля и диагностики» (ЮРГТУ (НПИ), Новочеркасск, 2014).
-
Международная научно-практическая конференция «Новые задачи технических наук и пути их решения» (АЭТЕРНА, Уфа, 2015).
8. VIII Международная научная конференция «Вулканизм, биосфера и
экологические проблемы» (Институт вулканологии и сейсмологии ДВО РАН,
Майкоп-Туапсе, 2016).
Публикации. По теме диссертации опубликовано 13 печатных работ, в том числе: 3 статьи в ведущих рецензируемых изданиях, рекомендованных ВАК; 2 свидетельства о государственной регистрации программ для ЭВМ; 8 публикаций по результатам международных и всероссийских научно-практических конференций.
Структура диссертации. Диссертация содержит 187 страниц основного текста, 21 рисунок, 19 таблиц и состоит из введения, четырех глав, заключения, списка сокращений, списка литературы из 191 наименования и 7 приложений объемом 44 страницы.
САПР как прикладная сфера использования интерполяционных сплайнов
В диссертации и статьях Богданова В.В. [32, 33, 34, 35] рассматриваются условия комонотонности и ковыпуклости нелокальной интерполяции кубическими сплайнами класса С2, а также исследуется возможность применения таких условий для разработки алгоритмов построения нелокальных изогеометрических интерполяционных сплайнов с использованием обобщений на основе классического кубического сплайна. На основе этих условий возможно построение алгоритмов автоматического выбора параметров в обобщённых конструкциях кубического сплайна для гарантированного наследования формы данных при их интерполяции.
Объектом исследования является нелокальный кубический сплайн S(x) класса С2[а,Ь], интерполирующий в узлах сетки значения {ft}, который на каждом промежутке можно представить в виде S(x) = (1 - t)ft + tfl+1 + (f1 t)h2Mt + qtt)h2Ml+1, (1.2) где cp(t) = (t3 -1)/6 , t = (x-xt )/ht, ht = xi+1 - xt, Mt = S"(xt), при этом краевые условия определяются значениями первых fa,fb либо вторых fa,fb производных на концах отрезка. В работе рассчитываются условия, при которых система линейных алгебраических уравнений для расчёта коэффициентов разложения сплайна по базисным функциях с трёхдиагональной матрицей специального вида и неотрицательной правой частью имеет неотрицательное решение, что может использоваться для описания условий согласованности знаковых схем вектора решения и вектора правой части для систем с трёхдиагональными матрицами без отрицательных элементов. Матрица решающей СЛУ рассматривается в двух представлениях: традиционном ленточном и обобщённом блочно-трёхдиагональном.
В работе доказывается ряд теорем, позволяющих исследовать вопросы об условиях наследования решением системы знаковой схемы правой части для систем с неотрицательными матрицами, а также свести задачу об условиях согласованности решения системы с неотрицательной матрицей и знакопеременной правой частью к задаче об условиях неотрицательности решения системы с неотрицательной правой частью и нестрого якобиевой матрицей. Далее даётся постановка задачи комонотонной и ковыпуклой интерполяции, приводятся результаты монотонной и выпуклой интерполяции классическими кубическими сплайнами класса С2. Под ковыпуклой сплайн-интерполяцией понимается задача построения сплайна S(x), удовлетворяющего условиям: 1) на каждом промежутке [ /, /+ ], к 3 выпуклости данных выполняется условие S"(x)S 0 для всех х є [xj, xj+1 J, j = і +1,..., і + к - 2; 2) если Xj - узел перемены направления выпуклости данных, то S"(x) на промежутке меняет знак только один раз.
Под комонотонной сплайн-интерполяцией понимается задача построения сплайна S(x), удовлетворяющего следующим условиям: 1) на каждом промежутке [х/5х/+Лг], к Ъ монотонности данных выполняется условие S (x)f[xj,xJ+l J 0 для всех х є [xj,xJ+l J, j = і; +1,..., і; + к - 2; 2) если Xj - узел перемены направления выпуклости данных, то S (x) на промежутке (X/_i,-X/+i) меняет знак только один раз.
В диссертации приводятся результаты кусочно-монотонной интерполяции классическим кубическим сплайном в представлении, использующем В-сплайны. Рассматривается задача построения выпуклых нелокальных обобщённых кубических сплайнов, интерполирующих данные, для которых условия выпуклости классического кубического сплайна класса С2 могут не выполняться. Приводится обобщающая представление (1.2) конструкция: на каждом интервале [х/5х/+1] сплайн задаётся формулой S(x)=cy(x)+ p(qi,\ - t)hfMt + (dpi+l,t)hfMi+l, где функция p(p,t)eC2[0,\] как функция от t имеет свободный параметру для управления поведением сплайна.
Формулируется алгоритм автоматического выбора одновременно всех параметров pi, qu при которых обобщённый сплайн является выпуклым. Результат работы алгоритма проиллюстрирован на примере обобщённого рационального сплайна Шпэта. Пример демонстрирует связь области параметров, описываемых достаточными условиями выпуклости сплайна, с областью всех параметров, при которых сплайн является выпуклым и тем самым показывает, что достаточные условия выпуклости обобщённого сплайна конструктивны и близки к оптимальным.
В диссертации Крымовой Е.А. [36] и статье [37] рассматривается задача интерполяции неизвестной функции f{x\ XGR: на основе данных (X,Y)={Xk, Yk=f(Xk\k = l,.../i} требуется восстановить значение функции/JC) в некоторой заданной точке х є (0,l). Интерполяционный сплайн определяется как предел решения следующей оптимизационной задачи при є - 0: 2e2lj J\ і 2Q0 SQm(x,Xj)= mgmm Ё&о-/М+чИ4 и в силу линейности по Yb к=1,… ,п записывается в следующем общем виде: п Щіт(х,х,г)= Ціт(х,хкук. к к=\ Показывается эквивалентность сплайновой интерполяции и оптимальной интерполяции обобщённого гауссовского процесса со спектральной плотностью со 1т. Проводится качественный анализ сплайновой интерполяции процессов со спектральными плотностями из класса Fm(b) на основе критерия максимальной ошибки интерполяции 2И45„]= sup af,(f,Sm), feFm(L) которая в результате оказывается близкой к минимаксной ошибке интерполяции. Предлагается метод контроля точности интерполяции сплайнами, основанный на использовании величины в качестве оценки для величины реальной ошибки интерполяции &т (Х) = [ЛХ) $т ( , Х Y)f .
В работе рассматриваются методы агрегации линейных упорядоченных оценок в задаче восстановления неизвестного вектора по зашумлённым данным, используемые при оценивании функции регрессии с помощью сглаживающих сплайнов. Эта задача состоит в том, что по наблюдениям Z/=/(X/) + ;,/=1,…,«, (1.3) где Xt є (0,l) и - независимые случайные величины со стандартным нормальным распределением необходимо восстановить гладкую функцию(JC), є[0,і], а в качестве оценок функции регрессии(х), хе[0,\] используются сглаживающие сплайны, которые определяются как решения оптимизационной задачи ( ,X,Z)=argmin{it[Z/ - f{xt)Y +P)[&\xidX (1.4) f [n i=l о J где p 0 - сглаживающий параметр. Для решения этой задачи с помощью сплайнов выполняется переход в базис Райнша-Деммлера, обладающий свойством двойной ортогональности.
Далее рассматривается обобщение задачи оценивания зашумлённого вектора при помощи агрегации упорядоченных оценок из заданного множества. Обобщённая задача рассматривается на примере оценки функции регрессии в гетероскедастичном шуме (х), х є [ОД] с помощью сглаживающих сплайнов по зашумлённым наблюдениям Z,- = f(Xi) + a(Xi ),/=1,…,и, (1.5) где С- стандартный белый гауссовский шум, сг2(х), х є [ОД] - неизвестная непрерывная функция. В качестве оценок используются сглаживающие сплайны, которые являются решением оптимизационной задачи (1.4). Решение обобщённой задачи с помощью базиса Райнша-Деммлера приводит к получению модели, эквивалентной результату моделирования функции (1.3), что позволяет сделать вывод о правомерности обобщения (1.5).
Разработанные методы тестируются в ходе вычислительных экспериментов, заключающихся в сравнении методов одномерной интерполяции данных. Предложенный в работе метод контроля точности для интерполяции сплайнами сравнивается с методом Криге, соответствующие эксперименты дают результат о лучшем контроле точности интерполяции, обеспечиваемом сплайнами.
Построение сетки узлов склеивания как задача моделирования, решаемая на предварительном этапе сплайновой интерполяции
Далее остаётся проверить условия (2.4). Если условия выполняются, полученное решение будет определять расположение узлов склеивания, соответствующее критерию оптимизации. Если же условия не выполняются, то решение системы следует искать по другим критериям, например, исходя из практической возможности задания краевых условий.
Таким образом, анализ способов вычисления узлов склеивания, приведённых в [117], позволяет сделать следующие выводы: в случае использования разбиения Хж+1 неоднозначность в определении узлов x0,...,xN+l требует от пользователя фиксации как минимум одного узла вручную, что снижает степень автоматизации разрабатываемой технологии, а также не исключает случайности во влиянии выбора узлов на соответствие результатов интерполяции требованиям практической задачи, так как компетентность пользователя в этих вопросах априори не гарантируется. Влияние расположения точек исходных данных на возможность построения сетки узлов x0,...,xN+l в этом же случае не позволяет считать данный способ универсальным и соответственно пригодным для реализации по обобщённой технологии, так как требует выполнения предварительных проверок существования решения системы (2.10) (2.4), которые являются достаточно сложными и приводят к существенным дополнительным затратам времени. Снижению автоматизации и увеличению влияния случайности также способствует пользовательское установление критериев, по которым тот или иной набор из спектра возможных решений будет являться оптимальным; при этом также будет присутствовать необходимость проверки решений принадлежности ОДЗ, определяемой условиями (2.4), что не позволяет существенно усовершенствовать метод нахождения узлов склеивания в общем случае при использовании разбиения 2ж+1. В случае же использования разбиения Хж+1 возникновение гетерогенных сплайнов усложняет реализацию методов построения интервальных представлений сплайнов, так как приводит к необходимости выполнения дополнительных функциональных построений. При этом следует отметить, что авторами статьи [117] изначально не предполагалось создание компьютерной реализации в силу объективных причин отсутствия технологической составляющей соответствующего уровня на момент публикации, в то время как в наших условиях требуется обеспечить бесперебойную работу системы компьютерного моделирования, построенной на основных принципах обобщённого программирования. В связи с этим подход к расчёту узлов склеивания необходимо обобщить посредством введения параметра, определяющего положение точек исходных данных по отношению к узлам склеивания, что позволяет сохранять принцип единственности биортогонального базиса в обобщённой реализации технологии.
Формулу (2.2) для нахождения узлов x0,...jcN+l можно записать в следующем обобщённом виде: х. = r(xf + xi+l), /=0,… Д (2.16) при г =1/2. Представление (2.16) может быть использовано для поиска узлов склеивания, при этом для каждого расположения точек исходных данных спектр возможных расположений узлов склеивания, которые мы без нарушения общности также будем обозначать xQ,...jcN+l, будет определяться не только возможными значениями фиксации узлов xQ,...jcN+l, но и возможными значениями фиксации параметра т . В этом случае для нахождения x0,...,xN+l потребуется решить следующую задачу: точки исходных данных x0,...,xN в общем случае образуют неравномерную сетку; требуется определить сетку узлов склеивания x0,... N+l, удовлетворяющую условиям (2.4), с учётом выполнения условий постоянства параметра г є (ОД): = 1 } =...= N X!0, =r=const. (2.17) xl X0 X2 X\ XN+\ - XN Из этой системы неравенств получаем, что х0 -х0 =т(х, -5C0)= JC1 = [х0 -(l-rfe]/r . Преобразуя таким образом каждое равенство в (2.17), получаем систему N+1 равенств с 7V+3 неизвестными: 3 =к-(1-т)5с0]/т,…,3 +1 = [ -(1-т) ]/т, (2.18) для решения которой требуется зафиксировать два свободных параметра, произвольно выбранных из набора X0,...,XN+1,T .
Аналитический метод решения системы (2.18) заключается в выводе и решении системы соотношений, получаемых в результате преобразования системы после фиксации свободных параметров. Однако при большом количестве точек исходных данных рациональность аналитического решения системы существенно снижается, так как требует использования приближённых методов нахождения корней многочленов высоких степеней. В разделе 3.1 рассмотрено решение этой задачи с помощью генетического алгоритма, реализованное с учётом основных принципов разработки обобщённой технологии сплайнового моделирования. Такое решение продиктовано тем, что генетический алгоритм имеет большое число свободных параметров, а также работает заведомо не хуже абсолютно случайного поиска.
Одним из важнейших этапов построения сплайн-функций на линейных оболочках, следующим после построения сетки узлов склеивания, является построение биортогонального базиса. На этой стадии сплайнового моделирования определяющим является выбор функций исходного базиса и определение системы функционалов, участвующих в построении функций биортогонального базиса, так как от этих функциональных параметров во многом зависят точность приближения и соответствие интерполяционного сплайна свойствам моделируемой системы. Как мы неоднократно убедимся при дальнейшем изложении основных принципов технологии сплайнового моделирования, а также демонстрации её работы на практических примерах, при выборе базисных функций и системы функционалов следует руководствоваться свойствами моделируемой системы, определяющими её природу и особенности поведения, а также практическими требованиями, предъявляемыми к результатам моделирования.
Рассмотрим основные операции, выполняемые при построении биортогонального базиса: расчёт формульных представлений функций биортогонального базиса на основе функций исходного базиса и системы функционалов; особенности математических конструкций, возникающих при переходе от исходного базиса к биортогональному; обобщение представления биортогональных базисов, построенных по одному исходному набору функций и различным системам функционалов; способы задания базисных функций, соответствующих определённым типам практических задач; некоторые особенности биортогональной формы базиса сплайна, которые позволяют определять параметры интерполяционного сплайна и оценивать точность приближения на стадии выбора функций исходного базиса. При изложении технологии построения биортогонального базиса также будем следовать принципу описания математических конструкций и методов применительно к компьютерной реализации, основанной на представлении конструкций в качестве программных объектов, обладающих общими свойствами, присущими всем сплайн-функциям.
Начнём изложение с вывода интервальных представлений (2.6) по методике, описанной в [117]. Если на каждом отрезке Ej определена система из п линейных функционалов \Я f , то совокупность справедливых на Е}- равенств
Решение задачи построения сетки узлов склеивания с помощью генетического алгоритма
Подводя итоги анализа различных алгоритмических подходов к вычислению производных высоких порядков от сложных функций, основанных на расчётных формулах (3.32), (3.33), (3.34), (3.35), (3.36), (3.37), можно сделать общий вывод о предпочтительности последнего в связи, так как этот подход учитывает возможность представления расчётных формул для функций еи, sin и, cos и, sinh и, cosh и в терминах полных полиномов Белла, а также специфику детерминантного представления полного полинома Белла. Таким образом, алгоритм, основанный на формулах (3.37), может быть рекомендован к практическому использованию при разработке пакетов прикладных программ для решения аналитических задач, в частности, рассматриваемой в настоящей диссертации задачи интерполяции сплайн-функциями. С учётом различий в подходах к вычислениям рассматриваемый набор алгоритмов позволяет считать результаты анализа достаточными для объективной оценки их степени оптимальности для программного выполнения вычислений [160].
В разделе 2.4 настоящей диссертации выведен общий вид решающей СЛУ для нахождения набора коэффициентов интервальных представлений сплайна в биортогональном базисе. Параметрами этой системы являются размерность базиса и набор порядков производных, задаваемых краевыми условиями, при этом второй из этих параметров также определяет функционалы, по которым строится биортогональный базис. Там же рассмотрен метод прогонки, который может быть использован для решения этой СЛУ в простейшем случае, когда матрица имеет трёхдиагональный вид. В этом разделе будут записаны формулы для метода матричной прогонки, который является обобщением классического метода и может быть применён в случае системы с блочно-трёхдиагональной матрицей.
В [161, с. 57] рассматривается следующее правило, общее для всех блочных матриц: действия над блочными матрицами производятся по тем же формальным правилам, что и в случае численных матриц, при этом следует учитывать некоммутативность перемножения матриц-блоков. Отсюда следует, что метод прогонки может быть распространён на случай блочно-трёхдиагональной матрицы. Применим это правило к матрице решающей СЛУ для нахождения недостающих коэффициентов интервального представления сплайна; общий вид этой матрицы вместе с выражениями для расчёта коэффициентов приведён в разделе 2.4 (формулы (2.29) и (2.30) соответственно). Расчётные формулы преобразуются следующим образом: на стадии прямой прогонки вычисляются матрицы Г, еМ _;+1 и вектор-столбцы 8l eRH+1 прогоночных коэффициентов:
В разделе 2.5 рассмотрены практические задачи, для решения которых по исходным данным требуется построить интерполяционные сплайны, при этом использование многочленных сплайнов в качестве метода построения таких моделей не всегда даёт желаемый результат. Таковой, например, является задача интерполяции функции свойств титана при нагревании. На рис. П1.2, б) (прил. 1) видно, что естественный кубический сплайн даёт значительно лучшие результаты интерполяции по сравнению с оптимальной интерполяцией многочленами 5-й степени. Однако в точках Т = 965 и Т = 975 кубический сплайн достигает минимума GЕКС= 0.592, который в исходном наборе экспериментально полученных данных не прослеживается. Подробно решение этой задачи средствами инструментального программного комплекса будет описано далее по ходу раздела, так как перед этим необходимо описать принципы реализации L-сплайновых конструкций, используемых при решении этой задачи и других практических задач, описанных в разделе 2.5, с помощью обобщённой объектно-ориентированной технологии. L-сплайны предлагается использовать в качестве обобщённого метода построения сплайновых моделей. Эти конструкции относятся к алгебраическому подходу в теории сплайнов, обеспечивающему большую близость к практическим потребностям вычислительной математики.
Для представления линейного дифференциального оператора Dn порядка п с постоянными вещественными коэффициентами, определяющего поведение динамической системы (общий вид оператора представляется формулой (2.22) в разделе 2.3), используется представление в виде произведения линейных дифференциальных операторов второго порядка: Dn = J /=1 (p-a)Y\D2i, n = 2m + 1, где D2i = p2 + bt p + Cj, i=1,…,m. Такое представление, во-первых, охватывает все возможные линейные дифференциальные операторы произвольного порядка с постоянными вещественными коэффициентами, так как в поле вещественных чисел неприводимыми являются линейные многочлены и квадратичные многочлены без вещественных корней [162, с. 218-224], а во-вторых, позволяет обходить при реализации решение уравнений высоких степеней сложными приближёнными методами, так как нахождение определяющих параметров системы - Я,со,\,\ в таблице 2.5 - в этом случае сводится к решению квадратных уравнений.
Модуль, реализующий аналитический метод построения сеток узлов склеивания сплайн-функций
Как было отмечено в разделе 4.1, основной функцией интерфейса программного комплекса «Моделирование и обработка числовых данных с помощью интерполяционных сплайнов» являются организация взаимодействия программного комплекса с пользователем, при этом естественным образом предполагается, что все операции, предоставляемые интерфейсом программного комплекса, выполняются автоматически на основе пользовательского выбора. В связи с этим интерфейс программного комплекса включает в себя инструменты, позволяющие организовать: считывание исходных данных, которые обычно представляют собой некоторый внешний файл; ввод параметров интерполяционного сплайна пользователем для построения модели; отображение табличного представления исходных данных и результатов интерполяции в удобном для пользователя виде. Эти операции реализованы с помощью основного компонента интерфейсной части программного комплекса - главной формы. Рассмотрим их реализацию более подробно.
Считывание исходных данных. В проекте реализована возможность считывания исходных данных для построения интерполяционного сплайна из файла формата Microsoft Excel. Пользователю предоставляется возможность выбрать Excel-файл исходных данных, который должен иметь следующий формат: 1) первая строка файла состоит из наименований моделируемых величин; 2) первый столбец содержит координаты точек, в которых имеются исходные данные. В качестве примера файла исходных данных на рис. 4.10 приведён Excel-файл с таблицей данных по 6 точкам отрезка [-0.45,5.24] со значениями абсциссы точки и функции (2.38) для каждого значения абсциссы из таблицы. Считается, что все считываемые из файла цифровые данные имеют тип double, а заголовки столбцов имеют тип string; при открытии файла исходных данных производится проверка типов, в случае несоответствия типов выдаётся сообщение об ошибке. Если исходный файл не отсортирован по координатам, то сортировка выполняется автоматически. Считывание исходных данных из файла выполняется следующим образом: 1) читается первая строка файла; 2) читается первый столбец файла, начиная со второй строки; 3) по результатам заполнения первой строки и первого столбца файла определяется общий объём имеющихся в файле данных; 4) считывается массив данных из файла, начиная со второй строки и второго столбца, в объёме, определённом в п.3.
Для считывания используется библиотека libxl.dll [186]. Подключение этой библиотеки позволяет считывать Excel-файлы, при этом не требуется наличие Microsoft Excel и платформы .NET. Для считывания используются классы Book и Sheet, реализованные в библиотеке. Чтобы пользователю в процессе работы было доступно численное представление исходных данных, на главную форму помещён визуальный табличный компонент gridData типа dataGridView, который принимает считываемые данные, а также позволяет выбрать способ представления измеренных величин в файле – являются ли исходные данные значениями величин в точках, средними значениями по отрезкам или интегралами по отрезкам.
Выбор размерности базиса и определение базисных функций. Выполнение этих операций обеспечивается с помощью компонента gridBase типа data-GridView следующим образом: сначала задаётся размерность базиса – не менее 2, после чего пользователю предоставляется возможность определения соответствующего количества базисных функций. Возможности программного комплекса позволяют определять базисные функции двумя способами: путём прямого задания или путём задания коэффициентов линейного дифференциального уравнения, определяющего поведение системы. При прямом задании пользователю предоставляется возможность выбора базисных функций из встроенного списка; альтернативным способом является ввод формульных представлений базисных функций пользователем, при этом произвольность выбора функций ограничена условием допустимости. При задании коэффициентов линейного дифференциального уравнения с вещественными коэффициентами, определяющего поведение системы, базисные функции рассчитываются как ФСР этого уравнения. Формулировка условий допустимости произвольного набора базисных функций и принципы формирования встроенного списка функций, предполагаемых для использования в качестве базисных, описаны в разделе 2.3. При этом для функций реализована возможность задания параметров и при помощи активации дополнительных ячеек таблицы gridBase, имеющих тип comboBox.
Выбор системы функционалов для построения биортогонального базиса, задание граничных условий и построение сплайновой модели. Для обеспечения возможности выбора системы функционалов на главную форму проекта помещён компонент cbFunc типа comboBox со списком всех систем функционалов, возможных для текущей размерности базиса; при изменении размерности базиса список автоматически пересчитывается. Список систем функционалов упорядочен по возрастанию индексов. После выбора системы функционалов краевые условия задаются значениями соответствующих производных на концах отрезка интерполяции. Построение интерполяционного сплайна по исходным данным, набору базисных функций и граничным условиям начинается при нажатии кнопки «Интерполировать». Классы, описанные в разделе 4.2, считывают исходную информацию с главной формы в свои поля, и в результате табличное представление сплайновой модели – координаты точек, взятых на отрезке интерполяции с заданным шагом, значения функции и всех её непрерывных производных в этих точках – выводится в компонент gridRes типа dataGridView, расположенный на главной форме, а графическое может быть визуализировано с помощью редактора graph_spline.