Содержание к диссертации
Введение
Глава 1. О сходимости приближенных решений линейных некорректных задач на некоторых компактных множествах 12
1.1 Одномерные функции 15
1.1.1 Монотонные функции 15
1.1.2 Выпуклые функции 19
1.1.3 Функции с известными константами Липшица 20
1.2 Многомерные функции 21
1.2.1. Функции выпуклые или вогнутые вдоль осей координат . 21
1.2.2 Выпуклые функции 26
Глава 2. Общая схема нахождения погрепіности решения линейных некорректных задач на некоторых компактных множествах 27
2.1 Конечномерная аппроксимация 27
2.2 Априорная оценка погрешности решения 30
2.3 Метод отсечения выпуклых многогранников 34
2.4 Метод расширяющихся компактов и обратная задача катодо-люминесцентной микротомографии 41
2.5 Одномерные функции 47
2.5.1 Монотонные функции 47
2.5-2 Выпуклые функции 48
2.5.3 Функции с известными константами Липшица 53
2.6 Многомерные функции 55
2.6.1. Функции выпуклые или вогнутые вдоль осей координат . 55
2.6.2 Выпуклые функции 66
Глава 3. Примеры решения линейных некорректных задач на некоторых компактных множествах 80
3.1 Задача Коши для уравнения Лапласа 80
3.1.1 Декартова система координат 81
3.1.2 Задача Коши в кольце 83
3.2 Первая обратная задача для уравнения теплопроводности . 84
3.3 Вторая обратная задача для уравнения теплопроводности . 91
3.4 Реконструкция симметричных профилей скорости в многоплоскостных измерительных модулях 93
3.5 Программный комплекс 96
Заключение 101
Список литературы 103
- Функции выпуклые или вогнутые вдоль осей координат
- Метод расширяющихся компактов и обратная задача катодо-люминесцентной микротомографии
- Функции выпуклые или вогнутые вдоль осей координат
- Реконструкция симметричных профилей скорости в многоплоскостных измерительных модулях
Введение к работе
Актуальность темы диссертации. Многие задачи современной физики являются обратными задачами, К сожалению, все реальные задачи зависят от погрешностей входных данных. Более ста лет назад считалось, что только задачи с решениями, устойчивыми по отношению к возмущениям входных данных, имеют физический смысл. Все же остальные задачи— просто математические абстракции. Именно поэтому для различия "реальных" и "искусственных" задач Ж, Адамар ввел понятие корректной (корректно поставленной) задачи как задачи, решение которой существует, единственно и устойчиво к ошибкам входных данных [1]. Задача, не удовлетворяющая хотя бы одному из этих трех условий, называется некорректной.
В дальнейшем было показано, что некорректные задачи не только существуют, но и составляют значительную часть всех обратных задач. Типичным примером некорректной задачи является линейное операторное уравнение первого рода с вполне непрерывным оператором. В этом случае могут нарушаться все три условия корректности.
Академиком А. Н. Тихоновым в 60-х годах прошлого века была заложена теория решения некорректных задач, основанная на понятии регуляризи-рующего алгоритма [2,3] как способа приближенного решения некорректной задачи. После основополагающих работ А. Н. Тихонова [2-7], М. М, Лаврентьева [8,9] и В, К. Иванова [10-13] теория некорректных задач была развита многими учеными в применении к разным областям науки и техники. Некоторые результаты работы отечественных и зарубежных ученых представлены в [14-41].
Некорректные задачи по своей сути являются недоопределенными задачами. Поэтому информация о структуре решения, естественных ограничениях на его поведение, применяющаяся при решении корректных задач, становится крайне важной при решении некорректных задач. Если же такой
информации крайне мало, то для решения задачи регуляризирующий алгоритм не может быть построен.
Рассмотрим линейную некорректную задачу, записанную в виде операторного уравнения
Az = щ z Z.uGU, (В1)
где Z, U — линейные нормированные пространства, а А ; Z —> U — линейный непрерывный оператор. Вместо точных оператора А и правой части й уравнения (В1) имеются приближенные оператор А^ и правая часть щ такие, что ||Ah — А\\ ^ /г, \\щ — й\\ ^8,7]= (/і, 5). По входным данным {А^щ^т)} необходимо построить регуляризирующий алгоритм Я(А/1>щ^т})) т. е, указать правило нахождения приближенного решения %ц = ^А^щ^т}) такое, что — г\\ —* 0 при г] —* 0, где z — точное решение уравнения (В1).
При практическом решении задач интересно не только приближенное решение zVl построенное с помощью регуляризирующего алгоритма, но и оценка его близости к точному решению. Приведем некоторые результаты, полученные В, А. Винокуровым в работах [42,43]. Для простоты считаем, что оператор в (В1) известен точно, т, е. А& = А, Точность приближенного решения z$ = Н(щ}5) задачи (В1) рассматриваем как некоторую функцию погрешности 6:
\\zs-z\\^K
где К не зависит от <5, а функция tp(8yz) определяет скорость сходимости z$ к z. Следует различать точечные и равномерные оценки погрешностей решений. Неравенство (В2) записано для случая точечной оценки. В случая равномерной оценки функция <р((5, z) в неравенстве (В2) должна быть заменена функцией (р(&), зависящей от некоторого множества М точных решений z.
Пусть A : Z — (/ — линейный непрерывный инъективный onepaTopj Z — банахово пространство, a U — линейное нормированное пространство. Предположим, что обратный оператор Л-1 неограничен на области определения D(A~^). Считаем, что tp(S) — некоторая положительная функция такая,
что tf(S) —> О при 5 — 0. Пусть R — некоторой метод решения задачи. Тогда следующее равенство выполняется для всех элементов z кроме, быть может, множества первой категории в пространстве Z:
hm sup < —— > = со.
Здесь Д(Д, <5, z) = sup{||/?(-U5,^) — z\\ : щ Є С/, \\Az — и$\\ < 5} —точечная характеристика погрешности для метода R. Видно, что равномерная оценка погрешности может существовать только на множестве первой категории в Z.
Примером множества первой категории является компактное множество в банаховом пространстве. В этом случае можно использовать специальные регуляризирующие алгоритмы для нахождения приближенного решения [31.,38,44] и становится возможным построение равномерной погрешности решения.
Из написанного выше следует, что равномерная оценка погрешности решения существует только для задач, по своей сути являющимися корректными. Для некорректных задач в общем случае невозможно не только построить погрешность приближенного решения Zff} но и даже оценить скорость его сходимости к точному Z.
Целью диссертации являются;
1. создание новых математических методов для оценки апостериорной и априорной погрешностей решения на множествах специальной структуры (на множествах монотонных, выпуклых функций и функций с известными константами Липшица — для ограниченных функций с одномерными областями определения; на множествах функций, выпуклых на всей области определения, и функций, выпуклых или вогнутых вдоль всех прямых, параллельных осям координат, — для ограниченных функций с многомерными областями определения);
обобщение результатов, полученных ранее для одномерных выпуклых функций, на многомерные функции, выпуклые на всем множестве определения или вдоль осей координат;
создание программного комплекса для нахождения приближенных решений одномерных и двумерных уравнений Фредгольма первого рода и для оценки погрешностей найденных решений на множествах функций, перечисленных ранее;
применение разработанных алгоритмов к задаче реконструкции симметричных профилей скорости в многоплоскостных измерительных модулях в акустике, к обратной задаче катодолюминесцентной микротомографии, к обратной задаче для уравнения теплопроводности, к задаче Коши для уравнения Лапласа.
Методика исследования базируется на основных положениях теории решения некорректных задач, функционального анализа, выпуклого анализа, математического программирования.
Научная новизна и практическая значимость. Равномерная сходимость приближенного решения к точному для множества монотонных функций впервые доказывается для счетного числа отрезков, не содержат щих концы области определения точного решения и его точек разрыва. Также впервые доказывается равномерная сходимость приближенных решений и строятся условия на сеточные значения для функций, выпуклых или вогнутых вдоль осей координат, а также для выпуклых функций на многомерных областях определения- Разработанные в работе алгоритмы оценивания погрешностей решения некорректных задач на компактных множествах могут быть использованы в широких областях (например* в томографии, геофизике, астрофизике, спектроскопии), так как рассматриваемые компактные множества очень часто встречаются при решении обратных задач. Функции, ограничивающие множества приближенных решений сверху и снизу, позволя-
ют гарантировано найти область, которой принадлежит точное решение, если оно существует. В связи с развитием вычислительной техники обобщение использованных ранее методов решения некорректных задач с одномерных на многомерные области определения позволяет численно решать многомерные задачи, решение которых ранее было технически невозможно.
Основные положения диссертации, выносимые на защиту, заключаются в следующем.
1. Предложен и реализован в виде комплекса программ алгоритм для реше
ния и оценки априорных погрешностей решения интегральных уравне
ний Фредгольма первого рода при условии, что точное решение является
ограниченной монотонной, выпуклой функцией или функцией с известными константами Липшица на отрезке [а, 6];
ограниченной функцией, выпуклой или вогнутой вдоль осей координат, или ограниченной выпуклой функцией на всей многомерной области определения,
2. Для рассматриваемых функций доказана равномерная сходимость
последовательности приближенных решений к точному решению на неко
торых подмножествах области определения решения при стремлении
погрешностей входных данных к нулю, В случае, если точное решение
является
монотонной ограниченной функцией на отрезке [а, Ь], то сходимость имеет место на произвольном множестве, являющемся конечным или счетным объединением замкнутых отрезков, не содержащих точек разрыва функции z(x)^ а также точек а и 6;
ограниченной функцией, заданной на открытом ограниченном множестве Q С Жп7 п > 2, и являющейся выпуклой или вогнутой вдоль осей координат (или выпуклой на всем множестве).
Предложен и обоснован алгоритм для нахождения неравенств, определяющих множество априорных ограничений на сеточные значения для двумерных выпуклых функций.
Предложенный алгоритм применен для нахождения решения и оценки погрешностей в задаче реконструкции симметричных профилей скорости в многоплоскостных измерительных модулях в акустике, в обратной задаче катодолюминесцентной микротомографии, в обратной задаче для уравнения теплопроводности ? в задаче Коши для уравнения Лапласа.
Апробация работы. Основные результаты работы докладывались на семинаре "Обратные задачи математической физики", проводящемся в НИВЦ МГУ под руководством профессоров А. Б. Бакушинского, А. В. Тихонравова и А. Г. Яголы, на конференциях "Обратные и некорректно поставленные задачи" (Москва, факультет ВМиК МГУ, 20-21 июня 2000 г., 26-28 июня 2001 г., 10-11 июня 2003 г.), "Ill-posed and non-classical problems of mathematical physics and analysis" (Узбекистан, Самарканд, 11-15 сентября 2000 г.), "Международная конференция студентов и аспирантов по фундаментальным наукам «Ломоносов-2001». Секция «Физика»" (Москва, физический факультет МГУ, 11 апреля 2001 г.), "Методы оптимизации и их приложения" (Иркутск, Байкал, 24 июня - 1 июля 2001 г.), "Ill-posed and Inverse Problems" (Новосибирск, 5-9 августа 2002 г), "International Symposium on Inverse Problems in Engineering Mechanics 2GQ3" (Япония, Нагано, 18-21 февраля 2003 г.), на семинарах программы "Inverse Problems: Computational Methods and Emerging Applications" (Institute for Pure and Applied Mathematics, University of California at Los Angeles, Лос-Анджелес, США, 8 сентября - 12 декабря 2003 г.),
Публикации. По теме диссертации опубликовано 22 печатных работы (из них 16 статей в журналах и трудах конференций, б тезисов конференций). Ссылки на работы приведены в списке литературы.
Структура и объем диссертации. Диссертация состоит из титульного листа, оглавления, введения, трех глав, заключения и списка литературы.
В первой главе рассматривается решение уравнения (В1) при условии, что точное решение z принадлежит компактному множеству. Предполагается, что имеется некоторая последовательность приближенных решений такая, что \\zm — z\\l rm —* 0 при т —> оо (р > 1> Q, С Rn— ограниченное множество). В качестве компактных множеств рассматриваются одномерные (монотонные, выпуклые, с известными константами Липшица на отрезке [а, Ь] = П) и многомерные (выпуклые и вогнутые вдоль осей координат, выпуклые на всей области определения ІЇ) функции. Доказывается равномерная сходимость приближенных решений на некоторых подмножествах областей определения решений. Для монотонных функций — это конечное или счетное объединение всех отрезков, не содержащих концы области определения точного решения и его точек разрыва. Для выпуклых функций—любой замкнутый отрезок, не содержащий концов области определения решения. Для функций с известными константами Липшица —вся область определения. В многомерном случае в качестве области определения решения рассматривается ограниченное открытое множество. Доказывается, что для упомянутых выше подмножеств любое замкнутое подмножество области определения можно рассматривать как область равномерной сходимости.
Во второй главе диссертации предлагается алгоритм для решения интегральных уравнений Фредгольма первого рода и оценки априорной (обычной и максимальной) погрешностей его решения. В результате конечномерной аппроксимации переходим к задаче нахождения минимальных и максимальных значений приближенного решения в точках сетки или к задаче нахождения диаметра выпуклого множества. При этом ограничения на сеточные значения образуют выпуклый многогранник. Указывается алгоритм построения неравенств, определяющих многогранник априорных ограничений для компактных множеств из первой главы. Для построения данного многогранника
предлагается метод отсечения выпуклых многоерапников (МОВМ), позволяющий строить пересечения выпуклых многогранников с полупространствами. Рассматривается обратная задача катодолюминесцентной микротомографии, для которой находится апостериорная погрешность решения с использованием метода расширяющихся компактов и МОВМ.
В третьей главе предложенный алгоритм для решения интегральных уравнений Фредгольма первого рода применяется к решению некоторых задач (задачи Коши для уравнения Лалласа, обратных задач для уравнения теплопроводности> задачи реконструкции симметричных профилей скорости в многоплоскостньтх измерительных модулях). Для рассматриваемых задач находятся приближенные решения, априорные (обычные и максимальные) погрешности, изучаются зависимости этих погрешностей от входных данных и параметров конечномерной аппроксимации. В конце главы приводится описание программного комплекса и его многопроцессорной реализации.
Объем диссертации —112 с, рисунков — 30, наименований в списке литературы—93.
Функции выпуклые или вогнутые вдоль осей координат
Из написанного выше следует, что равномерная оценка погрешности решения существует только для задач, по своей сути являющимися корректными. Для некорректных задач в общем случае невозможно не только построить погрешность приближенного решения Zff} но и даже оценить скорость его сходимости к точному Z.
Целью диссертации являются; 1. создание новых математических методов для оценки апостериорной и априорной погрешностей решения на множествах специальной структуры (на множествах монотонных, выпуклых функций и функций с известными константами Липшица — для ограниченных функций с одномерными областями определения; на множествах функций, выпуклых на всей области определения, и функций, выпуклых или вогнутых вдоль всех прямых, параллельных осям координат, — для ограниченных функций с многомерными областями определения); 2. обобщение результатов, полученных ранее для одномерных выпуклых функций, на многомерные функции, выпуклые на всем множестве определения или вдоль осей координат; 3. создание программного комплекса для нахождения приближенных решений одномерных и двумерных уравнений Фредгольма первого рода и для оценки погрешностей найденных решений на множествах функций, перечисленных ранее; 4. применение разработанных алгоритмов к задаче реконструкции симметричных профилей скорости в многоплоскостных измерительных модулях в акустике, к обратной задаче катодолюминесцентной микротомографии, к обратной задаче для уравнения теплопроводности, к задаче Коши для уравнения Лапласа. Методика исследования базируется на основных положениях теории решения некорректных задач, функционального анализа, выпуклого анализа, математического программирования. Научная новизна и практическая значимость. Равномерная сходимость приближенного решения к точному для множества монотонных функций впервые доказывается для счетного числа отрезков, не содержат щих концы области определения точного решения и его точек разрыва. Также впервые доказывается равномерная сходимость приближенных решений и строятся условия на сеточные значения для функций, выпуклых или вогнутых вдоль осей координат, а также для выпуклых функций на многомерных областях определения- Разработанные в работе алгоритмы оценивания погрешностей решения некорректных задач на компактных множествах могут быть использованы в широких областях (например в томографии, геофизике, астрофизике, спектроскопии), так как рассматриваемые компактные множества очень часто встречаются при решении обратных задач. Функции, ограничивающие множества приближенных решений сверху и снизу, позволя 8 ют гарантировано найти область, которой принадлежит точное решение, если оно существует. В связи с развитием вычислительной техники обобщение использованных ранее методов решения некорректных задач с одномерных на многомерные области определения позволяет численно решать многомерные задачи, решение которых ранее было технически невозможно. Основные положения диссертации, выносимые на защиту, заключаются в следующем. 1. Предложен и реализован в виде комплекса программ алгоритм для реше ния и оценки априорных погрешностей решения интегральных уравне ний Фредгольма первого рода при условии, что точное решение является ограниченной монотонной, выпуклой функцией или функцией с известными константами Липшица на отрезке [а, 6]; ограниченной функцией, выпуклой или вогнутой вдоль осей координат, или ограниченной выпуклой функцией на всей многомерной области определения, 2. Для рассматриваемых функций доказана равномерная сходимость последовательности приближенных решений к точному решению на неко торых подмножествах области определения решения при стремлении погрешностей входных данных к нулю, В случае, если точное решение является монотонной ограниченной функцией на отрезке [а, Ь], то сходимость имеет место на произвольном множестве, являющемся конечным или счетным объединением замкнутых отрезков, не содержащих точек разрыва функции z(x) а также точек а и 6; ограниченной функцией, заданной на открытом ограниченном множестве Q С Жп7 п 2, и являющейся выпуклой или вогнутой вдоль осей координат (или выпуклой на всем множестве). 3. Предложен и обоснован алгоритм для нахождения неравенств, определяющих множество априорных ограничений на сеточные значения для двумерных выпуклых функций. 4. Предложенный алгоритм применен для нахождения решения и оценки погрешностей в задаче реконструкции симметричных профилей скорости в многоплоскостных измерительных модулях в акустике, в обратной задаче катодолюминесцентной микротомографии, в обратной задаче для уравнения теплопроводности в задаче Коши для уравнения Лапласа.
Апробация работы. Основные результаты работы докладывались на семинаре "Обратные задачи математической физики", проводящемся в НИВЦ МГУ под руководством профессоров А. Б. Бакушинского, А. В. Тихонравова и А. Г. Яголы, на конференциях "Обратные и некорректно поставленные задачи" (Москва, факультет ВМиК МГУ, 20-21 июня 2000 г., 26-28 июня 2001 г., 10-11 июня 2003 г.), "Ill-posed and non-classical problems of mathematical physics and analysis" (Узбекистан, Самарканд, 11-15 сентября 2000 г.), "Международная конференция студентов и аспирантов по фундаментальным наукам «Ломоносов-2001». Секция «Физика»" (Москва, физический факультет МГУ, 11 апреля 2001 г.), "Методы оптимизации и их приложения" (Иркутск, Байкал, 24 июня - 1 июля 2001 г.), "Ill-posed and Inverse Problems" (Новосибирск, 5-9 августа 2002 г), "International Symposium on Inverse Problems in Engineering Mechanics 2GQ3" (Япония, Нагано, 18-21 февраля 2003 г.), на семинарах программы "Inverse Problems: Computational Methods and Emerging Applications" (Institute for Pure and Applied Mathematics, University of California at Los Angeles, Лос-Анджелес, США, 8 сентября - 12 декабря 2003 г.),
Метод расширяющихся компактов и обратная задача катодо-люминесцентной микротомографии
Рассмотрим численный алгоритм для построения в конечномерном евклидовом пространстве пересечения некоторого выпуклого многогранника Wq с полупространством, ограниченным заданной гиперплоскостью- В результате пересечения образуется многогранник И +ь который может быть в том числе и пустым множеством. Данный алгоритм был предложен в [57], где был назван методом отсечения выпуклых многогранников (МОВМ), и применялся для решения различных задач в [58-69].
Выпуклый многогранник можно рассматривать как пересечение полупространств, ограниченных плоскостями. Гранью выпуклого многогранника называется пересечение данного многогранника с одной из плоскостей, его образовавшей. Ребром выпуклого многогранника называется отрезок х\Х2 данного многогранника, где х\ и х% — его вершины, если любая внутренняя точка х отрезка х\Х2 является граничной точкой для всех граней многогранника, содержащих данную точку. Следует отметить, что в данном определении существенно, что точка х — внутренняя точка отрезка, так как, если точка х совпадает с одной из вершин (xi или хг), то такое определение не будет соответствовать интуитивным представлениям о ребре, что легко проверить для двумерного случая. Лемма 2.4: Отрезок х\Х2, соединяющий вершины х\ их% выпуклого многогранника W , является ребром этого многогранника тогда и только тогда, когда для любой внутренней точки х отрезка х\Х2 и любых двух точек х\, Х2 Є W, не лежащих па отрезке х\Х2У точка х не принадлежит отрезку, соединяющему точки х\ и Х2 Доказательство. Пусть отрезок х\Х2 является ребром многогранника W, а х —внутренняя точка отрезка х\хч Рассмотрим произвольные точки х\ и #2, такие, что точка х принадлежит отрезку х\Х2- Пусть точка х\ принадлежит многограннику W и не лежит на ребре 0:1X2- Ребро xi2 образовано пересечением нескольких плоскостей. Точка х принадлежит ребру яі#2 поэтому прямая, проходящая через точки х\ и #2, пересекает хотя бы одну из этих плоскостей, так как эта прямая не содержит ребро х\Х2 многогранника W. Из этого следует, что точка х2 лежит вне многогранника W. Тогда для любых двух точек хи #2 Є W\ не лежащих на отрезке х\Х2, точка х не принадлежит отрезку х\Х2- Прямое утверждение доказано. Докажем теперь обратное утверждение. Пусть для любых двух точек xi, Х2 ТУ, не лежащих на отрезке ж 13і внутренняя точка х отрезка х\Х2 не принадлежит отрезку х\х% Считаем, что выпуклый многогранник W рассматривается в n-мерном пространстве. Построим -окрестность точки х. Внутренние точки отрезка прямой, соединяющей точки х\ и Х2, концы которого отстоят от точки х на расстоянии е7 являются точками многогранника Wt лежащими в є-окрестности точки х. Построим для данного є точку Ру лежащую в -окрестности точки х и не принадлежащую многограннику W. Рассмотрим произвольную точку Р из -окрестности точки х, не принадлежащую отрезку хіХ2- Если точка Р не принадлежит многограннику W, то тогда точка Р построена (Р = Я ). Если же принадлежит, то проведем через точки Р и х прямую и найдем отрезок этой прямой, внутренние точки которого лежат в -окрестности точки х. Этот отрезок разбивается точкой х на два равных отрезка, в качестве точки Р возьмем любую внутрен нюю точку одного из этих равных отрезков, который не содержит точку Р . Предположим, что точка Р принадлежит многограннику Wy тогда, положив xi — Р , Х2 — Р, получим, что х\, Х2 Є W и не лежат на отрезке х\Х2, а при этом точка х принадлежит отрезку х\Х2, т. е. противоречие. Поэтому любая -окрестность точки х содержит точки, как принадлежащие многогранни ку W, так и не принадлежащие ему, а это по определению означает, что точка х является граничной точкой множества W. Граница выпуклого мно гогранника W образована пересечением плоскостей, и точка х принадлежит некоторым граням мжл-огранника W. Грань представляет собой выпуклый многогранник в (п— 1)-мерном пространстве, так как она образована пересе чением плоскости и выпуклого многогранника W. Повторяем те же рассуж дения, что и для n-мерного пространства. Таким образом, точка х является граничной точкой для рассматриваемой грали, а следовательно, и для всех граней, содержащих точку х. Поэтому отрезок х\х% является ребром. Теорема 2.13: Для того чтобы вершины х\ и Х2 выпуклого многогранника W соединялись ребром этого многогранника, необходимо и достаточно, чтобы для любой вершины многогранника W , не совпадающей с вершинами х\ UX2, множество плоскостей, проходящих через данную вершину, не содержало всех плоскостей, общих для точек х\ и Х2 Доказательство. Пусть вершины х\ и Х2 многогранника W соединяются ребром. Рассмотрим любую другую вершину многогранника W , обозначим её как х$. Плоскости, общие для точек х\ и Х2, пересекаются по ребру х\Х2-Любой отрезок с концом в точке х пересекающий отрезок х\Х2 в своей внутренней точке х пересекает хотя бы одну из этих плоскостей. Б противном случае существуют точки х\ — хз, #2 Є IV, не лежащие на прямой х\Х2, такие, что х х\Х2, а это по Лемме 2.4 означает, что х\Х2 не является ребром. Поэтому множество плоскостей, проходящих через вершину #з, не содержит В Себе ПО Крайней Мере ОДНу ИЗ ПЛОСКОСТеЙ, Общих ДЛЯ ТОЧеК XI И Х2 Докажем обратное утверждение. Рассмотрим любую грань, которой принадлежит точка х. Так как точка х принадлежит отрезку х\х У то точка х может быть либо граничной точкой либо внутренней для рассматриваемой грани. Проведем через любую вершину многогранника W, принадлежащую данной грани и не совпадающую с вершинами х\ и X2 (обозначим данную вершину как хз), луч х$х. Любая точка данного луча, не лежащая на отрез ке х%х, не принадлежит многограннику W, так как из исходного положения следует, что луч х%х пересекает хотя бы одну из плоскостей, ограничиваю щую многогранник W. Поэтому х — граничная точка для всех граней много гранника W, содержащих данную точку. Тогда по определению отрезок Хіх% является ребром выпуклого многогранника. Обратимся непосредственно к МОВМ. Для построения многогранни-ка Wq+\ достаточно координат всех вершин многогранника Wq. Но для более эффективного построения многогранника Wq+i считаем, что вес грани и вершины занумерованы и известна следующая информация о многограннике Wq:
Функции выпуклые или вогнутые вдоль осей координат
Входные данные: размерность задачи [1 или 2]; ядро интегрального уравнения [а) во входном файле задаются сеточные значения ядра, б) указывается функция для нахождения ядра]; сетки для функций гиііиз(І.І) [число точек, их координаты]; сеточные значения функции % векторы погрешностей для функции и} вид априорных ограничений [монотонность, выпуклость, значение констант Липшица и чисел, ограничивающих точную функцию сверху и снизу]; тип выходных данных [приближенное решение, априорная погрешность (по норме или точечная; обычная или максимальная)].
Как было показано во второй главе диссертации, большая часть матрицы F содержит нули, так как условия ограниченности, выпуклости, монотонности и наличия известной константы Липшица приводят к появлению неравенств, содержащих не более четырех сеточных значений. Поэтому при большой размерности конечномерной задачи желательно хранить и использовать матрицы F, записанные в компактном виде, что по желанию пользователя может быть сделано.
В блоке решения происходит проверка совместности всех неравенств, формирующих многогранник Щ ограничений на сеточные значения искомой функции. Если необходимо найти приближенное решение, то для этого используется вектор zv сеточных значений, принадлежащий Щ . При этом алгоритм нахождения z может быть различным: с использованием случайных чисел, на основе нахождения одной крайней точки множества Щд при решении симплекс методом, на основе нахождения барицентра для Zj , построенного с помощью метода отсечения выпуклых многогранников.
Если требуется найти оценку диаметра множества приближенных решений (в случае апостериорной погрешности в задаче катодолюминесцентной микротомографии или при оценке априорной погрешности по норме решения для интегральных уравнений на компактных множествах), то используется МОВМ. Так как при этом необходимо решать задачу минимизации выпуклой функции на выпуклом многограннике, то пользователь может выбрать метод минимизации (методы нулевого или первого порядков), а также точность нахождения решения (как абсолютную, так и относительную).
При нахождении функций, ограничивающих множество приближенных решений сверху и снизу, имеется возможность выбрать метод, используемый при решении задач линейного программирования (стандартные программные комплексы, например, симплекс-метод, или различные варианты метода отсечения выпуклых многогранников). При решении задач с помощью МОВМ для некоторых множеств априорных ограничений сформированы конечно-мерные многогранники М (например, для монотонных функций, выпуклых функций, монотонных и выпуклых функций).
Для удобства работы пользователя с данным программным комплексом был создан интерфейс в среде Microsoft Developer Studio [91], которая позволяет создавать приложения, написанные на нескольких языках программирования и предназначенные для работы в 32-разрядной операционной системой Windows. В качестве языков программирования использовались Fortran 90 и Visual C++ 7.0.
Программный интерфейс построен как "Мастер -приложение, т. е. вся программа разделена на несколько шагов, которые пользователь должен последовательно пройти: выбор решаемой задачи, выбор компактного множества и формирование сеток, вычисление погрешностей, нахождение приближенного решения, построение функций» ограничивающих множество приближенных решений сверху и снизу. На каждом этапе работы пользователь может воспользоваться разделом "Помощь" и разрешить появившиеся у него вопросы. В качестве результата работы программы пользователь может: 1. выбрать файл, в который будет записана все необходимая информация о решении, погрешностях, времени работы программы; 2, построить график с решением и областью, которой принадлежит любое приближенное решение задачи; 3. сохранить построенный график в формате .bmp (растровый рисунок) или ,eps (векторный рисунок-Программный комплекс содержит подпрограммы, которые могут работать независимо друг от друга (например, подпрограммы для вычисления точечных (обычных или максимальных) погрешностей для различных точек области определения решения. Поэтому программный комплекс содержит в себе блоки, которые могут быть распараллелены при решении задач на многопроцессорных компьютерах так, чтобы независимые части программы работали как отдельные процессы на разных процессорах компьютера [92].
При создании модификации программного комплекса, предназначенного для работы на кластере в Научно-исследовательском вычислительном центре МГУ, использовалась библиотека MPI (Message Passing Interface [93]). Кластер построен на базе двухпроцессорных узлов с процессорами Pentium III (частота процессора — 500 MHz, оперативная память для узла —4 модуля DIMM по 256 Mb), Узлы объединены в двумерную решетку с помощью сети SCI. В качестве служебной сети используется Fast Ethernet.
При этом программа модифицировалась следующим образом: выделялся один основной процесс, который работал с нераспараллеливаемой частью программы и который перенаправлял задачи другим процессам, когда программа достигала распараллеливаемой части. При этом основной процесс сам не участвовал в работе распараллеливаемых подпрограмм и функций, он только передавал и получай данные от других процессов.
Ясно, что так как в программном комплексе есть доля чисто последовательных операций (чтение из файла, запись в файл), то при увеличении числа процессоров в и раз время работы не уменьшается ровно в п раз (эмпирический закон Амдала). Необходимо также учесть, что часть времени тратится на передачу данных между процессами, что тоже замедляет работу. Поэтому, например, некоторые части прохраммы, которые по своей сути могут быть распараллелены, лучше не распараллеливать, так как время, потраченное на передачу данных и ожидание результата от каждого процесса, может оказаться больше, чем время работы нераспараллеленной части программы.
Для модифицированного программного комплекса оказалось, что время нахождения точечных погрешностей с большой точностью обратно пропорционально [п — 1) (не п, так как основной процесс не участвует в работе распараллеливаемых программ), где п — число используемых процессоров.
Реконструкция симметричных профилей скорости в многоплоскостных измерительных модулях
На каждом этапе работы пользователь может воспользоваться разделом "Помощь" и разрешить появившиеся у него вопросы. В качестве результата работы программы пользователь может: 1. выбрать файл, в который будет записана все необходимая информация о решении, погрешностях, времени работы программы; 2, построить график с решением и областью, которой принадлежит любое приближенное решение задачи; 3. сохранить построенный график в формате .bmp (растровый рисунок) или ,eps (векторный рисунок-Программный комплекс содержит подпрограммы, которые могут работать независимо друг от друга (например, подпрограммы для вычисления точечных (обычных или максимальных) погрешностей для различных точек области определения решения. Поэтому программный комплекс содержит в себе блоки, которые могут быть распараллелены при решении задач на многопроцессорных компьютерах так, чтобы независимые части программы работали как отдельные процессы на разных процессорах компьютера [92].
При создании модификации программного комплекса, предназначенного для работы на кластере в Научно-исследовательском вычислительном центре МГУ, использовалась библиотека MPI (Message Passing Interface [93]). Кластер построен на базе двухпроцессорных узлов с процессорами Pentium III (частота процессора — 500 MHz, оперативная память для узла —4 модуля DIMM по 256 Mb), Узлы объединены в двумерную решетку с помощью сети SCI. В качестве служебной сети используется Fast Ethernet.
При этом программа модифицировалась следующим образом: выделялся один основной процесс, который работал с нераспараллеливаемой частью программы и который перенаправлял задачи другим процессам, когда программа достигала распараллеливаемой части. При этом основной процесс сам не участвовал в работе распараллеливаемых подпрограмм и функций, он только передавал и получай данные от других процессов.
Ясно, что так как в программном комплексе есть доля чисто последовательных операций (чтение из файла, запись в файл), то при увеличении числа процессоров в и раз время работы не уменьшается ровно в п раз (эмпирический закон Амдала). Необходимо также учесть, что часть времени тратится на передачу данных между процессами, что тоже замедляет работу. Поэтому, например, некоторые части прохраммы, которые по своей сути могут быть распараллелены, лучше не распараллеливать, так как время, потраченное на передачу данных и ожидание результата от каждого процесса, может оказаться больше, чем время работы нераспараллеленной части программы.
Для модифицированного программного комплекса оказалось, что время нахождения точечных погрешностей с большой точностью обратно пропорционально [п — 1) (не п, так как основной процесс не участвует в работе распараллеливаемых программ), где п — число используемых процессоров.
Диссертация посвящена созданию алгоритмов, их теоретическому обоснованию, численной реализации и практическому применению для решения некорректных задач при наличии априорной информации о том, что точное решение принадлежит компактному множеству функций специального вида. Для компактных множеств можно не только построить приближенное решение, но и найти его апостериорные и априорные погрешности (как по норме, так и в каждой точке области определения). Нахождение функций, ограничивающих сверху и снизу все приближенные решения, а также погрешностей решений при численном решении обратных задач для уравнения теплопроводности, задач Коши для уравнения Лапласа и задачи реконструкция симметричных профилей скорости в многоллоскостных измерительных модулях продемонстрировало данное утверждение.
Доказательство равномерной сходимости приближенных решений к точному на некоторых подмножествах показывает, что функции, ограничивающие приближенные решения, стремятся к точному решению при стремлении погрешностей входных данных и аппроксимации к нулю. Построение же априорной погрешности и исследование ее зависимости от параметров задачи также подтверждает последнее утверждение.
Использование метода отсечения выпуклых многогранников позволяет находить погрешность решения не только для задач, решаемых на компактных множествах, но и для задач с информацией об истокообразной представимости точного решения.
Экстраполяция априорной погрешности на область большого числа точек сеток позволяет эффективно найти не только априорную погрешность, но и построить область допустимых решений для найденного приближенного решения. Такой способ нахождения погрешности решения более выгоден с вычислительной точки зрения, чем непосредственное построение функций, ограничивающих область допустимых решений.
Программный комплекс, основанный на алгоритмах, предложенных в диссертации, позволяет решать интегральные уравнения Фредгольма первого рода на компактных множествах функций с одномерными и двумерными областями определения. Модификация данного комплекса позволяет также решать задачи и на многопроцессорных компьютерах, что даст возможность уменьшить время решения задачи в несколько раз.
Автор хотел бы выразить свою искреннюю благодарность научному руководителю доктору физико-математических наук, профессору Анатолию Григорьевичу Яголе за постоянное внимание к работе и совместное обсуждение полученных результатов.
