Алгоритмы построения сплайнов в выпуклых множествах и их приложения тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат физико-математических наук Ковалков, Александр Викторович

• Ковалков, Александр Викторович
• кандидат физико-математических наук
• 1985

Оглавление диссертации кандидат физико-математических наук Ковалков, Александр Викторович

ВВЕДЕНИЕ.

ГЛАВА I. ПОСТРОЕНИЕ СПЛАЙНОВ В ВЫПУКЛЫХ МНОЖЕСТВАХ

ПО ДИСКРЕТНЫМ ОГРАНИЧЕНИЯМ ТИПА НЕРАВЕНСТВ.

§ I. Элементы линейной теории сплайнов.

1.1. Алгоритм построения сплайнов на основе функций Грина

1.2. Сходимость сплайнов

1.3. 3>т - сплайны и их сходимость

§ 2. Сплайны в выпуклых множествах. Существование, единственность. Характеризация.

§ 3. Алгоритм построения сплайна по дискретным ограничениям типа неравенств.

3.1. Характеризация решения. Эквивалентность задачи квадратичного программирования.

3.2. Описание основного алгоритма.

3.3. Вспомогательный метод.

§ 4.Вопросы численной реализации алгоритма и результаты экспериментов.

§ 5.Дискретизация сплайнов с операторными ограничениями типа равенств.

§ 6.Дискретизация сплайнов на выпуклых множествах. Теорема сходимости.

ГЛАВА 2. СПЛАЙНЫ, УДОВЛЕТВОРЯЮЩЕ НЕПРЕРЫВНЫМ ОГРАНИЧЕНИЯМ.

§ I. Постановка задачи. Структура решения.

§ 2. Эрмитовы сплайны и задача с подвижной границей.

§ 3. Гладкость сплайна и индикатрисы свободных границ.

3.1. Теорема об избыточной гладкости решения.

3.2. Индикатрисы и алгоритм локализации свободных границ.

§ 4. Эволюционные ограничения в задаче сплайнаппроксимации.

4.1. Постановка задачи с эволюционными непрерывными ограничениями.

4.2. Непрерывность изменения тривиальных зон сплайна. ИЗ

4.3. Переход от тривиальных зон к нетривиальным и непрерывность изменения свободных границ.

§ 5. Алгоритм построения сплайнов с ограничениями на функцию полиномиального и онлайнового типа.

§ 6. Построение сплайнов, удовлетворяющих ограничениям на производные.

6.1. Сведение дифференциальных ограничений к ограничениям на функцию.

6.2, Характеристические свойства связанных параметров зон прилипания.

Введение диссертации (часть автореферата) на тему «Алгоритмы построения сплайнов в выпуклых множествах и их приложения»

Современная теория сплайнов является мощным математическим аппаратом обработки экспериментальных данных. Зародившаяся в работах Шенберга (1946) , как алгебраический способ построения гладких кусочно-полиномиальных восполнений сеточных функций,теория приобрела более общий характер после того, как был открыт вариационный принцип, которому подчиняются сплайн-функции (Дж.Холидей, 1957). В 1965 году М.Атья предложил общее определение сплайна, как элемента гильбертова пространства, доставляющего минимум функционалу типа энергии при выполнении обобщенных интерполяционных условий, задаваемых линейным непрерывным оператором. В 1966 году им же было введено понятие сплайна на выпуклых множествах [32], которые порождаются линейными ограничениями на функцию. В математическом смысле при конечном наборе ограничений - это задача о минимизации квадратичного функционала с нетривиальным ядром на выпуклом множестве типа многогранника. Наиболее подробно задача о построении сплайна в выпуклом множестве гильбертова пространства была исследована Лораном /21J на основе теории двойственности. При этом рассматривались, как дискретные, так и непрерывные ограничения на функцию и ее производные.

