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

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

Крымова Екатерина Александровна

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

05.13.17 - Теоретические основы информатики.

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

' 'ПЯ 2013

Москва - 2013

005539009

Работа выполнена в секторе 5 Интеллектуального анализа данных и моделирования Федерального государственного бюджетного учреждения науки Института проблем передачи информации им. A.A. Харкевича РАН

Научный руководитель: доктор физико-математических паук,

Голубев Георгий Ксенофонтович

Официальные оппоненты: доктор физико-математических наук,

Бурнашев Марат Валиевич, лаборатория №1 Института проблем передачи информации им. A.A. Харкевича РАН, ведущий научный сотрудник

доктор физико-математических наук, профессор,

Назин Александр Викторович,

Институт проблем управления им. В .А. Трапезникова РАН, ведущий научный сотрудник

Ведущая организация: федеральное государственное бюджетное учреждение науки Вычислительный центр им. A.A. Дородницына Российской академии наук.

Защита состоится «_ в / д - часов на заседании диссер-

тационного совета Д 212.156.04 при Московском физико-техническом институте (государственном университете) по адресу: 141700, г. Долгопрудный, Московская обл., Институтский пер., д. 9, ауд. 204 нового корпуса.

С диссертацией можно ознакомиться в библиотеке Московского физико-технического института (государственного университета).

Автореферат разослан « » 2013 г.

Ученый секретарь

Общая характеристика работы

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

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

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

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

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

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

• позволяют хорошо интерполировать гладкие функции;

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

• допускают исключительно быстрые алгоритмы для их вычисления.

Эти свойства енлайнов были замечены и использованы инженерами очень давно, по-видимому, первое упоминание о сплайнах содержится в книге XVIII века А.-Л. Дюамеля дю Монсо.

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

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

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

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

Очевидно, что выбор наилучшей оценки из заданного семейства оценок является частным случаем поиска наилучшей выпуклой комбинации оценок из этого семейства. Такой метод построения оценок называется агрегацией. Первые подходы к агрегации оценок были основаны на разбиении наблюдений на две независимые части. При этом оценки строились по одной части наблюдений, а наилучшая выпуклая комбинация вычислялась по другой. Этот подход был разработан независимо А. Немировским и О. Катони. Разбиение выборки на две части неизбежно влечет потери статистической информации, содержащейся в наблюдениях, и на практике его естественно стараются избежать. С математической точки зрения деление выборки приводит к тому, что получающиеся верхние границы для риска агрегированной оценки оказываются хуже границ Кнайпа. Существенный прогресс в методах агрегации, не использующих разбиение выборки, был достигнут в работе Г. Леюнга и А. Баррона для метода экспоненциального взвешивания. Дальнейшее развитие методов этой работы сделано Г.К. Голубевым для агрегации проекционных оценок. Отметим также, что несколько иные результаты для метода агрегации функций из словаря с помощью метода экспоненциального взвешивания в задаче восстановления функции регрессии получены недавно Ф. Риголле и А. Цыбаковым, А. Далаляном и Ж. Салмоном.

Поэтому цели данной работы состоят в том, чтобы:

• математически обосновать близость интерполяционных сплайнов к наилучшим методам интерполяции функций из соболевских классов;

• разработать метод контроля точности для интерполяционных сплайнов;

• получить оракульные неравенства для экспоненциальной агрегации сглаживающих сплайнов, которые улучшают неравенство Кнайпа.

В соответствии с перечисленными целями были определены задачи исследования:

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, Москва, Россия);

• Международная конференция молодых ученых «Информационные Технологии и Системы» (2012, Петрозаводск, Россия; 2013, Калининград, Россия);

• 55-я Всероссийская научная конференция Московского физико-технического института (2012, Долгопрудный, Россия).

Также результаты работы обсуждались на семинарах Лаборатории структурных методов анализа данных в предсказательном моделировании МФТИ (2012, 2013).

Публикации. Основные результаты по теме диссертации изложены в восьми печатных изданиях, из которых [1-3] изданы в журналах, рекомендованных ВАК.

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

Структура и объем диссертации. Диссертация состоит из введения, 3 глав, заключения и библиографии. Общий объем диссертации 97 страниц, включая 15 рисунков. Библиография включает 65 наименований.

