автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Сглаживающие изогеометрические и робастные сплайны: методы и алгоритмы

кандидата технических наук
Березовский, Михаил Витальевич
город
Новосибирск
год
2004
специальность ВАК РФ
05.13.18
цена
450 рублей
Диссертация по информатике, вычислительной технике и управлению на тему «Сглаживающие изогеометрические и робастные сплайны: методы и алгоритмы»

Автореферат диссертации по теме "Сглаживающие изогеометрические и робастные сплайны: методы и алгоритмы"

На правах рукописи

Березовский Михаил Витальевич

СГЛАЖИВАЮЩИЕ ИЗОГЕОМЕТРИЧЕСКИЕ И РОБАСТНЫЕ СПЛАЙНЫ: МЕТОДЫ И АЛГОРИТМЫ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

автореферат диссертации на соискание ученой степени кандидата технических наук

Новосибирск - 2004

Работа выполнена в Новосибирском государственном архитектурно-строительном университете

Научный руководитель:

Официальные оппоненты:

доктор физико-математических наук, профессор Воскобойников Юрий Евгеньевич

доктор физико-математических наук, Бородулин Александр Иванович.

кандидат технических наук, доцент Лисицин Даниил Валерьевич

Ведущая организация:

Институт вычислительной математики и математической геодезии СО РАН (г. Новосибирск)

Защита состоится 29 сентября 2004 года в 10.00 на заседании диссертационного совета Д 212.173 06- при Новосибирском государственном техническом университете (630092, г. Новосибирск, пр. Карла Маркса 20)

С диссертацией можно ознакомиться в библиотеке Новосибирского государственного технического университета

Автореферат разослан августа 2004

Ученый секретарь диссертационного совета Д 212.173 06, к.т.н, доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Одними из основных задач, возникающих при обработке результатов экспериментов, являются задачи аппроксимации и дифференцирования табличных данных. Обычно эти данные искажены, шумами, и для обработки таких данных используются сглаживающие сплайны (чаще всего кубические).

При построении сглаживающих сплайнов необходимо регулировать их гладкость. Это осуществляется путем выбора специального параметра - параметра сглаживания. Если этот параметр будет малым, в полученном решении сохраняются высокочастотные составляющие, при выборе большого значения, решение становится более гладким, и при выборе слишком большого параметра, решение становится «переглаженным», и из него исчезает полезная информация. Поэтому решение задачи выбора этого параметра является одной из важнейших задач при построении сглаживающих сплайнов.

Во многих случаях у экспериментатора имеется дополнительная информация о свойствах приближаемой функции, например, о положительности или отрицательности функции и (или) ее производных на некоторых отрезках интервала определения функции. Целесообразно -учесть эту априорную информацию при построении сглаживающего сплайна, или, другими словами, необходимо сохранить в сплайне геометрические свойства функции, задаваемые системой априорных ограничений. В работах. Б.И.Квасова, А.И.Гребенникова, В.Л.Мирошниченко рассмотрены.так называемые изогеометрические сплайны, которые. сохраняли, геометрию приближаемой функции, но при очень существенном условии: табличные значения должны соот-ветствовать1 геометрическим свойствам функции. К сожалению, в эксперименте регистрируются «зашумленные» значения функции, которые, чаще всего, не соответствуют (из-за шума измерений) имеющейся априорной информации. Поэтому, задача построения сплайна по за-шумленным измерениям, удовлетворяющего априорной информации о геометрии приближаемой функции является актуальной.

Возможны ситуации, когда амплитуда шума измерений в несколько раз превосходит измеряемые значения функции, то есть некоторые измерения являются аномальными, число которых может составлять 10-20% от общего числа измерений. Сглаживающие сплайны, при построении, которых использовался квадратичный функционал невязки очень «чувствительны» к аномальным измерениям: значения сплайна «подтягиваются» к аномальным измерениям, что существенно

РОС. иЛЦ*ОиЛЛ!»КА9 »нывотыа '

увеличивает ошибки сглаживания и дифференцирования экспериментальных данных. Поэтому задача построения сглаживающих сплайнов, робастных (нечувствительных) к аномальным измерениям также является актуальной задачей.

Цель работы Разработка вариационных подходов, алгоритмов и программного обеспечения построения сглаживающих сплайнов, учитывающих имеющуюся у экспериментатора априорную информацию и робастных к аномальным измерениям.

Методы исследования Методы сплайн-функций, математического программирования, теории вероятностей, математической статистики и численного анализа.

Научная новизна

1. Введен новый класс сглаживающих сплайнов - изогеометрический сглаживающий сплайн, позволяющий учесть априорную информацию о значениях приближаемой функции и ее производных не только в узлах сетки, но и на интервалах.

2. Доказана теорема о существовании и единственности изогеомет-рического сглаживающего сплайна. Предложены эффективные алгоритмы построения изогеометрического сплайна

3. Введен новый класс сплайнов - сглаживающие сплайны, робаст-ные на классах распределений шумов Сформулирован вариационный подход к построению робастных сплайнов.

4. Доказана теорема о существовании и единственности робастных сплайнов. Предложены вычислительные схемы построения робастных сплайнов.

Практическая ценность работы заключается в следующем.

Методы и алгоритмы, разработанные в диссертационной работе дают возможность эффективно использовать изогеометрические и ро-бастные сплайны при обработке различных экспериментальных данных, выбирать параметр сглаживания при большом уровне шума и при коррелированном шуме.

Разработан пакет прикладных- программ «Spline tool», реализующий построение интерполяционных и сглаживающих сплайнов (в том числе изогеометрических и робастных). Он имеет удобный и понятный интерфейс и реализован для наиболее массовых и производительных операционных систем. Пакет может обрабатывать данные; которые представлены в различном виде (вводятся с клавиатуры, загружаются из файла или запрашиваются из базы данных).

Пакет,прикладных программ «Spline tool» использовался при обработке данных летного эксперимента в Институте теоретической и

прикладной механики СО РАН и это позволило получить из эксперимента более достоверную информацию об исследуемых аэродинамических процессах. Кроме того, пакет использовался для обработки данных слежения за траекториями спутников во ФГУП «Сибирский НИИ метрологии», что позволило расширить набор методов слежения, используемый в этом институте.

Апробация работы. Результаты диссертационной работы обсуждались на семинарах научного направления «Создание новых информационных технологий и систем автоматизированного проектирования» Новосибирского государственного архитектурно-строительного университета (НГАСУ) и докладывались на следующих конференциях:

• международная Байкальская школа-семинар «Методы оптимизации и их приложение» г. Иркутск, 1998 г;

• международная конференция KORUS-99;

• всероссийская конференция «Алгоритмический анализ некорректных задач», г. Екатеринбург, 1998г;

• российская конференция «Обратные и некорректно поставленные задачи», г. Москва 1998; 1999 г;

• научно-техническая конференция Новосибирского государственного архитектурно-строительного университета (Новосибирск) 1999, 2000 годов.

• Сибирская конференция «Методы сплайн-функций», посвященная памяти Ю.С. Завьялова (Новосибирск) 2001 г.

• Четвертый Сибирский Конгресс по прикладной и индустриальной математике, посвященный памяти М.А. Лаврентьева (ИН-ПРИМ-2000)

Публикации. По теме диссертации опубликовано 8 работ. Структура и объем диссертации. Диссертация состоит из введения, шести глав, заключения, списка литературы и содержит 167 страниц, включая 11 таблиц и 34 иллюстрации. Список литературы содержит 94 наименования.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновываются необходимость построения двух новых классов сглаживающих сплайнов - изогеометрических и роба-стных, а также обсуждаются проблемы корректной оценки параметра сглаживания. Кратко излагается содержание диссертационной работы по главам.