В алгоритмическом аспекте следует, по-видимому, разделить задачи о поиске сплайнов в выпуклом множестве на задачи двух типов. Первый класс задач связан с наличием конечного числа ограничений типа неравенств и сводится в точности к задаче квадратичного программирования при линейных ограничениях [12, 38 J . Решение этих задач актуально по следующей причине. Среди всего множества ограничений только некоторое подмножество активных ограничений определяет "информативные измерения", которых может оказаться существенно меньше, чем исходных. На этом пути может быть решена задача сжатия информации. Однако применение классических алгоритмов квадратичного программирования [27,28] для расчета сплайнов в выпуклых множествах приводит к трудоемким и медленно сходящимся процессам /Зб]. Более эффективным оказывается применение метода штрафов, разработанный в таких задачах Н.Н.Павловым [26]. Вместе с тем, отметим, что основным моментом при построении сплайна в выпуклом множестве является определение группы активных ограничений (информативной подсетки) , по которым нетрудно построить сплайн. В этой связи в главе I диссертации предлагается алгоритм ориентированного перебора измерений, значительно выигрывающий на практике у классических алгоритмов, и позволяющий строить многомерные аппроксимации [7,15J.

Второй тип задач связан с бесконечным количеством ограничений на аппроксимируемый элемент. К таким задачам относятся задачи построения так называемых изогеометрических аппроксимаций кривых, т.е. функций обладающих заданными геометрическими свойствами типа неотрицательности, монотонности или выпуклости, которые отражают обычно физические свойства объекта. В последние годы был создан ряд алгоритмов построения сплайнов, сохраняющих свойства монотонности и выпуклости на основе алгебраического подхода ["ЗЗ, 35, 37, 40J. В наиболее общем виде этот подход представлен в работе А.И.Гребенникова [ в]. Простым в реализации является алгоритм, разработанный В.Л.Мирошниченко на основе сплайнов Шпета (24j. Возможно использование регуляризующих алгоритмов А.Н.Тихонова [29/.

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

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

20,23,13,30,31 ] . Оказалось, что свободные границы сплайна характеризуются свойством повышенной гладкости сплайна fie].

Перейдем к краткому изложению результатов диссертации.

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

Назовем элемент б из гильбертова пространства X сплайном в выпуклом замкнутом множестве С из X , если

II Тб-\\г = min WTxfy {i) xgC где T - линейный непрерывный оператор из X в гильбертово пространство У .

Рассмотрим выпуклое множество порожденное конечным набором дискретных ограничений вида где - линейные непрерывные функционалы над X . В частности, это могут быть значения функции или ее производных в узлах некоторой сетки, Характеризация сплайна в W имеет следующий вид [21].

Теорема I. Элемент б^ из W является решением задачи (I) тогда и только тогда, когда

Т*Т6>\ = i: где

Л- L, (I)

7Lt & о, (et,er*) =oti , (П)

