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

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

ФОМОЧКИНА Анастасия Сергеевна

РАЗРАБОТКА, ОБОСНОВАНИЕ И ТЕСТИРОВАНИЕ ГЕОМЕТРИЧЕСКИХ МЕТОДОВ РЕШЕНИЯ СИСТЕМ УРАВНЕНИЙ С ПРИМЕНЕНИЕМ СОВРЕМЕННЫХ КОМПЬЮТЕРНЫХ ТЕХНОЛОГИЙ

Специальность: 05.13.18 — Математическое моделирование, численные методы и комплексы программ

3 МАР 2015

005559950

Москва — 2015

005559950

Работа выполнена на кафедре «Прикладная математика и компьютерное моделирование» в ФГБОУ ВПО «Российский государственный университет нефти и газа имени И. М. Губкина»

Научный руководитель:

доктор технических наук, профессор ГЛИВЕНКО Елена Валерьевна

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

доктор технических наук, профессор ФГБУН Института химической физики им. Н. Н. Семенова Российской академии наук МАНЕВИЧ Леонид Исаакович

Philosophy Doctor: Harvard University (USA), профессор НИУ «Высшая школа экономики» ФИНКЕЛЬБЕРГ Михаил Владленович

Ведущая организация:

ФГБУН Институт системного анализа Российской академии наук

Защита диссертации сстоится 24 марта 2015 года в 15 часов на заседании диссертационного совета Д 212.200.14 при ФГБОУ ВПО «Российский государственный университет нефти и газа имени И. М. Губкина» по адресу: 119991, Москва, Ленинский пр., д. 65, корп. 1, аудитория 308.

С диссертацией можно ознакомиться в библиотеке РГУ нефти и газа имени И. М. Губкина (Москва, Ленинский пр., д. 65, корп. 1) и на сайте http://gubkin.ru.

Автореферат разослан /В февраля 2015 года

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

диссертационного совета Д 212.200.14, доктор технических наук, профессор

. В. Егоров

ОБЩАЯ ХАРАКТЕРИСТИКА ДИССЕРТАЦИОННОЙ РАБОТЫ

Актуальность темы исследования

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

Случай линейных систем

Для линейных систем существует большое количество методов решения, которые хорошо себя зарекомендовали в случаях систем с хорошо обусловленными матрицами и ограниченным количеством уравнений. Но, учитывая, что значительное количество актуальных задач, возникающих при построении математических моделей, сводятся к решению систем линейных алгебраических уравнений (СЛАУ), то и требования к таким системам растёт. К примеру, к СЛАУ сводятся задачи интерполяции дискретно заданных функций или задачи построения сеточных аппроксимаций многомерных краевых задач для систем дифференциальных уравнений в частных производных. Такие задачи возникают при математическом моделировании для сложных междисциплинарных приложений, включающих гидрогазодинамические процессы, динамику напряжённо-деформационных состояний и другие (Гливенко Е.В. Математическое моделирование в нефтегазовом деле: учебное пособие. М.: МАКС Пресс, 2009). Само понятие многомерной задачи

быстро эволюционирует, и сейчас необходимо говорить о решениях СЛАУ с размерностями порядка Ю10 на многопроцессорных вычислительных системах с числом ядер, или потоков, в десятки и сотни тысяч (Ильин В. П. Методы и технологии конечных элементов. Новосибирск: Изд-во ИВМиМГ СО РАН, 2007).

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

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

Случай нелинейных систем

Также часто задачи математического моделирования сводятся к решению систем нелинейных уравнений. Они возникают, например, при нахождении экстремумов функции нескольких переменных или при аппроксимации дискретно заданных функций математическими моделями, нелинейными по отношению к параметрам и т.д. Такие задачи возникают повсеместно в различных областях науки, например, в химии {Джонсон К. Численные методы в химии. М.: Мир, 1983), электротехнике, при проектировании кустовых скважин (Иткин В. Ю. Математические методы пространственных траекторий при проектировании кустовых скважин: дис. ...канд. тех. наук: 05.13.18. М., 2004), в оперативном управлении большими трубопроводными системами, в частности, при идентификации их параметров и других. Чаще всего при решении нелинейных систем применяются итерационные методы типа метода Ньютона, использующие линеаризацию. Но такими методами ищется только одно решение, хотя на самом деле их бывает много. Какое из них искать пользователь решает из сторонних соображений так же, как и какое начальное приближение задать, что является определяющим в нелинейном случае.

