Теория и алгоритмы вариационной сплайн-аппроксимации Роженко Александр Иосифович

Содержание к диссертации

Введение

Глава 1. Элементы функционального и выпуклого анализа 29

1.1. Определения и обозначения 30

1.2. Условия нормальной разрешимости линейного ограниченного оператора 36

1.3. Эквивалентные нормы в банаховых пространствах 39

1.4. Линейная независимость операторов 42

1.5. Наилучшее приближение в выпуклом множестве 44

1.6. Сходимость наилучших приближений 45

1.7. Пространство С\ос(0) на локально-компактном множестве 46

Глава 2. Теория абстрактных сплайнов 49

2.1. Однозначная разрешимость смешанной задачи 53

2.2. Характеризация и операторное представление сплайнов 58

2.3. Разложение сглаживающего квазисплайна 66

2.4. Выбор параметра сглаживания 70

2.5. Представление невязки сглаживающего сплайна в виде суммы ряда 78

2.6. Сходимость абстрактных интерполяционных сплайнов 80

2.7. Сплайны на подпространствах: вариационная постановка и сходимость 88

Глава 3. Алгоритмы построения сплайнов 97

3.1. Воспроизводящее отображение полугильбертова пространства 100

3.2. Структура пространства сплайнов 106

3.3. Алгоритм построения смешанного сплайна 109

3.4. Построение полиномиального сплайна нечетной степени 114

3.5. Построение полиномиального сплайна четной степени 121

3.6. Использование разложения по базису ?-сплайнов 123

3.7. Построение jB-сплайнового разложения полиномиального сплайна 127

3.8. Построение гетерогенного полиномиального сплайна 130

3.9. Построение вариационного L-сплайна 133

Глава 4. Сплайн-аппроксимация функций многих переменных 142

4.1. 1>т-сплайн 145

4.2. Сходимость )т-сплайнов 147

4.3. Алгоритм построения 1)то-сплайна на подпространстве 155

4.4. Сплайны Дюшона 158

4.5. Алгоритм построения аналитического сплайна 163

4.6. Построение аналитического сплайна на вырожденной сетке 169

4.7. Метод наименьших квадратов в сплайн-аппроксимации 177

4.8. Интервальная сплайн-интерполяция 180

Глава 5. Сплайн-аппроксимация в тензорном произведении гильбертовых пространств 194

5.1. Тензорные произведения пространств 195

5.2. Нормально разрешимые операторы в тензорном произведении пространств 201

5.3. Сплайны в тензорном произведении пространств 204

5.4. Тензорные произведения функциональных пространств 210

Заключение 215

Литература 217

Приложение

• Эквивалентные нормы в банаховых пространствах
• Характеризация и операторное представление сплайнов
• Сходимость абстрактных интерполяционных сплайнов
• Построение полиномиального сплайна нечетной степени

Введение к работе

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

Принято считать, что теория сплайнов берет свое начало с работы Шёнберга [115], в которой было введено понятие сплайна как функции одной переменной, "склеенной" из кубических многочленов. На основе этого приема были предложены различные варианты аппроксимаций: полиномиальные сплайны высоких степеней, тригонометрические сплайны, L-сплайны. Рассматривались также сплайны с разнородными условиями интерполяции (гетерогенные сплайны) и различными типами краевых условий [12, 27, 69, 70, 117]. Усилиями зарубежных и советских авторов (Алберг, Нилсон, Уолш, B.C. Рябенький, Ю.С. Завьялов, СБ. Стечкин, Ю.Н. Субботин и др.) были получены оценки сходимости таких сплайнов к функциям различной гладкости с привлечением различных типов краевых условий и способов сгущения сетки. Задача одномерной полиномиальной сплайн-интерполяции была обобщена на многомерный случай интерполяции на прямоугольных сетках [1, 82, 27, 40].

Принципиально новый виток развития теории сплайнов начался с работы Холлидея [91], в которой был найден вариационный принцип для кубического сплайна. Аттья в [74, 75] обобщил понятие сплайна, рассматривая его как решение задачи аппроксимации в гильбертовом пространстве, минимизирующее некоторый выпуклый функционал типа полунормы. Новый подход оказался весьма продуктивным. Были получены в общей форме условия существования, единственности и характеризации сплайнов [41]; найдены вариационные принципы для биполиномиальных интерполяционных и сглаживающих сплайнов [24-26, 30]; разработаны алгоритмы построения сплайнов методом воспроизводящих ядер [76, 96]; доказаны общие теоремы сходимости сплайнов [13, 92]; показана связь между сплайнами и оптимальными в смысле Сарда аппроксимациями линейных функционалов [112, 116]; выявлена тесная связь сплайнов с теорії-

Введение

ей поперечников [36] и теорией регуляризации некорректно поставленных
* задач [50].

Следующий важный шаг в развитии теории сплайнов был сделан Дю-шоном [86-89]. Он исследовал задачу построения І)^ш-сплайна в Rn с произвольно расположенными узлами интерполяции, а также получил алгоритм и оценки сходимости такой интерполяции. С этого момента берет свое начало теория сплайнов многих переменных на хаотических сетках. Отметим в этой связи работы А.Ю. Бежаева и В.А. Василенко [79-81], О.В. Матвеева [43-46], М.И. Игнатова и А.Б. Певного [29], Пауэла [102], Мэдича и Нельсона [98-100], Шабака и By [114], Лайта и Вейна [95].

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

Для изложения результатов нам потребуются некоторые обозначения
используемые в работе (более полно все необходимые обозначения вводят-
ся в гл. 1, а также частично в других главах). Через X, Y, Z обознача
ем гильбертовы (иногда банаховы) пространства. Используем обычные
обозначения для скалярного произведения и нормы в X: {-,-)х ^и || * ||х-
Нижний индекс часто опускаем, если понятно из контекста о каком ска
лярном произведении или норме идет речь. Через А Є L(X, Y) обозначаем
линейный ограниченный оператор А, действующий из X bY. Его ядро и
образ обозначаем через N(A) и R(A) соответственно. Важную роль в те
ории сплайнов играют нормально разрешимые операторы, т.е. такие, что
R(A) замкнутое подпространство. Полунорму ||Лж||у, порожденную опе-
,^ ратором А, обозначаем также через ||ж||л- Аналогичные обозначения ис-

пользуем для скалярного произведения. Прямая сумма XY пространств X и Y есть пространство пар вида х фу с покомпонентным сложением и умножением на скаляр. В X У естественным образом вводится р-норма:

ІІ*ву||х.у = (||*|& + ||»||Н^І/'.

Обычно используем 2-норму. Прямая сумма операторов А : X —> У" и
В : X -> Z есть оператор AqB'.X-^YQZ, действующий по правилу:
(А ф В)х = Ах Вх. 2-норма, порождаемая прямой суммой операторов,
⁽* имеет вид

Введение

Млев = (IMIi + МІГ² = (ЯМІ + \\Bx\\%f\

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

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

Теоретические исследования автора содержатся в гл. 2, 4, 5. Практические аспекты иследований автора сконцентрированы в гл. 3, 4.

Начнем с теоретических результатов.

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

сг_а = arg min а||Тж||² + ІІЛ^ж — ^2ІІ², (0.1)

где Г Є L(X, Y), Ai Є L(X, Zi), A^ Є L(X, Z2), все пространства гильбертовы, z\ Є R(Ai), zi Є ^2) ск > 0 - параметр сглаживания. Данная задача объединяет в себе задачи интерполяции (А\ = А, А2 = 0) и сглаживания (Лі = 0, Л.2 = А). Постановка (0.1) была предложена А.Ю. Бежаевым и В.А. Василенко [80]. В этой же работе приведены условия однозначной разрешимости задачи (0.1) в практической ситуации конечномерности ядра N(T) оператора Т, получено условие характеризации и система операторных уравнений для смешанного сплайна. Автор продолжил эти исследования и доказал теорему о необходимых и достаточных условиях однозначной разрешимости задачи (0.1):

Теорема 2.1.3. Пусть оператор Т нормально разрешим (R(T) замкнуто б Y). Тогда следующие утверждения эквиваленты:

(а) существует оператор В Є L(X, W), действующий в некоторое
гильбертово пространство W, такой, что N(Ai) С N(B) и норма
Н^ж1|гвл₂ ⁼ (||^^ж1|²+ Н^^ж1|² + 1И2Сс||²) ' эквивалентна норме ЦягЦх/

(б) смешанная задача (0.1) однозначно разрешима при любых z\ z^ Є
Д(Лі) Z₂;

Введение

(в) задача и = arg min а\\Ти —f\\²-h\\A2U — g\\² однозначно разрешима

uGN(Ai)

при любых f ф g Є Y ф ^2/

(г) на подпространстве N(A\) нормы || ||тел₂ ^w || * ||х эквивалентны.

Данная теорема обобщает результаты П.-Ж. Лорана [41, теоремы 4.4.1-4.4.4] на смешанный случай.

Доказательство этой теоремы, а также других утверждений о смешанных сплайнах базируется на технике сведения задачи (0.1) к эквивалентной задаче наилучшего приближения в выпуклом множестве. В этом заключается отличие предлагаемого метода доказательства от методов, используемых другими авторами (данная методика близка к методике, используемой в работах В.А. Морозова [48, 50]).

В основе этой техники лежит следующая теорема об эквивалентных нормах в банаховых пространствах, доказанная автором:

Теорема 1.3.3. Справедливы утверждения:

(а) если нормы ]| \\ав ^и || ||х эквивалентны, то N(A) П N(B) — {0}
и N(A) + N(B) замкнуто;

(б) если на подпространстве N(A) нормы \\ \\в и \\ \\х эквивалентны
и R(A) замкнуто, то нормы || \\а@в ^и \\ ||х эквивалентны;

(в) если R(A), R(B) и N(A) + N(B) замкнуты и N(A) П N(B) = {0},
то нормы || ||лев и || \\х эквивалентны;

(г) если R(A) замкнуто, N(A) конечномерно и N{A)C\N(B) = {0}, то
нормы || \\ав ^и || ||лг эквивалентны.

2. Ясно, что любой сглаживающий сплайн является интерполяционным для некоторого другого вектора измерений z. В монографии П.-Ж. Лорана [41, теорема 4.6.4] рассматривается и обратная задача: пусть имеется интерполяционный сплайн и задано а > 0; существует ли вектор 5, для которого этот сплайн является сглаживающим. Обозначая через А⁺ и А+ операторы, сопоставляющие вектору z Є R(A) интерполяционный и сглаживающий сплайны соответственно, данную задачу можно сформулировать так: совпадают ли образы операторов А⁺ и А+? Ответ на этот вопрос

Введение

положительный. Множества интерполяционных и сглаживающих сплай-
'fc нов при фиксированном А совпадают и образуют пространство сплайнов

Spl(.A) С X, характеризующееся условиями

VueN(A) (Тх,Ти) = 0.

Автор ставит аналогичный вопрос об операторе А, сопоставляющем
.ф вектору z = ziZ2 Є R(Ai) ф Z₂ сплайн а_а - решение задачи (0.1). Ответ

на этот вопрос дает следующая теорема, предлагающая также способ продолжения оператора A + на все пространство Z\ ф Z₂\

Теорема 2.2.10. Пусть R(T) и R(Ai) замкнуты и задача (0.1) однозначно разрешима при любых допустимых исходных данных. Обозначим А = Аі ф А₂. Тогда:

(а) A* : R(A\) ф Z₂ —> Spl(A) - линейный ограниченный оператор;

(б) оператор А+ удовлетворяет тождеству

to-

A+z = A+Vz, (0.2)

где V - ортопроектор на R(Ai) Ф R(A₂), z = z\ Ф z₂ Є і?(^4і) Ф Z₂;

(в) оператор А непрерывно продолжается по формуле (0.2) на все пространство Z = Z\ 0 ^2, nmo соответствует замене задачи (0.1) wa задачу

д_а = arg min «ll^dl² + \\А₂х — z₂\\²',

W (г) если (Т, Л) - сплайн-пара и операторы А\ и А₂ линейно независимы

(R(Ai 0 А₂) = R{Ai) ф R(A₂)), то сужение оператора А+ на R(A) есть непрерывный изоморфизм между R(A) и Бр\(А).

Пару (Г, А) здесь и далее называем сплайн-парой, если R(T), R(A) и N{T) + N(A) замкнуты, N(T) П N(A) = {0}.

Пункт (г) этой теоремы можно выразить словами так: если (Г, А) -
сплайн-пара и операторы А\ и А₂ линейно независимы, то любой элемент
пространства сплайнов Spl(-A) является смепіанньїм сплайном при любом
,* а > 0 и подходящем (однозначном) выборе z Є R{A).

Введение

«є

3. Задача смешанной сплайн-аппроксимации изучалась автором также в контексте сплайнов на подпространстве. В.А. Василенко назвал сплайн, построенный методом конечных элементов, сплайном на подпространстве [14].

Пусть {^_г}_г>о - семейство замкнутых подпространств в X. Смешанным сплайном на подпространстве Е_Т называется решение задачи

oj = arg min а\\Тх\\² + \\А₂х - z₂\\². (0.3)

Здесь предполагается, что Аї¹{х{) П Е_т ф 0, т.е. условия интерполяции А\х = z\ не противоречивы на Е_т.

Введем эквивалентную норму || ||* = || \\_у/бтва₂ ^п0 теореме 2.1.3, возьмем ортопроектор Р_т на Е_т в норме || ||* и введем оператор сплайн-интерполяции S:

Su = arg min а||Тж||² + \\А₂х\\².

Axx—A\u

Автор доказывает следующую теорему сходимости сплайнов <т„ к сг_а:

Теорема 2.7.9. Пусть подпространства Е_Т предельно плотны в X при т —> 0 и найдется такое tq > 0, что при т < 7 R(AiP_T) = R(Ai) и выполнено одно из условий:

(а) dim R(A\) < со;

(б) ||(7-Р_т)5||.<С7<1.

Тогда ||5 — а_а\\х при т -> 0.

Доказательство этой теоремы базируется на доказанной автором теореме о сходимости наилучших приближений в замкнутых выпуклых множествах. Пусть М С X - замкнутое выпуклое множество и Рм ' X —» X -оператор, сопоставляющий каждому элементу / Є X наилучшее приближение h Є X на множестве М по формуле Рм/ = Л, = argmin^M \\х — /||².

Теорема 1.6.1. Пусть Мі С X - непустые замкнутые выпуклые множества и fi X - некоторые элементы, і Є IN. Предположим, что fi—tf при г —> оо и множества Мі удовлетворяют одному из условий:

Введение

(а) M_i+1 С Мі и П М_г = М;

»1N

(б) Мі С М и существует последовательность Х{ Є М», сходящаяся к

Тогда последовательность hi = PmJi сильно сходится к h — Рм/, т.е. \\Ы — h\\x -) 0 при г -> оо.

4. Следующая тема исследований автора - выбор параметра сглаживания а при построении сглаживающего сплайна

а_а = argmin а||Тж||² + \\Ах - zf. (0.4)

Задача сглаживания исследовалась многими математики, начиная с Райн-ша [103, 104]. Мы ограничимся здесь только исследованиями поведения сглаживающего сплайна при изменении а и алгоритмом, базирующемся на критерии невязки (см. монографию В.А. Морозова [50]). Работы автора в этом направлении [108, 61, 63] содержат несколько новых результатов. Предположим, что (Г, А) - сплайн-пара, и введем скалярное произведение

(и, v)„ = {щу)_ТфА = (Tu,Tv)_Y + {Au,Av)_z,

порождающее эквивалентную норму в X. Представим пространство X в виде

X = N(A) 0 N(T) Х, Х = (N(A) + N(T))±, (0.5)

где ортогональное дополнение берется относительно скалярного произведения (, )*.

Теорема 2.3.3. Пусть (Т, А) - сплайн-пара и операторы А*, Т* сопряжены к А, Т относительно скалярного произведения (, )*. Тогда:

(а) операторы А*А и Т*Т перестановочны, причем А*А + Т*Т = їх;

(б) разложение (0.5) приводит операторы А*А и Т*Т к виду

А*А(щ + и₂ + из) = Ощ_А)Щ + 1щт)Щ + Ли₃, Т*Т(щ + и₂ + щ) = 1щ_А)Щ + Ощ_Т)и₂ + Тщ,

где щ Є N(A), и₂ Є N(T), щ Є X;

Введение

(в) А,Т Є L(X) -перестановочные, самосопряженные, положительно определенные изоморфизмы, А-\-Т' = їх, \\Л\\ < 1, \\Т\\ < 1.

Здесь через 1у и Оу обозначены тождественный и нулевой операторы bV.

Теорема 2.3.4. Рассмотрим задачу построения сглаживающего квазисплайна

а_а = argmin а\\Тх — у\\² + \\Ах — z\\².

Положим

o-qo = are min \\Ax — z\\², сто = arg min \\Tx - y\\².

xu(A*A)-^l(A*z)

Тогда: gq — (7^ Є X; o_a = q_a = gq + r_a, причем q_a и r_a принадлежат X и определяются из уравнений

(I + aA~^lrr)qa = qo = o-Q- a^, (I + a~^lT~^lA)r_a = Гоо = о-,» - cr₀.

Из теоремы 2.3.4 легко выводится сходимость сглаживающего квазисплайна сг_а к предельным элементам ctq и егдо с оценками 0(a) и 0(а~¹) соответственно, причем при ctq ф (Too эти оценки не улучшаемы по порядку [63]. Факт сходимости квазисплайна о_а к предельным элементам хорошо известен (см., напр., [50]). По-видимому, была ранее известна и оценка сходимости сплайна о~_а к <то со скоростью 0(a), хотя в [17, 50] получена только оценка 0(а¹1²).

Один из методов выбора параметра сглаживания в задаче (0.4) заключается в решении уравнения <р(а) = \\Аа_а — z\\ = є относительно а. Это уравнение называют критерием невязки. В работе В.И. Гордоновой и В.А. Морозова [23] предлагается выбирать параметр сглаживания, решая эквивалентное уравнение

ГІР) = є', (0.6)

где /3 = а^-1, ф(/3) = <р(а). Если ^(0) ф VK⁰⁰)? то ф³(Р) при s > 0 -строго монотонно убывающая выпуклая вниз функция, при — 1 < s < 0 -

Введение

строго монотонно возрастающая выпуклая вверх функция, и скорость сходимости метода Ньютона максимальна при s = — 1.

