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

РОССИЙСКАЯ АКАДЕМИЯ НАУК СИБИРСКОЕ ОТДЕЛЕНИЕ

ИНСТИТУТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ГЕОФИЗИКИ

На правах рукописи

РОЖЕНКО Александр Иосифович

ТЕОРИЯ И АЛГОРИТМЫ ВАРИАЦИОННОЙ СП Л АЙ Н- АП П РОКСИ М АЦИ И

01.01.07 — вычислительная математика

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

НОВОСИБИРСК 2003

Работа выполнена в Институте вычислительной математики и математической геофизики Сибирского отделения Российской академии наук.

Ведущая организация: Институт математики и механики

УНЦ РАН, г. Екатеринбург.

Защита состоится 17 марта 2004 г. в 15 часов на заседании диссертационного совета Д 003.061.01 при Институте вычислительной математики и математической геофизики СО РАН по адресу: 630090, г. Новосибирск, проспект Академика Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале библиотеки ИВМиМГ СО РАН.

Автореферат разослан 21 января 2004 г.

Официальные оппоненты:

доктор физико-математических наук, профессор Ю.Е. Воскобойников,

доктор физико-математических наук, Б.И. Квасов,

доктор физико-математических наук, профессор В.А. Цецохо.

Ученый секретарь диссертационного совета д.ф.-м.н., профессор

Ю.И. Кузнецов

гао& 8

Общая характеристика работы

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

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

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

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

РОС. НАЦИОНАЛЬНА* БИБЛИОТЕКА С.Петербург

гоо£гк

Научная новизна. Автором получены новые результаты в следующих направлениях:

• изучение абстрактной смешанной задачи сплайн-аппроксимации;

• исследования зависимости сглаживающего сплайна от параметра сглаживания;

• исследования сходимости интерполяционных сплайнов;

• исследования нормальной разрешимости операторов в тензорном произведении гильбертовых пространств;

• построение воспроизводящих отображений в тензорном произведении гильбертовых пространств;

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

Более полное перечисление основных научных результатов, полученных автором, приведено в конце автореферата.

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

Апробация работы. Основные научные результаты диссертации докладывались на международной конференции "Численные методы и приложения" (София, 1988), на семинаре ЕЦММ БАН под руководством чл.-корр. БАН В. Попова (София, 1989), на Сибирской региональной школе по вычислительной математике (Новосибирск,

1989), на Школе молодых ученых ВЦ СО АН СССР (Новосибирск, 1990, 1992, 1994), на семинаре ВЦ СО АН СССР "Методы вычислительной математики" (Новосибирск, 1982, 1989, 1990), на семинаре ИМ СО АН СССР "Методы теории сплайнов" под руководством д.ф.-м.н. Ю.С. Завьялова (Новосибирск, 1990), на Третьем сибирском конгрессе по прикладной и индустриальной математике ИНПРИМ-98, на Международной конференции по вычислительной математике МКВМ-2002 (Новосибирск, 2002), обсуждались на семинаре ИММ УНЦ РАН под руководством чл.-корр. РАН Ю.Н. Субботина (Екатеринбург, 2001, 2002), на семинаре ИВМиМГ СО РАН "Методы вычислительной математики" (1999, 2000, 2002).

Публикации. Список основных работ автора по теме диссертации приведен в конце автореферата.

Структура и объем диссертации. Работа состоит из введения, пяти глав, заключения, списка литературы из 117 наименований и приложения. Объем диссертации - 231 с.

Используемые обозначения: Через X, У, 2 обозначаем гильбертовы (иногда банаховы) пространства. Используем обычные обозначения для скалярного произведения и нормы в X: (•, -)х и || • Нижний индекс часто опускаем, если понятно из контекста, о каком скалярном произведении или норме идет речь. Через А € Ь(Х,У) обозначаем линейный ограниченный оператор А, действующий из X в У. Его ядро и образ обозначаем через N(A) и Я(А) соответственно. Важную роль в теории сплайнов играют нормально разрешимые операторы, т.е. такие, что И(А) замкнутое подпространство. Полунорму || Ас||у, порожденную оператором А, обозначаем также через ||а;|Ц- Аналогичные обозначения используем для скалярного произведения. Прямая сумма X ф У пространств X и У есть пространство пар вида х © у с покомпонентным сложением и умножением на скаляр. В X ф У естественным образом вводится |>-норма:

Содержание работы

Обычно используется 2-норма. Прямая сумма операторов А : X -* У и В : X -4 X есть оператор А®В:Х-*У®г, действующий по правилу (А Ф В)х = Ах ф Вх. 2-норма, порождаемая прямой суммой операторов, имеет вид

1МЦ®в = (||«|й + М%)1/2 = (\\Ах\\2у + \\Вх\\%)1/2.

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

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

Важную роль в работе играет

Теорема 1.2.4. Пусть X, У - банаховы пространства и А £ Ь(Х,У) - некоторый оператор. Следующие утверждения эквивалентны:

(а) оператор А нормально разрешим, т. е. Л(А) замкнуто в У;

(б) полунорма || ■ ||д замкнута в X, т. е. пространство (X, || • ||д) полное;

(в) фактор-пространство ■ ||д) - банахово;

(г) на фактор-пространстве Х^{А) нормы || • и Ц ■ ||д эквивалентны;

(д) существует такая константа С > О, что для любого у € ЩА) найдется х 6 А'1 [у) такой, что ||а;|| < С||?/||.

Здесь А - оператор, полученный из А факторизацией по №(А).

Приведенные в данной теореме критерии не являются новыми. Однако формулировка в виде набора эквивалентных утверждений имеет методическую новизну. Впервые она приведена автором в [9]. Необходимость критерия (д) для нормальной разрешимости оператора хорошо известна, а достаточность этого критерия была получена

автором в [1] в предположении рефлексивности основного пространства. Позднее требование рефлексивности удалось снять.

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

Теорема 1.3.2. Пусть X, Y, Z - банаховы пространства, А £ L(X,Y), В G L(X,Z) - некоторое операторы. Тогда справедливы следующие утверждения:

(а) если R(A ф В) замкнуто, то N(A) + N(B) замкнуто;

(б) если R(A) и BN{A) замкнуты, то R(A ф В) замкнуто;

(в) если R{A), R{B) и N(A) + N(B) замкнуты, то R(A ф В) замкнуто;

(г) если R(A) замкнуто и N(A) конечномерно, то R(A ф В) замкнуто.

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

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

(б) если на подпространстве N(A) нормы || • ||в и || • ||х эквивалентны и Д(-А) замкнуто, то нормы || • ||д©в « || • ||х эквивалентны в X;

