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

• Фомочкина, Анастасия Сергеевна
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Фомочкина, Анастасия Сергеевна

Оглавление

Оглавление

Введение

Глава 1. Выход в (п+1)-мерное пространство

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

1.2. Теоретическое обоснование

1.3 Алгоритм

1.4 Моделирующая программа

1.5. Тестирование метода

1.6. Выводы

Глава 2. Некоторые сведения из топологии

Глава 3. Использование свойств неподвижной точки для решения систем линейных уравнений

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

3.2. Теоретическое обоснование

3.3. Алгоритм

3.4. Моделирующая программа

3.5. Тестирование метода

3.5.1. Тестирование на СЛАУ, полученных с помощью датчика случайных

чисел

3.5.2. Тестирование на СЛАУ, коэффициенты которых представляют собой

матрицу Гильберта

3.6. Выводы

Глава 4. Использование свойств неподвижной точки для решения систем нелинейных уравнений

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

4.2. Теоретическое обоснование

4.3. Алгоритм для случая п=2

4.4. Моделирующие программы

4.5. Тестирование метода

4.5.1. Тестирование на системах квадратных уравнений

4.5.2. Тестирование метода с построением таблицы углов

4.5.3 Тестирование метода на системе, возникающей при расчете

пространственной траектории горизонтальной скважины

4.6. Выводы

Заключение

Список литературы

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

Введение

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

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

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

Для линейных систем существует большое количество методов их решения, которые хорошо себя зарекомендовали в случаях систем с хорошо обусловленными матрицами и ограниченным количеством уравнений. Но, учитывая, что значительное количество актуальных задач, возникающих при построении математических моделей, сводятся к решению систем линейных алгебраических уравнений (СЛАУ), то и требования к таким системам растет. К примеру, к СЛАУ сводятся задачи интерполяции дискретно заданных функций или задачи построения сеточных аппроксимаций многомерных краевых задач для систем дифференциальных уравнений в частных производных [14,45,47]. Такие задачи возникают при математическом моделировании для сложных междисциплинарных приложений, включающих гидро-газодинамические процессы, динамику напряженно-деформационных состояний и другие [18,39,40]. Само понятие многомерной задачи быстро эволюционирует, и сейчас необходимо говорить о решениях СЛАУ с размерностями порядка 1010 на многопроцессорных вычислительных системах с числом ядер, или потоков, в десятки и сотни тысяч [9,32].

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

реализации не могут эффективно использоваться многопроцессорные системы, которые стремительно развиваются в настоящее время [5,6,16,17,20,40].

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

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

Также часто задачи математического моделирования сводятся к решению систем нелинейных уравнений. Они возникают, например, при нахождении экстремумов функции нескольких переменных или при аппроксимации дискретно заданных функций математическими моделями, нелинейными по отношению к параметрам и так далее [2,13,31,41]. Такие задачи возникают повсеместно в различных областях науки, например, в химии [28], в электротехнике, в проектировании кустовых скважин [33], в оперативном управлении большими трубопроводными системами, в частности, при идентификации их параметров и других[42,52]. Чаще всего при решении нелинейных систем применяются итерационные методы типа метода Ньютона, использующие линеаризацию [1,11,43]. Но такими методами ищется только одно решение, хотя на самом деле их бывает много. Какое из них искать пользователь решает из сторонних соображений так же, как и какое начальное приближение задать, что является определяющим в нелинейном случае.

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

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

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

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

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

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

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

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

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

Идея использования геометрической интерпретации задачи заимствована у В.И. Арнольда, который применял методы современной геометрии в теории дифференциальных уравнений. В его исследованиях большую часть «занимают методы, обычно называемые качественными»[7,8]. В настоящем исследовании также используются идеи классической геометрии. В последнее время эти идеи связывают с созданием параллельных алгоритмов и архитектурой многопроцессорных машин [19,21-26,29]. В работе широко применяются методы компьютерного моделирования, объектно-ориентированного программирования и программирования с использованием математических пакетов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Международной конференция "Нелинейные уравнения и комплексный анализ" (оз.Банное, респ. Башкортостан, 18-22 марта 2013);

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

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

Публикации

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

Глава 1. Выход в (п+1)-мерное пространство

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

