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

ФЕДЕРАЛЬНОЕ АГЕНТСТВО НАУЧНЫХ ОРГАНИЗАЦИЙ ИНСТИТУТ МАТЕМАТИКИ им. С.Л.СОБОЛЕВА СО РАН

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

Богданов Владимир Васильевич

ИЗОГЕОМЕ'ГРИЧЕСКАЯ ИНТЕРПОЛЯЦИЯ НЕЛОКАЛЬНЫМИ КУБИЧЕСКИМИ СПЛАЙНАМИ И ИХ

ОБОБЩЕНИЯМИ

01.01.07- вычислительная математика

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

17 АПР 2014

Новосибирск — 2014

005547254

005547254

Работа выполнена в Федеральном государственном учреждении науки Институте математики им. С. Л. Соболева Сибирского отделения Российской академии наук.

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

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

Субботин Юрий Николаевич, член-корреспондент РАН, доктор физико-математических наук, профессор, ФГБУН Институт математики и механики им. Н. Н. Красовского УрО РАН, главный научный сотрудник

Шумилов Борис Михайлович, доктор физико-математических наук, профессор, ФГБОУ ВПО Томский государственный архитектурно-строительный университет, профессор

Ведущая организация: ФГБУН Институт вычислительной математики и математической геофизики СО РАН

Защита состоится 8 мая 2014 г. в 15 час. на заседании диссертационного совета Д 003.015.04 при Институте математики им. С.Л. Соболева СО РАН по адресу:

630090, г. Новосибирск, проспект Академика Коптюга, 4.

С диссертацией можно ознакомится в библиотеке Института математики им. С. Л. Соболева СО РАН.

Автореферат разослан " марта 2014 г.

Ученый секретарь диссертационного совета кандидат физико-математических наук

В.Л. Мирошниченко

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

Актуальность темы. Имеется большое количество интерполяционных задач, в которых важно, чтобы решение обладало такими свойствами как знакопостоянство, монотонность или выпуклость, т.е. сохраняло геометрическую форму данных. Рассматривая задачу построения сплайнов с заданными геометрическими свойствами, А. И. Гребенников (1978) назвал её задачей изогеометрической аппроксимации. Эта терминология в дальнейшем стала использоваться и в задачах интерполяции. Часто, подчеркивая согласованность геометрических свойств интерпо-лянта с данными, интерполяцию называют формосохрапяющей (shape-preserving).

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

Впервые полиномиальные сплайны в качестве самостоятельного объекта исследования появились в работе И. Шёнберга (1946). Первая монография но сплайнам Дж. Алберга, Э. Нильсона, и Дж. Уолша (1967), пе-реведёная в 1972 году Ю. Н. Субботиным под редакцией С. Б. Стечкина послужила толчком к русскоязычному изложению развивающейся теории. В 1976 году вышла книга С. Б. Стечкина и Ю. Н. Субботина, посвя-щёнпая сплайпам в вычислительной математике. В 80-х годах прошлого века наблюдался пик активности в изложении основ теории сплайнов. Появились монографии Ю. С. Завьялова, Б. И. Квасова и B.JI. Мирошниченко (1980), JI. Шумейкера (1981), В. А. Василенко (1983), А.И. Гребенникова (1983), Н. П. Корнейчука (1984), К. деБора (1979), В.Н. Мало-зёмова и А. Б. Певного (1986). Вышедшие в дальнейшем книги А. И. Ро-женко (1999, 2005) и Б. И. Квасова (2006) систематизировали некоторые новые подходы к теории сплайнов.

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

Под задачей формосохраняющей или изогеометрической интерполяции понимается требование, чтобы интерполянт 5(а;) или какая-либо его производная S^(x) были знакопостоянными, если знакопостоянны интерполируемая функция f(x) или, соответственно, её производная f(k\x). Знакопостоянство fc-ой производной г) гладкой функции f(x) назы-

вают ¿-монотонностью, которая при к = 0,1,2 имеет классические названия: знакопостоянство, монотонность и выпуклость, соответственно.

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

Геометрические свойства функции /, заданной на отрезке [о, b] дискретно своими значениями = f(xi) в некоторых точках Xi, образующих сетку

А : а = хо < xi < ... < хп = Ь,

в отсутствие иной информации характеризуются знаками разделённых разностей порядка к, которые для всех возможных i определяются ре-куррентно: = /¿, ¿р' = (¿[+7^ — ¿Р"1')/(xi+k — щ). Такая характеристика обусловлена тем, что для достаточно гладкой функции существует £.ik S [xi, £(+*,], такое что

к]6(Ь) = /№(f.fc). Дискретные данные {/¿} со знакопостоянными разделёнными разностями порядка к также называются ¿-монотонными.

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

Данная работа посвящена вопросам интерполяции данных с учетом их ¿-монотонности и кусочной ¿-монотонности для к = 1,2. т.е. ко-монотонной (к = 1) и ковыиуклой (к = 2) интерполяции сплайнами. В этих случаях первую и вторую разделённые разности принято обозначать f[xi,xi+1] = и f[xi-i,xi,xi+i] = 5,-ij, для краткости =