(в) если R{A), R{B) и N(A)+N(B) замкнуты и N(A)nN(B)={0}, то нормы || ■ |U®B и || ■ ||x эквивалентны в X;

(г) ecAuR(A) замкнуто, N(A) конечномерно и N(A)HN(B) = {0}, то нормы || ■ Шея и || ■ ||jy эквивалентны в X.

Впервые теоремы 1.3.2, 1.3.3 приведены в [1] в более слабой формулировке (в критериях (б) и (в) предполагалось, что X рефлексивно). В работе [9] формулировки удалось усилить, воспользовавшись критерием (д) теоремы 1.2.4.

Глава 2 начинается с изучения абстрактной задачи смешанной сплайн-аппроксимации:

i«=arg min а||Тг||2 + ||Л2а;-г2||2, (1)

где Т € L(X,Y), Ах £ L(X,Zi), А2 6 L(X, Z2), все пространства гильбертовы, zi € z2 € Z2, а > 0 - параметр сглаживания.

Данная задача объединяет в себе задачи интерполяции (Ai = А, Аг = 0) и сглаживания {А\ = 0, Л2 = А).

Смешанная задача сплайн-аппроксимации известна также как интерполяционно-сглаживающая. Алгоритмы ее решения рассматривались гораздо раньше вариационной постановки. Постановка (1) была предложена А.Ю. Бежаевым и В.А. Василенко (1993). Ими же были получены условия однозначной разрешимости задачи (1) в практической ситуации конечномерности ядра оператора Т, условия характеризации и система операторных уравнений для смешанного сплайна. Автор продолжил эти исследования и доказал теорему о необходимых и достаточных условиях однозначной разрешимости задачи (1) в общем случае:

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

(а) существует оператор В € L(X, W), действующий в некоторое гильбертово пространство W, такой, что N(Ai) С N(B)

1 /о

и норма ||ж||т®вфА3 = (||Тг||2-|-||Вх||2+||>12®||2) эквивалентна норме ЦгЦх/

(б) смешанная задача (1) однозначно разрешима при любых z\ ф z2 е ф Z2;

(в) задача ü = arg min а\\Ти — /||2 4- ||Л2и — <?||2 однозначно

u€N(Ai)

разрешима при любых f ф g €Y Ф Z2;

(г) ко подпространстве N(Ai) нормы || • ||тед2 и II ' II* эквивалентны.

Данная теорема обобщает результаты П.-Ж. Лорана (1972) на смешанный случай. Она была фактически доказана автором в [1] и переформулирована в [9].

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

Теорема 2.1.5. Если R(T) незамкнуто, то найдется оператор А € L(X,Z), действующий в некоторое гильбертово пространство Z и удовлетворяющий условиям

N(T) П .ЛГ(Л) = {0}, R(A) и N(T) + N(A) замкнуты, (2)

такой, что задача сплайн-интерполяции

а = arg min ||Тг||2 (3)

хеА~г(г)

не имеет решения при некотором z 6 R(A).

В условиях (2) не хватает единственного условия (R(T) замкнуто) для того, чтобы оператор А ф Т порождал эквивалентную норму, что обеспечит однозначную разрешимость задачи (3). Как видно из данной теоремы, это условие существенно.

Решение задачи (1) определяется следующими условиями харак-теризации:

Теорема 2.2.1. Пусть R(T) замкнуто и смешанная задача (1) однозначно разрешима при любых допустимых исходных данных. Тогда решение этой задачи однозначно определяется из условий:

(а) Аг&а = Zi;

(б) а(Т&а,Ти) + (А2аа,А2и) = (z2,A2u) Vit € ЛГ(Лх).

Данная теорема доказана в [1]. Эквивалентное, но, на взгляд автора, более сложное условие характеризации было дано А.Ю. Бежа-евым и В.А. Василенко (1993).

Ясно, что любой сглаживающий сплайн является интерполяционным для некоторого другого вектора измерений z. П.-Ж. Лоран

(1972) рассмотрел обратную задачу: пусть имеется интерполяционный сплайн и задано а > 0; существует ли вектор г, для которого этот сплайн является сглаживающим? Обозначая через А+ и А+ операторы, сопоставляющие вектору г £ Я(А) интерполяционный и сглаживающий сплайны соответственно, данную задачу можно сформулировать так: совпадают ли образы операторов А+ и Ответ на этот вопрос положительный. Множества интерполяционных и сглаживающих сплайнов при фиксированном А совпадают и образуют пространство сплайнов 8р1(А, Т, X) с X, характеризующееся условиями

УиеЛГ(А) (Тх,Ти) = 0.

При фиксированных Т и X пространство сплайнов будем обозначать как 8р1(А).

Автор ставит аналогичный вопрос об операторе А+, сопоставляющем вектору г = г\ ф г^ € ЩАх) ф сплайн аа - решение задачи (1). Ответ на этот вопрос дает следующая теорема, доказанная в [9] и предлагающая также способ продолжения оператора на все пространство ф

Теорема 2.2.10. Пусть Я(Т) и Я{Ах) замкнуты и задача (1) однозначно разрешима при любых допустимых исходных данных. Обозначим А = А\ ф Аг- Тогда:

(а) : Д(Лх) ф Ъг -4 ЭрЦА) - линейный ограниченный оператор;

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

А^г = А+Тг, (4)

где V - ортопроектор на Я(Аг) ф Ц(А2), г = ф € ЩА^ ф

(в) оператор А+ непрерывно продолжается по формуле (4) на все пространство X — 2\ ф что соответствует замене задачи (1) на задачу

= "М2 +- *2||2;

(г) если (Т, А) - сплайн-пара и операторы Аг и А2 линейно независимы Ф А2) = R(A\) ф R(A2)), то сужение оператора А+ на R{A) есть непрерывный изоморфизм между и Spl (А).

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

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

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

оа = argmina||Ta;j|2 + |ji4x-z||2. (5)

z£X

Задача сглаживания исследовалась многими математики, начиная с Райнша (1967). Мы ограничимся здесь только исследованиями поведения сглаживающего сплайна при изменении а и алгоритмом, базирующемся на критерии невязки. Работы автора в этом направлении [6, 9, 12] содержат несколько новых результатов.

Предположим, что (Т, А) - сплайн-пара, и введем скалярное произведение

(u,v). = (и, v)t®a = (Tu,Tv)y + (Au,Av)z,

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

X = N(A)®N{T)<BX, X = {N(A) + N(T))i, (6)

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

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

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

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

А*А{и i + иг + «з) = ОщА)и i + /лг(г)«2 + Лиг, T*T(ui + «2 + из) = IN(A)U 1 -I- 0N(T)Uг + 7u3,