Благодарности. Автор благодарен своему научному руководителю Георгию Ксенофонтовичу Голубеву за постановки задач, плодотворные обсуждения, за постоянную поддержку и участие.

Работа выполнена при поддержке Лаборатории структурных методов анализа данных в предсказательном моделировании, МФТИ, грант правительства РФ дог. 11.G34.31.0073.

Содержание работы

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

В первой главе рассматривается задача интерполяции неизвестной функции /(х), х £ М. А именно, с помощью данных (Х.У) = {XУк = /(Хк), к = 1,. .., п} необходимо восстановить значение функции /(х) в некоторой заданной точке х £ (0,1). Здесь и далее для простоты предполагается, что все точки Хк различны, упорядочены Х\ < Х^ < ■ -. < Хп и принадлежат отрезку [0,1].

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

Во втором разделе изучается интерполяция стационарного гауссовского процесса со спектральной плотностью Ра(и>) = С^/(ш2т + а2т), где С}, а - положительные, как правило, неизвестные параметры, то > 1 - известное целое число.

Хорошо известно, что наилучшая в смысле квадратичного критерия качества интерполяция гауссовского процесса со спектральной плотностью Ра(ш) имеет вид

п

Цх, Х,У)=^ Хк)Ук,

к=1

где ядро Ка (5.т(-, ■) определяется как решение уравнения Винера-Хопфа-Колмо-горова

Е

пх,) = о, (1)

к=1 ^ где 5 = 1,... ,п. К сожалению, использовать это уравнение на практике затруд-

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

а 0. Заметим однако, что поскольку

оо

1

Нт —-— = —— и

а-»о Ш2т + а2т ш2т

„ Лш = оо,

ш2т '

— оо

,-2т

случайный процесс со спектральной плотностью С)ш~ т не существует в обычном смысле. Тем не менее, предельное ядро Кт(х. X) = Птп_>о X) существу-

ет. Чтобы найти уравнения, которым оно удовлетворяет, определим функции

40)И = \х. - хГ~\ = ¿уМ-^М

Теорема 1. Пусть все тонки Хк, к = 1,2.... ,п различны и п > тп + 1. Тогда Кт(х,Хк) является решением системы линейных уравнений

п

Кт(х, Хк)^[Хк] = 4т)[х], з = 1,...,п-т,

к=1 п

^Кт(х,Хк)Х1 = хр, р = 0,... ,т — 1. к= 1

Основным результатом раздела является эквивалентность интерполяции сплайнами и оптимальной интерполяции обобщенного гауссовского процесса со спектральной плотностью ш~2т. Интерполяционный сплайн определяется как предел при б —>• 0 решения следующей оптимизационной задачи:

^т(х,Х, У) = агетш {¿]Г [У, - /(X,)]2 + ± ' [/^(х)]2^}.

¿=1 о

Интерполяционный сплайн линеен но У^, к = 1,..., п и его можно записать в виде

п

X, У) = £ Кд т{х, Хк)Ук.

к=1

Теорема 2. Предполоо/силг, что все точки Xj = 1.... ,п, различны и п> т. Тогда

КЯ<™(Х'у) = Кт(х> у где ядро Кт(•, •) определено в теореме 1.

В третьем разделе рассматривается задача сравнения минимаксного риска интерполяции и интерполяции методом сплайнов в классе гладких стационарных гауссовских процессов. Пусть /(•) — стационарный гауссовский процесс с известной спектральной плотностью ¡^(и). Задача состоит в том, чтобы восстановить /(х) на интервале [О, Н\ по наблюдениям = где Xк = кИ, к = О, ±1, ±2,.... Поскольку процесс гауссовский и стационарный, то его наилучшая интерполяция имеет вид

оо

/(х,Х,У) = Л К(х-Хк)Ук,

к=-оо

где А'(-) симметричное ядро, которое находится из минимизации средне квадратичной ошибки интерполяции. Для интерполяции /(х, X, У) эта ошибка определяется следующим образом:

Л

E[f(x)-f(x,X,Y)}2dx.

Предположим, что процесс f{x) гладкий, точнее, что он является гуссовским процессом, спектральная плотность которого принадлежит классу ^^(L), определяемому условием

Щ1{т\х)}2 < L.

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

• вычислить минимаксную ошибку интерполяции

iW) = inf sup al(f,F),