XL = 0, cct <(е6,<5Г#) (Ш)

Из, теоремы следоет, что б* совпадает с интерполяционным

7\ сплайном б , являющимся решением задачи

II ТбЦу = // Гя/р» где функционалы Ец удовлетворяют условиям (I), а ^ условиям(П). Обозначим через 1ак = J L){t2i} объединение функционалов, удовлетворяющих (I) и (П). Предположим, число N* функционалов из LaK много меньше N . Тогда по затратам времени, а главное памяти ЭВМ оказывается эффективным следующий двухступенчатый алгоритм.

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

UU A Ur Л оставшихся ограничений тех, которые максимально нарушаются t построенном по •> и так, что

II TeJIу < UT6nt1fY.

Это условие обеспечивает сходимость процесса за конечное числао шагов. п

Для построения сплайна оп на подмножестве и<хк используем метод декомпозиции Саутвелла [Зб] для решения задач квадратичного программирования. Это требует построения фундаментальных . сплайнов по заданному набору функционалов. Для функций многих переменных по функционалам,определяющим значения функции и ее производных по направлениям в узлах хаотической сетки,они автоматически получаются в алгоритме построения сплайна с помощью функций Грина [7,14] реализованный автором [2,4] .

Скорость сходимости к Ьак на практике сильно зависит от выбора начального приближения. Приводится ряд приемов, позволяющих быстро и точно определить набор ограничений, близких к Lак. Это позволяет не только выиграть у традиционных методов 1-2 порядка по затратам времени, а главное памяти ЭВМ, но и успешно решать задачу двух переменных [7,15].

В § 5 главы I обоснована также возможность дискретизации задачи интерполяции ТбЦ2 = mm ЦТхЦг , (3) xef'te) где оператор А порожден некоторым множеством функционалов Л

Z с X а г -набор входных данных из гильбертова пространства % . Пусть X, У - сепарабельные пространства. А

Если построить плотное в Z множество линейных непрерывных

100 функционалов {» образующих оператор то для X решение задачи (3) для и решение интерполяционной задачи (3) для оператора Z и вектора совпадают. Определим последовательность операторов {(б£,х) и соответствующих им интерполяционных задач lm 6m=Lm ИТб^П* =

Теорема 2. Если для М > О существует единственный сплайн бм , то последовательность ПРИ тоо сходится по норме X к решению б задачи

II Тб Ну - min.

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

Для функций VJ У* из X, 4>~(t)< 4) + (t), рассмотрим выпуклое замкнутое множество

С1 = х/(е,<р-) $ се,х)*(е,ч>+), \/е£}П sPci,T)f где SP (/,, Т)сХ- пространство сплайнов, порожденное операторами /j ж Т [16]. Тогда С^ совпадает с С^ и для множеств

Clm ={xeXl « С4, X) *(ei, у% I = и^}Л spam>7) справедлива

Теорема 3. Пусть ядро оператора Т конечномерно , образ его замкнут и существует М >0 , для которого решение задачи (1)в С. ^ единственно.

Тогда последовательность решений бт задачи (I) в сходится по норме X к б - решению задачи (I) в С^ .

Во второй главе исследована структура и характеристические свойства решения задачи о построении сплайна в выпуклом замкнутом множестве С из для оператора Т -дифференцирования порядка m . Множество С порождено некоторым набором дискретных ограничений ы.^ ^ ocCt)(tj)$ fi^ на функцию и ее производные до (rn-f) порядка в узлах сетки {tf,t2 ^л/ } » определяющих выпуклое множество W и непрерывными дифференциальными ограничениями вида а), ^ о г

Vtw * би\-Ь) Ъ Ч>- (-6), ье{о, У,(4) где 41 , - произвольные достаточно гладкие функции. tf

Решение поставленной задачи характеризуется участками области определения [а,6], на которых оно удовлетворяет равенствам

6Ci)tt)=%(t) или = itje{oti,.~,m-i}. (5)

Эти участки назовем зонами прилипания сплайна, к ограничению, их концы £ £' - свободными границами зоны, а участки между i зонами - свободными зонами сплайна. 1 зон прилипания к Vr (t) » Ь > О » отметим также величины & (fy) или » к = О, i-1 и назовем их связанными параметрами зон прилипания. Справедливо утверждение

Лемма 4. Сплайн б на свободной зоне [y'f } q г 1 между нетривиальными, т.е. не состоящими из одной точки, зонами прилипания [уп yj и ] является сплайном б [у' ф J по набору дискретных ограничений исходной задачи на ^ J и краевым условиям на производные до (m-i) порядка, определяемых ограничениями и в точках и и связанными параметрами зон прилипания.

Для построения решения необходимо определить общую структуру зон прилипания к ограничениям, и найти свободные границы и -.связанные параметры зон прилипания. Для определения этих свойств воспользуемся аппаратом эрмитовых сплайнов [4, 23].

Вначале рассмотрим задачу с непрерывными ограничениями У £ только на функцию. Определим вспомогательную задачу о сплайне с ^подвижными границами - задачу (11Г). Пусть на отрезках [С, d ] и [j ] из [а,ё] заданы функции % £ W2m[c, d] и Ynp е W™ Се, f] , а на [ сС, 61 задан конечный набор дискретных дифференциальных ограничений, определяющий в выпуклое замкнутое множество. Для любых ^^eCCfd) и € (6J), называемых подвижными границами задачи (ПГ), существует единственное решение б^-j задачи о построении сплайна на участке , по заданному набору дискретных ограничений и условиям на концах участка вида с = O/n-i,