Глава 1 содержит необходимые для изложения результатов работы алгоритмы построения сглаживающих кубических сплайнов.

Вводятся точностные характеристики сглаживающего сплайна, и формулируется вариационная задача выбора параметра сглаживания по заданным точностным характеристикам.

В § 1.1 излагаются методы построения интерполяционного сплайна, необходимые для дальнейшего изложения.

В § 1.2 рассматривается задача построения сглаживающих сплайнов. Излагаются существующие методы их построения. Кроме того, формулируется вариационная задача построения сглаживающего сплайна Sa (х) из условия минимума функционала

где - случайная погрешность измерения

значения

При этом рассматриваем естественные краевые условия-

Лемма 1.1. Пусть заданы краевые условия (2). Тогда функционал энергии можно представить квадратичной формой

/(я; (*))2 =

о

где 5 (дт2),..., 5а (*„))Г- вектор, составленный из значений

сплайна £в(х) в узлах x, матрица ¡2 размером пхп положительно

полуопределена и имеет два нулевых собственных значения. Эта лемма позволяет переписать (I) в виде

а построение сглаживающего сплайна 5„ (*) представить двумя этапами:

Этап 1. Нахождение вектора 5а как решение вариационной задачи

шш

5 €£"

— 5ГС/„5 + + СОШ 2 ' ■

проекции которого равны значению сплайна Ба (*) в узлах х1,

(1)

(3)

(4)

Этап 2. По вектору строится интерполяционный сплайн, тождественно равный сглаживающему сплайну Ба (х).

Теорема 1.1. При любых а > 0 и векторе / существует единственное решение $а вариационной задачи(4).

В § 1.4 вводятся точностные характеристики сглаживающего -сплайна, которые трактуются как низкочастотный фильтр. При предположениях

а) шаг сетки одинаков и равен X = х(+| — л:,;

б) весовые множители р, = р, / = 1,2,...,/»,

Частотная характеристика сглаживающего сплайна предбгавля-ется соотношением

вт

1-С05й>Л"

, + 2 ц соб озХ + 7р соь2й)Х где р = ар!Хг, ц = Х/6~4арГХ\ Я = 2Х/3 + 6ар/Хг.

Аппаратная функция Аа (л:) сплайна связана с На (су) преобразованием Фурье ,

Ь (*) = ] На (ф) ехр (/«,) ¿0)

и эта аппаратная функция характеризует систематическую ошибку -сглаживания и дифференцирования:,чем меньше «ширина» функции тем меньше систематическая ошибка, сглаживания и'диффе-ренцирования, В качестве числовой характеристики аппаратной функции примем ее эквивалентную ширину, выражаемую формулой

Получено, что дисперсия случайной ошибки вычисле-

ния производной /'^(х). связана с дисперсией шума измерения формулой а* (а) = Кк » где. Кк (а) - коэффициент передачи дисперсии - а*.

Лемма 1.21 Ширина <£,(#) аппаратной функции является монотонно возрастающей функцией а , а дисперсия (а) и коэффи-

(5)

циент передачи дисперсии Кк (а) монотонно убывающими функциями а, то есть,

°'*(а.)>0'*(аг2); М«|)>А'*(а2). если ах<аг. (6)

Величины (а), ст'(а), достаточно полно описывают

фильтрующие свойства сплайна, поэтому они названы в работе точностными характеристиками сплайна.

Противоречивое влияние параметра а на величины систематической и случайной ошибок (см (6)) позволяет подойти к выбору параметра а , как к задаче построения (синтеза) сплайна с заданными точностными характеристиками. Задача синтеза сглаживающего сплайна формулируется в виде следующих вариационных задач

Задача А: ¡пГ&Да) при ограничении Кк{а)<Ккпр (7)

Задача В: ¡п£/^(а) при ограничении 5) (от) < дпр (8)

Решение задачи А синтезирует сплайн с максимальным-разре-шениемг (минимальная систематическая ошибка) при ограничении на-коэффициент передачи дисперсии Решение задачи В минимизи-

рует коэффициент передачи дисперсии при гарантированном

значении ширины аппаратной функции.

Теорема 1.2. Решение вариационных задач (7), (8) существуют, единственны и определяются как решения следующих нелинейных уравнений

• Решение задачи А есть корень нелинейного уравнения

Кк{а) = Ккпр; (9)

Решение задачи В есть корень нелинейного уравнения

= (10)

Сформулированные задачи А и В наполняют задачу выбора параметра сглаживания содержательным смыслом и позволяют интерпретировать построенный при таком параметре сплайн в терминах измерительных систем, используя понятие аппаратной функции, частотной характеристики, полосы пропускания и т.д.

Глава 2 посвящена исследованию способов выбора параметра сглаживания. Как следует из формулы (1), гладкость сплайна определяется параметром а . Если этот параметр близок к нулю, сплайн бу-

дет близок к интерполяционному, следовательно, в. построенном сплайне (а особенно в его производных) будут присутствовать «вредные» высокочастотные составляющие, обусловленные шумами г) . Если этот параметр выбрать слишком большим, сплайн будет, «переглаженным», то есть, в нем будут сглажены «тонкие» детали функции

При решении задачи оценки параметра сглаживания возможно существование различной априорной информации. Если заданы дисперсии случайных величин , то оценить оптимальное значение параметра сглаживания, минимальную среднеквадратическую оценку сглаживания можно на основе критерия оптимального сглаживания сплайна.

Однако, чаще всего априорная информация об уровне шума отсутствует. В этом случае для оценки параметра сглаживания чаще-всего применяется метод перекрестной значимости. В диссертации предлагается еще один метод оценки параметра сглаживания - метод L-кривой. Этот метод предложен Хансеном при построении регуляризи-рованных решений плохо обусловленных СЛАУ. В диссертации этот метод развит для выбора параметра сглаживания.

Параметр сглаживания сплайна выбирается исходя из баланса величин двух функционалов: функционалов невязки и функционала сглаживания сплайна. Для этого стпоится т.н. Т.-кпитадя. то есть множество точек с координатами

у, (а) = 1п |(5; (х))г (1х. Тогда оценкой параметра сглаживания выбираем максимум кривизны этой кривой, вычисляемый из формулы

Из проведенных вычислительных экспериментов следует, что метод L-кривой для некоррелированного шума дает оценки параметра сглаживания, близкие к оценкам метода перекрестной значимости. Однако, при корреляции шума оценки по L-кривой существенно лучше по сравнению с методом перекрестной значимости.

Глава 3 посвящена построению изогеометрического сглаживающего сплайна, то есть сплайна, который учитывает априорную ин-

формацию в виде ограничений на значения функции и ее производных на заданных интервалах.

Предполагается, что функция /(х) в узлах дс,, Х1 - 1,2,...,л сетки

Д = = х, <... < <х„ = ¿>} задана своими значениями £ = /(х1) + , где ту, - погрешность измерения - случайная величина с нулевым средним и дисперсией «г/ .

В § 3.1 приведена.классификация априорной информации, заданной в виде ограничений назначения функции и ее производных. Введены два типа ограничений.

Тип 1. Ограничения в узлах сетки

Априорная информация задается в виде системы неравенств, для значений функции /(*) или ее производных /^(дт) в узлах таблицы, т.е.

где > " минимальное и максимальное допустимые значения производной /-го порядка /и,) в узлах-х1, - множество, составленное из индексов узлов сетки

Тип 2. Интервальные ограничения

Ограничения на значения функции или ее производной задаются на интервалах аргумента.

Далее в § 3.2 и § 3.3 предложены алгоритмы построения изогео-метрического сглаживающего сплайна. Первый из них состоящего из трех этапов.

