Е. н акимова, канд физ мат наук, В. В. Васин



Скачать 131.33 Kb.
Дата24.12.2012
Размер131.33 Kb.
ТипДокументы


Е. Н Акимова, канд. физ.-мат. наук, В.В. Васин, чл.-корр. РАН

Институт математики и механики УрО РАН

(Россия, 620219, Екатеринбург, ул. С.Ковалевской, 16,

тел.(343) 3753446, Е-mail: aen@imm.uran.ru)
Параллельные алгоритмы решения обратных задач

гравиметрии и магнитометрии на МВС-1000 на основе

регуляризованного метода Ньютона

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

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

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



(1)

где гравитационная постоянная, gif" name="object10" align=absmiddle width=39 height=19>скачок плотности на границе раздела сред, аномальное гравитационное поле, асимптотическая плос-кость для данной геологической границы.

Постановка задачи 2. Рассматривается трехмерная структурная обратная задача магнитометрии по численному восстановлению разделяющей поверхности сред (геологической границы) на основе данных о магнитном поле, измеренном на некоторой площади земной поверхности, и скачке вектора намагниченности. Функция описывающая искомую поверхность раздела, удовлетворяет нелинейному двумерному интегральному уравнению Фредгольма первого рода


(2)

где скачок вертикальной компоненты вектора намагниченности,

аномальное магнитное поле, обусловленное отклонением искомой поверхности от асимптотической плоскости .

Предварительная обработка гравитационных либо магнитных данных,

связанная с выделением аномального поля (т.е. получение правых частей уравнений (1)(2)), выполняется по методике [1], разработанной П.С. Мартышко и И.Л. Пруткиным (Институт геофизики УрО РАН).

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

После дискретизации уравнений (1), (2) на сетке где заданы правые части и , и аппроксимации интегральных операторов и

по квадратурным формулам имеем системы нелинейных уравнений


Для решения нелинейных уравнений вида (3) используется итеративно регуляризованный метод Ньютона, успешно применяемый при решении обратных задач гравиметрии и магнитометрии с реальными данными [2][3]






Здесь конечномерные аппроксимации интегральных операторов и правых частей в (1)(2), производная Фреше оператора в точке

последовательность параметров регуляризации. Нахождение очередного приближения по найденному сводится к решению СЛАУ





где плохо обусловленная несимметричная заполненная матрица, вектор размерности
Элементы доказательных вычислений сходимости метода Ньютона при решении задачи гравиметрии. Как показал тщательный анализ, при подходя-щем выборе начального приближения и параметров регуляризации при решении задачи гравиметрии на некотором шаге фактически выполняются (в итерационных точках) условия сходимости одного из вариантов теоремы Нью-тона-Канторовича [4][6], что влечет практическую сходимость метода Ньютона.

Теорема 1. [4]. Пусть решения уравнения

Пусть и при некоторых

выполнены условия: при

при




Тогда при условиях 1,2 и

процесс Ньютона сходится с оценкой погрешности
Проведем доказательные вычисления сходимости метода Ньютона при решении модельной задачи гравиметрии по теореме 1.

Идея доказательных вычислений принадлежит К.И. Бабенко [7].

Условия теоремы 1 проверялись в итерационных точках при

решении модельной задачи гравиметрии для некоторой области

шаги сетки, скачок плотности на

поверхности раздела, гравитационная постоянная,

Синтетическое гравитационное поле определялось путем решения прямой задачи гравиметрии (1) для некоторой исходной поверхности раздела с добавлением случайного шума

Заметим, что в данной задаче модельные данные приближены к реальным.

Пусть решение уравнения решение на текущей итерации уравнения Введем обозначения:









Тогда, при подходящем выборе начального приближения

и параметра регуляризации начиная с некоторого имеем значения констант

удовлетворяющие условиям теоремы 1 о сходимости метода.

Имеем



В случае справедлива оценка

Приведем примеры выбора начального приближения.

















Следовательно, условия теоремы 1 выполняются в итерационных точках.

Теорема 2. [6]. Пусть выполняются неравенства







Тогда, если то уравнение




имеет решение к которому сходится процесс Ньютона, т.е.

