Теория и алгоритмы вариационной сплайн-аппроксимации тема диссертации и автореферата по ВАК РФ 01.01.07, доктор физико-математических наук Роженко, Александр Иосифович

• Роженко, Александр Иосифович
• доктор физико-математических наук
• 2003

Оглавление диссертации доктор физико-математических наук Роженко, Александр Иосифович

Введение.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.1. Dm-сплайн.

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

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

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

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

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

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

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

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

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

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

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

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

Введение диссертации (часть автореферата) на тему «Теория и алгоритмы вариационной сплайн-аппроксимации»

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

Принято считать, что теория сплайнов берет свое начало с работы Шёнберга [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]. Он исследовал задачу построения 2}т-сплайна в Rn с произвольно расположенными узлами интерполяции, а также получил алгоритм и оценки сходимости такой интерполяции. С этого момента берет свое начало теория сплайнов многих переменных на хаотических сетках. Отметим в этой связи работы А.Ю. Бежаева и В.А. Василенко [79-81], О.В. Матвеева [43-46], М.И. Игнатова и А.Б. Певного [29], Пауэла [102], Мэдича и Нельсона [98-100], Шабака и By [114], Лайта и Вейна [95].

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

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

IMvllxerMHi + M»1''

Обычно используем 2-норму. Прямая сумма операторов А : X —> Y и В : X —> Z есть оператор действующий по правилу:

А ф В)х = Ах © Вх. 2-норма, порождаемая прямой суммой операторов, имеет вид

Ыа*в = (IWIi + IMI If'2 = (WMy + \\Щ\\)1'2'

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

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

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

1. Задача смешанной сплайн-аппроксимации изучается в гл. 2. Смешанный сплайн есть решение следующей задачи: а = arg min а\\Тх\\2 + \\А2х - z2\\2, (0.1) где Т Е У), А\ 6 L(X, Z\), Ач (Е L(X, Z2), все пространства гильбертовы, z\ £ R(Ai), z2 (Е а > 0 - параметр сглаживания. Данная задача объединяет в себе задачи интерполяции (А\ = А, Ач — 0) и сглаживания (Лх = 0, А2 = А). Постановка (0.1) была предложена А.Ю. Бежаевым и В.А. Василенко [80]. В этой же работе приведены условия однозначной разрешимости задачи (0.1) в практической ситуации конечномерности ядра N(T) оператора Г, получено условие характеризации и система операторных уравнений для смешанного сплайна. Автор продолжил эти исследования и доказал теорему о необходимых и достаточных условиях однозначной разрешимости задачи (0.1):

Теорема 2.1.3. Пусть оператор Т нормально разрешим (R(T) замкнуто в У). Тогда следующие утверждения эквиваленты: а) существует оператор В Е L(X,W), действующий в некоторое гильбертово пространство W, такой, что N(A\) С N(B) и норма 1М|г©в©л2 = (||Та;||24- 11-ВяЦ2 + И^ЬжН2)1''2 эквивалентна норме ||ж||х/ б) смешанная задача (0.1) однозначно разрешима при любых z\ © z2 G

RiAJ © Z2; в) задача й = arg min а\\Ти — /II2 + IIA2U — g\\2 однозначно разрешима ueN{Ai) при любых f ф g G Y ф Zi', г) на подпространстве N(A{) нормы || • ||т©л2 и || • ||х эквивалентны.

Данная теорема обобщает результаты П.-Ж. Лорана [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 G R{A) интерполяционный и сглаживающий сплайны соответственно, данную задачу можно сформулировать так: совпадают ли образы операторов А+ и А^? Ответ на этот вопрос положительный. Множества интерполяционных и сглаживающих сплайнов при фиксированном А совпадают и образуют пространство сплайнов Spl(-A) С X, характеризующееся условиями ueN(A) (Тх,Ти) = 0. Л

Автор ставит аналогичный вопрос об операторе А^, сопоставляющем вектору z = z\ (&Z2 G i^(-Ai) © Z2 сплайн <та - решение задачи (0.1). Ответ на этот вопрос дает следующая теорема, предлагающая также способ Л продолжения оператора А+ на все пространство Z\ ф Z2'.

Теорема 2.2.10. Пусть R(T) и R(A\) замкнуты и задача (0.1) однозначно разрешима при любых допустимых исходных данных. Обозначим А = Ai © А2. Тогда: а) А* : R(A\) ф Z2 —> Spl(.A) - линейный ограниченный оператор; б) оператор А+ удовлетворяет тождеству

A+z = A+Pz, (0.2) где V - ортопроектор на R(Ai) Ф z = z\ ф z2 G ф Z2; в) оператор А+ непрерывно продолжается по формуле (0.2) на все пространство Z = Z\ ф Z2, что соответствует замене задачи