На первом этапе строится система ограничений (11) в узлах х, по имеющейся априорной информации о геометрии функции.

На втором этапе строится, дескриптивный сглаживающий сплайн, удовлетворяющий системе ограничений (11).

Для перехода от системы ограничений (11) к системе ограничений в терминах вектора доказывается следующая

Лемма 3.1 Систему ограничений (11) для сглаживающего кубического сплайна можно записать в виде

где D - прямоугочьная матрица, составленная из строк матриц 0а,01,й2, связывающих значения производных / = 0,1,2 в узле

х1 с проекциями вектора .

На основе (4) формулируется следующая вариационная задача:

ш1п

при ограничениях

Решение этой задачи - вектор содержит значения кубического сплайна Ба (х) в узлах х1, который удовлетворяет ограничениям

(11) и назван дескриптивным сглаживающим сплайном. Доказана следующая

Теорема 3.к Решение вариационной задачи (13), (14) существует и единственно, если решением системы

является нулевой вектор

Эта теорема дает не только условия существования и единственности. Исходя из нее, можно сделать вывод об избыточности априорных ограничений.

Для повышения вычислительной эффективности алгоритма нахождения решения предлагается переход от задачи (13), (14) к двойственной по Лагранжу задаче

шш

при условии

где - вектор размерности

После вычисления решения // этой вариационной задачи, вектор х* определяется соотношением

где - решение задачи (4) при выбранном параметре сглаживания Его выбор рекомендуется осуществлять на основе решения задач (7), (8).

На третьем этапе строится изогеометрический сплайн по «хорошим» данным, полученным на предыдущем этапе А именно, проекции вектора 5*, построенного на предыдущем этапе, трактуются как исходные данные, соответствующие требуемой геометрии приближаемой

(14)

(16) (17)

(18)

функции. По этим данным строится изогеометрический сплайн с использованием эрмитовых сплайнов.

Второй алгоритм основан на решении задачи квадратичного программирования с нелинейными ограничениями. Он также состоит из трех этапов:

1. формирование нелинейной системы ограничений по заданной априорной информации:

2. решение задачи квадратичного программирования с нелинейной системой ограничений, в результате которого получаем точки сплайна с правильной геометрией,

3. построение интерполяционного сплайна ло полученным данным

Несмотря на внешнюю схожесть эти два алгоритма существенно отличаются системой ограничений, а, следовательно, и методами решения задачи.

В § 3.4 приводятся результаты вычислительного эксперимента и обработки реальных экспериментальных данных. Эти результаты показали высокую эффективность применения изогеометрических-сглажи-вающих сплайнов.

Приведем результаты одного вычислительного эксперимента, в

котором значения функции на отрезке

хе[0,10] искажались нормально распределенным шумом г/1 с нулевым средним с относительным-уровнем шума 20% от максимального значения функции. В качестве ограничений использована следующая априорная информация

/(х)>0, * е [0,10]; /'(х)>0, *е[0,1.75];/'(х)£0, [1,4.5];

На рис. 1 приведены: зашумленные значения обозначенные символом ; Значения сглаживающего сплайна, построенного без учета ограничений - пунктирная линия; значения изогеометрического сглаживающего сплайна, построенного с учетом ограничений (19) -символ

Глава 4 посвящена построению нового класса сплайнов— роба-стных сглаживающих сплайнов, нечувствительных к нарушению априорных предположений о плотности распределения шума Они отличаются от обычных сглаживающих сплайнов тем, что в функционале

(1) второе слагаемое, названное функционалом невязки «образуется с помощью функции отличной от квадратичной.

В § 4. Ь формулируется задача построения робастного сглаживающего сплайна-Рассмотрена модель измерений вида

В каждом узле ^значение /(*,) искажается одним из двух шумов: г) - с вероятностью (!—}') или е1 с вероятностью у, при этом

Вводится функционал вида н

(¿-вд)

(21)

Второе слагаемое будем называть функционалом невязки, образованным, функцией p(t). Функция' p{t) должна удовлетворять условиям: а) р(0) = 0; б) производная i//(t) = p'(t) имеет следующие знаки: у/(г)>О,если />0 и ^(0<0,если г<0.

Рис 1; Изогеометрический сглаживающий сплайн..

Величина d исполняет роль нормирующего множителя и зависит от дисперсии шума.

Функцию доставляющую минимум (21) и удовлетво-

ряющую условиям: а) на каждом отрезке [х,,*,^) является кубическим многочленом; б) на интервале [а,Ь] имеет непрерывную вторую производную, назовемробастным сглаживающим сплайном