и справедлива оценка
Проведем доказательные вычисления сходимости метода Ньютона при решении модельной задачи гравиметрии по теореме 2.

Вычислим константу для задачи гравиметрии (1). Обозначим

Вычислим

Оценим




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

Приведем примеры выбора начального приближения.






Для области




Для области



Следовательно, условия теоремы 2 выполняются и процесс Ньютона сходится.
Методы решения СЛАУ и параллельная численная реализация.

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

В случае применения итерационных методов система (5) приводится к виду







где транспонированная матрица, параметры регуляризации.

Для решения СЛАУ (6) используются следующие методы:

  1. Итеративно регуляризованный метод простой итерации (МПИ)






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

2. Метод сопряженных градиентов в регуляризованном варианте (МСГ)



где и вычисляются по известным формулам [8].

Условием останова итерационных процессов является

Численная реализация и распараллеливание алгоритмов для решения задач гравиметрии и магнитометрии выполнены на многопроцессорном вычислительном комплексе МВС-1000/32 - российском массивно-параллельном суперкомпьютере третьего поколения, состоящем из 16 двухпроцессорных модулей Xeon 2,4 ГГц, 4 Гбайт оперативной памяти в каждом модуле, 40 Гбайт жесткого диска и cетевых интерфейсов Fast Ethernet и Gigabit Ethernet.

Параллельные алгоритмы реализованы с помощью библиотеки MPI на языке Фортран. Распараллеливание итерационных методов основано на разбиении матриц и горизонтальными полосами на блоков, а вектора решения и вектора правой части СЛАУ на частей так, что , где размерность системы уравнений, число процессоров, число строк матрицы в блоке. На каждой итерации каждый из процессоров вычисляет свою часть вектора решения. Host-процессор отвечает за пересылки данных и вычисляет свою часть вектора решения. В случае матричного умножения каждый из процессоров умножает свою часть строк транспонированной матрицы на всю матрицу .

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

На многопроцессорном комплексе МВС-1000/32 были решены задачи вида (1)-(2) с реальными данными. Например, для одного рудного объекта был обработан массив магнитных данных Оренбургской аномалии, измеренного на площади км2 с шагом км и км. Измерения магнитного поля для исследуемого района были выполнены сотрудником Института геофизики УрО РАН В.А. Пьянковым. Расстояние до асимптотической плоскости составляло 6 км. Скачок намагниченности принимался равным =2 (А/м). После дискретизации исходного уравнения на сетке задача (2) сводится к СЛАУ с несимметричной заполненной матрицей . Задача решалась итеративно регуляризованным методом Ньютона с числом итераций и параметром регуляризации . На каждом шаге метода Ньютона использовались параллельные алгоритмы МПИ (с числом итераций ) и МСГ (с числом итераций ). В ходе решения задачи (нахождения функции ) относительная норма невязки уменьшилась в 70 раз.

На рис. 1 представлена восстановленная поверхность раздела .



Рисунок 1: Восстановленная поверхность раздела .

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

В табл. 1 приведены времена счета и коэффициенты ускорения и эффективности решения задачи магнитометрии о восстановлении поверхности раздела между средами с использованием на каждом шаге метода Ньютона параллельного и последовательного итеративно регуляризованного метода простой итерации и метода сопряженных градиентов, соответственно. Здесь – время выполнения параллельного алгоритма на МВС1000 с числом процессоров время выполнения последо­вательного алгоритма на одном процессоре. представляет собой совокупность чистого времени счета и накладных расходов на межпроцессорные обмены, т.е. В общем случае эффективность распараллеливания меняется в пределах . В идеальном случае при равномерной и сбалансированной загрузке процессоров и минимальном времени обменов между ними значение близко к единице, но при решении практических задач она уменьшается за счет накладных расходов.
Таблица 1. Метод Ньютона (N=7) с использованием МСГ или МПИ

(число проц.)

(время, мин.)

(ускорение)

(эффективность)




МСГ / МПИ

МСГ / МПИ

МСГ / МПИ

1

103.15 / 174.86

¾

¾

2

73.06 / 117.42

1.41 / 1.49

0.71 / 0.74

4

41.40 / 63.76

2.49 / 2.74

0.62 / 0.69