где ui G N{A), u2 6 JV(T), u3 £

(в) A,T € L(X) - перестановочные, самосопряженные, положительно определенные изоморфизмы, Л + Т — Ix, ||-4|| < 1,

11711 < 1-

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

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

аа = arg min а\\Тх - у\\2 + \\Ах - z||2.

Положим

(Too = arg min \\Ах — z\\2, tro = arg min \\Tx-y\\2.

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

(I + aA~1T)qa = qo-vo- <Гоо,

(I + а-1Т_1Д)Га = Гоо — &оо - &0-

Из теоремы 2.3.4 легко выводится сходимость сглаживающего квазисплайна сга к предельным элементам сг0 и (Too с оценками 0(a) и 0(а-1) соответственно, причем при <jq ф а^ эти оценки не улучшаемы по порядку [12]. Факт сходимости квазисплайна <та к предельным элементам хорошо известен. По-видимому, была ранее известна и оценка сходимости сплайна сга к <то со скоростью 0(a), хотя у В. А. Морозова (1974) и В.А. Василенко (1983) доказана только оценка О (а1/2).

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

(7)

где ß = а-1, ф{р) = <р(а). Если г/)(0) ф тр(оо), то при

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

Строгая монотонность и выпуклость вверх функции до-

казана В.А. Морозовым в конечномерном случае, А.Ю. Бежаевым -для абстрактного сглаживающего сплайна, а автором в [9] - для абстрактного сглаживающего квазисплайна. Используемый автором метод доказательства является новым, поскольку базируется на разложении квазисплайна по теореме 2.3.4.

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

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

1 ~ Ца») , , _ (Raz,R2az) _ (Raz,R2az)

ak+1 ~ "" v(ak)/e - w(ak)' Ш[а) ~ (.Raz,Raz) " **(«) '

Данная теорема дает возможность построения универсального алгоритма выбора параметра сглаживания:

0. Предварительный шаг алгоритма: поиск критических значений невязки, которые суть

£min = min \\Ах - zII2, emax = min ||Ax - z\\2. xex x£n(t)

Значение emax обычно находится легко, a £m;a равно нулю, если линейные функционалы, из которых составлен оператор А,