Для выбора функции р{() рассмотрены несколько классов распределений шума />(и) в каждом классе определено устойчивое

распределение, принятие которого в качестве распределения шума приводит к минимальной потере качества оценивания методом максимального правдоподобия.

1. Класс распределений с ограниченной дисперсией. Распределения такого класса возникают при проведении экспериментов при одних и тех же условиях. В этом классе усто? г ляется нормальным с плотностью

2. Класс невырожденных распределений. Распределение такого класса возникает при проведении экспериментов при меняющихся условиях. В этом классе устойчивь~~----------у^~ием является экспоненциальное с плотностью

25

3. Класс распределений, образованный суммой распределений. Распределения этого класса служат для описания общей модели измерений (20), и в общем виде плотность таких распределений представляется выражением

где - любое симметричное относительно 0 распределение.

Устойчивым в этом классе является распределение с плотностью

Введенные таким образом устойчивые распределения позволяют ослабить требования к априорной информации о статистических свойствах шума измерения и достаточно указать априори только класс распределений, к которому относится «истинный» шум измерения.

В разделе 4.1.2 вводятся определения сглаживающих сплайнов, робастных на классах распределений шумов.

1. Сглаживающий сплайн, доставляющий минимум функционалу (21) с функцией

р,(1) = 1г (22)

назовем робастным на классе распределений с ограниченными дисперсиями:

2. Сглаживающий сплайн, доставляющий минимум функционалу (21) с функцией

А (0 = 14 (23)

назовем робастным на классе невырожденныхраспределений.

3. Сглаживающий сплайн, доставляющий минимум функционалу (21) с функцией

(24)

назовем робастным на классе невырожденных смешанных распределений.

Дополнительно была введена функция

(25)

используемая в теории робастного оценивания. Предложены соотношения для определения величины а, входящих в (24)-(25).

В § 4.2 рассматривает алгоритмы построения робастных сглаживающих сплайнов. Для построения эффективных вычислительных алгоритмов предлагается представление функционала невязки в виде

я

fr \

1=1

где ^(s) - (NxN)- матрица, зависящая ,от значений S'(xJ). Тогда,

построение робастного сглаживающего сплайна можно представить двумя этапами:

Этап 1. Решение вариационной задачи

tnin[/ (aQ + Тт {s))s-2sTTm (s)f + fTT„ (*)/]

(26)

(27)

Этап 2. Построение интерполяционного кубического сплайна по табличным значениям

Для различных функций р('), определяемых соотношениями (22)-(25) доказаны теоремы, условия которых гарантируют положительную определенность матрицы

В разделах 4.2.2-4.2.4 построены и анализируются различные алгоритмы минимизации функционала (27).

В § 4.3 анализируются различные способы выбора параметра сглаживания. Показано, что наилучшее приближение дает выбор а по заданным точностным характеристикам из решения задач (7), (8).

§ 4.4 рассматривает ряд вычислительных экспериментов, иллюстрирующих возможности робастных сплайнов по сглаживанию и дифференцированию данных, содержащих аномальные измерения. Приведем результаты одного из экспериментов.

Значения функции /(х)

, в узлах х,, / = 1,...,40 иска-

жались шумом в соответствии с моделью (20) с параметрами = 2, у =0.1, сг*=0.1, то есть, имеет место класс распределений образованный суммой распределений. По данным были построены сглаживающие сплайны с функциями невязок р, (/) - /?4 (/) . Точность построенного сплайна характеризовалась относительной среднеквадратичной ошибкой сглаживания, определяемой соотношением:

Ь^±Ш-/(*.))г/рЧ*.) (28)

где точное значение функции в точке Значения этой ошибки

приведены в таблице I.

Таблица 1

Из таблицы видно, что наименьшая ошибка сглаживания у роба-стного сплайна, соответствующего функции (ошибка заметно

меиыне по сравнению с обычным сглаживающим сплайном с функцией рх (/) ). В рассматриваемом эксперименте рА (/) оказалось предпочтительнее py{t) из-за игнорирования аномальных измерений с большой амплитудой выбросов

В главе 5 описывается программный комплекс «Spline Tool», предназначенный для построения сплайнов с использованием алгоритмов, предложенных в диссертации. Этот комплекс способен считывать данные из различных источников: из подготовленных файлов, из баз данных; вводить данные с клавиатуры; выводить результаты в файл и на экран, отображать графики.

В главе 6 приведены результаты обработки данных шести реальных экспериментов. Данные для одного из экспериментов предоставлены Институтом теоретической и прикладной механики СО РАН, данные остальных экспериментов - ФГУП Сибирский НИИ метрологии.

На рисунках 2 и 3 представлены результаты, наиболее интересные с точки зрения применения изогеометрических и робастных сплайнов, соответственно.

В первом случае, показанном на рис. 2 строился изогеометриче-ский сглаживающий сплайн с учетом априорной информации о невозрастании функции на всей области определения функции.

Кроме изогеометрического сплайна, обозначенного сплошной линией были построены обычный сглаживающий сплайн с тем же коэффициентом сглаживания (штрих-пунктирная линия) и сглаживающий сплайн с существенно большим параметром сглаживания (штриховая линия). Из рисунка видно, что обычные сплайны либо не выдерживают априорные ограничения, либо дают переглаженное решение.

Во втором случае было необходимо провести аппроксимацию данных, искаженных импульсной помехой. На рис. 3. представлен фрагмент графика, отображающего результат эксперимента. Кругами обозначены исходные данные. Измерение №9 - аномальное, его значение не попало в данный фрагмент, оно равно 29,8927.

Рис. 2 Обработка данных реального эксперимента с использованием изогеометрического сглаживающего сплайна

Рис. 3. Обработка данных реального эксперимента с использованием робастных сплайнов

Аппроксимация обычными сплайнами с разными коэффициентами сглаживания (тонкая и толстая сплошные линии) дает в области этого измерения существенное искажение результатов, в то время как применение робастных сплайнов (штриховая и пунктирная линии) позволяет избежать этого эффекта.

По результатам этих и других экспериментов можно сделать вывод, что методы, разработанные в диссертации, позволяют получить физически существенно более точные результаты по сравнению с традиционными сплайнами за счет использования априорной информации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

1. На основе метода L-кривой предложен новый алгоритм выбора параметра сглаживания, позволяющий успешно оценить оптимальное значение параметра даже в случае большого уровня шума или в случае коррелированности шума измерений.

2. Предложен новый класс сглаживающих сплайнов - изогеометри-ческий сглаживающий сплайн, позволяющий учесть априорную информацию о геометрии приближаемой функции даже а том случае, когда измеренные значения противоречат этой априорной информации.

3. Разработан эффективный алгоритм построения изогеометрическо-го сглаживающего сплайна и выполнен многочисленный вычислительный эксперимент, показавший существенное повышение точности решения задач сглаживания и дифференцирования зашумленных данных.

4. Предложен новый класс сглаживающих сплайнов - робастных сплайнов, обладающих малой чувствительностью к аномальным измерениям. Разработан алгоритм построения робастных сплайнов. Выполнены исследования эффективности этих сплайнов при обработке данных, искаженных шумами с различными распределениями.

5. Разработан комплекс программ «Spline Tool», предназначенный для обработки экспериментальных данных с использованием сплайн-функций. Этот комплекс включает в себя методы построения интерполяционного, сглаживающего, изогеометрического сглаживающего и робастного сглаживающего сплайнов. В нем реализована возможность получения данных как из файлов, так и из баз данных.

6. Комплекс программ «Spline tool» использован для решения ряда практических задач.

По теме диссертации опубликованы следующие работы.

1. М.В.Березовский, Ю.Е.Воскобойников Построение дескриптивных приближений с использованием локальных сплайнов. /11-я Байкальская международная школа-семинар Методы оптимизации и их приложения - Иркутск, 1998 - Труды конференции - с. 71-74

2. М.В.Березовский, Ю.Е.Воскобойников Построение дескриптивных приближений на основе рациональных сплайнов. / Алгоритмический анализ некорректных задач.- Екатеринбург, 1998 - Тезисы докладов Всероссийской научной конференции, посвященной памяти В.К. Ива-нова.-с. 53.

3. М.В.Березовский Робастные сглаживающие сплайны / Тезисы всероссийской конференции «Обратные и некорректно поставленные задачи» - Москва, МГУ, 1998 - с. 16

4. М.В.Березовский, Ю.Е.Воскобойников Изогеометрические сглаживающие сплайны. / Научный вестник НГТУ. - 1999. - №2(7) - с.3-13

5. M.V.Berezowsky Local approximation algorithms in B-spline basis // 3-rd international conference KORUS'99 (Abstract) - Новосибирск, 1999. -c.532

6. М.В.Березовский Изогеометрические сглаживающие сплайны в обратных задачах / Обратные и некорректно поставленные задачи (тезисы докладов конференции) - Москва, МГУ, 1999 - с.74

7. М.В.Березовский, Ю.Е.Воскобойников Робастные сглаживающие сплайны / Обратные и некорректно поставленные задачи (тезисы докладов конференции) - Москва, МГУ, 1999, - с. 74-75

8., М.В.Березовский Построение сплайнов с заданной геометрией/Труды НГАСУ. - 2003 - т.6 - №6(27) - с.27-31

Новосибирский государственный архитектурно-строительный университет (Сибстрин)

630008, Новосибирск, ул. Ленинградская, 113

Отпечатано мастерской оперативной полиграфии НГАСУ*

ТиражЛ 00 экз. Заказ № 30д% .2004.

04- 1 523 1

Оглавление автор диссертации — кандидата технических наук Березовский, Михаил Витальевич

Введение.

Глава 1. Кубические сплайны. Основные методы и алгоритмы.

1.1. Интерполяционный кубический сплайн.

1.1.1. Определение интерполяционного кубического сплайна.

1.1.2. Методы вычисления интерполяционного сплайна.

1.2. Сглаживающий кубический сплайн.

1.2.1. Определение сглаживающего кубического сплайна.

1.2.2. Методы вычисления сглаживающего сплайна.

1.3. Определение среднеквадратичного приближения.

1.3.1. Проблемы выбора параметра сглаживания.

1.3.2. Выбор размерности пространства В-сплайнов.

1.4. Частотная модель сглаживающего сплайна.

1.5. Выводы.

Глава 2. Выбор параметра сглаживания.

2.1. Алгоритмы оценивания оптимального параметра сглаживания.

2.1.1. Алгоритм выбора параметра сглаживания на основе критерия оптимальности.

2.1.2. Выбор параметра сглаживания на основе критерия перекрестной значимости (cross-validation method).

2.1.3. Выбор параметра сглаживания на основе метода L-кривой.

2.2. Выбор параметра сглаживания по заданным точностным характеристикам.

2.3. Сравнение методов выбора параметра сглаживания различными алгоритмами.

2.3.1. Исследование качества оценки параметра сглаживания при некоррелированном шуме.

2.3.2. Исследование влияния коррелированности шума на качество построения параметра сглаживания.

2.4. Выводы.

Глава 3. Изогеометрические сглаживающие сплайны.

3.1. Задача построения изогеометрических сплайнов.

3.1.1. Классификация априорной информации.

3.1.2. Подходы к решению.

3.2. Построение изогеометрического сглаживающего сплайна (первый метод).

3.2.1. Восстановление геометрии исходных данных.

3.2.2. Построение изогеометрического сплайна.

3.3. Построение изогеометрического сглаживающего сплайна (второй метод).

3.3.1. Построение системы ограничений.

3.3.2. Согласованность системы ограничений.

3.3.3. Алгоритм построения изогеометрического сглаживающего сплайна.

3.4. Вычислительный эксперимент.

3.4.1. Описание вычислительного эксперимента.

3.4.2. Результаты вычислительного эксперимента.

3.5. Выводы.

Глава 4. Робастные сплайны и алгоритмы их построения.

4.1. Робастный сглаживающий сплайн.

4.1.1. Устойчивые плотности распределения шумов.

4.1.2. Сглаживающие сплайны, робастные на классах распределений шумов измерений.

4.2. Алгоритмы построения робастных сплайнов.

4.2.1. Существование и единственность робастного сплайна.

4.2.2. Алгоритм №1 решения вариационной задачи.

4.2.3. Алгоритм №2 решения вариационной задачи.

4.2.4. Алгоритм №3 решения вариационной задачи.

4.3. Выбор параметра сглаживания вробастных сплайнах.

4.4. Вычислительный эксперимент.

4.4.1. Эксперимент 1. Восстановление данных, искаженных «смешанным» шумом.

4.4.2. Эксперимент 2. Восстановление данных, искаженных экспоненциальным шумом.

4.4.3. Эксперимент 3. Восстановление данных, искаженных нормальным шумом.

4.5. Выводы.

Глава 5. Комплекс программ «Spline Tool».

5.1. Характеристика программного комплекса.

5.2. Требования к программному и аппаратному обеспечению.

5.3. Описание интерфейса программного комплекса «Spline Tool».

5.4. Подготовка информации для работы комплекса.

5.4.1. Формат файла данных.

5.4.2. Формат файла априорных ограничений.

5.5. Подсистема ввода и отображения числовых данных.

5.6. Подсистема вычисления сплайнов.

5.6.1. Компонента работы с матрицами.

5.6.2. Компонента вычисления параметра сглаживания.

5.6.3. Компонента вычисления кубического сплайна.

5.7. Выводы.

Глава 6. Обработка данных реальных экспериментов.

6.1. Обработка экспериментальных данных изогеом етр и ч еским и сглаживающими сплайнами.

6.1.1. Обработка данных аэродинамического эксперимента.

6.1.2. Обработка данных системы слежения за спутниками использованием изогеометрическых сглаживающих сплайнов.

6.2. Обработка данных системы слежения за спутниками использованием робастных сплайнов.

6.3. Выводы.

Введение 2004 год, диссертация по информатике, вычислительной технике и управлению, Березовский, Михаил Витальевич

Одной из основных задач, возникающих при обработке результатов экспериментов, является задача интерполяции и дифференцирования табличных данных. Из-за сложности математических моделей экспериментов процесс точного их восстановления более трудоемок по сравнению с построением модели, близкой по свойствам к модели эксперимента. Для более точного приближения построенной математической модели к эксперименту, помимо информации, полученной в результате эксперимента, используется априорная информация, которая задает дополнительные ограничения на поведение функции.

Известно, что наилучшее приближение для функций класса Ж22 [а,Ь] с ъ точки зрения функционала энергии вида ск дают кубические а сплайны. То есть, кубический сплайн обладает минимальной кривизной среди всех интерполяционных функционалов, построенных по заданным точкам. Наиболее простым кубическим сплайном является интерполяционный кубический сплайн, методы вычисления которого являются базовыми для вычисления других видов сплайнов. Для учета информации о геометрии функции и для построения наиболее гладкого сплайна в работах [29, 30, 31] предложен сплайн специального вида, т.н. изогеометрический сплайн.

Однако область применения таких сплайнов ограничена таблицами, содержащими точные значения интерполируемой функции. То есть при использовании этого типа сплайнов мы должны быть уверены, что экспериментальные данные не содержат ошибок, которые могут быть внесены, например, регистрирующей аппаратурой. В случае наличия таких ошибок выполнение условий интерполяции приводит к искажению исходной функции, более того, при дифференцировании построенного сплайна его производная будет содержать высокочастотные «шумовые» осцилляции большой амплитуды, обусловленные некорректной операцией дифференцирования. Чтобы избежать такой ситуации используются сглаживающие кубические сплайны.

Одним из главных вопросов аппроксимации таблично заданных данных кубическими сглаживающими сплайнами является оценка параметра сглаживания, то есть выяснение того, насколько построенный сплайн будет приближен к исходным данным. Если принять завышенную оценку, сплайн окажется переглаженным и часть информации может быть потеряна, если оценка будет заниженной, восстанавливаемые данные могут содержать «вредные» высокочастотные составляющие. Существует ряд методов, позволяющих оценивать этот параметр, однако эти методы требуют задания уровня шума и чувствительны к коррелированности помехи. В работе предлагается новый метод, который является модификацией метода Ь-кривых, разработанного Хансеном [63] для решения СЛАУ.

При построении сглаживающих кубических сплайнов для обработки экспериментальных данных используется минимальная информация - о сетке и точных или неточных значениях функции в узлах этой сетки. Однако, наряду с этой информацией, как правило, существуют дополнительные (априорные) данные о свойствах функции, например, об ее неотрицательности или монотонности на некоторых отрезках. Они могут быть получены при изучении физических свойств объекта эксперимента и позволяют точнее восстановить исследуемую функциональную зависимость.

Для интерполяционных сплайнов учет такой информации осуществляется при построении изогеометрических сплайнов [31]. При построении таких сплайнов гарантируется только сохранение информации о возрастании/убывании и выпуклости/вогнутости функции, но не рассматривается вопрос об ограничении значений функции.

Для сглаживающих сплайнов в работах [16, 19] предложена методика учета априорной информации, заданной в виде ограничений на значения функции и ее производных только в узлах сетки. Недостатком данной методики является то, что она гарантирует заданное поведение функции только в узлах сетки. Хотя, в задачах обработки экспериментальных данных необходимо выполнять априорные ограничения на всем заданном интервале. Метод, предложенный в диссертации, позволяет распространить эту информацию на интервалы между узлами сетки.

Помимо помех малой амплитуды, накладываемых регистрирующей аппаратурой, результаты эксперимента могут искажаться случайными выбросами большой амплитуды (аномальные измерения). В этом случае, обычные методы построения сплайнов с квадратичным функционалом невязки приводят к отклонению результатов в сторону этих выбросов. В теории оценивания устойчивость оценок к аномальным измерениям достигается построением специальных - робастных - алгоритмов. В применении к сплайнам эта задача была поставлена, но решения были найдены только для одного класса распределения шума - равномерного.

Таким образом, целью диссертации является разработка вариационных методов построения сглаживающих сплайнов, учитывающих имеющуюся у экспериментатора априорную информацию и устойчивых к аномальным измерениям.

Общая цель включает в себя следующие задачи:

1. Исследование и разработка методов оценки параметра сглаживания, не требующих задания уровня шума измерения и устойчивых к коррелированности шума.

2. Выбор параметра сглаживания, не требующего задания числовых характеристик шумов измерений.

3. Разработка методов и алгоритмов построения изогеометрических сглаживающих кубических сплайнов, учитывающих априорную информацию о поведении функции и производных на различных отрезках.

4. Разработка методов и алгоритмов построения робастных сплайнов с различными функционалами невязок, обладающих высокой устойчивостью к аномальным измерениям. Исследование свойств этих сплайнов при использовании в качестве функционалов невязок различных функций, применяемых в теории робастного оценивания.

5. Создание пакета прикладных программ построения изогеометрических и робастных сглаживающих сплайнов, реализующего эти алгоритмы и пригодного для обработки экспериментальных данных, представляемых различными способами.

6. Использование разработанных методов для обработки данных реальных задач

Диссертация состоит из шести глав.

В первой главе приводятся методы построения интерполяционных и сглаживающих сплайнов, используемые в других главах. Также приведены методы интерполяции эрмитовыми и В-сплайнами, некоторые из которых затем использованы в главе 3 при вычислении изогеометрического сглаживающего сплайна.

Во второй главе рассматриваются два подхода к выбору параметра сглаживания: а) выбор параметра из условия минимума среднеквадратической ошибки сглаживания; б) выбор параметра по заданным точностным характеристикам сплайна.