0.1) на задачу a°=arg^:^№l)a||Tx|12 + ||Л2Х ~~ гг||2; г) если (Т, А) - сплайн-пара и операторы А\ и А2 линейно независимы (.R(Ai ф А2) = R(A{) ф R(A2)), то сужение оператора на -Й(Л) есть непрерывный изоморфизм между R(A) и Spl(-A).

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

Пункт (г) этой теоремы можно выразить словами так: если (Т, А) -сплайн-пара и операторы А\ и Ач линейно независимы, то любой элемент пространства сплайнов Spl(A) является смешанным сплайном при любом о; > 0 и подходящем (однозначном) выборе 2 G R(A).

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

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

7J = arg min а\\Тх\\2 + ||Л2® - *2||2- (0.3)

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

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

Su = arg min а||Тж||2 + \\А2х\\2. Автор доказывает следующую теорему сходимости сплайнов ата к аа:

Теорема 2.7.9. Пусть подпространства ЕТ предельно плотны в X при г —> 0 и найдется такое то > 0, что при г < tq R(A\Pt) = и выполнено одно из условий: а) dimi?(^i) < оо; б) ||(/-Рг)%<С<1. Тогда — <та\\х при т —)■ 0.

Доказательство этой теоремы базируется на доказанной автором теореме о сходимости наилучших приближений в замкнутых выпуклых множествах. Пусть М С X - замкнутое выпуклое множество и Рм ' X —> X -оператор, сопоставляющий каждому элементу / £ X наилучшее приближение h £ X на множестве М по формуле Рмf = h = arg minx6M ~~ /||2

Теорема 1.6.1. Пусть Mi С X - непустые замкнутые выпуклые множества и fi £ X - некоторые элементы, г £ IN. Предположим, что fi —У f при г —У оо и множества Mi удовлетворяют одному из условий: а) Mi+i С М{ и П Мг = М; i€lN б) М{ С М и существует последовательность Xi £ М^ сходящаяся к

Рм/.

Тогда последовательность hi = PmJi сильно сходится к h = Рм/? т.е. У'1» — Щх —> 0 при г —> оо.

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

Ста = argmin а\\Тх\\2 + ||Ах - z\\2. (0.4)

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

Предположим, что (Г, А) - сплайн-пара, и введем скалярное произведение u,v)* = (u,v)TeA = (Tu,Tv)Y + {Au,Av)z, порождающее эквивалентную норму в X. Представим пространство X в виде

X = N(A) © N(T) фХ, X = (N(A) + N(T))±, (0.5) где ортогональное дополнение берется относительно скалярного произведения (•, •)*.

Теорема 2.3.3. Пусть (Т,А) - сплайн-пара и операторы А*, Т* сопряжены к А, Т относительно скалярного произведения (•, •)*. Тогда: а) операторы А*А и Т*Т перестановочны, причем А*А + Т*Т = 1х; б) разложение (0.5) приводит операторы А*А и Т*Т к виду

А*А(и 1 + «2 + Щ) = ОщА)Щ + 1щт)и2 + Аи3, T*T(ui + li2 + ^з) = 1щА)П 1 + 0N(T)U2 + Ти 3, где их G N(A), и2 G N(T), и3 G X;

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

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

Теорема 2.3.4. Рассмотрим задачу построения сглаживающего квазисплайна cra = argmin а\\Тх — у||2 + ||Ах — z\\2.

Too = arg min II Ах — z\\2, arg caJA^UA. ^ WTx ~ у\\2'

Тогда: его — cr00 Е X; сга = а^ + qa = сго + га, причем qa и га принадлежат X и определяются из уравнений

I + aA1T)qa = qo = сг0 - <Хоо,

I + сГ1Т~1А)га = Гоо — о"оо - 00

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

Один из методов выбора параметра сглаживания в задаче (0.4) заключается в решении уравнения <р(а) — ||Ааа — z\\ = е относительно а. Это уравнение называют критерием невязки. В работе В.И. Гордоновой и В.А. Морозова [23] предлагается выбирать параметр сглаживания, решая эквивалентное уравнение рцз) = (0.6) где (3 — аГ1, ^(/3) = <р{а). Если ^(0) ф Ф{оо), то ф*(0) при s > 0 -строго монотонно убывающая выпуклая вниз функция, при — 1 < s < 0 строго монотонно возрастающая выпуклая вверх функция, и скорость сходимости метода Ньютона максимальна при s = — 1.

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

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

1 ~ м(оц) , v (rgz> Rjz) (rgz,R2az) ak+i = ak -—r, w(a) = —-=-—. p{ock)/£ -w(ak) {Raz,Raz) <рг(а)

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

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

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

Ы ак

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

DkRa = (-1 )h+1-^Rka(I - Ra), k > 1.

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

0.7) fc=0 «о у абсолютно сходящегося на отрезке [0,2о:о]

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

