Методы изогеометрической аппроксимации сплайнами тема автореферата и диссертации по математике, 01.01.07 ВАК РФ
|
Квасов, Борис Ильич
АВТОР
|
||||
|
доктора физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Новосибирск
МЕСТО ЗАЩИТЫ
|
||||
|
1997
ГОД ЗАЩИТЫ
|
|
01.01.07
КОД ВАК РФ
|
||
|
|
||||
Р Г 5 ОД
На правах рукописи
О 2 ИЮН 1997
Квасов Борис Ильич
МЕТОДЫ ИЗОГЕОМЕТРИЧЕСКОЙ АППРОКСИМАЦИИ
СПЛАЙНАМИ
01.01.07 - вычислительная математика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени доктора физико-математических наук
Новосибирск - 1997
Работа выполнена в Институте вычислительных технологий СО РАН (г. Новосибирск)
Официальные оппоненту: д. ф. - м. н., профессор В. Л. Василенко
д.'ф. - м. н., профессор А. Ф. Воеводин д. ф. - м. н., профессор Ю. Е. Воскобшшиков'
Ведущая организация - Институт математики СО РАН (г. Новосибирск)
Защита диссертации состоится ^^ 1997 года в часов, на
заседании специализированного совета Д 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 с дополнительными узлами. Дается алгоритм автоматического выбора параметров натяжения, исходя из условий изогеометрии, гарантирующий существование и единственность решения.
Пусть на плоскости Et2 фиксирована последовательность точек V = {Р,\г = 0,1 ,...,N}, Pi = (), у которых совокупность абсцисс Х{ задает на отрезке [а, Ь] разбиение Д : а = :r0 < Xi < ■ ■ ■ < х^ — Ь. Введем обозначения для первых двух разделенных разностей Д,/ = (/,>i — fi)/h{, Ы = ¿ = 0,l,...,iV-l; 6if =Aif- Ai-if, i = l,2,...,N-l.
Как обычно, будем говорить, что исходные данные монотонно возрастают
, 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) выполнены условия:
(1) S(x) £ C'2[a,b];
(2) S(xi) = /,, i =0,1,...,ЛГ;
(3) S'(x)Aif > 0 при &if fin S'(x) = 0 при A{f = 0 для всех X € [х,, х1+1], i = 0,1,..., N - 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.
Лемма 2.2. При b{f — 0 л > 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),
необходимо выполнение одного из условий:
(1) S'(ii)&-i/> 5"(и) = 0;
(2) S'(x) = Д;/, S"(x) = 0 для всех х £ [х;_,, х1+]].
Лемма 2.4. Пусть ф 0 и S"{xi)S"{x) > 0 при всех х € [21,-2]) 2], 22 € [г,, x-j+i]. Тогда для того, чтобы S(x) £ /(К), необходимо выполнение одного in условий:
(1) S'(zi) <AZS< S'(za) для Sif> 0,
(2) S'(z0 > AZS > S'(z2) для ¿if < 0,
(3) S'(x) = &zS, S"{x) =0.для всех x £[zuz2\, где ДZS = {S(z2) -S(zi))/(z2 - zi).
Из леммы 2.4 непосредственно вытекают следующие следствия.
Следствие 2.2. Яри / > 0 и S'(xj) ф , j — г,г + 1 для того,
чтобы S(x) € /(I-7) необходимо выполнение условий
S'(xi)6if < Aif&if < S'(xHl)6if.
Следствие 2.3. При <5,_i/(5j/ > 0 н <5,/<5г-н / > 0 для изогеометрии S(x) необходимо выполнение неравенств
min(Ai_i/, Д,-/) < < тах(Д,_1/, Д;/).
Лемма 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] для следующих возможных конфигураций данных:
(A) <5?/<5i+1/>0, 0 < г < JV — 1;
(B) 6if = 0, ¿¿_i/<5;+1/ < 0, 1 < i < N - 1;
(C) Sif6i+rf < 0, 1 <i<N-2
(при г = 0, N формально полагаем = 5"(аг,) ).
Введением на прямой, соединяющей точки Р,, P,+i, дополнительной точки перегиба, расширяющей сетку Д, случал (С) сводится к случаю (В). В случаях (А) и (В) задача построения функции с изогеометрией сводится к решению на [а;,-, x^+i] задачи эрмитовой интерполяции по заданным значениям S^ = S^(xj), г = 0,1,2; j = i,i +1 при выполнении условий монотонности и выпуклости -и дополнительных ограничений:
mm(s;, < д,/ < ma^s;, s;+1). (2.1)
Ai/s;> 0, S'j/{S'i+l-S<)>0, j = i,i +1. (2.2)
Согласно определению 2.1 должны быть выполнены также следующие соотношения:
S"(x)S"(xj) > 0, - з = i,i + 1; х £ [xi,'xi+1].- (2.3)
Вопрос о локальном построении функции с изогеометрией S(x) решается на основе обобщенных кубических сплайнов с натяжением.
Определение 2.2. Обобщенным кубическим-сплайном с.натяжением с узлами на сетке Д назовем функцию S(x) £ С2[а, Ь] такую, что на каждом подинтервале [xj,x]+i] она имеет вид:
S(x) = [Sj - *>,(0)А^](1 -t) + [Sj+1 - ФЛl)h)S';^
где t — {х — Xj)/hj и функции tpj(t), Ф:(0 подчинены ограничениям ^г)(1) = ^г)( 0)=0, г = 0,1,2; = =
Предполагается, что 4>"{t), Ф"^) - монотонные функции аргумента t 6 [0,1] и <pj(t) = Vj(pj,t), = <Pj(qj, 1 - t), 0 < pj, qj < oo.
Для решения задачи эрмитовой интерполяции с ограничениями (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 определяются затем, исходя из условий изогеометрии. Введем обозначения
.. ff+i ~ ¿J „ •-• -а.1
' — Т' 5Г> i ~ с/ сг> 3 — г, г + L.
°1+1 ~ '-'¡+1 — °г
Теорема 2.2. При выполнении ограничений
существует единственный обобщенный кубический сплайн с изогеометрп-ей ¿'(я), решающий задачу эрмитовой интерполяции с ограничениями
Алгоритм главы 2 основан на кусочном представлении сплайна и дает решение задачи изогеометрической интерполяции. Однако обычно мы имеем дело с данными, имеющими ограниченную точность. Следовательно, требуются методы построения пзогеомегрическнх аппроксимаций, удовлетворяющих заданному коридору ограничений и наследующих геометрические характеристики исходных данных. В диссертации такие алгоритмы развиты на основе методов локальной аппроксимации обобщенными В-сплайнами с натяжением.
В главе 3 излагаются три новых универсальных метода построения - локальных базисов для обобщенных кубических сплайнов с натяжением. Первый метод использует кусочность структуры В-сплайнов и условие нормализации и позволяет получать явные формулы для таких сплайнов. Второй метод основан на решении системы уравнений, вытекающих из условий гладкости и замыкаемых соотношениями нормализации. Третий метод дает рекуррентные соотношения для построения обобщенных В-сплайнов с натяжением и служит основным аппаратом исследования их качественных свойств. Проведен анализ свойств обобщенных В-сплайнов и рядов из них.
Множество сплайнов, удовлетворяющих определению 2.2, обозначим через . Рассмотрим вопрос о построении базиса из функций с локальными носителями минимальной длины для Так как <Ит(3$) = — 3 (Аг—1) = Л^+З, то для удобства расширим сетку А, дополнив ее точками Xj, ] = -3,-2,-1, N4- 1,Л^-Ь2,ЛГ-ЬЗ такими, что £_3 < < ж-1 < а, Ь < агдг+1 < < £лг+з •
Потребуем, чтобы базисные сплайны В,(х), г = — N+1 обладали свойствами: В{(х) > 0 если % 6 (ж;-2> ж1+2) и Вх(х) = 0 в противном случае,
(2.1)-(2.3).
лч-1
Введем -обозначения
^ = Г = 0,1,
'1
Согласно определению 2.2 базисный сплайн В,(х), отличный от нуля лишь на интервале (а;;_2, £¿+2) 1 должен иметь вид
'Ф,-_2(х)В;,(а;1-_1), х 6 £,_!],
*,■(*)={ (3-2)
Ф1+1(х)В-'(х;+1), X 6 О, ж $ [х,-2,х;+2].
В силу условия нормализации (3.1) для х € [а,-, согласно формуле (3.2) имеем
•+2 ¡+1 1+2 £ В;(-х)=Ф<(х) £ в;.'(х1) + Ф,(х)^В,"(х1+1)
7=1—1 ¿=1—1
- в;'(х;+1)г;+1(х - у,-+1) + - и) = 1.
Отсюда, принимая во внимание линейную независимость функций 1, х\ Фг(х) и Ф;(я), получаем уравнения
¿+1 ¿+2 ]Г = -+1) = о,
3=1-1 ¿=1
я."(*.+1)4нг/Г+1 -= «1г, г = о,1,
из которых, проводя исключение, получаем формулы
*'М-1 ш
, 7 = г — 1, г, г -ь 1,
(3.3)
= (х -У1~\)(х -уО{х
Условия гладкости в (3.2) позволяют записать также тождества
г+1 »-и '
£ ВКх>Ц(х - Ю) = 0 или X] = °> г =
7=1-1 ¿=г—1
Замыкая эту систему с помощью соотношений нормализации (3.1) и проводя исключение, получаем опять формулы (3.3). Введем в рассмотрение сплайны
{Ф"(ж)> XI < х < л^+ь
О, * в противном случае,.
j —i-2, г — 1,г. Сплайны В;>1(г) являются обобщением "функций-крыш" для полиномиальных В-сплайнов.
Используя (я), определим рекуррентно сплайны
^ампИ^, (3.5)
С},к-1= / В^к-\{т)йт, j = г - 2,г - 1, к = 2,3.
Простые вычисления дают = 4+1, ] = г — 2, г — 1, г; с^2 = — г/,+1, = г — 2, г — 1, проясняя геометрический смысл этих величин.
Функции Bjlk(x), к — 2,3 обладают многими из свойств, присущих обычным полиномиальным В-сплайнам.
Теорема 3.1. Функции В]^(х), к = 2,3 обладают следующими свойствами:
1. В^к{х) > 0 для х б (г^жу+^+х) и В^к(х) = 0 для а; £ 1);
2. сплайн непрерывно дифференцируем к — 1 раз;
3. В,#.(х) = 1 для а: 6 [о,Ь], Ф;-(х) = Щ(х) =
для X е [Х;,х^], 3 = 0,..., N - 1 ; 4- З^+г-В^зОс) = г = 0,1 для ж € [а, 6],
Ф^ж) = ^(г/у - у^В^з^х), Фг(ж) = ~ %+1)5у>3(х)
для х 6 , 7 = 0,..., ЛГ - 1.
Дифференцируя (3.5), также имеем
В)\к{х) = ~ к = 2,3. (3.6)
Обозначим через множество сплайнов £ Ск~1[а, Ь] таких, что на каждом подотрезке , г = 0,..., /V — 1 они образованы ли-
нейными комбинациями функций .{1,..., хк~2, Ф^3~к\х), Ф;3-^(а:)}, к = 1,2,3. Нетрудно показать, что сплайны В^^х), ] ~ —к,N — 1, к = 1,2,3 имеют носители минимальной длины, линейно независимы и
образуют базис в пространстве . В частности, с учетом (3.6) всякий обобщенный кубический сплайн 5(х) 6 и его производные до порядка к <2 могут быть единственным образом представлены в виде
N-1
где
Sik\x)= ]Г Ь\к)Виг-к{х) для хеМ, (3.7)
i>J+2, к' = 0, 2-3=L_t к = 1,2.
Cj,3-k I
Если теперь Ь^ > О, к = О,1, 2, j = — 3 -f к,..., N — 1, то сплайн S(x) будет положительной, монотонно возрастающей и выпуклой функцией.
Если величины bj в (3.7) известны, то в силу формулы (3.5) можно записать удобное для вычислений выражение для обобщенного кубического сплайна S(x) на подотрезке [ж,-. хг+1]
S(x) =Ь{+ Д,-Ь(х - у{) + с;Ф;(х) + ci+i$;(x), (3.8)
где Cj = (Ajb - Aj~\b)lz), j .= i, i + 1, Ajb = (bj+l - bj)/(yj+ г - у,).
Формула (3.8) дает возможность также выразить коэффициенты сплайна S(x) в его представлении через В-сплайны (3.7) в виде
ь = . S(Vj) - 5"(^-1)Ф>-1(У;) -.S"(Xj)*i-l(W), Vi < Xj, j S S(yj) - - S"{xi+1)9j(yj), Vi >Xj.
Использование представлений (3.7),(3.8) позволяет указать простой и эффективный способ приближения поточечно заданной , функции /(х).
Теорема 5.2. При bj = }{у3), з = -1,..., Аг + 1 формула (3.8) точна на многочленах первой степени и реализует локальное сглаживание.
При bj = Л}/] ) формулу (3.8) можно переписать в виде 5(х) =/(у«) +2/0 + (!/.+1 ~ У»-1)/[г/«-ьУ.'.У«+1]Ф.-(а;)/г,'
+ (У«+2 аг 6 [х;,Х,-+1], '
где квадратные скобки обозначают разделенные разности функции /(х) по значениям аргумента уу , ^ = г — 1, г, г + 1, г + 2.
Следствие 3.1. Полагая в (3.8)
bj = fj - - (3-10)
zj
имеем формулу трехточечной локальной аппроксимации, точную на многочленах первой степени.
Сплайн S/{x) = ¡{У) )В]{х) обладает свойством уменьшения
вариации. Это позволяет доказать следующее утверждение.
Теорема 3.3. При bj = j{rjj), j = —1,... ,N+1 локально-аппроксимаци-онный сплайн Sj(х) пересекает произвольную прямую не большее число раз, чем это делает функция f(x).
Отметим, что согласно (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 натянуто на систему линейно независимых функций {1,х,..., хп~2, Ф,-,п(а:), Ф,1П(:г)}, n > 1 и всякая функция из имеет гг — 1 непрерывных производных.
Определение 4.1. Обобщенным сплайном с натяжением порядка п назовем функцию S(x) € которая (1) для всех х G [ж,-, , г = 0,..., N — 1 имеет вид
S(x) = Pitn-2(x) + + ^"-'Чг.+ О^пМ,
где Pitn-2 (я) _ долин ом степени п — 2, и
Ф$(г{+1) = ФЦС*0=0, г = О,... ,п — 1,
- »irwo = 1;
(2) Я(х)&Сп-Ца,Ь].
Предполагается, что " монотонные функции аргу-
мента X е [я.^-ц] И Фг,п{х) = рг), Ф.>(а:) = Ф!)П(ж,9;), (0 <
Pi,qi< оо).
Рассмотрим задачу построения базиса в пространстве состоящего из функций с локальными носителями минимальной длины. С этой целью расширим сетку Д добавлением точек ж_„ < ••• < х-\ < а, Ь < < ■ •• < хк+п. Так как (Ит^) = (п + 1)ЛГ — п(Л" — 1) = ЛГ + га, то достаточно построить систему линейно независимых сплайнов ,.
3 = -п,... — 1 в таких, что В],п(х) >. О для х е и
В^<п(х) = 0 при х $ (х;,Х2+п+1):
Для п > 1 потребуем выполнения условия нормализации
ЛГ-1
^ В^п(х) = 1 для х£[а,Ъ].
(4.2) .
3 = -п
(4.3)
Согласно определению 4.1 базисные сплайны будем искать в виде
1,п (.х), Х]<х<х]+1,
хц-1 <х <хл-1+1, I = 1,...,п-1,
Вид В^<п(х) в (4.3) для х е к = 0, п упрощается в
силу выполнения условий = В^О^+п+х) =0, г = 0,..., п — 1 и
свойств (4.1) функций Ф]1П(х), .
В силу условий непрерывности многочлены г^); I = 1, • • ■,
п — 1 в (4.3) связаны между собой соотношениями
Р^п-2(х) = Р^-ипМ*) + В^-1\хш) - х}+1у/г\,
г=0
/ = 1,...,п, (4.4)
где = ~ ФЯс.» .....
Так как в (4.3) многочлены Р^;1П_2(а:) = 0 для I = 0, п, то, применяя повторно формулу (4.4), имеем тождество
£ В{]:~1)(х}+1) £ - Х]+1у/г\ ее 0.
(4.5)
г=1
Используя разложение полиномов (4.5) по степеням х, приходим к системе п — 1 линейных алгебраических уравнений для определения неизвестных I = 1,...,п. Для получения единственного решения используется условие нормализации (4.2).
Пусть
'Ф^Г1^), х^<х<х,+1, Вы(х) = Ф^^г), < х < х3+2, (4-6)
0, х <£
Рассмотрим последовательность В-сплайнов, определяемых рекуррентной формулой
В
(х)= Г ём=1&с[Г- Г
Л,- 1 Jxj + 1 С}+1,к-1
к — 2,... ,п, '(4.7)
где
= / \{т)(1т.
" хз
Дифференцируя формулу (4.7), получаем
В'^к(х) = В^к-1{х)/с5,к-1 - ВН1,к-\(х)/ч+1,к-1, к = 2,...,п. (4.8)
Теорема 4.1. Рекуррентные формулы (4.6), (4.7) определяют последовательность В-сплайнов вида
< х < 1 — \,...,к-1,
В^Чхз + к^У+к^х), х5+к <х< Х^к+1, к0, X ■
ь(п-к)
к — 1,... ,п, где
Г =1 т=п-к '
. - ' • (4-Ю) .
и ^
£ г\г+1>п{х — Х]+1)г~п+к/{г — п + А;)! = О,
1=1 г=п—к
к — 2,... ,п.
Доказательство проводится методом индукции на основе формулы дифференцирования (4.8).
Для вычислений по формулам (4.9) и (4.10) предварительно надо найти величины I = 1,... ,к; к = 2,..., п. Согласно (4.8), . >
/ = 1,..., к-, к = 2,... ,п. В частности, отсюда следует при Bj!l(xj+l) = 1, что
(4.11)
В'м(хН2) = - Г^-, ^(^>2) = - + ——
В'1 з(х,-+з) =
и т.д. Следовательно, чтобы найти необходимые значения производных базисных сплайнов во внутренних узлах их интервалов-носителей, нужно знать величины то есть интегралы от В-сплайнов В^ ^(х), к =
Теорема 4.2. Интегралы с^к = /х'+к+1 В]^{т)с1т от обобщенных базисных сплайнов выражаются формулой
п-2
(г) {х^а - 3?д-ц)
г—п+/с-|-1
Ег>{к-1), ч (г) 1
(4+0 (г_„ + Ь+1)! ' (4 12)
1=1 г=п—к—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];
- ----1 - ----1
■ф1>(*) = ( П 'сМ,п-г(х), = П
для х £ [х^, , .7=0,..., ТУ - 1, г = 0,..., ге — 1.
Обозначим через множество сплайнов £(ж) £ Ск~1 [а, Ь] таких, что на каждом подотрезке [.г,, £¿+1], г = 0,..., N — 1 они образованы линейными комбинациями функций {1,... ,х1с~2,ф\п~к\х), Ф;П-*^(х)}, к = 1,..., п. Сплайны , з = — к,..., N — 1, к'= 1,... ,п имеют носите-
ли минимальной длины, линейно независимы и образуют базис в 5£*, то есть всякий обобщенный сплайн 3(х) £ , к = 1,... ,п пв силу (4.8) его производные до порядка г < к — 1 могут быть однозначно представлены в виде
N-1
= ь{йВз>к~г(х) Для *е[а,Ь], (4.13)
где
х
j=—k+r [ bjjk, 1 = 0, h V -i* .1-12 Г
Л cLk_i ' i, z,..., / .
Если теперь >0, г — 0,1,2, j = —fc + г,..., Лг — 1, то сплайн 5(х) будет положительной, монотонно возрастающей и выпуклой функцией.
Пусть Z[a i,](/(o;)) - число изолированных нулей функции f(x) на отрезке [а, !>].
Лемма 4.1. Если сплайн 3(х) = г к = 1,... ,п не обра-
щается тождественно в нуль ни на каком подотрезкс из [а, 6], то
Обозначим через виррВ^^х) = {х ) Вуд(х) ^ 0}, к = I,... ,п носитель сплайна то есть интервал
Теорема 4.4. Пусть < т-к+1 < ••■ < ^N-1 ,к = 1,..., п . Тогда
0=<1еЦВ,,к(!п))ф 0, {¿ = -к,..., N-1
тогда и только тогда, когда
ту £ вирр В],к{х), у - -к,... + 1. (4-14)
Если условие (4.Т4) выполнено, то £> > 0.
Следующие утверждения непосредственно следуют из теоремы 4.4.
Следствие 4.1. Система обобщенных В-сплайнов ] = —к,
..., N — I, к = 1,... ,71 является слабой чебышевской системой, то есть для любых т-к < г-к+\ < ••• < т,\'-1 имеем А > 0 и О > 0 если и только если выполнено условие (4.14). Если последнее условие выполнено, то обобщенный сплайн 5(ж) к = 1,...,п имеет не
более чем Ж + к — 1 изолированных нулей.
Следствие 4.2. Яри выполнении условий теоремы 4.4 решение задачи интерполяции 8{т{) = г — —к,... — 1, /; € М существует и единственно.
Следствие 4.3. Для произвольных целых чисел —к < < ... < щ-к-1 < N — 1 и < Т-1С+1 < • • • < Т1-к-\, к = 1,..., п имеем
А = ¿е^В^ту)} > 0, 1,] = -к,...,1-к-\
и £>( > 0 если и только если т.,- е вирр , ^ = —к,... ,1 - к - 1,
то есть матрица {В^аДт;)}, = —к,..., N — 1 является положительно определенной.
Обозначим через б- (у) число изменений знака в последовательности компонент вектора V. = (и], • ■ •, ?;„) без учета нулей. Для ограниченной вещественной функции /(ж) пусть 5~(/) = 5_(/(х)) - число изменений знака функции /(г) на вещественной оси И без учета нулей
Я"(/(а)) =8ир5-[/(т1),...,/(г„)], п <т2<...<тп.
П
Теорема 4.5. Сплайн 8(х) = 5^1-л: ^'Л-Д».*^1) > к = 1 является
функцией, уменьшающей вариацию, т.е. число перемен знака Б(х) не превосходит числа перемен знака в последовательности его коэффициентов
Щ £ <5"(Ь), ь = (Ь-к,к,...,ЬК-1,к).
Пусть 5^ - множество обобщенных сплайнов на сетке Д = {£; | .т,- = рт,- -Ь ч,} = 0,..., ./V}, получаемое из линейного пространства 5^ посредством линейного преобразования переменной х = рх + ^, где р ф- 0 и ц -постоянные.
Теорема 4.6. Всякий обобщенный сплайн 5(ж) £ 5^' инвариантен относительно линейного преобразования вещественной оси Л = (—оо, оо).
В силу локальности В-сплайнов на подотрезке [ж,-, , г = О,..., N—1 представление сплайна Я(х) в виде линейной комбинации В-сплайнов (4.13) для к — п приводится к виду
j=i — n
Теорема 4.7. Представление сплайна 5(e) в форме (4.15) на интервале [xi, Xi+\\, г = 0,..., N — 1 можно преобразовать к виду
где
fc=0
<Зг,п-2(ж)М_1Д, fc=0,
n—2
k= 1,2,..., n — 2,
г=о
= -i = Ь(0)=Ь.Я1 .....,
Cj.n — k
Этот результат является новым даже для полиномиальных сплайнов и доказывается индукцией по п.
Во многих практических задачах исходные данные известны приближенно. Поэтому представляет интерес разработка алгоритмов сглаживания исходных данных в пределах заданного уклонения с одновременным наследованием геометрических особенностей данных.
В главе 5 такал задача изогеометрической аппроксимации формализуется введением понятия класса аппроксимирующих функций с изогеоме-трией. Разработан алгоритм изогеометрической локальной аппроксимации на основе аппарата обобщенных В-сплайнов с натяжением глав 3 и 4. При этом сглаживание осуществляется применением формул локальной аппроксимации с автоматическим выбором параметров натяжения, исходя из условий сохранения свойств выпуклости и монотонности исходных данных. Алгоритм обобщен на случай изогеометрической аппроксимации поверхностей.
Пусть на сетке А : а — х0 < х i <■■■< х = b задан набор интервалов F = {í;|» =0,...,JV}, Fi = [Д-(Ti,/i+ £,•], г = 0,... ,N, где £¿ > 0 -заданные малые числа. Рассмотрим задачу построения достаточно гладкой функции S(x) £ C2[a,b] такой, что € í¿, г = 0,... ,N и S(x) сохраняет форму исходных данных.
Чтобы формализовать эту задачу введем обозначения для интервальных разностей
Д = h~l{Fi+1 - Fi) = [Д if - a, A if + a), e¿ = h~\ei + ei+l),
i =0,...,N- 1,
6¡F = AiF - Ai-iF = [6if - Eit6¡f + Ei), F¿ = e,-_i + e¿,
i = 1,...,N~1,
[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 =
0....,N, то A{S € AiF,. i = 0,...,N - 1, 6¡S G Ó;F, i = 1 ,...,N -
1. Принимая во внимание ограничения для исходных данных, получаем AiS Aif > 0, i = 0,... ,N — 1, 6iS6if> 0, г = 1,.. .,iV — 1.
Определение 5.1. Множество 1(А,Г) называется классом функций с изогеометрией, если для любой функции 5(ж) £ /(А, Р) выполнены условия:
1. 5(х) еС2М];
2. 5(х,-) б К, г = 0,..., ЛГ;
3. 5(х) монотонна на [ж,-, х,+1], г = 1, —2 при Д,_1/Д1/ > О, - ¿лif&i+lf > 0; Б(х) монотонна на [х0,х\] при Д0/Д1/ > 0 и на
[х,\г_ь при Дд!—2/Дл!—1 / > 0; 5'(ж) имеет перемену знака на [х{-1,х{-1г1], х — 1,...,;V — I при Д;_х/Д;/ < 0; число перемен знака функции 5'(х) на [а, 6] совпадает с числом перемен знака в последовательности Д0/, Дх/,..., Ддг-1/,'
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) вычисляются по формуле
Ь,- = /,--2Л?(А,-_1+Л|-Г1^(0)г,-/, « = 1.....ЛГ- 1. (5.2)
Для нахождения коэффициентов Ь{ при г = —1,0, /V, Д,г + 1 используются краевые условия: = /¡к\ г = О, IV, к = 0,1, для которых
предполагается выполнение ограничений:
«1/(Ло/-Л)> 1^/Мо1, /оАо/>0,
Параметры р;, <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 и Ь{ — Х{, i = N + 1 и, следовательно, согласно (5.1)
изогеометрический сплайн 8(х) восстанавливает прямые линии.
Пусть область <3 : [с, х [0,1] С \У11 разбивается прямыми w = Wi, г = 0,..., N сетки Д№ : с = ад о < «>1 < ■ • • < 1«л = <1 на Лг прямоугольных подобластей. Предположим, что на каждой из прямых ад = и); задана сетка Дц : 0 = и'0 < и\ < ■ • • < и'м. = 1, I = 0,1,..., N. Число узлов и их положение для сеток Д^, г = 0,..., N не зависят друг от друга. В узлах и}, j — 0,..., М{, г = 0,..., Лг заданы значения /¿у некоторой функции /(«;, и) с допустимыми уклонениями .
Построение поверхности класса С2,2(б), проходящей через точки =(«;,■, ы}, ), где /¿у 6 [/¿у - , Л; 4- е^], ] = 0,..., М,-, г = 0,..., N и обладающей свойствами сохранения формы исходных данных, можно осуществить обобщением алгоритма 5.1 локальной изогеометричесюш аппроксимации.
Поверхность ищется в виде функции
N+1
.(5.4)
¿=-1
где обобщенные базисные сплайны с натяжением ВгЫ>) те же, что и-в (3.7). Функции Ь;(и), % = —1,..., АГ + 1 обобщают формулы-локаль-. ной аппроксимации (5.2) (Алгоритм 5.1), являясь линейными комбинациями одномерных интерполяционных сплайнов с изогеометрией 5'!(м), г — О,..., Дг главы 2, задающих кривые вдоль сечений и; = -шг, г = 0,..., N и проходящих через точки (и}, /¿¿), ^ = 0,..., М,-.
Формально необходимые формулы (Алгоритм 5.2) получаются заменой значений в Алгоритме 5.1 соответственно функциями ¿ = 0,1. Аналогичные изменения осуществляются для краевых условий: S{wi,u) = 5,-(и), = £,(«)> г — 0,/V при рДи) = ^/(шг,и).
Алгоритм 5.2. Коэффициенты в (5.4) находятся по формулам:
Ь,-(и) = ЗД - 2А?(Л^1 4г = 1,...,ЛГ-1,
где
¿¡5(и) = Д;5(и) - Д<_15(и), Дл-5(и) = [5лЧ1(«) - 5,-(«)]/Л,-, 1,«.
Аппроксимирующий сплайн и) обладает следующими свойствами сохранения формы исходных данных.
5.5)
Свойство 5.1. Пусть функции Б ¡(и), 2 = г — 1,..., г + 2, 1 < г < И— 1 монотонны и/шпг выпуклы на отрезке [?1т,йгп+1] и удовлетворяют условиям
(и)6^(и) < о, ¿^о,^, ^'(ц)^'(«) < 0, ¿ = 0,^,
где соответственно к = 1 а/или к — 2. Тогда построенный по алгоритму 5.2 обобщенный сплайн 3(и),и) при всяком фиксированном й> € [и^, , 2 < г < N — 3 будет на [ит, •йгл+1] монотонным л/пли выпуклым.
Свойство 5.2. Пусть для любых 5,(гг) таких, что Д,5(г/), <5,5(к) яе меняют знак для всех и £ [0,1], выбор параметров р,, qi, г = —2,..., ЛГ+2 обобщенного сплайна и) обеспечивает оценку
• -< ад, j = о,..., ы,
где Е3(и) - заданные функции. Тогда при любом фиксированном и сплайн ЯН =■ 3(ги,и) является функцией с изогеометряей.
Построение неоднозначной изогеометрической поверхности, заданной поточечно в виде семейства, вообще говоря, криволинейных непересекающихся сечений, осуществляется с помощью введения стандартной параметризации
' ж=5х(ш,и), у = Я" (ад, и), г = 5г(№,и).' (5.6)
Считается, что исходные точки Т^ = {х^^у^, j = 0 ,...,М{, г = 0, ...,ЛГ, принадлежат параллелепипеду [],_, = {Хи'НХи _ ХО'1 < е^}, где полагается хо' = Ч?) Для каждой из координатных функций
(5.6), а - допустимая погрешность по соответствующей переменной. Результирующая поверхность будет получена как тройка изогеометриче-ских сплайнов, построенных по алгоритму 5.2.
В главе 6 интерполяционные сплайны определяются как решения многоточечных дифференциальных краевых задач. Изложение проведено на примере гиперболических сплайнов с натяжением. Трудности работы с такими сплайнами привели к тому, что они фактически были вытеснены рациональными сплайнами. Развитый в этой главе разностный метод построения сплайнов с натяжением позволяет фактически обойтись без вычисления гиперболических функций, делая дискретные сплайны с натяжением весьма эффективным средством решения задач изогеометрической интерполяции.
Пусть известны данные
1=0,...,N+1, (6.1)
где а = х0 < X} < .,., х = Ь. Положим А; = х;+1 — х;, г = 0,..., N.
Интерполяционный сплайн с натяжением со множеством параметров натяжения {/)г > 0 | г = 0,..., А7} является решением многоточечной краевой задачи
5бС2[ а,Ь], (6.3) с интерполяционными условиями
5(®0 = /й ¿=0,...,^+1 (6.4) и граничными данными
= 8"{Ь) — (6.5)
Для практических целей часто достаточно знать проекцию решения задачи (6.2)-(6.5) на заданную сетку отрезка [а, 2>] и не обязательно иметь для решения аналитическое выражение. .В данной главе не ставится задача нахождения сеточной проекции решения 5 задачи (6.2)^(6.5). Вместо этого рассматривается естественная дискретизация этой задачи. Доказывается, что дискретная задача имеет единственное решение, называемое сеточным решением, и изучаются его свойства. Конечно, это ведет к тому, что сеточное решение не является проекцией 5 но оно может быть продолжено на [а,Ь\ как функция и(х), свойства которой весьма сходны со свойствами 5 и которая стремится к 5' при уменьшении шага дискретизации к нулю. В силу этих свойств мы называем и(х) дискретным интерполяционным сплайном с натяжением.
Предположим, что каждый шаг сетки /г, является целочисленным кратным шага г некоторой "мелкой" равномерной сетки на [а, 6]. Полагая п{ — кг/г,. будем искать сеточную функцию й = | = 0,..., п;, г = 0,..., АГ}, удовлетворяющую разностным уравнениям:
. [Л2- з = 1,...,гг;-1, г = 0,'...,]У, (6.6)
где -
_ Цг,.7-1 ~ 2цМ
Условия гладкости (6.3) заменяются на уравнения
2 Г
2т—г = 1,...,ЛГ, (6.7)
= Ли;, о,
эквивалентные соотношениям
«.-Mi-.+j = uíj, j = -1,0,1. (6.8) Условия интерполяции (6.4) дают нам
«¿,0 = fi, Wí,n¡=/¡+i> ¿ = 0,...,iV (6.9) а для граничных данных (6.5) имеем
Au0,0 = /о , Auíí,„„ = (6.10)
Равенства (6.8) позволяют исключить "лишние" неизвестные в разностных уравнениях (6.6). Неизвестные щ,о, « = 0, ...,N+ 1 находятся непосредственно из интерполяционных условий (6.9) a «0>_i и « .vjUjV+1 исключаются с помощью краевых условий (6.10). Затем на практике мы имеем дело с т* х т* линейной системой (та* = щ — N — 1)
А'и*=.Ъ\ (6.11)
где 5-диагональная матрица А* является симметрической и положительно определенной и, следовательно, решение системы (6.11) существует и единственно. .
Для числа обусловленности Ц2(А*) в спектральной норме матрицы А* имеем следующую оценку сверху, не зависящую от числа точек исходных данных N + 2:
шах,-[16 + 4(^)2]
В силу структуры матрицы А* линейная система (6.11) может быть эффективно решена прямым методом для ленточных матриц. Так как А* - положительная ленточная матрица с шириной ленты 2, то классическое разложение Холесского А* =
LLT дает нижнюю треугольную матрицу L с лентой 2 и может быть реализовано за О(2гп*) операций.
При использовании обозначения M¡j = Au¡j, j = 0,... ,п,, i = 0,..., N на интервале [ж,-, a:¿+i] 5-диагональная система (6.6) может быть переписана в виде двух 3-диагональных систем
Mi0 = Mi,
M^-2Mj+Mij+1 _ =Q j = v ;n¡ _ ^ (6 12)
Mitm = Mi+1,
где Мг и Мг+1 - заданные числа, и
«ю = /,,
= (6.13)
«!>, = /¿+1-
Функция
М;(х) = /¡(1 - 0 + + <¿¡(1 - t)h?M¡ + <М*)Ь?М;+1,
где
. . . апЬ(А:,-<) - г япЬ^,-) .г - я,- 2 А,-г,- „ г
<М<) =- 2 ■ и, N 1 = ~Е—> -ятЬ— =р;>0, т,- = —,
^¿8ша(л;,-) /г,- г,- 2 /г,-
удовлетворяет условиям щ(х^) = Лгц(х^ = М^, ] = г,г+ 1 и дает нам решение систем (6.12) и (6.13) с и^ = Ui(xij) и = Ащ(х^),
j = 0,... ,П{.
Условия гладкости (6.7) дают линейную систему с 3-диагональной матрицей
М0 =
+ + а;/цМ; = г = 1,...,ЛГ, (6.14)
А4дЧ1 =
где
/¿+1 - /1 /г — /г—1
й,- =
„, _ -У.-(-П) я _ ^¿(1+^) п)
Матрица система (6.14) имеет диагональное преобладание и, следовательно, эта система имеет единственное решение.
Теперь можно сделать вывод, что функция и(х), совпадающая с иг(х) на отрезке [яг,-, аГг+1], г = 0,1,... ,ЛГ, является дискретным интерполяционным сплайном с натяжением. Сеточная выборка сплайна и(х) дает решение системы (6.6). Сплайн и(х) может также быть легко восстановлен по решению системы (6.6).
Вместо прямого решения системы (6.6) можно рекомендовать следующий алгоритм.
Шаг 1. Решить 3-диагональную систему (6.14) для М;, г = 1,..., N.
Шаг 2. Решить # + 1 3-диагональных систем (6.12) для М1}, ] =
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). Получена оценка
<hb2\ max Д—-Ь
~ I ,=1,...>Лг (Pi-A^hi + iPi Г A
x max — [i=o.....n 1ц
4||M||2 + max
1=0,JV ft;
1
+ |||М||2}.
(6.15)
где 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{) и при tv > 0, 7"2 > 0 используем обозначения
ДТ2 S{x) = - [5(х + r2) - S{x)], Д?] S(x) = - [S(z) - S{x - n)], тг Ti
л С-Л.. r2AflS(x)^nAf2S{xy • AT2S(x) — Дг,5(ж)
ilAf^TjOVXj — - — , Of T2S\X) — .
П + T"2 . (7l + T2 J/2
Определение 7.1. Обобщенным дискретным кубическим сплайном назовем функцию S(r) та кую, что
S(i) = 5i(i) ={Si - Ф{(х{)Мг]{1 -t) + [Si+1 - ®i(ii+1)Mi+1]i + $i(x)Mi+4!i{x)Mi+1
на каждом подотрезке i = 0,... ,'N — 1. Здесь t = (x — Xi)[hi,
Mj = bfi,,T2lS(xj), j — -fl з функция и Ф,(;г) подчинены усло-
виям
- Tli+i) = Ф<(Жг+х) = $i(a:i+1 + T2i+1) = 0, Фг(жг - = = Vjfa + r2l) = 0,
¿п,,г2,Фг(а:г) = 1, = 1.
Получены ограничения на функции Фг(х) и ФДа:), обеспечивающие существование и единственность обобщенного дискретного сплайна S(x).
Лемма 7.1. Лри выполнении условий
0 < <£i(Xi) < 0 < Ф.(^-и) <
г = 0,..., JV — 1 обобщенный дискретный кубический сплайн S(x) существует и единственен.
На основе методов главы 3 в пространстве обобщенных дискретных кубических сплайнов S.f построен базис из функций с конечными носителями минимальной длины типа В-сплайнов. Дискретные базисные сплайны обладают свойствами: Bi{x) > 0 при х £ (жг- + г2,-,Ж{+4 — Тц+а) II Bi(x) = 0 при X £ (Xi, £¿+4) ,
N-1
¡=-3
В частном случае тц = Тг,- = т для всех г получены рекуррентные формулы для дискретных В-сплайнов. Положим
Xj
6T,T<&j+l{x), Xj 0, В]
Uj < X < Xj+1, Bj,l(x) = { 6f,T<&j+l{x), Xj+1 <X< Xj+2,
противном случае,
] = г, г + 1, г + 2. Предполагается, что <5-г,гФу(х) и <5т,тФу+1(х) - монотонные функции соответственно на подотрезках [ху,ху+1] и [ху+1, ху+г] •
Тогда при х — Мт < хг- имеем
= тТ \В'ЛХ ~ кт) - ВшАх ~ *г)1, ; = - + 1, вг 3(х) = т У [-В"2(Х ~ кт) - В;+1'2(х " кг)
где суд = Д^2у+1(ху+1), Су,2 = уу-и - уу, Уу = ху - 2у(ху)/Д?2у(ху), ^(ху) = Фу_!(ху)-Фу(ху).
Легко проверить справедливость формул
сг',2 сг'+1,2
Основные свойства обобщенных кубических сплайнов с натяжением (глава 3) переформулированы и доказаны для обобщенных дискретных кубических сплайнов.
В главе 8 рассмотрен вопрос построения монотонизирующен параметризации для изогеометрических сплахшовых аппроксимаций.
Пусть дан набор попарно различных точек Р; = (х,-, у,-), г = 0,1,..., N на плоскости ХУ. Для проведения кривой через эти точки в общем случае необходимо построить сетку Д : а = <0 < ¿1 < • ■ • < ¿лт = Ь и задать на ней непрерывную вектор-функцию С(1) — (Cx(í), Су{1)), t £ [в,Ь] такую, что
Сх(и) = хи Су(и) = уг, г = 0,1,..., -/V,
то есть
С(и)=Р{, I = 0,1,..., N.
Форма кривой зависит как от выбора сетки, так и от метода решения на этой сетке задачи интерполяции. Будем говорить, что кривая С(1.) согласована по монотонности с исходными данными на отрезке [£&,</], к > I, если выполнены условия
с;(0(ху+1 - ху) > 0, с;(0(уу+! - уу) > 0 при t £ [*,-, гу+1] '
для всех ] = к,.. .,1 — 1.
В данной главе приведен новый алгоритм монотонизирующей параметризации в смысле (8.1) при интерполяции кубическими сплайнами класса гладкости С2. Такая параметризация позволяет улучшить визуальное
соответствие кривой и исходных данных и обеспечивает сгущение сетки в областях больших градиентов. При интерполяции однозначной функции гарантировано взаимно однозначное соответствие между осью абсцисс и точками кривой. Алгоритм обобщен на случай аппроксимации поверхностей.
В приложении 1 дается пример применения изложенных в диссертации методов изогеометрической аппроксимации сплайнами при реконструкции поверхности "корабля викингов". Исходные данные представляли собой поточечно заданные огибающие бортов и киля лодки а также данные шести шпангоутов. Вначале с помощью алгоритма изогеометрической интерполяции главы 2 строилась система кривых вдоль плазовых сечений. По ортогональному направлению согласно результатам главы 5 генерировалось семейство изогеометрических локально-аппроксимаци-онных сплайнов. Вычисление эйлеровых координат изогеометрической поверхности выполнялось с использованием монотонизирующей параметризации главы 8.
В приложении 2 дается описание комплекса программ на Фортране по описанию неоднозначной поверхности в трехмерном пространстве, реализующего разработанные в диссертации методы изогеометрической аппроксимации сплайнами.
ЗАКЛЮЧЕНИЕ
Основные результаты, полученные в диссертационной работе, состоят в следующем:
1. Разработан универсальный алгоритм изогеометрической локальной интерполяции обобщенными кубическими сплайнами с натяжением, дающий полное решение задачи изогеометрической интерполяции в классе функций С2 для произвольных данных с сохранением свойств монотонности и выпуклости исходных данных, выделением участков линейности, углов и изломов.
2. Предложены и обоснованы прямые методы построения локальных базисов для обобщенных сплайнов с натяжением, позволяющие получать для них явные формулы.
3. Разработаны рекуррентные формулы вычисления обобщенных В-сплайнов с натяжением произвольного порядка, являющиеся одновременно аппаратом исследования их качественных свойств.
4. Изучены свойства обобщенных В-сплайнов с натяжением и рядов от ' них. Показано, что такие сплайны обладают свойством уменьшения
вариации и являются чебышевскими сплайнами.
5. Разработаны алгоритмы изогеометрической локальной аппроксимации обобщенными сплайнами с натяжением одной и двух переменных, обеспечивающие сохранение свойств монотонности и выпуклости исходных данных.
6. Разработаны и обоснованы разностные методы интерполяции дискретными сплайнами с натяжением.
7. Построены базисы из обобщенных дискретных В-сплайнов с натяжением, изучен аппарат дискретных обобщенных В-сплайнов с натяжением и рядов от них.
8. Предложены алгоритмы монотонизпрующей параметризации для изо-геометричегких гплайновых кривых и поверхностей, позволяющие существенно улучшить визуальное соответствие исходных данных и результирующих гплайновых аппроксимаций.
По результатам проведенных исследований можно сделать следующий вывод. На единой методологической основе обобщенных сплайнов с натяжением разработаны методы изогеомстрцческой аппроксимации сплайнами. позволяющие дать достаточно полное решение задачи изогеомстрцческой аппроксимации для произвольных сеточных данных.
СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ
1. Завьялов Ю. С.. Квасов Б. И., Мирошниченко В. Л. Методы сплайн-функций. М.: Наука, 1980. - 352 с.
2. Квасов Б. И. О построении Ь-сплайнов // Численные методы механики сплошной среды. - Новосибирск, 1972. - Т. 3. - N 3. - С. 64-71.
3. Квасов Б. И. Получение сплайнов осреднением кусочно-постоянных функций. Сплайны с дополнительными узлами // Численные методы механики сплошной среды. Новосибирск, 1973. - Т. 4. - N 1. -С. 39 55.
1. Квасов Б. И. Об итерационном методе построения сплайнов //Вариационно-разностные методы в математической физике. - Новосибирск. ВЦ СО АН СССР, 1974. - С. 107-115.
5. Квасов Б. И. Интерполяция сплайнами первой степени // Методы сплайн-функций. Новосибирск. 1975. - Вып. 65: Вычислительные системы." - С. 50- 59, 161 162.
6. Квасов Б. И. Сплайн-решение смешанной задачи Лагранжа-Эрмита // Численные методы механики сплошной среды. - Новосибирск. 1977. - Т. 8. - N 1. - С. 59-82.
7. Квасов Б. И. О краевых условиях при интерполяции параболическими сплайнами // Методы аппроксимации и интерполяции. - Новосибирск, 1981. - Вып. 87: Вычислительные системы. - С. 11-17.
8. Квасов Б. И. Интерполяция квадратпчеекпмп сплайнами. - Новосибирск, 1981. - 61 с. - (Препринт / АН СССР. Сиб. отд-ние. Ин-т теор. и прикл. механики, N 3).
9. Квасов Б. И. О реализации интерполяции параболическими сплайнами // Численные методы механики сплошной среды. - Новосибирск. 1982. - Т. 13. - N 4. - С. 35-51.
10. Квасов Б. И. Дискретные интерполяционные параболические сплайны и их применение к задаче численного дифференцирования. - Новосибирск, 1982. - 27 с. - (Препринт / АН СССР. Сиб. отд-ние. Вычислительных"! центр, N 97).
11. Квасов Б. И. Применение параболических сплайнов для решения задач интерполяции // Журнал вычислительной математики и математической физики. - М., 1983. - Т. 23. - N 2. - С. 278-289.
12. Квасов Б. И. Численное дифференцирование и интегрирование на основе интерполяционных параболических сплайнов // Численные
методы механики сплошной среды. - Новосибирск, 1983. - Т. 14.
- N 2. - С. 68-80. • .
13. Квасов Б. И. Численное дифференцирование на основе дискретных кубических сплайнов // Численные методы механики сплошной среды. - Новосибирск, 1983. - Т. 14. - N 4. - С. 84-96.
14. Квасов Б. И. Обобщенные параболические сплайны // Междунар. конф. по теории аппроксимации функций. - Киев, 30 мая-6 июня 1983 г. - С. 92-93.
15. Квасов Б. И. Обобщенные X -сплайны // Новосибирск, 1983. - Вып. ■ 98: Вычислительные системы. - С. 3-19, 151.
16. Квасов Б. И. О методе интерполяции дискретных функций // Новосибирск, 1983. - Вып. 98: Вычислительные системы. - С. 20-26, 151.
17. Квасов Б. И. Оценки аппроксимации интерполяционными-параболическими сплайнами. - Новосибирск, 1984. - 24 с. -(Препринт /- АН СССР. Сиб. отд-ние. -Ин-т теор. и прикл. механики, N 2-84).
18. Квасов Б. И. Интерполяция эрмитовыми параболическими сплайнами // Известия ВУЗов. Математика. - Казань, 1984. - N 5. -С. 2.5-32.
19. Квасов Б. И. Оценки точности аппроксимации функции одной вещественной переменной эрмитовыми параболическими сплайнами / / Моделирование и оптимизация структурных систем. - Барнаул, 1984.
- С. 30-39.
20. Квасов Б. И. Интерполяция посредством дискретных параболических сплайнов // Журнал вычислительной математики и математической физики. - М., 1984. - Т. 24. - N 5. - С. 640-649.
21. Квасов Б. И. ' Дискретные квадратические сплайны // Численные методы механики сплошной среды. - Новосибирск, 1984. - Т. 15. -N 6. - С. 94-109.
22. Квасов Б. И. Интерполяция рациональными параболическими сплай-■ нами // Численные методы механики сплошной среды. - Новосибирск, 1984. - Т. 15. - N 4. - С. 60-70.
23. Квасов Б. И. Продолжение сеточных решений уравнений с разрывными коэффициентами параболическими сплайнами / / Вариационно-разностные методы в математической физике. Сборник научных работ. - М., ИВМ АН СССР, 1984. - Т. 2. - С. 144-150.
24. Квасов Б. И. О краевых условиях при интерполяции параболическими сплайнами на неравномерной сетке // Новосибирск, 1986, - Вып. 115: Вычислительные системы. - С. 60-71, 151.
25. Квасов Б. И. Полиномиальные сплайны // Вычислительные технологии. - Новосибирск, ИВТ СО РАН. - 1994. - Т. 3. - N 9. -С. 71-107.
26. Квасов Б. И. Алгоритмы и комплекс программ изогеометрической аппроксимации обобщенными сплайнами // Труды конф. "Пакеты программ математической физики". Вычислительные технологии. -Новосибирск, ИВТ СО РАН, 1995. - Т. 4. - N 1. - С. 219-232.
27,
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
Квасов Б. И. Методы построения обобщенных В-сплайнов п их свойства1// Доклады Российской Академии наук. - М., 1995. - Т. 341. -N 6. - С. 744-748/ •
Квасов Б. И. Обобщенные В-сплайны с натяжением произвольного порядка // Доклады Российской Академии наук. - М. (принято к печати).
Квасов Б. И. Обобщенные В-сплайны и алгоритмы изогеометриче-ской аппроксимации // Журнал вычислительной математики и математической физики. - М. (в печати).
Квасов Б. И., Кобков В. В'. Некоторые свойства кубических эрмитовых сплайнов с дополнительными узлами // Доклады Академии наук СССР. - М., 1974. - Т. 217.' - N 5. - С. 1007-1010. Квасов Б. И., Кобков В. В. Сплайны с дополнительными узлами II. Их пределы и некоторые свойства // Численные методы механики сплошной среды. - Новосибирск, 1974. - Т. 5. - N 4. - С. 48-70. Квасов Б. И., Яценко С.' А. Изогеометрическая интерполяция рациональными сплайнами // Аппроксимация сплайнами. - Новосибирск, 1987. - Вып. 121: Вычислительные системы. - С. 11-36, 125. Квасов Б,- И., Яценко С. А. Решение задачи изогеометрической интерполяции в классе рациональных сплайнов. - Новосибирск, 1988. - 60 с. - (Препринт / АН СССР. Сиб. отд-ние. Ин-т теор. и прикл.. механики, N 3-88).
Квасов Б. И., Яценко С. А. Алгоритмы изогеометрической аппроксимации рациональными сплайнами. - Новосибирск, 1990. - 34 с. -(Препринт/АН СССР. Сиб. отд-ние. Ин-т теорет. и прикл.. механики, N 9-90).
Квасов Б. И., Яценко С. А. Трехмерная изогеометрическая аппроксимация рациональными В-сплайнами // Конф. "Теоретические основы и конструирование численных алгоритмов для решения задач математической физики". - Красновидово, 15-19 окт., М., ИПМ АН СССР им. Келдыша, 1991. - С. 112-116.
Яненко Н. Н., Квасов Б. И. Итерационный метод построения поликубических сплайн-функций // Доклады Академии наук СССР. - М., 1970. - Т. 195. - N 5. - С. 1055-1057.
Яненко Н. Н., Квасов Б. И. Итерационный метод построения поликубических сплайн-функций // Численные методы механики сплошной среды. - Новосибирск, 1970. - Т.,1. - N 3. - С. 84-89. Яценко С. А., Квасов Б. И. О выборе параметризации для кубических сплайнов // Моделирование в механике. - Новосибирск, 1991. -Т. 5(22). - N 5. - С. 118-135.
Kvasov В. I. Data dependent parametrization for shape preserving spline approximation // Third Russian-Japan symposium on computational aerodynamics. - Vladivostok, 1992. - P. 131-132.
Kvasov В. I. Local bases for generalized cubic splines // Russian Journal of Numerical Analysis and Mathematical Modelling. - VSP BV, The Netherlands, 1995. - Vol. 10. - No. 1. - P. 49-80.
41. Kvasov В. I. Isogeometric interpolation by generalized splines // Russian Journal of Numerical Analysis and Mathematical Modelling. - VSP BV, The Netherlands, 1995. - Vol. 10. - No. 6.
42. Kvasov В. I. GB-splines and their properties // Annals of Numerical Mathematics. - 1996. - Vol. 3. - P. 139-149.
43. Kvasov В. I. Shape Preserving Spline Approximation via Local Algorithms. in: Advanced Topics in Multivariate Approximation. F.Fontanel-la, K.Jetter and P.J.Laurent (eds.), pp. 181-196. World Scientific Publishing Co., Inc., 1996.
44. Kvasov В. I. Shape Preserving С2 Spline Interpolation // Proceedings of The Second Asian Mathematical Conference. - Nakhon Ratchasima, Thailand, Oct. 17-20, 1995. - 8 p. (в печати).
45. Kvasov В. I., Sattayatham P. Generalized tension B-splines of arbitrary degree // Third Int. Conference on Curves and Surfaces. - Chamonix Mont-Blanc, France, June 27 - July 3, 1996. - P. 32.
46. Kvasov В. I., Sattayatham P. Fair-Shape-Preserving Approximation via Tension B-splines // Seventh IMA Conference on The Mathematics of Surfaces. - University of Dundee, Scotland, 1st - 4th September 1996. "2 P.
47. Kvasov В. I., Sattayatham P. Generalized Tension B-splines // in: Curves and Surfaces with Applications in CAGD. A. Le Mehaute, C. Rabut, and L.L. Schumaker (eds.), Vanderbilt Univ. Press, Nashville, TN, ISBN 08265-1293-3,1997. - P. 247-254.
48. Kvasov В. I., Vanin L. A. Rational B-splines and algorithms of isogeometric local approximation // Russian Journal of Numerical Analysis and Mathematical Modelling. - VSP BV, The Netherlands, - 1993. - Vol. 8. - No. 6. - P. 481-504.
49. Kvasov В. I., Yatsenko S. A. Conservative Interpolation by Rational Splines // Approximation Theory VI: Proceedings of the Sixth International Symposium on Approximation Theory. Vol. II. Chui С. K., Schumaker L. L., Ward J. D. (eds.). - Boston: Academic Press, 1989. - P. 365-
367.
