Методы изогеометрической аппроксимации сплайнами тема автореферата и диссертации по математике, 01.01.07 ВАК РФ
заседании специализированного совета Д 002.10.01 при Вычислительном " ния РАН по адресу: 630090 Новосибирск 90, пр.
С диссертацией можно ознакомиться в читальном зале библиотеки ВЦ СО РАН (630090 Новосибирск 90, пр. академика Лаврентьева, 6) Автореферат разослав Н/ ^ Ц 1997 г.
Ученый секретг специализированною д. ф.- м. н.
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность темы. В настоящее время основным аппаратом автоматизированного геометрического проектирования при описании сложных кривых и поверхностей являются методы сплайн-функций. Вычерчивание кривых н поверхностей по дискретным данным требует наличия методов, которые сохраняли бы геометрические свойства исходных данных. Стандартные методы сплайн-аппроксимации не дают удовлетворительного решения этой задачи. Для получения необходимых геометрических свойств результирующей кривой/поверхности различные авторы вводят в структуру сплайна параметры натяжения с тем, чтобы удовлетворить заданным геометрическим ограничениям (положительность, выпуклость, монотонность, наличие линейных и плоских участков и т.д.). Ключевая идея состоит в построении алгоритмов с автоматическим выбором этих параметров. Диссертация посвящена разработке методов изогеометриче-ской аппроксимации обобщенными сплайнами с автоматическим выбором параметров натяжения.
Целью диссертационной работы являлась разработка сплайно-вых методов построения по дискретным данным кривых и поверхностей сложной формы с сохранением таких изогеометрических характеристик исходных данных как монотонность, выпуклость, наличие прямолинейных и плоских участков, углов п изломов.
Научная новизна. На единой методологической основе аппарата обобщенных сплайнов с натяжением разработан ряд новых методов изогео-метрической аппроксимации сплайнами кривых и поверхностей сложной формы. Характерной особенностью этих методов является автоматический выбор параметров, контролирующих форму сплайновых кривых и поверхностей. Разработаны следующие методы:
1. Метод изогеометрпческой интерполяции обобщенными сплайнами с натяжением, дающий полное решение задачи изогеометрической интерполяции в классе функций С2 для произвольных данных.
2. Прямые и рекуррентные методы построения обобщенных В-сплайнов с натяжением.
3. Методы исследования свойств обобщенных В-сплайнов с натяжением и рядов от них.
4. Методы локальной изогеометрической аппроксимации кривых и поверхностей обобщенными В-сплайнами с натяжением.
5. Разностные методы построения изогеометрических интерполяционных сплайнов с натяжением.
6. Методы построения дискретных В-сплайнов с натяжением и исследования их свойств.
7. Методы монотонизирующей параметризации сплайновых кривых и поверхностей, существенно улучшающие качество результирующей изогеометрической аппроксимации.
Комплексное использование разработанных методов позволяет дать достаточно полное решение задачи изогеометрической аппроксимации для произвольных сеточных данных.
Практическая ценность работы. Вычислительные методы автоматизированного геометрического проектирования на основе изогеометрической аппроксимации сплайнами являются чрезвычайно полезным аппаратом при решении ряда важных прикладных задач. В частности,
такие методы традиционно важны при проектировании самолетных поверхностей, корпусов судов, кузовов автомобилей, сложных деталей двигателей. Из новых областей приложений отметим робототехнику, компьютерное зрение и контроль промышленной продукции, медицинские исследования (программное обеспечение цифрового диагностического оборудования), телевизионные системы высокой разрешающей способности, картографию, индустрию фильмов и т.д.
Достоверность полученных результатов подтверждается апробиро-ванностью используемых математических моделей и численных методов, внутренними методическими исследованиями, сопоставлением с результатами расчетов других авторов. - *
Апробация работы., Материалы диссертации докладывались на международной конференции' "Теория аппроксимации функций" (Киев, 1983 г.), на международной конференций "Вариационно-разностные методы в математической физике" (Москва, 1983 г.), на I, II и III всесоюзных конференциях "Теория аппроксимации и задачи вычислительной математики" (Москва, 1986 г.; Салкт-Петербург, 1989 г.; . Новосибирск, 1991 г.), на всесоюзной конференции "Теоретические основы и конструирование численных алгоритмов для решения задач математической физики" (Москва, 1990 г.), на III и IV всесоюзных конференциях "Проблемы построения сеток для решения задач математической физики" (Екатеринбург, 1990, 1992 гг.), на международной конференции "Численное решение обыкновенных дифференциальных уравнений" (Финлян- . дия, 1990 г.), на II и III международных конференциях "Математические методы в автоматизированном геометрическо.м проектировании" (Норвегия, 1991, 1994 гг.), на международной конференции "Автоматизированное геометрическое проектирование" . (Малайзия, 1994 г.), на международной конференции "Пакеты программ математической физики" (Новосибирск, 1994 г.), на международном семинаре "Многомерная аппроксимация и интерполяция". (Италия, 1995 г., приглашенный доклад), на "Второй международной азиатской математической конференции" (Тай-ланд, 1995 г., приглашенный доклад), на III международной конференции "Кривые и поверхности" (Франция,. 1996 г.),'на VII международной конференции "Математика поверхностей" (Шотландия, 1996 г.), на международном семинаре "Алгебраический анализ" (Тайланд, 1997 г., приглашенный доклад), на семинаре под руководством академика Ю. И. Шохина (Институт вычислительных технологий СО РАН, г. Новосибирск), на семинаре под руководством профессора Ю. С. Завьялова (Институт математики СО РАН., г. Новосибирск), на семинаре под руководством профессора В. П. Ильина (Вычислительный центр СО РАН, г. Новосибирск). По результатам, полученным в диссертации, автор прочел цикл лекций в университетах Флоренции, Милана и Сьены (Италия, ноябрь-декабрь 1996 г.). '
Публикации. Основные результаты диссертации опубликованы в 49 печатных работах. - • .
Структура и объем диссертации. Работа состоит из введения, восьми глав, заключения, списка литературы из 209 наименований и двух приложений. Полный объем диссертации 248 стр., включая 63 рисунка и 11 таблиц.
Во введений обоснованы актуальность и практическая значимость рассматриваемой в диссертации тематики,- представлено современное состояние проблемы, сформулированы цели и задачи диссертации, описано содержание диссертации по главам.
В главе 1 рассмотрены полиномиальные сплайны произвольной степени одной и двух переменных. Дало описание аппарата B-сплайнов с кратными узлами, основных вычислительных алгоритмов на основе В-сплайнов. Рассмотрены интерполяционные задачи Лагранжа и Эрмита для сплайнов, для которых доказаны критерии существования и единственности решения в виде соответствующих ограничений на расположение узлов сплайна по отношению к точкам интерполяции. Экстремальные свойства сплайнов нечетных степеней даются на основе аппарата B-сплайнов. Кратко описаны основные алгоритмы построения сплайнов двух переменных на прямоугольной сетке. Результаты главы 1 служат теоретическим фундаментом для многих развиваемых далее в диссертации методов. Содержание данной главы существенно улучшает и обобщает изложение соответствующего материала монографии 1.
В главе 2 сформулирована задача изогеометрической интерполяции как задача построения функции нужной гладкости, интерполирующей исходные данные и сохраняющей форму этих данных. Поскольку решение задачи изогеометрической интерполяции не единственно, дало определение множества допустимых решений и проведена классификация возможных конфигураций исходных данных, что позволило сформулировать теорему о необходимых и достаточных условиях существования функции с изогеометрией и свести задачу построения такой функции к задаче локальной эрмитовой интерполяции с ограничениями. Последняя задача решается в классе обобщенных кубических сплайнов класса С2 с дополнительными узлами. Дается алгоритм автоматического выбора параметров натяжения, исходя из условий изогеометрии, гарантирующий существование и единственность решения.
Как обычно, будем говорить, что исходные данные монотонно возрастают
, 1 Завьялов Ю. С., Квасов Б. И., Мирошниченко В. Л. Методы сплайн-функций. М.: Наука, 1980, 352 с.
(убывают) на подотрезке п > к, если Л;/ > О (Д,/ < 0) для
? = п. к — 1, и выпуклы вниз (вверх) на [х„, х*,], к > п + 1, если <5;/ > 0 (6;/<0), г = п. Д — 2.
Задачей изогеометрической интерполяции будем называть задачу об отыскании функции S(x) нужной гладкости такой, что S(x,) = /;. г = 0,1, . 2V и S(x) сохраняет форму исходных данных. Последнее означает, что там, где данные монотонно возрастают или монотонно убывают, S(x) должна вести себя таким же образом. Аналогично, на участках выпуклости (вогнутости) исходных данных 5(аг) также должна быть выпуклой (вогнутой).
Очевидно, что решение задачи изогеометрической интерполяции не единственно. Формализуем поэтому класс функций, где будет искаться решение.
Определение 2.1. Множество функций I(V) называется классом функций с изогеометрией, если для любой S(x) € I(V) выполнены условия:
(2) S(xi) = /,, i =0,1. ЛГ;
(4) S"(xi)6J > 0, i — 1,2, . 2V- 1; S"[x)Bjf > 0, х £ [i.-.ii+i], j = г, г -J-1 при > 0; 5(х) имеет не более одной точки перегиба х на интервале (a^x^i) при Sifbi+\f < 0, причем S"(x)6if > 0 для х 6 [xi,x], а количество точек перегиба на интервале i,t1+i) не превосходит числа перемен знака в последовательности bjf. j = i — 1, г, г -f 1.
Следующие утверждения, характеризующие свойства функций с изо-геометрий, доказываются путем простых геометрических рассуждений.
Лемма 2.1. При Дг-_|/Д,/ < 0 для шогсометрпи функции S(x) необходимо, чтобы S'(x.i) = 0.
изогеометрией на отрезке [.т,-_ i , 3',+ t] является прямая, проходящая через точки Р,-,, Р,, Р,+ [.
Следствие 2.1. При b,f = ¿¡+1/ = 0 единственной функцией с изогеометрией на отрезке [х:;_1,х';+1] является прямая, проходящая через точки Р3, j = i- 1,1,2+1,24-2.
Лемма 2.3. Яри 6,f — 0 я < 0 для тога, чтобы 5(x) € /(V),
необходимо выполнение одного из условий:
(2) S'(x) = Д;/, S"(x) = 0 для всех х £ [х;_,, х1+]].
Из леммы 2.4 непосредственно вытекают следующие следствия.
Следствие 2.2. Яри / > 0 и S'(xj) ф , j — г,г + 1 для того,
чтобы S(x) € /(I-7) необходимо выполнение условий
Следствие 2.3. При <5,_i/(5j/ > 0 н <5,/<5г-н / > 0 для изогеометрии S(x) необходимо выполнение неравенств
Лемма 2.5. При 5'(ж,) = 0 для тогеометрпи S(x) необходимо выполнение условий S"(xi)&if > О, S"(xi)&i-if < 0.
Теорема 2.1. Для существования функции с изогеометрией необходимо и достаточно, чтобы не выполнялось условия:
(1) Ai_i/Ai/<0, ф 0, 6,-_зА-/> 0, <5,-1/ = 0, г = 3. N - 1, (2j Ai-i/AJ <0, Д;/^0, ¿, А+2/> 0, ii+i/ = О, г = 1. ЛГ — 3, (3) ¿¡/ ф 0, = г,-+1/ = 0, 6ifSkf >0,k = i-2,i+2, г = 3. .,N-3.
Необходимость этого утверждения доказывается непосредственно на основе лемм 2.1-2.5. Доказательство достаточности состоит в локальном построении функции с изогеометрией 5(ж), интерполирующей произвольные исходные данные, для которых не выполняются условия (1)-(3) теоремы 2.1.
Для построения функции с изогеометрией S(x) достаточно исключить из рассмотрения интервалы линейности S(x) и определить S(x) на произвольном подотрезке [а^, x,+i] для следующих возможных конфигураций данных:
(B) 6if = 0, ¿¿_i/<5;+1/ < 0, 1 < i < N - 1;
(при г = 0, N формально полагаем = 5"(аг,) ).
Введением на прямой, соединяющей точки Р,, P,+i, дополнительной точки перегиба, расширяющей сетку Д, случал (С) сводится к случаю (В). В случаях (А) и (В) задача построения функции с изогеометрией сводится к решению на [а;,-, x^+i] задачи эрмитовой интерполяции по заданным значениям S^ = S^(xj), г = 0,1,2; j = i,i +1 при выполнении условий монотонности и выпуклости -и дополнительных ограничений:
Согласно определению 2.1 должны быть выполнены также следующие соотношения:
Вопрос о локальном построении функции с изогеометрией S(x) решается на основе обобщенных кубических сплайнов с натяжением.
Определение 2.2. Обобщенным кубическим-сплайном с.натяжением с узлами на сетке Д назовем функцию S(x) £ С2[а, Ь] такую, что на каждом подинтервале [xj,x]+i] она имеет вид:
Для решения задачи эрмитовой интерполяции с ограничениями (2.1)-(2.3) на отрезке [х;, х1+1] определяется функция
g/x\ _ f S(x,xi,xn) при /2 5)
1 > \S(x,xn,xi+1) при х e [xiuxi+1],
имеющая вид (2.4) на интервалах [a^Sii], [xu,xi+i] и удовлетворяющая условиям интерполяции и гладкости
5(r)(^) = /jr), S^foj-OH.SWOru+O), т = 0,1,2; j = i,i +1. (2.6)
Выполнение девяти условий (2.6) обеспечивается за счет выбора 8 коэффициентов функции S(x) в (2.5) а также положения узла стыковки хц. Параметры натяжения pj, qj, j = ¿,¿1 определяются затем, исходя из условий изогеометрии. Введем обозначения
Теорема 2.2. При выполнении ограничений
существует единственный обобщенный кубический сплайн с изогеометрп-ей ¿'(я), решающий задачу эрмитовой интерполяции с ограничениями
Алгоритм главы 2 основан на кусочном представлении сплайна и дает решение задачи изогеометрической интерполяции. Однако обычно мы имеем дело с данными, имеющими ограниченную точность. Следовательно, требуются методы построения пзогеомегрическнх аппроксимаций, удовлетворяющих заданному коридору ограничений и наследующих геометрические характеристики исходных данных. В диссертации такие алгоритмы развиты на основе методов локальной аппроксимации обобщенными В-сплайнами с натяжением.
В главе 3 излагаются три новых универсальных метода построения - локальных базисов для обобщенных кубических сплайнов с натяжением. Первый метод использует кусочность структуры В-сплайнов и условие нормализации и позволяет получать явные формулы для таких сплайнов. Второй метод основан на решении системы уравнений, вытекающих из условий гладкости и замыкаемых соотношениями нормализации. Третий метод дает рекуррентные соотношения для построения обобщенных В-сплайнов с натяжением и служит основным аппаратом исследования их качественных свойств. Проведен анализ свойств обобщенных В-сплайнов и рядов из них.
Множество сплайнов, удовлетворяющих определению 2.2, обозначим через . Рассмотрим вопрос о построении базиса из функций с локальными носителями минимальной длины для Так как <Ит(3$) = — 3 (Аг—1) = Л^+З, то для удобства расширим сетку А, дополнив ее точками Xj, ] = -3,-2,-1, N4- 1,Л^-Ь2,ЛГ-ЬЗ такими, что £_3 < < ж-1 < а, Ь < агдг+1 < < £лг+з •
Потребуем, чтобы базисные сплайны В,(х), г = — N+1 обладали свойствами: В/] ) формулу (3.8) можно переписать в виде 5(х) =/(у«) +2/0 + (!/.+1
где квадратные скобки обозначают разделенные разности функции /(х) по значениям аргумента уу , ^ = г — 1, г, г + 1, г + 2.
Следствие 3.1. Полагая в (3.8)
имеем формулу трехточечной локальной аппроксимации, точную на многочленах первой степени.
вариации. Это позволяет доказать следующее утверждение.
Отметим, что согласно (3.9) bj = S(yj) + O(h^), hj = ma.x(hj-i,hj). Отсюда следует квадратичная сходимость контрольного полигона к функции /(аг), как для bj = /(?/,) так п при использовании формулы (3.10).
В главе 4 изучаются обобщенные B-сплайны с натяжением произвольного порядка, являющиеся неотрицательными функциями с носителями минимальной длины, образующими разбиение единицы. Разработаны рекуррентные формулы для вычисления B-сплайнов с натяжением. Исследованы основные свойства обобщенных B-сплайнов с натяжением и рядов от них такие как положительность, монотонность, выпуклость, инвариантность относительно линейных преобразований. Показано, что ряды из обобщенных B-сплайнов обладают свойством уменьшения вариации а системы обобщеных B-сплайнов с натяжением являются слабыми чебышевскими системами. Получены формулы локальной аппроксимации обобщенными B-сплайнами с натяжением.
Пусть на отрезке [а, Ь] задано разбиение А : а = Xq < < ■ ■ • < хn = Ь. Ассоциируем с ним пространство сплайнов S®, сужение которого на подинтервал [x,-,:rI+i], г = 0. N — 1 натянуто на систему линейно независимых функций , n > 1 и всякая функция из имеет гг — 1 непрерывных производных.
Определение 4.1. Обобщенным сплайном с натяжением порядка п назовем функцию S(x) € которая (1) для всех х G [ж,-, , г = 0. N — 1 имеет вид
где Pitn-2 (я) _ долин ом степени п — 2, и
Предполагается, что " монотонные функции аргу-
Рассмотрим задачу построения базиса в пространстве состоящего из функций с локальными носителями минимальной длины. С этой целью расширим сетку Д добавлением точек ж_„ < ••• < х-\ < а, Ь < < ■ •• < хк+п. Так как (Ит^) = (п + 1)ЛГ — п(Л" — 1) = ЛГ + га, то достаточно построить систему линейно независимых сплайнов ,.
3 = -п. — 1 в таких, что В],п(х) >. О для х е и
В^<п(х) = 0 при х $ (х;,Х2+п+1):
Для п > 1 потребуем выполнения условия нормализации
Согласно определению 4.1 базисные сплайны будем искать в виде
хц-1 <х <хл-1+1, I = 1. п-1,
Вид В^<п(х) в (4.3) для х е к = 0, п упрощается в
силу выполнения условий = В^О^+п+х) =0, г = 0. п — 1 и
свойств (4.1) функций Ф]1П(х), .
В силу условий непрерывности многочлены г^); I = 1, • • ■,
п — 1 в (4.3) связаны между собой соотношениями
Р^п-2(х) = Р^-ипМ*) + В^-1\хш) - х>+1у/г\,
Так как в (4.3) многочлены Р^;1П_2(а:) = 0 для I = 0, п, то, применяя повторно формулу (4.4), имеем тождество
1)(х>+1) £ - Х]+1у/г\ ее 0.
Используя разложение полиномов (4.5) по степеням х, приходим к системе п — 1 линейных алгебраических уравнений для определения неизвестных I = 1. п. Для получения единственного решения используется условие нормализации (4.2).
Рассмотрим последовательность В-сплайнов, определяемых рекуррентной формулой
Л,- 1 Jxj + 1 С>+1,к-1
Дифференцируя формулу (4.7), получаем
Теорема 4.1. Рекуррентные формулы (4.6), (4.7) определяют последовательность В-сплайнов вида
В^Чхз + к^У+к^х), х5+к <х< Х^к+1, к0, X ■
Доказательство проводится методом индукции на основе формулы дифференцирования (4.8).
Для вычислений по формулам (4.9) и (4.10) предварительно надо найти величины I = 1. ,к; к = 2. п. Согласно (4.8), . >
/ = 1. к-, к = 2. ,п. В частности, отсюда следует при Bj!l(xj+l) = 1, что
и т.д. Следовательно, чтобы найти необходимые значения производных базисных сплайнов во внутренних узлах их интервалов-носителей, нужно знать величины то есть интегралы от В-сплайнов В^ ^(х), к =
а — . к] к = 1. п — 1.
Доказательство проводится методом индукции на основе интегрирования •формул (4.9) и (4.10).
Для построения базисных сплайнов , к = 2. п применяются
формулы (4.11), (4.12) и находятся величины , о = 1. /,'.
/г = 1. п и /3 = 0. ,п — к, к = 1. ,п — 1.
Сформулируем некоторые свойства вВ-сплайнов, которые в основном аналогичны свойствам полиномиальных В-сплайнов.
Теорема 4.3. Функции В^^(х), к — 1. п имеют следующие свойства:
1. В^к(х) > 0 для х £ (xj,xj+k±l) я =0 при х £ (х^,х^+к+1);
2. сплайн В^ ^(х) имеет к — 1 непрерывных производных;
3. при к >2 Взл(х) — 1 для х £ [«, 6];
для х £ [х^, , .7=0. ТУ - 1, г = 0. ге — 1.
Обозначим через множество сплайнов £(ж) £ Ск
1 [а, Ь] таких, что на каждом подотрезке [.г,, £¿+1], г = 0. N — 1 они образованы линейными комбинациями функций , к = 1. п. Сплайны , з = — к. N — 1, к'= 1. ,п имеют носите-
ли минимальной длины, линейно независимы и образуют базис в 5£*, то есть всякий обобщенный сплайн 3(х) £ , к = 1. ,п пв силу (4.8) его производные до порядка г < к — 1 могут быть однозначно представлены в виде
j=—k+r [ bjjk, 1 = 0, h V -i* .1-12 Г
Если теперь >0, г — 0,1,2, j = —fc + г. Лг — 1, то сплайн 5(х) будет положительной, монотонно возрастающей и выпуклой функцией.
Пусть Z[a i,](/(o;)) - число изолированных нулей функции f(x) на отрезке [а, !>].
Лемма 4.1. Если сплайн 3(х) = г к = 1. ,п не обра-
щается тождественно в нуль ни на каком подотрезкс из [а, 6], то
Обозначим через виррВ^^х) = , к = I. ,п носитель сплайна то есть интервал
Теорема 4.4. Пусть < т-к+1 < ••■ < ^N-1 ,к = 1. п . Тогда
тогда и только тогда, когда
Если условие (4.Т4) выполнено, то £> > 0.
Следующие утверждения непосредственно следуют из теоремы 4.4.
Следствие 4.1. Система обобщенных В-сплайнов ] = —к,
. N — I, к = 1. ,71 является слабой чебышевской системой, то есть для любых т-к < г-к+\ < ••• < т,\'-1 имеем А > 0 и О > 0 если и только если выполнено условие (4.14). Если последнее условие выполнено, то обобщенный сплайн 5(ж) к = 1. п имеет не
более чем Ж + к — 1 изолированных нулей.
Следствие 4.2. Яри выполнении условий теоремы 4.4 решение задачи интерполяции 8, получаемое из линейного пространства 5^ посредством линейного преобразования переменной х = рх + ^, где р ф- 0 и ц -постоянные.
Теорема 4.6. Всякий обобщенный сплайн 5(ж) £ 5^' инвариантен относительно линейного преобразования вещественной оси Л = (—оо, оо).
В силу локальности В-сплайнов на подотрезке [ж,-, , г = О. N—1 представление сплайна Я(х) в виде линейной комбинации В-сплайнов (4.13) для к — п приводится к виду
Теорема 4.7. Представление сплайна 5(e) в форме (4.15) на интервале [xi, Xi+\\, г = 0. N — 1 можно преобразовать к виду
Этот результат является новым даже для полиномиальных сплайнов и доказывается индукцией по п.
Во многих практических задачах исходные данные известны приближенно. Поэтому представляет интерес разработка алгоритмов сглаживания исходных данных в пределах заданного уклонения с одновременным наследованием геометрических особенностей данных.
В главе 5 такал задача изогеометрической аппроксимации формализуется введением понятия класса аппроксимирующих функций с изогеоме-трией. Разработан алгоритм изогеометрической локальной аппроксимации на основе аппарата обобщенных В-сплайнов с натяжением глав 3 и 4. При этом сглаживание осуществляется применением формул локальной аппроксимации с автоматическим выбором параметров натяжения, исходя из условий сохранения свойств выпуклости и монотонности исходных данных. Алгоритм обобщен на случай изогеометрической аппроксимации поверхностей.
Пусть на сетке А : а — х0 < х i <■■■< х = b задан набор интервалов F = , Fi = [Д-(Ti,/i+ £,•], г = 0. ,N, где £¿ > 0 -заданные малые числа. Рассмотрим задачу построения достаточно гладкой функции S(x) £ C2[a,b] такой, что € í¿, г = 0. ,N и S(x) сохраняет форму исходных данных.
Чтобы формализовать эту задачу введем обозначения для интервальных разностей
6¡F = AiF - Ai-iF = [6if - Eit6¡f + Ei), F¿ = e,-_i + e¿,
[oi,a2] - [bi, b2] = [ai — 62,02 — Ьг] > О если только aj > 62-
Будем говорить, что исходные данные монотонно возрастают (убывают) на интервале [хц, хк], К > R, если справедливо неравенство AiF > О (AiF < 0), г = R. К — 1. Данные будем называть выпуклыми вниз (вверх) на [жд^а], К > R + 1 ,если выполняется неравенство ó¡F > 0 (<5¿F < 0), г — fí -f 1,. • • ,А" — 1.
Будем предполагать, что интервалы AiF, 6¡F для всех г не содержат нулей, то есть исходные данные удовлетворяют ограничениям (Д^/)2 > e?, » = 0. JV-1; (¿¿/)2 >E1, i = l. N-l.
Если для значений некоторой функции S(x) имеем 5(ж,) 6 Fi, i =
1. Принимая во внимание ограничения для исходных данных, получаем AiS Aif > 0, i = 0. ,N — 1, 6iS6if> 0, г = 1. .,iV — 1.
Определение 5.1. Множество 1(А,Г) называется классом функций с изогеометрией, если для любой функции 5(ж) £ /(А, Р) выполнены условия:
2. 5(х,-) б К, г = 0. ЛГ;
3. 5(х) монотонна на [ж,-, х,+1], г = 1, —2 при Д,_1/Д1/ > О, - ¿лif&i+lf > 0; Б(х) монотонна на [х0,х\] при Д0/Д1/ > 0 и на
4. S"(xi)¿if > 0,1 = 1. Лг — 1; число перемен знака функции 5"(х) для х € [а, Ь] совпадаег с числом перемен знака в последовательности
Задачей изогеомегпрпческой аппроксимации назовем задачу отыскания функции 5(.х) € /(Д,Р). Решение этой задачи ищется в виде обобщенного кубического сплахша с натяжением определения 2.2, записываемого в виде линейной комбинации обобщенных В-сплайнов (3.7).
Будем рассматривать случай, когда усредненные узлы В-сплайнов ^Л = хг — г,/г,', г = 0. N совпадают с узлами основной сетки Д, то
есть = _1 _1 - = 0, г = 0, . ЛГ и = х0 — г/г0,
= ;сд' -+- л/г V_] , г = 1,2,3. В этом предположении выражение (3.8)
на подотрезке [а,-, преобразуется к виду
5(ж) = 6,- + Д;6(х - х,-) + + (5.1)
где <5уЬ = Дуб - Д |_1 Ь, ] = г, г + 1, Д,-Ь = - . Алгоритм 5.1. Коэффициенты в (5.1) вычисляются по формуле
предполагается выполнение ограничений:
Параметры р;, <7;, г —О. N — 1 находятся из условий изогеоме-трии, сформулированных в определении 5.1, в два этапа. Используя ограничения |Ь; — /¡| < е*, » = 1. ЛГ — 1, которые в силу (5.2) эквивалентны неравенствам
2А?(Л4_! + АО_1¥><(0)М < е» г = 1. ,ЛГ - 1, вначале находим р, и определяем д,_х из условия 2,- = 0. Затем рг, (ц уточняются из ограничений |5(ж;) — < е;, » = 0. АГ. Условия определения 5.1 удовлетворяются путем окончательного выбора параметров Pi, qi, г = 0. N - 1.
Теорема 5.1. При выполнении ограничений (5.3) обобщенный кубический сплайн с натяжением 3(х), построенный по Алгоритму 5.1 локальной аппроксимации, является функцией с изогеометрисй.
Замечание 5.1. При /(х) = 1 и /(ж) = х непосредственной проверкой имеем bi = 1 и Ь< — Х, j — 0. М, ), где /¿у 6 [/¿у - , Л; 4- е^], ] = 0. М,-, г = 0. N и обладающей свойствами сохранения формы исходных данных, можно осуществить обобщением алгоритма 5.1 локальной изогеометричесюш аппроксимации.
Поверхность ищется в виде функции
где обобщенные базисные сплайны с натяжением ВгЫ>) те же, что и-в (3.7). Функции Ь;(и), % = —1. АГ + 1 обобщают формулы-локаль-. ной аппроксимации (5.2) (Алгоритм 5.1), являясь линейными комбинациями одномерных интерполяционных сплайнов с изогеометрией 5'!(м), г — О. Дг главы 2, задающих кривые вдоль сечений и; = -шг, г = 0. N и проходящих через точки (и>, /¿¿), ^ = 0. М,-.
Формально необходимые формулы (Алгоритм 5.2) получаются заменой значений в Алгоритме 5.1 соответственно функциями ¿ = 0,1. Аналогичные изменения осуществляются для краевых условий: S, ] =
1. ,,гс; - 1, г = 0. /V. Шаг 3. Решить N 4- 1 3-диагональных систем (6.13) для , ] = 1. - 1, г = О. ,,ЛГ.
Шаги 2 п 3 могут быть заменены прямым расщеплением системы (6.6) и решением /V + 1 систем с 5-диагональными матрицами.
Вычисления для решения систем (6.12) и (6.13) могут быть проведены использованием многопроцессорной вычислительной системы. Если п,- = п для всех г, то вначале запоминается треугольная факторизация матриц этих систем а затем используются параллельные вычисления.
Оценено расстояние между дискретным и "гладким " сплайнами с натяжением, интерполирующими одно и то же множество данных и удовлетворяющих одним и тем же краевым условиям. Классический гладкий сплайн с натяжением, интерполирующий данные (6.1), является функцией 5, удовлетворяющей условиям (6.2)-(6.5). Получена оценка
I ,=1. >Лг (Pi-A^hi + iPi Г A
где M = (Mx. .,Mjv)t", g = (/о'>/л-ц)Т'> постоянные Л;, Б, и С, являются ограниченными функциями параметра pi a ctj, /3; - элементы матрицы трехдиагональной системы, используемой для построения сплайна 5 и совпадающей с (6.14) при г —► 0.
Согласно (6.15) для всякой фиксированной последовательности значений Po. Pn имеем второй порядок сходимости дискретного сплайна с натяжением к соответствующему гладкому сплайну с натяжением. Эти результаты согласуются с порядком аппроксимации первой, второй и четвертой производных при дискретизации дифференциальной задачи. Ограничение (6.15) позволяет получить оценки скорости сходимости дискретных сплайнов с натяжением к интерполируемой функции при max,- hi —► 0.
В главе 7 рассматриваются обобщенные дискретные сплайны, естественно возникающие при разностной аппроксимации многоточечной краевой задачи, используемой для определения сплайна с натяжением в главе 6. Рассматриваемый подход обобщает результаты для дискретных сплайнов главы 6 и позволяет получить как предельный частный случай основные результаты главы 3.
Пусть на отрезке [а,Ь] задано разбиение Д:а = жо<ж1<---< х,v =6. Для непрерывной функции S(x) положим S, = S(x