Исследование свойств обобщенной конечно-элементной аппроксимации тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

; Гь ОД

1 2 к;;;! №

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи УДК 519.6

ЛЕБЕДИНСКАЯ Наталия Александровна

ИССЛЕДОВАНИЕ СВОЙСТВ ОБОБЩЕННОЙ КОНЕЧНО-ЭЛЕМЕНТНОЙ АППР ОКСИМАЦИИ

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

АВТОРЕФЕРАТ

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

Санкт-Петербург 2000

Работа выполнена в Санкт-Петербургском государственном университете.

Научный руководитель — доктор физико-математических наук,

профессор Демьянович Юрий Казимирович.

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

доктор физико-математических наук, профессор Репин Сергей Игоревич;

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

Ведущая организация — Московский государственный университет имени М. В. Ломоносова

Защита состоится " $ » ш-онл 2000 г. в 13 час. 00 мин. на заседании диссертационного совета Л 063.57.30 по защите диссертаций на соискание ученой степени доктора физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904, Санкт-Петербург, Петродворец, Библиотечная площадь, д. 2. Математика-механический факультет. Ауд. 4526.

С диссертацией можно познакомиться в научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская набережная, 7/9.

Автореферат разослан 2000 г.

Ученый секретарь

диссертационного совета Д 063. 57.30 Ю. А. Сушков

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

Актуальность темы.

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

В мировой литературе имеется большое количество работ по конечно-элементной аппроксимации. Отметим в этой связи работы С.Г. Мих-лина, Ф. Сиарле, Г. Стрэнга, Дж. Фикса. К таким аппроксимациям примыкают аппроксимации сплайнами. В 1952 г. В.С.Рябенький впервые построил сплайны с локальным интерполяционным базисом. Дж.Гозл (1968 г.) и С.Г.Михлин (1971 г.) получили базисные функции из аппроксимационных соотношений. Ю.К.Демьянович модифицировал эти соотношения и получил так называемые обобщенные минимальные сплайны.

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

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

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

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

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

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

Апробация работы. Результаты диссертации докладывались на Городском семинаре "Всплески и их приложения" и на заседаниях кафедры Вычислительной математики СПбГУ. Работа была поддержана грантом РФФИ, а также грантом для молодых ученых правительства Санкт-Петербурга (1996-1998).

Публикации. По теме диссертации автором опубликовано б работ [1-6]. Пакеты программ, переданные в ГФАП, опубликованы в

[1], И-

Объем и структура работы. Диссертация состоит из введения, трех глав, двух приложений и списка литературы. Объем работы 142 страницы. Библиография содержит 31 наименование. Приложение I

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

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

Во введении содержится общая характеристика работы, краткий исторический обзор, а также краткое содержание параграфов диссертации.

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

На вещественной оси Я1 рассмотрим сетку {Хк}, — кк, к £ 2, И

— вещественное положительное число. На отрезке [а, 6] введем сетку {жь}, = аЛ-кК, к = 0,... , п—1. Обе сетки обозначаются одинаково, так как в дальнейшем из контекста всегда будет ясно, какая из них имеется в виду. Пусть 3 — множество индексов, 3 — 2, если сетка бесконечная, = {—га,... , п — 1}, если сетка конечная.

Пусть ц = (//о, /м, • • ■ , /<ш) — вектор с вещественными компонентами, причем цц = 1. Введем вектор и — ,г/т), щ = 1, связанный с /1 соотношением

* (

(я «=1,.-.,«. (1)

1=0 ^ ''

Рассмотрим функционалы

(2)

а=0

Обобщенными минимальными сплайнами будем называть линейные комбинации сдвигов функции ш^Ь/к) на ]Н {] £ 2), где

— образующая функция, удовлетворяющая следующим аппроксима-

ционным соотношениям: А

Л (/}'1)>Ы^оо ~ -О = пМ* ^

Т

г: € (ж*,з:н1)> ¿ = 0,...,/«, яирро;^) = [0,т + 1],