Цель и задачи работы

Цель работы — создание и исследование новых вычислительных методов для нахождения области, содержащей решения систем вида:

Гп(х1,...,хп) = 0.

Задачи, в соответствии с выбранной целью, сформулированы следующим образом:

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

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

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

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

сопй{А) = ^А ¡-¡Л-11 и характеризует точность решения задачи).

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

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

Методы исследования

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

3

исследованиях большую часть «занимают методы, обычно называемые качественными» (.Арнольд В. И. Дополнительные глава теории обыкновенных дифференциальных уравнений. М.: Наука, 1978). В настоящем исследовании также используются идеи классической геометрии. В последнее время эти идеи связывают с созданием параллельных алгоритмов и архитектурой многопроцессорных машин (Гливенко Е. В., Демьянов В.Л. О параллельных алгоритмах геометрической интерпретации // Информационные технологии. 2000. № 3). В работе широко применяются методы компьютерного моделирования, объектно-ориентированного программирования и программирования с использованием математических пакетов.

Научная новизна работы

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

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

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

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

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

Положения, выносимые на защиту

• Алгоритм отыскания области, содержащей решение систем нелинейных уравнений «с выходом в (л+1)-мерное пространство».

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

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

• Комплекс моделирующих программ, реализующих разработанные алгоритмы.

Апробация работы

Материалы диссертационной работы доложены и обсуждены на международных и всероссийских конференциях:

• 8-я Всероссийская научно-техническая конференция, посвя-щённая 80-летию Российского государственного университета нефти и газа им. И.М. Губкина, «Актуальные проблемы развития нефтегазового комплекса России». Москва, 1—3 февраля 2010;

• 64-я Международная научная студенческая конференция «Нефть и газ-2010». Москва, 12-15 апреля 2010;

• 2-я Международная конференция «Развитие вычислительной техники и её программного обеспечения в России и странах бывшего СССР». Великий Новгород, 12—16 сентября 2011;

• Международная конференция «Нелинейные уравнения и комплексный анализ» оз. Банное, Республика Башкортостан, 18— 22 марта 2013;

• 2-я Российско-монгольская конференция молодых учёных по математическому моделированию, вычислительно-информационным технологиям и управлению. Иркутск, Россия — Ханх, Монголия, 25 июня — 1 июля 2013;

• 4-я Всероссийская конференция «Математическое моделирование и вычислительно-информационные технологии в междисциплинарных научных исследованиях». Иркутск, 30 июня — 4 июля 2014.

Публикации

По теме диссертации опубликовано 11 работ, включая 5 тезисов докладов и 6 статей, в журналах, входящих в перечень ВАК РФ.

Структура и объём работы

Диссертация состоит из введения, четырёх глав, заключения и списка литературы из 57 наименований. Работа содержит 60 рисунков и 14 таблиц. Общий объём диссертации 113 страниц.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

В первой главе описывается метод отыскания области, содержащей решение системы уравнений. Идея данного метода состоит в следующем.

Пусть есть система из п уравнений, которая представлена в виде:

Задача ставится следующим образом: разбить область поиска решения на подобласти и выделить те, внутри которых лежат точки — решения системы (при подстановке координат данных точек в систему (1) уравнения превращаются в тождества). Таким образом, взяв любую точку подобласти, можно говорить о приближённом решении, которое отличается от точного не больше, чем на диаметр данной подобласти. Уточнять решение можно, уменьшая размер подобласти.

Проиллюстрируем метод на примере системы из двух уравнений.

Ъ(Х,У)= 0.

_Рг(х,у) = 0.

Построим две поверхности в трёхмерном пространстве г = ^(х, у) и г. = Р2(х, у) (рисунок 1).

Рисунок 1 — Графики двух поверхностей в трёхмерном пространстве

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

Рисунок 2 — Графики нулевых линий уровня

График функции z — F(x, у) делит пространство на области, где F(x, у) > 0 и F(x, у) < 0, поэтому в окрестности точки-решения найдутся и точки, где у) > 0 и точки, где Fx(x, у) < 0, а также точки, где F2(x, у) > 0 и точки, где F2(x, у) < 0 (рисунок 3).

Рисунок 3 — Графики нулевых линий уровня со знаками функций