f[x%-1, Xi, Xi+i].

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

1Sr.hvip.ikp.rt D. G. An interpolation curve using a spline in tension /'/ Л. Math. Phvs. — 1966. — Vol. 45. — P. 312-317.

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

Все конструкции, в которых так или иначе используются параметры натяжения, принято называть обобщенными сплайнами; они и обозначили один из путей подавления нежелательных осцилляций. Названия функций, внедрённых в структуру, определили и названия таких сплайнов. Г. Шпэт (1969) ввел в обращение понятие рационального сплайна, экспоненциальные сплайны рассматривались в работах С. Пруэса (1979), П. Рентропа (1980), Б. МакКартина (1990). Р. Соанес (1976) предложил конструкцию сплайнов переменной степени (VP-сплайны). Взвешенные сплайны изучали К. Салкаускас (1984), Т. Фоли (1987), В. J1. Мирошниченко (1995), Б. И. Квасов (2013).

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

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

Для локальных методов fc-монотонной кубической сплайн-интерполяции класса С1 обе задачи исследованы достаточно полно. Такие условия были установлены теоремами о необходимых и достаточных условиях монотонности3 сплайна или его выпуклости4 на всей области задания. Методы и алгоритмы построения локальных изогеометрических интерполяционных сплайнов, в том числе и основанные на этих условиях, широко представлены в литературе. Этой же теме посвящена работа [5] автора диссертации. В силу локальности конструкции, задачи комонотонпой или ковыпуклой интерполяции решаются разбиением данных на области монотонности или выпуклости.

2дс Бор К. Практическое рукоподство по сплайнам. — М.: Радио и связь, 1985. — 304 с.

3Fritsch F.N., Carlson R.E. Monotone piecewise cubic interpolation // SIAM .1. Numer. Anal. — 1980. — V. 17, № 2. — P. 238-246.

4 Schmidt J. W., Hess W. Shape-preserving C2 liistopolation // J. Approx.Theory. — 1993. — V. 75. — P. 325-315.

В нелокальных методах монотонной и выпуклой интерполяции класса С2 технологии получения априорных условий долгое время не существовало, для проверки будет ли сплайн формосохраняющим фактически требовалось строить сам сплайн. Явные формулы априорной проверки появились с публикацией результатов B.J1. Мирошниченко5. Им и установлены первые достаточные условия монотонности и выпуклости нелокального сплайна. Некоторые достаточные условия рассматривались в работах В. И. Пинчукова. Ю. С. Волков на основе предложенного им нового представления нелокального сплайна через разложение его производной по базису из параболических .B-сплайнов получил достаточные условия монотонности, отличные от условий Мирошниченко. Для сплайнов второй степени условия /с-монотонности исследовали Ю. С. Волков и В. Т. Шевалдин (2012). В задаче построения нелокальной монотонной или выпуклой кубической сплайн-интерполяции, изначально предлагались методы, основанные на обобщенных конструкциях, в которых выбор параметров натяжения на проблемных участках либо был сильно ограничен за счет фактического уменьшения количества параметров, чтобы не нарушать условия применимости метода, либо носил скорее эвристический характер. Вслед за результатами В. JI. Мирошниченко (1984, 1990) в которых впервые были приведены явные формулы априорной оценки данных с точки зрения формосохраняющей интерполяции, появились и методы автоматического выбора параметров натяжения. А идея Ю.С. Завьялова (1996) заложила возможности гарантированного выбора параметров при построении нелокальной комонотонной или ковыпуклой сплайн-интерполяции.

На начальных этапах исследований в направлении формосохране-ния при интерполяции нелокальными сплайнами комонотонность и ко-выпуклость вообще не обсуждались. Попытка разобраться в этом вопросе предпринималась в работах Ю.С. Завьялова (1997) и автора [1]. Однако вопрос об условиях комонотонности и ковыпуклости нелокальной сплайн интерполяции классическим кубическим сплайном класса С2. ввиду невозможности использования для этих целей традиционного классического представления сплайна и отсутствия в то время других подходящих его представлений, не ставился, хотя задел6 к этому времени

5Мирошниченко В. Л. Convex and monotone spline Interpolation // Constructive theory of function'84. Proc. Int. Conf. Sofia: Publishing House of Bulgarian Academy of Sciences; 1984, P. 610-620.

6 Зааъялов Ю. С. О неотрицательном решении системы уравнений с нестрого якобиевой матрицей // Сиб. матем. журн. — 1996. — Т.37, №6. — С. 1303-1307.

уже был.

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

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

Научная новизна. Все основные результаты диссертации являются новыми и получены автором лично.

Основные результаты, выносимые на защиту.

1. Для нового класса трёхдиагональных систем линейных уравнений установлены условия неотрицательности решения, обобщающие условия В. Л. Мирошниченко и Ю. С. Завьялова

2. Установлены условия на исходные данные, при которых классический кубический сплайн класса С2 обладает свойствами комоиотонности или ковыпуклости.

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

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