где т — степень сплайнов, число к £ 2, если сетка бесконечная, и к — 0,... ,п — 1 в случае конечной сетки. Задавая вектор /(, можно получать сплайны с различными свойствами аппроксимации и гладкости. Так, например, могут быть получены Л-сплайны и минимальные сплайны с локальным интерполяционным базисом.

Для функции и(х) из класса Ст+1 или IVрассмотрим аппроксимацию вида

ад = (4>

Формулы (3) означают, что аппроксимация (4) точна на пространстве 7гт многочленов степени не выше ш.

Теорема 1 Если и(х) — функция

класса , к £ тпо

для аппроксимации й(х) вида (4) справедлива оценка

11^ - < С^Л^'-'И«^)(5)

где — положительная константа, которая не зависит от

функции и{х) и от ¡г, г — целое, г = 0,... ,т. Значение константы СЭД, дается формулой

с<"1 = й(г)| +(^Ы- (6)

где

т а=0

Доказательство теоремы 1 основывается на использовании формулы Тейлора с остатком в интегральной форме и аппроксимацион-ных соотношений (3).

Теорема 2 Если и(х) — функция класса р > 1, то для

аппроксимации гг(х) вида (4) справедливы оценки 1), 2): 1) ?>р>1

Цй« - ««<%(*) < СЙ^А^ИИи^ЧИ^,),

2) <7 = оо, р = 1

Если и(х) — функция класса (а, Ь), то для аппроксимации й(х) вида (4) справедливы оценки 3), 4):

3) р > <7 > 1

||Й(,) - «(!)1км < сй^1"'!!»^4«^.

4) q — 1, р = оо

1|й(0 - «(01и1[а.ч < с2!,-,,)Лт+1-'11«(т+1)1|2-м-

Здесь — положительные константы, которые не за-

висят от функции и € и от К. Числа р и д связаны соотно-

шением 1/д + 1/р — 1, г — целое, г = 0,... , т. Значения констант ^(/<\д)> ^(/¡о даются формулами

(2) _ (та + 1) "

—_ _ _

т! |Д (т — {)!) ^(т - г) + 1) (?(т - ») + 2)

т ..г+1 ,т-г ч д

(8)

1 Г т~Т ' 1

СМ = т! Е ■+Л1- (—тут)-

При доказательстве теоремы 2 используются неравенства Гель-дера для сумм и интегралов, неравенство Иенсена и теоремы вложения Соболева.

Используя формулы (8) и (9), были вычислены приближенные значения указанных констант. Для увеличения точности вычисления интегралов находились корни многочленов (5„¡(у), 1 < т < 7.

Погрешность вычисления интегралов, фигурирующих в (8), (9), составила величину порядка Ю-12. Определенный интерес представляют те значения вектора ц, при которых константы аппроксимации минимальны. В приложении I приведены таблицы наименьших приближенных значений констант С^, С^. ^ и параметры при которых соответствующие константы минимальны (параметры д, г фиксировались), а также графики зависимости некоторых констант от параметра ц.

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

Для функций, заданных на гг-мерном (п > 1) гладком многообразии, существует способ построения конечно-элементных аппроксимаций, который позволяет использовать ряд хорошо известных плоских аппроксимаций (Куранта, Зламала, Аргириса).

Для построения аппроксимации на многообразии необходимо иметь

1) представление многообразия с помощью атласа из континуального числа карт, взаимно-однозначно соответствующих точкам многообразия,

2) симплициальное подразделение многообразия,

3) подходящее семейство аппроксимаций в евклидовом пространстве.

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

ствий номеров симплексов и номеров вершин.

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

