Сплайны в задачах интерполяции и регрессионного анализа гауссовских процессов и гладких функций тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Крымова, Екатерина Александровна
- Специальность ВАК РФ05.13.17
- Количество страниц 97
Оглавление диссертации кандидат наук Крымова, Екатерина Александровна
Содержание
Введение
Глава 1. Сплайны и интерполяция стационарных гауссовских процессов
1.1. Обзор методов интерполяции
1.1.1. Сплайны
1.1.2. Сплайны с натяжением
1.1.3. Кригинг
1.1.4. Барицентрический метод интерполяции
1.2. Эквивалентность метода интерполяционных сплайнов и предельных интерполяций стационарного гауссовского процесса
1.3. Минимаксная интерполяция стационарных гауссовских процессов
1.4. Интерполяция гладких функций
1.5. Контроль точности для интерполяции сплайнами
1.6. Выводы
Глава 2. Экспоненциальное взвешивание упорядоченных оценок
2.1. Оценивание в белом шуме с помощью упорядоченных оценок
2.1.1. Постановка задачи
2.1.2. Сглаживающие сплайны как упорядоченные оценки
2.2. Оракульное неравенство для метода экспоненциального взвешивания в задаче оценивания вектора в белом шуме
2.2.1. Метод экспоненциального взвешивания
2.2.2. Экспоненциальное взвешивание упорядоченных оценок
2.2.3. Дополнительные результаты
2.2.4. Доказательство Теоремы И
2.3. Оценивание в стационарном шуме при помощи упорядоченных оценок
2.4. Выводы
Глава 3. Результаты экспериментов
3.1. Сравнение методов одномерной интерполяции
3.1.1. Быстрый алгоритм для сплайнов порядка га
3.1.2. Результаты сравнения методов одномерной интерполяции
3.2. Сравнение методов контроля точности интерполяции для сплайнов и кригинга
3.3. Сравнение метода экспоненциального взвешивания и метода минимизации несмещенной оценки риска
3.4. Выводы
Заключение
Литература
Список публикаций
Рекомендованный список диссертаций по специальности «Теоретические основы информатики», 05.13.17 шифр ВАК
Изогеометрическая интерполяция нелокальными кубическими сплайнами и их обобщениями2014 год, кандидат наук Богданов, Владимир Васильевич
О статистическом оценивании плотности распределения сплайн функциями1985 год, кандидат физико-математических наук Муминов, Махаммаджон Саминович
Хорошо обусловленные методы построения сплайнов высоких степеней и сходимость процессов интерполяции2006 год, доктор физико-математических наук Волков, Юрий Степанович
Некоторые модификации процедур стохастической аппроксимации1984 год, кандидат физико-математических наук Никитенко, Валентин Гаврилович
Приближение функций многочленами на треугольной сетке2008 год, кандидат физико-математических наук Матвеева, Юлия Васильевна
Введение диссертации (часть автореферата) на тему «Сплайны в задачах интерполяции и регрессионного анализа гауссовских процессов и гладких функций»
Введение
Актуальность работы. Диссертация посвящена задачам математической теории интерполяции стационарных гауссовских процессов и оценивания гладких функций регрессии. При этом существенное внимание уделяется интерполяционным методам и методам оценивания, основанным на сплайнах [1].
Задачи интерполяции функций естественным образом возникают в различных областях прикладной математики, а методы интерполяции широко используются в многочисленных инженерных приложениях. Как правило, задача интерполяции заключается в восстановлении неизвестной функции по ее значениям, заданным на дискретном множестве точек. Очевидно, что в общем случае точно восстановить функцию во всех точках невозможно и поэтому основной целью является поиск методов интерполяции, обеспечивающих минимально возможную ошибку интерполяции. Понятно также, что как ошибка интерполяции, так и метод интерполяции критически зависят от имеющейся априорной информации об интерполируемой функции. Во многих случаях довольно естественно предполагать, что интерполируемая функция является гладкой. При этом естественно возникает неформальная задача о том, как оптимальным образом трансформировать интуитивное понятие гладкости в метод интерполяции.
Классические подходы к интепроляции гладких функций связаны с интерполяциями с помощью полиномов. Они разрабатывались Лагранжем, Ньютоном, Стирлингом и др. [2-4]. Хорошо известно, что интерполяция полиномами становится крайне неустойчива при возрастании числа наблюдений (феномен Рунге) [5], к тому же нет возможности контролировать степень гладкости получающейся интерполяции. Именно поэтому возникла идея использования интерполяционных локальных полиномов невысокой степени. Для снижения погрешности интерполяции отрезок наблюдения функции разбивается на несколько отрезков и на каждом из них строится интерполяционный локальный полином, затем полиномы гладко сшиваются. Степень локального полинома чаще вы-
бирается из априорного представления о гладкости функции. Эта идея по-разному реализована в методах кусочно-гладкой интерполяции Лагранжа, Эрмита (при заданных производных в точках наблюдения) [6-8], сплайнах. Отметим также, что локальные полиномы используются в барицентрическом методе дробно-рациональной интерполяции Флоатера [9]. Однако точность этого метода при нерегулярном расположении точек чаще всего неудовлетворительна.
Принципиально иной подход к задаче интерполяции основан на использовании вероятностных моделей для интерполируемой функции. Наиболее часто используемый на практике, в особенности, в геостатистике, метод кригинга [10] использует предположение о том, что наблюдаемая функция является реализацией гауссовского процесса с ковариационной функцией из некоторого заданного параметрического семейства. К сожалению, практически никогда нет уверенности в том, что интерполируемый процесс принадлежит выбранному классу. Также при построении интерполяции приходится оценивать параметры неизвестной ковариационной функции, что приводит к невыпуклой задаче оптимизации.
Среди многочисленных методов интерполяции функций, используемых на практике, сплайны занимают особое место. Это прежде всего обусловлено тем, что они
• позволяют хорошо интерполировать гладкие функции;
• имеют простую и ясную физическую интерпретацию. В частности, кубический сплайн описывается формой тонкой гибкой линейки, проходящей через заданные точки;
• допускают исключительно быстрые алгоритмы для их вычисления.
Эти свойства сплайнов были замечены и использованы инженерами очень давно, по-видимому, первое упоминание о сплайнах содержится в книге XVIII века А,-Л. Дюамеля дю Монсо [11].
Широкое использование сплайнов на практике требует их всестороннего теоретического обоснования. Поэтому, в частности, возникает задача сравнения интерполяции сплайнами с минимаксными интерполяциями гладких стационарных гауссовских процессов и функций из соболевских классов. Кроме того, в инженерных приложениях часто требуется не только построить хороший метод интерполяции, но и оценить точность интерполяции, которую он может обеспечить. К сожалению, в рамках классической теории функциональной интерполяции последняя задача не имеет решения. Ее решение становится возможным при некоторой дополнительной априорной информации об интерполируемой функции. В качестве такой информации может служить гипотеза о том, что функция представляет собой реализацию гауссовского процесса.
Метод решения задачи о вычислении минимаксной интерполяции и ее точности для соболевского класса гладких функций идейно близок к методу, предложенному М. С. Пинскером [12] для асимптотически точного вычисления минимаксного риска фильтрации квадратично-интегрируемых сигналов. Точное аналитическое решение задачи минимаксной интерполяции возможно, если значения функции задаются на бесконечной равномерной решетке. В этом случае можно осуществить переход в спектральную область с помощью преобразования Фурье (см., например, статьи Г. К. Голубева [13], Г. К. Голубева и М. Нусба-ума [14]). При этом нижние границы для ошибки интерполяции получаются на основе решения хорошо известной задачи об интерполяции стационарных стохастических последовательностей, которая была детально изучена в работах А. Н. Колмогорова [15, 16] и Н. Винера [17].
Задача интерполяции является предельным случаем задачи оценивания функции регрессии при уровне шума, стремящемся к нулю. Поэтому в диссертации наряду с задачами интерполяции рассматриваются задачи восстановления функции регрессии с помощью сглаживающих сплайнов. При использовании сглаживающих сплайнов в случае ненулевого уровня шума возникает проблема выбора параметра сглаживания. Часто он находится с помощью метода ОСУ
[17], который является одним из вариантов метода несмещенного оценивания риска [18]. Для риска оценок, полученных с помощью метода несмещенного оценивания риска, А. Кнайп [19] получил очень хорошие верхние границы, равномерные по всем оцениваемым функциям регрессии, которые часто называются в современной математической статистике оракульными неравенствами.
Очевидно, что выбор наилучшей оценки из заданного семейства оценок является частным случаем поиска наилучшей выпуклой комбинации оценок из этого семейства. Такой метод построения оценок называется агрегацией. Первые подходы к агрегации оценок были основаны на разбиении наблюдений на две независимые части. При этом оценки строились по одной части наблюдений, а наилучшая выпуклая комбинация вычислялась по другой. Этот подход был разработан независимо А. Немировским [20] и О. Катони [21]. Разбиение выборки на две части неизбежно влечет потери статистической информации, содержащейся в наблюдениях, и на практике его естественно стараются избежать. С математической точки зрения деление выборки приводит к тому, что получающиеся верхние границы для риска агрегированной оценки оказываются хуже границ Кнайпа. Существенный прогресс в методах агрегации, не использующих разбиение выборки, был достигнут в работе Г. Леюнга и А. Баррона [22] для метода экспоненциального взвешивания. Дальнейшее развитие методов этой работы сделано Г.К. Голубевым [23] для агрегации проекционных оценок. Отметим также, что несколько иные результаты для метода агрегации функций из словаря с помощью метода экспоненциального взвешивания в задаче восстановления функции регрессии получены недавно Ф. Риголле и А. Цыбаковым [24], А. Далаляном и Ж. Салмоном [25].
Поэтому цели данной работы состоят в том, чтобы:
• математически обосновать близость интерполяционных сплайнов к наилучшим методам интерполяции функций из соболевских классов;
© разработать метод контроля точности для интерполяционных сплайнов;
• получить оракульиые неравенства для экспоненциальной агрегации сглаживающих сплайнов, которые улучшают неравенство Кнайпа.
В соответствии с перечисленными целями были определены задачи исследования:
1. Вычислить ошибку минимаксной интерполяции гауссовских процессов из соболевских классов и сравнить его с ошибкой интерполяции сплайнами.
2. Рассмотреть задачу минимаксной интерполяции гладких функций на равномерной решетке со случайным сдвигом.
3. Предложить и обосновать метод контроля точности сплайновой интерполяции на основе эквивалентности сплайнов и оптимальной интерполяции для гауссовских стационарных процессов со специальными спектральными плотностями.
4. Доказать новые оракульные неравенства для задачи оценивания функции регрессии с помощью метода экспоненциального взвешивания, улучшающие известные результаты.
5. Экспериментально сравнить метод экспоненциального взвешивания с методом несмещенного оценивания риска.
Научная новизна результатов, полученных в диссертации, заключается в том, что предложен новый метод оценивания качества интерполяции методом сплайнов. Основываясь на вероятностных свойствах несмещенной оценки риска, доказаны новые оракульные неравенства для метода экспоненциального взвешивания упорядоченных оценок. Причем остаточный член в полученных оракульных неравенствах улучшен по сравнению с результатом Кнайпа.
Практическая значимость. Практическая значимость диссертационной работы определяется широким использованием предложенного метода контроля качества сплайнов, реализованного в программном продукте Macros ком-
пании Datadvance, в частности, для решения ряда прикладных задач концерна EADS.
На защиту выносятся следующие результаты:
1. Показано, что риск интерполяции сплайнов близок к риску минимаксной интерполяции гладких стационарных гауссовских процессов.
2. Вычислен риск минимаксной интерполяции гладких функций на равномерной решетке со случайным сдвигом. Полученный риск равен минимаксному риску интерполяции гладких гауссовских стационарных процессов.
3. Предложен метод контроля точности интерполяции сплайнами. Показано, что для определенного класса процессов предложенный метод является хорошей оценкой для реальной ошибки интерполяции.
4. Задачи восстановления функции регрессии с помощью сглаживающих сплайнов сведены к задаче оценки зашумленного вектора при заданном множестве упорядоченных оценок. Для метода экспоненциального взвешивания упорядоченных оценок выведены новые оракульные неравенства.
5. Проведены численные эксперименты, которые показали, что в случае, когда отношение риска оракула к дисперсии шума мало, экспоненциальное взвешивание позволяет получить оценку с меньшим риском.
Апробация работы. Результаты работы докладывались и обсуждались на следующих конференциях:
• 18-я European Young Statisticians Meetings (2013, Осиек, Хорватия);
• 43-rd Probability Summer school (2013, Сент-Флур, Франция);
• 9-я Международная конференция «Интеллектуализация обработки информации» (2012, Будва, Черногория);
• + исправить слайды по рудакову
• Международная конференция молодых ученых «Информационные Технологии и Системы» (2012, Петрозаводск, Россия; 2013, Калининград, Россия);
• 55-я Всероссийская научная конференция Московского физико-технического института (2012, Долгопрудный, Россия).
Также результаты работы обсуждались на семинарах Лаборатории структурных методов анализа данных в предсказательном моделировании МФТИ (2012, 2013).
Публикации. Основные результаты по теме диссертации изложены в восьми печатных изданиях, из которых три изданы в журналах, рекомендованных ВАК.
Личный вклад автора. Содержание диссертации и основные положения, выносимые на защиту, отражают персональный вклад автора в опубликованные работы. Подготовка к публикации полученных результатов проводилась совместно с соавторами, причем вклад диссертанта был определяющим.
Структура и объем диссертации. Диссертация состоит из введения, 3 глав, заключения и библиографии. Общий объем диссертации 97 страниц, включая 15 рисунков. Библиография включает 65 наименований.
Благодарности. Автор благодарен своему научному руководителю Георгию Ксенофонтовичу Голубеву за постановки задач, плодотворные обсуждения, за постоянную поддержку и участие.
Работа выполнена при поддержке Лаборатории структурных методов анализа данных в предсказательном моделировании, МФТИ, грант правительства РФ дог. 11.G34.31.0073.
Глава 1
Сплайны и интерполяция стационарных гауссовских процессов
В этой главе рассматривается задача восстановления неизвестной функции /(ж), х Е М, по наблюдениям
Ук = /(Хк), к = 1,..., п;
здесь и далее для простоты предполагается, что все точки различны, упорядочены Х\ < Хъ < ... < Хп и принадлежат отрезку [0,1]. С помощью данных (Хк,Ук), к = 1,... ,п мы хотим найти неизвестное значение функции /(ж) в некоторой заданной точке х Е (0,1).
1.1. Обзор методов интерполяции
Спектр методов, применяемых для решения этой задачи, очень широк, поэтому остановимся на методах, которые чаще всего используются на практике.
1.1.1. Сплайны
Среди многочисленных методов интерполяции, используемых на практике, методы интерполяции сплайнами занимают особое место. Это прежде всего обусловлено их способностью хорошо интерполировать гладкие функции и тем, что они допускают простую и ясную физическую интерпретацию. Эти свойства сплайнов широко используются в различных практических задачах [1, 26, 27]. По-видимому, впервые интерполяция сплайнами была упомянута в [11] как метод для проектирования корпусов судов (см. Рис. 1.1).
У кубического сплайна имеется очень простая физическая интерпретация: он описывается формой тонкой гибкой линейки, проходящей через точки на
Рис. 1.1. Кубический сплайн из [11] (1752 год).
плоскости с координатами (хг,/(хг)). Поскольку энергия гибкой линейки, имеющей форму /(ж), х Е [а, 6], пропорциональна /^[/"(ж)]2 с1х, то с математической точки зрения кубический сплайн 5з(ж) является решением следующей оптимизационной задачи:
ь
5з(ж) = а^ пип
[д"(х)]2с1х.
Это определение непосредственно обобщается на сплайны порядка д [28, 29]:
52(7-1(ж) = а^ тш
\д{я)(х)]2<Ь;
(1.1)
здесь д^\х) обозначает производную порядка д функции д{х). Нетрудно проверить, что решение задачи (1.1) удовлетворяет дифференциальному уравнению
^-Л1) = 0, хе[хк,хк+1],
то есть является полиномом порядка 2д — 1. Также просто проверить, что 52д-1(ж) — полином степени д — 1 на [а,жх) и (хп,Ь\ и что эта функция имеет непрерывные производные до 2д — 2-го порядка включительно. На практике, как правило, неизвестно, какой гладкостью обладает интерполируемая функция. Если она имеет сингулярности, такие как разрывы, то чем выше порядок
сплайна, тем хуже будут интерполироваться данные в окрестности сингулярности.
В большинстве работ, посвященных методам сплайнов в задаче одномерной интерполяции, используется алгебраический подход [30]. А именно используется тот факт, что сплайн является кусочно-полиномиальной функцией, причем коэффициенты полиномов удовлетворяют некоторой системе линейных уравнений. При этом используются свойства матриц возникающих систем (например, диагональное преобладание, цикличность и др.). Аппроксимативные свойства сплайнов (в общем случае для задачи интерполяции функций многих переменных) исследовались в работах [31-34], в которых получены точные по порядку оценки погрешности приближения сплайнами, а также изучены свойства сходимости сплайнов к интерполируемой функции в пространствах \¥р(£1) Соболева [35] с дополнительным требованием равномерной ограниченной непрерывности на производных порядка < к функций из [30].
Различные применения сплайнов в статистике и вероятности рассмотрены в многочисленных работах, например в статьях Карлина [36], Вахбы [26, 37, 38], Веба [39], Селезнева [40].
1.1.2. Сплайны с натяжением
Один из возможных подходов к улучшению качества интерполяции вблизи сингулярностей функции основан на так называемых сплайнах с натяжением. Эвристическая идея состоит в том, чтобы использовать сплайны высокого порядка вдали от сингулярностей, а вблизи их сплайны низкого порядка. Формально кубический сплайн с натяжением [41, 42] определяется как решение
следующей минимизационнои задачи:
Хк+1
У УК-Ьг} 3 \-LiJ ^
[д'\х)У&х
ак
+ к
(1-2)
2
(Хк+1 ~ Хк)2
Заметим, что если все сг^ равны нулю, то Тз(ж) является кубическим сплайном, а если все велики, то приближается к линейному сплайну, для кото-
рого нет гиббсовского эффекта. Решение оптимизационной задачи (1.2) легко находится: на отрезке [хк,хк+\] кубический сплайн с натяжением является решением дифференциального уравнения
Поэтому в отличие от обычных кубических сплайнов, сплайны с натяжением уже не являются локальными полиномами третьей степени, а содержат гиперболические синусы. Для выбора коэффициентов натяжения ак применяется метод, обеспечивающий их минимальные значения при сохранении гладкости решения Тз(ж). Он заключается (см. [43, 44]) в нахождении коэффициентов ак, при которых начинает выполняться условие выпуклости и монотонности функции Т$(х) на интервале [хк,хк+\].
1.1.3. Кригинг
Несколько иной подход к задаче интерполяции основан на использовании вероятностных моделей для /(•).
Предположим, что /(х) — гауссовский случайный процесс с нулевым средним и корреляционной функцией Щи, у) — 'Ef(u)f(v). Формальное решение задачи об интерполяции гауссовского процесса /(•) с известной корреляционной функцией хорошо известно (см., например, [15, 16] и [17]): наилучшая в смысле
средне-квадратичного критерия качества интерполяция имеет вид:
п
(1.3)
к=1
где ядро К(-,-) удовлетворяет уравнению Винера-Хопфа-Колмогорова
Е
/(х)-^К(х,Хк)/(Хк)
к=1
/рд = о, 5 = 1,...,п.
(1.4)
При этом ошибка интерполяции вычисляется следующим образом:
2
<?{х) =Е
=Е
к=1
п
¡(х)-^К(х,Хк)ЦХк)
к=1
т.
В геостатистике этот метод известен под именем кригинга [10, 45-47]. Практическое применение этого метода осложняется тем, что, как правило, корреляционная функция •) точно не известна. Поэтому довольно часто для описания корреляционной функции используются конечномерные параметрические модели, параметры которых оцениваются по данным /(хк) с помощью метода максимального правдоподобия. Например, можно использовать модель = ехр[— (и — у)2/{262)]. Таким образом, для того чтобы найти К{х, Хк) надо оценить параметр в. К сожалению, кригинг оказывается довольно чувствительным к выбору вероятностной модели. Например, если воспользоваться описанной выше моделью для интерполяции функций с разрывами, то результат может быть несравнимо хуже, чем при использовании кубических сплайнов. Если же функция будет гладкой, то метод работает, как правило, очень хорошо.
1.1.4. Барицентрический метод интерполяции
С математической точки зрения, идея использовать дробно-рациональные функции для интерполяции основана на их способности хорошо приближать
как очень гладкие функции, так и функции являющиеся кусочно-пол иномиаль-ными. В частности, справедлив следующий факт (см. [48]). Пусть Т>т множество дробно-рациональных функций
ао + а\х + • • • + атхт
Dm(x) =
1 + Ь\х Н-----1- Ътх
т
порядка га. Тогда
inf sup ||а;| — D(x)| < ехр(—у/т).
DGVmxe{-i,i]
Поэтому на первый взгляд кажется, что для интерполяции можно было бы использовать
п
Dn(x) = arg min V]\D(xk) - f(xk) I-
л
Однако Dn(x) может иметь сингулярности типа (х — xs)~ , где xs некоторая точка из интервала (х\, хп), и поэтому использовать данный метод не целесообразно.
Один из подходов, позволяющий избавиться от полюсов в дробно-рациональной интерполяции, связан с барицентрическим методом [49]. Его идея — построить дробно-рациональную аппроксимацию на основе локальных интерполяционных полиномов рк(х), к = 1,..., п — d степени d таких, что
Рк{хг) = f(xt), г = к,..., к + d.
В работе [9] был предложен следующий метод гладкой склейки этих полиномов:
n—d /n—d
Г(Ж) = Кг(х)рг(х) / ^ (L5)
г=1 ' г=1
где
(-1)г
Кг(х) =
(X — хг)(х — Жг+1.) . . .{х — Жг+сО Легко проверить, что
г(хг) = Цх1), г = 1,...,п.
Менее тривиальны два следующие результата [9].
Теорема 1. Функция г{х) не имеет полюсов на действительной оси.
Обозначим h — тахг |жг_1 — хг\ и определим норму функции и{х), х £ [а, 6] как ||n||c = sup^b] |w(x)|.
Теорема 2. Пусть d > 1, f е Cd+2[ а, Ь]. Если число п — d нечетное, то
iir _ /цс <
п d + 2
/Три четном п — d
~f\\c<hd+1(
(b-a)\\f^\\c , H/^llc"
ik--ль- + d+1 ,
Описанный выше барицентрический метод обеспечивает хорошую точность интерполяции в случае равномерной сетки хг+\ — хг = const и высокой гладкости интерполируемой функции. Если же сетка неравномерна или функция / имеет разрывы, то его точность может быть невысока. Это явление объясняется наличием «глубокой памяти» у данного метода, когда \к>к(х)Рк(х)\ убывает очень медленно при удалении точки х от отрезка xk+d\- Этим также объясняется присущий этому методу ярко выраженный гиббсовский эффект.
1.2. Эквивалентность метода интерполяционных сплайнов и предельных интерполяций стационарного гауссовского процесса
В этом разделе мы покажем, что методы интерполяции сплайнами тесно связаны с классической задачей интерполяции стационарных гауссовских процессов, а именно, с интерполяцией гауссовского случайного процесса со спектральной плотностью
FQ,mAu) = . .2т , „2т > (L6)
Я
cjzm + a
здесь Q - положительная постоянная, a ^ 0 и т > 1 - известное целое число.
Напомним, что спектральная плотность стационарного процесса /(■) с корреляционной функцией = Е/(£ + в)/(в) определяется как
оо
Г(со) = е (И.
—оо
Напомним, что формальное решение задачи об интерполяции гауссовско-го процесса /(•) с известной корреляционной функцией следующее (см. раздел 1.1.3): наилучшая в смысле средне-квадратичного критерия качества интерполяция имеет вид (1.3), где ядро К(-, •) удовлетворяет уравнению Винера-Хопфа-Колмогорова (1.4).
К сожалению, использовать на практике эти формулы довольно сложно. В нашем случае, когда процесс /(■) имеет спектральную плотность из (1.6), оптимальное ядро
') = О»
являющееся решением (1.4), зависит от параметров аиС^ которые, как правило, неизвестны. Поэтому их необходимо оценивать, например, используя метод максимального правдоподобия. Такой подход принципиально усложняет решение задачи интерполяции, так как возникает необходимость решать невыпуклую оптимизационную задачу. Если же учесть то, что практически никогда нет уверенности в том, что интерполируемый процесс имеет действительно спектральную плотность С}(и)2тп + а2т)_1; то оценивание этих параметров при помощи метода максимального правдоподобия кажется не совсем обоснованным.
Более робастный подход к задаче интерполяции основан на линейном методе, который получается в результате предельного перехода в (1.4) при а —> 0. Заметим, что в этом случае для построения интерполяции уже не нужно оценивать ни ф, ни а. Однако отметим также, что этот предельный переход не совсем очевидная операция поскольку
Нт Я = -5-
а—»о и)2т + а2т 002т
и
оо
G rl
du — оо.
и2т
Это означает, что предельный случайный процесс со спектральной плотностью Qtü~2m не существует в обычном смысле. Тем не менее, как мы увидим далее, нетрудно выписать простые линейные уравнения для предельного ядра интерполяции
lim KQ^m{x, Хк) = Кт(х, Хк), к = 1,...,п.
а—» О
Определим функции s = 1,... ,п — 1} следующим рекуррентным
образом:
-Л. s_|_i — J\s
= (L7)
Xs+j+1 - xs
Теорема 3. Пусть все точки Xk, к = 1,2,... ,п различны и п > т. Тогда Кт(х,Хк) - решение линейной системы уравнений
п
Y,Km{x,Xk)Xl = xp, р = 0,... ,т — 1, (1.8)
k=1
п
J2Km(x,Xk)d^(Xk) = d^(x), s = 1,... ,п - т. (1.9)
к=1
Доказательство. Нетрудно проверить с помощью формулы Тейлора и простых вычислений, что для корреляционной функции процесса /(•) со спектральной плотностью из (1.6) справедливо следующее представление:
Ra(r) d=E/(0)/(r) = Q
cos(2ttut) —5-^—düj
—oo
(1.10)
=Q [ra(r) + rc(r) + Pa(r)] ,
где
г„(т) =а1-2™ £
2s
s=0 оо
(2*)!
■(та)
2s
OJ
2s
ш2 то + I
dcu,
r0(r) =| r
\2m-l
OJ
-2m
—oo
TO—1
л V (-1)'(2тч)2"
-oo
dcj,
oo
(1.11)
Pair) =a
1-2 to
W2m(l +CJ2m)
X
-oo
X
со8(27гато;) — ^^ в=0
Легко также видеть, что
то-1 / ^«м \ 2s
(—1)5(27го;та;)'
dco.
lim pQ(r) = 0.
а->0
(1.12)
Заметим еще, что интеграл во втором уравнении в (1.11) вычисляется как
оо
СО
-2 то
то—1
(-1)S(2W)
-оо
2s'
(-1)ш(2тг)2т 2(2т - 1)! '
duj =
(1.13)
В этом несложно убедиться, интегрируя по частям 2га — 1 раз
00
0J
-2 то
то—1
соб
н-Е
S. ,2s'
s=0
(2s)!
dcu
(-2га + 1)
(2га - 1)! ^ (-l)m+1
OJ
—2то+1
d
—оо оо
0J
-оо оо
(2га- 1)!
doj
_,d2m~l du2m~l
sin(o;)
то—1
сое
м-Е
s, ,2s
s=О то—1
сое
н-Е
s=0
(25)!
(-l)so;2g (2s)!
doj
duj
du =
(—l)m 7Г
CO
-oo
(2га- 1)!'
Для того, чтобы найти уравнения для предельного ядра •) преобразуем систему уравнений (1.4) к эквивалентной форме. Для этого определим следующие величины
дЫ _ дЬ1
дм = /(*,), = ^ 5
Xs+j+i — Xs
Используя их, можно переписать (1.4) как две системы уравнений
Е Е
п
f(x)-Y,KQ,a,m(x>Xk)f(Xk)
fc=1 п
f(x)-Y,KQ^m{x,Xk)f{Xk)
к=1
дМ = о
А[1] -О
гг—1 — и>
(1.14)
Е
f(x)-^KQta,m(x,Xk)f(Xk)
к=1
д [m—1] _ 0
^n-m+l — и
и
Е
п
}{х)-^^т{х,Хк)}{Хк)
к=\
дн = 0, s = 1,...,п-
т.
(1.15)
Домножим первое уравнение в (1.14) на а2т 1. Тогда из (1.10)—(1.12) легко видеть, что в получившемся уравнении можно перейти к пределу при а —>■ 0 и
(1.16)
fc=i
Посмотрим теперь на второе уравнение в (1.14). Домножив его на а2т 3, получим в силу (1.10)—(1.11)
\im\(x-Xn)2-(x-Xn^)2
71 V
- xk) [№ - Хп)2 - {Хк - хп._i)2] \ = 0.
к=1 ^
Отсюда, учитывая (1.16) получаем
п
ХкКт(х, Хк) = ж.
fc=1
Продолжая действовать аналогичным образом, приходим к (1.8). Уравнения (1.9) вытекают из (1.15) и определения функций d\T\x) из (1.7). ■
Напомним, что интерполяционный сплайн определяется как предел при б —» 0 решения следующей оптимизационной задачи:
1
{1 п 1 1
+ (1-17)
.7 = 1 г\
Очевидно, что интерполяционный сплайн из (1.17) линеен по Yk, к — 1,..., п и его можно записать в виде
п к=1
Теорема 4. Предположим, что все точки Х3, j = 1..., п различны ип > т. Тогда
]™кЬ,т(х,У) = Кт(х, у), где ядро Кт(-, •) определено в теореме 3.
Доказательство. Со статистической точки зрения решение задачи (1.17) можно интерпретировать следующим образом. Предположим, что у нас имеются наблюдения
Yk = f(Xk) + k = 1,..., n,
Похожие диссертационные работы по специальности «Теоретические основы информатики», 05.13.17 шифр ВАК
Сглаживающие изогеометрические и робастные сплайны: методы и алгоритмы2004 год, кандидат технических наук Березовский, Михаил Витальевич
Минимальные вещественные и комплексные сплайны2000 год, доктор физико-математических наук Бурова, Ирина Герасимовна
Моделирование и обработка числовых данных с помощью унифицированной технологии построения интерполяционных сплайнов2016 год, кандидат наук Дорофеев, Алексей Анатольевич
Оптимизация рекуррентных моделей временных рядов на основе B-сплайнов 2-го и 3-го порядков2008 год, кандидат физико-математических наук Эшаров, Элзарбек Асанович
Математические методы и алгоритмы обработки информации при идентификации динамических систем2004 год, доктор физико-математических наук Малевинский, Михаил Федорович
Список литературы диссертационного исследования кандидат наук Крымова, Екатерина Александровна, 2013 год
Литература
1. Green P., Silverman В. Nonparametric Regression and Generalized Linear Models: A Roughness Penalty Approach. Chapman and Hall/CRC Monographs on Statistics and Applied Probability Series. Chapman &; Hall, 1994. P. 184.
2. Молчанов И. Машинные методы решения прикладных задач алгебра, приближение функций. Наук, думка, 1987. С. 287.
3. Дзядык В. Аппроксимационные методы решения дифференциальных и интегральных уравнений. Наукова думка, 1988. С. 302.
4. Березин И., Жидков Н. Методы вычислений. № т. 1. Наука, Глав. ред. физико-математической лит-ры, 1966. С. 464.
5. Kvasov В. Methods of Shape-preserving Spline Approximation. World Scientific, 2000. P. 338.
6. Калиткин H. H. Численные методы. 2 изд. БХВ-Петербург, 2011. С. 592.
7. Завьялов Ю. С., Квасов Б. И., Мирошниченко В. Л., Яненко H. Н. Методы сплайн-функций. Наука, 1980. Р. 352.
8. Чебышев П. Л. Избранные труды, Ed. by О. С. Гельфонд. Классики науки. Изд-во Академии Наук СССР, 955. Р. 888.
9. Floater M. S., Hormann К. Barycentric rational interpolation with no poles and high rates of approximation // Numerische Mathematik. 2007. — august. Pp. 315-331.
10. Krige D. A statistical approach to some mine valuations and allied problems at the Witwatersrand: Master's thesis / University of Witwatersrand. 1951. P. 272.
11. Duhamel du Monceau H.-L. Élémente de l'architecture navale: ou Traité pratique de la construction des vaisseaux. Chez C.-A. Jombert, 1758. P. 352.
12. Пинскер М. Оптимальная фильтрация квадратично-интегрируемых сигналов в белом гауссовском шуме // Проблемы Передачи Информации. 1980. Т. 16, № 2. С. 120-133.
13. Голубев Г. К. О минимаксной фильтрации функций в Ь2 // Проблемы Передачи Информации. 1982. Т. 18, № 4. С. 67-75.
14. Голубев Г. К., Нусбаум М. О непараметрическом оценивании функции регрессии в L2 // Проблемы Передачи Информации. 1990. Т. 26, № 3. С. 38-49.
15. Колмогоров А. Н. Стационарные последовательности в гильбертовом пространстве // Бюлл. МГУ. 1941. Т. 2, № 6. С. 3-40.
16. Колмогоров А. Интерполирование и экстраполирование стационарных случайных последовательностей // Изв. АН СССР. 1941. Т. 5, № 1. С. 3-14.
17. Wiener N. Extrapolation, Interpolation, and Smoothing of Stationary Time Series: With Engineering Applications. Massachusetts institute of technology, 1970. P. 176.
18. Stein C. Estimation of the mean of a multivariate normal distribution // Ann. Statist. 1981. Vol. 9. Pp. 1135-1151.
19. Kneip A. Ordered linear smoothers. // Annals of Statistics. 1994. Vol. 22. Pp. 835-866.
20. Nemirovski A. Topics in non-parametric statistics. Lectures Notes in Math. Berlin: Springer-Verlag, 2000. P. 197.
21. Catoni O. Statistical learning theory and stochastic optimization. Lectures Notes in Math. Berlin: Springer-Verlag, 2004. P. 273.
22. Leung G., Barron A. Information theory and mixing least-squares regressions // IEEE Transactions on Information Theory. 2006. Vol. 35, no. 8. Pp. 3396-3410.
23. Golubev Y. Exponential weighting and oracle inequalities for projection estimates // Problems of Information Transmission. 2012. Vol. 48, no. 3. Pp. 269-280.
24. Rigolet P., Tsybakov A. Sparse estimation by exponential weighting. // Statist. Sei. 2012. Vol. 27, no. 4. Pp. 558-575.
25. Dalalyan A., Salmon J. Sharp oracle inequalities for aggregation of affine estimators // Annals of Statistics. 2012. Vol. 40, no. 4. Pp. 2327-2355.
26. Wahba G. Spline Models for Observational Data. CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics, 1990. P. 169.
27. Wang Y. Smoothing Splines: Methods and Applications. Chapman & Hall/CRC Monographs on Statistics & Applied Probability. Taylor к Francis, 2011. P. 384.
28. Лоран П.-Ж. Аппроксимация и оптимизация. МИР, 1975. С. 496.
29. De Boor С. A practical guide to splines. Springer, 1978. Vol. 27 of Applied Mathematical Sciences. P. 372.
30. Матвеев О. В. Интерполирование 1)то-сплайнами и базисы в пространствах Соболева // Матем. сб. 1998. Т. 189, № 11. С. 75-102.
31. Матвеев О. В. Сплайн-интерполяция функций нескольких переменных и базисы в пространствах Соболева // Труды МИАН. 1992. Т. 198. С. 125-152.
32. Матвеев О. В. Аппроксимативные свойства интерполяционных £>т-сплайнов // Докл. АН СССР. 1991. Т. 321, № 1. С. 14-18.
33. Матвеев О. В. Интерполирование 1}то-сплайнами на хаотических сетках: Дис. докт. физ.-матем. наук / Ин-т матем. и мех. УрО РАН. Екатеринбург, 1994. С. 14-18.
34. Шадрин А. Ю. О приближении функций интерполяционными сплайнами, заданными на неравномерных сетках // Матем. сб. 1990. Т. 181, № 9. С. 1236-1255.
35. Никольский С. М. Соболева пространство // Матем. Энциклопедия. М.: Сов. Энциклопедия, 1985. Т. 5. С. 56-58.
36. Karlin S., Micchelli С. A., Rinott Y. Multivariate splines: a probabilistic perspective // Journal of Multivariate Analysis. 1986. Vol. 20, no. 1. Pp. 69-90.
37. Wahba G., Craven P. Smoothing noisy data with spline functions // Numerische Mathematik. 1978. Vol. 31, no. 4. Pp. 377-403.
38. Wahba G. Smoothing noisy data with spline functions // Numerische Mathematik. 1975. Vol. 24, no. 5. Pp. 383-393.
39. Weba M. Simulation and approximation of stochastic processes by spline functions // SIAM Journal on Scientific and Statistical Computing. 1992. Vol. 13, no. 5. Pp. 1085-1096.
40. Seleznjev O. Spline approximation of random processes and design problems // Journal of Statistical Planning and Inference. 200. Vol. 84, no. 1-2. Pp. 249-262.
41. Schweikert D. G. An interpolation curve using a spline in tension //J. Math. Phys. 1966. Vol. 45, no. 3. Pp. 312-317.
42. Späth К. Exponential Spline Interpolation // Computing. 1969. Vol. 4, no. 3. Pp. 225-233.
43. Renka R. J. Interpolatory tension splines with automatic selection of tension factors // SIAM Journal on Scientific Computing. 1987. — May. Vol. 8, no. 3. Pp. 396-415.
44. Renka R. J. Algorithm 716: TSPACK: tension spline curve-fitting package // ACM Transactions on Mathematical Software. 1993. Vol. 19, no. 1. Pp. 81-94.
45. Sacks J., Welch W. J., Mitchell T. J., Wynn H. P. Design and Analysis of Computer Experiments // Statistical Science. 1989. Pp. 409-435.
46. Kanevski M. Advanced mapping of environmental data: geostatistics, machine learning and Bayesian maximum entropy. John Wiley and Sons, 2008. P. 352.
47. Emery X. Simple and Ordinary Kriging. Mulrigaussian Kriging for Estimation recoverable Reserves // Mathematical Geology. 2005. Vol. 37, no. 3. Pp. 295-310.
48. Дзядык В. К. Введение в теорию равномерного приближения функций полиномами. Наука, 1977. С. 511.
49. Berrut J.-P., Trefethen L. N. Barycentric Lagrange Interpolation // SIAM. 2004. Vol. 46, no. 3. Pp. 501-517.
50. Тихомиров В. Некоторые вопросы теории приближений. Москва: Наука, 1976. С. 304.
51. Speckman P. Spline smoothing and optimal rates of convergence in nonparamet-ric regression // Ann. Statist. 1985. Vol. 13. Pp. 970-983.
52. Eubank R. Nonparametric Regression and Spline Smoothing, Second Edition. Statistics: A Series of Textbooks and Monographs. Taylor & Francis, 1999. P. 360.
53. Tikhonov A., Arsenin V. Solution of Ill-posed Problems. Scripta Series in Mathematics. Washington: V. H. Winston & Sons, 1977.
54. Engl H., Hanke M., Neubauer A. Regularization of Inverse Problems. Mathematics and Its Applications. Springer, 1996. P. 322.
55. Demmler A., Reinsch C. Oscillation matrices with spline smoothing // Numerische Mathematik. 1975. Vol. 24. Pp. 375-382.
56. Nussbaum M. Spline smoothing in regression models and asymptotic efficiency in L2 // Annals of Statistics. 1985. Vol. 13, no. 3. Pp. 984-997.
57. Akaike H. Information theory and an extension of the maximum likelihood principle // Proc. 2nd Intern. Symp. Inf. Theory. 1973. Pp. 267-281.
58. Juditsky A., Nemirovski A. Functional aggregation for nonparametric regression // Annals of Statistics. 2000. Vol. 28. Pp. 681-712.
59. Yang Y. Combining different procedures for adaptive regression //J. Multivariate Anal. 2000. Vol. 74. Pp. 135-161.
60. Rigolet P., Tsybakov A. Linear and convex aggregation of density estimators // Math. Methods Statist. 2007. Vol. 16. Pp. 260-280.
61. Lecue G. Simultaneous adaptation to the margin and to complexity in classification // Annals of Statistics. 2007. Vol. 35. Pp. 1698-1721.
62. Golubev Y. On universal oracle inequalities related to high dimensional linear models // Ann. Statist. 2010. Vol. 38, no. 4. Pp. 2751-2780.
63. Conte S., de Boor C. Elementary Numerical Analysis. New York: McGraw-Hill, 1972. P. 258.
64. Gene G., Van Loan C. F. Matrix computations. Johns Hopkins University Press, 2012. Vol. 3 of Johns Hopkins Studies in the Mathematical Sciences. P. 756.
65. Lophaven S.N. H., Nielsen, S0ndergaard J. DACE - A Matlab Kriging Toolbox, Version 2.0. DTU, 2002. P. 26.
Список публикаций
1. Голубев Г. К., Крымова Е. А. Об интерполяции гладких процессов и функций // Проблемы Передачи Информации. 2013. Т. 49. С. 61-84.
2. Крымова Е. А., Черноусова Е. О. Оракульное неравенство для метода экспоненциального взвешивания упорядоченных оценок // Труды МФТИ. 2013. Т. 5, № 3(19). С. 55-66.
3. Chernousova Е., Golubev Y., Krymova Е. Ordered smoothers with exponential weighting // Electronic Journal of Statistics. 2013. Vol. 7. Pp. 2395-2419.
4. Голубев Г. К., Крымова Е. А. Сплайны и стационарные гауссовские процессы // Доклады 9-ой Международной конференции «Интеллектуализация обработки информации». 2012. С. 207-211.
5. Голубев Г. К., Крымова Е. A. Splines and stationary Gaussian processes // Информационные технологии и системы - 2012 (ИТиС 2012): сб. трудов конференции. ИППИ РАН, 2012. С. 145-150.
6. Крымова Е. А. Оракульное неравенство для метода экспоненциального взвешивания упорядоченных оценок // Труды 55-й научной конференции МФТИ. МФТИ, 2012. С. 147-149.
7. Chernousova Е., Golubev Y., Krymova Е. On oracle inequality for exponential weighting of ordered smoothers // Proceedings of the 18th European Young Statisticians Meeting (EYSM- 2013). 2013. Pp. 1-5.
8. Krymova E. Oracle inequalities for the exponential weighting method in the case of regression estimation problem // Информационные технологии и системы -2013 (ИТиС 2013): сб. трудов конференции. ИППИ РАН, 2013. С. 348-351.
Обратите внимание, представленные выше научные тексты размещены для ознакомления и получены посредством распознавания оригинальных текстов диссертаций (OCR). В связи с чем, в них могут содержаться ошибки, связанные с несовершенством алгоритмов распознавания. В PDF файлах диссертаций и авторефератов, которые мы доставляем, подобных ошибок нет.