Предлагаемый алгоритм поиска области, содержащей точку — решение системы, отыскивает такую область, где есть точки всех четырёх типов («+, +», «+, —», «—, +», «—, —»).

В случае системы размерности п таких вариантов знаков будет 2".

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

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

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

идее метода «выхода в (л+1)-мерное пространство», можно поделить область на подобласти, количество которых кратно количеству процессоров (или процессоров х ядра, если учитывать многоядер-ность процессора), и поручить каждому процессору работу со своей группой подобластей. Тем самым время счета уменьшается пропорционально количеству процессоров.

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

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

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

Линейную систему записывают в виде:

Х1 = а\ Л + а\2Х2 + • • -а\пХп1

(3)

Хп = апХХ1+ап2Х2+-атХ22-

Затем эту запись рассматривают как линейное преобразование «-мерного пространства

Х1нов = а\\Х\ст + й12Х2ст + ■ ■■а\пХпст'

(4)

Х«нов ~ «„Лет + аи2х2ст + • ■ • аппХпст'

Если матрица А (матрица с элементами а у) осуществляет «сжимающее отображение» (норма матрицы А меньше 1), то решение получают итерационным методом. Начиная с некоторого вектора х°, подставляют координаты в правую часть преобразования (4) и получают вектор х1. Таким образом повторяют процесс, с каждым шагом приближаясь к решению системы.

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

Итак, пусть система записана в виде преобразования (4).

В диссертации приводится доказательство следующего факта.

Пусть в пространстве задан «-мерный симплекс с вершинами х\ х2, ..., х(в двухмерном случае это х1, х2, х3). Подставив координаты каждой из вершин х' в правую часть преобразования (4), получим («+1)-вектор • (начало в вершинах симплекса,

конец — в образах вершин). Эти векторы будут все лежать в одном и полупространстве, если начальный симплекс не содержит решение системы (3) и наоборот, если решение системы содержится внутри симплекса, то не найдётся такого общего для всех векторов полупространства, где будут находиться все |г-.

Описанный в третьей главе метод решения системы линейных уравнений основывается на использовании этого факта. Проиллюстрируем метод решения для случая п = 2 (рисунок 4).

Решение снаружи симплекса Решение внутри симплекса

Рисунок 4 — Векторы |2, |3 после нормировки

На рисунке 4 представлены векторы уже в нормирован-

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

Итак, для реализации метода нам нужно уметь выяснять, лежат ли векторы |2, ..., |я+1 в одном «-мерном полупространстве.

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

Решение снаружи симплекса Решение внутри симплекса

Итак, заданы три вектора |2> 1з- Рассмотрим четыре направления: положительный луч оси х, отрицательный луч оси х, положительный луч оси у, отрицательный луч оси у. Каждый из векторов спроецируем на каждое из этих направлений. Если какой-то вектор не имеет проекции на какое-то направление, то считаем эту проекцию нулевой.

Найдём четыре максимума (максимума проекций) для каждого из направлений. Из этих максимумов выберем минимальный.

Полученный результат назовём минимаксной функцией системы векторов 1з и обозначим Мту.

Теперь возьмём попарные суммы векторов |], \ъ Н3 с последующей нормировкой (на рисунке 5 попарные суммы обозначены пунктиром). Минимаксную функцию для нормированных попарных сумм обозначим Мт2. В исследовательских целях также находилось значение минимаксной функции для ненормированных попарных сумм векторов, обозначим её Мтъ.

Случай, когда Мт, = 0 или Мт7 = 0 (следовательно, и Мтъ = 0), будет означать, что векторы лежат в одном полупространстве (так как на одно из направлений проекции нет), а значит точка, являющаяся решением системы, не содержится в рассматриваемом симплексе. Затем, если Мт2 ^ 0 (МтЛ * 0) переходим к следующей части процедуры.

Эта часть процедуры связана с гипотезой, которая была предложена после многочисленных экспериментов, проводимых с помощью моделирующей программы. Гипотеза гласит следующее: если Мт1 ^ 0 и Мт2 0 (Мт3 0), при этом разность г = Мт2 — Мтх > 0, то векторы (/ = 1. ,п+1) не лежат ни в каком одном л-мерном полупространстве, т.е. решение системы находится внутри рассматриваемого симплекса.

Для данного метода была написана моделирующая программа, с помощью которой было проведено тестирование. Для исследования рассматривались:

• системы разной размерности;

