Содержание к диссертации
Введение
1. Интерполяционные D -сплайны 15
1. Существование и единственность. Теоремы сходимости 15
1.1. Предварительные сведения из теории соболевских пространств 15
1.2. Определение и свойства -сплайнов 17
1.3. П.-сети и теорема сходимости 20
2. Оценки сходимости- 24
2.1. Специальное покрытие области 24
2.2. Равномерная эквивалентность норм 25
2.3. Лемма о соболевских функциях со сгущающимся семейством нулей 29
2.4. Сходимость сплайнов в нормах L 35
2.5. Сплайны по локальным средним 39
3. Сплайны с краевыми условиями 42
3.1. Существование и единственность. Свойство ортогональности 42
3.2. Оценки сходимости в L 46
2. Следы сплайнов на гладких шогообразиях 50
4. Следы сплайнов на неалгебраических многообразиях 50
4.1. Пространства НС 50
4.2. Существование и единственность. Теорема сходимости 53
4.3. Скорость сходимости вНСОиССГ 60
5. Следы сплайнов на алгебраических многообразиях 64
5.1. Следы полиномов 65
5.2. Единственность следа сплайна 67
5.3. Сходимость 72
6 Е-сплайны в &*" 73
3. Численные алгоритмы построения сплайнов 82
7. Алгоритмические аспекты метода сплайнов на подпространстве 82
8. Сходимость бикубических сплайнов в задаче интерполяции функции на хаотическоей сетке 89
8.1. Дискретизация задачи 90
8.2. Оценки погрешности 96
9. Приближение функций, заданных на сфере 104
9.1. Разложение пространства 'мч 104
9.2. Алгоритм построения х> -сплайна на сфере 110
Литература 117
- Определение и свойства -сплайнов
- Сходимость сплайнов в нормах L
- Существование и единственность. Теорема сходимости
- Сходимость бикубических сплайнов в задаче интерполяции функции на хаотическоей сетке
Введение к работе
Современная теория сплайнов представляет собой быстроразви-ваіощийся раздел вычислительной математики, ориентированный на решение задач гладкой аппроксимации функциональных зависимостей, заданных в дискретной форме. Эта теория, зародившаяся в работах Шенберга как алгебраический аппарат построения гладких восполнений сеточных функций, получила новый импульс для развития, когда был открыт (Дж.Холидей, 1957) вариационный принцип, которому подчиняются сплайн-функции. (Следует отметить, что алгебраическая теория сплайнов продолжает успешно развиваться, в основном благодаря усилиям советских математиков во главе с Ю.С.Завьяловым и Ю.Н.Субботиным). В конечном итоге это привело к общему определению сплайна как элемента гильбертова пространства, принимающего заданные значения на некоторых линейных функционалах и минимизирующего квадратичный функционал типа энергии (М.Аттья, 1966). В дальнейшем был предложен общий алгоритм построения таких сплайнов (П.-Ж.Лоран, Ф.Анселон, 1968), окончательно выяснены вопросы существования и единственности сплайнов. С этого времени стала очевидной связь между теорией сплайнов и теорией регуляризации некорректно поставленных задач, разделом, созданным советскими математиками во главе с А.Н.Тихоновым.
Вопросам сходимости сплайнов в общей форме был посвящен цикл работ В.А.Василенко. На основе введенного им понятия пра-
вильной системы операторов (1973) ему удалось доказать общую теорему сходимости сплайнов и применить ее для анализа сходимости интерполяционных сплайнов на хаотических сетках, кривых и т.д. (Это приложение весьма важно для дальнейшего изложения материала). В дальнейшем было показано (А.Имамов,. 1977), что понятие правильности системы операторов является фундаментальным и необходимо для сходимости интерполяционного процесса.
Поскольку сплайн-функции многих переменных на хаотических сетках, минимизирующие функционал энергии, заимствованный из вариационного принципа для решения полигармонического уравнения, представляют собой сложные неполиномиальные конструкции, для вычисления которых, кроме того, необходимо решать системы алгебраических уравнений с плотными матрицами, В.А.Василенко предложил использовать метод конечных элементов для их приближенного расчета (алгоритмические проблемы и конкретное программное обеспечение, реализованное автором диссертации для решения такого типа задач, обсуждается в 7 диссертационной работы). В общем случае это привело к понятию сплайнов на подпространствах и доказательству факта сходимости таких аппроксимаций.
Тем самым, к настоящему времени многие принципиальные теоретические и алгоритмические вопросы в теории сплайнов на хао-тических сетках (в современной терминологии V -сплайнов) решены. Однако оставались неясными методы получения порядков сходимости Е -сплайнов на сгущающихся К—сетях. По-видимому, наибольшего успеха в этом направлении добился Ж.Дюшон (1977), получивший такие оценки в нормах типа L . Однако для этого он рассмотрел конструкцию, не являющуюся сплайном в гильбертовом пространстве.
Основные усилия в главе I направлены на получение оценок
сходимости D-сплайнов и их производных в ограниченных областях, без учета краевых условий и с их учетом. При этом используется техника теорем вложения, теорем о следах, и доказываются специальные леммы о поведении соболевских функций со сгущающимся семейством нулей.
В дальнейшем основное направление исследований - сплайн-аппроксимация неоднозначных пространственных поверхностей. Несмотря на успехи теории сплайнов, решение такого сорта задач представляет определенные трудности. В диссертации предлагается ис-пользовать для этих целей следы V -сплайнов на многообразиях меньшей размерности, чем размерность исходной области. Удалось доказать соответствующие оценки сходимости следов -V -сплайнов в случае, когда сгущение интерполяционных точек происходит не во всей области, а только на многообразии.
И, наконец, предметом рассмотрения главы Ш были алгоритмические вопросы аппроксимации функций многих переменных на хаотических сетках, а также неоднозначных поверхностей.
Перейдем к краткому изложению результатов диссертации. Она состоит из введения, трех глав и приложения.
Понятие Ъ -сплайна было впервые введено в работе Атья І2І для конечного числа интерполяционных точек. В диссертации оно обобщается на произвольное множество А интерполяционных точек, доказываются теоремы существования и единственности Х> -сплайна, а также теоремы сходимости.
Обозначим через SL - ограниченную односвязную область в (R, с границей і , удовлетворяющей условию Липшица. Положим ^2. &) ~ соболевское пространство действительных функции со скалярным произведением
Си it) = С-* ir) + l(2>uv) ч ' '
' l4sl) V &SL)
и нормой
±
кгч.« - ( In*. І* + ||1^/|г f (0.2)
где (Ъ и, 2> і-) и If 3> u, II , обозначают
/ —7 ] . cLoc
o*-l x. dec
(0.3)
2.
(0.4)
(Z j С^)^)г,
^ - мультииндекс, <^«- ^,.. . ,^K) , ^7 ^ О , 2»o^ =^
'T*
tf X
-^- - частная производная порядка m- .
Положим ha>~- целое, и пусть А подмножество в h .
Определение I. Пусть задана функция -j- в пространстве W (fl). Назовем функцию І V/ (il) интерполяцион-ным D-сплайном, если она доставляет минимум функционалу l/J> u^l/2- л на множестве функций и.е\л/ (І2), совпадаю-щих с і на множестве А .
В I показано, что интерполяционный сплайн \ существует и единственен, если множество А содержит L - разрешимый набор точек для пространства полиномов РііЛ_-± степени меньшей ha. от і'и - переменных ( L - разрешимость означает, что полином Лагранжа по точкам набора существует и единственен).
Будем говорить, что множества ^,,4-, * образуют сгущающуюся 4\- сеть в области SL , если расстояние Хаусдорфа
кк - сі (AK>JL) = sup L*~/ 1~і-(Ц
(0.5)
t A'k CiCal
между множествами Ак ж Si стремится к нулю при к -> «» .
На основе общей теоремы сходимости (В.А.Василенко [її] ) доказано, что в этих условиях сплайны / * сходятся к функции d в норме пространства W (Si),
Вопросам доказательства оценок сходимости сплайнов f к функции посвящен 2. С использованием метода, описанного в работах Дюшона JI6J и Аркангели |2j7a также сведений из теории соболевских пространств доказывается следующая лемма о функциях со сгущающимся семейством нулей.
Лемма 2.5. Существуют константы с>о и ^О>о такие, что для любого ^я0 неравенство
|[ А ІІ * с С~*'г + ? IJ 2)1 II (0.6)
Ли) LZ(SL)
справедливо для любой функции it е W ( Я) , имеющей л_- сеть нулей в области Si . Константа С зависит от параметров ы,, и. 9 к , р f но не зависит от функции ьс .Параметры М-,
К , К и )о удовлетворяют неравенствам у^-~ > к - 5 (исключая случай к-\^ь~~ , ь-« ).
Через II 3> u. If обозначена полунорма в Соболевском
пространстве w (SC) , включающая только лишь производные порядка < , аналогичная (0.4).
Лемма является основополагающей для всех оценок погрешности сплайнов, полученных в диссертации. В частности, для
A введенных"*
D-сплайнов -f справедливы асимптотические оценки
НВКаАЧ)|| -оСІ^~2^) (0.7)
при ^>^ . Оценка (0.7) получается подстановкой в неравен-ство (0.6) функции ошибки (f e~f) , имеющей -к - сеть нулей в области JL .
Дальнейшее изложение 2 посвящено вопросам получения оценок сходимости при сгущении интерполяционных точек внутри некоторой подобласти JL 0 области SL 9 а также исследованию сплайнов по локальным интегральным средним.
В 3 вводятся -> -сплайны с краевыми условиями в многомерной ограниченной области.
Рассмотрим для этого гильбертово подпространство в W (JI) определенное следующим образом
Пусть /e Vv/ (SI) ; рассмотрим в пространстве V, Oi) афинное замкнутое многообразие
Н, ^ Ь V/ (л) (0.8)
Пусть /А - произвольное множество в Л .
Определение 2. Назовем функцию д ^ н/ интер-
поляционным D -сплайном с краевыгли условиями, если она ми-
нимизирует функционал II jD и. || на множестве функций -ис Н ,
я гаг) д і
совпадающих сів точках множества А .
Теорема существования такого сплайна формулируется аналогич-но случаю J) -сплайна без краевых условий. Однако оценки сходимости удалось улучшить.
Теорема 3.2. Существует \0> о такое, что для любого L^^Q и множества А , образующего к - сеть в области JL } сплайн ^ существует и единственен для любой е VJ (И) и справедлива оценка
II D ({"-/) || *e I p (0.9)
Константа С не зависит от параметра А и функции | .
Определение и свойства -сплайнов
Современная теория сплайнов представляет собой быстроразви-ваіощийся раздел вычислительной математики, ориентированный на решение задач гладкой аппроксимации функциональных зависимостей, заданных в дискретной форме. Эта теория, зародившаяся в работах Шенберга как алгебраический аппарат построения гладких восполнений сеточных функций, получила новый импульс для развития, когда был открыт (Дж.Холидей, 1957) вариационный принцип, которому подчиняются сплайн-функции. (Следует отметить, что алгебраическая теория сплайнов продолжает успешно развиваться, в основном благодаря усилиям советских математиков во главе с Ю.С.Завьяловым и Ю.Н.Субботиным). В конечном итоге это привело к общему определению сплайна как элемента гильбертова пространства, принимающего заданные значения на некоторых линейных функционалах и минимизирующего квадратичный функционал типа энергии (М.Аттья, 1966). В дальнейшем был предложен общий алгоритм построения таких сплайнов (П.-Ж.Лоран, Ф.Анселон, 1968), окончательно выяснены вопросы существования и единственности сплайнов. С этого времени стала очевидной связь между теорией сплайнов и теорией регуляризации некорректно поставленных задач, разделом, созданным советскими математиками во главе с А.Н.Тихоновым. Вопросам сходимости сплайнов в общей форме был посвящен цикл работ В.А.Василенко. На основе введенного им понятия пра- вильной системы операторов (1973) ему удалось доказать общую теорему сходимости сплайнов и применить ее для анализа сходимости интерполяционных сплайнов на хаотических сетках, кривых и т.д. (Это приложение весьма важно для дальнейшего изложения материала). В дальнейшем было показано (А.Имамов,. 1977), что понятие правильности системы операторов является фундаментальным и необходимо для сходимости интерполяционного процесса. Поскольку сплайн-функции многих переменных на хаотических сетках, минимизирующие функционал энергии, заимствованный из вариационного принципа для решения полигармонического уравнения, представляют собой сложные неполиномиальные конструкции, для вычисления которых, кроме того, необходимо решать системы алгебраических уравнений с плотными матрицами, В.А.Василенко предложил использовать метод конечных элементов для их приближенного расчета (алгоритмические проблемы и конкретное программное обеспечение, реализованное автором диссертации для решения такого типа задач, обсуждается в 7 диссертационной работы).
В общем случае это привело к понятию сплайнов на подпространствах и доказательству факта сходимости таких аппроксимаций. Тем самым, к настоящему времени многие принципиальные теоретические и алгоритмические вопросы в теории сплайнов на хао-тических сетках (в современной терминологии V -сплайнов) решены. Однако оставались неясными методы получения порядков сходимости Е -сплайнов на сгущающихся К—сетях. По-видимому, наибольшего успеха в этом направлении добился Ж.Дюшон (1977), получивший такие оценки в нормах типа L . Однако для этого он рассмотрел конструкцию, не являющуюся сплайном в гильбертовом пространстве. Основные усилия в главе I направлены на получение оценок сходимости D-сплайнов и их производных в ограниченных областях, без учета краевых условий и с их учетом. При этом используется техника теорем вложения, теорем о следах, и доказываются специальные леммы о поведении соболевских функций со сгущающимся семейством нулей. В дальнейшем основное направление исследований - сплайн-аппроксимация неоднозначных пространственных поверхностей. Несмотря на успехи теории сплайнов, решение такого сорта задач представляет определенные трудности. В диссертации предлагается ис-пользовать для этих целей следы V -сплайнов на многообразиях меньшей размерности, чем размерность исходной области. Удалось доказать соответствующие оценки сходимости следов -V -сплайнов в случае, когда сгущение интерполяционных точек происходит не во всей области, а только на многообразии. И, наконец, предметом рассмотрения главы Ш были алгоритмические вопросы аппроксимации функций многих переменных на хаотических сетках, а также неоднозначных поверхностей. Перейдем к краткому изложению результатов диссертации. Она состоит из введения, трех глав и приложения. Понятие Ъ -сплайна было впервые введено в работе Атья І2І для конечного числа интерполяционных точек. В диссертации оно обобщается на произвольное множество А интерполяционных точек, доказываются теоремы существования и единственности Х -сплайна, а также теоремы сходимости. Обозначим через SL - ограниченную односвязную область в (R, с границей і , удовлетворяющей условию Липшица.
Сходимость сплайнов в нормах L
В I показано, что интерполяционный сплайн \ существует и единственен, если множество А содержит L - разрешимый набор точек для пространства полиномов РііЛ_-± степени меньшей ha. от і и - переменных ( L - разрешимость означает, что полином Лагранжа по точкам набора существует и единственен). Будем говорить, что множества ,,4-, образуют сгущающуюся 4\- сеть в области SL , если расстояние Хаусдорфа между множествами Ак ж Si стремится к нулю при к - «» . На основе общей теоремы сходимости (В.А.Василенко [її] ) доказано, что в этих условиях сплайны / сходятся к функции d в норме пространства W (Si), Вопросам доказательства оценок сходимости сплайнов f к функции посвящен 2. С использованием метода, описанного в работах Дюшона JI6J и Аркангели 2j7a также сведений из теории соболевских пространств доказывается следующая лемма о функциях со сгущающимся семейством нулей. Лемма 2.5. Существуют константы с о и О о такие, что для любого я0 неравенство справедливо для любой функции it е W ( Я) , имеющей л_- сеть нулей в области Si . Константа С зависит от параметров ы,, и. 9 к , р f но не зависит от функции ьс .Параметры М-, К , К и )о удовлетворяют неравенствам У - к - 5 (исключая случай к-\ ь , ь-« ). Через II 3 u. If обозначена полунорма в Соболевском пространстве w (SC) , включающая только лишь производные порядка , аналогичная (0.4). Лемма является основополагающей для всех оценок погрешности сплайнов, полученных в диссертации. В частности, для A введенных" D-сплайнов -f справедливы асимптотические оценки при . Оценка (0.7) получается подстановкой в неравен-ство (0.6) функции ошибки (f e f) , имеющей -к - сеть нулей в области JL . Дальнейшее изложение 2 посвящено вопросам получения оценок сходимости при сгущении интерполяционных точек внутри некоторой подобласти JL 0 области SL 9 а также исследованию сплайнов по локальным интегральным средним. В 3 вводятся - -сплайны с краевыми условиями в многомерной ограниченной области. Рассмотрим для этого гильбертово подпространство в W (JI) определенное следующим образом Пусть /e Vv/ (SI) ; рассмотрим в пространстве V, Oi) афинное замкнутое многообразие Пусть /А - произвольное множество в Л . Определение 2. Назовем функцию д н/ интер- поляционным D -сплайном с краевыгли условиями, если она ми- нимизирует функционал II JD и. на множестве функций -ис Н , совпадающих сів точках множества А . Теорема существования такого сплайна формулируется аналогич-но случаю J) -сплайна без краевых условий.
Однако оценки сходимости удалось улучшить. Теорема 3.2. Существует \0 о такое, что для любого L Q и множества А , образующего к - сеть в области JL } сплайн существует и единственен для любой е VJ (И) и справедлива оценка Константа С не зависит от параметра А и функции . Глава 2 посвящена изучению свойств следов Л)-сплайнов на гладких многообразиях размерности И.-1 в пространстве Ш. . Вначале исследуется существование и единственность следа _D -сплайна, затем выводятся оценки сходимости сплайна при сгущении интерполяционных узлов на многообразии. Пусть Л - подобласть области Л , и граница Г области Sha является бесконечно дифференцируемым многообразием размерности С -1) . Рассматриваются сплайны, введенные определением I, где множество А предполагается подмножеством Г . В 4 рассматривается случай неалгебраической поверхности Г . Теорема существования и единственности формулируются следующим образом: найдется ho 0 , что для любого множества А , являющегося - i- сетью в і при л\ (Vc , задача определения р-А сплайна 1 имеет единственное решение. Для алгебраической поверхности формулировки сохраняются; но единственным является след сплайна 1 на границу Г , а не сам сплайн. Этот случай рассмотрен в 5. Для сплайнов Дюшона ІІ5 [, определенных в 6 формулируются аналогичные теоремы. Оценки сходимости для сплайнов, доказанные в 4, с небольшими изменениями переносятся в сформулировать следущим образом. Теорема . Пусть f є Н (Т) (Н(г)соболевокое пространство функций, определенных на Г [22j), " - р, множества А±, А ,,.. образуют сгущающуюся & - сеть на Г Тогда для следов D -сплайнов справедливы асимптотические оценки при к » о . Параметр 5 принадлежит интервалу [ о, - і ] Для доказательства используются теоремы о следах Соболевских функций, теоремы о продолжениях [22 j и лемма о функциях со сгущающимся семейством нулей. Глава 3 посвящена численным алгоритмам приближенного построения JJ -сплайнов.
В 7 исследуются вопросы реализации алгоритма построения интерполяционного и сглаживающего сплайна методом сплайнов на подпространствах для хаотических сеток. Теоретические основы алгоритма были разработаны в работах В.А.Василенко, однако программной реализации не было из-за сложности структур возникающих матриц. Автором диссертации был разработан комплект программ IM L для интерполяции и сглаживания функции любого числа переменных кусочно полиномиальными сплайнами дефекта І. В качестве конечных элементов были выбраны базисные В-сплайны. Это позволило редуцировать задачу к разреженной системе линейных уравнений, компактно хранить матрицы систем в дву- мерном массиве и построить быструю процедуру извлечения элементов матрицы из массива с целью умножения матрицы на произвольный вектор. Это позволяет применить к решению итерационные методы. В 8 предлагается алгоритм интерполяции функции двух переменных бикубическими сплайнами. Теоретической основой для алгоритма послужили J -сплайны с краевыми условиями, изученные в 3. Исследование оценок погрешности аналогично проделанному в Относительно интерполируемой функции предполагаются известными ее значения на хаотической L- сети внутри прямоугольника, а также значения функции и значение ее нормальных производных на границе прямоугольника, и значения смешанных производных в четырех угловых точках. При численной реализации краевые условия естественно требуются в конечном числе точек, а не на всей границе.
Существование и единственность. Теорема сходимости
Простым следствием теорем 122 является факт существования ограниченности линейного оператора, действующего из гиль- гл.- — бертова пространства Н 2(w в H((R) , сопоставляющего функции \ , определенной на Г , ее продолжение на IR. . Так как след на область Л функции из Н (Щ ) лежит в пространстве W (XI) , то и неравенство (4.8) очевидно. Лемма доказана. 4.2. Существование и единственность. Теорема сходимости Пусть А - подмножество Г , Н г(Ґ) , Как и прежде, назовем элемент \ W (JL) интерполяционным 2 -сплайном, если он является решением следующей задачи Множество А С4 1л) состоит из функций пространства W (Л.) , совпадающих с на множестве А =- П По теореме I.I решение задачи (4.9) единственно, если множество А, (и) непусто, а множество А содержит /» - разрешимый набор для пространства полиномов ьг-і По лемме 4.1 функцию \ можно продолжить на SL с помощью оператора Ц , так что 3 6 W (ІГ) . Ясно, что Предположим, что Г не является алгебраической поверхностью порядка t)n-l) , т.е. не существует полинома F -x) P t такого, что Рт.1(тс) .о , Vxtf Лемма 4.2. Найдется положительное te такое, что для любого к& к 0 множество A f являющееся k. - сетью в Г , содержит L - разрешимы!! набор. Доказательство . Воспользуемся определением 1.2 А - разрешимого набора и покажем, что существует А/ -точек &L,..., ь на Г , образующие А - разрешимый набор. Обозначим базисные мономы пространства Pm_i через Проведем доказательство индукцией по числу Для одной точки f Г можно построить интерполяциоН ный глногочлен из пространства Р Предположим, что для р точек -»,... , 1р Г можно построить интерполяционный глногочлен, т.е. V гА,... ,?р ft существуют коэффициенты lL,... такие, что совпадает в точках полином лами ,..., г« : л/ коэффициенты « можно получить из системы Ар = : Ранг матрицы А равен р , поскольку иначе система не была бы разрешима при любых Х1,.. ,, гр . Поэтому можно так перенумеровать базисные элементы, чтобы матрица была невырожденной. Докажем, что к точкам ъ1?к1 )ь- еГ можно добавить точку pj-i- такую, ,чтобы матрица Ар и. имела ранг (э+±) . Пусть это не так, и для любой точки с из Г матрица имеет ранг Р . Поскольку первые р столбцов матрицы (4.II) линейно независшлы, то P + І столбец выражается через их линейную комбинацию. Существуют константы с с у І ІЛІ для которых справедливы соотношения Система линейных уравнений (4.12) имеет невырожденную матрицу (4.10), поэтому коэффициенты CjC-O определяются однозначно из (4.12) и не зависят от t c . Отсюда следует Условие (4.14) означает, что -Г описывается полиномом (Ьг-1) порядка. Это противоречит предположению, и процесс добавления точек можно продолжить.
Определенные точки t л/ - образуют L - разрешимый набор, поскольку матрица А невырождена, и коэффициенты интерполяционного многочлена U. , » ,. д, определяются однозначно по интерполяционным значениям. Повторяя рассуждения теоремы 1.3, заменив в нем область JTL на границу Г » получим окончательный результат леммы. Теорема 4.3. Пусть задана функция н Н 2(Г) , и множества А , А г , ... образуют сгущающуюся н-сеть в Г7 . Тогда следы на Г сплайнов сходятся к функции в норме пространства п "(Г). Доказательство . Обозначим множество решений задачи (4.9) при всевозможных функциях / и множестве А , совпадающего с Г , через SpCH Свойство ортогональности (4.14) утверждает, что для любого элемента 64 S/э г) и функции r W CSl) ,аннулирующейся на , справедливо соотношение и если (4.16) выполняется для любой таким образом определенной функции тг , то s"eSp r). Из неравенства (4.16) можно заключить, что множество SbCO является гильбертовым подпространством в W (_&) . Действительно, если 6 и б принадлежат Sp(r) , то для них выполняется равенство (4.16), и, конечно, равенство (4.16) выполняется для любой линейной комбинации Я16 1 + Стало быть р(Г) - линейное пространство. Используя неравенство Шварца, можно показать, что для любых гс,1Г W\CSL) . Докажем замкнутость S«( О . Пусть fcSpCr) и 6 сходятся к 6 Покажем, что ь также удовлетворяет (4.16). Имеем неравенства Последнее выражение стремится к нулю при »х- о , и поэтому и является элементом Ьр(Г) . Поскольку Sp(P) линейное и замкнутое подпространство в W (JT) , то оно является гильбертовым. При доказательстве теоремы 1.3 было установлено, что W, (SI) /Р , - является гильбертовым пространством с нормой и из вышеизложенного следует, что %(Г)/Рт_і является гильбертовым подпространством с нормой 11-11 . Докажем, что фактор пространство Н " /Рт_ с нормой является гильбертовым. Легко заметить, что определение (4.18) не зависит от выбора функции в классе и.+ Ры_± , это следует из свойства ортогональности (4.16). Введем отображение сопоставляющее классу + -1 ж-і к 71300 «\ + Рм-і6 г)/Рт_1; где V - элемент класса к + Pm а 6 является решением задачи Опять же из свойства (4.16) можно заключить, что определение оператора Ь - корректно, и не зависит от выбора представителя, и оператор t является биекцией. Поскольку нормы элементов w- Py -i и є"ч+ pm-± совпадают, a t - биекция, то Н (r)/ . также гильбертово пространство как и Докажем, что оператор . сопоставляющий элементу ueH г(г класс іс+Р И гСг) /Pm.± -непрерывен.
Используя оператор Ті , определенный в лемме 4.1, имеем неравенства Для доказательства утверждения теоремы воспользуемся теоремой 1.2. Положим Х(Г) хН ЧГ) , ( - введенный выше оператор Т. Х(0 -+Y Оператор » непрерывен, пространство Н 2(Г) непрерыв но вложено в С (Г) , и ясно, что мы находимся в условиях теоремы 1.2, а функции " JL , определенные равенством (I.I8), являются следами на і решений задач (4.15). Из теоремы 1.2 следует, что і сходятся к H г(0 . Теорема доказана. 4.3. Скорость сходимости в Н СГ) и С(0 Теорема 4.4. Пусть f є Н (О , п. —г и множества А ч f А 2 , ... образуют сгущающуюся tt- сеть. Тогда для решений задачи (4.15) справедливы асимптотические оценки Параметр S принадлежит интервалу [oy)rc-i Доказательство . Пусть B( V) - единичны: шар в IR. , тогда из неравенства (2.19) следуют соотно- шения справедливые для любой функции U є w (Е (оіУ) , имеющей fi - сеть нулей в шаре 6(0 1) . Простым следствием неравенств (4.21) и (4.22) являются следующие: справедливые для любой функции ueW С 86 1)) , имеющей к- сеть нулей в шаре В (0,1) Пусть функция ги принадлежит W с В 6 1)) , тогда гс лежит в Н (Г) ( 22 J , и справедливо неравенство где Y не зависит от выбора функции VL . Из определения (4.6) следует, что функции f[( \tA принадлежат пространству W С В (0,0) . Предположим, что -и. имеет - сеть нулей на Г . Функции і являются бесконечно d дифференцируемыми, поэтому они удовлетворяют условию Липшица Из определения (4.3) и неравенства (4.26) следует, что функции f; (ct;-i/) имеют И и - сеть нулей в шаре B(07i) , стало быть можно воспользоваться неравенствами (4.23), (4.24) для функций f 6= ; ъ.) . Для всех і 1, у получаем нера венства (4.28) справедливы для любой и.ъ Н лбг) , шлеющей я-сеть нулей на ГДЙЯ„. Воспользуемся определением (4.6) нормы которая эквивалентна норме, определенной равенством (4.5). Из неравенств (4.27), (4.28) и определения (4.29) получаем неравенства справедливые для любой функции а а Н С Г) , имеющей К - сеть нулей на Г Функции (f "-f ) имеют -к - сеть нулей на Г7 , следовательно, справедливы неравенства при целых S . В теореме 4.3 доказана сходимость сплайнов к функции в норме пространства Н 5СГ") , нера-венство (4.25) обеспечивает сходимость ив Н (Т). Следовательно, для целых S сходимость (4.20) установлена.
Сходимость бикубических сплайнов в задаче интерполяции функции на хаотическоей сетке
Для приближенного построения интерполяционного D -сплайна (см. І) в ограниченной области SL воспользуемся методом сплайнов на подпространстве, описанном в работе [ill. Пусть Ь. конечномерное подпространство в V, (1}, тогда интерполяционный сплайн на подпространстве fe определим как решение следующей задачи Наряду с интерполяционным рассмотрим сглаживающий сплайн на подпространстве Е , как решение задачи где A- \ » . ., Eg г Разрешимость задач (7.1), (7.2) имеет место, когда множество А содержит L, -разрешимый на бор. Сходимость сплайнов % , и 4 k К функции 4- при О и сгущении множества А исследована в работах ъ , 6 _ - векторы-столбцы коэффициентов разложения (7.3) и (7.4) _Д - вспомогательный вектор множителей Лагранжа При численной реализации в качестве SL удобно взять К. -мерный параллелепипед, охватывающий точки множества А В качестве конечномерного пространства Ёк выберем пространство полиномиальных сплайнов дефекта I, связанных с равномерной сеткой в области SL . Тогда к имеет базис из 6-сплайнов 17- -сплайны многих переменных являются произведениями одномерных 6 -сплайнов для которых, в свою очередь, можно вывести удобные рекуррентные соотношения (вследствии того, что В -сплайн степени К является сверткой В -сплайна степени к-1 с функцией-ступенью) . Поскольку базис с . у. . , 7 со /-к\ выбран из В -сплайнов, а они локальны, то матрицы А и Т разрежены. Появляется возможность экономно хранить их, организовывать умножение на эти матрицы, что в свою очередь позволяет употребить для решения систем (7.5), (7.6) широкий класс итерационных методов 1 24 (в j 4 избран метод Ланцоша). Укажем некоторые характерные особенности матриц А и Т , а именно особенности хранения и организацию умножения на вектор на примере матрицы А Элементы матрицы А можно вычислить по формуле поэтому главной особенностью матрицы является то, что она многоиндексная Особенностью конечных элементов является, то, что они легко упорядочиваются, так как в (7.9) индексы удовлетворяют неравенствам где А/ N .., д/ - некоторые натуральные числа. Введем ото-бражение многомерных индексов в одномерные по правилу индекс і меняется от І до /VCc) = -П ЛЛ Пусть р указывает степень полиномиальных сплайнов пространства К , тогда носители двух базисных функций со- и со. пересекаются, если индексы -і и I удовлетворяют неравенствам: следует, что элемент х-т і равен нулю, если носители базисных функций со- и ; не пересекаются и,следовательно, из (7.13) вытекает, что в строке матрицы А , соответствующей индексу ъ , возможны только лишь фр+1) ненулевых элементов. Итого, в матрице А может быть не более NCк) х (Лр+1) ненулевых элементов.
Пусть индекс -I фиксирован, тогда на множестве многомерных индексов L , удовлетворяющих (7.13), введем одномерную нумерацию по правилу: Легко заметить, что для фиксированного индекса і значения %У меняются от і до (2р+1) . Используя симметрию матрицы A-0 -} , будем хранить ее в массиве так, что элемент а-« находится в ячейке А [a, - I . Таким образом, мы храним лишь ненулевые элементы матрицы А . Заметим, что не все индексы V , удовлетворяющие неравенствам (7.13), соответствуют какой-либо базисной функции (возможен выход из ограничений (7.II). Поэтому в ячейках А(г,?:. J t с которым не соответствует элемент матрицы С \:) , будем хранить условное число. Умножение на Л .Пусть ос = (х у ..,, сы(1с)) произвольный вектор, a -u =( d ч. , ъ ) - результат умножения на вектор эс : Учитывая способ хранения элементов матрицы А получаем следующую формулу для вычисления вектора Ч соответствует t?" по (7.14). Вторая сумма в (7.16) возникает из-за того, что в массиве А хранится только половина ненулевых элементов матрицы Д вследствии ее симметричности. Суммирование в (7.20) должно производиться только по тем индексам t. , для кото рых Д Ы( ) и значения /\S S- (с э+i) -г 1 не являются условными числами. Заметим, что формулы (7.16) не эффективны для расчета, поскольку необходимо всякий раз ВЫЧИСЛЯТЬ ЧИСЛО I , для чего требуется воспользоваться правилом, обратным к (7.14) и правилом (7.12). Построим более эффективную процедуру. Вычитая из индекса L индекс v получаем: Отсюда следует, что j J =-6+4() , где З- О определяется по формуле: Через -т" обозначено деление нацело. Заметим, что вычислив один раз функцию QC -) при t - 1 (lb+if » можно организовать процедуру умножения на матрицу Д" следующим образом где суммирование идет по индексам X. , для которых 1 + 4Съ) л/ск) и Л[Є5г] , А[б+асъ) , ( ь+±) -О не являются условными числами. Структура матрицы Т аналогична структуре матрицы А , поэтому для нее можно организовать такую же процедуру умножения, как и для А . Однако для матрицы Г можно уменьшить требования на память, поскольку в массиве, соответствующем матрице Т много совпадающих строк, и хранить ее в массиве размера (2.Р+1) /р4- ) Комплект программ PI/VEL , созданный автором диссертации, реализует алгоритм этого параграфа. В приложении приводится краткое описание комплекта . 8. Сходимость бикубических сплайнов в задаче интерполяции функции на хаотической сетке Пусть односвязная область ЛсК. имеет кусочно-гладкую границу, функция с\лС(Л) , hv . Положим Ек , tc є ТУ , последовательность конечномерных подпространств в W 6П), определенная в п.7.1. Пусть А , А & ,... последовательность конечных множеств в SL , образующих сгущающуюся в 4 -сеть. Обозначим через i0ifii) натураль ные числа такие, что V к к0(Л ) множество A L (l\ . П Is" - непусто, т.е. решение задачи (7.1) оп- ределено в любом подпространстве t , К 0Ск ) Из неравенства (2.19) следует оценка погрешности приближений функции f сплайнами \к . В работе 12 показана равномерная ограниченность выражений стало быть, справедлива оценка погрешности приближения сплайна на подпространстве к функции {- . В (8.2) предполагается, что выбор подпространства Ек согласован с мерой густоты -сети, т.е.
В этом параграфе, основываясь на идее -D -интерполянтов с краевыми условиями, будет построен алгоритм интерполяции функции двух переменных и исследована оценка погрешности, которая будет меньше, чем для аналогичных сплайнов без краевых условий. 8.1. Дискретизация задачи Пусть - прямоугольник с границей Г , Г- Г . и П- , где Г . - стороны SL , параллельные оси Ох , Ги - параллельны Ом . Предположим, что заданы значения функции I в точках Р4,... Р области Д 2,\_Г Кроме того известны значения I на Г , значения частной производной 1 по -х. на границе Г , значения „ на Гх , и смешанная производная х задана в четырех угловых- точках прямоугольника JZ . Введем равномерную сетку Л-л х л , где На этой сетке рассмотрим кубические сплайны дефекта I от двух переменных. Множество таких сплайнов обозначим 3„Сд) , его можно рассматривать как тензорное произведение пространств одномерных сплайнов 5.,( А/) и S, (М) размерностей Л/+Z и М + Я соответственно, и размерность 3д) равна Будем говорить, что K(x,v) S3 сд) удовлетворяет усло вию А) для функции Z , если и удовлетворяет условию Б) для функции \ , если Множество функций k S3CA ) , удовлетворяющих условиям А) и Б), будем обозначать Н (. &) Назовем функцию G e S3 0 интерполяционным Л) -сплайном с краевыми условиями, если она является решением задачи Теорема 8.1. Если множество Но( л) непусто, то решение ь задачи (8.3) существует и единственно. Доказательство . Пусть W - множество функций из $ъс& ) , удовлетворяющих условиям А) и Б) для функции і = 0 . Легко видеть, что W - линейное подпространство функций в SJCA") , конечномерное. Пусть kcx,u)-некоторая функция из ЬКС утверждается, что и тем самым Н - конечномерное аффинное подпростран-ство. Действительно, пусть МОх ) = (-L , тогда функция М( х, ц) кс», м) Удовлетворяет условиям А) и Б) для -0 . ТІозтому функция И( , )- Сх7-и) лежит в W и равенство (8.4) установлено. Таким образом, (8.3) является задачей минимизации квадратичного непрерывного функционала на конечномерном аффинном подпространстве М„(й). Такая задача имеет единственное решение если функционал (8.5) не обращается в нуль ни на какой функции из W , кроме нулевой. В ядре функционала (8.5) лежат полиномы вида + + 4 Пространство W таких полиномов не содержит, поскольку линейный многочлен, равный нулю в точках Са с) » (&, ) » (ёуС) сетки А , является нулевым.