Апробация работы. Основные результаты диссертации в целом и отдельные её разделы докладывались на Третьем и Четвёртом Сибирских конгрессах по прикладной и индустриальной математике «ИН-

ПРИМ» (Новосибирск, 1998, 2000), Международной конференции «Теория приближения функций и операторов» (Екатеринбург, 2000), Международной конференции «Геометрия и приложения» (Новосибирск, 2000), Сибирской конференции, посвящёиной памяти Ю. С. Завьялова, «Методы сплайн-функций» (Новосибирск, 2001), Международной конференции по вычислительной математике МКВМ-2004 (Новосибирск, 2004), Российской конференции, посвящённой 50-летию ИМ СО РАН (Новосибирск, 2007), Международной конференции «Функциональные методы в теории аппроксимации и теории операторов III» (Киев, 2009), Всероссийской конференции, приуроченной к 80-летию академика С.К. Годунова (Новосибирск, 2009), Российской конференции «Методы сплайн-функций», посвящённой 80-летию со дня рождения Ю.С. Завьялова (Новосибирск, 2011), Всероссийской конференции по вычислительной математике КВМ-2011 (Новосибирск, 2011), Международной конференции по Современному Анализу (Донецк, 2011), Международной конференции «Теория аппроксимации функций и её приложения» (Каменец-Подольский, 2012), а также на научных семинарах отдела численных методов математического анализа Института математики им. С. Л. Соболева СО РАН (рук. к.ф.-м.н. В.Л.Мирошниченко, д.ф.-м.н. С.И.Фадеев), на Школе-семинаре С. Б. Стечкина по численному анализу Института математики и механики им. Н. Н. Красовского УрО РАН (рук. академик В. И. Бердышев), на Общеинститутском математическом семинаре Института математики им. С. Л. Соболева СО РАН (рук. академик Ю. Г. Ре-шетняк).

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

Структура и объем диссертации. Диссертация состоит из введения, трёх глав, заключения и списка литературы из 93 наименований. Объём диссертации 113 страниц, в тексте содержится 15 иллюстраций.

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

Во введении приводится краткое описание проблематики, даются основные понятия и определения. Объектом исследования является нелокальный кубический сплайна 5(х) класса С2[а,Ь], интерполирующий в узлах сетки Д значения {/,}, который па каждом промежутке можно представить в виде

ад = + + + (1)