В рамках первого подхода предлагается алгоритм выбора по Ь-кривой сглаживающего сплайна. В рамках второго подхода вводятся точностные характеристики сплайна и формулируется ряд вариационных задач, решение которых позволяет строить сглаживающий сплайн с требуемыми точностными характеристиками.

Третья глава посвящена построению изогеометрического сглаживающего сплайна.

При высоком уровне погрешностей исходных данных не всегда удается построить сглаживающий сплайн, приемлемый как с точки зрения требуемой точности, так и соответствия некоторым физическим представлениям об исследуемом процессе. Как отмечалось выше, исходя из физических представлений, экспериментатор может иметь достаточную априорную информацию о возможном поведении функции и ее производных на различных интервалах. Эта информация представляет собой набор ограничений на значения функции и ее производных. По форме задания эту информацию можно разделить на два типа:

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 too 1» использовался при обработке данных летного эксперимента в институте теоретической и прикладной механики и это позволило получить из эксперимента более достоверную информацию об исследуемых аэродинамических процессах.

5. Пакет программ «Spline Tool» передан в эксплуатацию в ФГУП СНИИМ для использования при обработке данных аппаратуры слежения за спутниками.

Достоверность результатов диссертации основана на строгом проведении математических доказательств и совпадении свойств сплайнов, построенных по этим методикам, с априорными условиями, заданными при построении этих сплайнов, а также повторяемостью результатов при расчете одной задачи разными методами.