Пусть М. — п-мерное дифференцируемое многообразие, заданное атласом А = {(х<> Щ) I С € где (хс, и с) — карта с носителем {/<; и с: картирующим отображением Х( '• Е^, — открытый шар в

евклидовом пространстве Я", а 2 — некоторое множество индексов.

Очевидно, многообразие М. — метризуемо. Пусть р((,п, <Ы — не-хсоторая метрика на ЛЛ.

Предположим, что атлас А удовлетворяет следующим условиям:

(1) 2 = М, (У) С е и(, (ш) хсС = о.

(IV) точка 0 является центром шара Е(.

Для иллюстрации в качестве многообразия М возьмем гладкую поверхность, гладко вложенную в Я"+1, в точке ( € М проведем к ней касательную плоскость Ь^ и выберем начало координат в Ь^ в точке касания. Полученное в Ь^ арифметическое пространство возьмем в качестве упомянутого выше пространства Я", а за отображение хс примем ортогональное проектирование на Ьг\ далее построим в Ь( столь малый шар Е^ С с центром в точке касания, чтобы ближайшая к Ьс часть Ьтг поверхности Л4 проектировалась биективно на Нетрудно проверить, что семейство {(хо^с) I С С 2} состоит из попарно согласованных карт, объединение носителей которых совпадает с М, и значит А = {(д'о I С € 2} является атласом для М.. Справедливость условий (1)-(1у) очевидна.

Пусть точки и £1 содержатся в Ь7(. Отрезок прямой (без концевых точек), соединяющий их образы '= хс£о и '= хсб в шаре обозначим (£¿,£1) и будем называть открытым отрезком.

Рассмотрим множество ¿(£о|£х) тех точек С, Для которых отрезок сожержит точку 0, т.е.

= (Ю)

Определение. Множество будем называть абстракт-

ным А-отрезком (соединяющим точки и (1 на М). Если абстрактный А-отрезок является простой незамкнутой кривой, то его будем называть отрезком псевдопрямой, порожденной атласом А.

В §2 главы II выясняются достаточные условия того, чтобы абстрактные Л-отрезки были простыми незамкнутыми кривыми, соединяющими близкие точки компактного куска гладкой выпуклой поверхности, заданной континуальным атласом из семейства атласов специального вида. Показано, что для упомянутого куска поверхности всегда можно указать столь малое число е > 0, при котором для е-близких точек абстрактный А-отрезок оказывается простой незамкнутой кривой. Получены также итерационные методы приближенного отыскания Л-отрезков с априори заданной точностью, сходящиеся со скоростью геометрической прогрессии. Очевидно, что любое гладкое многообразие можно считать локально гладко вложенным в евклидово пространство так, что результаты вложений — компактные выпуклые куски гладких поверхностей. Тогда имеет место следующая

Теорема 3 Пусть п-мерное компактное многообразие ЛЛ, задано я +1 раз дифференцируемым атласом А = {(хо I С € -2}, удовлетворяющим условиям (1)-(%м), и пусть карта (хо з раз дифференцируема по параметру Тогда можно построить такой атлас А' и найти столь малое £ > 0, при котором для е-близких точек абстрактный А'-отрезок оказывается простой незамкнутой 5 раз дифференцируемой кривой .

Третий параграф данной главы посвящен реализации аппроксимации второго порядка на сфере и на сфере с вырезом ([1], [2]). При написании пакетов программ была поставлена цель получить достаточно мелкую триангуляцию указанных поверхностей. Триангуляция поверхности задается двумя трехстолбцовыми таблицами, первая из которых в г-й строке содержит номера вершин, принадлежащих г-му треугольнику, а во второй в ^'-й строке содержатся координаты ¿-й вершины. При измельчении триангуляции каждый треугольник подразделяется на четыре новых.

Для полумения достаточно мелкого подразделения был предложен следующий подход: сначала задается исходная крупная триангуляция и информация об этой триангуляции хранится в отдельном файле. Каждый треугольник крупной триангуляции измельчается согласно существующему алгоритму заданное число раз, и информация о подразбиениях каждого такого треугольника хранится в других отдельных файлах. Имена этих файлов генерируются автоматически и содержат два параметра — номер крупного треугольника исходной триангуляции и число его подразбиений. Длина каждого файла такова, что он может быть целиком считан в оперативную память. В то время, когда создавался данный пакет программ, ограничение на память было следующее — 64 Кбайт. Это соответствует хранению информации о 45 треугольников триангуляции. Такой подход позволил увеличить число треугольников в триангуляции в количество раз, пропорциональное числу треугольников исходной крупной триангуляции.

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

Третья глава посвящена выяснению возможной степени распараллеливания МКЭ. В качестве объекта исследования была взята первая краевая задача для обыкновенного дифференциального уравнения второго порядка:

-(Ки')'+С1и = Р и( 0) = «(1) = 0.

Здесь (¿(х),Р(х) £ И'!1"*1, К(х) £ И^1"1"2, — натуральное число, и выполнены неравенства К(х) > > 0, <2(я) > 0. Процесс решения .этой задачи отражает характерные особенности, которые встречаются при распараллеливании и при однопроцессорном подходе.

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

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

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

Теорема 4 Для любой функции и £ И7™+1(0,1) существуют минимальные сплайны й степени т, для которых

где С не зависит от и(х), й{х); здесь к — шаг сетки на [0,1], Л = 1 /п.

В частности, для т = 1, т = 2, т = 3 в случае /3 — 1 мы вычисляем константу С явно:

Си 1.5 , при т = 1;

Си 1.2 , при т = 2 (1 = 2,8 = 1);

С и 0.75 , при ш = 3 (/ — 2,5= 2).

В предположении, что интегралы, входящие в элементы матрицы МКЭ и правой части, вычисляются по составной квадратурной формуле Гаусса (сI — число узлов в простой квадратурной формуле Гаусса) даются оценки погрешности квадратурных формул с использованием норм производных минимальных сплайнов.

Численное решение исходной задачи состоит из двух .этапов: 1) вычисления элементов матрицы и столбца правых частей, 2) решения системы линейных уравнений с ленточной матрицей. На первом этапе вычисляется ряд интегралов. Число операций на однопроцессорном компьютере получается умножением числа интегралов в матрице МКЭ на число операций, необходимое для вычисления самого трудоемкого интеграла. Для нараиельной вычислительной системы в этом случае число параллельных операций (тактов) определяется числом операций самого трудоемкого интеграла. В п.2) для однопроцессорного случая система решается с использованием LDLT-разложения, а для параллельного — с помощью ¿{/-разложения.

Общее количество тактов при решении задачи на указанных типах компьютеров определим как функцию ряда переменных: требуемой точности решения задачи б, параметров сплайнов тп, I и коэффициентов задачи К(х), Q(x), F(x). Учитывая равенство оценок погрешности аппроксимации н погрешности квадратурных формул, можно выразить все параметры через один — степень сплайна. В результате получим функцию одной переменной. Для рассматриваемой задачи были получены упомянутые функции, выражающие время, затрачиваемое на ее решение на однопроцессорном и параллельном компьютерах. При упомянутых выше предположениях относительно вычислительных систем и значениях параметров

f = 10-R, С = 10, в, = 8, d = 4, I = j, р = q = 1,

К{Х) = (dbp = php F{X) = (2^ выяснилось, что время решения задачи на параллельной вычислительной системе на шесть порядков меньше, чем на однопроцессорном компьютере.

Кроме теоретических оценок трудоемкости, была осуществлена реализация упомянутого метода решения задачи (11) на компьютере, занимающем промежуточное положение между однопроцессорной и параллельной вычислительной системой, а именно, на векторной машине Convex Института высокопроизводительных вычислений

и баз данных в Санкт-Петербурге (параллельно выполняется 128 одноименных операций). Эта реализация предполагает решение задачи с произвольной сеткой узлов, причем константы вводятся как макроопределения, а коэффициенты уравнения как процедуры, так что тс и другие могут быть легко изменены. Погрешность решения рассматриваемой краевой задачи для тестового примера составила величину порядка Ю-11. Текст и описание процедур соответствующей программы содержатся в приложении II. В диссертации также приведены результаты расчетов для различных уровней оптимизации, которые показывают, что использование векторных и параллельных машин позволяет реально увеличить скорость решения задачи. Третий параграф главы III посвящен решению периодической задачи для уравнения второго порядка с использованием обобщенных минимальных сплайнов; здесь используется теоретический материал первой главы.

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

[1] Демьянович Ю.К., Смирнова H.A. Пакет программ "Локальная аппроксимация функций, заданных на сфере и на сфере с вырезом" // Гос. фонд алг. и прогр. России. Инв. N 50960000043. М., 1996. 35 с.

[2] Демьянович Ю.К., Смирнова H.A. Пакет программ "Локальная аппроксимация функций, заданных на плоскости" // Гос. фонд алг. и прогр. России. Инв. N 50960000044. М., 1996. 51 с.

[3] Лебединская H.A. О распараллеливании при численном решении задачи Штурма-.Лиувилля. С.-Петерб., 1998.42 с. Дсп. в ВИНИТИ. 28.01.98, № 214В98.

[4] Демьянович Ю.К., Лебединская H.A. О существовании и единствен- ности в малом отрезков псевдопрямых // Вести. С.-Петерб. ун-та.-Сер.1. 1998. Вып. 3(N 15). С.12-14.

[5] Лебединская H.A. О распараллеливании при численном решении одномерной краевой задачи // Вестник молодых ученых. Серия: прикладная математика и механика. 1999, N 1.

[6] Лебединская H.A. Теоремы аппроксимации различными минимальными сплайнами. С.-Петерб., 2000. 35 с. Деп. в ВИНИТИ. 28.01.00, N 169 - В00.

ЛР№ 040815 от 22.05.97.

Подписано к печати 17.04.2000 г. Формат бумаги 60X90 1/16. Бумага офсетная. Печать ризографпческая. Объем 1 пл. Тираж 100 экз. Заказ 1312. Отпечатано в отделе оперативной полиграфии НИИХ СПбГУ с оригинал-макета заказчика. 198904, Санкт-Петербург, Старый Петергоф, Университетский пр. 2.

Введение.

Глава I. Теоремы аппроксимации обобщенными минимальными сплайнами

§1. Об образующих минимальных сплайнах.

1. Образующие минимальные сплайны

2. Определяющие функционалы и аппроксимация.

3. О вложенности пространств минимальных сплайнов

§2. Теоремы аппроксимации

1. Об аппроксимации обобщенными минимальными сплайнами

2. Оценка приближения в равномерной норме.

3. Оценка в норме пространства

4. Случай пространства Ьд, д >

5. Вычисление констант аппроксимации

Глава II. Конечно-элементная аппроксимация функций на многообразии

§1. Построение аппроксимаций на многообразии

1. Аппроксимационные соотношения.

2. Построение аппроксимаций на многообразии с помощью семейства плоских аппроксимаций

3. Общая схема.

§2. О существовании и единственности в малом отрезков псевдопрямых

1. Построение специального атласа для поверхности

2. О сферических изображениях

3. О сегментах выпуклых областей

4. Структура абстрактного А-отрезка для близких точек выпуклой поверхности

5. Абстрактный А-отрезок для близких точек многообразия

§3. Аппроксимация функций на сфере и на сфере с вырезом

1. О построении триангуляции

2. Построение аппроксимации типа Куранта на сфере и на сфере с вырезом.

3. Построение аппроксимации типа Зламала на сфере

4. Численная аппроксимация и пакеты программ

Глава III. О численном решении некоторых краевых задач

§1. Постановка задачи и описание приближенного метода.

1. Постановка задачи.

2. МКЭ для решения 1-й краевой задачи с граничными минимальными сплайнами в качестве базисных функций

§2. О распараллеливании МКЭ для 1-й краевой задачи

1. Об оценке погрешности.

2. Оценка трудоемкости решения

2.1. Однопроцессорный компьютер.

2.2. Параллельная вычислительная система

3. О реализации вычислений на векторных машинах

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

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

В основе метода конечных элементов лежит понятие конечно-элементной аппроксимации. Основными чертами конечно-элементной аппроксимации являются:

1) триангуляция исходной области (или более общее клеточное подразделение),

2) кусочно-многочленный характер аппроксимации,

3) локальный интерполяционный базис.

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

В мировой литературе имеется большое количество работ по конечно-элементной аппроксимации. Отметим в этой связи работы С.Г. Михлина, Ф. Сиарле, Г. Стрэнга, Дж. Фикса. К упомянутым аппроксимациям примыкают аппроксимации сплайнами. В 1952 г. В.С.Рябенький впервые построил сплайны с локальным интерполяционным базисом. Дж.Гоэл (1968 г.) и С.Г.Михлин (1971 г.) получили базисные функции из аппроксимационных соотношений. Ю.К.Демьянович модифицировал эти соотношения и получил так называемые обобщенные минимальные сплайны.

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

Целью данной диссертационной работы является:

I) исследование вопросов теории аппроксимации обобщенными минимальными сплайнами: получение эффективных констант аппроксимации в нормах различных пространств, вычисление этих констант, сравнение их для различных пространств сплайнов;

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

III) использование параллельных вычислений при решении задач математической физики: получение оценок трудоемкости сплайно-вой аппроксимации при численном решении краевых задач методом конечных элементов без распараллеливания и с распараллеливанием; реализация вычислений на векторных вычислителях.

Перейдем к обзору содержания диссертации по главам. Глава I посвящена аппроксимации обобщенными минимальными сплайнами. Сплайновые аппроксимации являются одним из наиболее распространенных методов решения задач аппроксимации и приближения. Классическим примером сплайнов являются Б-сплайны, которые обладают свойством оптимальности по n-поперечнику и неотрицательностью локального базиса. Однако Б-сплайны не являются интерполяционным базисом. Для решения интерполяционных задач Эрмита известны эрмитовы сплайны, но они не всегда удобны, поскольку помимо значений интерполируемой функции требуются также значения ее производных в узлах. При решении интерполяционных задач, связанных с постоянным получением новых данных, удобнее оказываются минимальные интерполяционные сплайны. Последние обладают локальным интерполяционным базисом и упомянутой выше оптимальностью. К минимальным сплайнам с локальным интерполяционным базисом относятся ломаная Эйлера, интерполяции Дженкинса, сплайны B.C. Рябенького; в задаче Эрмита — это эрмитовы сплайны.

Возникла ситуация, когда имеется много различных сплайнов, обладающих одинаковыми аппроксимативными свойствами и похожими по простоте структурами базисных функций, но с весьма различными свойствами устойчивости, с различными константами в оценках аппроксимации и разной трудоемкостью их использования. Ввиду неоднородности способов их описания затруднительно отдать предпочтение тому или иному виду сплайнов. Для упрощения ситуации оказалось удобно исходить из аппроксимационных соотношений (Дж.Гоэл, С.Г.Михлин, Ю.К.Демьянович). Идея состоит в том, чтобы при заданном порядке аппроксимации и гладкости минимизировать кратность накрытия носителями базисных функций, и из этих условий отыскивать сами базисные функции. Первоначально таким способом удалось получить новые сплайны с интерполяционным локальным базисом для задач Лагранжа и Эрмита (см.[6], [10], [24]), а в последнее время — путем модификации аппроксимационных соотношений удалось построить широкий набор сплайнов (так называемых обобщенных минимальных сплайнов), который включает также и В-сплайны (см.[8], [9], [11], [13]).

Первый параграф главы I содержит основы теории обобщенных минимальных сплайнов на равномерной сетке (см. [8]). Здесь рассматриваются обобщенные минимальные сплайны на равномерной сетке, которые получаются линейной комбинацией сдвигов одной функции, названной приведенным образующим сплайном. В зависимости от типа образующего сплайна получаются те или иные пространства минимальных сплайнов. В первом разделе §1 дается определение приведенного образующего сплайна, исследуются различные виды аппроксимационных соотношений, а также устанавливается представление приведенных образующих сплайнов через стандартные сплайны. Во втором разделе вводится понятие определяющих функционалов и рассматривается аппроксимация функций с помощью элементов пространства, порожденного приведенными образующими сплайнами. Третий раздел посвящен вложенности пространств минимальных сплайнов при измельчении сетки.

В §2 главы I доказываются теоремы аппроксимации обобщенными минимальными сплайнами на равномерной сетке в норме пространств С и Ья. При доказательстве теорем используются аппрок-симационные соотношения для минимальных сплайнов, неравенства

Гельдера, неравенство Иенсена, а также теоремы вложения Соболева. Второй параграф состоит из пяти разделов. Первый раздел посвящен аппроксимации обобщенными минимальными сплайнами. Со второго по четвертый раздел доказываются теоремы аппроксимации. Во втором разделе дается оценка приближения в норме пространства С. Здесь представлены два подхода. Первый из них позволяет получить более простые, но и более грубые оценки (теорема 1), второй подход сложнее с вычислительной точки зрения, но зато позволяет получить более точные оценки (теорема 2). В третьем и четвертом разделах (с использованием второго подхода) получены оценки в норме пространств ¿2 (теорема 3) и Ьд (теорема 4) соответственно. Пятый раздел раздел параграфа содержит примеры вычисления констант и их сравнение для различных пространств сплайнов. В приложении I имеются таблицы некоторых констант и приведены графики их зависимостей от типа сплайнов.

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

1) представление многообразия с помощью атласа из континуального числа карт, взаимно-однозначно соответствующих точкам многообразия,

2) симплициальное подразделение многообразия,

3) подходящее семейство аппроксимаций в евклидовом пространстве.

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

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

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

В связи с этим, в §2 рассматриваются свойства абстрактных А-отрезков, обобщающих понятие отрезка геодезической на случай произвольного дифференцируемого многообразия. Абстрактный А-отрезок не всегда гомеоморфен отрезку прямой, однако в тех случаях, когда такой гомеоморфизм имеется, будем называть его отрезком псевдопрямой. В §2 выясняются достаточные условия существования и единственности отрезков псевдопрямых, соединяющих близкие точки компактного куска гладкой выпуклой поверхности, заданной континуальным атласом из семейства атласов специального вида. Здесь показано, что для упомянутого куска поверхности всегда можно указать столь малое число е > 0, при котором для е-близких точек абстрактный А-отрезок оказывается простой незамкнутой кривой; кроме того дан алгоритм построения точек этого отрезка с априори заданной точностью. Очевидно, что любое гладкое многообразие можно считать локально гладко вложенным в евклидово пространство Дп+1 так, что результаты вложений — компактные выпуклые куски гладких поверхностей. Тем самым из полученного в этом параграфе результата следует, что для компактного гладкого многообразия, удовлетворяющего достаточно общим условиям, может быть построен атлас А', для которого существует столь малое е > 0, при котором для е-близких точек абстрактный А'-отрезок оказывается простой незамкнутой кривой.

Заключение

Данная работа является вкладом в изучение обобщенной конечно-элементной аппроксимации. Основными результатами работы являются:

I. Исследование вопросов теории аппроксимации обобщенными минимальными сплайнами:

1) получены оценки приближения функций обобщенными минимальными сплайнами в норме пространств С и Ьч]

2) вычислены константы аппроксимации и произведено сравнение этих констант для различных классов сплайнов.

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

1) исследованы свойства абстрактных А-отрезков, обобщающих понятие отрезка геодезической на случай произвольного дифференцируемого многообразия;

2) получены итерационные методы приближенного отыскания А-отрезков и даны оценки скорости сходимости;

3) установлено, что существуют атласы, для которых абстрактные Л-отрезки представляют собой простые незамкнутые кривые;

4) разработан алгоритм глубокого измельчения триангуляции поверхности;

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

III. Использование параллельных вычислений при решении задач математической физики:

1) получена оценка трудоемкости сплайновой аппроксимации при численном решении 1-ой краевой задачи методом конечных элементов без распараллеливания и с распараллеливанием;