Решением задачи (ПГ) назовем функцию t), t

6)

VnpCt),

В [18] были доказаны следущие свойства

Лемма 5. Гладкость функций б ) и

6(m)(£z~0, ) ^г) по переменным и не меньше гладкости функций и ) .

Лемма 6. Для Ь гладкость функции

6(t; , ) и функционала энергии ^ т Ь по переменным и не меньше гладкости функций Определение . Функцию назовем полной энергией задачи (ПГ) на [с,/] .Ее гладкость ввиду леммы 6 не меньше гладкости функций и w ш-1) глр

Лемма 7. Если € [с, и е /7 то справедливо неравенство

При этом равенство в (7) имеет место, если на

Г*,', Ы Ф Чг и V»P на Ш, fc * К °УТЬ полиномы степени не выше (2m-i) .

Рассмотрим ограничения , 93/ » обладающие непрерывными на Со.,8] производными, за исключением конечного числа точек, где терпят разрыв производные, начиная с порядка m Множество узлов, в которых рвутся производные порядка к z п7, обозначим QK ( ) или QK () » а объединение этих мноч жеств по k- Q (Ч>~)жш(р(

- 13

Пусть [у' , - свободная зона сплайна между нетривиальными зонами прилипания к и . Справедлива

Теорема 8. Если eQm CV~) и ё$т (<р+) , то решение задачи 6 в узлах у' и удовлетворяет равенствам

8)

WУ'гц) = б'т'(?,-о)- бСт)(ъ~о,

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

Определение . Функции вида назовем индикатрисами свободных границ ^ и .

На основе аппарата индикатрис реализован алгоритм локализации свободных границ.

Для определения общей структуры зон прилипания сплайна при непрерывных ограничениях на функцию организуем эволюционный процесс "надвигания" непрерывного ограничения на сплайн 6 в W-множестве вида (2). Введем эволюционное ограничение

9Z &= %'(t) -T.tz, где 7> maac (9'Ct)-^ (t) ) teCo.,61 и соответствующее ему параметрическое семейство выпуклых множеств „, , ~ ,, с = w Wf[a,el/x(i) > % (*,*>} со сплайном, б{Ь,*С) =■ W. подобно задаче (ПГ) определим задачу с эволюционными подвижными узлами ( £ ~ (Т) * = § W) - задачу (ЭПУ). Результаты о гладкости изменения сплайна при варьировании подвижных границ в леммах 5-7 имеют место и для бЦ;^^),^) в задаче (ЭПУ); при непрерывном изменении £ (TJ . Имеет место

Теорема 9. Для V* из Cm[a,S] функционал энергии Ф(^) и границы зон прилипания по Т изменяются непрерывно.

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

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

Автор выражает благодарность к.ф.-м.н.Василенко В.А. и коллективу сотрудников отдела Мацокина A.M. за помощь в работе.

Список литературы диссертационного исследования кандидат физико-математических наук Ковалков, Александр Викторович, 1985 год

1. Бежаев АД). Оценки ошибки сплайн-интерполяции в многомерных ограниченных областях. - Новосибирск, 1984. - 17 с. -(Препринт J6 102, ВЦ СО АН СССР).

2. Бежаев А.Ю., Василенко В.А., Зюзин М.В., Ковалков А.В. и др. Библиотека программ LIM~3.no аппроксимации функций и цифровой фильтрации. Автометрия, 1984, № 6, с. 7-13.

3. Библиотека программ ПО А для аппроксимации функций и обработки данных. Вариант Ф0РТРАН-1У/ В.А.Василенко,А.В.Ковалков, М.В.Зюзин и др. Новосибирск, 1981. - 39с.-(Препринт/СО АН СССР, ВЦ; № 300).

4. Библиотека программ LIQA-3. по аппроксимации функцийи цифровой фильтрации: Оперативно-информ. материал. Новосибирск: ВЦ СО АН СССР, 1983 - 162 с.