где ф{Ь) = (£3 — Ь = (Х-Хг)/^ , 1ц = хш -хи Мг = и произ-

водные которого в концевых точках отрезка [а, Ь) принимают значения известных первых /'п, /'ь, либо, соответственно, вторых /", /" производных функции на концах отрезка:

5'(а) = /а, = Л,

(2)

либо

5"(а) = Г, 5"(Ь) = Л'. (3)

Неизвестные узловые значения вторых производных сплайна А/* называются моментами и находятся из системы линейных уравнений, определяемой условиями гладкости сплайна класса С2:

/ЛМ<_1 + 2Мг + А<М(+1 = г = 1,..., п - 1,

(4)

где А^ = + /г;), /<,: = 1 — А.;, ^ = 65,-, и вытекающими из (2) или,

соответственно, (3) краевыми условиями

2 А/ц + А/1 = ¿о, А/„_1 + 2А/„ = йп

(5)

А/0 = ¿о, А/п = </„, (6)

где ¿о = 6(/[гг0, Ж1] - /а)/(я1 - ж0), йп = 6(Д' - /[хп_ьа;,1])/(а;п- х„_1) в нервом случае и г/о = /", (/„ = /" — во втором.

Первая глава является вспомогательной. В ней получены условия, при которых система линейных алгебраических уравнений Аг = (1 с трёхдиагональной матрицей специального вида и неотрицательной правой частью имеет неотрицательное решение. Этот результат используется для описания условий согласованности знаковых схем вектора решения и вектора правой части для систем с трёхдиагональными матрицами без отрицательных элементов.

Матрица А рассматривается в двух представлениях: традиционном ленточном и блочно-трёхдиагональном:

А =

Ь0

ах

О

\

С, 1-1

Сг}

Ьп-1 ап

( Ао В0 Сг А1 В!

О

\

С,

тп— 1

Ат-1 Ст

Вт-1 Ат

Квадратные диагональные блоки Aj, j = 0различных, вообще говоря, порядков, определяют размерности прямоугольных внедиа-гональных блоков В^ и j = 0,... ,т — 1.

Матрицы, для которых выполняются соотношения с(+^ > 0, г = О,..., п — 1, называют нестрого якобиевыми.

Знаковой схемой sgn V вектора V е Кп+1 с компонентами г^^ будем называть вектор = ... ,8§пг)п)Г (э^я = 1 при х > О, sgna; = — 1 при х < 0, sgna: = 0 при х = 0). Вектор называем неотрицательным V > 0, если все > 0.

Матрицей монотонного вида называется матрица А, для которой из условия Ау > 0 следует V > 0.

Решение системы линейных уравнений Az = сI назовём согласованным с правой частью (I = (с10, (1п)Т, если sgrl z = sgn

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

Теорема 1.2 . Пусть элементы матрицы А и вектора правой части (1 системы Аг = (1 неотрицательны, и матрица А со строгим диагональным преобладанием по столбцам: ап — С\ > 0, о^ — £>,-_ 1 — с»+1 >0, г — 1,..., п — 1, а„ — Ъп-1 > 0. Тогда решение z будет неотрицательным, если выполнены неравенства

¿¿о--- >0,

а\

(¿1--— --— сг,:+1 >0, г = 1,..., п - 1,

Ог-1 йг + 1

<1п--— > 0.

ап-1

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

Лемма 1.4. Пусть система Аг = (1 с матрицей, подчиняющейся условиям теоремы 1.2 имеет правую часть й, компоненты е^ которой отличны от нуля и Г) — diag{sgncí} — диагональная матрица. Для

того чтобы знаковые схемы векторов z и d совпадали, достаточно, чтобы матрица DAD была матрицей монотонного вида.

Таким образом в некоторых случаях удаётся свести задачу об условиях согласованности решения системы с неотрицательной матрицей и знакопеременной правой частью, к задаче об условиях неотрицательности решения системы с неотрицательной правой частью и нестрого яко-биевой матрицей. Решение последней задачи приводится в разделе 1.3.

Теорема 1.5. Пусть трёхдиагоналъная матрица А с диагональным преобладанием по столбцам удовлетворяет условиям > О, г = 0,..., п — 1 и блоки Aj, j = 0,..., т её блочной структуры не содержат вне главной диагонали положительных эле.ментов. Пусть Da = diag(Ao, Ai,..., Ат) — блочно-диагональная матрица, I — единичная матрица и G = 21 — ADд1. Тогда матрица GA является матрицей монотонного вида.

Отметим, что утверждение теоремы 1.5, как показано Ю. С. Завьяловым (1996), верно и в случае диагонального преобладания по строкам.

Свойства матриц монотонного вида позволяют сформулировать следующий результат.

Теорема 1.6. Для того чтобы система уравнений Az — d с матрицей, для которой выполнены условия теоремы 1.5 имела неотрицательное решение z > 0 достаточно, чтобы выполнялось условие Gd > 0.

Результаты главы 1 применяются в главе 2 при изучении задачи изо-геометрической интерполяции классическими кубическими сплайнами.

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

В разделе 2.1 приводятся результаты о монотонности и выпуклости интерполяции классическими С2-сплайнами, даётся постановка задачи комонотонной и ковыпуклой интерполяции.

Под ковыпуклой сплайн-интерполяцией понимается задача построения сплайна S(x), удовлетворяющего условиям:

а) на каждом промежутке [x¿, Xi+k\ выпуклости данных, к > 3 выполняется условие: S"(x)5j > 0 для всех х £ [xj, Xj+1], j = i+1,... ,i + k — 2;

б) если XI — узел перемены направления выпуклости (вверх или вниз) данных, т.е. выполняются условия £¿<5;+1 < 0, то ¿"'(ее) на промежутке {xi,xi+l) меняет знак только один раз.

Теорема 2.2. Пусть на сетке Л вторые разделённые разности <5* функции /(х) не обращаются в нуль. Тогда для того, чтобы сплайн (1) с краевыми условиями (2) или (3) был ковыпуклым необходимо и достаточно, чтобы совпадали знаковые схемы решения и правой части систем (4),(5) или (4),(6), соответственно.

Условия совпадения знаковых схем получаются применением леммы 1.4 и теоремы 1.6. Ковыпуклость на всём отрезке следует из представления (1) и условий (2) или (3).

В частности, если в наборе (а значит и {<5г}) всего одна перемена знака ¿о > 0,..., ф > 0 и ¿¡+1 < 0,..., с?„ < 0, то достаточные условия ковыпуклости сплайна (1) с краевыми условиями (2) или (3) имеют вид

_ _ >0, у = 1,2,

7 , Щ-1 , 2ААг_1А;

1 - а/_2—---й1--1- Щ+х- > 0,

2 иц и>1

Ь - ог;_1у > о,

¿1+1 - < °>

¿1+2 + - ¿1+1 2/Х'+2 - ¿1+з^^ < О,

- ~ - Э = 1 + 3'''''п ~

¿п - ¿п-1 < О,

где 6о = Сп = 1 в случае краевых условий (2) и Ьо = с^ = 0 в случае краевых условий (3).

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

Комонотонной сплайн-интерполяцией называют задачу построения сплайна 5(х), удовлетворяющего условиям:

а) на каждом промежутке [х^х^] монотонности данных, к > 3 выполняется условие: S'(x)f[xj,xj+í] > 0 для всех х 6 [xj,xj+l], ] =

б) если Хг — узел перемены направления монотонности данных, т.е. ВЫПОЛНЯЮТСЯ условия /[х,_ 1,х^/[х1,хг+х\ < 0, /[Хг_2, Хг] > О, /[¡Гг+Ъ Хг+2]/[х1+2, Хг+а] > О, ТО 5"'(х) На промежутке (Хг_1,Хг+1) меняет знак только один раз.

Условия комонотонности сплайна устанавливаются в разделе 2.3. Для этого в разделе 2.2 приведено предложенное Ю. С. Волковым (2002) новое, нетрадиционное, представление 6*2-сплайна, основанное на разложении его производной

п+1

З'^НХ^ВД (7)

по базису Вк, к = 0,..., п + 1, из нормализованных В-сплайнов второй степени с носителями [х^-2,Хк+1\- Сплайн 5(х) полностью определяется параметрами /3 = (Дь ..., /Зп+1). Выполнение интерполяционных условий 5(хг) = /¿, г = 0,..., п, приводит к системе уравнений относительно параметров /3, для однозначного определения которых задаются ещё первая или вторая производные на концах. Тогда система, определяющая сплайн, например с условиями (2), имеет вид:

( А) = Га,

I ^¿-1 О , (1 + + д . п гГ 1-1 (Я\

< -у-А-1 +--з--А + уА+1 = /№-1,г = 1,... ,71, (б)

Аг+1 = Л

Обозначим правую часть

11 = ((¿о, с?ь ..., «г„, й/п+О7 = /[х0, хх],..., /[х„_1, хп], ¡'ь)т.

Ее знаковая схема характеризует монотонность или кусочную монотонность данных.

Теорема 2.4. Пусть в системе уравнений (8), определяющей сплайн 5(х), выполнены неравенства

¿о > 0,..., ¿1 > 0, ¿г+1 < 0,..., сг„+1 < 0. (9)

Тогда если Pidi > 0, i = О, ...,п + 1, то существует единственная точка £ е [xí_i, arj+i] такая, что S'(x) > 0 для х е [а, £], S'(x) < О для

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

Теорема 2.6. Если направление монотонности данных меняется с возрастания на убывание в 1-ом узле (9), то кубический сплайн с граничными условиями (2) будет комонотонным при выполнении условий

di-di-1 Xí~\.--di+г * >0, i = l,...,l-2, (10)

1 + M¿—2 + Ai_i 1 + Mi + A¿+1

<к-г - --+ * + + dl+1&±l > 0, (11)

1 + Mí-3 + A¿_2 Wl wi

di-di-! ^ . >0, (12) 1 + мг-2 + A;-i

d¡+1 - dl+2 Щ+1 < 0, (13)

1 + Mi+i + A/+2

dl+2 + i - - ^t-^V < 0, (14)

Щ Щ 1 + M¡+2 + A¡+3

di - tfr.i ^ Л--di+1 * < 0, i = l + 3,... ,n, (15)

1 + Mi-2 + Ai_i 1 + M¿ + Ai+i

где полагаем M-i = An+i = 1 и w¡ = (1 + Mí-i + A/)(l + М/ + A/+i) — М/А/.

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

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

В разделе 3.1 приведена обобщающая представление (1) конструкция: на каждом интервале [ж*, ¡] сплайн задаётся формулой

S(a:) = а{х)^ф{Яи1-^к2М1 + ф{р,+ъ£)к2М1+ъ (16)

где функция ф(р, t) £ С2[0,1], как функция от t, имеет свободный параметр р для управления поведением сплайна. Из условий интерполяции вытекают ограничения для всех значений р:

ф(р, 0) = ф(р, 1) = ф"(р, 0) = 0, Ф"(р, 1) = 1

(производная берётся по t). Кроме того, должны быть выполнены условия

lim ф(р, t) = (t3 - t)/6, lim ф(р, t) = 0,

р—>0 р—voo

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

ф(р, t) < ф(р, t) при р > р > 0.

Показано, что обобщенный сплайн S(x) с заданными на концах отрезка значениями первой или второй производной существует и единствен, поскольку трёхдиагональная матрица определяющей системы относительно неизвестных Mi, зависящая от полного набора параметров pi, заданных (и, вообще говоря, различных) на каждом интервале сетки, имеет при некоторой допустимой нормировке строк и при дополнительном условии

ф'(р, 0) < 0, ф'(р, 0) + ф'(р, 1) > 0 при р > 0 (17)

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

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

В Заключении перечислены основные результаты работы, представленные к защите. Далее приведён список цитированной литературы, состоящий из 93 наименований.

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

Основные результаты диссертации опубликованы в работах:

1. Богданов В. В. Об алгоритме построения обобщённого сплайна, сохраняющего направления выпуклости данных // Вычислительные системы. — Новосибирск: ИМ СО РАН, 1997. — Вып. 159: Сплайн-функции и их приложения. — С. 72-86.

2. Богданов В. В., Волков Ю. С. Выбор параметров обобщенных кубических сплайнов при выпуклой интерполяции // Сиб. журн. вычисл. математики. - 2006. — Т. 9, № 1. — С. 5-22.

3. Богданов В. В. Достаточные условия комонотонной интерполяции кубическими сплайнами класса С2 // Мат. труды. — 2011. — Т. 14, № 2. — С.3-13.

4. Богданов В. В. Достаточные условия неотрицательности решения системы уравнений с нестрого якобиевой матрицей // Сиб. матем. журн. — 2013. - Т. 54, № 3. - С. 544-550.

5. Завьялов Ю.С., Богданов В.В. Изогеометрическая эрмитова интерполяция обобщёнными кубическими сплайнами // Сплайны и их приложения. — Новосибирск, 1991. — Вып. 142: Вычислительные системы. — С. 15-46.

Богданов Владимир Васильевич

Изогеометрическая интерполяция нелокальными кубическими сплайнами и их обобщениями

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

Подписано в печать 04.03.2014 Формат 60x84 1\16 Усл. печ. л. 1,25 Объем 20 стр. Тираж 100 экз. Заказ №46

Отпечатано Омега Принт 630090, г. Новосибирск, пр. Ак.Лаврентьева,6 email: omegap@yandex.ru

ФЕДЕРАЛЬНОЕ АГЕНТСТВО НАУЧНЫХ ОРГАНИЗАЦИЙ ИНСТИТУТ МАТЕМАТИКИ им. С.Л.СОБОЛЕВА СО РАН

04201457816

На правах рукописи БОГДАНОВ Владимир Васильевич

ИЗОГЕОМЕТРИЧЕСКАЯ ИНТЕРПОЛЯЦИЯ НЕЛОКАЛЬНЫМИ КУБИЧЕСКИМИ СПЛАЙНАМИ И ИХ

ОБОБЩЕНИЯМИ

Специальность 01.01.07 — вычислительная математика

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

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

Новосибирск — 2014

Оглавление

Стр.

Введение.................................. 3

Глава 1. Трёхдиагональные системы с нестрого якобиевой матрицей 31

1.1. Вводные замечания ......................... 32

1.2. Задача о наследовании решением системы линейных уравнений знаковой схемы правой части.................... 34

1.3. Условия неотрицательности решения системы с нестрого якобиевой матрицей и диагональным преобладанием по строкам или

по столбцам.............................. 41

Глава 2. Условия изогеометрической интерполяции классическими кубическими сплайнами класса С2 51

2.1. Комонотонность и ковыпуклость при сплайн-интерполяции . . 53

2.2. Представления сплайнов, приводящие к системам с диагональным преобладанием по столбцам....................................64

2.3. Условия комонотонной интерполяции кубическими сплайнами . 66

Глава 3. Изогеометрическая интерполяция обобщёнными кубическими

сплайнами класса С2 76

3.1. Обобщенные нелокальные кубические сплайны.......... 77

3.2. Оптимальность параметров при выпуклой интерполяции .... 80

3.3. Численная реализация алгоритма выбора управляющих параметров сплайна............................ 87

Заключение 102

Литература

104

Введение

К геометрическим характеристикам функции обычно относят свойства её графика, которые принято называть /с-монотонностью. Для гладкой функции /(х) под ^-монотонностью мы понимаем знакопостоянство к-ой производной (х). В принципе, понятие /с-монотонности можно и не связывать с гладкостью функции, но мы на этом останавливаться не будем. При невысоких значениях к для /с-монотонности есть специальные названия: к = 0 — знакопостоянство, к = 1 — монотонность, к = 2 — выпуклость (вниз или вверх). Иногда /с-монотонность, аналогично, называют /с-выпуклостью. Для функций, не обладающих свойством к-монотонности, интерес представляет возможность разбиения области задания на промежутки /с-монотонности, что характеризует свойство кусочной к-монотонности функции. Смена знака производной порядка к характеризует изменение направления /с-монотонности функции.

Геометрические свойства функции /, заданной на отрезке [а, Ь] дискретно своими значениями /г = /(хг) в некоторых точках хг, образующих сетку

Д : а = хо < XI < ... < хп = 6,

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

г!0) = /., = («Т11 - - *.)•

Такая характеристика обусловлена тем, что для достаточно гладкой функции существует £гк е [хг,хг+к], такое что к\ =

Дискретные данные {/г} с неотрицательными разделёнными разностями порядка к также будем называть /с-монотонными. Очевидно, что если функция / является /с-монотонной, то ^-монотонным является и набор её сеточных значений /г = /(хг), т.е. > 0 для всех возможных г.

Произвольные сеточные данные, не являющиеся /¿-монотонными, характеризуются участками /¿-монотонности, в этом смысле будем говорить о кусочно /¿-монотонных данных. Изменение знака разделённых разностей порядка к на границе участков /¿-монотонности 5< 0 будем называть изменением направления к-монотонности данных.

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

Данная работа посвящена вопросам интерполяции данных с учетом их /¿-монотонности и кусочной /¿-монотонности для к = 1,2, т.е. комо-нотонной (к = 1) и ковыпуклой (к — 2) интерполяции сплайнами. В этих случаях первую и вторую разделённые разности принято обозначать /[жг, Хг+г] = и /¡£¿-1, х^, Х{+\] = <5^, в последнем случае для краткости будем использовать обозначение д{ = /[^-1,^5^+1]-

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

Хотя кусочно гладкие функции используются с незапамятных времён, впервые полиномиальные сплайны, как объект исследования, появились в работе И.Шёнберга [88]. С развитием вычислительных средств теория сплайнов стала развиваться стремительно. Простота, алгоритмичность и открытость для внедрения в сплайновую конструкцию самых разных математических объектов в сочетании с изобилием представлений сплайнов, превратили их в универсальный аппарат решения задач вычислительной математики и теории приближений.

Первая монография по сплайнам Дж. Алберга, Э. Нильсона, и Дж. Уол-ша, появившаяся в 1967 году на английском языке и переведенная в 1972 году Ю. Н. Субботиным под редакцией С. Б. Стечкина [1] послужила толчком к русскоязычному изложению развивающейся теории. И уже в 1976 году

вышла книга С. Б. Стечкина и Ю.Н. Субботина [46], посвящённая сплайнам в вычислительной математике. Чуть позже в монографии Ю. С. Завьялова, Б. И. Квасова и В. Л. Мирошниченко [26] были изложены методы построения, исследования и применения сплайн-функций в численном анализе, причем большое внимание в книге уделено построению алгоритмов, эффективно реализуемых на ЭВМ. В монографии К. деБора [7] акцентируется внимание на важности представления сплайн-функций в виде линейных комбинаций В-сплайнов, предлагается большое число программ на ФОРТРАНе и также рассматриваются те разделы из теории сплайнов, которые полезны при вычислениях.

В монографии Л. Шумейкера [89] рассматриваются алгебраические, аналитические и аппроксимационно-теоретические свойства различных пространств сплайнов. Монография Н. П. Корнейчука [32] посвящена использованию сплайнов в теории приближений. Вариационный подход к теории сплайнов представлен в работах В. А. Василенко [8] и его ученика А. И. Роженко [43], [44], который, кроме того, дал стройное изложение абстрактной теории сплайнов. В монографии А. И. Гребенникова [19] изложены элементы теории сплайнов на основе двух подходов: метода регуляризации Тихонова и определения сплайна как гладко склеенной кусочной функции. В одной из глав книги даны постановка и решение задачи изо-геометрической аппроксимации, т.е. приближения функций с сохранением их геометрических свойств. Методы изогеометрической аппроксимации сплайнами составляют содержание книги [28] Б. И. Квасова.

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

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

Д. Швейкерт в работе [90] обратил внимание на посторонние точки перегиба при интерполяции кубическим сплайном выпуклых данных и предложил средство устранения этой излишней жёсткости. Введённые им понятия натяжения и параметра управления определили новое направление развития теории сплайнов. Введя с структуру сплайна гиперболические функции с параметром, он получил гладкую кусочную конструкцию, которая с увеличением параметра натяжения в пределе давала конструкцию линейного сплайна, гарантирующего выпуклость интерполяции. В монографии К. деВора [7] сплайны с натяжением (напряжённые слайны) строятся на основе экспоненциальных функций с параметром, только уже со своим на каждом интервале сетки; в отличие от сплайна Швейкерта, в котором натяжение применялось ко всему сплайну, даже там, где этого не требовалось. Это дало право говорить о нелокальной конструкции с локальным натяжением. Предпочитая не сильно уходить от кубического сплайна, во многом идеальной конструкции, К. деВор предложил использовать натяжение для кусочно полиномиальных интерполяций понижая гладкость функции между узлами сетки введением фиктивных дополнительных узлов. Г. Шпэт [92] ввел в обращение понятие рационального сплайна, предложив использовать в структуре кубического сплайна рациональную функцию с параметром. Обобщение этой конструкции на более широкий класс функций предложил С. Пруэс [80].

Все конструкции, в которых так или иначе используются параметры натяжения, принято называть обобщенными сплайнами; они и обозначили один из путей подавления нежелательных осцилляций. Названия функций, внедрённых в структуру, определили и названия таких сплайнов. Экспоненциальные сплайны, например, рассматривались в работах С. Пруэса [80], П. Рентропа [83], Г. Шпэта [92], Б. МакКартина [75]. Р. Соанес ввёл в

рассмотрение сплайны переменной степени (УР-сплайны) [91]. Взвешенные сплайны исследовали К. Салкаускас [84], Т. Фоли [68], В. Л. Мирошниченко [39].

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

Ещё один путь — это радикально меняющий картину уход от самой интерполяции в сторону аппроксимации [73], [86], [26], [18], [53], [54], [11]. Интересные результаты получены Ю. Н. Субботиным для параболических сплайнов и их некоторых обобщений [48], [49], [50], и Е. В. Шевалдиной для кубических сплайнов [55]. Особое место занимает вопрос об аппроксимации /с-монотонных данных полиномами (Д. Левиатан, И. А. Шевчук, Г. А. Дзю-бенко, К. Копотун [64], [65], [70]). Однако он носит в основном теоретический характер. Довольно интересное направление могут представлять гибридные методы, сочетающие локальную аппроксимацию и частичную интерполяцию. Но эта тема выходит за рамки представленной работы.

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

Кубический сплайн представляет собой функцию 3(х), являющуюся на каждом сеточном интервале [а^, а^+х] полиномом, степени не выше трёх, причём полиномы соседних интервалов гладко склеены (либо нет) в уз-

лах сетки. Сплайны <5(ж), значения которых во внутренних узлах сетки совпадают Б(х{ — 0) = Б{хг + 0), реализуют на всём отрезке [а, Ь] гладкость С0. Кубические сплайны Б(х) бесконечной гладкости на всём отрезке являются полиномами не более чем 3 степени. Наибольший интерес представляют сплайны максимальной конечной гладкости С2, а также сплайны класса только один раз непрерывно дифференцируемые в узлах. Разность между минимальным возможным порядком гладкости в узлах сетки, не понижающим порядок гладкости между узлами, и минимальным имеющимся порядком гладкости в узлах называется дефектом сплайна.

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

Заметим, что кубические сплайны — это общепризнанное разумное сочетание степени и гладкости с точки зрения точности приближения, порядков сходимости и устойчивости вычислений. Однако упомянутая выше "жёсткость", которая неизбежно преследует нелокальность и повышенную гладкость, вынуждает зачастую жертвовать ими, понижая гладкость до С1 (в узлах сетки). Оправдывая разрывы второй производной, апеллируют к преимуществу локальности С1-сплайнов, которая позволяет управлять формой графика сплайна, меняя его параметры только на тех интервалах, где проявляется неудовлетворительное качество интерполяции. Историю этого вопроса наряду с описанием самих методов можно найти в работах [39], [59], [68], [69], [81], [82]. Некоторые исследователи предпочитают локальные конструкции без понижения общей гладкости С2 — понижают гладкость между узлами, "разрывая" третью производную в некоторых внутренних точках интервалов сетки, и тем самым получая право на дополнительные параметры [28], [81].

Имеется большое количество интерполяционных задач, в которых важ-

но, чтобы решение обладало такими свойствами как знакопостоянство, монотонность или выпуклость, т.е. сохраняло геометрическую форму данных. Задача построения сплайнов с заданными геометрическими свойствами была формализована А. И. Гребенниковым [18], который назвал её задачей изогеометрической аппроксимации. Для построения изогеометрической аппроксимации им предложены методы, основанные на локальной сплайн-аппроксимации. В работе Ю. А Флёрова [51] использовался ещё термин "консервативная интерполяция", который фокусирует внимание на сохранении качественных характеристик исходных данных при интерполяции заданных значений функции.

Часто, подчёркивая согласованность геометрических свойств интерпо-лянта с данными, интерполяцию называют формосохраняющей (shape-preserving) [63], [67], [71], [81].

Под задачей формосохраняющей интерполяции понимается требование, чтобы интерполянт S(x) или какая-либо его производная S^(x) были знакопостоянными на тех участках, на которых знакопостоянны (с тем же знаком) интерполируемая функция f(x) или, соответственно, её производная f{k)(x).

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

Здесь возникают две задачи.

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

ли установлены теоремами о необходимых и достаточных условиях монотонности сплайна [69] или его выпуклости [87] на всей области задания. В нелокальных методах монотонной и выпуклой интерполяции класса С2 для проверки условий приходилось сначала фактически строить сам сплайн. Явные формулы априорной проверки появились с публикацией результатов В. Л. Мирошниченко [76], [37]. Им и установлены первые достаточные условия монотонности и выпуклости нелокального сплайна. Некоторые достаточные условия рассматривались в работах В. И. Пинчукова [41], [42]. Ю. С. Волков для предложенного им нового представления нелокального сплайна через разложение его производной по базису из параболических 5-сплайнов получил достаточные условия монотонности [14], отличные от условий Мирошниченко, пользовавшегося традиционным поинтер-вальным представлением сплайна. Для сплайнов второй степени условия /с-монотонности исследовали Ю. С. Волков и В. Т. Шевалдин [17].

Задача нелокальной интерполяции с ограничениями на знаки производных изучена слабо, поскольку является чрезвычайно сложной. Из публикаций на эту тему следует, что подходы к её решению, в общем-то, отсутствуют. На начальных этапах исследований в направлении формосохра-нения при интерполяции нелокальными сплайнами комонотонность и ко-выпуклость вообще не обсуждалась, хотя уже были известны результаты о существовании неинтерполяционных полиномиальных аппроксимаций с подобными свойствами [77], [72]. Попытка разобраться в этом вопросе предпринималась в работах Ю. С. Завьялова [25] и автора [2]. Однако вопрос об условиях комонотонности и ковыпуклости нелокальной сплайн интерполяции классическим кубическим сплайном класса С2, ввиду невозможности использования для этих целей традиционного классического представления сплайна и отсутствия в то время других подходящих его представлений, не ставился, хотя задел в виде результатов работы [22] к этому времени уже был.

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

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