2) осуществлена реализация упомянутого метода решения модельной задачи на векторном вычислителе Convex.

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

Автор выражает глубокую признательность Демьяновичу Ю.К. за научное руководство и за постоянную помощь и поддержку при выполнении данной работы.

1. Беккенбах Э., Беллман Р. Неравенства. М., 1965. 276 с.

2. Бурова И.Г., Демьянович Ю.К. Гранично-минимальные сплайны и их применение. СПб., 1996. 88 с.

3. Воеводин В.В., Тыртышников Е.Е. Вычислительные процессы с теплицевыми матрицами. М., 1987. 294 с.

4. Воеводин В.В. Математические модели и методы в параллельных процессах. М., 1986. 296 с.

5. Демьянович Ю.К. Вычислительные методы для решения задач математической физики. Л.: Издательство ЛГУ. 1986. 72 с.

6. Демьянович Ю.К. Локальная аппроксимация на многообразии и минимальные сплайны. СПб., 1994. 356 с.

7. Демьянович Ю.К. Локальная аппроксимация на многообразиях. СПб. 1991. 80 с.

8. Демьянович Ю.К. О классификации пространств минимальных сплайнов. Деп. в ВИНИТИ 2486-В97 от 24.07.1997. 25 с.

9. Демьянович Ю.К. О представлениях и о свойствах некоторых минимальных сплайнов, Деп. в ВИНИТИ 2487-В97 от 24.07.1997. 22 с.