линейно независимы. (Если сплайн ищется методом конечных элементов, то ет{п обычно отлично от нуля и довольно легко вычислимо.) После проверки неравенств ет-т < е < етах начинаем итерации с произвольного ао > 0.

1. Если <р(с1к) > £, то выполняется итерация по методу Ньютона (теорема 2.4.4). При этом в последующих итерациях значения а* будут монотонно сходиться к точному решению.

2. Если же <р(ак) < е, то выполняется шаг дробно-рационального приближения по формуле

шах

*+1 * <р(ак)/е-<р(ак)/е тах '

1 - ы(а)

Этот алгоритм реализован автором в библиотеке программ Л8р1ше+.

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

Лемма 2.4.3. Для оператора невязки Яа € Ь(^), задаваемого правилом Яаг — г — Аоа = (I — АА^)г, имеет место следующая формула дифференцирования по параметру а:

£>*Д„ = (~1)к+1^Яка(1 - Я*), к> 1.

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

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

А<тао, (8)

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

Похожее разложение (только самого сплайна сга, а не невязки) рассматривалось ранее А.Ю. Бежаевым (1993): им была доказана сходимость разложения сплайна иа в ряд Тейлора, но на открытом интервале (0,2ао). Автору в теореме 2.5.1 удалось расширить интервал сходимости ряда для Аоа и явно представить разложение по степеням оператора Яа.

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

Теорема 2.5.3. Пусть /?о > 0- Тогда невязка г — Аа1ц3 представила в виде суммы ряда

* - Аат = (г - Аа1/0О), (9)

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

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

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

Далее в гл. 2 изучается сходимость абстрактных интерполяционных сплайнов при "сгущении сеток узлов интерполяции". В терминах операторов интерполяционных условий А{ это означает, что ядра операторов Ai ассимтотически сужаются до некоторого подпространства Н(А). Традиционно рассматривают два способа сужения ядер: вложенное (^(^¡+1) С М(А{)) и произвольное.

В случае вложенного сужения ядер В.А. Василенко (1972) ввел понятие правильной системы операторов, формирующих условия интерполяции, и доказал, что если система правильная, то имеет место сходимость интерполяционного сплайна к интерполируемой функции из основного пространства. А. Имамов (1976) установил необходимость этого условия при таком способе сгущения сеток. Автор в [2] установил, что критерий правильности эквивалентен нулевому пересечению ядер операторов А,, и доказал сходимость интерполяционных сплайнов на вложенных сетках, если пересечение ядер нетривиально.

В случае произвольного сужения ядер для доказательства сходимости необходимы дополнительные условия. Сходимость абстрактных интерполяционных сплайнов при произвольном способе сгущения сеток впервые исследовалась Жоли (1967). Он установил следующий критерий сходимости: если ядро энергетического оператора Т конечномерно и линейные оболочки функционалов интерполяции образуют ф-последовательность, то интерполяционные сплайны сходятся к интерполируемой функции. Этот критерий применен Дюшоном (1977) при доказательстве сходимости 1>т-сплайнов в Я„ и их обобщений, называемых нами сплайнами Дюшона.

В.А. Василенко (1993) предложил другой критерий сходимости интерполяционных сплайнов, базирующийся на непрерывности параметрического семейства функционалов, по которым осуществляется интерполяция. В применении к £>т-сплайнам в области Л ему удалось доказать следующую теорему: если область П ограничена и имеет липшицеву границу, то при произвольном способе сгущения комечкыа; е-сеток всюду в П £>т-сплайны, интерполирующие функцию / € И^П), сходятся к /.

Используя аналогичный подход, автор в [2, 5, 9] усилил результаты В.А. Василенко и снял практически все ограничения на область и сетки узлов интерполяции (эти ограничения выделены в предыду-

щем абзаце курсивом). В настоящей формулировке осталось только одно (и весьма существенное) ограничение: последовательность сеток должна быть предельно вложенной (ш{ С шПП).

Пусть П С Rn - некоторое множество, и задано параметрическое семейство функционалов $(П) = {<pt 6 X', t € П}. Далее, пусть ш - некоторое подмножество в П, а / е X - произвольный элемент. Положим

M(f, и>) = {хеХ: <pt(x) = ipt(f), t е w}.

Теорема 2.6.7. Пусть N(T) конечномерно, множество П локально-компактно (т.е. П \ SI замкнуто) и семейство функционалов Ф(П) непрерывно по параметру (т.е. ||<ps — <pt\\x' —► 0 при s —> t, s,t 6 il). Пусть также задача

а = arg min ||Txl|2

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

Тогда если последовательность множеств {a>j С w П предельно плотна в ш, то существует такое ¿о € IN, что при г >%о задача

= arg min ||Tz||2 ®6 M(f,u>i)

однозначно разрешима, и ||сг» — а\\х —> 0 при i -»• оо.

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

= arg min a\\Txf + \\A2x-z2f. (10)

x€A^l(xi)nBT

Здесь предполагается, что A^x(zi) ПЕт ф 0, т.е. условия интерполяции А\х — z\ не противоречивы на Ет.

Введем по теореме 2.1.3 эквивалентную норму

II ' II* — II ' 11>/вТфВ©Аа»

возьмем ортопроектор Рт на Ет в норме || • ||» и зададим оператор сплайн-интерполяции S по формуле

Su = arg min a\\Tx\\2 + ||42a;||2.

An=Aiu

Автор в [4] доказал следующую теорему сходимости сплайнов ога к аа-.

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

(а) dimii(i4i) < оо,

(б) \\{I-Pr)S\\,<C<l. Тогда Ца* - сга\\х при т 0.

Глава 3 посвящена алгоритмам построения вариационных сплайнов, основанным на их представлении с помощью воспроизводящего ядра полугильбертова пространства. Здесь приводятся элементы общей теории и излагаются алгоритмы одномерной сплайн-аппроксимации.

В § 3.1 приводятся элементы теории воспроизводящих отображений, с помощью которой в дальнейшем выполняется характериза-ция пространства сплайнов Spl(v4,T, X). Эта теория была развита Аронжайном (1950) для воспроизводящих ядер гильбертовых пространств. Идея применения ядер для характеризации пространства сплайнов возникла у Аттья (1965) и использовалась в дальнейшем многими математиками. А.Ю. Бежаев (1991) ввел понятие воспроизводящего отображения, обобщающее теорию воспроизводящих ядер на абстрактные полугильбертовы пространства.

Пусть X - гильбертово пространство и р(х) - ограниченная полунорма в X (р(х) < С||а;||х Vx £ X), порождаемая скалярным произведением p(u,v) (р(х) = р*-/2(х, х)). Пусть X - полное пространство относительно полунормы р, т.е. (X, р) - полугильбертово пространство. Обозначим через Р ядро полунормы р, а через Р° - аннулятор подпространства Р, т.е. множество функционалов

Р° = {v? € X': Vti € Р <р{и) = 0}.

Здесь X' - сопряженное пространство ограниченных линейных функционалов над X.

Пусть X - подпространство некоторого векторного пространства X. Линейное отображение 7 : X' X называют воспроизводящим отображением пространства X относительно полунормы р, если 7(Р°) С X и

Ч<р€Р°, х е X <р(х) =р(х,у<р). (11)

Если Р ф {0}, то воспроизводящее отображение пространства {Х,р) не единственно.

Если X = i2n - векторное пространство вещественнозначных функций над П С Rn, то функцию G(s,t) £ ДПхП называют воспроизводящим ядром, если индуцируемое этой функцией линейное отображение 7 : X' -»• X по формуле 7^> = <pG (функционал <р действует на G по переменной f) есть воспроизводящее отображение полугильбертова пространства (Х,р).

Автор в [9] ввел понятие (И, ^-согласованного воспроизводящего отображения. Пусть U и V - некоторые замкнутые подпространства в X, являющиеся дополнениями к Р (U П Р = {0}, U + Р = X, УПР = {0}, V + Р — X). Линейное отображение 7 : X' -> X назовем {U, V)-согласованным, если:

(а) Д(7) = U-,

(б) Vv е X', х е V <р(х) =p(x,jip). Следующая теорема доказана автором в [9]:

Теорема 3.1.7. (U, V)-согласованное отображение существует, единственно, непрерывно и является воспроизводящим отображением полугильбертова пространства (Х,р).

В §3.2 приводятся известные результаты характеризации пространства сплайнов Spl(A,T,X) с помощью воспроизводящего отображения пространства (X, || • ||т).

В §3.3 рассматривается смешанная задача сплайн-аппроксимации с весами. Пусть Ai = tpi ф ... ф у>м> А2 = <рм+1 Ф ... Ф фи и функционалы <pi £ X', i = 1,..., N, линейно независимы. Предположим, что образ оператора Т замкнут, ядро конечномерно с базисом и к и операторы Т и А = Ai ф А2 порождают эквивалентную норму в X.

Пусть X - подпространство в fi С fín, G{s, t) - воспроизводящее ядро пространства X относительно полунормы || • ||х- Рассмотрим задачу

<Pi{oa) = Zi, i = 1,..., М, N

<*\\Т&а\\2+ £

t=AÍ+l

построения смешанного сплайна с весами p¿ > 0, i = М + 1,..., N. Решение этой задачи имеет вид

N К

t=l i=l Векторы неизвестных коэффициентов

A = (Ai,...,A N)t, ц = (/xi,...,/ík-)t

находятся из невырожденной системы линейных уравнений

(СГ S) o-С).

где С и U - NxN- и N х .йГ-матрицы с коэффициентами

Cíj = 4>i4>jG, uik = Pi(ufc), i,j = 1,...,N, k = l,...,K

(<Pi действует на G по переменной s, a y>j - по í), P - диагональная матрица с коэффициентами

при i = 1,... , М, Pii ~ ^ ~ при i = М + 1,..., N.

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

Известно, что систему уравнений (12) можно преобразовать к системе меньшего размера с симметричной положительно-определенной матрицей, если построить некоторый линейный оператор Н : Я1* -4 так, чтобы выполнялось условие N(11) =

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

ы-к к

«=1 »=1

где г/>, = г = 1,..., N — К, Иу - коэффициенты матри-

цы Н.

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

Аа V = Нг (13)

с матрицей Аа = А + аНРН*, причем матрица А = НСН* симметрична и положительно определена. Коэффициенты матрицы А не зависят от выбора воспроизводящего ядра С7 и задаются формулой ау = (^¿<3, ^ФjG)т = причем функции = Т^С? € У также не зависят от выбора воспроизводящего ядра.

Сплайн аа удовлетворяет условиям интерполяции с вектором га = г - аРН*р, а вектор неизвестных коэффициентов ц можно найти из условий интерполяции А&а = га и представления Таа = либо из системы уравнений 11ц = г — (С + аР)Н*и.

Преобразование системы уравнений (12) к системе с симметричной, положительно-определенной матрицей хорошо известно. Однако факт, что при этом мы приходим к алгоритму Анселона-Лорана, не был замечен. Отметим также, что в теореме 3.3.6 дополнительно доказывается независимость матрицы системы (13) и функций Wi от выбора воспроизводящего ядра. Эти факты были замечены автором в [9].

Далее в § 3.4, 3.5 подробно излагаются алгоритмы построения полиномиальных сплайнов нечетной и четной степеней соответственно. Изложение начинается с получения воспроизводящего ядра Сга(з, ¿)

оператора m-кратного дифференцирования. Поскольку это ядро хорошо известно, доказательство приведено только с целью демонстрации техники, основанной на теореме 3.1.7 о характеризации (U, V)-согласованного воспроизводящего отображения. Для построения полиномиальных сплайнов нечетных и четных степеней используется алгоритм Анселона-Лорана, подробно описанный В. А. Василенко (1983). Он был реализован в различных версиях библиотеки программ LID A (Library on Interpolation and Data Approximation), разрабатывавшейся под руководством B.A. Василенко в Вычислительном центре СО АН СССР в 1980-1987 гг. (последняя версия алгоритма в библиотеке LIDA-3 была реализована автором диссертации).

Отметим, что использовавшийся при этом метод расчета коэф- .

фициентов матрицы А через скалярные произведения Р-спл айнов Wi неэффективен (требует в среднем 3m4N арифметических операций для расчета коэффициентов матрицы). Гораздо эффективнее (всего за 3m2N действий) можно вычислить коэффициенты матрицы А, воспользовавшись ее представлением в виде НСН*. Этот метод использовался автором в новой версии алгоритмов полиномиальной сплайн-аппроксимации, реализованной в библиотеке JSpline+. Способ вычисления полного полиномиального представления сплайна в ячейках сетки также несколько отличается от метода, предложенного В.А. Василенко. При вычислении младших производных полиномиального сплайна в узлах сетки автору удалось обойтись без решения систем линейных уравнений (использовались явные расчетные формулы, основанные на интерполяционной формуле Ньютона и ее преобразовании в ряд Тейлора).

Хранение полиномиального сплайна в полном полиномиальном разложении очень неэффективно по количеству используемой опера- ,

тивной памяти: если функция на сетке из N узлов аппроксимируется сплайном степени 2m — 1, то количество коэффициентов в решении будет 2mN, т.е. возрастет в 2т раз. Это служит серьезным пре- »

пятствием для применения полного полиномиального разложения в тензорных сплайнах. Гораздо эффективнее по используемой памяти будет разложение по Я-сплайнам.

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

ния сплайна в точке можно использовать два метода: нисходящий и восходящий. При нисходящем методе берется группа коэффициентов тех В-сплайнов в разложении сплайна, носитель которых пересекается с точкой расчета, и с помощью формул пересчета с понижением степени В-сплайнов вычисляется значение сплайна в точке. При восходящем методе значения В-сплайнов в заданной точке определяются, начиная с В-сплайна нулевой степени, путем повышения степени базисных сплайнов. Восходящий метод был предложен де Бором (1978) и затем незаслуженно забыт, видимо, потому что количество операций этого метода вдвое превышает число операций нисходящего метода. Однако оказывается, что после небольшой модификации число операций восходящего метода становится просто равным числу операций нисходящего метода (правда требуется потом еще дополнительно 2п операций для расчета значения сплайна в точке по вектору коэффициентов и значений В-сплайнов). Более того, если требуется рассчитать несколько сплайнов в одной точке (например, в задачах тензорной аппроксимации), то восходящий метод становится существенно эффективнее нисходящего, поскольку после однократного расчета значений В-сплайнов степени п в точке за 3.5п2 операций расчет значения сплайна в точке выполняется существенно быстрее - всего за 2п операций.

В § 3.7 приводится модифицированный алгоритм расчета полиномиального сплайна, начинающийся с алгоритма Анселона-Лорана, а заканчивающийся построением В-сплайнового разложения полиномиального сплайна. По числу операций данный алгоритм практически совпадает с алгоритмом из §3.4. В работе [9] автор использовал метод решения локальных систем уравнений для получения В-сплайнового разложения сплайна по В-сплайновому представлению его 7П-й производной. При реализации этого алгоритма в библиотеке Л8р1те+ автору удалось избавиться от решения локальных систем линейных уравнений, получив явные формулы пересчета полинома в форме Тейлора в В-сплайновое разложение. Описание этого алгоритма приведено в диссертационной работе. Ранее оно не публиковалось.

§ 3.8 посвящен построению гетерогенного полиномиального сплайна по разнородной информации в узлах сетки (как по значениям функции, так и по производным порядка не выше тп — 1). В алгоритме используются известные локальные базисы эрмитовых конечных

элементов. Автор реализовал этот алгоритм в библиотеке программ ЬША-З.

Наконец, в §3.9 рассматривается алгоритм построения вариационного L-сплайна. Отметим два частных случая: экспоненциальный и тригонометрический сплайны, соответствующие операторам D2 — а21 и D2 + а21. Для них легко выводится линейная система уравнений алгоритма Анселона-Лорана с трехдиагональной ленточной матрицей по типу матрицы для кубических сплайнов. Автору представляется перспективным использование этих сплайнов в интерполяции.

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

Изложение материала начинается в § 4.1 с хорошо известных Dm-сплайнов многих переменных. В случае ограниченной области определение 1)т-сплайна обычно давалось в пространстве W^fî). При этом, чтобы обеспечить замкнутость образа оператора Dm, прея-полагалась липптицевость границы области. В кандидатской диссертации автора были рассмотрены £>"'-силайны в ограниченных областях с разрезами, точнее, в областях, удовлетворяющих слабому условию конуса. Автор в [2] распространил постановку задачи Dm-аппроксимации на произвольную область il в Rn. При этом в качестве X надо брать L^((î) - пространство функций в ÎI, т-е частные производные которых интегрируемы с квадратом.

§ 4.2 посвящен сходимости Рт-сплайнов. Сходимость ^"'-сплайнов в Rn изучалась Дюшоном (1976). В ограниченной области с липшицевой границей сходимость изучалась А. Имамовым (1976) и В.А. Василенко (1983). Доказательство сходимости интерполяционных £>т-сплайнов в произвольной области получено автором в [2, 5].

Теорема 4.2.3. Пусть последовательность множеств {wi С ЙП ii}tew предельно плотна в w, m > п/2 и / € - интерполируе-

мая функция. Тогда последовательность интерполяционных сплайнов <?i = SWif сходится к сплайну <т = Swf в норме пространства

Здесь Sw - оператор, сопоставляющий функции / G интерполя-

ционный Z)m-сплайн а с условиями интерполяции a(t) = f(t), t Ç а>.

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

Теорема 4.2.2. Пусть О С Rn ~ локально-компактное множество, X непрерывно вложено в С^с(П) при некотором 0 < а < 1. Предположим, что оператор Т € L(X,Y) имеет конечномерное ядро и замкнутый образ; множество ш С Я содержит L-набор точек для N(T); последовательность множеств {ич С шГ\ fi}tgn предельно плотна в ш. Тогда найдется такое число ¿о > 0, что при i > io задача

<т( = argmin{||Ta;||2, х € X, x(t) = /(t), t 6 u>i}

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

а = argmm{||Ta;||2, х е X, x(t) = f(t), t е ш} при i оо.

Здесь С1"с(П) - пространство непрерывных функций в П, локально удовлетворяющих условию Гельдера с параметром 0 < а < 1 (отметим, что параметр а может зависеть от t е Я).

Теорема 4.2.2, в свою очередь, выводится из приведенной выше теоремы 2.6.7 о сходимости интерполяций на сгущающемся семействе функционалов.

Оценки сходимости £>т-сплайнов на /i-сети узлов интерполяции вида

IIDa(a - /)||м<1) < Chm'k~n/2+n^\\Dm{o - /)|Ua(n), (14)

|a| = k, p > 2 и m - k — n/2 + n/p > 0 (m — k — n/2 > 0 при p = oo), были получены Дюшоном (1978) для следов £>т-сплайцов из L™(Rn) в ограниченную область Я, удовлетворяющую слабому условию конуса. Затем эти оценки были перенесены А.Ю. Бежаевым (1984) на случай функции, имеющей h-сетъ нулей в ограниченной области с липшицевой границей. В работе [2] автор распространил эти оценки на ограниченные области, удовлетворяющие слабому условию конуса, а в [9] сделал еще одно усиление оценок: убрал условие ограниченности области. Требуется только, чтобы множество О было

объединением конечного числа областей, удовлетворяющих слабому условию конуса и допускающих непрерывное продолжение функций из Ь™ с сохранением класса гладкости.

§4.3 посвящен построению £>т-сплайна методом конечных элементов. Специфика метода конечных элементов состоит в том, что обычно не гарантируется существование интерполяционного сплайна на подпространстве (возможно, что А-1 (г) П Ет =0). Поэтому вместо условий интерполяции рассматривают условия псевдоинтерполяции на множестве

Автору в этом пункте принадлежит следующее утверждение: решение псевдоинтерполяционной задачи совпадает с решением задачи интерполяции методом наименьших квадратов.

Алгоритм построения £>т-сплайна методом конечных элементов применялся многими математиками. В литературе рассматривается два подхода: построение конечных элементов путем триангуляции сетки узлов интерполяции (при этом обычно удается обеспечить непротиворечивость интерполяционной задачи, но применение этого подхода затруднено в практических задачах с большим числом узлов интерполяции) и использование сетки конечных элементов, не связанной с сеткой узлов интерполяции. Второй подход использовался А.Ю. Бежаевым (1983) в библиотеке LIDA-2 в комплекте программ FINEL. Автор также использовал этот подход в комплекте программ BREAK (1989), служащем для построения £>т-сплайна в двумерной области с разрезами.

§ 4.4 посвящен сплайнам Дюшона. Дюшон (1976) получил воспроизводящее ядро GT пространства (D~mHr(Rn), \\Dm • Цд,.):

RT(z) = е ЕТ : \\Ах - z\\ = mm \\Аи - z|||.

7 - целое, иначе,

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

Соответствующие этому ядру сплайны М.И. Игнатов и А.Б. Пев-ныи называют степенными (при 7^ IN) и логарифмическими (при 7 € IN). Отметим, что знак воспроизводящего ядра (?7 установлен М.И. Игнатовым и А.Б. Певным, что весьма важно при построении сглаживающих сплайнов. Обобщением сплайнов Дюшона является теория радиальных базисных функций, которая очень популярна за рубежом.

Использование воспроизводящих ядер G1 открывает возможности приближения функций с большим числом переменных. В отличие от £)т-сплайнов, для которых должно выполняться неравенство т > п/2, у сплайнов Дюшона параметр 7 не связан с размерностью п пространства независимых переменных. Это позволяет использовать, например, псевдолинейные (т = 2, 7 = 1/2), псевдоква-дратические (то = 2, 7 = 1) и псевдокубические (т = 2, 7 = 3/2) сплайны Дюшона в задачах с любым числом независимых переменных. При этом размерность ядра оператора Dm остается небольшой (dim N{Dm) = п+1) и условия единственности решения проверяются легко.

§ 4.5 посвящен построению сплайна многих переменных, если воспроизводящее ядро известно (например, ядро Дюшона). Такие сплайны автор называет аналитическими. Многие математики сводили систему уравнений метода функций Грина к системе с положительно-определенной матрицей (см. теорему 3.3.6). При этом использовались в основном геометрические идеи при построении матрицы Я: выбирались подсетки интерполяционных узлов, на которых строились конечно-разностные схемы, аннулирующие базис ядра оператора Т. Такой подход имел ограниченное применение и требовал дополнительных геометрических построений и проверок. К тому же не было гарантии, что обусловленность матрицы не будет существенно ухудшена в результате плохого выбора псщсеток узлов. Автор в [7, 9] предложил чисто алгебраический метод сведения исходной системы уравнений к системе с положительно-определенной матрицей, не требующий учета геометрии расположения узлов, обладающий высокой устойчивостью за счет применения ортогональных преобразований и не ухудшающий обусловленность сужения исходной матрицы на подпространство решений. Отметим также, что приведенный алгоритм легко обобщается на случай произвольной правой части (см. [10]) для блочной системы типа (12).

Идея предложенного автором алгоритма заключается в построении матрицы Н в виде где матрица (} приводит матрицу V из (12) к верхне-треугольной матрице с помощью, например, ортогональных преобразований, а матрица Зг понижает размерность вектора, отбрасывая его первые К компонент. Отметим, что использование ортогональных преобразований оптимально в смысле сопс^, а именно, число обусловленности сопс^ А матрицы А совпадает с числом обусловленности оператора "РС\щщ±, являющегося сужением оператора ТС на подпространство Д(£/)х, где V - ортопроектор на Л(£0Х [Ю].

В практических задачах решение может оказаться неединственным в случае вырождения сетки (например, сетка узлов попала в некоторое собственное афинное подпространство в Д„).

§4.6 посвящен алгоритму построения сплайна в таких случаях. Автор в [10] предлагает модификацию алгоритма Анселона-Лорана, обеспечивающую выбор в некотором смысле наилучшего решения в случае вырождения сетки. Этот алгоритм основан на модификации фР-разложения прямоугольных матриц, также предложенной в [10].

В библиотеке 18рНпе+ реализованы 3 варианта модифицированного алгоритма решения системы (12) с возможностью использования методов вращений, отражений и Гаусса с выбором главного элемента при построении преобразования П. Реализовано также обобщение этого алгоритма на случай произвольной правой части.

Остальные параграфы главы 4 посвящены алгоритмам приближения функций по неточным данным. В § 4.7 рассматривается алгоритм построения сплайна методом наименьших квадратов, а в § 4.8 изучается алгоритм построения сплайна по доверительным интервалам значений, заданных в узлах сетки.

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

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

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

Формально, пусть в Дп задана сетка узлов интерполяции шв — {«<}& и некоторая сетка узлов шг — Будем искать сплайн

N К

»М = £ ЭД8' ь) + £ (15)

3=1 ¿=1

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

= 1 = 1,..., К, (16)

¿=1

и минимально квадратично уклоняющийся от условий интерполяции *(•<) = *, г = 1,..., М. (17)

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

Данная задача есть задача наименьших квадратов с линейными ограничениями. Для ее решения поступаем следующим образом. Построим оператор Н : Д^ —► в виде ./г*?, удовлетворяющий условию N(11) = Л(СГ4), ^ = Воспользовавшись заменой переменных Л = Я* V, сводим данную задачу к задаче наименьших квадратов без ограничений в пространстве векторов 6 В?1~к@11к. Последнюю задачу решаем, воспользовавшись модифицированным фД-разложением с накоплением.

Алгоритм построения сплайна методом наименьших квадратов описан в [11]. Новизна предложенного метода в том, что сплайн наименьших квадратов должен точно удовлетворять линейным ограничениям, обеспечивающим его принадлежность пространству сплайнов. Алгоритм модифицированного метода вращений с накоплением реализован в библиотеке ЛЭрИпе-Ь

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

и достаточные условия характеризации решения. Основная особенность решения такой задачи заключается в разделении множества узлов на "узлы прилипания", в которых решение "прилипает" к верхнему или нижнему ограничению, и свободные узлы, в которых решение проходит строго между ограничений. Бели некоторый узел сетки свободный, то соответствующий ему коэффициент в представлении (15) равен нулю. Таким образом, в представлении сплайна участвуют базисные функции только в узлах прилипания, и можно надеяться получить решение, в котором задействовано существенно меньше узлов сетки. Подход, основанный на поиске узлов прилипания сплайна, был реализован A.B. Ковалковым для одномерного сплайна (1984). Аналогичные идеи были запрограммированы М.И. Игнатовым (1991) для сплайна многих переменных.

Пусть X X (П), Y = Y((l) - гильбертовы пространства функций в (1 С Rn, Т £ L(X, Y) - нормально разрешимый оператор с конечномерным ядром, X непрерывно вложено в Cioc(fl). Пусть в узлах конечной сетки ш = {£i,...,£iv} С О заданы доверительные интервалы [z~< zf, i = 1,...,N, в которые должен попадать сплайн.

Задачу

<r = arg min ||Ti||2, (18)

X£Mu{z~ ,Z + )

Mu(z',z+) = { xeX: Zi < x{U) < zf, г = 1,..., iV},

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

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

Решение задачи (18) имеет вид (15), (16), причем справедливо следующее: если a(ti) — z~, то А, > 0; е'сли <r(i,) = zf, то А, < 0; если z~ < er(ti) < zf, то А* = 0.

Узлы сетки, для которых А, ф 0, назовем активными, а в которых a(ti) = z~ или (t(U) = zf - узлами прилипания. Ясно, что сетка узлов прилипания содержит в себе сетку активных узлов.

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

Теорема 4.8.2. Пусть сетка ш содержит L-набор для N(T). Тогда множество Sa,(z~,z+) решений задачи (18) есть замкнутый выпуклый ограниченный многогранник в пространстве сплайнов Spl(w), параллельный N(T), т.е. если cri,сг2 G Sw(z~,z+), то cri — <r2 € N(T).

Теорема 4.8.3. Пусть сетка ш содержит L-набор для N(T). Тогда для любых <7i,(72 € Su(z~,z+) множества активных узлов сплайнов cri и <72 совпадают. Обозначая через шЛС множество активных узлов, имеем <ri(i) = ^¡{t) для всех t б а/4®.

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

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

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

Метод решения промежуточной задачи квадратичного программирования на подсетке также отличается от методов, использован-

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

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

к

"(*) = Ц + Длил (в).

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

а = агдтт{||Та;||2, х[Ьк) = 7*, Ьк € £>},

где

_ Г 0 при 6 ш0, ~ ^ —Л* при £ й>1 и П>2-

Здесь А*. - коэффициенты предыдущего приближения.

Предложенный алгоритм построения сплайна был реализован И. А. Молотковой (1996) под руководством автора диссертации. Описание данного алгоритма завершается рассмотрением случая существенной неединственности решения, когда вся сетка узлов не содержит ¿-набор. Приводится модификация алгоритма для этого случая.

Глава 5 посвящена сплайн-аппроксимации в тензорном произведении пространств. Она написана на основе статьи [8].

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

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

Следуя В.А. Морозову, назовем линейные ограниченные операторы А и В взаимно дополнительными, если оператор АфВ порождает эквивалентную норму в Л" (у В.А. Морозова операторы взаимно дополнительны, если имеет место односторонняя оценка ||®|Ц©в > С||а;||х; однако, поскольку обратная оценка очевидна в силу ограниченности операторов, условие взаимной дополнительности для ограниченных операторов совпадает с условием эквивалентности норм). Будем также называть оператор А дополнительным к В (В дополнительным к .А), если А и. В взаимно дополнительны.

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

Теорема 5.2.3. Пусть Х{, У{, - гильбертовы пространства, Т^ € У^), В{ € Ь(Хг, - некоторые операторы, г = 1,..., п. Если операторы Т{ нормально разрешимы и операторы дополнительны к Т{, то оператор

Т = [(2\ ® Вг) ® ... ® (Г„ © В„)] © \Вх ® ... ® нормально разрешим и Ы(Т) — ® ... ® Ы(Тп).

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

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

Операторы Т € Ь(Х,У) и В £ Ь(Х, ЦТ) назовем строго взаимно дополнительными, если они взаимно дополнительны и линейно не-

зависимы. Это означает, что пространство X разлагается в прямую сумму И(Т) + N(13), а операторы Т и В нормально разрешимы.

Пусть 7 - воспроизводящее отображение пространства (X, || ■ ||т) и 7Г - воспроизводящее отображение пространства (X, || • ||в). Возьмем проектор Р е 1>(Х) со свойствами: М(Р) = #(Т), ЩР) — Построим двойственный ему оператор Р' € Ь{Х') по правилу (Р'<р)(х) = <р(Рх), х € X, <р 6 X'. Рассмотрим также проектор (} = 1-Р и двойственный ему оператор Напомним, что через 17° обозначаем аннулятор подпространства V С X, т. е. подпространство линейных функционалов из X', равных нулю на ЕЛ

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

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

(а) V ^ е АГ(Т)°, х£Х (Вх, В*гу) = 0;

(б) Ууз е хеХ {Тх, Тчф) = 0;

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

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

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

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

В п. 5.3.6 описывается алгоритм построения регуляризованного воспроизводящего отображения в случае сНт./У(Т) < оо. Он был предложен Д.С. Кротовым (1997) в магистерской диссертации и обобщен автором в [8].

Пусть теперь Х{, - гильбертовы пространства, Т< 6

и В; € - строго взаимно дополнительные опе-

раторы, 7« € Хх) - регуляризованные воспроизводящие ото-

бражения относительно (Х^, || ■ ||г(, || ■ ||вД г = 1,..., п.

Теорема 5.3.7. Отображение 7 = 71 ® • • ■ ® 7п является воспроизводящим отображением пространства X — Х\ ® ... ® Хп относительно нормы, порожденной оператором Т = (Т\ ф В\) ® ... ®

(Г„ ф Вп), и относительно полунормы, порожденной оператором

Данная теорема дает способ построения воспроизводящего ядра в тензорном произведении пространств относительно полунормы, порожденной оператором Т. П. 5.3.8 содержит примеры регуляризо-ванных воспроизводящих ядер для линейного (m = 1) и кубического (т = 2) сплайнов.

В приложении к диссертации приводится описание библиотеки сплайн-аппроксимации JSpline+ (библиотеку можно найти по адресу http://www.excelsior-usa.com/jspline), созданной под руководством и при непосредственном участии автора студентами НГУ A.B. Галковым, O.A. Лихачевым, А.Е. Никишкиной, Н.Ф. Фурсовой, а также аспирантом ИВМиМГ СО РАН Д.В. Петраковым.

В настоящий момент в библиотеке реализовано большое количество алгоритмов линейной алгебры, в том числе модифицированное QjR-разложение в трех вариантах, QiZ-разложение с накоплением, решение системы линейных уравнений с блочной матрицей вида (12) путем сведения ее к системе (13), решение системы (12) с произвольной правой частью. В разделе сплайн-аппроксимации реализованы алгоритмы одномерной полиномиальной сплайн-аппроксимации сплайнами четной и нечетной степеней. Для этих сплайнов имеются режимы интерполяции, сглаживания, выбора параметра сглаживания по критерию невязки. Коэффициенты полиномиальных сплайнов могут храниться либо в виде полного полиномиального разложения по ячейкам сетки, либо в виде разложения по .B-сплайнам (в версии, выложенной на сайте, отсутствуют программы разложения по B-сплайнам). Реализованы сплайны Дюшона многих переменных, для которых также имеются режимы интерполяции, сглаживания, выбора параметра сглаживания по критерию невязки.

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

Основные результаты диссертации

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

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

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

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

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

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

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

Основные публикации по теме диссертации

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

[2] Роженко А.И. Разрывные £>т-сплайны и общие теоремы сходимости интерполяционных сплайнов. — Новосибирск, 1994. — (Препринт / РАН. Сиб. отд-ние. ВЦ; 1030).

[3] Rozhenko A.I. Mixed spline approximation // Bull, of the Novosibirsk Computing Center. Series: Num. Anal. — Novosibirsk: NCC Publisher, 1994. — № 5. — P. 67-86.

[4] Rozhenko A.I. Convergence of variational splines I // Bull, of the Novosibirsk Computing Center. Series: Num. Anal. — Novosibirsk: NCC Publisher, 1995. — № 6. — P. 69-82.

[5] Rozhenko A.I. On the convergence of abstract variational splines // East J. on Approx. — 1995. — Vol. 1, № 1. — P. 25-36.

[6] Rozhenko A.I. On optimal choice of spline-smoothing parameter // Bull, of the Novosibirsk Computing Center. Series: Num. Anal. — Novosibirsk: NCC Publisher, 1996. — № 7. — P. 79-86.

[7] Роженко А.И. О новой модификации алгоритма численного построения абстрактного сплайна // Третий сибирский конгресс по прикладной и индустриальной математике, посвященный памяти C.JI. Соболева (1908-1989). Тезисы докл., ч. II. — Новосибирск: Изд-во Института математики СО РАН, 1998. — С. 24.

[8] Роженко А.И. Сплайн-аппроксимация в тензорном произведении пространств // Сиб. журн. вычисл. математики / РАН. Сиб. отд-ние. — Новосибирск, 1998. — Т. 1, № 4. — С. 373-390.

[9] Роженко А.И. Абстрактная теория сплайнов. — Новосибирск: Изд. центр НГУ, 1999.

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

[11] Rozhenko A.I. On fitting inaccurate data with splines // Proc. of International Conference on Computational Mathematics ICCM-2002: Part I / Eds. G.A. Mikhailov, V.P. Il'in, Yu.M. Laevsky. — Novosibirsk, 2002. — P. 159-164.

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

РОЖЕНКО Александр Иосифович

ТЕОРИЯ И АЛГОРИТМЫ ВАРИАЦИОННОЙ СПЛАЙН-АППРОКСИМАЦИИ

01.01.07 — вычислительная математика

Автореферат диссертации на соискание ученой степени доктора физико-математических наук

Лицензия № 020888 от 15.05.1995 г. Подписано в печать 12.01.2004 г.

Формат бумаги 60 х 84'/хв Объем 2,5п. л., 2,2 уч.-изд. л. Тираж 90 эхз. Заказ № 19

Издательский центр ИВТ СО РАН Новосибирск-90, пр. Лаврентьева, 6

РНБ Русский фонд

2006-4 32028

О 1 ФРВ 2004

Введение.

Глава 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]. Библиотека разрабатывалась под научным руководством и при непосредственном участии автора студентами НГУ А.В. Галковым, О.А. Лихачевым, А.Е. Никишкиной, Н.Ф. Фурсовой, а также аспирантом ИВМиМГ СО РАН Д.В. Петраковым.

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.