• системы с разным числом обусловленности;

• метод с нормировкой векторов, полученных после «размножения»;

• метод без нормировки векторов, полученных после «размножения»;

• различные размеры симплекса и его расположение.

По результатам работы программы были построены графики. Один из таких графиков для случая «размножения» векторов без нормировки для л = 10 и числа обусловленности, принадлежащего интервалу (103, 105), приведён на рисунке 6. По оси абсцисс отложен номер эксперимента, по оси ординат разность МтЪ — Мт].

Решение внутри:

Реш а««; снаружи:

Рисунок 6 — Графики разности минимаксной функции для //=10 (ось абсцисс — номер эксперимента, ось ординат — Мт3 — Мтх)

В качестве плохо обусловленных систем рассматривались системы, коэффициенты которых представляют собой матрицу Гильберта. Для этих систем проводилось сравнение с несколькими итерационными методами, такими как LU-разложение, PLU-разложение, BiSGStab. Часть результатов сравнения приведены в таблице 1.

В первой колонке таблицы указана размерность рассматриваемой СЛАУ, во второй — определитель матрицы, в третьей — число обусловленности, в четвертой, пятой и шестой — норма разности между точным решением и решением, полученным с помощью метода LU-разложения, PLU-разложения и BiCGStab соответственно. В остальных — разность минимаксов в соответствии с алгоритмом, в случаях, когда решение находится внутри и снаружи рассматриваемого симплекса.

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

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

Итак, пусть задана система

= 0,

Fj , ,. = 0,

Fn{xvx2,. = 0.

Следуя методике, описанной выше, переписываем эту систему в виде

Таблица 1 — Исследование метода на матрице Гильберта, сравнение с другими методами

Размерность Определитель Число обусловленности Норма невязки для Ш-разложения Норма невязки для РШ-разложения Норма невязки для BiCGStab П,без нормировки решение внутри г1, без нормировки, решение снаружи г2, с нормировкой решение внутри г2, с нормировкой решение снаружи

2 8.333Е-02 2.700Е+01 0.000Е+00 0.000Е+00 3.11Е-08 —0.4472 0 0.03495 0

10 2.160Е-53 3.540Е+13 8.696Е+02 3.500Е+03 0.1831 —0.1153 0 -0.01171 0

20 4.210Е-226 6.280Е+28 1.550Е+18 1.810Е+18 1757 —0.04848 0 0.02421 0

30 3.402Е -519 1.180Е+44 4.430Е+33 3.020Е+33 1.218 —0.02625 0 0.05032 0

35 6.860Е -711 5.190Е+51 9.000Е+41 1.990Е+41 5.63Е+14 —0.02247 0 0.04728 0

40 1.097Е-932 2.250Е+59 1.230Е+49 7.520Е+47 1.479 —0.01964 0 0.05569 0

45 1.390Е-1184 9.880Е+66 6.130Е+56 2.130Е+56 0.6583 —0.01744 0 0.05211 0

50 1.393Е-1466 4.330Е+74 2.060Е+65 9.990Е+64 3.9Е+16 —0.01569 0 0.04912 0

55 1.104Е-1778 1.910Е+82 7.410Е+74 2.600Е+72 185000000 —0.01425 0 0.04659 0

60 6.916Е-2121 8.420Е+89 1.760Е+84 2.260Е+82 1.744 —0.01306 0 0.0444 0

65 3.424 Е-2493 3.710Е+97 3.630Е+94 1.380Е+91 4.247 —0.01205 0 0.04248 0

70 1.339Е-2895 1.650Е+105 7.990Е+104 1.130Е+100 1.091 —0.01119 0 0.04079 0

75 4.138Е-3328 7.260Е+112 3.360Е+114 2.610Е+109 3.013 —0.01044 0 0.03928 0

80 1.010Е-3790 3.240Е+120 1.340Е+126 2.160Е+119 43.36 —0.009783 0 0.03792 0

85 1.946Е-4283 1.430Е+128 1.200Е+137 1.440Е+128 2165 —0.009206 0 0.03669 0

90 2.960Е-4806 6.400Е+135 8.840Е+148 7.730Е+136 1.195 —0.008693 0 0.03558 0

95 3.555Е-5359 2.830Е+143 5.100Е+159 5.190Е+143 4.261 —0.008234 0 0.03455 0

96 2.261 Е-5473 9.620Е+144 1.390Е+162 7.750Е+148 2.369 —0.008148. 0 0.03436 0

97 8.992Е-5589 3.260Е+146 3.220Е+164 7.150Е+151 1.473 —0.008063 0 0.03417 0

98 2.235Е-5705 1.100Е+148 7.650Е+166 9.020Е+153 2.43 —0.007981 0 0.03398 0

99 3.471 Е-5823 3.730Е+149 7.040Е+169 2.860Е+155 1.359 —0.0079 0 0.03379 0

100 3.370Е-5942 1.270Е+151 2.020Е+172 2.520Е+156 6.29Е+11 —0.007821 0 0.03361 0

хп=хп + рп(х\>->хп)-

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

Х1нов =Х1ст + Хлст)'