5

35.22 / 52.83

2.93 / 3.31

0.59 / 0.66

10

22.91 / 31.51

4.50 / 5.55

0.45 / 0.55

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

  1. Мартышко П.С., Пруткин И.Л. Технология разделения источников гравитационного поля по глубине // Геофизический журнал, 2003. Т. 25. № 3. С. 159-168.

  2. Akimova E.N., Vasin V.V. Stable parallel algorithms for solving the inverse gravimetry and magnetometry problems //Journal for Engineering Modelling. - University of Split, Croatia, 2004. Vol. 17, No. 1. Pp. 3-16.

  3. Акимова Е.Н., Васин В.В., Скорик Г.Г. Решение обратных задач магнитометрии и гравиметрии о восстановлении разделяющей поверхности сред // Материалы 35–й сессии Международного семинара им. Д.Г. Успенского – Ухта: УГТУ, 2008. С. 10–13.

  4. Бахвалов Н.С. Численные методы - М.: Наука, 1973.

  5. Канторович Л.В., Акилов Г.П. Функциональный анализ - М.: Наука, 1977.

  6. Бакушинский А.Б., Кокурин М.Ю. Итерационные методы решения нерегулярных уравнений - М.: ЛЕНАНД, 2006.

  7. Бабенко К.И., Петрович В.Ю. Доказательные вычисления в задаче о существовании решения удвоения // ДАН СССР, 1984. Т. 277. № 2. С. 265-270.

  8. Фаддеев В.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. - М.: Гос. издат. физ. - мат. литературы, 1963.


Похожие:

Е. н акимова, канд физ мат наук, В. В. Васин iconМетодические указания к лабораторному практикуму по механике для студентов первого курса всех специальностей Воронеж 2005
Составители: канд физ.мат наук Евсюков В. А., канд физ.мат наук А. Г. Москаленко, канд физ.мат наук Н. В. Матовых, канд физ.мат...
Е. н акимова, канд физ мат наук, В. В. Васин iconС. Н. Колупаева, канд физ мат наук, доцент, Л. Е. Попов, д-р физ мат наук, профессор
В работе рассмотрена дислокационная динамика кристаллографического скольжения. Показано, что дислокации при движении осуществляют...
Е. н акимова, канд физ мат наук, В. В. Васин iconСоставители: канд физ мат наук., доц
Одним из основных электрофизических параметров вещества является его удельное сопротивление
Е. н акимова, канд физ мат наук, В. В. Васин iconКафедра автоматики и телемеханики
...
Е. н акимова, канд физ мат наук, В. В. Васин iconМеждународный Фестиваль «Звезды Нового Века»
Марчук Эдуард Викторович, канд физ мат наук, учитель физики моу лицея №8: Олимпия
Е. н акимова, канд физ мат наук, В. В. Васин iconПредседатель чл кор. Ран, д-р физ мат наук, проф. В. Д. Мазуров Секретарь аспирант А. М
...
Е. н акимова, канд физ мат наук, В. В. Васин iconГосударственный стандарт союза сср
В. Ф. Беренсон, канд техн наук; Ю. Ф. Крашаков, канд техн наук; В. Б. Скрибачилин, канд техн наук; С. А. Семенов, канд техн наук;...
Е. н акимова, канд физ мат наук, В. В. Васин iconЧадин Р. М., методист Информационно-методического центра мрио, канд физ мат
Использование табличного процессора Excel в практической деятельности учителя математики
Е. н акимова, канд физ мат наук, В. В. Васин iconПрограмма дошкольного образования Москва «Просвещение»
Н., канд пед наук, Дякина А. А., доктор филол наук, Евту­шено И. Н., канд пед наук, Каменская В. Г., доктор псих наук, Кузьмишина...
Е. н акимова, канд физ мат наук, В. В. Васин iconД. М. Лаковский (руководитель темы); И. В. Колечицкая; С. А. Резник, канд техн наук; А. В. Цареградский; Л. А. Вассердам; Л. С. Экслер; В. Н. Свердлов, канд техн наук; Р. А. Каграманов, канд техн наук; В. С. Сытник, канд техн наук
Удк 625. 42: 006. 354 Группа Ж02
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org