На защиту выносятся следующие положения.

1. Оценка параметра сглаживания методом L-кривой.

2. Вариационный подход к построению изогеометрического сглаживающего сплайна. Теорема о существовании и единственности решения сформулированной вариационной задачи. Условия непротиворечивости априорных ограничений.

3. Вариационный поход к построению сглаживающего сплайна, робастного на классах распределений шумов измерений и алгоритмы его построения. Теорема существования и единственности такого сплайна.

4. Пакет прикладных программ «Spline Tool», реализующий построение интерполяционного, сглаживающего, изогеометрического сглаживающего, робастного сглаживающего сплайнов.

5. Результаты одной из случаев применения изогеометрического сглаживающего сплайна для обработки данных аэродинамического эксперимента.

6. Результаты применения изогеометрических сплайнов для обработки данных системы слежения за спутниками.

7. Результаты применения робастных сплайнов для обработки данных системы слежения за спутниками

При нумерации разделов, формул и рисунков первая цифра указывает номер главы, вторая - их порядковый номер.

Основные результаты, полученные в диссертации, опубликованы в 8 работах [4-10,50].

Апробация результатов работы.

Результаты диссертационной работы неоднократно (в течение 1998-2002 годов) обсуждались на семинарах научного направления «Создание новых информационных технологий и систем автоматизированного проектирования» Новосибирского государственного архитектурно-строительного университета (НГАСУ) и докладывались на следующих конференциях

• Международная Байкальская школа-семинар «Методы оптимизации и их приложение» Иркутск, 1998 г.

• Международная конференция КО!Ш8-99, НГТУ, Новосибирск, 1999 г.

• Всероссийская конференция «Алгоритмический анализ некорректных задач», Екатеринбург, 1998г.

• Российская конференция «Обратные и некорректно поставленные задачи» Москва 1998; 1999 г.

• Научно-технические конференции Новосибирского государственного архитектурно-строительного университета (Новосибирск) 1999, 2000 годов.

• Четвертый Сибирский Конгресс по прикладной и индустриальной математике, посвященный памяти М.А. Лаврентьева (ИНПРИМ-2000)

• Сибирская конференция «Методы сплайн-функций», посвященная памяти Завьялова Ю.С., Новосибирск 2001 г.

Автор выражает глубокую благодарность доктору физико-математических наук Воскобойникову Юрию Евгеньевичу за научное руководство, а также кандидату физико-математических наук Мирошниченко Валерию Леонидовичу за критические замечания и советы при подготовке диссертации.

Заключение диссертация на тему "Сглаживающие изогеометрические и робастные сплайны: методы и алгоритмы"

Основные результаты, полученные в этой работе состоят в следующем:

1. Исследованы методы оценивания параметра сглаживания при известных и неизвестных характеристиках шума. Предложен новый метод оценивания параметра сглаживания - метод L-кривой, который является более устойчивым к коррелированности шума по сравнению с методом перекрестной значимости.

2. Исследован сглаживающий сплайн, позволяющий при построении учитывать априорную информацию в виде ограничений на значения приближаемой функции и ее производных - сглаживающий изогеометрический сплайн. Предложена методика построения таких сплайнов, исследованы на предмет эффективности некоторые методы их построения.

3. Сформулирована и доказана теорема существования и единственности изогеометрического сглаживающего сплайна для заданных ограничений.

4. Сформулирована и доказана теорема о неизбыточности и непротиворечивости ограничений, накладываемых на построенный сплайн.

5. Исследован сглаживающий сплайн, позволяющий учитывать информацию о классе распределений шума - робастный сплайн. Предложены несколько алгоритмов построения такого сплайна.

6. Сформулирована и доказана теорема существования и единственности сглаживающего робастного сплайна при заданном классе шумов распределений.

7. Разработан комплекс программ «Spline Tool», предназначенный для обработки экспериментальных данных с использованием сплайн-функций. Этот комплекс включает в себя методы построения интерполяционного, сглаживающего, изогеометрического сглаживающего и робастного сглаживающего сплайнов. В нем реализована возможность получения данных как из файлов, так и из баз данных. Этот комплекс использован для решения практических задач.

8. Разработан комплекс программ «Spline Tool», предназначенный для обработки экспериментальных данных с использованием сплайн-функций. Этот комплекс реализует методы построения интерполяционного, сглаживающего, изогеометрического сглаживающего и робастного сглаживающего сплайнов.

9. Комплекс «Spline tool» использован для обработки результатов ряда аэродинамических экспериментов в ИТПМ СО РАН. Это позволило уточнить данные об обтекании воздухом поверхностей сложной формы при различных углах атаки.

Ю.Комплекс использован при обработке данных системы слежения за спутниками в ФГУП СНИИМ (Новосибирск). Применение этого комплекса позволило учесть априорную информацию, известную исследователям и получить более точные результаты.

Заключение

Библиография Березовский, Михаил Витальевич, диссертация по теме Математическое моделирование, численные методы и комплексы программ