5. Василенко В.А. Теория сплайн-функций. Новосибирск: НГУ, 1978. - 65 с.

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

7. Василенко В.А., Зюзин М.В., Ковалков А.В. Сплайн-функции и цифровые фильтры. Новосибирск: ВЦ СО АН СССР, 1984.156 с.

8. Гребенников А.И. Метод сплайнов и решение некорректных задач теории приближений. М.: МГУ, 1983. - 208 с.

9. Имамов А. Некоторые вопросы теории сплайнов в гильбертовом пространстве: Автореферат канд. физ.-мат. наук. -Новосибирск, 1977. 8 с.

10. Имамов А. Сплайны в выпуклых множествах. Новосибирск, 1979. - 14 с. - (Препринт / СО АН СССР, ВЦ;.№ 65).

11. Киндерлерер Д., Стампаккья Г. Введение в вариационные неравенства и их приложения. М.: Мир, 1983. - 256 с.

12. Ковалков А.В. Функции Грина и сплайн-аппроксимации в многомерных областях. Новосибирск, 1980. - 21 с. -(Препринт/СО АН СССР, ВЦ; № 70).

13. Ковалков А.В. Об одном алгоритме построения сплайнов с дискретными ограничениями типа неравенств. Новосибирск, 1982. - 15 с. - (Препринт/СО АН СССР, ВЦ; В 385).

14. Ковалков А.В. О приближенном вычислении сплайна с непрерывными ограничениями типа неравенств. В сб.: Вычислительные алгоритмы в задачах математической физики. Новосибирск, 1983, с. 78-86.

15. Ковалков А.В. Об одном алгоритме построения сплайнов с дискретными ограничениями типа неравенств. СЕРДЙКА Българ. математ. спис., 1983, т. 9, с. 417-424.

16. Ковалков А.В. Характеристические свойства изогеометри-ческих сплайн-аппроксимаций. Новосибирск, 1984. - 30с.-(Препринт/СО АН СССР, ВЦ; № ПО).

17. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. М.: Наука, 1976. - 496 с.

18. Лионе Ж.-Л. Некоторые методы решения нелинейных краевых задач. М.: Мир, 1972. - 587 с.

19. Лоран П. Ж. Аппроксимация и оптимизация. - М.: Мир,1975. 496 с.

20. Люстерник Л.А., Соболев В.Н. Элементы функционального анализа. М.: Наука, 1965. - 519 с.

21. Марчук Г.И. Методы вычислительной математики. М.: Наука, 1980. - 534 с.

22. Мирошнеченко В.Л. Интерполяция функций с большими градиентами. В кн.; Методы аппроксимации и интерполяции Материалы Всесоюз.конф. Новосибирск, 1981, с. 98-107.

23. Морозов В.А. 0 приближенном решении операторных уравнений методом сплайнов. Докл. АН СССР, 1971, т. 300,В I, с. 35-38.

24. Павлов Н.Н. Сплайновые методы сглаживания экспериментальных данных: Автореф. канд. физ.-мат. наук. Новосибирск, 1984. - 12 с.

25. Поляк Б.Т. Введение в оптимизацию. М.: Наука, 1983. -384 с.

26. Пшеничный Б.Н., Данилин Ю.М. Численные методы в экспериментальных задачах. М.: Наука, 1975. - 319 с.

27. Тихонов А.Н. и др. Регуляризующие алгоритмы и априорная информация. М.: Наука, 1983. - 198 с.

28. Фаге Д.М. Метод индикатрис в задачах с ограничениями. -М., 1981. 13 с. - (Препринт/ВИНИТИ, АН СССР; В 6).

29. Фаге Д.М. Приближенное решение одной нелинейной задачи, с ограничением душ двумерного эллиптического уравнения. Докл. АН СССР, 1980, т. 255, В 3, с. 531-534.

30. Atteia М. Fonctions-spline definies sur un ensemble eonr-vexe. Numer. Math., 1968, v. 12, p. 192-210.