Содержание к диссертации
Введение
Глава 1. Кубические сплайны. Основные методы и алгоритмы 16
1.1. Интерполяционный кубический сплайн 16
1.1.1. Определение интерполяционного кубического сплайна 16
1.1.2. Методы вычисления интерполяционного сплайна 18
1.2. Сглаживающий кубический сплайн 30
1.2.1. Определение сглаживающего кубического сплайна 31
1.2.2. Методы вычисления сглаживающего сплайна 32
1.3. Определение среднеквадратичного приближения 40
1.3.1. Проблемы выбора параметра сглаживания 40
1.3.2. Выбор размерности пространства В-сплайнов 41
1.4. Частотная модель сглаживающего сплайна 45
1.5. Выводы 49
Глава 2. Выбор п араметра сглаживания 50
2.1. Алгоритмы оценивания оптимального параметра сглаживания.. 51
2.1.1. Алгоритм выбора параметра сглаживания на основе критерия оптимальности 52
2.1.2. Выбор параметра сглаживания на основе критерия перекрестной значимости (cross validation method) 56
2.1.3. Выбор параметра сглаживания на основе метода L-кривой 57
2.2. Выбор параметра сглаживания по заданным точностным характеристикам 61
2.3. Сравнение методов выбора параметра сглаживания различными алгоритмами 62
2.3.1. Исследование качества оценки параметра сглаживания при некоррелированном шуме 62
2.3.2. Исследование влияния коррелированности шума на качество построения параметра сглаживания 67
2.4. Выводы 72
Глава 3 . Изогеометрические сглаживающие сплайны 73
3.1. Задача построения изогеометрических сплайнов. 73
3.1.1. Классификация априорной информации 73
3.1.2. Подходы к решению 74
3.2. Построение изогеометрического сглаживающего сплайна (первый метод ) 76
3.2.1. Восстановление геометрии исходных данных 76
3.2.2. Построение изогеометрического сплайна 83
3.3. Построение изогеометрического сглаживающего сплайна (второй метод) 87
3.3.1. Построение системы ограничений 87
3.3.2. Согласованность системы ограничений 90
3.3.3. Алгоритм построения изогеометрического сглаживающего сплайна 90
3.4. Вычислительный эксперимент 91
3.4.1. Описание вычислительного эксперимента 91
3.4.2. Результаты вычислительного эксперимента 94
3.5. Выводы 94
Глава 4. Робастные сплайны и ал горитмы их построения 95
4.1. Робастный сглаживающий сплайн 95
4.1.1. Устойчивые плотности распределения шумов 99
4.1.2. Сглаживающие сплайны, робастные на классах распределений шумов измерений 104
4.2. Алгоритмы построения робастных сплайнов 109
4.2.1. Существование и единственность робастного сплайна 109
4.2.2. Алгоритм № 1 решения вариационной задачи 112
4.2.3. Алгоритм №2 решения вариационной задачи 112
4.2.4. Алгоритм №3 решения вариационной задачи 115
4.3. Выбор параметра сглаживания вробастных сплайнах 117
4.4. Вычислительный эксперимент 119
4.4.1. Эксперимент 1. Восстановление данных, искаженных «смешанным» шумом 120
4.4.2. Эксперимент 2. Восстановление данных, искаженных экспоненциальным шумом 121
4.4.3. Эксперимент 3. Восстановление данных, искаженных нормальным шумом 125
4.5. Выводы 127
Глава 5. Комплекс п рограмм «Spline Tool» 128
5.1. Характеристика программного комплекса 128
5.2. Требования к программному и аппаратному обеспечению 128
5.3. Описание интерфейса программного комплекса «Spline Tool» 129
5.4. Подготовка информации для работы комплекса 130
5.4.1. Формат файла данных 130
5.4.2. Формат файла априорных ограничений 130
5.5. Подсистема ввода и отображения числовых данных 131
5.6. Подсистема вычисления сплайнов 131
5.6.1. Компонента работы с матрицами 132
5.6.2. Компонента вычисления параметра сглаживания 133
5.6.3. Компонента вычисления кубического сплайна 134
5.7. Выводы 138
Глава 6. Обработка данных реаль ных экспериментов 139
6.1. Обработка экспериментальных данных изогеометрическими сглаживающими сплайнами 139
6.1.1. Обработка данных аэродинамического эксперимента 139
6.1.2. Обработка данных системы слежения за спутниками с использованием изогеометрических сглаживающих сплайнов 143
6.2. Обработка данных системы слежения за спутниками с использованием робастных сплайнов 150
6.3. Выводы 156
Заключение 157
Список литературы 159
- Алгоритм выбора параметра сглаживания на основе критерия оптимальности
- Построение изогеометрического сглаживающего сплайна (первый метод
- Существование и единственность робастного сплайна
- Требования к программному и аппаратному обеспечению
Введение к работе
Одной из основных задач, возникающих при обработке результатов экспериментов, является задача интерполяции и дифференцирования табличных данных. Из-за сложности математических моделей экспериментов процесс точного их восстановления более трудоемок по сравнению с построением модели, близкой по свойствам к модели эксперимента. Для более точного приближения построенной математической модели к эксперименту, помимо информации, полученной в результате эксперимента, используется априорная информация, которая задает дополнительные ограничения на поведение функции.
Известно, что наилучшее приближение для функций класса Ж,2 [а,6] с ъ точки зрения функционала энергии вида [( "(х)) ах дают кубические а сплайны. То есть, кубический сплайн обладает минимальной кривизной среди всех интерполяционных функционалов, построенных по заданным точкам. Наиболее простым кубическим сплайном является интерполяционный кубический сплайн, методы вычисления которого являются базовыми для вычисления других видов сплайнов. Для учета информации о геометрии функции и для построения наиболее гладкого сплайна в работах [29, 30, 31] предложен сплайн специального вида, т.н. изогеометрический сплайн.
Однако область применения таких сплайнов ограничена таблицами, содержащими точные значения интерполируемой функции. То есть при использовании этого типа сплайнов мы должны быть уверены, что экспериментальные данные не содержат ошибок, которые могут быть внесены, например, регистрирующей аппаратурой. В случае наличия таких ошибок выполнение условий интерполяции приводит к искажению исходной функции, более того, при дифференцировании построенного сплайна его производная будет содержать высокочастотные «шумовые» осцилляции большой амплитуды, обусловленные некорректной операцией дифференцирования. Чтобы избежать такой ситуации используются сглаживающие кубические сплайны.
Одним из главных вопросов аппроксимации таблично заданных данных кубическими сглаживающими сплайнами является оценка параметра сглаживания, то есть выяснение того, насколько построенный сплайн будет приближен к исходным данным. Если принять завышенную оценку, сплайн окажется переглаженным и часть информации может быть потеряна, если оценка будет заниженной, восстанавливаемые данные могут содержать «вредные» высокочастотные составляющие. Существует ряд методов, позволяющих оценивать этот параметр, однако эти методы требуют задания уровня шума и чувствительны к коррелированности помехи. В работе предлагается новый метод, который является модификацией метода L-кривых, разработанного Хансеном [63] для решения СЛАУ.
При построении сглаживающих кубических сплайнов для обработки экспериментальных данных используется минимальная информация - о сетке и точных или неточных значениях функции в узлах этой сетки. Однако, наряду с этой информацией, как правило, существуют дополнительные (априорные) данные о свойствах функции, например, об ее неотрицательности или монотонности на некоторых отрезках. Они могут быть получены при изучении физических свойств объекта эксперимента и позволяют точнее восстановить исследуемую функциональную зависимость.
Для интерполяционных сплайнов учет такой информации осуществляется при построении изогеометрических сплайнов [31]. При построении таких сплайнов гарантируется только сохранение информации о возрастании/убывании и выпуклости/вогнутости функции, но не рассматривается вопрос об ограничении значений функции.
Для сглаживающих сплайнов в работах [16, 19] предложена методика учета априорной информации, заданной в виде ограничений на значения функции и ее производных только в узлах сетки. Недостатком данной методики является то, что она гарантирует заданное поведение функции только в узлах сетки. Хотя, в задачах обработки экспериментальных данных необходимо выполнять априорные ограничения на всем заданном интервале. Метод, предложенный в диссертации, позволяет распространить эту информацию на интервалы между узлами сетки.
Помимо помех малой амплитуды, накладываемых регистрирующей аппаратурой, результаты эксперимента могут искажаться случайными выбросами большой амплитуды (аномальные измерения). В этом случае, обычные методы построения сплайнов с квадратичным функционалом невязки приводят к отклонению результатов в сторону этих выбросов. В теории оценивания устойчивость оценок к аномальным измерениям достигается построением специальных - робастных - алгоритмов. В применении к сплайнам эта задача была поставлена, но решения были найдены только для одного класса распределения шума - равномерного.
Таким образом, целью диссертации является разработка вариационных методов построения сглаживающих сплайнов, учитывающих имеющуюся у экспериментатора априорную информацию и устойчивых к аномальным измерениям.
Общая цель включает в себя следующие задачи:
1. Исследование и разработка методов оценки параметра сглаживания, не требующих задания уровня шума измерения и устойчивых к коррелированности шума.
2. Выбор параметра сглаживания, не требующего задания числовых характеристик шумов измерений.
3. Разработка методов и алгоритмов построения изогеометрических сглаживающих кубических сплайнов, учитывающих априорную информацию о поведении функции и производных на различных отрезках.
4. Разработка методов и алгоритмов построения робастных сплайнов с различными функционалами невязок, обладающих высокой устойчивостью к аномальным измерениям. Исследование свойств этих сплайнов при использовании в качестве функционалов невязок различных функций, применяемых в теории робастного оценивания.
5. Создание пакета прикладных программ построения изогеометрических и робастных сглаживающих сплайнов, реализующего эти алгоритмы и пригодного для обработки экспериментальных данных, представляемых различными способами.
6. Использование разработанных методов для обработки данных реальных задач Диссертация состоит из шести глав.
В первой главе приводятся методы построения интерполяционных и сглаживающих сплайнов, используемые в других главах. Также приведены методы интерполяции эрмитовыми и В-сплайнами, некоторые из которых затем использованы в главе 3 при вычислении изогеометрического сглаживающего сплайна.
Во второй главе рассматриваются два подхода к выбору параметра сглаживания:
а) выбор параметра из условия минимума среднеквадратической ошибки сглаживания;
б) выбор параметра по заданным точностным характеристикам сплайна. В рамках первого подхода предлагается алгоритм выбора по L-кривой сглаживающего сплайна. В рамках второго подхода вводятся точностные характеристики сплайна и формулируется ряд вариационных задач, решение которых позволяет строить сглаживающий сплайн с требуемыми точностными характеристиками.
Третья глава посвящена построению изогеометрического сглаживающего сплайна.
При высоком уровне погрешностей исходных данных не всегда удается построить сглаживающий сплайн, приемлемый как с точки зрения требуемой точности, так и соответствия некоторым физическим представлениям об исследуемом процессе. Как отмечалось выше, исходя из физических представлений, экспериментатор может иметь достаточную априорную информацию о возможном поведении функции и ее производных на различных интервалах. Эта информация представляет собой набор ограничений на значения функции и ее производных. По форме задания эту информацию можно разделить на два типа:
1. ограничения на значения функции и производных в узлах сетки
2. ограничения на значения функции и производных на интервалах между узлами.
Задача построения сплайна с априорной информацией первого типа рассмотрена в [16, 19]. Задача со вторым типом информации тоже рассматривались (напр, [32, 33]). Предложенные методы обладают рядом недостатков. Во-первых, рассмотрены ограничения только вида /(х) 0, во-вторых, сплайн, построенный этим методом, может исказить решение и сделать его верным с точки зрения математики, но не удовлетворяющим физическим законам (особенно это касается поведения производных).
В данной главе предложены два метода построения изогеометрического сглаживающего сплайна, то есть сглаживающего сплайна, который учитывает ограничения на все производные сплайна на любом заданном интервале.
Первый метод, предложенный в этой главе, позволяет построить изогеометрический сглаживающий сплайн, который учитывает априорную информацию о поведении первой и второй производных приближаемой функции. Процесс построения сглаживающего изогеометрического сплайна состоит из двух этапов. На первом этапе строится сглаживающий дескриптивный сплайн, тем самым создается «правильная» геометрия исходных данных в узлах сетки. На втором этапе по этой геометрии строится изогеометрическии сплайн, который в силу своих свойств сохраняет эту геометрию на интервалах между узлами.
Второй метод позволяет учесть априорную информацию и о самой приближаемой функции на интервалах сетки.
При построении сглаживающего изогеометрического сплайна решается задача о непротиворечивости и достаточности накладываемых на сплайн ограничений, имеющая важное значение при задании априорных ограничений. Сформулирована и доказана соответствующая теорема.
Четвертая глава посвящена разработке методики построения робастных сплайнов.
В этой главе вводится понятие сплайна робастного на классе распределений шумов, каждый из которых характеризуется определенным устойчивым распределением шума: нормальное распределение (эта модель применяется, если эксперимент проводился при одинаковых условиях), экспоненциальное распределение (модель используется при описании шумов, возникающих при проведении экспериментов в изменяемых условиях) и смешанное распределение.
В соответствие с этими моделями введены три класса распределений шумов и для каждого класса распределений введен специальный вид функционала невязок, используемого вместо стандартного квадратичного функционала. На основе этой задачи формулируется определение робастного сплайна, то есть сплайна, который может «учесть» информацию о классе шума, искажающего экспериментальные данные.
Формулируется и доказывается общая теорема существования и единственности решения такой задачи. Далее доказываются теоремы существования и единственности решений для введенных классов распределений шумов.
На основе этих теорем предложены несколько алгоритмов решения этой задачи, наиболее детально рассмотрен алгоритм, использующий методы оптимизации первого порядка.
Пятая глава описывает программный комплекс, реализующий методы, описанные в главах 2, 3 и 4. Чтобы проверить предложенные алгоритмы и предоставить этот инструментарий исследователям, был разработан комплекс программ «Spline tool». Комплекс разработан под платформу .NET.
В шестой главе описаны эксперименты, проведенные с использованием комплекса программ «Spline Tool».
Интерфейс с пользователем, описание библиотек, особенности реализации комплекса и необходимая для его использования документация подробно приведены в этой главе. Кроме того в этой главе приведены результаты использования комплекса программ для обработки данных, полученных в ходе реальных экспериментов
В конце диссертации сделаны выводы по проделанной работе.
Научная новизна исследований заключается в следующем.
1. Введен новый класс сглаживающих сплайнов - изогеометрический сглаживающий сплайн, позволяющий учесть априорную информацию о значениях приближаемой функции и ее производных не только в узлах сетки, но и на интервалах. На основе этой информации производится «коррекция» плохой геометрии исходных данных. Доказан ряд теорем о существовании и единственности изогеометрического сглаживающего сплайна, а также теорем об избыточности и непротиворечивости ограничений, накладываемых на сплайны.
2. Предложен алгоритм построения изогеометрического сглаживающего сплайна, состоящий из двух этапов: первый этап - корректировка «плохой геометрии» исходных данных на основе имеющейся априорной информации; второй этап - построение сплайна, сохраняющего полученную на первом этапе геометрию.
3. Введен новый класс сплайнов - сглаживающие сплайны, робастные на классах распределений шумов. Сформулирован вариационный подход к построению робастных сплайнов. Доказана теорема о существовании и единственности робастных сплайнов.
4. предложены два алгоритма выбора параметра сглаживания: из L-кривой сплайна и по заданным точностным характеристикам.
5. Предложены вычислительные схемы построения робастных сплайнов.
Практическая значимость работы заключается в следующем.
1. Методы и алгоритмы, разработанные в диссертационной работе, дают возможность эффективно использовать изогеометрические и робастные сплайны при обработке различных экспериментальных данных.
2. Разработан пакет прикладных программ «Spline tool», реализующий построение интерполяционных и сглаживающих сплайнов (в том числе изогеометрических и робастных). Он имеет удобный и понятный интерфейс и реализован для наиболее массовых и производительных операционных систем. Пакет может обрабатывать данные, которые представлены в различном виде (вводятся с клавиатуры, загружаются из файла или запрашиваются из базы данных).
3. Сформулированные в работе результаты позволяют сделать вывод об избыточности или противоречивости задаваемой априорной информации.
4. Пакет прикладных программ «Spline tool» использовался при обработке данных летного эксперимента в институте теоретической и прикладной механики и это позволило получить из эксперимента более достоверную информацию об исследуемых аэродинамических процессах.
5. Пакет программ «Spline Tool» передан в эксплуатацию в ФГУП СНИИМ для использования при обработке данных аппаратуры слежения за спутниками.
Достоверность результатов диссертации основана на строгом проведении математических доказательств и совпадении свойств сплайнов, построенных по этим методикам, с априорными условиями, заданными при построении этих сплайнов, а также повторяемостью результатов при расчете одной задачи разными методами.
На защиту выносятся следующие положения.
1. Оценка параметра сглаживания методом L-кривой.
2. Вариационный подход к построению изогеометрического сглаживающего сплайна. Теорема о существовании и единственности решения сформулированной вариационной задачи. Условия непротиворечивости априорных ограничений.
3. Вариационный поход к построению сглаживающего сплайна, робастного на классах распределений шумов измерений и алгоритмы его построения. Теорема существования и единственности такого сплайна.
4. Пакет прикладных программ «Spline Tool», реализующий построение интерполяционного, сглаживающего, изогеометрического сглаживающего, робастного сглаживающего сплайнов.
5. Результаты одной из случаев применения изогеометрического сглаживающего сплайна для обработки данных аэродинамического эксперимента.
6. Результаты применения изогеометрических сплайнов для обработки данных системы слежения за спутниками.
7. Результаты применения робастных сплайнов для обработки данных системы слежения за спутниками
При нумерации разделов, формул и рисунков первая цифра указывает номер главы, вторая - их порядковый номер.
Основные результаты, полученные в диссертации, опубликованы в 8 работах [4-10,50].
Апробация результатов работы.
Результаты диссертационной работы неоднократно (в течение 1998-2002 годов) обсуждались на семинарах научного направления «Создание новых информационных технологий и систем автоматизированного проектирования» Новосибирского государственного архитектурно-строительного университета (НГАСУ) и докладывались на следующих конференциях
• Международная Байкальская школа-семинар «Методы оптимизации и их приложение» Иркутск, 1998 г.
• Международная конференция KORUS-99, НГТУ, Новосибирск, 1999 г.
• Всероссийская конференция «Алгоритмический анализ некорректных задач», Екатеринбург, 1998г.
• Российская конференция «Обратные и некорректно поставленные задачи» Москва 1998; 1999 г.
• Научно-технические конференции Новосибирского государственного архитектурно-строительного университета (Новосибирск) 1999, 2000 годов.
• Четвертый Сибирский Конгресс по прикладной и индустриальной математике, посвященный памяти М.А. Лаврентьева (ИНПРИМ-2000)
• Сибирская конференция «Методы сплайн-функций», посвященная памяти Завьялова Ю.С., Новосибирск 2001 г.
Автор выражает глубокую благодарность доктору физико-математических наук Воскобойникову Юрию Евгеньевичу за научное руководство, а также кандидату физико-математических наук Мирошниченко Валерию Леонидовичу за критические замечания и советы при подготовке диссертации.
Алгоритм выбора параметра сглаживания на основе критерия оптимальности
В работах [20, 21] был предложен статистический алгоритм, позволяющий достаточно точно оценить осопт, и не требующий априорной информации о приближаемой функции f(x). Приведем основные соотношения этого алгоритма, необходимые для дальнейшего изложения. Введем вектор невязки е(а) размерности п с проекциями Таким образом, возникает задача проверки гипотезы о распределении статистики рцг (а), а именно: подчиняется ли рцг [ос] % - распределению с п степенями свободы. Для проверки этой гипотезы построим интервал Задача вычисления параметра aw тесно связана с задачей вычисления Pw{a) Для любого значения а 0. Наиболее простой алгоритм получается для естественных краевых условий. Используя выражение e(a) = E(a)f, получаем «универсальную» формулу pjjr(a) = e (a)V f. Если проекции вектора шума г/ не коррелированны, то V„ является диагональной матрицей Pw{«) = l t (2-5) Словами это означает, что для заданного значения а нужно первоначально найти коэффициенты ai=Sa{xi) сглаживающего сплайна, затем et a) = fi-щ, і = 1,...,п, а потом вычислить рцг(а) по соотношению (2.5). Заметим, что значения рцг(а) очень слабо зависят от используемых краевых условий (особенно при достаточно большом п 30). Поэтому рассмотрим алгоритм вычисления ацг для «естественных» краевых условий (1.3). После нахождения aw можно построить кубический сплайн с нужными типами краевых условий.
Введем верхнюю трехдиагональную (я - 2) х я матрицу Я с элементами:диагональную матрицу P = diag [p\, p2, , pn }, где hj = Xj+i -Xj, j = 1,..., n -1, Pi 0 весовые множители функционала (1.43). Предположим, что проекции шума 77 не коррелированны, т.е. V диагональная и матрица Р задается В работе [24] предложен алгоритм, основанный на следующих свойствах квадратичной формы Rw(у):
1. \\mRfV(y) = R0\ lim %(/) = () 2. Rw{r) 0; Rw{r) 0; Щу{г) Ъ при /є[0,о ), где RQ - значение Rw{y), соответствующее сглаживающему сплайну, построенному при Mj = О, i = \,...,n, что соответствует а = оо. Алгоритм, основанный на приведенных свойствах Rw [у), реализует итерационную процедуру ньютоновского типа, состоящую из следующих шагов: 1(Г8,1(Г6 Шаг 1. Задается начальное значение р є и вычисляется вектор q = Hf. Принимаем номер проекции к = 0, Шаг 2. Решается система (y(kh + HPHT\mr=q, матрица которой положительно определена, симметрична и имеет пять диагоналей. Шаг 3. Вычисляется значение Rw[rk ) = cpqTmr. Шаг 4. Проверка условия (2.4). Если условие выполняется, то шаг 7, если не выполняется - шаг 5. Шаг 5. Вычисление производной Rjflp }\ = q пу, где пу - вектор решения системы (y A + HPHT\nr =-Атг. Шаг 6. Вычисление очередного значения /(М) = у( )_Ду(г( ))_й//Дг(г( ))) t = (U)2 (2.7) и повторение шагов 2), 3), 4). Шаг 7. Вычисление параметра сглаживания aw = l/;r и вектора вторых производных М = (М2, М3,..., Mn_i) как М = уту. Напомним, что для краевых условий (1.3) Мх = S"(x{) = 0; М„ = S"(xn ) = 0. Можно показать, что при выполнении следующих условий: матрица Р определяется соотношением (2.6); Ro 3n{Pl2) то для любого начального значения у описанный выше алгоритм вычислит значение ссцг. Заметим, что а является случайной величиной и это характерно для оценок, получаемых методами математической статистики. Приведенные в [24] результаты показывают, что среднее значение aw совпадает с аопт, а все значения осцг находятся в окрестности точки аопт. Эти свойства ацг позволяют сделать следующий вывод. Величина ссщ может быть принята как оценка оптимального значения параметра сглаживания аопт. 2.1.2. Выбор параметра сглаживания на основе критерия перекрестной значимости (cross-validation method) Метод выбора параметра сглаживания из метода перекрестной значимости исследован в большом числе работ (например [81]-[84]), поэтому приведем его краткое описание. В этом методе параметр сглаживания выбирается исходя из условия минимума функционала ) = 1(//- ())2. (2-8) где Sy (JC) - сглаживающий сплайн, построенный по вектору /" , полученному из вектора / путем удаления проекции /j, Іц - множество Поскольку координате yL, xL для сглаживающего сплайна являются параметрическими функциями параметра а, то приведем другую формулу для вычисления функции кривизны
Построение изогеометрического сглаживающего сплайна (первый метод
Априорная информация о поведении функции на интервалах сетки А задается системой неравенств (3.2). Очевидно, что эти неравенства будут выполняться в отдельных узлах сетки, попавших в эти интервалы. Таким образом, подставляя в (3.2) вместо х узлы xh приходим к системе неравенств (3.1). Как отмечалось в первой главе, задача построения сглаживающего сплайна сводится к нахождению коэффициентов at, bt, ct, dt. Для построения сплайна будем использовать «естественные» краевые условия вида: Sn,a{a) = S a{b) = 0. (3.3) Напомним, что сглаживающий кубический сплайн с краевыми условиями (3.3) доставляет минимум следующему функционалу Fa [S] = a \(S\x)f dx + XP;\ft - S(Xi))2 , (3.4) a i =l в котором a О - параметр сглаживания, pt О весовые множители, равные С ТОЧНОСТЬЮ ДО КОНСТаНТЫ ДИСПерСИИ (Tj . Естественно, что этот сплайн не учитывает ограничения вида (3.1). Рассмотрим процедуру учета этих ограничений. Согласно лемме 1.1 функционал (3.4) для кубических сглаживающих сплайнов, удовлетворяющих краевым условиям (3.3), допускает представление Fa[s] = asTQs + (s-f)TP(s-f), (3.5) где s- n-мерный вектор, составленный из значений 5( ,), /- вектор значений ft, P = diag{pi,p2,.-,pn}, Q- симметричная (пхп) матрица, определенная в главе 1. Заметим, что двухсторонние ограничения 1-го типа могут быть записаны в виде системы односторонних ограничений: / (хг) dS , і є //. Здесь к = 1 для ограничений вида p (xt) /4i ПРИ этом = fmL» к = -1 для ограничений вида р (х,) / / , при этом dS = -/ , 1 = 0,1,2. Если обозначить S(XJ) = S;, DQ = E - единичная матрица, то для узлов сетки xt, для которых существует ограничение на значение функции (то есть, ІЄІ0) очевидно, можем записать {DQs}. 40),ieIQ. (3.6) Для получения аналогичной записи для ограничений на производные рассмотрим следующие леммы. Лемма 3.1 Точечные ограничения S"(xj) dj , iel2 для кубических сплайнов могут быть записаны в виде системы неравенств вида {D2s}. \d . (3.7) Доказательство В главе 1 показано, что для интерполяционного кубического сплайна справедливо равенство AM = Hs, где М = (Mi,M2,...,Mn) - вектор коэффициентов Mj из представления сплайна (1.44). Там же показано, что для таких сплайнов 5" (хг) = 2Мг-. Следовательно, если обозначим s = (S"(xl),S"(x2),...,S (xN))T, можем записать s = 2A lHs = D2s. Тогда условие 5" (д:г) d\ эквивалентно условию {D2s}i Лемма 3.2 Точечные ограничения S (xj) d} , z e/j для кубических сплайнов могут быть записаны в виде системы неравенств вида условия 5"(х/) й? может быть записано в виде {D s) . dj Используя (3.6), (3.7) и (3.8), можем записать обобщенное ограничение на /-ю производную для г-го узла сплайна в виде {Ds). dt, где { }. - і-я строка матрицы Dj, и [d]. - і-й элемент вектора dj. Таким образом, все ограничения (3.1) могут быть записаны в виде Ds d. Сформулируем вариационную задачу построения кубического сплайна, удовлетворяющего ограничениям (3.1). В работе [20] этот сплайн назван дескриптивным. Введем матрицу Ua = 2(aQ + Р) и вектор и = -2Р/. Тогда, используя (3.5), можем представить вариационную задачу в виде \\ т т пшн— s Uas + s и + const , (3.9) при ограничениях Ds d. (ЗЛО) Лемма 3.3 При любых а 0 и векторе / существует единственное безусловное решение 5 вариационной задачи (3.10). Доказательство Поскольку матрица Q положительно полуопределена (по построению), а матрица Р - положительно определенная диагональная, то при любом а 0 матрица Ua положительно определена, а минимизируемый функционал является строго выпуклым. Следовательно, рассматриваемая вариационная задача имеет единственное решение Несмотря на то, что дескриптивный сплайн Sn(x) в узлах удовлетворяет ограничениям (3.1), между узлами эти ограничения могут не выполняться. Например, если Sn(x) удовлетворяет ограничениям Sn (хг) О,
Sn(xi+\) 0, то возможна смена знака производной между узлами xt, хм. Поэтому, введем дополнительные ограничения. Сплайн Sn(x) назовем изогеометрическим сглаживающим кубическим сплайном с дефектом 1, если он удовлетворяет «точечным» ограничениям (3.1) и дополнительно выполнены условия
Существование и единственность робастного сплайна
Для построения робастного сплайна преобразуем функционал (4.4) к более удобному виду. Используя результаты леммы 1.1, перепишем функционал в виде 1. При заданном параметре сглаживания находим вектор s =lsi,...,sn\ , значение которого доставляет минимум функционалу (4.27). 2. По вычисленным значениям s( строим интерполяционный сплайн с требуемыми краевыми условиями. Рассмотрим первый этап. Для функций p(t), рассмотренных в параграфе 4.2.1, не удается получить линейную систему алгебраических уравнений для нахождения точки минимума s , как это имело место для p(t) = t p(t) = t2, т.е. квадратичного функционала невязки. Поэтому приходится для решения вариационной задачи использовать итерационные процедуры минимизации. Возникает вопрос: существует ли решение вариационной задачи (4.28)? Для ответа на него проведем следующие рассуждения. Лемма 4.1 Функционал (4.27) является выпуклым вниз, если функция p(t) выпуклая. Причем если он строго выпуклый вниз, функционал - также строго выпуклый.
Для выяснения вопроса существования решения задачи (4.28) воспользуемся результатами леммы 4.1. Поскольку функционал (4.27) является выпуклым вниз, то его градиент должен монотонно невозрастать. Следовательно, для того, чтобы для каждой проекции градиента существовало нулевое значение необходимо показать, что для этой проекции существуют положительное и отрицательное значения.
Известно, что одним из решений задачи Qs = 0 является вектор s = 0. Будем считать, что решением задачи р \—— =0 является вектор s2=f.
(-f\ Тогда VFa[s\] = p — , a VFa[s2] = 2aQf. Поскольку матрица Q \ d )
положительно полу определена, sign Qf = sign/ для всех проекций, для которых собственные числа отличны от нуля. Тогда, если функция p (t) сохраняет знак аргумента, получаем, что VFa (s\) —f, a VFa [s2 ] f.
Следовательно, каковы бы ни были исходные данные /, знак градиента в точках $1 и 2 - противоположен. Значит, в силу монотонности функции градиента, между этими точками существует некоторая точка s , такая, что VFa[s3] = 0.
РАЯ проекций, соответствующих нулевым собственным числам (а их две) 2aQs = 0. Таким образом, для существования нулевого градиента (VFa(s)y
необходимо, чтобы производная вектора невязки достигала нуля в некоторой своей точке. Если градиент в этой точке не существует, достаточно просто существования минимума функции невязки по этим проекциям.
Лемма доказана.
Единственность решения определяется из леммы 4.1, а именно, если функционал (4.27) - строго выпуклый, решение - единственное, если не строго, решений может быть множество. Кроме того, в силу выпуклости функционала вниз, если найден локальный минимум, то он является и глобальным. Теперь рассмотрим вопросы существования и единственности решения задачи (4.28) в применении к рассмотренным выше функций невязок. Исходя из вида этих функций, следует, что только функция невязки p (t) = t строго выпуклая, только для этой функции невязки существует единственное решение. Функции невязки / (t) = \t\ и Рз(/) " нестрого выпуклые, для них существуют решения, но они не единственные, хотя и глобальные. Поскольку функция невязки р4 выпукло-вогнутое, то о глобальности решения для такой функции ничего сказать нельзя. Хотя, в силу того, что производная этой функции невязки сохраняет знак аргумента, то согласно лемме 4.2, решение все равно существует Приведем один из способов решения системы (4.27). На каждом шаге фиксируется матрица Г . В этом случае можно вычислить производную функционала: F (S) = 2(aQ + T(S))S -2T(S)f. Следовательно, решение системы (4.27) будет иметь вид:
Решение не всегда можно достигнуть из любой начальной точки. Например, в случае функционала невязки Хубера при удалении s от f матрица aQ + Т вырождается, поэтому последовательность точек S может удаляться от /, тем самым, делая систему все больше вырожденной. Этот алгоритм предложен Утрерасом в работе [63]. Он рассматривает построение робастных сплайнов с произвольным функционалом невязки. Рассмотрим задачу минимизации функционала (4.27) с произвольным функционалом невязки Ф($-/)єС [a,b].
Требования к программному и аппаратному обеспечению
Программный комплекс «Spline Tool» предназначен для решения задач интерполяции и дифференцирования таблично заданных результатов экспериментов с использованием аппарата интерполяционных, сглаживающих, сглаживающих изогеометрических и робастных кубических сплайнов. Комплекс состоит из следующих компонентов: 1. Подсистема ввода исходных данных. 2. Подсистема вычисления сплайнов. 3. Подсистема отображения и сохранения результатов расчетов. Эти компоненты интегрированы в одном приложении. Все компоненты написаны на языке программирования С#. Для реализации этих компонентов была написана библиотека для платформы .NET, которая реализует основные операции для работы с матрицами, алгоритмы решения СЛАУ методами LU-разложения и SVD-разложения, методы решения нелинейных вариационных задач, описанные в диссертации. Эта библиотека реализована в виде компонента платформы .NET и может использоваться независимо от приложения. Описание этого компонента приведено ниже.
Для работы программы необходима нормально функционирующая операционная система Windows 98, Windows NT SP6, Windows 2000 SP2, Windows XP для семейства процессоров x86. Кроме этого, необходимо наличие пакета Microsoft .NET Framework Redistributive, версии не ниже 1.0, который можно взять на сайте Microsoft. Специальных требований по производительности процессора, объему оперативной памяти, свободному месту на жестком диске, характеристикам подсистем ввода/вывода нет, но производительность работы программы зависит от этих параметров.
1. Область числовых данных. Она расположена в левой части основного окна. В ней производится ввод и отображение всей числовой информации, в том числе - входной информации, значений сплайна и его производных в узлах сетки, краевые условия, информация по выбору параметра сглаживания и т.д. 2. Область графиков. Она расположена в правой средней части основного окна приложения. В данной зоне выводятся графики сплайнов и графики исходной функции. 130 3. Область краткой информации о сплайне. Она расположена в правой верхней части основного окна приложения. В ней выводятся основные характеристики строящегося сплайна такие как имя и тип текущего графика, краевые условия и параметр сглаживания. 4. Область журнала работы программы. Она расположена в правой нижней части основного окна. В ней отображается протокол работы программы. 5.4. Подготовка информации для работы комплекса Программный комплекс «Spline tool» может работать с информацией, которая подготовлена заранее. Он может считывать информацию из текстовых файлов. Для этого данные должны быть представлены специальным образом
Как отмечалось выше, подсистема ввода и отображения числовых данных предназначена для работы пользователя с числовыми характеристиками строящихся сплайнов. Данная подсистема оформлена в виде набора таблиц и форм. С помощью них вводится следующая информация: Значения абсцисс и ординат для исходной функции. Краевые условия для сплайна Способ выбора параметра сглаживания (методом перекрестной значимости, L-кривой, непосредственный ввод пользователем) Ограничения на геометрию функции - для построения изогеометрического сглаживающего сплайна. После окончания вычисления сплайна в таблицу, содержащую исходные данные о функции выдается информация о значениях сплайна и его первой и второй производных
Подсистема вычисления сплайнов реализует алгоритмы, описанные в диссертации. Она состоит из трех компонент: 1. Компонента работы с матрицами. 2. Компонента вычисления параметра сглаживания 3. Компонента вычисления сплайнов, в том числе: 1) Субкомпонента вычисления интерполяционного сплайна 2) Субкомпонента вычисления сглаживающего сплайна 3) Субкомпонента вычисления изогеометрического сглаживающего сплайна. 4) Субкомпонента вычисления робастного сплайна Все компоненты оформлены в виде одной библиотеки, которая может быть доступна для любого приложения платформы .NET. Все компоненты размещены в пространстве имен (namespace) MatLib, в котором для каждого компонента существует собственное подпространство имен. Рассмотрим каждую из них подробнее.
Это компонента предназначена для выполнения матричных операций, таких как операции сложения, умножения, инверсии матриц, а так же решения СЛАУ. Она располагается в пространстве имен Matlib. И включает в себя следующее: 1. Класс Vector - для работы с векторами. В этот класс включены следующие операции: 1) Операция создания вектора 2) Операция доступа к элементам вектора - оператор [] 3) Операторы сложения и вычитания векторов 4) Операторы умножения векторов, умножения и деления вектора на вещественное число 5) Операция извлечения подвектора из вектора 6) Операция вычисления евклидовой нормы вектора 2. Класс Matrix - для работы с матрицами. В него включены следующие операции: 1) Операция создания матрицы 2) Операция сложения матриц 3) Операции умножения матриц, умножения матрицы на вектор, умножения матрицы на вещественное число. 4) Операция транспонирования матрицы 5) Операторы извлечения элемента матрицы и вектора-столбца из матрицы