Метод, рассматриваемый в этой главе, представляет собой алгоритм отыскания области, содержащей решение системы уравнений. В данной работе под уравнением от п независимых переменных х\,...,хп понимается связь между двумя функциями от этих переменных, определенная знаком равенства. Если имеется п уравнений, то можно говорить о решении системы этих уравнений, называя решением набор координат (х1°, х®,..., х„°) некоторой точки «-мерного пространства, которые при подстановке в каждое из этих уравнений обращает эти уравнения в тождества. Таких решений может не быть совсем, а может быть несколько и даже бесконечное число решений.

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

1.2. Теоретическое обоснование

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

лг2,..., хи) = О = О

'......................... (1.1)

= О

Рассмотрим п поверхностей, расположенных в (и+1)-мерном пространстве, которые описываются уравнениями:

(1.2)

Л+1

Каждое из уравнений системы (1.1) описывает «-мерное многообразие, которое представляет собой нулевую линию уровня для (л+1)-мерной поверхности, заданной соответствующим уравнением из системы (1.2).

Каждое /-ое многообразие обладает тем свойством, что делит и-мерное пространство на две области: область, где < 0 и область,

где^(х1,х2,...,хл) > 0. В окрестности многообразия находятся как точки одной области, так и точки другой. Имея п многообразий, получим 2п соответствующих областей.

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

О

^ Ъ ох + - +

о.

2 _

+ +

+ -

+

+

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

Проиллюстрируем метод на примере системы из двух уравнений: У1{х,у) = О

Построим две поверхности в трехмерном пространстве г=Е\(х,у) и ,у)

(рисунок 1.1).

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

Рисунок 1.2 - Графики нулевых линий уровня График функции г=Р{х,у) делит пространство на области, где 2 = /7(х,>,)>0 и г= =Дл\у)<0, поэтому в окрестности точки-решения найдутся и точки, где и

точки, где /г1(лг,_у)<0, а также точки, где и точки, где Г2(х,у)<0 (рисунок

1.3).

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

1.3 Алгоритм

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

= О

Е2{рс^х 2,...,хп) = О

<

Представим рассматриваемую область гиперплоскости в виде набора ячеек, размеры которых определяются шагом сЬс(с1хь скъ... , с1хп).

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

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

3. Если в некоторых узлах ячейки встречается как знак «плюс», так и знак «минус», то это означает, что через данную ячейку проходит многообразие ^ (л:! рсг,.. -рс„)=0. Аналогичным образом проверяем данную ячейку на содержание многообразий ...уси)=0 ...

^п1 } • • ■ у^п)~ 0 •

4. Если окажется, что ячейка содержит в себе все многообразия Рг{х\уХ2>»'*Хп)=®> 1=0..п, то это ячейка становится «подозрительной» на решение, т.е. кандидатом на содержание внутри себя решения системы. При этом стоит заметить, что расстояние между любыми двумя функциями системы в любой точке «подозрительной» ячейки не превосходит диаметра этой ячейки. В некоторых задачах такого

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

5. Внутри «подозрительной» ячейки рассмотрим более детальную сетку, в узлах которой снова будем вычислять значения Р^ху^—^-®, 1=0..п. И если среди этих узлов найдутся такие, в которых будут содержаться все комплекты знаков (всевозможные сочетания «плюсов» и «минусов» всех функций), то это будет означать, что в данной ячейке находится решение системы.

1.4 Моделирующая программа

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

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

проверяются все ячейки на содержание внутри них нулевых линий уровня для всех поверхностей хп+\=Г1{х\,..х^) (/=1..я) и выбираются те ячейки, в которых найдутся все нулевые линии уровня. Блок-схема первой подпрограммы изображена на рисунке 1.4.

Рисунок 1.4 - Блок-схема первой подпрограммы Рассмотрим подробнее алгоритм второй подпрограммы, реализующей пункт 5 из вышеизложенного алгоритма. На её вход поступают сами функции F, (i=l..n), границы области поиска х° (яД х20,..., хп°) и х' (xi', х2',..., хп% шаг детализации dx {dxь dx2>... , dxn). Для определения все ли сочетания знаков имеются, заводится массив булевых переменных (переменные, принимающие два значения - false или

true) размерности 2", переменная bin_sign, принимающая значения в двоичной системе счисления, а также счетчик, который считает, сколько сочетаний знаков уже имеется на данном этапе подпрограммы.

