Содержание к диссертации
Введение
Глава 1. Трёхдиагональные системы с нестрого якобиевой матрицей 31
1.1. Вводные замечания 32
1.2. Задача о наследовании решением системы линейных уравнений знаковой схемы правой части 34
1.3. Условия неотрицательности решения системы с нестрого якоби-евой матрицей и диагональным преобладанием по строкам или по столбцам 41
Глава 2. Условия изогеометрической интерполяции классическими кубическими сплайнами класса C2 51
2.1. Комонотонность и ковыпуклость при сплайн-интерполяции 53
2.2. Представления сплайнов, приводящие к системам с диагональным преобладанием по столбцам 64
2.3. Условия комонотонной интерполяции кубическими сплайнами 66
Глава 3. Изогеометрическая интерполяция обобщёнными кубическими сплайнами класса C2 76
3.1. Обобщенные нелокальные кубические сплайны 77
3.2. Оптимальность параметров при выпуклой интерполяции 80
3.3. Численная реализация алгоритма выбора управляющих параметров сплайна 87
Заключение 102
Литература 104
- Задача о наследовании решением системы линейных уравнений знаковой схемы правой части
- Комонотонность и ковыпуклость при сплайн-интерполяции
- Условия комонотонной интерполяции кубическими сплайнами
- Численная реализация алгоритма выбора управляющих параметров сплайна
Введение к работе
Актуальность темы. Имеется большое количество интерполяционных задач, в которых важно, чтобы решение обладало такими свойствами как знакопостоянство, монотонность или выпуклость, т.е. сохраняло геометрическую форму данных. Рассматривая задачу построения сплайнов с заданными геометрическими свойствами, А.И. Гребенников (1978) назвал её задачей изогеометрической аппроксимации. Эта терминология в дальнейшем стала использоваться и в задачах интерполяции. Часто, подчёркивая согласованность геометрических свойств интерпо-лянта с данными, интерполяцию называют формосохраняющей (shape-preserving).
Основным аппаратом решения задач интерполяции в настоящее время являются полиномиальные сплайны. В то же время вопросы, связанные с наследованием ими геометрической формы данных порой довольно сложны, изучены далеко не полно и до сих пор актуальны.
Впервые полиномиальные сплайны в качестве самостоятельного объекта исследования появились в работе И. Шёнберга (1946). Первая монография по сплайнам Дж. Алберга, Э. Нильсона, и Дж. Уолша (1967), пе-реведёная в 1972 году Ю.Н. Субботиным под редакцией С.Б. Стечкина послужила толчком к русскоязычному изложению развивающейся теории. В 1976 году вышла книга С.Б. Стечкина и Ю.Н. Субботина, посвя-щённая сплайнам в вычислительной математике. В 80-х годах прошлого века наблюдался пик активности в изложении основ теории сплайнов. Появились монографии Ю.С. Завьялова, Б.И. Квасова и В.Л. Мирошниченко (1980), Л. Шумейкера (1981), В.А. Василенко (1983), А.И. Гребенникова (1983), Н.П. Корнейчука (1984), К. деБора (1979), В.Н. Мало-зёмова и А.Б. Певного (1986). Вышедшие в дальнейшем книги А.И. Ро-женко (1999, 2005) и Б.И. Квасова (2006) систематизировали некоторые новые подходы к теории сплайнов.
Наиболее популярны и востребованы в практических задачах кубические сплайны. Однако присущая им некоторая “жёсткость” может негативно проявляться при изогеометрической интерполяции.
Под задачей формосохраняющей или изогеометрической интерполяции понимается требование, чтобы интерполянт S(x) или какая-либо его производная S(k)(x) были знакопостоянными, если знакопостоянны интерполируемая функция f(x) или, соответственно, её производная f(k)(x). Знакопостоянство k-ой производной f(k)(x) гладкой функции f(x) назы-
вают /^-монотонностью, которая при к = 0,1,2 имеет классические названия: знакопостоянство, монотонность и выпуклость, соответственно.
Для функций, не обладающих свойством /^-монотонности, интерес представляет возможность разбиения области задания на промежутки /с-монотонности, что характеризует свойство кусочной /с-монотонности функции. При этом смена знака производной порядка к характеризует изменение направления /с-монотонности функции.
Геометрические свойства функции /, заданной на отрезке [а, Ъ] дискретно своими значениями fi = fix і) в некоторых точках Хі, образующих сетку
А : а = хо < х\ < ... < хп = 6,
в отсутствие иной информации характеризуются знаками разделённых разностей порядка к, которые для всех возможных і определяются ре-куррентно: д\ = fi, б\ = {6i+l — б\ )/{xi+k — Хі). Такая характеристика обусловлена тем, что для достаточно гладкой функции существует &к Є [Хі,хі+к], такое что к\ б\к] = /(/г)(Ы. Дискретные данные Ш со знакопостоянными разделёнными разностями порядка к также называются /с-монотонными.
Аппроксимацию, согласованную с кусочной /с-монотонностью данных, представляющих заданную на сетке функцию, называют сохраняющей кусочную /с-монотонность или /с-комонотонной.
Данная работа посвящена вопросам интерполяции данных с учетом их /с-монотонности и кусочной /с-монотонности для к = 1,2, т.е. ко-монотонной (к = 1) и ковыпуклой (к = 2) интерполяции сплайнами. В этих случаях первую и вторую разделённые разности принято обозначать f[xi,xi+1] = 5^ и f[xi-UXi,xi+1] = б\% для краткости 5г =
f[Xi-UXi,Xi+1].
Первым обратил внимание на проблему формосохранения (посторонние точки перегиба) при интерполяции кубическим сплайном выпуклых данных и предложил средство устранения этой излишней жёсткости Д. Швейкерт1. Введённые им понятия натяжения и параметров, управляющих им, определили новое направление развития теории сплайнов. Встраивая в структуру сплайна гиперболические функции, он получил конструкцию, которая с увеличением параметра натяжения приближалась к линейному сплайну, гарантирующему выпуклость интерполяции.
lSchweikert D. G. An interpolation curve using a spline in tension // J. Math. Phys. - 1966. -Vol. 45. - P. 312-317.
Предпочитая не сильно уходить от кубического сплайна, во многом идеальной конструкции, К. деБор2 предложил использовать натяжение (напряжённые сплайны) для кусочно полиномиальных интерполяций понижая гладкость функции между узлами сетки введением фиктивных дополнительных узлов.
Все конструкции, в которых так или иначе используются параметры натяжения, принято называть обобщенными сплайнами; они и обозначили один из путей подавления нежелательных осцилляций. Названия функций, внедрённых в структуру, определили и названия таких сплайнов. Г. Шпэт (1969) ввел в обращение понятие рационального сплайна, экспоненциальные сплайны рассматривались в работах С. Пруэса (1979), П. Рентропа (1980), Б. МакКартина (1990). Р. Соанес (1976) предложил конструкцию сплайнов переменной степени (VP-сплайны). Взвешенные сплайны изучали К. Салкаускас (1984), Т. Фоли (1987), В.Л. Мирошниченко (1995), Б.И. Квасов (2013).
Таким образом, в проблеме изогеометрической интерполяции можно выделить две задачи.
Первая касается отыскания условий возможности интерполяции классическими сплайнами, согласованной с кусочной, вообще говоря, k-монотонностью данных. Вторая задача связана непосредственно с построением комонотонной или ковыпуклой интерполяции. Интерес в этой связи представляют методы, допускающие расширение классической конструкции за счёт введения управляющих параметров.
Для локальных методов k-монотонной кубической сплайн-интерполяции класса C1 обе задачи исследованы достаточно полно. Такие условия были установлены теоремами о необходимых и достаточных условиях монотонности3 сплайна или его выпуклости4 на всей области задания. Методы и алгоритмы построения локальных изогеометрических интерполяционных сплайнов, в том числе и основанные на этих условиях, широко представлены в литературе. Этой же теме посвящена работа [5] автора диссертации. В силу локальности конструкции, задачи комоно-тонной или ковыпуклой интерполяции решаются разбиением данных на области монотонности или выпуклости.
2де Бор К. Практическое руководство по сплайнам. — М.: Радио и связь, 1985. — 304 с.
3Fritsch F. N., Carlson R. E. Monotone piecewise cubic interpolation // SIAM J. Numer. Anal. 1980. — V. 17, № 2. — P. 238–246.
4 Schmidt J. W., Hess W. Shape-preserving C2 histopolation // J. Approx.Theory. — 1993. — V. 75. P. 325–345.
В нелокальных методах монотонной и выпуклой интерполяции класса C2 технологии получения априорных условий долгое время не существовало, для проверки будет ли сплайн формосохраняющим фактически требовалось строить сам сплайн. Явные формулы априорной проверки появились с публикацией результатов В.Л. Мирошниченко5. Им и установлены первые достаточные условия монотонности и выпуклости нелокального сплайна. Некоторые достаточные условия рассматривались в работах В.И. Пинчукова. Ю.С. Волков на основе предложенного им нового представления нелокального сплайна через разложение его производной по базису из параболических B-сплайнов получил достаточные условия монотонности, отличные от условий Мирошниченко. Для сплайнов второй степени условия k-монотонности исследовали Ю.С. Волков и В.Т. Шевалдин (2012). В задаче построения нелокальной монотонной или выпуклой кубической сплайн-интерполяции, изначально предлагались методы, основанные на обобщенных конструкциях, в которых выбор параметров натяжения на проблемных участках либо был сильно ограничен за счет фактического уменьшения количества параметров, чтобы не нарушать условия применимости метода, либо носил скорее эвристический характер. Вслед за результатами В.Л. Мирошниченко (1984, 1990) в которых впервые были приведены явные формулы априорной оценки данных с точки зрения формосохраняющей интерполяции, появились и методы автоматического выбора параметров натяжения. А идея Ю.С. Завьялова (1996) заложила возможности гарантированного выбора параметров при построении нелокальной комонотонной или ковыпуклой сплайн-интерполяции.
На начальных этапах исследований в направлении формосохране-ния при интерполяции нелокальными сплайнами комонотонность и ко-выпуклость вообще не обсуждались. Попытка разобраться в этом вопросе предпринималась в работах Ю.С. Завьялова (1997) и автора [1]. Однако вопрос об условиях комонотонности и ковыпуклости нелокальной сплайн интерполяции классическим кубическим сплайном класса C2, ввиду невозможности использования для этих целей традиционного классического представления сплайна и отсутствия в то время других подходящих его представлений, не ставился, хотя задел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. — C.1303–1307.
уже был.
Цель работы. Целью работы является вывод простых, и легко проверяемых априорных условий комонотонности и ковыпуклости нелокальной интерполяции классическими кубическими сплайнами класса C2, а также исследование возможности применения таких условий для разработки алгоритмов построения нелокальных изогеометрических интерполяционных сплайнов с использованием обобщений на основе классического кубического сплайна.
Методы исследования. В рамках исследований по теме представленной работы использовались методы линейной алгебры, математического анализа и вычислительной математики.
Научная новизна. Все основные результаты диссертации являются новыми и получены автором лично.
Основные результаты, выносимые на защиту.
-
Для нового класса трёхдиагональных систем линейных уравнений установлены условия неотрицательности решения, обобщающие условия В.Л. Мирошниченко и Ю.С. Завьялова
-
Установлены условия на исходные данные, при которых классический кубический сплайн класса C2 обладает свойствами комонотонности или ковыпуклости.
-
Рассмотрены обобщения нелокальных кубических сплайнов для решения задачи выпуклой интерполяции. Разработан алгоритм автоматического выбора параметров натяжения, близких к оптимальным.
Теоретическая и практическая ценность. Результаты представленных исследований устанавливают новые свойства классического кубического сплайна, связанные с задачей нелокальной изогеометрической, а именно, комонотонной или ковыпуклой интерполяции, существенно проясняют картину в плане возможностей классического сплайна, позволяют проводить анализ данных и выявлять в них проблемные участки. На основе априорных условий возможно построение алгоритмов автоматического выбора параметров в обобщенных конструкциях кубического сплайна, для гарантированного наследования формы данных при их интерполяции.
Апробация работы. Основные результаты диссертации в целом и отдельные её разделы докладывались на Третьем и Четвёртом Сибирских конгрессах по прикладной и индустриальной математике «ИН-
ПРИМ» (Новосибирск, 1998, 2000), Международной конференции «Теория приближения функций и операторов» (Екатеринбург, 2000), Международной конференции «Геометрия и приложения» (Новосибирск, 2000), Сибирской конференции, посвящённой памяти Ю. С. Завьялова, «Методы сплайн-функций» (Новосибирск, 2001), Международной конференции по вычислительной математике МКВМ-2004 (Новосибирск, 2004), Российской конференции, посвящённой 50-летию ИМ СО РАН (Новосибирск, 2007), Международной конференции «Функциональные методы в теории аппроксимации и теории операторов III» (Киев, 2009), Всероссийской конференции, приуроченной к 80-летию академика С.К. Годунова (Новосибирск, 2009), Российской конференции «Методы сплайн-функций», посвящённой 80-летию со дня рождения Ю.С. Завьялова (Новосибирск, 2011), Всероссийской конференции по вычислительной математике КВМ-2011 (Новосибирск, 2011), Международной конференции по Современному Анализу (Донецк, 2011), Международной конференции «Теория аппроксимации функций и её приложения» (Каменец-Подольский, 2012), а также на научных семинарах отдела численных методов математического анализа Института математики им. С. Л. Соболева СО РАН (рук. к.ф.-м.н. В.Л.Мирошниченко, д.ф.-м.н. С.И.Фадеев), на Школе-семинаре СБ. Стечкина по численному анализу Института математики и механики им. Н. Н. Красовского УрО РАН (рук. академик В.И.Бердышев), на Общеинститутском математическом семинаре Института математики им. С. Л. Соболева СО РАН (рук. академик Ю. Г. Ре-шетняк).
Публикации. Основные результаты по теме диссертации опубликованы в 5 статьях, 3 из которых в журналах из перечня ВАК.
Структура и объем диссертации. Диссертация состоит из введения, трёх глав, заключения и списка литературы из 93 наименований. Объём диссертации 113 страниц, в тексте содержится 15 иллюстраций.
Задача о наследовании решением системы линейных уравнений знаковой схемы правой части
Решение z = (z0,z1 ...,zn)T системы линейных уравнений назовём согласованным с правой частью d = (d0,d1,...,dn)T, если sgnz = sgn d.
Если, например, sgnd 0, то согласованным с правой частью будет решение z 0, называемое неотрицательным.
При решении систем линейных алгебраических уравнений в различных приложениях нередко возникает вопрос, будет ли решение положительным (неотрицательным), если правая часть положительна (неотрицательна). Как уже говорилось, Л. Коллатцем [31] был даже введен класс матриц монотонного вида, таких, что при любой неотрицательной правой части решение системы с такой матрицей неотрицательно. Конечно, решение может оказаться неотрицательным (для некоторой конкретной правой части) и в том случае, когда матрица системы не принадлежит указанному классу. Поэтому естественно и возникает вопрос об описании дополнительных ограничений на правую часть, обеспечивающих неотрицательность решения системы с матрицами из других классов.
Впервые инструментарий для решения задачи в такой постановке для трехдиагональных систем уравнений разработал В.Л. Мирошниченко [76], что позволило ему описать ограничения на правую часть, гарантирующие неотрицательность решения. Это было сделано им для класса трёхдиаго-нальных матриц с неотрицательными элементами и диагональным преобладанием по строкам.
Теорема 1.1 ([76]). Пусть элементы матрицы A и вектора правой части d системы (1.5) неотрицательны, и матрица A имеет строгое диагональным преобладанием по строкам
Тогда решение z будет неотрицательным, если выполнены неравенства
Результат был получен на языке элементарных преобразований системы, приводящих её к пятидиагональной.
К каждому i-му уравнению добавляется линейная комбинация двух соседних уравнений для i = 1,...,n - 1 либо одного соседнего для первого и последнего уравнений так, что из него исключаются неизвестные с индексами i - 1 и i + 1, а для первого и последнего с индексами 1 и n - 1, соответственно. При этом новая система приобретает следующие свойства: 1) является пятидиагональной с нулевыми первыми наддиагона-лью и поддиагональю, 2) элементы второй наддиагонали и второй поддиа-гонали неположительны, 3) имеет диагональное преобладание по строке.
Условия теоремы 0.1 для матрицы системы оказываются выполнеными, и можно заключить, что пятидиагональная матрица является матрицей монотонного вида. В результате достаточные условия неотрицательности решения записываются в виде ограничений на знаки компонент преобразованной правой части системы.
Этот результат в работе [76] носил вспомогательный характер и был сформулирован в виде леммы, за которой в дальнейшем укрепилось название леммы Мирошниченко. Лемма Мирошниченко нашла многочисленные применения, например, в задачах формосохраняющей сплайн-интерполяции [3], [14], [15], [23], [24], [37], [38], [39], [40] и послужила толчком для исследований в этом направлении.
Поскольку анализ систем опирается на диагональное преобладание по строке, то и при построении “хороших” сплайновых систем обычно используется именно свойство строчного диагонального преобладания. При различных обобщениях нелокального классического сплайна, расширяющих его изогеометрические возможности, условия леммы Мирошниченко требуют соблюдать это ограничение, что в свою очередь закладывается, например, в правила задания параметров обобщения и ограничивает их выбор. Другой путь — расширение класса систем, для которых применима идея Мирошниченко.
К таким системам, не обладающим диагональным преобладанием по строкам относятся трёхдиагональные системы, матрицы которых, при некоторой нормировке строк обладают диагональным преобладанием по столбцам и по прежнему не содержат отрицательных элементов. Техника В.Л. Мирошниченко переносится на такие системы [3] или приводящиеся к ним, причем с теми же, установленными в [76] леммой Мирошниченко дополнительными ограничениями на правую часть.
Покажем теперь, что условия Мирошниченко можно распространить на класс матриц с диагональным преобладанием по столбцам.
Теорема 1.2. Пусть элементы матрицы A и вектора правой части d системы (1.5) неотрицательны, и матрица A со строгим диагональным преобладанием по столбцам
Тогда решение z будет неотрицательным, если выполнены неравенства (1.6).
Доказательство. Основная идея доказательства та же, что в [76]: из каждых трёх последовательных уравнений системы с неизвестными zi-2, zi-1, zi, zi+1, zi+2 исключаем zi-1 и zi+1. Каждое уравнение новой системы (кроме крайних) будет содержать также ровно три неизвестных, но только либо с чётными, либо с нечётными индексами.
В [76] установлено, что такое преобразование системы уравнений (1.5) сохраняет диагональное преобладание по строкам. Мы же покажем, что это преобразование, независимо от наличия в системе строкового диагонального преобладания, сохраняет диагональное преобладание по столбцам.
Комонотонность и ковыпуклость при сплайн-интерполяции
В настоящее время основным аппаратом решения подавляющего большинства задач, связанных с практическим приближением функций, стали сплайновые методы. И задачи интерполяции здесь не исключение. При этом наиболее востребованными и используемыми являются кубические сплайны класса С2 — основной и универсальный инструмент — благодаря хорошим аппроксимативным свойствам в сочетании с присущей им простотой реализации на ЭВМ. Однако, всё же эти кубические сплайны не идеальны, и именно в задачах формосохраняющей интерполяции зачастую приходится от них отказываться, поскольку интерполяционный кубический сплайн, вообще говоря, не наследует такие геометрические характеристики как знакопостоянство какой-либо производной исходной функции. Известно, что даже при приближении сколь угодно гладких функций могут возникать нежелательные осцилляции, если исходные данные не достаточно “густые”. Для подобных задач разработаны многочисленные модификации и обобщения кубических сплайнов, но при этом почти всегда в “жертву” приносятся некоторые из достоинств классического сплайна — гладкость, точность, порядок приближения, простота реализации и пр. Однако, если обычный кубический сплайн на каких-либо данных всё-таки обладает требуемыми свойствами, то в этом случае представляется естественным использовать интерполяцию именно классическим сплайном, не обращаясь к обобщениям.
Наша цель определить понятие сохранения кусочной монотонности или кусочной выпуклости данных при интерполяции кубическими сплайнами и выявить условия, при которых интерполяция с сохранением этих свойств данных возможна.
Рассмотрим сначала задачу построения монотонного или выпуклого на отрезке [а, Ь] сплайна S(x) класса С2, интерполирующего заданные в узлах сетки значения функции
Будем требовать, чтобы сплайн S(x) принимал на концах заданные значения производных:
Кубический сплайн на каждом промежутке [хг}хг+1] сетки есть кубический полином, который может быть представлен через значения и вторые производные в концах этого промежутка:
Неизвестные узловые значения МІ вторых производных сплайна находятся из системы линейных уравнений, определяемой условиями гладкости сплайна класса С2. Ясно, что возможные “неприятности” в поведении обычного кубического сплайна возникают из-за слагаемых с функциями ф в (2.6), содержащих кубические многочлены, поскольку а{х) обеспечивает линейную интерполяцию.
Как известно из требования стыковки производной S (xt+0) = S (xt-0) следует, что должны выполняться условия
где di = 65г, Хг = hi/(hi-i + Ы), цг = 1 - Хг. Для получения замкнутой системы уравнений относительно неизвестных {Мг} необходимо добавить два уравнения, вытекающие из краевых условий (2.4) или (2.5). В первом случае добавляемые уравнения таковы:
В задаче выпуклой интерполяции именно система уравнений (2.7),(2.8) относительно моментов МІ с краевыми условиями, отвечающими заданию первой производной в концах отрезка [а, Ь], или система (2.7),(2.9), при задании концевых значений второй производной, удобны для исследования. Действительно, в системе связаны соотношениями узловые значения вторых производных сплайна и набор вторых разделённых разностей функции /, с точностью до числового множителя совпадающего с правой частью системы.
Пусть f(x) выпуклая функция. Очевидно, что на сетке А вторые разделённые разности Si функции f(x) неотрицательны. Тогда для того, чтобы сплайн (2.6), интерполирующий узловые значения f(x) на сетке А с краевыми условиями (2.4) или (2.5) был выпуклым необходимо и достаточно, чтобы все МІ, составляющие решение систем (2.7),(2.8) или, соответственно, (2.7),(2.9) были неотрицательными.
Действительно вторая производная сплайна на каждом промежутке [ЖІ,ЖІ+1] линейна и принимает на концах отрезка (t = 0 и t = 1) значения Мг и Мг+1. Неотрицательность этих значений равносильна неотрицательности второй производной сплайна на всём [а, Ъ].
Таким образом, для того чтобы определить будет ли сплайн выпуклым, надо определить знаки величин М{. Это можно сделать разными способами. Первый заключается в непосредственном решении систем (2.7),(2.8) или (2.7),(2.9). Главный недостаток здесь состоит в том, что численное решение системы, или громоздкость формул явного решения делают невозможным проведение анализа как заданной сетки, так и самой функции с целью выявить по какой причине сплайн оказался не выпуклым.
Другой способ заключается в установлении признаков того, что система с неотрицательной правой частью имеет неотрицательное решение. Собственно, такие условия, достаточные, но довольно широкие и в то же время простые и надёжные в вычислениях, были установлены В.Л. Мирошниченко [76].
Условия комонотонной интерполяции кубическими сплайнами
Исследование свойства комонотонности, как и в рассмотренном выше случае ковыпуклости, особенно привлекательно, когда участки монотонности одного “направления” (возрастания или убывания) содержат достаточно много интервалов сетки. Тогда удается максимально полезно использовать результаты, касающиеся сохранения просто возрастания (убывания) данных, и модифицировать их только на интервалах непосредственно примыкающих к критическим узлам — где меняется направление монотонности.
Теорема 2.4. Пусть в системе уравнений (2.21), определяющей сплайн S{x), выполнены неравенства
Тогда если /3,d, 0, і = 0,..., п + I, то существует единственная точка С Є [х1-иХ1+1] такая, что Доказательство. В силу финитности и неотрицательности Б-сплайнов производная сплайна S(x) в каждой точке х Є [а, хі-і] определена линейной комбинацией
Яcно, что на [а, Ж/_і] U [ж/+ь 6] значения производной 5"(ж) требуемого знака. Известно, что число перемен знака функции S (x) не превосходит чис ла перемен знака в наборе коэффициентов её Б-сплайнового разложения (свойство “уменьшения вариации” [89]). Поэтому S (x) имеет ровно одну перемену знака на [а, Ь], причем именно на [ж/_ьж/+і], что и требовалось доказать. Поскольку носитель Б-сплайна второй степени содержит только три сеточных интервала, и при ж Є [хг-Ъхг] значение производной сплайна определяется только тремя слагаемыми то утверждение легко переносится на случай более одной перемены направления монотонности данных. Действительно, пусть [а, Ь] разбит на промежутки монотонности данных, т.е. если [xi,Xj] такой промежуток, то di+i,... ,dj одного знака, а в узлах Х{ и Xj, характер монотонности меняется 0. Пусть все такие промежутки содержат не менее трех интервалов сетки: j — і 3. Тогда если мы предполагаем совпадение знаковых схем /3 и d, то сплайн S(x), во-первых, сохраняет монотонность данных на [xi+i,Xj-\\. А во-вторых, если [IEJJIEJ], [xj,Xk] два таких промежутка монотонности данных со сменой направления в узле Xj, то на промежутке [XJ-I,XJ+I] направление монотонности сплайна также меняется ровно один раз, в силу того, что при х Є [xj-i,Xj+\\ производная определяется выражением
Заметим, что экстремумы сплайна S{x), вообще говоря, не совпадают с узлами перемены направления монотонности данных, но и не уходят от них далее одного сеточного интервала, что обычно согласуется с поведением функции, представленной этими данными. Тогда очевидно, что если есть промежутки монотонности данных, состоящие из одного или двух интервалов сетки, то рассчитывать на то, что нелокальный классический кубический сплайн класса С2 на всем таком промежутке будет монотонным, вообще говоря, не следует. Однако ясно, что с учетом этого замечания между точками экстремумов направление монотонности данных наследуется.
Рассмотрим теперь задачу о совпадении знаковых схем решения (3 и правой части d. В векторном виде система (2.21) имеет вид причём матрица А - трёхдиагональная, элементы поддиагонали, главной диагонали и наддиагонали её так же как в (1.1) будем обозначать сг}аг}Ъг, соответственно. Все они неотрицательны, и удовлетворяют условиям (1.3) диагонального преобладания по столбцу. Пусть компоненты dt ф 0 вектора правой части d не все одного знака.
Требуется найти условия, при которых знаковые схемы векторов /3 и d совпадают: fydi 0 для всех і.
Покажем какими будут условия комонотонности в случае одной перемены знака в наборе компонент вектора d. Для определенности пусть при некотором 0 I п + 1
Пусть, как и раньше, D = diagjsgnd} — диагональная невырожденная матрица, и пусть матрица G построена по элементам матрицы А в соответствии с правилом (1.22).
Замечание 2.5. Для того чтобы трехдиагональная система (2.23) с неотрицательными элементами, диагональным преобладанием по столбцам аг Ъг_1 + Q+i (полагаем 6_i = сп+2 = 0) и правой частью d, удовлетворяющей условию (2.24), имела решение /3 с той же знаковой схемой, что и вектор d, достаточно, чтобы совпадали знаковые схемы векторов DGDd и d.
Используя полученные в теореме 1.6 условия (1.23), приведём достаточные условия комонотонности сплайна S(x) с граничными условиями (2.20), и производная которого задана равенством (2.19).
Теорема 2.6. Если направление монотонности данных меняется с возрастания на убывание в 1-ом узле (2.22), то кубический сплайн с граничными условиями (2.20) будет комонотонным при выполнении условий
Численная реализация алгоритма выбора управляющих параметров сплайна
Рассмотрим задачу интерполяции на равномерной сетке промежутка [0,1] с шагом 0.1 значений выпуклой функции
Считаем, что в точках x = 0 и x = 1 известны значения первой производной интерполируемой функции.
На рисунках 6 и 7 изображены графики классического кубического сплайна, интерполирующего имеющиеся данные, и его второй производной. Хотя данные являются выпуклыми, сплайн не является выпуклым. Вторая производная в трёх узлах оказывается отрицательной, и сплайн имеет шесть не свойственных данным перегибов. Однако проверка достаточных условий выпуклости показывает, что нарушаются только два из неравенств (3.19) при i = 5 и i = 7.
Для получения выпуклого интерполянта будем использовать обобщённые кубические сплайны, т. е. функцию ф(і) = (t3 - t)/6 в представлении (2.6) заменим функцией ф(р, t), имеющей свободный параметр р, тем самым перейдём к представлению (3.1).
Наиболее известны следующие обобщённые сплайны:
- рациональные (сплайны Шпэта)
Для всех этих обобщённых сплайнов функции ф(р,г) удовлетворяют условиям (3.2), (3.14), и, следовательно, для них справедлива теорема 3.1. Заметим, что гиперболические сплайны (иногда в литературе именно их называют экспоненциальными) обладают вариационным свойством, но для практических вычислений они удобны менее других. Это связано с тем, что из всех предыдущих сплайнов обычный кубический получается при нулевых параметрах натяжения, в то время как для гиперболического просто взять р = 0 мы не можем — надо раскрывать неопределённость. В связи с этим при р, близких к 0, формула для гиперболического сплайна должна быть другой [83], что, естественно, усложняет работу с ним.
Работа нашего алгоритма выбора параметров натяжения для обобщённых сплайнов начинается с определения тех узлов, в которых необходимо натяжение, т.е. с построения множества J. Обратим внимание на то, что на первом этапе работа алгоритма не зависит от конкретного выбора функции ф(р,і). Проверка выполнения неравенств (3.19) показывает, что это множество для рассматриваемого примера должно состоять всего из одного элемента: J = {6}. Следовательно, все параметры pi, , кроме р6 и q6, полагаем равными нулю, ар6и нужно задавать так, чтобы выполнялись неравенства (3.25), с величинами 6 = 0.015 и щ = 0.220, найденными по формулам (3.26), (3.27). В этом случае условия теоремы 3.3 будут выполнены, и обобщённый сплайн получится выпуклым.
Нахождение конкретных значений для р6 и q6, конечно, уже зависит от конкретного выбора функции j (p,t), т.е. вида обобщённого сплайна. Однако для указанных выше видов обобщённых сплайнов с параметрами натяжения, выбранными по нашей методике, графики сплайнов практически не отличаются друг от друга, а графики вторых производных качественно также отличаются мало (кое-какие отличия есть для второй производной гиперболического сплайна). Поэтому мы ограничимся подробным рассмотрением только рационального сплайна Шпэта, а для остальных сплайнов приведём лишь некоторые замечания.
На рисунке 8 изображено семейство линий, описываемых уравнением (3.35) при Хг = їм = 1/2, для значений & = 0.01,0.02,0.1,0.2,0.5. При І = 0.5 кривая проходит через начало координат (при отсутствии натяжения в г-ом узле величины и rji равны 1/2), с уменьшением кривые смещаются вправо и становятся более пологими. Для уравнения (3.36) картина симметрична относительно прямой pi = qi. Кроме того, прямые являются вертикальной и горизонтальной асимптотами соответственно кривых (3.35) и (3.36).
Заметим, что для монотонности нам достаточно было установить следующие неравенства: которые будут выполнены и для остальных, приведённых выше, типов обобщённых сплайнов, кроме гиперболических.
Как было ранее показано, искомая точка пересечения линий границы области может быть найдена как решение более простой системы уравнений (3.33), которая в случае рационального сплайна Шпэта принимает вид а её решение сводится к решению квадратного уравнения и не составляет труда.
В рассматриваемом нами примере параметры натяжения требуется искать только в узле Х6. Здесь 6 = 0.015, щ = 0.220, и вычисления дают щ = 24.467 ид6 = 5.015. Соответствующая область допустимых значений параметров р6 q6 для выпуклости рационального сплайна изображена на рисунке 9 (заключена между кривыми k и l). Точкой A, которая и имеет координаты (24.467, 5.015), обозначено пересечение кривых k и l. Если положить p6 = q6 (биссектриса b), то наименьшие значения этих параметров, попадающие в указанную область (точка B), окажутся существенно больше. Точка B имеет координаты (66.042,66.042). Данное огрубление вычисления параметров рационального сплайна ведёт к излишнему натяжению графика сплайна вблизи 6-го узла. С другой стороны, применение ещё одной, упоминавшейся ранее, упрощенной схемы выбора параметров, а именно, замены кривой l её асимптотой a, наоборот даёт параметры, не сильно отличающиеся от оптимальных. На рисунке 9 это точка C с координатами (27.647, 7.091).
Похожие диссертации на Изогеометрическая интерполяция нелокальными кубическими сплайнами и их обобщениями