■"•«нов — хпст + ^п (Х1ст' • • •' хпст ) •

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

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

Предлагаемый в главе 4 метод решения нелинейной системы уравнений заключается в численной реализации этой теоремы.

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

С помощью этой программы решена задача, возникающая при расчёте пространственной траектории горизонтальной скважины (Иткин В.Ю. Математические методы пространственных траекторий при проектировании кустовых скважин: дис. ...канд. тех. наук: 05.13.18. М„ 2004).

Рассматривается модель траектории вида «дуга окружности — отрезок — дуга окружности». На рисунке 7 изображена скважина, наклонно-направленная часть которой состоит из четырёх участков:

• вертикальный участок от устья до точки зарезки — отрезок длины 1Д

• участок набора зенитного угла — дуга в вертикальной плоскости радиуса Ш,

• участок стабилизации — наклонный отрезок длины 1Л,

• участок изменения зенитного угла и азимута — дуга в наклонной (вообще говоря) плоскости радиуса Я2.

Устье — точка Вн„ точка входа в пласт — Ек.

Рисунок 7 — Скважина

На рисунке 7: 1 — точка зарезки; 2 — вертикальный участок; 3 — дуга в вертикальной плоскости; 4 — участок стабилизации; 5 — дуга в наклонной плоскости; 6 — горизонтальный участок.

Направление вертикального участка — строго вниз, определяется вектором У0 = [0, 0, 1]. Направление участка стабилизации определяется единичным вектором У,. Направление в точке входа в пласт определяется единичным вектором У2. Известные параметры: Вк — точка входа;

Е„ — точка входа в продуктивный пласт; /_о — длина вертикального участка; /?! — радиус первой дуги;

— радиус второй дуги; У0 — вектор, направление вертикального участка [0, 0, 1]; У2 — единичный вектор, направление в точке входа в продуктивный пласт.

Неизвестные параметры:

Ь] — длина участка стабилизации;

К, — направление участка стабилизации.

Каждый вектор может задаваться двумя углами: зенитным углом 7л (углом между вектором и вертикалью) и азимутом А (углом между направлением на север и горизонтальной проекцией вектора):

V, = [5т(у| 1 )-зт(/л,), со5(Л|)-5И1 (/л,), 005(7/1,)],