На первом этапе вычисляется значение F\(x), где х - это рассматриваемый узел. В начале программы лс=х°, затем далее по узлам (порядок обхода всей области будет приведен ниже). Если Fi(x)>0, тогда bin_sign= 1. Затем вычисляется F2(x) и если F2(x)>0, тогда bin_sign= 10+bin sign. Так вычисляем все Ffa) (/=1..п) и если F,{x)>0, тогда bin_sign=\0,A+bin sign. Тем самым переменная binjsign характеризует сочетание знаков Fj(x) (/=1..п). Например,

ад ад ад ад

Знаки + ... - + +

тогда binjsign - 1...011. Чтобы запомнить такое сочетание знаков, переведем binjsign в десятичную систему счисления m=convert{bin_sign, dec, bin) и в специально заведенном нами булевом массиве т-ому элементу присвоим значение true, mas[m\=true.

При этом введем счетчик, который считает, сколько различных вариантов на данном этапе программы. Как только вариантов будет 2", это будет означать, что найдены всевозможные сочетания знаков, следовательно, точное решение находится внутри рассматриваемой области. Блок-схема второй подпрограммы изображена на рисунке 1.5.

Рисунок 1.5 - Блок-схема второй подпрограммы

пронумеруем все узлы по порядку числами от 1 до ГТ , где - это целая часть

1=1

((х/-х°)/ сЬс,)+1. При этом сначала увеличиваем координату затем х\, и так далее, заканчивая увеличением х„. Тогда, если у узла порядковый номер равен р, то координаты его можно вычислить следующим образом:

х, = х,° + ост.от _ деления

(р}

У

•сЬсх

х2 = х2 + целмасть

ост.от деления

Г

Р

х. = х{ + целмасть

ост.от деления

\

\\

Ш

V & У

гк

;=1

• СЬС;

У

хп = хп + целмасть

ост.от деления

п—1

7=1

V

• сЬс„

У

1.5. Тестирование метода

Рассмотрим подробно работу программы на нескольких примерах. Пример 1.

Первой подпрограмме были заданы следующие начальные условия: + л:22 — 1 = О

х,+*2 -1.1 = 0

е [-5.2;2] ,х2е [-1.2 ;1.5], шагпо*! 0.002, пох2 0.001 Нулевые линии уровня примера 1 приведены на рисунке 1.6.

Рисунок 1.6 - График нулевых линий уровня примера 1

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

Пример 2.

Первой подпрограмме были заданы следующие начальные условия:

2.

Х\ + Х2 ~ 3*1 + 2*2 —1 = 0

Х\е [-3;3], х2е [-3 ;3], шаг по я^О.О!, по х20.02

х\ +хг -1-1 = 0 Нулевые линии уровня примера 2 приведены на рисунке 1.7.

Рисунок 1.7 - График нулевых линий уровня примера 2 В результате работы первой подпрограммы были выделены следующие «подозрительные» на решение ячейки (первый интервал по хь второй интервал по

х2):

[-0.56;-0.55]х[-0.9;-0.88] [0.6;0.61]х[-0.84;-0.86] [0.61 ;0.62]х[-0.84;-0.86]

Детально эти ячейки можно рассмотреть на рисунке 1.8, рисунке 1.9 и рисунке 1.10.

Рисунок 1.8 - Ячейка [-0.56;-0.55]х[-0.9;-0.88] примера 2

Рисунок 1.9-Ячейка [0.6;0.61]х[-0.84;-0.86] примера2

отт одае

0,056 0.854 0362-

сдавив 0,609 0,61 0311 0312 0,613 0,614 0.615

Рисунок 1.10 - Ячейка [0.61;0.62]х[-0.84;-0.86] примера 2 Данные «подозрительные» ячейки были переданы в качестве начальных условий второй подпрограмме, в результате чего последняя ячейка была исключена, а нахождение решения в первых двух было подтверждено.

Пример 3.

Первой подпрограмме были заданы следующие начальные условия:

{х2+х2+х,+Х —1 = 0

1 , 2 12 х,е[-1;3] ,х2е[-2 ;2], шаг по хг 0.0009, по х2 0.00085 5х, +3х2-1.1 = 0

Нулевые линии уровня примера 2 приведены на рисунке 1.11.

Рисунок 1.11- График нулевых линий уровня примера 3

[0.7244;0.7253]х[-0,5108;-0.50995] [0.7244;0.7253]х[-0.50995;-0.5091] [0.7244;0.7253]х[-0,5091;-0.50825] [0.7244;0.7253]х[-0.50825;-0.5074]

Детально эти ячейки можно рассмотреть на рисунке 1.12, рисунке 1.13, рисунке 1.14 и рисунке 1.15.

X

0,7247 0,7248 0 7249 0,725 0.7251 0,7252 0.7253 •0,51151021,51041.510615108:

Рисунок 1.12 - Ячейка [0.7244;0.7253]х[-0,5108;-0.50995] примера 3

X

0,7247 0/246 0/249 0.725 . 0/251 0/252 1,50921,50941,50961,5098-

Рисунок 1.13 - Ячейка [0.7244;0.7253]х[-0.50995;-0.5091] примера 3

0,72465 Q .72460,72465 0,72470,724750.72480,72485

1,5064

1,5066

1,5068

0,509

Рисунок 1.14 - Ячейка [0.7244;0.7253]х[-0,5091;-0.50825] примера 3

0,7244 0,72445 0,7245 0,72455 0,7246 0,72465 0,7247 (¿074 ............... ...............

1,5076

15078

•0,506

15062

Рисунок 1.15 - Ячейка [0.7244;0.7253]х[-0.50825;-0.5074] примера 3 Данные «подозрительные» ячейки были переданы в качестве начальных условий второй подпрограмме, в результате чего все ячейки кроме [0.7244;0.7253]х[-0,5091;-0.50825] были исключены, а нахождение решения в этой ячейке было подтверждено.

Далее тестирование проводилось на системах, состоящих из уравнений-полиномов, коэффициенты и степени которых были получены с помощью датчика случайных чисел. А именно для каждого из п уравнений был случайным образом сгенерирован вектор коэффициентов размерности к (в рассматриваемых ниже примерах к=5) - а(а\,а2...ак). Также для каждого из уравнений была сгенерирована матрица размерности к*п, которая отвечала за степень каждой

Ai — Р\к

переменной перед каждым из а, коэффициентов — , свободный же

_Дг1 — Рпк_

коэффициент выбирался так, чтобы точка jc0[1,1 »•••!] была решением данного

к

а1х^х2А\..хпА" +...+акх^1х2А2...хпА" +Ь = 0, где .

¿=1

В приведенных ниже примерах показана только работа второй подпрограммы на области х;е [0; 1.5], /=1 ..п. Сетка при этом бралась размерности 10". Ввиду того, что алгоритм предполагает вычисление функций в каждом узле,

то для удобства пользователя также находится значение гтп^|/^(х)| и номер узла, в котором этот минимум достигается.

5Ох, + 9х,х22 - 48х2 + 20х,2х2 + 65х22 +4 = 0 6х}2 +31х1х22 + 77х,х2 -61х2 -53 = 0

График представлен на рисунке 1.16.

Результат: решение находится в данной ячейке, минимум суммы модулей функции равен 13.03425 и достигается в узле №74.

1 -

0,5-

-I-----1—

0,5

-1-1-1-1-1-1-1

1 1,5

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

-70xj + 88xjx22 + 80x2 + 21x,2x2 + 60x22 -179 = 0 6x,2 - 82xjx22 + 19x,2x2 + 90x2 -33 = 0 График представлен на рисунке 1.17.

Результат: решение находится в данной ячейке, минимум суммы модулей функции равен 121.1125 и достигается в узле №83.

1,4

u-

1,0-

0,8-

0,6-

0,4-

0,2 -

fU

1,5

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

91xj -38xjx22 -91х2 — 4xj2X2 -20х22 +62 = 0 |-79х,2 + 38X,X22 - 44xj2X2 + 5х2 +156 = 0 График представлен на рисунке 1.18.

Результат: решение находится в данной ячейке, минимум суммы модулей функции равен 25.7375 и достигается в узле №76.

1,5

0,5

"Л-1-1-1-1-1-1 | I-1 I-1' |

0,5 1 1,5

x

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

-40л:,2 - 79х,х22 - 54х,2х2 - 5х2 +178 = 0 75х, - 72х,х22 + 47х2 - 10х,2х2 + 9х22 - 49 = 0 График представлен на рисунке 1.19.

Результат: решение находится в данной ячейке, минимум суммы модулей функции равен 16.8105 и достигается в узле №75.

1,5

1 -

0,5-

\

—i— 0,5

—I

1,5

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

-101х,2 +11х,х22 -39х,2х2 + 92х2 -165 = О [б1х, + 62х,х22 + 73х2 +44х,2х2 + 92х22 -148 = 0 График представлен на рисунке 1.20.

Результат: решение находится в данной ячейке, минимум суммы модулей функции равен 3.80975 и достигается в узле №74.

у

0,5-

0-'—I—|—I—|—I—|—I—1—I—|—I—>—I—|—I—1—I—>—I

0,6 0,7 0,8 0,9 1,0 1,1 1,2 1,3 1,4 1,5 х

Рисунок 1.20 - График нулевых линий уровня 86х3х2х1 +1 8х3х2 - 62х32 -Збх, - 61 х\хх +61 = 0 < 154х2 + 27х3х2х, - 81х22 + 23х3х2 -123 = 0

18х,х2 - 94х32 - 88х2х2 + 28х3х2х, + 78х3х2 +58 = 0 Результат: решение находится в данной ячейке, минимум суммы модулей

функции равен 19.5471 и достигается в узле №524.

-29х2х, +11х2 - 4 - З2х3х2х, + 54х2х2 = 0 •! 29х23х1х] -76х3х2х1 -66х, -9х3х2 + 79х3х2х2 + 43 = 0

35х2 + 82х2х2 - 81х, + 69х2 - 99х3х2х, -6 = 0 Результат: решение находится в данной ячейке, минимум суммы модулей

функции равен 7.94 и достигается в узле №38.

5х4х32 + 45х4х2 + 88х42;Сзх,2 + 6х22 + 33х42хзх2х, -177 = О

32I 67х3 — 3 11 * 3 Вх^ I ¡х^ 1 115 — О

79х4х3х2х2 -55х3 -91х3х2 -55х4х3 -43х4х3х2 +165 = О 40х2х2х2 + 14х2х3х2 - 43х2х2х2 + 41х3х2 + 36х2х2х2 - 88 = О

Результат: решение находится в данной ячейке, минимум суммы модулей функции равен 25.489 и достигается в узле №10237.

-60х4х2х2 -17х2 + 88х2х2х2 +71х4х, -77х1 - 5 = 0 -97х4х3Х2 -68х2х2х2 +81х42х32х, -51х4х, + 93х2Х2 +42 = 0 -87х3х2 + 48х4х3х2х2 + 86х4х2х12 + 10х3х2х2 + 76х2х2 -133 = 0 -57х3 + х4х2х2 + 26х42х3х2х2 +88х4х3х2 -36х4х2х2х1 -22 = 0

Результат: решение находится в данной ячейке, минимум суммы модулей функции равен 25.514 и достигается в узле №9039.

-94х4х3х2х2 + 75х4х3х2х2 + 88х4х3х2 -64х2х4х3х2х1 +10х5х4 -15 = 0 3гХ| ™™ З^х^х^^ "I ^ ^ 1 "I- 3х^х^ 100 0

« —54х2х2 -29х2х4х3х2 + 58х5х2х3х1 + 89х2х4х2 + 80х4х32х2 -144 = 0 -96х2х2 + 40х5х4х3х2х2 + 38х5х4х3х2 + 49х3х2х, + З5х5х4х32х2х1 — 66 = 0 -69х2х2 + 63х5х4х, + Зх4х3 + 38х4х2х2 + 50х5х2 -85 = 0

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

-53х2х4х2 -24х2х3х2 -69х2х4х2х, +68х5х2х2 - 44х6х4х2х2х, +122 = 0 89х3х2х2 — 82х2х2х1 - 86х6х2х4х3х2х2 +70х4х2х2 -95х2х5х2х2 +104 = 0 I хъ I 92хв х^ ^2 ^ 32*х^х^ х^ I 90х^ ^4 207 0

<

7х^ х^х^ х^х^ 11 х^х^ х^ ^ "I- 4 ~145 — 0

1х^ х^ х3 ™™ 1 ^^^б52х5хах3х2 I ^^2 ^ ^59 --** 0 3 5х^х^х^х^х2 I" 50х^ х^х^ I 5 х^ ! 72х^ Х^Х2Х|_ х^х^ х^х^ ™™ 168 0

Результат: решение находится в данной ячейке, минимум суммы модулей функции равен 29.691 и достигается в узле №1078680.

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

1.6. Выводы

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

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

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

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

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

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

Исследование показало, что реализация метода требует значительных вычислений. Однако метод обладает свойством естественного параллелизма, что позволяет эффективно использовать многопроцессорные системы [53]. А именно, следуя идее метода «выхода в (п+1)-мерное пространство», можно поделить область на подобласти, количество которых кратно количеству процессоров (или процессоров х ядра, если учитывать многоядерность процессора), и поручить каждому процессору работу со своей группой подобластей [50]. Тем самым время счета уменьшается пропорционально количеству процессоров.

Глава 2. Некоторые сведения из топологии

В данной главе будут приведены некоторые определения, теоремы и их следствия из топологии, взятые из [3,4,10,12,15,27,30,35-38,49,57]. Данные сведения потребуются в главе 3 и главе 4. Гомотопные отображения

Пусть задано два непрерывных отображения С\ и С2 компакта^в компакт У Скажем, что отображения С\ и С2 гомотопны, если существует деформация С(х,9), переводящая пары точек х и 0, где хе X, а бе [а,Ь] в компакт У таким образом, что С(х,а)=С\(х), а С(х,Ь)=С2(х).

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

Барицентрические координаты

Плоскость К(ао,..., аг) состоит из тех точек пространства К", которые могут быть представлены в виде я=|1{А) +..

При дополнительном условии, что • -+Цг=1 •

Числа однозначно определённые точкой а, называют

барицентрическими координатами точки а в координатной системе (а0,...,аг). Это обозначение, введенное Ф.А. Мебиусом, имеет следующее

основание: под "материальной точкой" пространства Я" понимают точку с отнесенным к ней действительным числом а - "массой" материальной точки.

Если даны материальные точки я,- с массами о,и [I =-—-, то точка а есть

а,+... + аг

по определению центр тяжести этого распределения масс. При этом числа а,-могут и не быть положительными. Они могут быть любыми действительными числами, удовлетворяющими условию: а0+...+о,^0.

/2-мерный симплекс

Пусть в /и-мерном евклидовом пространстве Ят даны п+1 линейно независимые точки 0<п<т в силу линейной независимости, эти точки

определяют «-мерную плоскость Я"(ео,е1,...,е„)<^Дт и в ней систему барицентрических координат. Те точки плоскости ],...,£„), все

барицентрические координаты которых Цо^ь.-^Ц-« в системе (ео,еи...,еп) положительны, по определению образуют «-мерный симплекс 7"=! ей,е\,...,еп \ с вершинами е0,еи...,е„.

Список литературы диссертационного исследования кандидат наук Фомочкина, Анастасия Сергеевна, 2014 год

Список литературы

1. Абаффи, Й., Математические методы для линейных и нелинейных уравнений: Проекционные ABS-алгоритмы: Пер. с англ./ Й Абаффи, Э. Спедикато. - М.: Мир, 1996.-268 с.

2. Алгазин, С.Д. Численные алгоритмы без насыщения в классических задачах математической физики/ С.Д. Алгазин. - М.: Научный Мир, 2002.-155 с.

3. Александров, П.С. Комбинаторная топология/ П.С. Александров. - М.: Государственное издательство технико-теоретической литературы, 1947. -660 с.

4. Александров, П.С. Введение в теорию размерности / П.С. Александров, В.А. Пасынков. — М.: Наука, 1973. — 576 с.

5. Андреев, А.Н. Кластеры и суперкомпьютеры - близнецы или братья?/ А.Н. Андреев, Вл.В. Воеводин, С.А. Жуматий //Открытые системы. - 2000. - №5-6. -С. 9-14.

6. Антонов, A.C. Эффективная адаптация последовательных программ для современных векторно-конвейерных и массивно-параллельных супер-ЭВМ/ A.C. Антонов, Вл.В. Воеводин // Программирование. - 1996. - №4. - С.37-51.

7. Арнольд, В.И. Обыкновенные дифференциальные уравнения/ В.И. Арнольд. -Ижевск: Ижевская республиканская типография, 2000. - 368 с.

8. Арнольд, В.И. Дополнительные глава теории обыкновенных дифференциальных уравнений/ В.И. Арнольд. - М: Наука,1978.- 304 с.

9. Баландин, М.Ю. Методы решения СЛАУ большой размерности/ М.Ю. Баландин, Э.П. Шурина. - Новосибирск: Изд-во НГТУ, 2000. - 70 с.

10. Баскаков, А.Г. Сжимающие отображения и решение нелинейных уравнений/ А.Г. Баскаков// Соросовский образовательный журнал. - М- 1997. - №5. -С. 118-121.

11. Бахвалов, Н.С. Численные методы (анализ, алгебра, обыкновенные дифференциальные уравнения)/ Н.С. Бахвалов. -М: Наука, 1975. - 631 с.

12. Босс, В. Лекции по математике. Нелинейные операторы и неподвижные точки: учебное пособие. / В.Босс. - 2-е изд., М.: Книжный дом «ЛИБРОКОМ», 2011.-224 с.-15т.

13. Васильев, Ф.П. Численные методы решения экстремальных задач. /Ф.П. Васильев. - 2-е изд., перераб. и доп.- М.: Наука. Гл.ред.физ.-мат.лит., 1988. -552 с.

14.Ващенко, Г.В. Вычислительная математика. Основы алгебраической и тригонометрической интерполяции/Г .В. Ващенко. - Красноярск: СибГТУ, 2008. - 64 с.

15. Виро, О .Я. Элементарная топология/ О .Я. Виро, O.A. Иванов, Н.Ю. Нецветаев, В.М. Харламов - М: МЦНМО, 2012. - 358 с.

16. Воеводин, В.В. Теория и практика исследования параллелизма последовательных программ/В .В. Воеводин.// Программирование. - 1992. -№3.-С. 38-53.

17. Гливенко, Е.В. Использование персональных компьютеров для анализа параллельных алгоритмов геометрической интерпретации задачи/ Е.В. Гливенко, И. Заооль //Вопросы радиоэлектроники. -2005. - №1- С. 71-73.

18. Гливенко, Е.В. Математическое моделирование в нефтегазовом деле: учебное пособие/ Е.В. Гливенко. - М.: МАКС Пресс, 2009. - 172 с.

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

20. Гливенко, Е.В. Многопроцессорные компьютеры и математическое моделирование./ Е.В. Гливенко, А.К. Козлова //Вопросы радиоэлектроники. -2007.-№4.-С. 7-10.

21.Гливенко, Е.В. О параллельных алгоритмах геометрической интерпретации/ Е.В. Гливенко, В.Л Демьянов. // Информационные технологии. - 2000 г. - № 3.

22. Гливенко, Е.В. Параллельные вычисления при разведке и разработке залежей нефти и газа/ Е.В. Гливенко. - М.: МАКС Пресс, 2010.- 180 с.

23. Гливенко, E.B. Параллельный процессор первичной обработки информации / Е.В. Гливенко. - М.: Радио и связь, 1992. - 105 с.

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

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

26. Головкин, Б.А. Параллельные вычислительные системы / Б.А. Головкин. -М.: Наука, 1980.-520 с.

27. Данилов, В.И., Лекции о неподвижных точках / В.И. Данилов. - М: Российская экономическая школа, 2006 г. - 30 с.

28. Джонсон К. Численные методы в химии/ К.Джонсон. - М.: Мир, 1983.

29. Демьянов, В.Л. Разработка и исследование параллельных методов для решения некоторых типовых задач: дис. ... канд.тех.наук: 05.13.18/ Демьянов Валерий Лукьянович. - М.,2002. - 136 с.

30. Дубровин, Б.А. Современная геометрия. Методы и приложения. Издание второе, переработанное / Б.А. Дубровин, С.П Новиков., А.Т. Фоменко. - М: «Наука», Главная редакция физико-математической литературы, 1986. - 760 с.

31. Дэннис Дж. Численные методы безусловной оптимизации и решения нелинейных уравнений: Пер. с англ. /Дж. Дэннис, мл., Р. Шнабель. - М.: Москва, 1988.-440 с.

32. Ильин, В.П. Методы и технологии конечных элементов/ В.П. Ильин. -Новосибирск: Изд-во ИВМиМГ СО РАН, 2007.

33. Иткин, В.Ю. Математические методы пространственных траекторий при проектировании кустовых скважин: дис. ...канд.тех.наук: 05.13.18/ Иткин Виктор Юрьевич. - М., 2004.

34. Краснопольский, Б.И. Исследование эффективности переупорядоченного метода BICGSTAB на вычислительных системах СКИФ МГУ «Чебышев» и «Ломоносов»/ Б.И. Краснопольский// Вестник Южно-Уральского

государственного университета. Серия: Математическое моделирование и программирование. - 2011. - №4.

35. Красносельский, М.А. Геометрические методы нелинейного анализа / М.А. Красносельский, П.П. Забрейко. - М: «Наука», Главная редакция физико-математической литературы, 1975. - 512 с.

36. Красносейльский, М.А. Векторные поля на плоскости/ М.А. Красносельский. -М.: Физматгиз, 1963. - 248 с.

37. Куратовский, К. Топология / К.Куратовский. М.: Мир, 1966 - 595с. - т.1.

38. Куратовский, К. Топология / К.Куратовский. М.: Мир, 1969- 624с. - т.2.

39. Максимов, Д.Ю.Исследование нелинейных многосеточных методов решения задач однофазной фильтрации / Д.Ю. Максимов, М.А. Филатов// Препринты ИПМ им. М.В.Келдыша. - 2011. - № 43. - 26 с.

40. Мухтарулин, B.C. Использование многопроцессорных компьютеров в научных исследованиях /B.C. Мухтарулин/ЛЗопросы радиоэлектроники. -2011.- №4.-С. 5-8.

41. Ортега, Дж. Итерационные методы решения нелинейных систем уравнений со многими неизвестными /Дж. Ортега, В.М. Рейнболдт . -М.: Мир, 1975 - 560с.

42. Пасконов, В.М. Численное моделирование процессов тепло- и массообмена /В.М. Пасконов, В.И. Полежаев, JI.A. Чудов. - М.: Наука, 1984. - 372 с.

43. Полянин, А.Д. Методы решения нелинейных уравнений математической физики и механики/А.Д. Полянин, В.Ф. Зайцев, А.И. Журов. -М.: Физматлит, 2005.-256 с.

44.Савотченко, С.Е. Методы решения математических задач в Maple: Учебное пособие / С.Е. Савотченко, Т.Г. Кузьмичева. - Белгород: Изд. Белаудит, 2001. - 116 с.

45. Самарский, A.A., Методы решения сеточных уравнений/ A.A. Самарский, Е.С. Николаев. - М.: Наука, 1978.

46.Сдвижков, O.A. Математика на компьютере: Maple 8/ O.A. Сдвижков - М.: Солон-пресс, 2003. - 175 с.

О ü/7

47. Сегерлинд, JI. Применение метода конечных элементов/ Л.Сегерлинд. - М.: Мир, 1979.-393 с.

48.Семушин, И.В. Вычислительные методы алгебры и оценивания: учебное пособие / И.В. Семушин. - Ульяновск: УлГТУ, 2011. - 366 с.

49. Скопенков, А.Б. Алгебраическая топология с элементарной точки зрения/ А.Б. Скопенков. -М.:МНЦМО, 2005. -127 с.

50.Таненбаум Э., Распределенные системы. Принципы и парадигмы/ Э. Таненбаум, М. ван Стеен. — СПб.: Питер, 2003. — 877 с.

51. Тыртышников Е.Е. Методы численного анализа /Е.Е. Тыртышников. - М.: Издательский центр «Академия», 2007. - с. 61.

52. Уоллис, Г. Одномерные двухфазные течения/ Г.Уоллис. - М.: Мир, 1972. -440 с.

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

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

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

56. Форсайт, Дж. Численное решение систем линейных алгебраических уравнений. / Дж. Форсайт., К. Молер; перевод с английского В.П. Ильина и Ю.И. Кузнецова; под редакцией Г.И. Марчука. - М.: Мир, 1969. - 168 с.

57. Шашкин, Ю.А. Неподвижные точки / Ю.А. Шашкин. - М: «Наука», Главная редакция физико-математической литературы. -1989. - 80 с.