10. Демьянович Ю.К. Об аппроксимации пространствами локальных функций // Вестн. Ленингр. ун-та. 1977. N.1 С.35-41.

11. Демьянович Ю.К. Об образующих минимальных сплайнах и их характеристических многочленах. Деп. в ВИНИТИ 2485-В97 от 24.07.1997. 32 с.

12. Демьянович Ю.К., Михлин С.Г. О сеточной аппроксимации функций соболевских пространств. Численные методы и функциональный анализ // Зап. научн. сем. ЛОМИ. 1973. Т.35 С.6-11.

13. Demjanovich Y.K. Some Properties of Minimal Splines // Math. Nachr. 1996. Vol. 177. P. 57-79.

14. Крутиков М.П. Оптимизация программ под архитектуру CONVEX С СПб., 1996. 29 с.

15. Михлин С.Г. Вариационно-сеточная аппроксимация//Зап. науч. семинаров ЛОМИ АН СССР. 1974. Т.48. с.32-188.

16. Михлин С.Г. Некоторые вопросы теории погрешностей. -Л.: Издательство Ленинградского университета. 1988. 333 с.

17. Норден А.П. Теория поверхностей. М., 1956. 260 с.

18. Постников М.М. Лекции по геометрии. Гладкие многообразия. М. 1987. 480 с.