Автором также исследовано поведение сплайна <та вблизи бесконечности. Полагая Qp = I — получаем точно такие же правила дифференцирования оператора Qp по /3 как в лемме 2.4.3, из которых, с привлечением теоремы 2.3.3, выводится следующая

Теорема 2.5.3. Пусть /?о > 0. Тогда невязка z — Acrijp представима в виде суммы ряда абсолютно сходящегося на отрезке [0,2(Зо].

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

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

5. Задачи сплайн-аппроксимации функций многих переменных представляют как теоретический, так и практический интерес. Теоретические вопросы включают в себя проверку корректности (однозначной разрешимости) задачи сплайн-аппроксимации, доказательство сходимости интерполяционных сплайнов и получение оценок сходимости. Автор ограничивается только случаем, когда аппроксимируемая функция - Аат = [ t - A'VA)

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

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

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

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

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

6. D"1-сплайны в произвольной области представляют в основном теоретический интерес. Задача /?т-аппроксимации обычно рассматривается либо в области с липшицевой границей, либо в Rn. Автор в [58] распространил постановку задачи 2}ш-аппроксимации на произвольную область в Rn. При этом в качестве X надо брать L™(Q) - пространство функций в fi, m-e частные производные которых интегрируемы с квадратом.

Доказательство сходимости 1)т-сплайнов в произвольной области получено .автором. Ранее В.А. Василенко было доказано [80], что если область О, ограничена и имеет липшицеву границу, то при произвольном способе сгущения конечных е-сеток в Q, 1)т-сплайны, интерполирующие функцию / € W^fi), сходятся к / в норме пространства ТУ™ (ft). Автору удалось убрать все ограничения, выделенные в предыдущем предложении курсивом, и доказать следующую теорему:

Теорема 4.2.3. Пусть последовательность множеств {щ С wflftj-ieiN предельно плотна в и), т > п/2 и f 6 L™(Q) - интерполируемая функция. Тогда последовательность интерполяционных сплайнов = SWJ сходится к сплайну а — Suf в норме пространства L™(ft).

Здесь 5с — оператор, сопоставляющий функции / Е L™(ft) интерполяционный £)т-сплайн а с условиями интерполяции cr(t) = /(£), t Е ш.

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

Теорема 4.2.2. Пусть Q С Rn ~ локально-компактное множество, X непрерывно вложено в С£с(Г1) при некотором 0 < а < 1. Предположим, что оператор Т 6 L(X, Y) имеет конечномерное ядро и замкнутый образ; множество и С ft содержит L-набор точек для N(T); последовательность множеств {wi С tUHflj-jeiN предельно плотна в ш. Тогда найдется такое число го > 0, что при i>io задача cri = argmin{||Ta;||2, х 6 X, x(t) = /(£), t G c^} однозначно разрешима и последовательность {сгг} сходится в норме пространства X к а = argmin{||Ta;||2, х G X, x(t) = /(£), t 6 и} при i —> оо.

Здесь Ci"c(fi) - пространство непрерывных функций в ft, локально удовлетворяющих условию Гельдера с параметром 0 < а < 1. Множество ft С Rn назовем локально компактным, если для любой точки t € ft найдется компактная относительная окрестность ftj этой точки в П. В свою очередь, множество ftj С ft называют относительной окрестностью точки t в ft, если существует множество Dt С Лп - окрестность точки t в i^, такое, что ftf = Dt П ft.

Замечание. Замкнутые и открытые множества в Rn являются локально компактными. Автор в § 1.7 дает эквивалентные определения локально-компактного множества и доказывает, что пространство Cioc(f2) функций, непрерывных в £], является пространством Фреше.

Теорема 4.2.2, в свою очередь, выводится из теоремы о сходимости интерполяций на сгущающемся семействе функционалов, усиливающей теорему В.А. Василенко о сходимости на сгущающихся е-сетях (ср. [80]).