У2 = [5т(/42)-8т(//12), со5(/42)'5т(/и2), СО5(7И2)].

В диссертационной работе подробно описан алгоритм получения системы. Она выглядит следующим образом:

h + W

t.

Ll +

sin (In2) t-,

sin (Itlj)

h +

'I+A+:

U

sin (/h2)

где введены следующие обозначения: Tu

sin(/4í)sin(7rtI) + /2 sin(/l2) = jV,, cosí/í^-siní/w^ + íj COS(/12) = 7V2, eos (7л,) + /2ctg(7«2) = N},

= tg t2 = R2 tg

sin(7«,);

T2 = arceos |cos(7«2 — 7л() —sin(7/j1)-sin(/«2)(l — cos(/42 — Л,))];

[/V[, N2, N3] — координаты вектора N= Ew — Bw— 70-F0.

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

В ячейках записан угол от положительного направления оси ОХ (ось изменения 1пх) до вектора, полученного после подстановки /л1 и Ау в преобразование согласно алгоритму. Если сумма значений углов по контуру области все время увеличивается или уменьшается, это означает, что искомый интеграл равен 1 или — 1, следовательно, решение системы лежит внутри области.

Таблица 2 — Таблица углов для задачи расчёта пространственной траектории горизонтальной скважины

0 20 21,5 23 24,5 26 27,5 29 30,5 32 33,5 35 36,5 38 39,5 41 42,5 44 45,5 47 48,5

210 47,9 46,7 45,3 43,6 41,5 38,9 35,5 30,9 24,5 15,2 1,32 341,6 318,3 297,9 283,3 273,5 267 262 259 256

211,5 49,1 48,1 46,9 45,4 43,7 41,5 38,6 34,7 29 20,5 6,9 345,2 317,4 293,4 277,8 268 262 258 254 252

213 50,3 49,5 48,5 47,4 45,9 44,2 41,8 38,7 34 26,7 14,1 350,99 316,3 287,4 271,1 262 256 253 250 248

214,5 51,5 50,9 50,1 49,3 48,2 46,9 45,2 42,8 39,3 33,7 23,3 0,279 315,2 279 263 255 251 248 246 244

216 52,7 52,3 51,8 51,2 50,5 49,7 48,6 47,1 44,9 41,3 34,2 15,5 313,7 ■ШШ 253 аШ?' 244 242 241 240

217,5 53,9 53,7 53,4 53,2 52,9 52,5 52 51,4 50,5 49,1 46,3 38,1 310,1 248 ЩЦ 239 237 236 236 235

219 55,1 55,1 55,1 55,1 55,1 55,2 55,4 55,6 56 56,8 58,4 63,2 341::' 229 230 230 231 231

220,5 56,3 56,5 56,7 57 57,4 57,9 58,7 59,7 61,3 64 69,2 82,5 135 198 214 220 223 224 225 226

222 57,5 57,8 58,3 58,9 59,6 60,5 61,8 63,6 66,3 70,5 78,2 94,6 133 179 201 210 215 218 220 222

223,5 58,6 59,2 59,9 60,7 61,7 63,1 64,8 67,3 70,8 76,2 85,3 102 132 167 189 201 208 212 215 217

225 59,8 60,5 61,4 62,4 63,8 65,5 67,7 70,7 74,9 81,1 90,8 107 131 159 180 193 201 206 210 212

226,5 60,9 61,8 62,9 64,1 65,7 67,8 70,3 73,8 78,5 85,2 95 110 130 153 172 185 194 200 204 208

228 62 63 64,3 65,8 67,6 69,9 72,8 76,6 81,6 88,6 98,3 112 129 148 165 178 188 194 199 203

229,5 63 64,2 65,7 67,3 69,4 71,9 75,1 79,1 84,4 91,4 101 113 128 145 160 173 182 189 194 198

231 64,1 65,4 67 68,8 71,1 73,8 77,1 81,4 86,8 93,7 103 114 127 142 156 167 177 184 190 194

232,5 65,1 66,5 68,2 70,2 72,6 75,5 79 83,4 88,8 95,6 104 115 127 140 152 163 172 179 185 190

234 66 67,6 69,4 71,6 74,1 77,1 80,7 85,1 90,6 97,2 105 115 126 137 149 159 168 175 181 186

235,5 66,9 68,6 70,5 72,8 75,4 78,5 82,3 86,7 92,1 98,5 106 115 125 135 146 155 164 171 177 182

237 67,8 69,6 71,6 74 76,7 79,9 83,6 88,1 93,3 99,6 107 115 124 134 143 152 160 167 173 178

238,5 68,7 70,5 72,6 75 77,8 81,1 84,9 89,3 94,4 100 107 115 123 132 141 149 157 164 170 175

Разбив область на блоки размером 4x4 ячейки в таблице 2 и вычислив степень отображении по границам этих блоков, получим подобласть [38; 42,5]х[216; 220,5]. Затем, уменьшая размеры ячеек, бьши получены области меньшего размера, содержащие решение /л, = 39,1°, Ах = 218,9°, которое соответствует решению, найденному В. Ю. Иткиньтм.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ ДИССЕРТАЦИОННОГО ИССЛЕДОВАНИЯ

1. Разработан новый метод отыскания области, содержащей решение системы уравнений, основанный на свойствах нулевых линий уровня функций, входящих в систему. Метод включает в себя:

• алгоритм нумерации узлов сетки;

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

• алгоритм проверю! «подозрительной» подобласти на содержание внутри себя решения.

2. Разработан новый метод отыскания области, содержащей решение системы линейных алгебраических уравнений, основанный на свойствах неподвижной точки и степени отображения непрерывного преобразования. Метод включает в себя:

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

• алгоритм проверки расположения векторов, а именно получение ответа на вопрос лежат ли л+1 вектор л-мерного пространства в одном л-мерном полупространстве.

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

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

• алгоритм определения ориентации расположения точек;

• алгоритм подсчёта степени отображения.

4. Написан комплекс моделирующих программ, реализующих разработанные методы.

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

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

ОСНОВНЫЕ ПОЛОЖЕНИЯ ДИССЕРТАЦИОННОЙ РАБОТЫ ОТРАЖЕНЫ В СЛЕДУЮЩИХ ПУБЛИКАЦИЯХ

Статьи в журналах, рекомендованных ВАК

1. Гливенко, Е. В. Решение систем квадратных уравнений на многопроцессорной ЭВМ / Е.В. Гливенко, A.C. Фомочкина, С. А. Прядко // Вопросы радиоэлектроники.— 2010,— №2.— С. 9-11.

2. Фомочкина, A.C. Использование сеточного метода для решения систем нелинейных алгебраических уравнений / А. С. Фомочкина // Вопросы радиоэлектроники,— 2011.— № 4,— С. 13-18.

3. Гливенко, Е. В. Методы решения систем линейных и нелинейных алгебраических уравнений, обладающие естественным параллелизмом / Е.В. Гливенко, A.C. Фомочкина, С.А. Прядко, К.А. Левонян // Информационные технологии,— 2011.— № 10,— С. 31-35.

4. Фомочкина, А. С. Применение параллельных методов для решения систем нелинейных уравнений / А. С. Фомочкина // Вопросы радиоэлектроники.— 2013.— № 2.— С. 13—18.

5. Гливенко, Е. В. Решение систем нелинейных алгебраических уравнений с помощью степени отображения / Е. В. Гливенко, A.C. Фомочкина, С.А. Прядко // Информационные технологии,- 2013,- № 7,- С. 7-10.

6. Фомочкина, А. С. Использование топологических свойств неподвижной точки для решения систем линейных алгебраических уравнений на кластерных системах / A.C. Фомочкина // Вопросы радиоэлектроники,— 2014.— Т. 4.— № 4,— С. 17—21.

Публикации в сборниках всероссийских и международных конференций

1. Гливенко, Е. В. Параллельные алгоритмы при геометрической интерпретации задачи / Е.В. Гливенко, A.C. Фомочкина, С. А. Прядко // Тезисы докладов 8-й Всероссийской научно-технической конференции, посвященной 80-летию Российского государственного университета нефти и газа им. И. М. Губкина, «Актуальные проблемы развития нефтегазового комплекса России». Москва, 1-3 февраля, 2010,— Ч. 2,— Секция 5-11.— С. 57-58.

2. Фомочкина, A.C. Параллельные алгоритмы при геометрической интерпретации задачи / А. С. Фомочкина // Тезисы докладов 64-й Международной научной студенческой конференции «Нефть и газ-2010». Москва, 12—15 апреля 2010,— Секция «Автоматизация систем нефтегазовой отрасли»,— 2010,— С. 29.

3. Гливенко, Е.В. Первая отечественная многопроцессорная ЭВМ М-10 / Е. В. Гливенко, A.C. Фомочкина, С.А. Прядко // Труды SORUCOM-2011. 2-я Международная конференция «Развитие вычислительной техники и её программного обеспечения в России и странах бывшего СССР». Великий Новгород, 12-16 сентября 2011,— С. 89-95.

4. Фомочкина, А. С. Методы геометрической интерпретации задачи для решения систем нелинейных (недифференциальных) уравнений / А. С. Фомочкина // Тезисы докладов Международной конференции «Нелинейные уравнения и комплексный анализ». Оз. Банное, 18—22 марта 2013.— С. 48.

5. Фомочкина, А. С. Параллельный метод для решения систем обыкновенных нелинейных уравнений / А. С. Фомочкина // Тезисы докладов 2-й Российско-монгольской конференции молодых учёных по математическому моделированию, вычислительно-информационным технологиям и управлению. Иркутск, Россия — Ханх, Монголия, 25 июня — 1 июля 2013.

055(02)2 Ротапринт ИКИ РАН

_Москва, 117997, Профсоюзная ул., 84/32

_ Подписано к печати 2.2.2015 г.

Заказ 3346 Формат 70х 108/32 Тираж 100 1,47 усл.-печ. л.

Для заметок