19. Смирнов В.И. Курс высшей математики. Т.5, М., 1959. 655 с.

20. Сьярле Ф. Метод конечных элементов для эллиптических задач. М., 1980, 512 с.

21. Федоренко Р.П. Релаксационный метод решения разностных эллиптических уравнений // Журн. вычисл. матем. и матем. физики. 1961. Т.1. N о. С. 922-927.

22. Daubechies I. Ten lectures on wavelets. Philadelphia, 1992. 357 p.

23. Golub G.H. and C.F. Van Loan. Matrix Computations. London, 1989. 642 p.

24. Michlin S.G. Approximation auf dem kubischen Gitter. Berlin: Akademie-Verlag. 1976. 204 p.

25. Strang G., Fix G. Fourier Analysis of the finite element method in Ritz Galerlciii Theory // Stud. Appl. Math. 1969. Vol. 48. N.3 P. 265^273.

26. Демьянович Ю.К., Смирнова H.A. Пакет программ "Локальная аппроксимация функций, заданных на сфере и на сфере с вырезом" // Гос. фонд алг. и прогр. России. Инв. N 50960000043. М., 1996. 35 с.

27. Демьянович Ю.К., Смирнова H.A. Пакет программ "Локальная аппроксимация функций, заданных на плоскости" // Гос. фонд алг. и прогр. России. Инв. N 50960000044. М., 1996. 51 с.

28. Лебединская H.A. О распараллеливании при численном решении задачи Штурма-Лиувилля. С.-Петерб., 1998. 42 с. Деп. в ВИНИТИ. 28.01.98, N 214В98.

29. Демьянович Ю.К., Лебединская H.A. О существовании и единствен- ности в малом отрезков псевдопрямых // Вестн. С.-Петерб. ун-та. Сер.1. 1998. Вып. 3(N 15). С.12-14.

30. Лебединская H.A. О распараллеливании при численном решении одномерной краевой задачи // Вестник молодых ученых. Серия: прикладная математика и механика. 1999, N 1.

31. Лебединская H.A. Теоремы аппроксимации различными минимальными сплайнами. С.-Петерб., 2000. 35 с. Деп. в ВИНИТИ. 28.01.00. N 169 В00.