1. Алберг Дж., Нильсон Э., Уолш Дж. Теория сплайнов и ее приложения. -М.: Мир, 1972.-316 с.

2. Базара М. Шетти К. Нелинейное программирование: Теория и алгоритмы. М.: Мир, 1982.- 460с.

3. Бахвалов Н. С., Жидков Н. П., Кобельков Г. М. Численные методы. М.: Наука, 1987.-630 с.

4. Березовский М.В. Изогеометрические сглаживающие сплайны в обратных задачах / Обратные и некорректно поставленные задачи (тезисы докладов конференции) Москва, 1999, - с. 74.

5. М.В.Березовский, Ю.Е.Воскобойников Робастные сглаживающие сплайны / Обратные и некорректно поставленные задачи (тезисы докладов конференции) Москва, МГУ, 1999, - с. 74-75.

6. М.В.Березовский Изогеометрические сглаживающие сплайны в обратных задачах / Обратные и некорректно поставленные задачи (тезисы докладов конференции) Москва, МГУ, 1999 - с. 16.

7. Березовский М.В., Воскобойников Ю.Е. Изогеометрические сглаживающие сплайны. / Научный вестник НГТУ. 1999. - №2(7) - с. 3-13.

8. М.В.Березовский, Ю.Е. Воскобойников Изогеометрические и робастные сплайны: алгоритмы и применение Новосибирск, 2000. - 32 с. - (Препринт / НГАСУ №4).

9. М.В.Березовский, Ю.Е.Воскобойников Построение дескриптивных приближений с использованием локальных сплайнов. / 11-я Байкальская международная школа-семинар Методы оптимизации и их приложения -Иркутск, 1998 Труды конференции - с. 119-122.

10. Боровков A.A. Математическая статистика. М.: Наука, 1984. - 472 с.

11. З.Бурова И. Г., Демьянович Ю. К. О построении сглаженных сплайнов с минимальным носителем. // Вестник ЛГУ, сер. матем., мех., астр. -N13, 1983. -С. 10-15.

12. Васильев В.Ф. Численные методы решения экспериментальных задач. -М.:Наука. 1980 -548 с.

13. Василенко В.А. Сплайн-функции: теория, алгоритмы, программы. -Новосибирск: Наука, 1983.-215 с.

14. Васин В.В. О сходимости методов градиентного типа для нелинейных уравнений ДАН, 1998 - т.359, N 1 - с.7-9.

15. Вапник В.И. Восстановление зависимостей по эмпирическим данным. М: Наука. 1979.-448 с.

16. Волков В.Г., Никулин М.С. Несмещенные оценки и их применение. М.: Наука. 1989.-448 с.

17. Воронин В.Т. Построение сплайнов, сохраняющих геометрию. -Новосибирск, 1982. 19 с. - (Препринт / АН СССР. Сиб. Отд-ние. Вычислительный центр; №404).

18. Воскобойников Ю.Е. Дескриптивные сглаживающие сплайны и алгоритмы их построения //Моделирование в механике. Сб. научных трудов. Новосибирск, Институт теоретической и прикладной механики СО РАН. 1991.-т.5.-№5.с.30-37.

19. Воскобойников Ю.Е., Частотный подход к оценке точности сглаживания и дифференцирования экспериментальных данных на основе сглаживающих сплайнов // Автометрия.- 1986.-№1.-с.38-47.

20. Воскобойников Ю.Е. Эффективный алгоритм решения плохо обусловленных систем уравнений при интерпретации экспериментальных данных // Автометрия. 1988. №5. с. 46-51.

21. Воскобойников Ю.Е., Мицель А. А. Решение обратных задач зондирования газовой составляющей атмосферы на основе дескриптивных сплайнов //Оптика атмосферы.-1991.т.4.№2-с.41-48.

22. Воскобойников Ю.Е., Преображенский Н.Г., Седельников А.И. Математическая обработка эксперимента в молекулярной газодинамике. Новосибирск, Наука, 1984.

23. Гантмахер Ф.Р. Теория матриц. М.: Наука, 1967. - 575 с.

24. Демьянович Ю. К. Сплайны на многообразии и их применение. // Вычислительная механика деформируемого тела, Вып. 1, 1990. С. 108-128

25. Демьянович Ю. К. О сплайнах с минимальным носителем. Сб. Методы вычислений, вып. 17. 1995. С. 87-104.

26. ЗО.Игнатов М. И., Малоземов В. Н., Певный А. Б. О сглаживании // Вестник ЛГУ. Сер. 1. 1989. Вып. 2 (№8). С. 7-11.31 .Квасов Б.И. Методы построения обобщенных В-сплайнов и их свойства // Доклады Российской Академии наук. М., 1995. Т.341, №6. 744-748.

27. Квасов Б.И. Изогеометрическая аппроксимация сплайнами: Учебное пособие / Новосибирский университет. Новосибирск, 1998. 152 с.

28. Квасов Б.И., Кобков В.В. Некоторые свойства кубических эрмитовых сплайнов с дополнительными узлами // Доклады АН СССР. 1974. - т.217.-№5.- 1007-1010.

29. Квасов Б.И., Яценко С.А. Изогеометрическая интерполяция рациональными сплайнами И Аппроксимация сплайнами. Новосибирск, 1987.-Вып.121: Вычислительные системы. - с. 11-36.

30. Квасов Б.И., Яценко С.А. Алгоритм изогеометрической аппроксимации рациональными сплайнами //Новосибирск, 1990. 34 с. - (Препринт АН СССР. Сиб. отделение. Институт теоретической и прикладной механики, №9-90).

31. Кирушев В.А., Малоземов В.Н. Интерполяция положительных данных при помощи неотрицательных натуральных кубичских сплайнов // Вестн. СПб ун-та-Сер. 1. 1995. Вып. 2(№8). С. 25-30.

32. Кирушев В.А., Малоземов В.Н. Об одном алгоритме построения неотрицательного кубического сплайна // ЖВМ и МФ. 1997. - т. 37. - №4. - с. 387-394.

33. Малоземов В.Н., Певный А.Б. Полиномиальные сплайны. JL: Изд-во АТУ, 1986.

34. Мирошниченко B.JI. Достаточные условия монотонности и выпуклости для интерполяционных кубических сплайнов класса С //Приближение сплайнами.-Новосибирск. 1990. -Вып 137:Вычислительные системы, с.31-40.

35. Роженко А.И. Абстрактная теория сплайнов. Учебное пособие. -Новосибирск: Издательский центр НГУ, 1999 176 с.

36. Стечкин С.Б., Субботин Ю.Н. Сплайны в вычислительной математике. -М.: Наука, 1976.-248 с.

37. Сапожников П.Н. Алгебраические методы оптимального статистического оценивания. Пермь: Изд-во Перм. ун-та, 168 с.

38. Фабриков A.B., Алдошина О.И., Мамаева A.B. Оценивание времен запаздывания сигналов методом адаптивной фильтрации с применением сглаживающих сплайнов // Оптика атмосферы и океана -1995г том 8, № 08, стр.1213.

39. Фихтенгольц Г.М. Курс интегрального и дифференциального исчисления в 3 томах М.; Физматлит, 2001 - 680 с.

40. Шметтерер JI. Введение в математическую статистику. М.: Наука, 1976. - 520 с.

41. Шориков А.Ф. Минимаксное оценивание и управление в дискретных динамических системах. Екатеринбург: Изд-во Уральск, ун-та, 1997. - 248 с.

42. Шуп Т. Прикладные численные методы в физике и технике М.; Высш. шк., 1990.-255 е.: ил.

43. Akima Н. A method of bivariate interpolation and smooth surface fitting for irregulary distributed data points // ACM Trans. Math. Software. -1978. -Vol.4, N 2. -P.148-159.