Автору удалось получить формулу шага метода Ньютона для решения уравнения (0.6) при s = — 1 в терминах оператора невязки R_az — z — Ао~_а:

Теорема 2.4.4. Итерация метода Ньютона для решения уравнения (0.6) при s = — 1 имеет вид

1-и>(а_А) , . {R_az,R²_az) (R_az,R²_az)

(р(ос_к)/є-ш(а_к) (R_az,R_az) (p^l{a)

Данная теорема дает возможность построения универсального алгоритма выбора параметра сглаживания. Этот алгоритм реализован автором в библиотеке программ JSpline+ [93].

Интересное применение имеет полученная автором формула дифференцирования оператора невязки R_a:

Лемма 2.4.3. Для оператора невязки R_a Є L(Z), задаваемого правилом R_az — z — Acr_a = (I — AA*)z, имеет место следующая формула дифференцирования по параметру а:

D^kR_a = (_i)*+i^Д(/ - R_a), к > 1.

На основании этой леммы с привлечением теоремы 2.3.3 автору удалось доказать следующую теорему о разложении невязки:

Теорема 2.5.1. Пусть «о > 0. Тогда невязка z — Аа_а представима в виде суммы ряда

[_k=0\ а₀ і абсолютно сходящегося на отрезке [0,2«о]

Аа_ао, (0.7)

Похожее разложение (только самого сплайна а_а, а не невязки) рассматривалось ранее А.Ю. Бежаевым. Так в [80, Theorem 12.10] доказана сходимость разложения сплайна сг_а в ряд Тейлора, но на открытом интервале (0,2ао). Автору в теореме 2.5.1 удалось расширить интервал сходимости ряда для Аа_а и явно представить разложение по степеням оператора R_a.

Введение

Автором также исследовано поведение сплайна <т_а вблизи бесконечно-
щ сти. Полагая Qp = I — Ri/p, получаем точно такие же правила дифферен-

цирования оператора Qp по j3 как в лемме 2.4.3, из которых, с привлечением теоремы 2.3.3, выводится следующая

Теорема 2.5.3. Пусть / > 0. Тогда невязка Z ~~ Aaijp представимо, в виде суммы рлда

* г - Аа_т = \ Е (¹^] (* - М/а), (0-8)

Ц=о^ч A) ^J \

абсолютно сходящегося на отрезке [0,2/].

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

шаге метода.

Теоремы 2.5.1, 2.5.3 дают возможность построения более эффективного алгоритма выбора параметра сглаживания за один шаг: выбираем начальный коэффициент сглаживания ао; выполняем один раз построение и декомпозицию матрицы сплайновой системы; анализируем, с какой стороны от решения находимся и в зависимости от этого используем разложение (0.7) или (0.8) для поиска параметра сглаживания. При этом потребуется рассчитать начальный отрезок достаточной длины от соответствующего ряда, получить формулу вычисления невязки (квадрат

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

5. Задачи сплайн-аппроксимации функций многих переменных

представляют как теоретический, так и практический интерес. Теоре
тические вопросы включают в себя проверку корректности (однознач
ной разрешимости) задачи сплайн-аппроксимации, доказательство сходи
мости интерполяционных сплайнов и получение оценок сходимости. Ав-
Л" тор ограничивается только случаем, когда аппроксимируемая функция

Введение

принадлежит пространству, в котором ищется сплайн. Более общие конструкции (продолжение оператора сплайн-интерполяции в банаховы пространства и оценки сходимости) рассматривались, например, в работах О.В. Матвеева [43, 44].

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

Построение сплайна методом конечных элементов (сплайны на подпространствах в терминологии В.А. Василенко). Здесь различаются два варианта построения конечных элементов: когда носители конечных элементов строятся на основе сетки узлов интерполяции и когда носители не связаны с сеткой. Второй вариант предпочтительнее, поскольку мы не можем выбирать сетку узлов интерполяции, а значит не можем гарантировать качественную триангуляцию области определения функции если используем сетку узлов интерполяции как основу для построения конечных элементов (в этом отличие МКЭ для сплайнов от МКЭ в задачах математической физики).

Аналитические методы, использующие представление сплайна через воспроизводящее ядро полугильбертова пространства (X, || \\т)-Пример таких сплайнов - сплайны Дюшона. Ограничения данного подхода: воспроизводящее ядро известно только в частных случаях.

Построение сплайна на регулярной сетке, являющейся прямым произведением одномерных сеток. Это сплайн-аппроксимация в тензорном произведении пространств.

6. )^т-сплайны в произвольной области представляют в основном теоретический интерес. Задача >^т-аппроксимации обычно рассматривается либо в области с липшицевой границей, либо в Я_п. Автор в [58] распространил постановку задачи Х)^ш-аппроксимации на произвольную область в Rn. При этом в качестве X надо брать L(Q) - пространство функций в ГІ, m-e частные производные которых интегрируемы с квадратом.

Доказательство сходимости )^т-сплайнов в произвольной области получено .автором. Ранее В.А. Василенко было доказано [80], что если область О, ограничена и имеет липшицеву границу, то при произвольном

Введение

способе сгущения конечных є-сеток в fi 1)^т-сплайны, интерполирующие функцию / Є W^fi), сходятся к / в норме пространства W^fi). Автору удалось убрать все ограничения, выделенные в предыдущем предложении курсивом, и доказать следующую теорему:

Теорема 4.2.3. Пусть последовательность множеств {ш{ С и? П S1}jgbst предельно плотна в и, т > п/2 и f Є L^) - интерполируемая функция. Тогда последовательность интерполяционных сплайнов 0{ — S_WJ сходится к сплайну a = S_uf в норме пространства Ь(П).

Здесь S_u — оператор, сопоставляющий функции / Є 1^(0.) интерполяционный )^т-сплайн а с условиями интерполяции cr(t) = f(t), t Є w.

Данная теорема есть следствие другой, более общей теоремы, доказанной автором в [107, 61]:

Теорема 4.2.2. Пусть fi С Rn ~ локально-компактное множество, X непрерывно вложено в Cio_C(fi) при некотором 0 < а < 1. Предположим, что оператор Т Є L(X, Y) имеет конечномерное ядро и замкнутый образ; множество w С П содержит L-набор точек для N(T); последовательность множеств {ш{ С ШПГ2}і_Єдо предельно плотна в и. Тогда найдется такое число г'о > 0, что при і > г'о задача

о і = argmin{||Tz||², х Є X, x(t) = f(t), t Є 0}

однозначно разрешима и последовательность {оу} сходится в норме пространства X к

а = argmin{||T:r||², х Є X, x(t) = /(і), t Є и}

при г —> со.

Здесь Cfo_c($l) - пространство непрерывных функций в fi, локально удовлетворяющих условию Гельдера с параметром 0 < а < 1. Множество fi С Rn назовем локально компактным, если для любой точки t Є Q найдется компактная относительная окрестность fit этой точки в П. В свою очередь, множество fit С fi называют относительной окрестностью точки t в П, если существует множество Dt С Rn - окрестность точки t в Rn, такое, что fi_t = D_tC\ fi.

Введение

Замечание. Замкнутые и открытые множества в Rn являются локально
«I компактными. Автор в 1.7 дает эквивалентные определения локально-

компактного множества и доказывает, что пространство Ci_oc(^) функций, непрерывных в П, является пространством Фреше.

Теорема 4.2.2, в свою очередь, выводится из теоремы о сходимости

интерполяций на сгущающемся семействе функционалов, усиливающей

теорему В.А. Василенко о сходимости на сгущающихся є-сетях (ср. [80]).

Пусть Г2 С Rn - некоторое множество, и задано параметрическое семейство функционалов Ф(П) = {(pt Є X', t Є ГХ}. Далее, пусть cv -некоторое подмножество Q, и / 6 X - произвольный элемент. Положим

M(f,u>) = {х Є X : cp_t{x) = _t{f), t Є и)}.

Автором доказана в [107, 61] следующая

Теорема 2.6.7. Пусть N{T) конечномерно, множество Ct локально-компактно и семейство функционалов Ф(П) непрерывно по параметру, т. е. \\_s — (pt\\x' -* 0 при ^s —* і) s,i Є П. Пусть также задача

^{а = arg} Л»? ч и^гя?и²

однозначно разрешима.

Тогда если последовательность множеств {ші С о7ПП}геж предельно плотна в ш, то существует такое г'о Є IN, что при і > г'о задача

U{ = arg min ||Тя;||²

однозначно разрешима, и ||ст,- — о~\\х —> 0 npw і —> оо.

7. Оценки сходимости Г>^т-сплайнов в ограниченной области с лип-шицевой границей были получены А.Ю. Бежаевым в [4] в виде

\\D^kx\\_Lp(n) < Ch^m-^k-ⁿ^ⁿ^\\D^mx\\_L2{ii) (0.9)

при р>2 ж т — к — п/2 -f п/р > 0 (т — к — п/2 > 0 при р = оо). Здесь

х Є Ь(0,) - произвольная функция, имеющая h-сеть нулей в П и констан-

? та С > 0 не зависит от ж и выбора /і-сети. Автор в [58] распространил эти

Введение

оценки на ограниченные области, удовлетворяющие слабому условию конуса (в частности, на области с разрезами, выколотыми точками, острыми пиками, направленными внутрь), а в [61] - на (возможно неограниченные) области являющиеся объединением конечного числа областей типа Ь (удовлетворяющих слабому условию конуса и допускающих продолжение за пределы области с сохранением класса гладкости). В работах О.В. Матвеева [43, 44], получен более широкий спектр оценок сходимости І)^то-сплайнов в различных метриках, однако рассмотрение ограничивается только областями, удовлетворяющими сильному условию конуса.

8. Сплайны Дюшона. Французский математик Дюшон предложил в [87] сплайны, являющиеся обобщением -О^т-сплайнов в ^(Rn). Он рассмотрел пространство D~^mH^r(Rn), состоящее из обобщенных функций, ттг-е производные которых принадлежат "почти Соболевскому" классу ^^Г(Л_П) функций умеренного роста с ограниченной полунормой

ч1/2

Ы\нг=(!_Кп\т\^2г\Гх\*<1т) ,

которая при г < п/2 является нормой. Здесь Т - преобразование Фурье. Воспроизводящее ядро пространства D~^mH^r{R_v) относительно полунормы || |І)ш есть радиальная базисная функция

\s — |²⁷ln|s — t\, 7 - целое,
\s — t\²⁷ иначе,

где 7 = m + r — n/2, 0 < 7 < ra, [7] - целая часть 7, a

1/2

G₇(M) = (-1)^W+1 <

(n \

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

- /)||ь,(П) < Ch-^k-»'²⁺ⁿ'*\\_h - f\\_wm,

если П - ограниченная область, удовлетворяющая слабому условию конуса, s > п/2, s - к - п/2 + п/р > О, р > 2 [114, 95].

Введение

9. Задачи сплайн-аппроксимации в тензорном произведении
Ф гильбертовых пространств обычно рассматриваются на прямом про-

изведении сеток. Это хорошо известные задачи биполиномиального восполнения [1, 24-27, 30]. Такие сплайны, называемые тензорными, достаточно легко строятся: алгоритм редуцируется к сериям одномерных задач. Наряду с задачами, имеющими тензорную природу (параллелепипедаль-ные сетки узлов интерполяции), можно рассматривать и задачу в тензор-ном произведении пространств с произвольной сеткой узлов интерполяции. Для этого необходимо построить нормально разрешимый оператор, чтобы использовать его в энергетическом функционале.

Следуя В.А. Морозову [48], назовем операторы А и В взаимно дополнительными, если оператор А Ф В порождает эквивалентную норму в X. Будем также называть оператор А дополнительным к В (В дополнительным к А), если А и В взаимно дополнительны.

Рассмотрим тензорное произведение гильбертовых пространств X = Xi.. .Х_п. Автор доказал следующую теорему о нормально разрешимом операторе в X:

Теорема 5.2.3. Пусть Xi, Yi, W{ - гильбертовы пространства, Ті Є L(Xi,Yi), Ві Є L(X{,Wi) - некоторые операторы, і — 1,...,п. Если операторы Ті нормально разрешимы и операторы В{ дополнительны к Ті, то оператор Т = [(Ті фВ\) ... (Т_пфВ_п)] Q [В\ <8>... В_п] нормально разрешим и N(T) = N(Ti) ... N(T_n).

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

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

Операторы Т Є L(X,Y) и Б Є L(X,W) назовем строго взаимно дополнительными, если они взаимно дополнительны и линейно независимы. Это означает, что пространство X разлагается в прямую сумму

Введение

N(T) + N(B), а операторы T и В нормально разрешимы.

Пусть 7 ^_ воспроизводящее отображение пространства (X, || \\т) и тг -воспроизводящее отображение пространства (X, || ||в). Возьмем проектор Р Є 1/(Х) со свойствами: N(P) = N(T), R(P) = N(B). Построим двойственный ему оператор Р' Є L(X') по правилу (Р'(р)(х) — (р(Рх), х Є X, (р Є X'. Рассмотрим также проектор Q = І—Р и двойственный ему оператор Q'. Через U⁰ обозначаем аннулятор подпространства U С X, т.е. подпространство линейных функционалов из X', равных нулю на U.

Автор доказывает следующую теорему о регуляризованном воспроизводящем отображении:

Теорема 5.3.5. Регуляризованное воспроизводящее отображение -у = P'jP' + QttQ' удовлетворяет следующим условиям:

(а) \/tp Є N(T)\ хЄХ (Вх,В^уср) = 0;

*

(б) У ер Є N(B), хеХ {Тх, Tjip) = 0;

(в) -у ~ воспроизводящее отображение (X, || \\т)\
/ (г) 7 ~~ воспроизводящее отображение (X, || ||в);

(д) 7 ~ воспроизводящее отображение (X, || ||тв);

(е) отображение -у непрерывно, симметрично и действует на все про
странство X.

Пусть теперь Xi, Yi, W{ - гильбертовы пространства, Т{ Є L(Xi,Y_t)
и В{ Є L(Xi, W{) - строго взаимно дополнительные операторы, 7» Є
1»(Х_г-, Х_г) - регуляризованные воспроизводящие отображения относитель-
^ HO (Xi, || ||т,, || ||в.), г = 1,. . . , П.

Теорема 5.3.7. Отображение у = 71 7п является воспроизводящим отображением пространства X = Xi Х_п относительно нормы, порожденной оператором Т — (Ті jBi) ... (Т_п ф 5_n), гі относительно полунормы, порожденной оператором Т = Т в [#i ... J5_n].

На этом собственно круг теоретических исследований автора заканчи
вается. Перейдем к практическим исследованиям, посвященным алгорит-
» мам построения сплайнов.

Введение

10. Центральное место в практических исследованиях автора занимает алгоритм построения смешанного сплайна с весами. Пусть А\ =

(fi ф ... Ф <рмj -А-2 = Ум+1 Ф Ф и функционалы у>г Є -X⁷, г = 1,..., N, линейно независимы. Предположим, что образ оператора Т замкнут, ядро конечномерно с базисом щ,... , гг#- и операторы Т и А = А\ ф Аг порождают эквивалентную норму в X.

Пусть гильбертово пространство X непрерывно вложено в C\_oc(i), О С Rn, G(s,t) - воспроизводящее ядро пространства X относительно полунормы || Цу. Рассмотрим задачу

>і(б-а) = 2ї, г = 1,..., М,

i=M+l ^Х

построения смешанного сплайна с весами р_г > 0. Решение этой задачи имеет вид

N К

^a(s) = 53 ^mG{s, -) + 53 /W(s).

г=1 г=1

Векторы неизвестных коэффициентов Л = (Лі,..., \n)^T> № = (а*ъ ---5 А⁴*:)⁷ находятся из невырожденной системы линейных уравнений

С + аР U\ (\\ (z\ ,_плп.

* о) („)-(о)- ^(ai0)

где С ж U - NxN- и ЛГхііГ-матрицьі с коэффициентами

cij = ip_tщ_к = <рі{щ), г, j = 1,..., АГ, к - 1,..., К

[ірі действует на G по переменной s, a диагональная матрица с коэффициентами

0 при і = 1,..., М,

Рг При І = М + 1, . . . , N.

Отметим, что коэффициенты вектора Л не зависят от выбора воспроизводящего ядра G (хотя это ядро и неединственно, но при замене его на другое воспроизводящее ядро в решении изменяются только коэффициенты вектора /і).

Введение

Систему уравнений (0.10) можно преобразовать к системе меньшего
Л размера с симметричной положительно-определенной матрицей, если по-

строить некоторый линейный оператор Н : R^N —> R^N~^K так, чтобы выполнялось условие N(H) = R(U).

Теорема 3.3.6. Смешанный сплайн а_а имеет вид

N-К К

¹ і=1 г=1

где фі = T,f₌i hij(fj, і = 1,..., N — К.

Вектор v находится из системы уравнений

A_av = Hz (0.11)

с симметричной, положительно-определенной матрицей А_а = А 4-
аНРН*, причем матрица А = НСН* симметрична и положительно
определена. Коэффициенты матрицы А не зависят от выбора воспро-
^ изводящего ядра G и задаются формулой а^ = (фіЄ,^С)т = (wi,Wj)y,

причем функции W{ = TtJjiG Є Y также не зависят от выбора воспроизводящего ядра.

Сплайн а_а удовлетворяет условиям интерполяции с вектором z_a = z — ctPH*v, а вектор неизвестных коэффициентов /2 можно найти из условий интерполяции Аа_а = z_a и представления Та_а = T.f^{^K fi^i, либо из системы уравнений U/л = z — (С + aP)H*v.

Преобразование системы (0.10) к виду (0.11) хорошо известно. Обычно в качестве Н берется разреженная матрица конечных разностей, постро-

ф- енных на достаточном количестве L-наборов узлов. Еще используются

построения с шаблонами, число узлов в которых на единицу больше [101]. Автор предложил иной метод, основанный на чисто алгебраических преобразованиях системы (0.10) к виду (0.11). Этот метод был реализован Д.С. Кротовым [38] под научным руководством автора. Отметим также, что аналогичный подход практически в то же время был предложен Ша-баком [113].

Идея предложенного автором алгоритма заключается в построении матрицы Н в виде J2Q, где матрица Q приводит матрицу U к верхне-тре-

^ угольной матрице с помощью, например, ортогональных преобразований,

Введение

а матрица J2 понижает размерность вектора, отбрасывая его первые К
щ компонент (см. 4.5). Отметим, что использование ортогональных пре-

образований оптимально в смысле сопсЬ, а именно, число обусловленности сопсЬА матрицы А совпадает с числом обусловленности оператора ТС\щщі-, являющегося сужением оператора VC на подпространство R(U)^L, где V - ортопроектор на Я(С)^Х [62].

В практических задачах трудно гарантировать, что узлы сетки распо-
^ ложены "хорошо". Может возникнуть ситуация неединственности регле-

ния из-за вырождения сетки (например, сетка узлов попала в некоторое собственное афинное подпространство в И„). Автор в [62] распространил предложенный алгоритм на случай вырождения сеток (см. п. 4.6.4). Для этого он разработал алгоритм модифицированного Q-R-разложения, позволяющий вычислять нормальное псевдорешение систем уравнений с прямоугольной матрицей. Этот алгоритм реализован под руководством автора в библиотеке JSpline+ [93].

$" 11. Классические методы построения интерполяционного, сглаживающе-

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

Интересный подход к решению больших задач использовался А.Ю. Бе-жаевым в комплекте программ LocalGreen в [97]. Исходное "облако" точек с помощью последовательной дихотомии гиперплоскостями разбивается на перекрывающиеся подмножества приемлемого размера (порядка 1000 узлов вместо исходных сотен тысяч), в которых осуществляется сплайн-аппроксимация. Затем полученные решения в подобластях "склеиваются" с помощью разбиения единицы, т.е. выполняется композиция сплайнов (оценки сходимости метода композиции сплайнов получены Д.С. Кротовым [37] под руководством автора диссертации). Отметим также эксперименты М.И. Игнатова и А.Б. Певного [29] с регулярным разбиением множества узлов на подмножества для двумерной задачи.

Отметим также другую специфическую черту больших задач: измере-

_ы ния интерполируемой функции обычны неточны и иногда противоречивы.

Введение

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

низкая, поэтому в базис часто добавляют радиальные функции (нейрон
ные сети типа РБФ [51]). Функцию G(s,t) называют радиальной, если
G(s, t) = g(\s —1\). На функцию G(s, t) дополнительно накладывается тре
бование условной положительной определенности [102]. Это означает, что
G есть воспроизводящее ядро некоторого полугильбертова пространства
*~ функций [98, 99]. Например, в качестве G можно брать воспроизводящее

ядро сплайна Дюшона. Сплайн Дюшона можно также относить к нейронным сетям типа РБФ, но здесь есть существенное отличие, а именно, сплайн содержит полиномиальную добавку и коэффициенты сплайна дополнительно удовлетворяют условию ортогональности.

Идея использования метода наименьших квадратов в сплайн-аппро-оксимации не нова. Она предлагалась еще де Бором [83] для приближения функции одного переменного с помощью линейной комбинации В-сплайнов. Такой способ дает приемлемые результаты, если в сетке узлов измерений нет больших пропусков. В противном случае в промежутках между узлами интерполяции будут "провалы", что приведет к плохим результатам.

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

Формально, пусть в Rn задана сетка узлов интерполяции uj_s = {s^Li и некоторая сетка узлов LOt = {tj}f=i- Будем искать сплайн

a(s) = XjGis, tj) + _m(s), (0.12)

удовлетворяющий условиям ортогональности

Ё XjUiitj) = 0, і = 1,...,К, (0.13)

и минимально квадратично уклоняющийся от условий интерполяции
_щ) a(si) = Z{, і = 1,..., М. (0-!4)

Введение

Здесь щ - базисные функции N(T).

Данная задача есть задача наименьших квадратов с линейными ограничениями. Для ее решения поступаем следующим образом. Построим оператор Н : R^N -» R^N~^K в виде J2Q, удовлетворяющий условию N(H) = R(Ut), Ut = Ш). Воспользовавшись заменой переменных Л = H*v, сводим данную задачу к задаче наименьших квадратов без ограничений в пространстве векторов v [і Є R^N~^K Ф R^K. Последнюю задачу решаем, воспользовавшись Qil-разложением с накоплением (см. п. 4.7.1).

12. Другой подход к решению задач с неточными данными заключается в построении сплайна, проходящего вблизи интерполируемых значений: в узлах сетки задаются доверительные интервалы, через которые должно проходить решение. Это задача в выпуклом множестве, изучавшаяся П.-Ж. Лораном [41]. Он получил необходимые и достаточные условия характеризации решения. Основная особенность решения такой задачи заключается в разделении множества узлов на "узлы прилипания", в которых решение "прилипает" к верхнему или нижнему ограничению, и свободные узлы, в которых решение проходит строго между ограничений. Если некоторый узел сетки свободный, то соответствующий ему коэффициент в представлении (0.12) равен нулю. Таким образом, в представлении сплайна участвуют базисные функции только в узлах прилипания, и можно надеяться получить решение, в котором задействовано существенно меньше узлов сетки. Подход, основанный на поиске узлов прилипания сплайна, был реализован А.В. Ковалковым для одномерного сплайна (см. [18]). Аналогичные идеи были запрограммированы М.И. Игнатовым для сплайна многих переменных (см. [29]).

Пусть X = Х($1), Y = У (О) - гильбертовы пространства функций в ГІ С Лп, Г Є L(X, Y) - нормально-разрешимый оператор с конечномерным ядром и X непрерывно вложено в Cioc(^). Пусть в узлах конечной сетки ш = {ii,..., t^} С ft заданы доверительные интервалы [zf, zf], zj < zf, і — 1,..., N, в которые должен попадать сплайн.

Задачу

а = arg min ||Г*||², (0.15)

агЄЛ/_ц,(г^-,г⁺)

M_w(z~,z⁺) = {x Є X : zf < x(U) < zt, і = 1,..., N},

Введение

назовем задачей интервальной сплайн-интерполяции.

# Как было отмечено выше, интервальный сплайн характеризуется уз
лами прилипания к ограничениям. П.-Ж. Лоран получил условия един
ственности решения, в которых существенно, что сетка узлов интерполя
ции удовлетворяет условию Хаара на N(T). Для полиномов многих пере
менных это условие обычно не выполняется. По этой причине, единствен
ность решения при построении интервального сплайна многих перемен-

** ных гарантировать невозможно.

Решение задачи (0.15) имеет вид (0.12), (0.13), причем справедливо следующее: если o~(ti) = zf, то Aj > 0; если а(и) — zf, то А* < 0; если zf < ст(и) < zt, то А; = 0 [41].

Узлы сетки, для которых Af ф 0, назовем активными, а узлы сетки, в которых о{и) — z~ или а(и) = л*, назовем узлами прилипания. Ясно, что сетка узлов прилипания содержит в себе сетку активных узлов.

Следующие теоремы доказаны автором:

* Теорема 4.8.2. Пусть сетка uj содержит L-набор для N(T). Тогда
множество S_u(z~,z⁺) решений задачи (0.15) есть замкнутый выпуклый
ограниченный многогранник в пространстве сплайнов Spl(a;), параллель
ный N(T), т. е. если сгі,сг2 Є S_u(z~,z⁺), то Є N(T).

Теорема 4.8.3. Пусть сетка и содерэюит L-набор для N{T). Тогда для любых 0"і,о"2 Є Stj(z~,z⁺) множества активных узлов сплайнов о~\ и &2 совпадают. Обозначая через ш^&с - множество активных узлов, имеем cri(t) = сг₂() для всех t Є w^ac.

Если к тому же множество ш^ас содержит L-набор для N(T), то
Ч решение задачи (0.15) единственно.

Теорема 4.8.4. Пусть сетка и) содержит L-набор для N(T). Тогда найдется такое решение а Є S_w{z~,z⁺), что его множество узлов прилипания о;^с1(<т) содержит L-набор для N(T).

Теорема 4.8.4 дает обоснование алгоритма поиска решения путем пе
ребора узлов прилипания сплайна. Отметим первый шаг предлагаемого
в п. 4.8.5 алгоритма, отсутствующий в алгоритмах других авторов: по-
,* строение начального приближения, в результате которого либо находит-

Введение

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

сетки узлов прилипания также отличается от методов, использованных А.В. Ковалковым (см. [18]) и М.И. Игнатовым (см. [29]). Вместо того, чтобы сразу искать подсетку узлов прилипания для сплайна с заданными доверительными интервалами (и рисковать получить решение с числом узлов, сравнимым с числом узлов сетки), предлагается сначала ослабить

* ограничения, а затем постепенно их сжимать. При этом можно контроли
ровать число узлов прилипания и строить более сложные критерии оста
нова процесса приближения.

Метод решения промежуточной задачи квадратичного программирования на подсетке также отличается от методов, использованных другими авторами. Решение задачи ищется методом проекции градиента. Автор получил крайне простые формулы вычисления сплайна, являющегося проекцией градиента. Разобьем подсетку й, на которой ищем решение промежуточной задачи, на три подсетки: подсетка u)q состоит из узлов прилипания, в которых условия характеризации предыдущего приближения выполняются; подсетка а>і состоит из узлов прилипания, в которых условия характеризации предыдущего приближения нарушаются; подсетка 0)2 содержит остальные узлы подсетки ш.

Теорема 4.8.7. Сплайн

tju! k=l

коэффициенты которого Аф/t задают вектор проекции градиента, есть решение задачи сплайн-интерполяции

о = arginin{||Tz||², x(t_k) = 7*, t_k Є a)},

Г 0 при t_k Є шо,

[ -А& при tk Є wi U a>2-

Здесь Afc — коэффициенты предыдущего приближения. Предложенный алгоритм построения сплайна был реализован

* И.А. Молотковой [47] под руководством автора диссертации. Описание

Введение

данного алгоритма завершается рассмотрением случая существенной не
фі единственности решения, когда вся сетка узлов не содержит L-набор. При
водится модификация алгоритма для этого случая.

13. В приложении к диссертации приводится описание библиотеки сплайн-аппроксимации JSpline+ [21, 93], созданной под руководством и при непосредственном участии автора студентами НГУ А.В. Галковым,

^ О.А. Лихачевым, А.Е. Никишкиной, Н.Ф. Фурсовой, а также аспирантом

ИВМиМГ СО РАН Д.В. Петраковым.

В настоящий момент в библиотеке реализовано большое количество алгоритмов линейной алгебры, в том числе модифицированное QR-разло-жение в трех вариантах, Q-R-разложение с накоплением, решение системы линейных уравнений с блочной матрицей вида (0.10) путем сведения ее к системе (0.11), решение системы (0.10) с произвольной правой частью. В разделе сплайн-аппроксимации реализованы алгоритмы одномерной полиномиальной сплайн-аппроксимации сплайнами четной и нечетной

* степеней. Для этих сплайнов имеются режимы интерполяции, сглажива-

ния, выбора параметра сглаживания по критерию невязки. Коэффициенты полиномиальных сплайнов могут храниться либо в виде полного полиномиального разложения по ячейкам сетки, либо в виде разложения по 1?-сплайнам. Реализованы сплайны Дюшона многих переменных, для которых также имеются режимы интерполяции, сглаживания, выбора параметра сглаживания по критерию невязки.

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

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

Введение

#

Математические утверждения (теоремы, леммы и т.д.) не имеют собственной нумерации. При ссылке на них используются номера пунктов, в которых эти утверждения приведены. Часто формулировки теорем состоят из нескольких утверждений, имеющих буквенную нумерацию (а), (б) и т.д. При ссылке на конкретное утверждение такой теоремы к номеру пункта добавляется соответствующая буква. Так, например, фраза "теорема 1.2.4 (в)" означает ссылку на утверждение (в) теоремы, приведенной в п. 1.2.4. Нумерация формул двойная и не зависит от разбиения текста по параграфам. Конец доказательства помечается символом , прижатым к правому краю страницы.

Эквивалентные нормы в банаховых пространствах

Смешанный сплайн есть решение следующей задачи: где Г Є L(X, Y), Ai Є L(X, Zi), A Є L(X, Z2), все пространства гильбертовы, z\ Є R(Ai), zi Є 2) ск 0 - параметр сглаживания. Данная задача объединяет в себе задачи интерполяции (А\ = А, А2 = 0) и сглаживания (Лі = 0, Л.2 = А). Постановка (0.1) была предложена А.Ю. Бежаевым и В.А. Василенко [80]. В этой же работе приведены условия однозначной разрешимости задачи (0.1) в практической ситуации конечномерности ядра N(T) оператора Т, получено условие характеризации и система операторных уравнений для смешанного сплайна. Автор продолжил эти исследования и доказал теорему о необходимых и достаточных условиях однозначной разрешимости задачи (0.1): Теорема 2.1.3. Пусть оператор Т нормально разрешим (R(T) замкнуто б Y). Тогда следующие утверждения эквиваленты: (а) существует оператор В Є L(X, W), действующий в некоторое гильбертово пространство W, такой, что N(Ai) С N(B) и норма Нж1гвл2 = ( ж12+ Н ж12 + 1И2Сс2) эквивалентна норме ЦягЦх/ (б) смешанная задача (0.1) однозначно разрешима при любых z\ z Є Д(Лі) Z2; при любых f ф g Є Y ф 2/ (г) на подпространстве N(A\) нормы тел2 w х эквивалентны. Данная теорема обобщает результаты П.-Ж. Лорана [41, теоремы 4.4.1 Доказательство этой теоремы, а также других утверждений о смешанных сплайнах базируется на технике сведения задачи (0.1) к эквивалентной задаче наилучшего приближения в выпуклом множестве. В этом заключается отличие предлагаемого метода доказательства от методов, используемых другими авторами (данная методика близка к методике, используемой в работах В.А. Морозова [48, 50]). В основе этой техники лежит следующая теорема об эквивалентных нормах в банаховых пространствах, доказанная автором: 2. Ясно, что любой сглаживающий сплайн является интерполяционным для некоторого другого вектора измерений z. В монографии П.-Ж. Лорана [41, теорема 4.6.4] рассматривается и обратная задача: пусть имеется интерполяционный сплайн и задано а 0; существует ли вектор 5, для которого этот сплайн является сглаживающим. Обозначая через А+ и А+ операторы, сопоставляющие вектору z Є R(A) интерполяционный и сглаживающий сплайны соответственно, данную задачу можно сформулировать так: совпадают ли образы операторов А+ и А+? Ответ на этот вопрос положительный. Множества интерполяционных и сглаживающих сплай fc нов при фиксированном А совпадают и образуют пространство сплайнов Spl(.A) С X, характеризующееся условиями Автор ставит аналогичный вопрос об операторе А, сопоставляющем .ф вектору z = ziZ2 Є R(Ai) ф Z2 сплайн аа - решение задачи (0.1). Ответ на этот вопрос дает следующая теорема, предлагающая также способ продолжения оператора A + на все пространство Z\ ф Z2\

Теорема 2.2.10. Пусть R(T) и R(Ai) замкнуты и задача (0.1) однозначно разрешима при любых допустимых исходных данных. Обозначим А = Аі ф А2. Тогда: (а) A : R(A\) ф Z2 — Spl(A) - линейный ограниченный оператор; (б) оператор А+ удовлетворяет тождеству to где V - ортопроектор на R(Ai) Ф R(A2), z = z\ Ф z2 Є і?( 4і) Ф Z2; (в) оператор А непрерывно продолжается по формуле (0.2) на все пространство Z = Z\ 0 2, nmo соответствует замене задачи (0.1) wa задачу W (г) если (Т, Л) - сплайн-пара и операторы А\ и А2 линейно независимы (R(Ai 0 А2) = R{Ai) ф R(A2)), то сужение оператора А+ на R(A) есть непрерывный изоморфизм между R(A) и Бр\(А). Пару (Г, А) здесь и далее называем сплайн-парой, если R(T), R(A) и N{T) + N(A) замкнуты, N(T) П N(A) = {0}. Пункт (г) этой теоремы можно выразить словами так: если (Г, А) сплайн-пара и операторы А\ и А2 линейно независимы, то любой элемент пространства сплайнов Spl(-A) является смепіанньїм сплайном при любом , а 0 и подходящем (однозначном) выборе z Є R{A). 3. Задача смешанной сплайн-аппроксимации изучалась автором также в контексте сплайнов на подпространстве. В.А. Василенко назвал сплайн, построенный методом конечных элементов, сплайном на подпространстве [14]. Пусть { г}г о - семейство замкнутых подпространств в X. Смешанным сплайном на подпространстве ЕТ называется решение задачи Здесь предполагается, что Аї1{х{) П Ет ф 0, т.е. условия интерполяции А\х = z\ не противоречивы на Ет. Введем эквивалентную норму = \\У/БТВА2 П0 теореме 2.1.3, возьмем ортопроектор Рт на Ет в норме и введем оператор сплайн-интерполяции S: Автор доказывает следующую теорему сходимости сплайнов т„ к сга: Теорема 2.7.9. Пусть подпространства ЕТ предельно плотны в X при т — 0 и найдется такое TQ 0, что при т 7 R(AiPT) = R(Ai) и выполнено одно из условий: (а) dim R(A\) со; (б) (7-Рт)5. С7 1. Тогда 5 — аа\\х при т - 0. Доказательство этой теоремы базируется на доказанной автором теореме о сходимости наилучших приближений в замкнутых выпуклых множествах. Пусть М С X - замкнутое выпуклое множество и Рм X —» X -оператор, сопоставляющий каждому элементу / Є X наилучшее приближение h Є X на множестве М по формуле Рм/ = Л, = argmin M \\х — /2. Теорема 1.6.1. Пусть МІ С X - непустые замкнутые выпуклые множества и fi X - некоторые элементы, і Є IN. Предположим, что fi—tf при г — оо и множества МІ удовлетворяют одному из условий:

Характеризация и операторное представление сплайнов

Данный подход хорошо работал в одномерном случае, а также в многомерном на "прямоугольной" сетке узлов. Для доказательства сходимости многомерных интерполяционных сплайнов на хаотических сетках потребовался совершенно другой математический аппарат, использующий их вариационные свойства. При этом задача сходимости изучается в следующей постановке: рассматривается w некоторый функциональный класс (например, 1 (ft)), и функция из этого класса интерполируется сплайном, полученным с помощью минимизации вариационного функционала на этом же классе функций. Традиционно рассматриваются два способа сгущения сеток: вложенное сгущение (следующая сетка содержит в себе предыдущую) и произвольное. В работе В.А. Василенко [13] доказана "общая теорема сходимости" интерполяционного процесса на вложенных сетках, базирующаяся на том, что система операторов, соответствующих добавляемым узлам интерполяции, должна быть правильной. А. Имамовым установлено, что условие правильности этой системы не только достаточно, но и необходимо для сходимости [31]. В [58] автор показал, что система операторов правильная тогда и только тогда, когда их ядра пересекаются по нулю. Здесь общая теорема сходимости (теорема 2.6.1) формулируется в терминах пересечения ядер операторов. Сходимость абстрактных интерполяционных сплайнов при произвольном способе сгущения сеток впервые исследовалась Жоли [92]. Он установил следующий критерий сходимости: если ядро энергетического оператора Т конечномерно и линейные оболочки функционалов интерполяции образуют Q-последовательность, то интерполяционные сплайны сходят ся к интерполируемой функции. Этот критерий применен Дюшоном в работе [88] при доказательстве сходимости )т-сплайнов в Rn и их обобщений, называемых нами сплайнами Дюшона. В.А. Василенко предложил другой (более естественный) критерий сходимости интерполяционных сплайнов, базирующийся на непрерывности параметрического семейства функционалов, по которым осуществляется интерполяция [80]. В применении к 1?т-сплайнам в области 1 ему удалось доказать следующую теорему: если область

О. ограничена и имеет липши & цеву границу, то при произвольном способе сгущения конечных е-сеток в Q. .От-сплайны, интерполирующие функцию / Є H 2m( ), сходятся к /. Используя аналогичный подход, автор усилил результаты В.А. Василенко и снял практически все ограничения на область и сетки узлов интерполяции (эти ограничения выделены в предыдущем абзаце курсивом) [58,107]. В настоящей формулировке осталось только одно (и весьма существенное) ограничение: последовательность сеток должна быть предельно вложенной (ШІ С о7ПП). При нарушении этого условия предельный сплайн (если он существует) может удовлетворять условиям интерполяции, которые отсутствовали у последовательности приближений. Например, если построить последовательность сплайнов, у которых один интерполяционный узел (скажем, s) стремится к другому узлу (t) вдоль направления t — s, то предельный сплайн будет дополнительно интерполировать производную функции / в точке t по направлению s — t. Задача исследования сходимости сплайнов при нарушении условия предельной вложенности сеток в настоящий момент практически не изучена. 2.7, завершающий данную главу, посвящен задаче построения сплайнов методом конечных элементов, которые В.А. Василенко назвал "сплайнами на подпространствах". Предложенный им и обоснованный в работах [14-17] метод существенно отличается от обычного способа применения метода конечных элементов в задачах математической физики. Отличия заключаются в том, что сетка конечных элементов может быть не согласована с узлами интерполяции (узлы разбросаны хаотично, а сетка -регулярная, прямоугольная). Сходимость интерполяционных и сглаживающих сплайнов на подпространстве доказана в [80] (в этой работе допущена неточность: в теореме 4.1 слабую сходимость подпространств ЕТ к X следует заменить на сильную, поскольку формула (4.31) есть условие сильной сходимости Ет к X, а не слабой, как там утверждается). Теорема 2.7.9 о сходимости смешанных сплайнов на подпространствах установлена автором [106]. Оценки сходимости интерполяционных сплайнов на подпространствах (п. 2.7.10) получены в работе [80] и упрощены автором в [110]. Далее будет показано, что для однозначной разрешимости задач сплайн-аппроксимации (2.1)-(2.3) достаточно, чтобы энергетический и интерполяционный операторы были сплайн-парой. Однако эти условия не всегда являются необходимыми (например, требование замкнутости $ R{A) излишне, если N(T) конечномерно). Поясним, за что ответственны условия, предъявляемые в определении сплайн-пары. Условия (а) и (в) обеспечивают существование сплайна, а условие (б) - его единственность. На первый взгляд наиболее загадочным представляется условие (в). Когда оно выполняется? Ответ на этот вопрос в практических случаях очень прост: если хотя бы одно из замкнутых подпространств N(T) или N(A) имеет конечную размерность или коразмерность, то их сумма замкнута. В приложениях обычно dim N(T) со, и тем самым (в) выполняется. 2.1.3. Теорема. Пусть оператор Т нормально разрешим (R(T) замкнуто в Y). Тогда следующие утверждения эквиваленты: (а) существует оператор В Є L(X,W), действующий в некоторое гильбертово пространство W, такой, что N(Ai) С N(B) и норма \\Х\\ТВА2 = (ІІ ІР-Ь ІІ- Ц2 + ll- 2 2) эквивалентна норме \\х\\х; (б) смешанная задача (2.3) однозначно разрешима при любых z\ 0 z Є

Сходимость абстрактных интерполяционных сплайнов

Рассмотрим сначала сходимость интерполяционных сплайнов в пред положении, что последовательность интерполяционных операторов {АІ Є L(X, Zi)} удовлетворяет условию N(Ai+i) С N(Ai). На практике это означает, что следующая сетка интерполяционных узлов содержит в себе предыдущую, т. е. речь идет о "вложенном" сгущении сеток. 2.6.1. Теорема. Пусть оператор Т нормально разрешим и задачи xeA;Hz,) однозначно разрешимы при любых Z{ Є R(Ai). Если N(Ai+{) С М(Аг), г Є IN, и А Є L(X, Z) - оператор с ядром в некоторое гильбертово пространство Z, то последовательность операторов Si = S(Ai,T,X) сильно сходится к оператору сплайн-интерполяции S = S(A, Т,Х), т. е. для любого f Є X последовательность Stf сходится к Sf в норме пространства X. Доказательство. Пусть f Є X - некоторый элемент. По определению Stf = arg min Tz2. (2.63) По теореме 2.1.3 найдется такой оператор В Є L(X,W), что N(Ai) С N(B) и норма \\ТФВ эквивалентна норме \\х Учитывая очевидное тождество Ajl(Aif) = f + N(Ai) и соотношения N(Ai) С N(Ai) С N(B), перепишем задачу (2.63) в эквивалентной форме SJ = arg mmJ\x\\ B. По теореме 1.6.1 (а) последовательность Sif сильно сходится к сплайну С учетом (2.62) (7 = 5/. Следствие. Пусть оператор Т нормально разрешим, задачи (2.61) однозначно разрешимы при любых допустимых исходных данных и N(Ai+i) С N(Al), г Є IN. Тогда следующие утверждения эквивалентны: (а) последовательность операторов Si сильно сходится к тожде ственному оператору I, т.е. \/ж Є X S{X —» х; (б) ПЛГ(Д) = {0}. 2.6. Сходимость абстрактных интерполяционных сплайнов Далее рассматривается случай произвольного сгущения сеток при условии dimiV(r) оо. 2.6.2. Сплайн-интерполяция на параметрическом семействе функционалов. Пусть О, С Rn некоторое множество, и задано параметрическое семейство функционалов # Ф(СІ) = { РІЄХ , ten}. (Обычно (ft = St - функционал, сопоставляющий функции из X ее значение в точке t.) Далее, пусть ь) - некоторое подмножество Q и / Є X -произвольный элемент. Положим M(/,w) = {х Є X : pt(x) = (/), t Є ш} и рассмотрим задачу сплайн-интерполяции а = arg mm Тя2. (2.64) iM(/,w) v4l Рассмотрим также некоторое семейство подмножеств {щ С П}ІШ И соответствующие им задачи сплайн-интерполяции (Л = arg mm Гж2. жЄМ(/м) Нас интересуют условия, при которых имеет место сходимость 7г- — сх —0 при г - со. Сначала установим несколько вспомогательных фактов о свойствах семейства функционалов Ф(П), а затем докажем основную теорему сходимости. Ч 2.6.3.

Лемма. Пусть dimN(T) = к и R{T) замкнуто. Задача (2.64) имеет единственное решение тогда и только тогда, если найдется такое множество точек {і,- Є ш, г = 1,..., к}, что N(T) П N( ph) П ... П N( pth) = {0}. (2.65) Доказательство. Введем линейный оператор А : X — Яш по правилу Ах = {(ft(x), t Є w}. В i2w не требуется задавать структуру гильбертова пространства, поскольку для корректной постановки задачи сплайн-интерполяции необходима только замкнутость N(A). Ядро оператора А определяется формулой 2.6. Сходимость абстрактных интерполяционных сплайнов 83 N(A) == М(0,ш) = П Ы и, очевидно, замкнуто как пересечение семейства замкнутых подпространств. По теореме 2.1.4 (г) условие однозначной разрешимости задачи (2.64) имеет вид N(T) П N(A) = {0}, что эквивалентно (2.65) в силу конечно мерности N(T). Набор точек {U Є Єї, і = 1,..., к} назовем L-набором, если соответствующие им функционалы (р , ..., щ% удовлетворяют (2.65). Далее будем считать, что задача (2.64) однозначно разрешима, т.е. в ш имеется некоторый L-набор точек Si, ..., S&. Для произвольной точки t Є П через B(t,s) обозначим относительную е-окрестность (см. п. 1.7.1) точки t в fi: Б( ,с)ї{яЄП: p(s,t) e}. Рассмотрим множество Вє = B{s\, є) X... х #(s&, є), состоящее из "шаров" радиуса е с центрами в точках L-набора s = (si,..., 5). 2.6.4. Будем предполагать, что (а) множество Q, локально-компактно; (б) семейство функционалов Ф(П) непрерывно по параметру, т.е. \\(ps — tftWx — 0 при s — t, s, і є П: 2.6.5. Лемма. i?evm выполнены предположения 2.6.4, то существует такое єо 0, что множество В компактно при любом є Єо и любой вектор t = (ti,..., tfc) Є ВЄо является L-набором. Доказательство. В силу локальной компактности множества Л и конечности L-набора s найдется такое є, что В компактно при є є (лемма 1.7.2). Выберем какой-нибудь базис щ,...,ик в N(T). Тогда условие (2.65) на L-наборе s записывается в виде системы линейных уравнений к Е РзХиз)аз г = 1,...,/г, 2.6. Сходимость абстрактных интерполяционных сплайнов 84 с кх/г-матрицей U, имеющей коэффициенты и = ips,{uj) Поскольку эта система должна иметь только нулевое решение, то матрица U невырождена. Следовательно, det U ф 0. В силу непрерывности определителя матрицы как функции ее коэффициентов, найдутся такие Sij 0, что любая матрица U с коэффициентами щ, удовлетворяющими условию \uij — Uij\ 5ij, невырождена. Отсюда достаточно показать, что найдутся такие є -, что \ ft(uj) - PsAuj)\ йі ПРИ t е B(shij)- (2.66) Тогда Єо = тіп{є } будет искомым числом. Докажем (2.66) для произвольных sfi, и Є X к 5 0. Рассмотрим функцию f(t) = tft(u)- Поскольку семейство Ф(П) непрерывно по , то функция / непрерывна в П. Пусть t Є B(s,e). В силу локальной компактности ГХ множество B(s, є) компактно при є es. Следовательно, найдется такое 0 е ss, что \f(t) — f(s)\ S при t Є B(s,є). 2.6.6. Лемма. Если выполнены предположения 2.6-4 и число Єо выбрано по лемме 2.6.5, то при любом t = (i,... ,2) Є ВЄо справедливо неравенство /к \ 1/2 V Є X \\х\\х С[Е РІ(х) + Tz2J (2.67) с константой С 0, не зависящей от t. Доказательство.

Построение полиномиального сплайна нечетной степени

Коэффициенты матрицы А не зависят от выбора воспроизводящего ядра G и задаются формулой aij = (фіЄ, i jG)T = {wh WJ)Y, (3.31) причем функции wi — ТфіЄ Є Y также не зависят от выбора воспроизводящего ядра. Сплайн аа удовлетворяет условиям интерполяции с вектором za = z- aPH v, (3.32) а вектор неизвестных коэффициентов \i можно найти из условий интерполяции Ааа = za и представления N-K Таа = utwt (3.33) г=1 либо из системы уравнений Ufi = z-(C + аР)Н и. (3.34) Напомним, что выражение т/ С? означает, что функционал фі действует на воспроизводящее ядро G по переменной t. Доказательство. Представление (3.29) следует из (3.26). Формулы (3.30), (3.32) и (3.34) легко получаются из (3.27) и (3.28), а (3.33) - из (3.29). Осталось доказать, что матрица А симметрична и положительно определена, ее коэффициенты а удовлетворяют (3.31), и что а и и і не зависят от выбора воспроизводящего ядра G. Имеем Oij = Еhikhji WPiG = (Еhik(pk){Y,hj№)G = фіф k,l к I или aij = фi( yфj), где j(p = pG - воспроизводящее отображение. Из тождества HU = О выводим ФіМ =Т,ЫкРк{щ) = Е hikUkj = 0, к к т. е. фі Є N(T). Применяя лемму 3.1.4, получим 3.4- Построение полиномиального сплайна нечетной степени 114 Доказательство. Поскольку оператор Dm действует "на" L [а, Ь], то его образ замкнут в силу полноты Li [а, Ь]. Несомненно, что оператор Dm линеен и ограничен в W fa, b]. Следовательно, W a, b] - S-пространство с полунормой Цдт. Известно, что H fa, 6] непрерывно вкладывается в С[а, 6]. Согласно п. 3.1.8 достаточно построить такую пару (U, V) дополнений к N(T), что: (а) ViGO Gra(.,t)Gl7; Ц (б) V Є П, х Є V x(t) = (Gm{ ,t),x)Dm. Пусть Эти подпространства имеют коразмерность т и пересекаются с N(T) по нулю. Тем самым они действительно служат дополнениями к N(T). (Напомним, что функционал сопоставляет функции ее значение в точке t.) Таким образом утверждение (а) выполняется. Далее, Здесь оператор Dm действует на Gm по переменной s. Применяя (т — 1)-кратное интегрирование по частям и учитывая, что х Є V, получим Замечание 1. Воспроизводящее ядро Gm(s,i), как функция переменного s при фиксированном , удовлетворяет уравнению Наконец, взяв полусумму функций Gm и Gm, получим еще одно воспроизводящее ядро и А - оператор, ставящий в соответствие функции из W ja, Ъ] (тп 0) ее значения на сетке ш = [а ti ti ... ijv b}. По теореме 2.1.4 задачи (2.1)-(2.3) однозначно разрешимы при условии N(Dm) П N(A) = {0}. Это условие выполняется, если число узлов интерполяции N не меньше т. В соответствии с теоремами 3.2.2, 3.4.1 решение задач (2.1)-(2.3) представимо в виде где Aj и /ij - свободные коэффициенты. Отсюда: (а) а Є C2m 2[a, &]; (б) на интервалах (ti,U+i) сплайн а - полином степени 2т — 1; (в) на интервалах (a, t\) и (#, Ь) сплайн т - полином степени т — 1.

Тот факт, что сплайн а будет полиномом степени т — 1 на интервале (%,&), можно доказать двояко: либо применив условие ортогональности для коэффициентов вектора Л из теоремы 3.2.2, либо заменив ядро Gm на Gm из замечания 2 к теореме 3.4.1. Из свойств (а) и (в) следует, что сплайн а удовлетворяет естественным краевым условиям Алгоритм Анселона-JIорана для задачи полиномиальной сплайн-аппроксимации на отрезке при специальном выборе матрицы Н сводится к системе (3.30) с ленточной матрицей. Покажем, как это осуществляется. 3.4.3. Построение матрицы Н. В соответствии с п. 3.3.5 коэффици енты hij матрицы Н должны выбираться из условий где fy - узлы сетки, tk = Uk(t) - базисные функции ядра оператора Т = Dm. Рассмотрим шаблон Аг- = { ,... ,г-+то}, состоящий из m -f- 1 узла интерполяционной сетки, и построим на нем конечно-разностную схему, аппроксимирующую оператор Dm (с точностью до умножения на константу). Коэффициенты этой схемы, дополненные нулями в остальных узлах сетки, можно взять в качестве строки матрицы Н. Передвигая шаблон Дг- по узлам сетки (г = 1, ...,N — m), получаем требуемую матрицу Н размера (N — m) х N. При вычислении коэффициентов г -й строки матрицы Н обычно используют аппарат разделенных разностей. Если f(t) - некоторая функция, то ее к-я разделенная разность /[,-,..., г+&] определяется рекуррентно через (к — 1)-е разделенные разности: начиная с нулевых разностей f[ti] = f(ti). Ясно, что коэффициент hij матрицы Н при j = г,..., г + т есть 7П-Я разделенная разность на подсетке Аг- от функции -, равной единице в узле tj и нулю в остальных узлах сетки. Построение матрицы Н с помощью разделенных разностей реализуется за 0(m2N) операций, если последовательно вычислять сначала первую разделенную разность на всех подсетках, затем вторую и т.д. Отметим, что матрица Н имеет га+1 ненулевой элемент в каждой строке. Поэтому для ее хранения требуется (га + l)(iV — m) ячеек памяти. 3.4.4. Построение матрицы А. В соответствии с теоремами 3.4.1, 3.3.б и с учетом ленточности матрицы Н коэффициенты матрицы А системы (3.30) имеют вид

Похожие диссертации на Теория и алгоритмы вариационной сплайн-аппроксимации

Методы изогеометрической аппроксимации сплайнамиКвасов, Борис Ильич

Алгоритмы исключения неизвестных, основанные на теории многомерных вычетов, и их компьютерная реализацияОсетрова, Татьяна Александровна

Соотношения о среднем и их приложения к алгоритмам метода Монте-Карло в задачах теории упругостиШалимова, Ирина Александровна

Равномерное приближение сплайнами: свойства, алгоритмы, приложенияПопов, Богдан Александрович

Дискретно-стохастические численные алгоритмы со сплайн-восполнениямиМилосердов Владимир Владимирович

Разработка алгоритмов компактной аппроксимации возмущений для построения высокоточных численных теорий движения ИСЗТайбаторов, Константин Александрович

Аппроксимация сплайнами с нефиксированными узламиВасильев, Юрий Сергеевич

Применение методов интерполяции и сплайн-аппроксимации для синтеза субоптимальных стратегий стабилизации движения летательных аппаратовЧжоу, Гуйхуа

Аппроксимация локальными L-сплайнамиСтрелкова Елена Валерьевна

О вложениях классов функций Н w в классы функций ограниченной обобщенной вариации и некоторые вопросы теории аппроксимации функцийМедведева Мария Викторовна