f FeT-»(L)

где inf вычисляется по всем интерполяциям;

• построить минимаксную интерполяцию У), то есть такую, что

i№)= sup al(l,F).

FeJ^(L)

Теорема 3. Минимаксная ошибка интерполяции вычисляется как При этом минимаксная интерполяция имеет вид

h

f(Xk),

к= — ос

где — симметричное ядро, преобразование Фурье которого определяется

как

к, и =

здесь ел, = 1 - 2-i+Vm.

1, и€[0,ш,),

2m'1(l-w)m, ше[ш„1/2),

1 — 2т_1о/", ш 6 [1/2,1 -и>,),

О, ш > 1 — LO*',

Чтобы понять, насколько хорошо сплайны интерполируют процессы со спектральными плотностями из класса Jrm{L), вычислим максимальную ошибку интерполяции

sup olU,Sm)-fef™(L)

здесь Sm(x,Y) = limf_>o S!^(x, Y) — интерполяционный сплайн, который в силу теорем 1, 2 имеет следующий вид:

Sm(x,X,Y) = j jr kJX~XC

k=—oo

h

I(Xk).

При этом преобразование Фурье ядра Кт(-) определяется как

Кт(и) = Можно показать, что

fc/O

—2т-

-1

Г / l \ 2тп

72h[j^(L),Sm} = - (-) maxgm(uj),

где

kftO 4 у J