44. Barth J, Kraft A., Kraft J Estimation of liquidity trap using spline functions. // The Review of Econ. And Stat. 1976 - Vol. 58 - P. 218-222.

45. Berezowsky M.V. Local approximation algorithms in b-spline basis / 3-rd international conference KORUS'99 (Abstract) P. 532.51 .Buse A, Lim L Cubic splines as a special case of restricted least squares // J. ASA. 1977. - Vol. 72 - P. 64-68.

46. Clements J.C. Convexity-preserving piecewise rational cubic interpolation // SIAM J. Numer. Anal. 1990. - Vol. 27. - P. 1016-1023.

47. Dauner H., Reinsch C.H. An analysis of two algorithms for shape preserving cubic spline interpolation // IMA J. Numer. Analys. 1989. Vol. 9. P. 299-314.

48. Demjanovich Yu. K. Some properties of the minimal splines. International Conference "Optimization Finite Element Approximations" (Abstracts). 1995. St. Petersburg. P. 51.

49. Dikshit H.P., Ojha A., Zalik R.A. Wachspress type rational complex planar splines of degree (3,1) // AICM, 1994. - Vol. 2 (№2). - p. 235-250.

50. Dorato, P., Fortuna, L., Muscato, G. Robust control for unstructured perturbations an introduction -: Berlin et al. : Springer 1992, V 118 p.

51. Edwards J. A. Exact Equations of the Nonlinear Spline // TOMS 1992, -Vol. 18 (№2).-p. 174-192.

52. Fletcher, R. and M.J.D. Powell, "A Rapidly Convergent Descent Method for Minimization," //Computer Journal, Vol. 6, pp. 163-168, 1963.

53. Floater M.S. A weak condition for the convexity of tensor-product Bezier and B-spline surfaces // AICM, 1994. - Vol. 2 (№1). - p. 67-80.

54. Fredenhagen S., Oberle H.J., Opfer G. On the construction of optimal monotone cubic spline interpolations // J. Approx. Theory 96 (1999) Vol. 1.

55. Goodman T.N.T., Ong B.H., Unsworth K. Constrained interpolation using rational cubic splines // Nurbs for Curves and Surface Design. G. Farin (ed.). -SIAM, 1991.-P. 59-74.

56. Goodman T.N.T., Unsworth K. Shape preserving interpolation by parametrically defined curves // SIAM J. Numer. Anal. 1988. - Vol. 25. - No. 8. P. 1453-1465.

57. Goodman T.N.T., Unsworth K. Shape preserving interpolation by curvature continuous parametric curves // Computer Aided Geometric Design. 1988. - Vol.5. -P. 323-340.

58. Hansen P.C. Analysis of discrete ill-poised problems by means of the L-curve // SIAM Review 34 pp 561, cql 1992.

59. Hutchinson M. F. A Fast Procedure for Calculating Minimum Cross-Validation Cubic Smoothing Splines // TOMS 1986, - Vol. 12 (№2). - p. 150-153.

60. Lawton W., Lee S.L., Shen Z. Characterization of compactly supported refmable splines // AICM, 1995. - Vol. 3 (№1-2). - p. 137-145.

61. Lee E.T.Y. Choosing nodes in parametric curve interpolation // Computer Aided Design. 1989.-Vol. 21.-P. 363-370.

62. Loach P. D., Wathen A. J. On the best least squares approximation of continuous functions using linear splines with free knots // IMAJNA 1991. - Vol. 11 (№2).

63. Luo Z., Wahba G. Hybrid adaptive splines // J. Amer. Statist. Assoc 1997. - Vol. 92. - P. 107-114.

64. McGee V.E., Carlton W.T. Piece-wise regression // J. ASA 1970. - Vol. 65. -P. 1109-1124.71.0pfer G., Oberle H. J. The derivation of cubic splines with obstacles by methods of optimization and optimal control // Numer. Math. 1988. Vol. 52. P. 1731.

65. Petrus P. Robust Huber Adaptive Filter // IEEE Transactions On Signal Processing 1999. - Vol. 47. - P. 1129-1132.

66. Poirere D.J Piece-wise regression using cubic splines // J. ASA 1973. - Vol. 68-P. 515-524.

67. Press W.H., Teukolsky S.A., Vetterling W.T., Flannery B.P. Numerical recipes in C. Second Edition // Cambridge University Press 1995. - P. 994.

68. Rieder H. Robust statistics, data analysis, and computer intensive methods -New York et al.: Springer 1996 .

69. Rozhenko A.I. On optimal choice of spline-smoothing parameter // Bulletin of Novosibirsk Computing Center, Series: Numerical Analysis, Novosibirsk: NCC Publisher, 1996 - Issue 7 - p.79-86.

70. Schmidt J.W. Results and problems in shape preserving interpolation and approximation with polynomial splines // Math. Research. Berlin: Akademie Verlag, 1989. Vol. 52-P. 159-170.

71. Suits D.B. Spline functions fitted by standard regression methods // The Review of Econ. And Stat. 1978 - Vol. 60 - P. 132-139.

72. Utreras F.I. On computing robust splines and applications // SIAM J. Sci. Stat. Comput.-1981.-Vol. 2.-P. 153-163.

73. Unser M„ Blu T. Fractional Splines and Wavelets // SIAM J. Rev. 2000 -Vol.42(№l)~P. 43-67.

74. Wahba G. Generalization and regularization in nonlinear learning systems // Handbook of Brain Theory and Neural Networks 1995. - P. 426-430.

75. Wahba G., Wendelberger J. Some new mathematical methods for variational objective analysis using splines and cross-validation // Monthly Weather Review -1980.-Vol. 108.-P. 36-57.

76. Xiang D., Wahba G. A generalized approximate cross validation for smoothing splines with non-Gaussian data // Statistica Sinica 1996. - Vol. 6- P. 675-692.

77. Wahba G., Nychka D., Goldfarb S., Pugh T. Cross validated spline methods for the estimation of three dimensional tumor size distributions from observations on two dimensional cross sections. // J. Amer. Statist. Assoc. 1989 - Vol. 79 - P. 832846.

78. Wahba G. A comparison of GCV and GML for choosing the smoothing parameter in the generalized spline smoothing problem. //Ann. Statist. 1985 - Vol. 13-P. 1378-1402.

79. Wahba G., Villalobos M. Inequality-constrained multivariate smoothing splines with application to the estimation of posterior probabilities // J. Amer. Statist. Assoc. 1987 - Vol. 82 - P. 239-248.

80. Xiang D., Wahba G. Approximate smoothing spline methods for large data sets in the binary case // Proceedings of the 1997 ASA Joint Statistical Meetings 1998. -P. 94-98.

81. P. Huber Robust smoothing, In Robustness in Statistics, Proceedings of the ARO Workshop, R. Launder and G. Wilkinson, eds., Academic Press, New York, 1979.

82. Byrd R.H., Pyne D.A. Convergence of the iteratively reweighted least squares algorithm for robust regression John Hopkins University Technical Report - 1979 -№313.

83. B. Krumm, Th. Gasser. Robust spline smoothing. Communication at the workshop held at Heidelberg on Smoothing Techniques for curve extimations 1979.

84. Lenth R.V. Robust splines // Comm. Stastist. 1977 - № A6 - P. 847-854.

85. Rockafellar R.T. Convex Analysis, Princeton: Princeton University Press, 1970.

86. Yamaguchi F. Curves and Surfaces in Computer Aided Geometric Design. -New York: Springer, 1988.

87. Yan Z. Piecewise cubic curve fitting algorithm // Math. Comp. 1987. - Vol. 49. P 203-213.