Пусть fi С Rn ~ некоторое множество, и задано параметрическое семейство функционалов Ф(П) = {(ft £ X', t Е S7}. Далее, пусть и) -некоторое подмножество Пи/бХ - произвольный элемент. Положим

М(/, и) = {хвХ: <pt(x) = <pt(f), t Е ш}.

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

Теорема 2.6.7. Пусть N{T) конечномерно, множество S7 локально-компактно и семейство функционалов Ф(П) непрерывно по параметру, т. е. ||(ps — (pt\\x1 0 при s t, s,t € П. Пусть также задача а = arg min ||Гж||2 xeM{f,w) однозначно разрешима.

Тогда если последовательность множеств {щ С tJnfl}j<=]N предельно плотна в и, то существует такое го Е IN, что при г > го задача = агё .Ж1 JTa;l|2 однозначно разрешима, и ||<тг- — <j||j^ —V 0 при г —Y оо.

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

Dkx\\Lp(Q) < Chm-k-n^\\Dmx\\L2(sl) (0.9) при р>2нт — к — п/2 + п/р > 0 (т — к — п/2 > 0 при р = оо). Здесь х Е L™^) - произвольная функция, имеющая h- сеть нулей вПи константа С > 0 не зависит от ж и выбора Л,-сети. Автор в [58] распространил эти оценки на ограниченные области, удовлетворяющие слабому условию конуса (в частности, на области с разрезами, выколотыми точками, острыми пиками, направленными внутрь), а в [61] — на (возможно неограниченные) области являющиеся объединением конечного числа областей типа SL21 (удовлетворяющих слабому условию конуса и допускающих продолжение за пределы области с сохранением класса гладкости). В работах О.В. Матвеева [43, 44], получен более широкий спектр оценок сходимости DTO-сплайнов в различных метриках, однако рассмотрение ограничивается только областями, удовлетворяющими сильному условию конуса.

8. Сплайны Дюшона. Французский математик Дюшон предложил в [87] сплайны, являющиеся обобщением 1)т-сплайнов в L™(Rn). Он рассмотрел пространство D~mHr(Rn), состоящее из обобщенных функций, га-е производные которых принадлежат "почти соболевскому" классу i?r(i2n) функций умеренного роста с ограниченной полунормой 1/2 hr = (lRjrm*dr) , которая при г < п/2 является нормой. Здесь Т - преобразование Фурье. Воспроизводящее ядро пространства D~mHr(Rn) относительно полунормы || • || есть радиальная базисная функция g7M = (- ip+l< s — £|2т1п |s — £|, 7 - целое, |s — £|2т иначе, где 7 = rn + г — п/2, 0 < 7 < т, [7] - целая часть 7, а

1/2 п \

- «О2)

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

D\cth - f)\\Lp{U) < Ch3-k-n^\\o-h - f\\wm, если ft - ограниченная область, удовлетворяющая слабому условию конуса, s > п/2, s - к - п/2 + п/р > 0, р > 2 [114, 95].

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

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

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