Аналитически вычислить максимум функции gm(w) довольно сложно. Можно подсчитать его численно и найти величину (T^[Jrm(L),5'm]//i™(Z;), которая характеризует эффективность интерполяции сплайнами при различных т. Оказывается, что ошибка интерполяции сплайнами довольно близка к минимаксной ошибке интерполяции. Например, эффективность для кубических сплайнов (т. = 2) приблизительно равна 1,35.

Четвертый раздел посвящен интерполяции гладких функций, заданных значениями на бесконечной равномерной решетке со случайным сдвигом. Точнее рассмотрим интерполяцию гладких функций из соболевского класса W™(L), задаваемого условиями

оо

[f(m\x)}2dx<LT, supp{/} € [0;Т].

—ос

При этом будем предполагать, что точки Х^ расположены на решетке Х^ = /с/г + Ci А: = 0 ± 1,... с шагом h > 0. Здесь и далее С ~ случайная величина равномерно распределенная на [0, h].

Задача состоит в том, чтобы восстановить функцию /(х), х € [0,Т] при заданных значениях Yj* = f(X£). При этом потенциально наилучшее качество интерполяции определяется минимаксной ошибкой интерполяции

т

Ph(L) = inf sup Е (\\f(x)-f(x,X<,Y<)fdx, f fewp(L) J

где усреднение по распределению величины a inf вычисляется по всем интерполяциям.

Следующий результат показывает, что минимаксные интерполяции гауссов-ских случайных процессов со спектральными плотностями из класса J7"1{L) и функций из соболевского класса W™(L) очень близки.

Qm (w) =

1

^bn—X^Jlm

1 - Кг,

Теорема 1. При Т —> оо

Т 4 ч//2

В пятом разделе предлагается простой метод контроля точности интерполяции сплайнами. Будем считать, что Хи — кИ, к = 0. ±1. ±2,... и У*, = /(Xк)-Обозначим Зт(х, У) интерполяционный сплайн порядка т и соответственно «5т+1(:г, X, У) интерполяционный сплайн следующего порядка. В качестве оценки для величины реальной ошибки интерполяции

а2т(х) = и(х)-§т(х,Х,У)}2 будем использовать величину

ст2т(х) = [§т+1(х, X, У) - §т(х, X, У)]2.

Следующий результат обосновывает этот метод.

Теорема 4. Пусть /(х) - стационарный процесс со спектральной плотностью имеющей представление Р(и>) = ф(ш)ш~2т; где ф(-) - положительная четная функция, не возрастающая при и> > 0. Тогда существует постоянная Ут такая, что

Хь+1 х,

(Iх < Ут хк X

Еа2т(х)с1х. (2)

Если интерполируемая функция обладает большой гладкостью, то можно показать, что постоянная Ут в неравенстве (2) близка к 1, точнее Игг^-юо Ут — \.

Заметим также, что условие невозрастания функции ф{ш) при положительных ш можно заменить на условие Аф0(и>) < ф(со) < Вфа(и>), где А, В - некоторые положительные постоянные, а ф0(со) симметричная, не возрастающая функция при положительных со.

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

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

В первом разделе приводится постановка и мотивация задачи оценивания вектора /л = (fij,... ,ßn)T по наблюдениям

Yi = т + г =1,2, ...,п, (3)

где белый гауссовский шум. Для простоты предполагается, что параметр а > О известен. Основная цель состоит в том, чтобы построить оценку вектора ß на основе семейства линейных оценок

fi?(V) = hiYu h е Ч, (4)

где И — заданное множество векторов из К", которое будет описано ниже. Риск оценки Д(У) = (/¿¿(У),..., ßn(Y))T измеряется величиной

здесь Е^, — математическое ожидание по мере Р;„ порожденной наблюдениями (3), | J - [[ и {•, •) обозначают норму и скалярное произведение в К" соответственно, то есть ||х||2 = ]Г"=1 xf, (х, у) = г х^.

Нетрудно показать, что средне-квадратичный риск линейной оценки ßh(Y) вычисляется следующим образом:

R{ß\ß) = \\(l-h).ßf + o2\\h\\\

где х ■ у означает покоординатное произведение векторов х, у G Rn, то есть х ■ у £ М" с компонентами х^, г = 1,..., п.

Очевидно, что этот риск зависит от h и мы можем найти его минимум по h € W, который часто называют оракульным риском

>НЫ = min R(ßh, и), hen

Однако, мы не можем использовать оценку

М*(У) = к* - У, h* = arg min R(ßh, ц),

h€ti

так как она зависит от неизвестного вектора /л. Поэтому нашей целью является построение оценки ДН(У) на основе заданных оценок ДЛ(У), к € И, такой, чтобы се риск был как можно ближе к риску оракула. То есть мы хотим, чтобы равномерно по /х € Ж" выполнялось неравенство следующего вида:

где — остаточный член, который мы хотели бы сделать меньше риска ора-

кула гп(ц). Такого типа неравенства часто называются оракульными. Основной задачей является поиск оценок с минимальным остаточным членом. В общем случае эта задача не имеет решения. Однако в некоторых случаях удается построить оценку ¡л4{У) такую, что:

• < Сгп(ц) для всех /хбЁ", где С > 1 константа,

• Ап(ц) «С гп({1) для всех /х : гп(ц) ;§> а1.

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

Определение 1. Множество % состоит из упорядоченных векторов, если

• Ы € [0,1], г = 1,..., п для всех к ^ И,

• ^¿+1 < Ы, г = 1,..., гг для всех к 6 И,

• если для некоторого натурального к и некоторых к, д € И

кк < Ук, тогда /г* < д, для г = 1,... , п.

Последнее условие означает, что векторы из И могут быть естественным, образом упорядочены, так как для любых к,д € Н возможно только два случая: к, < gi или кг > для всех г = 1,... ,п.

В качестве мотивации для задачи оценивания зашумленного вектора при заданном множестве упорядоченных оценок рассмотрим задачу оценивания регрессионной функции с помощью сглаживающих сплайнов. Необходимо восстановить гладкую функцию /(х), х € [0.1] по наблюдениям

^ = /№> + £&': г = 1,.... п, (5)

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

1

г) = ащ /№)]2 + Р

{^т\х)\Чх\, (6)

где — производная порядка т и р > 0 — сглаживающий параметр.

Для того чтобы свести задачу оценивания функции регрессии с помощью

сплайнов к задаче восстановления вектора в белом гауссовском шуме (3), перейдем

в базис Райнша-Деммлера 4'к{х), х 6 [0,1], к = 1,... ,п. Этот базис обладает

свойством двойной ортогональности

1

/,("•)/■-п.//"1)

(Фк.-Фдп =

■ф(™'{х)ф\т>(х)4х = 6ы\к, к,1 = 1,...,гг, (7)

о

где здесь и ниже {и, у)п обозначает скалярное произведение

п • ,

г=1

и собственные числа упорядочены Лп > ... > Аь Функцию /(•) и наблюдения Z можно разложить по базису Райнша-Деммлера следующим образом:

п

е

}{Хг) = Ук = (•£, Фк)п = Рк + -7=&-

V«

Затем, подставляя (8) в (6), приходим к

п

Ёр(х,Х, У) = ^2рк-фк{х),

к= 1

где

Ик = ащ тш

V 1г-1 4—1 ^

п

- к= 1 к=1 Поэтому задачи (3)-(4) и (5)-(6) эквивалентны при а = е/\Дг, причем

1

П={Н:кк =

-,р> О

1 +р\к

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

Рассматривается оценка, полученная с помощью экспоненциального взвешивания оценок /У\ Н&И, то есть оценка следующего вида

Д(У) = £>Л(У)ДЛ(У),

О)

к€П

где -ш'!(У) положительные веса, такие что Х^лея ^(У) = 1 и

т{У^Н) 1 /V- , Г г(У,р

ю" (У) = 7Г ехр

2/За2

£

96-Н

7Г9 ехр

, /3 > О,

г(У,р,н) — несмещенная оценка риска линейной оценки Д'!(У), а именно г"(У, /х") = ||(1 - А)У ||2 + 2<х2 ¿) А4 - <г2

п.

г=1

Априорные веса 7гл зададим следующим образом

7ГЛ =

1 — ехр< —

1|й+||1 - м,

Р

где

/г+ = тт{д € Н : д > /г},

7ГЛ»« = 1, где 1гтах = тахНеНк, и \\h\U = N.

Также будем предполагать выполненным следующее условие.

Условие 1. Существует постоянная К0 > 0, такая что для всех Н> д из Л

т2-\\9\\2>1<т\1-\Ш-

19

Следующая теорема является основным результатом раздела.

Теорема 5. Пусть ¡5 > 4 и выполнено Условие 1. Тогда равномерно по р £ Ш.п выполнено следующее неравенство:

где С = С{Ка,(3) строго полоэ/сителъная постоянная, зависящая от К0,/3.

Заметим, что этот результат улучшает классическое неравенство Кнайпа.

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

где & — стационарный гауссовский процесс с нулевым средним и = 1, оценить неизвестный вектор р = {р,\,... ,рп}- Основная цель состоит в том, чтобы показать, что оракульные неравенства для метода экспоненциального взвешивания упорядоченных линейных оценок, полученные для белого щума, останутся справедливыми и для цветных шумов.

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

где С — стандартный белый гауссовский шум, а о2(х), х ё [0,1] — неизвестная непрерывная функция. В качестве оценок будем использовать сглаживающие сплайны, которые являются решением оптимизационной задачи (6). Для того чтобы проверить эквивалентность моделей (11) и (10), воспользуемся базисом Райнша-Деммлера ^(.т), х Е [0,1], к = 1 ,...,п из (7). Представляя функцию

О"

У, =/х, + сг&, г = 1,2,..., п.

(10)

^ =/№) + <7(^)0, г = 1,..., тг,

(П)

регрессии в виде f(x) = V'/tMPfc, получаем, что наблюдения (11) эквива-

лентны

п

Ук = {Z, Vfe)n = Míe + ГДе Íí: = °ШМХг)Сг-

j=1

При равномерном распределении точек -AT¿ для базиса Райнша-Деммлера известна следующая асимптотика:

[2

фк(х) ~ \ — cos(ttкх), п,к —» оо. V п

Поэтому при больших гг, j

J n '

P=1

Таким образом, гауссовская последовательность случайных величин к = 1,..., п близка к стационарной. При этом для дисперсии шума в (10) справедлива асимптотическая формула ст2 ~ X^íLi °'2(^¿)/n- Отметим также, что эту величину несложно оценить но наблюдениям (11), например, с помощью оценки a2{Z) = ~~ zi+i?- Поэтому параметр а в (10) можно считать известным.

Оказывается, что для этой задачи оценивания вектора в стационарном гаус-совском шуме с помощью метода экспоненциального взвешивания (9) верен аналогичный Теореме 5 результат.

Теорема 6. Пусть ¡3 > 4 и выполнено Условие 1. Тогда равномерно по ц 6 Мп выполнено следующее неравенство:

С|1 + ^Г

где С = С(К0) /?) строго положительная постоянная, зависящая от Ка,/3.

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

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

В заключении перечислены следующие основные результаты.

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

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

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

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

5. Проведены численные эксперименты, которые показали, что в случае, когда отношение сигнал/шум невелико, экспоненциальное взвешивание позволяет получить оценку с существенно меньшим риском.

Список публикаций

1. Голубев Г. К., Крымова Е. А. Об интерполяции гладких процессов и функций // Проблемы Передачи Информации. 2013. Т. 49. С. G1-84.

2. Крымова Е. А., Черноусова Е. О. Оракульное неравенство для метода экспоненциального взвешивания упорядоченных оценок // Труды МФТИ. 2013. Т. 5, № 3(19). С. 55-6G.

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.

Крымова Екатерина Александровна

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

АВТОРЕФЕРАТ

Подписано в печать 12.11.2013. Формат 60 х 84 1/16. Усл. печ. л. 1,0. Тираж 100 экз. Заказ 354.

Федеральное государственное автономное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)» Отдел оперативной полиграфии «Физтех-полиграф» 141700, Московская обл., г. Долгопрудный, Институтский пер., 9.

Федеральное государственное бюджетное учреждение науки Институт проблем передачи информации им. A.A. Харкевича Российской Академии Наук

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

04201365695

Крымова Екатерина Александровна

Сплайны в задачах интерполяции и регрессионного анализа гауссовских процессов и

гладких функций

05.13.17 - Теоретические основы информатики.

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

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

доктор физико-математических наук

Голубев Георгий Ксенофонтович

Москва - 2013

Содержание

Введение ........................................................................4

Глава 1. Сплайны и интерполяция стационарных гауссовских процессов ........................................................................11

1.1. Обзор методов интерполяции..........................................11

1.1.1. Сплайны........................................................11

1.1.2. Сплайны с натяжением........................................13

1.1.3. Кригинг........................................................14

1.1.4. Барицентрический метод интерполяции....................15

1.2. Эквивалентность метода интерполяционных сплайнов и предельных интерполяций стационарного гауссовского процесса..........17

1.3. Минимаксная интерполяция стационарных гауссовских процессов 25

1.4. Интерполяция гладких функций......................................32

1.5. Контроль точности для интерполяции сплайнами..................41

1.6. Выводы..................................................................44

Глава 2. Экспоненциальное взвешивание упорядоченных оценок 45

2.1. Оценивание в белом шуме с помощью упорядоченных оценок . . 45

2.1.1. Постановка задачи............................................45

2.1.2. Сглаживающие сплайны как упорядоченные оценки ... 48

2.2. Оракульное неравенство для метода экспоненциального взвешивания в задаче оценивания вектора в белом шуме..................50

2.2.1. Метод экспоненциального взвешивания ....................50

2.2.2. Экспоненциальное взвешивание упорядоченных оценок . 54

2.2.3. Дополнительные результаты..................................58

2.2.4. Доказательство Теоремы И..................................70

2.3. Оценивание в стационарном шуме при помощи упорядоченных оценок....................................................................73

2.4. Выводы..................................................................78

Глава 3. Результаты экспериментов....................................80

3.1. Сравнение методов одномерной интерполяции......................80

3.1.1. Быстрый алгоритм для сплайнов порядка га ..............80

3.1.2. Результаты сравнения методов одномерной интерполяции 81

3.2. Сравнение методов контроля точности интерполяции для сплайнов и кригинга..........................................................82

3.3. Сравнение метода экспоненциального взвешивания и метода минимизации несмещенной оценки риска ..............................86

3.4. Выводы..................................................................87

Заключение......................................................................90

Литература......................................................................91

Список публикаций ..........................................................97

Введение

Актуальность работы. Диссертация посвящена задачам математической теории интерполяции стационарных гауссовских процессов и оценивания гладких функций регрессии. При этом существенное внимание уделяется интерполяционным методам и методам оценивания, основанным на сплайнах [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)

здесь д^\х) обозначает производную порядка д фу