Теорема 5.2.3. Пусть Х{, Y{, Wi - гильбертовы пространства, Т{ G L{Xi,Yi), Bi G L(Xi,Wi) - некоторые операторы, i = 1 Если операторы нормально разрешимы и операторы В{ дополнительны к Ti} то оператор Т = [(Ti © Bi) ®. ® (Тп 0 Вп)] © [В\ <g>. ® Вп] нормально разрешим и N(T) = N(Ti) ® . ® N(Tn).

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

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

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

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

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

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

Теорема 5.3.5. Регуляриз о ванное воспроизводящее отображение 7 = Р7Р' + QitQ' удовлетворяет следующим условиям: а) Усре N(T)°, х£Х (Вх,В^ф) = 0; б) \/ср£ N(B)°, х£Х (Тх, T'jtp) = 0; в) 7 - воспроизводящее отображение (X, || • Цу); г) 7 - воспроизводящее отображение (X, || • ||в); д) 7 - воспроизводящее отображение (X, || • ||т®в); е) отображение 7 непрерывно, симметрично и действует на все пространство X.

Пусть теперь Х{, Wi - гильбертовы пространства, Т{ £ L(Xi,Yt) и В{ £ L(X{, W{) - строго взаимно дополнительные операторы, -у* £ L{X[, Х{) - регуляризованные воспроизводящие отображения относительно (XiJ-HT.J-llB,)»^1'---^

Теорема 5.3.7. Отображение 7 = 71 ® . ® 7п является воспроизводящим отображением пространства X = Х\ ® . ® Хп относительно нормы, порожденной оператором Т = (ф jBi) <g> . ® (Тп ф Вп), и относительно полунормы, порожденной оператором Т = Т © [.В\ ® . ® Вп].

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

10. Центральное место в практических исследованиях автора занимает алгоритм построения смешанного сплайна с весами. Пусть А\ = <pi ф . ф (рм5 Ai — (рм+i Ф • • • Ф <Pn и функционалы щ G Xг = 1,., N, линейно независимы. Предположим, что образ оператора Т замкнут, ядро конечномерно с базисом и\,.,ик и операторы Т и А = А\ ф А2 порождают эквивалентную норму в X.

Пусть гильбертово пространство X непрерывно вложено в Cioc(^)5 П С Rn5 G(s,t) - воспроизводящее ядро пространства X относительно полунормы || • ||у. Рассмотрим задачу

Vi{&a) = Zi, г = 1,., М, i=M+l Х построения смешанного сплайна с весами рг > 0. Решение этой задачи имеет вид

N К a(s) = Z Ai<PiG(s, •) + 2 ^гЩ(з).

Векторы неизвестных коэффициентов Л = (Ai,., \n)T, Ц = (^ъ • • •»А4^)7 находятся из невырожденной системы линейных уравнений где С и U - NxN- и iV х lf-матрицы с коэффициентами

Cij = ViVjG, uik = <pi(uk), i, j = 1,., iV, к = 1,., К

Pi действует на G по переменной s, а (pj - по £), Р - диагональная матрица с коэффициентами

Ра

0 при г = 1,., М, Pi при г = М + 1,., N.

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

Систему уравнений (0.10) можно преобразовать к системе меньшего размера с симметричной положительно-определенной матрицей, если построить некоторый линейный оператор Н : RN —> RN~K так, чтобы выполнялось условие N(H) = R(U).

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

N-К К aa(s) = £ Vii>iG(s,-) + Е/здМ, г=1 i=l где г/ji = Ef=i hijVjf i = 1, - • ,N - К.

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

Aav = Hz (0.11) с симметричной, положительно-определенной матрицей Аа — А 4-аНРН*, причем матрица А = НСН* симметрична и положительно определена. Коэффициенты матрицы А не зависят от выбора воспроизводящего ядра G и задаются формулой aij = (^iG,ipjG)x = {w^w3)y, причем функции Wi — TijiiG £ Y также не зависят от выбора воспроизводящего ядра.

Сплайн аа удовлетворяет условиям интерполяции с вектором za = z — аРН*и, а вектор неизвестных коэффициентов ц можно найти из условий интерполяции Асга = za и представления Т&а — £i=i ViWi, либо из системы уравнений Up = z — (С + aP)H*v.

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

Идея предложенного автором алгоритма заключается в построении матрицы Н в виде J2Q, где матрица Q приводит матрицу U к верхне-тре-^ угольной матрице с помощью, например, ортогональных преобразований, а матрица J2 понижает размерность вектора, отбрасывая его первые К компонент (см. §4.5). Отметим, что использование ортогональных преобразований оптимально в смысле сопсЬ, а именно, число обусловленности contb А матрицы А совпадает с числом обусловленности оператора являющегося сужением оператора VC на подпространство R(U)L, где V - ортопроектор на Щи)1 [62].

В практических задачах трудно гарантировать, что узлы сетки расположены "хорошо". Может возникнуть ситуация неединственности решения из-за вырождения сетки (например, сетка узлов попала в некоторое собственное афинное подпространство в Rn). Автор в [62] распространил предложенный алгоритм на случай вырождения сеток (см. п. 4.6.4). Для этого он разработал алгоритм модифицированного фЛ-разложения, позволяющий вычислять нормальное псевдорешение систем уравнений с прямоугольной матрицей. Этот алгоритм реализован под руководством автора в библиотеке 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 задана сетка узлов интерполяции ujs = {sl}f£1 и некоторая сетка узлов ujt = {tj}f=i. Будем искать сплайн a(s) = Л,■<?(*, tj) + 53 wM, (0.12) j=i 3=1 удовлетворяющий условиям ортогональности

53 XjUiitj) = 0, i = (0.13)

3=1 и минимально квадратично уклоняющийся от условий интерполяции r(si) = Zi, г = 1,., М. (0.14)

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

Данная задача есть задача наименьших квадратов с линейными ограничениями. Для ее решения поступаем следующим образом. Построим оператор Н : RN RN~K в виде J2Q, удовлетворяющий условию N(H) = R(Ut), Ut = (£")• Воспользовавшись заменой переменных Л = сводим данную задачу к задаче наименьших квадратов без ограничений в пространстве векторов v © д £ RN~K © RK. Последнюю задачу решаем, воспользовавшись (^.^-разложением с накоплением (см. п. 4.7.1).

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

Пусть X = X(Q), Y = Y(Ct) - гильбертовы пространства функций в Q. С Rn,T Е L(X, Y) - нормально-разрешимый оператор с конечномерным ядром и X непрерывно вложено в С\ос(0.). Пусть в узлах конечной сетки ш = {£1, С П заданы доверительные интервалы [zf, zf], zj < zf, г = 1,., N, в которые должен попадать сплайн.

Задачу

0.15) z+) = {xeX: zr < x(ti) <zt, г = 1,., N}, назовем задачей интервальной сплайн-интерполяции. 4 Как было отмечено выше, интервальный сплайн характеризуется узлами прилипания к ограничениям. П.-Ж. Лоран получил условия единственности решения, в которых существенно, что сетка узлов интерполяции удовлетворяет условию Хаара на N(T). Для полиномов многих переменных это условие обычно не выполняется. По этой причине, единственность решения при построении интервального сплайна многих перемен** ных гарантировать невозможно.

Решение задачи (0.15) имеет вид (0.12), (0.13), причем справедливо следующее: если cr(U) = zf, то Ai > 0; если <j(U) — zf, то Ai < 0; если zf < a(U) < zf, то Л; = 0 [41].

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

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

Теорема 4.8.2. Пусть сетка uj содержит L-набор для N(T). Тогда множество Su(z~,z+) решений задачи (0.15) есть замкнутый выпуклый ограниченный многогранник в пространстве сплайнов Spl(u>), параллельный N(T), т. е. если сг\,<Т2 £ , z+), то <ji — 02 €Е N(T).

Теорема 4.8.3. Пусть сетка из содержит L-набор для N(T). Тогда для любых <Ti,<j2 G Su;(z~, z+) множества активных узлов сплайнов <Ji и <72 совпадают. Обозначая через ш&с - множество активных узлов, имеем <ri(£) = <7г(£) для всех t е о>ас.

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

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

Теорема 4.8.4 дает обоснование алгоритма поиска решения путем перебора узлов прилипания сплайна. Отметим первый шаг предлагаемого в п. 4.8.5 алгоритма, отсутствующий в алгоритмах других авторов: построение начального приближения, в результате которого либо находится решение из ядра энергетического оператора, либо строится начальное приближение подсетки узлов прилипания сплайна. Сам процесс поиска сетки узлов прилипания также отличается от методов, использованных А.В. Ковалковым (см. [18]) и М.И. Игнатовым (см. [29]). Вместо того, чтобы сразу искать подсетку узлов прилипания для сплайна с заданными доверительными интервалами (и рисковать получить решение с числом узлов, сравнимым с числом узлов сетки), предлагается сначала ослабить ограничения, а затем постепенно их сжимать. При этом можно контролировать число узлов прилипания и строить более сложные критерии останова процесса приближения.

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

Теорема 4.8.7. Сплайн коэффициенты которого Хфр, задают вектор проекции градиента, есть решение задачи сплайн-интерполяции s) = £ AjG(s,tj) + £ fLkUk(s), к tjecj k= 1 т = argmin{||Tx||2, ж(4) = 7fc, tk G w}, где при tk £ wo, при tk £ й>i U а>2

Здесь Afc — коэффициенты предыдущего приближения. Предложенный алгоритм построения сплайна был реализован И.А. Молотковой [47] под руководством автора диссертации. Описание данного алгоритма завершается рассмотрением случая существенной не-[f> единственности решения, когда вся сетка узлов не содержит L-набор. Приводится модификация алгоритма для этого случая.

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

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

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

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

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

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

Заключение диссертации по теме «Вычислительная математика», Роженко, Александр Иосифович

Заключение

Автор выносит на защиту следующие результаты:

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

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

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

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

5. Усовершенствованы алгоритмы построения полиномиальных сплайнов произвольной степени на отрезке. Предложен алгоритм построения аналитического сплайна, основанный на сведении системы линейных уравнений метода воспроизводящих ядер (функций Грина) к алгоритму Анселона-Лорана с помощью ортогональной трансформации. Предложенный алгоритм не ухудшает число обусловленности сужения исходной матрицы на подпространство решений и не требует анализа взаимного расположения узлов сетки в отличии от известных ранее методов трансформации системы. Предложен также алгоритм модифицированного Q-R-разложения прямоугольных матриц, на основе которого разработан алгоритм построения аналитического сплайна при вырождении сетки узлов интерполяции.

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

Цитируемые совместные работы автора с А.Ю. Бежаевым [9, 78] и В.А. Василенко [19] не содержат результатов, вынесенных на защиту. Работа [110] - обзор ранее полученных результатов. В совместной работе с И.А. Молотковой [64] автору принадлежат идеи алгоритма, а И.А. Молотковой - их программная реализация.

На базе описанных алгоритмов создана библиотека программ по сплайн-аппроксимации JSpline+ [21, 93]. Библиотека разрабатывалась под научным руководством и при непосредственном участии автора студентами НГУ А.В. Галковым, О.А. Лихачевым, А.Е. Никишкиной, Н.Ф. Фурсовой, а также аспирантом ИВМиМГ СО РАН Д.В. Петраковым.

Список литературы диссертационного исследования доктор физико-математических наук Роженко, Александр Иосифович, 2003 год

1. Алберг Дж., Нильсон Э., Уолхы Дж. Теория сплайнов и ее приложения, — М.: Мир, 1972.

2. Ахиезер Н.И., Глазман И.М. Теория линейных операторов в гильбертовом пространстве. — М.: Гостехиздат, 1950. ^i 3. Базара М., Шетти К. Нелинейное программирование. Теория и алгоритмы. — М.: Мир, 1976.

3. Бежаев А.Ю. Оценки ошибки сплайн-интерполяции в многомерных ограниченных областях. — Новосибирск, 1984. — (Препринт / АН СССР. Сиб. отд-ние. ВЦ; 102).

4. Бежаев А.Ю. Следы £)"*-сплайнов на гладких многообразиях. — Новосибирск, 1984. — (Препринт / АН СССР. Сиб. отд-ние. ВЦ; 113).

5. Бежаев А.Ю. Воспроизводящие отображения гильбертовых пространств и харак- теризация операторных сплайнов / / Моделирование в механике. — Новосибирск, 1991. — Т. 5 (22), № 1. — 3-16.

6. Бежаев А.Ю., Роженко А.И. Вариационные сплайны в тензорных произведениях пространств. — Новосибирск, 1989. — (Препринт / АН СССР. Сиб. отд-ние. ВЦ; 853).

7. Варга Р. Функциональный анализ и теория аппроксимации в численном анализе. — М.: Мир, 1974.

8. Василенко В.А. Сходимость сплайнов в гильбертовом пространстве / / Числ. методы механики сплошной среды. — Новосибирск, 1972. — Т. 3, N2 3. — 18-23. Литература 218

9. Василенко В.А. Сглаживающие сплайны на подпространствах и теоремы ком- >^ пактности / / Числ. методы механики сплошной среды. — Новосибирск, 1974. — Т. 5, № 5. — 37-42.

10. Василенко В.А. Теория сплайн-функций. — Новосибирск: Изд-во НГУ, 1978.

11. Василенко В.А. Приближенное решение задачи продолжения функций методом конечных элементов / / Вариационно-разностные методы в математической физике. — Новосибирск, 1978. — 142-149. '^

12. Василенко В.А. Сплайн-функции: теория, алгоритмы, программы. — Новосибирск: Наука. Сиб. отд-ние, 1983.

13. Василенко В.А., Зюзин М.В., Ковалков А.В. Сплайн-функции и цифровые фильтры. — Новосибирск: Изд. ВЦ СО АН СССР, 1984.

14. Голуб Дж., Ван Лоун Ч . Матричные вычисления: Пер. с англ. — М.: Мир, 1999.

15. Завьялов Ю.С. Экстремальные свойства сплайн-функций многих переменных / / Теория приближения функций. — М.: Наука, 1977. — 182-187,

16. Завьялов Ю . С , Имамов А. О вариационных задачах теории сплайнов / / Математический анализ и смежные вопросы математики. — Новосибирск: Наука, 1978. — 27-36.

17. Завьялов Ю . С , Квасов Б.И., Мирошниченко В.Л. Методы сплайн-функций. — М.: Наука, 1980. Литература 219 4*0 ^ •^

18. Зуховицкий СИ. , Авдеева Л.И. Линейное и выпуклое программирование. — М., 1964.

19. Игнатов М.И., Певный А.Б. Натуральные сплайны многих переменных. — Л.: Наука. Ленингр, отд-ние, 1991.

20. Имамов А. О некоторых экстремальных свойствах сплайнов многих переменных / / Вычислительные системы. — Новосибирск, 1975. — Вып. 65. — 68-73.

21. Имамов А. Сходимость интерполяционного процесса в гильбертовом пространстве и ее применения / / Числ. методы механики сплошной среды. — Новосибирск, 1976. — Т. 7, № 7. — 15-21.

22. Имамов А. Некоторые вопросы теории сплайнов в гильбертовом пространстве: Автореф. дис. . . . канд. физ.-мат. наук: 01.01.07. — Новосибирск, 1977.

23. Имамов А. Сплайны, связанные с хаотической сеткой узлов / / Некоторые вопросы прикладной математики и механики. — Наманган, 1984. — Вып. 3. — 71-77.

24. Иосида К. Функциональный анализ. — М.: Мир, 1967.

25. Кириллов А.А., Гвихпиани А.Д. Теоремы и задачи функционального анализа: Учеб. пособие для вузов. — 2-е изд. — М.: Наука, 1988.

26. Корнейчук Н.П. Сплайны в теории приближения. — М.: Наука, 1984.

27. Кротов Д.С. Оценки сходимости метода композиции сплайнов на основе разбиения единицы. — Новосибирск, 1996. — (Препринт / РАН. Сиб. отд-ние. ВЦ; 1058).

28. Кротов Д.С. Применение метода композиции сплайнов в задаче многомерной интерполяции при помощи радиальных функций: Квалификационная работа на соискание степени магистра математики. — Новосибирск: НГУ, 1997.

29. Кутателадзе С. Основы функционального анализа. — 2-е изд., доп. — Новосибирск: Изд-во ИМ СО РАН, 1995.

30. Лигун А.А. Локальные сплайны двух переменных, асимптотически совпадающие с интерполяционными / / Исследования по современным проблемам суммирования и приближения функций и их приложения. — Днепропетровск: ДГУ, 1979. — 121-126.

31. Лоран П.-Ж. Аппроксимация и оптимизация. — М.: Мир, 1975.

32. Мазья В.Г. Пространства Соболева. — Л.: Изд-во ЛГУ, 1985.

33. Матвеев О.В. Аппроксимативные свойства интерполяционных 1)"'-сплайнов / / ДАН СССР. — 1991. — Т. 321, № 1. — 14-18. Литература 220

34. Матвеев О.В. Сплайн-интерполяция функций нескольких переменных и базисы в -щ^ пространствах Соболева / / Тр. Всесоюз. школы по теории функций. — М.: Наука, 1992. — 125-152. — (Тр. МИР АН, Т. 198).

35. Матвеев О.В. Интерполирование функций на хаотических сетках / / ДАН. — 1994. — Т. 339, № 5. — 594-597. 1}^

36. Матвеев О.В. Методы приближенного восстановления функций, заданных на хаотических сетках / / Изв. РАН. Сер. мат. — 1996. — Т. 60, № 5. — 111-156.

37. Молоткова И.А. Решение задачи многомерной сплайн-аппроксимации с дискретными ограничениями типа неравенств: квалификационная работа на соискание степени бакалавра. — НГУ, 1996.

38. Морозов В.А. Регулярные методы решения некорректно поставленных задач. — М.: МГУ, 1974.

39. Нейронные сети. STATISTICA Neural Networks: пер. с англ. — М.: Горячая линия- Телеком, 2000.

40. Никольский С М . Об устойчивых граничных значениях дифференцируемой функции многих переменных / / Матем. сб. — 1963. — Т. 61 (103), № 2. — 224-252.

41. Роженко А.И. Основные свойства ^-сплайнов и алгоритм их построения на основе эрмитовых конечных элементов / / Вычислительные алгоритмы в задачах математической физики. — Новосибирск: ВЦ СО АН СССР, 1985. — 113-127.

42. Роженко А.И. Тензорные и разрывные аппроксимации на основе вариационной ^ теории сплайнов: дис. . . . канд. физ.-мат. наук: 01.01.07. — Новосибирск, 1990.

43. Роженко А.И. Вариационные рациональные сплайны многих переменных / / Моделирование в механике. — Новосибирск, 1991. — Т. 5 (22), № 1. — 78-88.

44. Роженко А.И. Оценки сходимости рациональных ^'"-сплайнов / / Моделирование в механике. — Новосибирск, 1991. — Т. 5 (22), № 1. — 89-101.

45. Роженко А.И. Условия однозначной разрешимости задачи смешанной сплайн- аппроксимации. — Новосибирск, 1994. — (Препринт / РАН. Сиб. отд-ние. ВЦ; 1023).

46. Роженко 4 А.И. Разрывные 1)"*-сплайны и общие теоремы сходимости интерполяционных сплайнов. — Новосибирск, 1994. — (Препринт / РАН. Сиб. отд-ние. ВЦ; ^ ' 1030). Литература 221

47. Роженко А.И. О построении нормального псевдорешения системы линейных алгебраических уравнений с прямоугольной матрицей / / Сиб. журн. вычисл. математики / РАН. Сиб. отд-ние. — Новосибирск, 2001. — Т. 4, № 3. — 285-293.

48. Роженко А.И. Об ортогональном разложении пространства в задаче сглаживания сплайнами// Сиб. журн. вычисл. математики / РАН. Сиб. отд-ние. — Новосибирск, 2003. — Т. 6, № 3. — 291-297. • }

49. Рудин У. Функциональный анализ. — М.: Мир, 1975.

50. Соболев Л. Некоторые применения функционального анализа в математической физике. — Л.: Изд-во ЛГУ, 1950.

51. Соболев Л. Введение в теорию кубатурных формул. — М.: Наука, 1974.

52. Стейн И. Сингулярные интегралы и дифференциальные свойства функций. — М.; Мир, 1973.

53. Стечкин СБ. , Субботин Ю.Н. Сплайны в вычислительной математике. — М.: Наука, 1976.

54. Тихомиров В.М. Некоторые вопросы теории приближений. — М.: МГУ, 1976.

55. Трибель X. Теория интерполяции, функциональные пространства, дифференциальные операторы. — М.: Мир, 1980.

56. Уилкинсон, Райнп1. Справочник алгоритмов на языке АЛГОЛ. Линейная алгебра: Пер. с англ. — М.: Машиностроение, 1976.